овнюємо нулями (щоб було видно, що вони не входять до плану).
Отриманий план буде ациклічним і буде складатися не більше ніж з k + l -1 компонент. Цей план і приймаємо за вихідний. Він буде краще плану, побудованого за способом північно-західного кута, і для знаходження оптимуму потрібно менше обчислень. [5]
7. Перехід від одного опорного рішення до іншого
Числа і називають потенціалами. У розподільну таблицю додають рядок і стовпець. Потенціали і знаходять з рівності , Справедливого для зайнятих клітин. Одному з потенціалів дається довільне значення, а інші потенціали визначаються однозначно. Якщо відомий потенціал, то, якщо відомий потенціал , То. p> Позначимо, яку називають оцінкою вільних клітин. Якщо всі оцінки вільних клітин, то опорне рішення є оптимальним. Якщо хоча б одна з оцінок, то опорне рішення не є оптимальним і його можна поліпшити, перейшовши від одного опорного рішення до іншого.
Наявність позитивної оцінки вільної клітини () при перевірці опорного рішення на оптимальність свідчить про те, що отримане рішення не оптимально і для зменшення значення цільової функції треба перейти до іншого опорного рішенням. При цьому треба перерозподілити вантажі, переміщаючи їх із зайнятих клітин у вільні. Вільна клітина стає зайнятою, а одна з раніше зайнятих клітин - вільною.
Для вільної клітини з будується цикл (ланцюг, багатокутник), всі вершини якого, крім однієї, знаходяться в зайнятих клітинах; кути прямі, число вершин парне. Близько вільної клітини циклу ставиться знак (+), потім по черзі проставляють знаки (-) І (+). У вершин із знаком (-) вибирають мінімальний вантаж, його додають до вантажів, що стоять біля вершин зі знаком (+), і віднімають від вантажів у вершин із знаком (-). В результаті перерозподілу вантажу отримаємо нове опорне рішення. Це рішення перевіряємо на оптимальність і т.д. до тих пір, поки не отримаємо оптимальне рішення. [7]
8. Розподільний метод
Розподільчий метод вирішення транспортної завдання відрізняється від методу потенціалів деякою зміною обчислювального процесу і іншим (за формою) критерієм оптимальності.
Алгоритм розподільного методу полягає в наступному.
1. Відшукуємо первісний ациклічний план, що містить ( k + l -1) компонент (при нестачі компонент дописуємо нулі).
2. Включаємо в набір вільну клітину, будуємо для неї цикл, означивающей його, приписуючи вільної клітці знак плюс, і обчислюємо по цих знаках алгебраїчну суму тарифів, що стоять у всіх вершинах циклу. Отримане число з його знаком записуємо всередині вільної клітини.
3. Проробляємо зазначену в п.2 операцію для кожної вільної клітини, будуючи щоразу свій цикл перерахунку. В результаті в кожній вільній клітці з'явиться число (позитивне, негативне або нуль).
4. Якщо всі отримані числа ненегативні, то з...
