18. Перетворення планів т-задачі. Цикли т-задачі.

Перенести якусь кількість продукції (од.вантажу) означає збільшити перевезення в вершинах зі значенням «+» і зменшити перевезення у вершинах зі знаком «-».

З перенесення одиниць вантажу по циклу рівновага між замовленнями і запасами зберігаються: сума перевезень у кожному рядку = запасам цього рядка, а сума перевезень у кожному стовбчику дорівнює = запасам по цьому стовбчику. Отже за будь-якого циклічного перетворення, що залишає невідємним ці перевезення , опорний план залишається допустимим планом. Сумарна вартість усього плану перевезень може змінбватись, збільшуватись або зменшуватись.

ПП ПВ	В1	В2	В3	В4	В5	В6	Запаси ai
А1	c11	c12	с13	c14 +	с15	с16 ^–	a1
А2	c21 ^+	c22	с23 ^–	c 24	с25	с26	a2
А3	с31	с32	с33	с34 ^+	с35 ^–	с36	а3
А4	с41 ^–	с42	с43 ^+	с44 ^–	с45	с46 +	а4
А5	с51	с52	с53	c54 ^–	с55 +	с56	а5
Замовлення bj	b1	b2	b3	b4	b5	b6

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

Наприклад, для циклів зображених в табл, ціна циклів відповідно дорівнює:

с₂₁ – с_{2 3}+ с₄₃ – с₄₁ і с₁₄ – с₁₆ + с₄₆ – с₄₄ + с₃₄ – с₃₅ + с₅₅ – с₅₄.

Позначимо ціну циклу через r. Із переміщенням одиниці вантажу по циклу вартість перевезення збільшиться на величину r; із переміщенням по ньому k одиниць вантажу вартість перевезень збільшиться на kr. Звідси випливає: щоб поліпшити план перевезень, треба здійснювати перевезення тими циклами, ціна яких від’ємна. Якщо кожного разу вдасться здійснити таке переміщення, то вартість плану зменшиться на величину kr.

Оскільки перевезення не можуть бути від’ємними, будемо користуватися лише тими циклами, «від’ємні» вершини яких лежать у базових клітинках таблиці. Якщо циклів з від’ємними числом r у таблиці не залишилося, це означає, що подальше поліпшення плану не можливе, тобто задачі розв’язані:

, ,