ь (здійснюється зсув по циклу). Перевезення В«завантажуєтьсяВ» в обрану вільну клітину і звільняється одна із зайнятих клітин, виходить нове опорне рішення.
Якщо таблиця транспортної задачі містить опорне рішення, то для будь-якої вільної клітини таблиці існує єдиний цикл, що містить цю клітку і частина клітин, зайнятих опорним рішенням.
Для зручності обчислень вершини циклів нумерують і відзначають непарні знаком В«+В», а парні знаком В«-В». Такий цикл називається зазначеним. <В
Зрушенням по циклу на величину називається збільшення обсягів перевезень у всіх непарних клітинах циклу, відмічених знаком В«+В», Та зменшення обсягів перевезень на ту ж величину під всіх не парних клітинах, відмічених знаком В«-В».
1.2.3 МЕТОД ПОТЕНЦІАЛІВ
Широко поширеним методом вирішення транспортних завдань є метод потенціалів.
Якщо допустиме рішення, i = 1,2, ..., m; j = 1,2, ... n транспортної задачі є оптимальним, то існують потенціали (числа) постачальників i = 1,2, ..., m і споживачів j = 1,2, ..., n, яке задовольняє наступним чином:
В
Група рівностей (2.1) використовується як система рівнянь для знаходження потенціалів. Дана система рівнянь має m + n невідомих i = 1,2, ..., m і j = 1,2, ..., n. Число рівнянь системи, як і число відмінних від нуля координат невиродженого опорного рішення, так само m + n-1. Так як число невідомих системи на одиницю більше числа рівнянь, то одній з них можна задати значення довільно, а інші знайти з системи.
Група нерівностей (2.2) використовується для перевірки оптимальності опорного рішення. Ці нерівності зручніше представити в наступному вигляді:
(2.3)
Числа називаються оцінками для вільних клітин таблиці (векторів умов) транспортної задачі.
Опорна рішення є оптимальним, якщо для всіх векторів умов (клітин таблиці) оцінки недодатні.
Оцінки для вільних клітин транспортної таблиці використовуються при поліпшенні опорного рішення. Для цього знаходять клітку (l, k) таблиці, відповідну. Якщо, то рішення оптимальне. Якщо ж, то для відповідної клітини (l, k) будують цикл і покращую рішення, перерозподіляють вантаж
по цьому циклу.
Алгоритм вирішення транспортних завдань методом потенціалів:
1. Перевірити виконання необхідного і достатнього умови розв'язності задачі. Якщо завдання має неправильний баланс, то вводиться фіктивний постачальник або споживач з відсутніми запасами або запитами і нульовими вартостями перевезень.
2. Побудувати початкове опорне рішення (методом мінімальної вартості або яким-небудь іншим методом), перевірити правильність його побудови за кількістю зайнятих клітин (Їх має бути m + n-1) і переконатися в лінійній незалежності векторів умов (використовується метод викреслювання).
3. Побудувати систему потенціалів, відповідних опорному рішенням. Для цього вирішують систему рівнянь:
В
яка має нескінченну безліч рішень. Для знаходження...
