На цьому способі зменшення вартості в подальшому і буде заснований алгоритм оптимізації плану перевезень. Циклом в транспортній задачі ми будемо називати кілька зайнятих клітин, з'єднаних замкнутої, ламаної лінією, яка в кожній клітині робить поворот на 90 В°. Існує кілька варіантів циклу:
.) 2.) 3.)
В
Неважко переконатися, що кожен цикл має парне число вершин і значить, парне число ланок (стрілок). Домовимося відзначати знаком + ті вершини циклу, в яких перевезення необхідно збільшити, а знаком - , ті вершини, в яких перевезення необхідно зменшити. Цикл із зазначеними вершинами будемо називати зазначеним. Перенести якусь кількість одиниць вантажу по зазначеному циклу, це означає збільшити перевезення, що стоять в позитивних вершинах циклу, на цю кількість одиниць, а перевезення, що стоять в негативних вершинах зменшити на ту ж кількість. Очевидно, при переносі будь-якого числа одиниць по циклу рівновагу між запасами і заявками не змінюється: по колишньому сума перевезень у кожному рядку дорівнює запасам цього рядка, а сума перевезень в кожному стовпці - заявці цього стовпця. Таким чином, при будь-якому циклічному перенесення, який полишає перевезення невід'ємними, допустимий план залишається допустимим.
Вартість же плану при цьому може змінюватися: збільшуватися або зменшуватися. Назвемо ціною циклу збільшення вартості перевезень при переміщенні однієї одиниці вантажу по зазначеному циклу. Очевидно, ціна циклу рівна алгебраїчної сумі вартостей, що стоять у вершинах циклу, причому стоять в позитивних вершинах беруться зі знаком + , а в негативних зі знаком - . Позначимо ціну циклу через g.
При переміщенні однієї одиниці вантажу по циклу вартість перевезень збільшується на величину g. При переміщенні по ньому k одиниць вантажу вартість перевезень збільшитися на kg. Очевидно, для поліпшення плану має сенс переміщати перевезення тільки по тих циклам, ціна яких негативна. Щоразу, коли нам вдається зробити таке переміщення, вартість плану зменшується на відповідну величину kg. Так як перевезення не можуть бути негативними, ми будемо користуватися лише такими циклами, негативні вершини яких лежать в базисних клітинах таблиці, де стоять позитивні перевезення. p align="justify"> Якщо циклів з негативною ціною в таблиці більше не залишилося, це означає, що подальше поліпшення плану неможливо, тобто оптимальний план досягнутий. Метод послідовного поліпшення плану перевезень і полягає в тому, що в таблиці відшукуються цикли з негативною ціною, за ним переміщуються перевезення, і план поліпшується до тих пір, поки циклів з негатив...
