Цикли перерахунку транспортної задачі

Перехід від одного опорного плану до іншого виконують заповненням небазисної клітинки, для якої порушена умова оптимальності. Якщо окреслених клітинок кілька, то для заповнення вибирають таку, що має найбільше порушення, тобто max{ . Для вибраної порожньої клітинки будують цикл перерахунку.

Циклом у транспортній задачі називають замкнену ламану лінію, сторони якої проходять уздовж рядків і стовпчиків таблиці, і одна з вершин якої знаходиться в небазисній клітинці, для якої порушена умова оптимальності, а всі інші вершини - базисні клітинки.

Перерозподіл продукції в межах циклу здійснюють за такими правилами:

а) кожній вершині циклу приписують певний знак, причому незаповненій клітинці знак «+», а всім іншим по черзі знаки «-» та «+»;

б) у порожню клітинку заносять найменше з чисел, що стоять у клітинках зі знаком «-». Одночасно це число додають до відповідних чисел, що стоять у клітинках зі знаком «+» і віднімають від чисел, що розміщені у клітинках зі знаком «-».

Отже, клітинка, що була вільною, стала заповненою, а відповідна клітинка, де знаходилося найменше число (у вершині з «-») стала незаповненою. В результаті такого перерозподілу продукції ми отримаємо новий опорний план транспортної задачі, який знову перевіряємо на оптимальність. Якщо розв’язок оптимальний, то обчислюємо мінімальне значення цільової функції (мінімальну вартість перевезення всього вантажу), а якщо неоптимальний, то знову будуємо цикл перерахунку і з допомогою зсуву по циклу переходимо до нового опорного плану. Процес повторюють до тих пір, доки не отримаємо оптимального розв’язку транспортної задачі.

Значення базисних клітинок, які не брали участі в циклі перерахунку, в новій таблиці залишаються без змін.

Якщо на деякому кроці потреби співпадають із запасами, то в потребах ставимо дійсний нуль, а в запасах – фіктивний (нуль з крапкою – О). Тоді одразу будується повна система рівнянь для знаходження значень потенціалів.

У задачах з виродженим планом часто зсув стосовно циклу треба робити на 0. Тоді при переході до наступної таблиці значення базисних клітинок, що брали участь в циклі перерахунку, не змінилося. Тільки цей «базисний нуль» переводять у небазисну клітинку, для якої по суті робили цикл перерахунку, а клітинка, в якій знаходився цей 0, стає вільною.