П’ята ітерація тт

	B1	B2	B3	B4	Запаси ai		ai'
A1	4 70	7	2 –	5 –	100	7-4=3	100-70=30
A2	3 10	6 –	1 110	8 –	0	К
A3	9 –	3 70	6 –	2 70	0	К
Заявки bj	70	30	0	0	100
	4-4=0 К	7-7=0	К	К
bj'	70-70=0

Таблиця 44

Шоста ітерація тт

	B1	B2	B3	B4	Запаси ai		ai'
A1	4 70	7 30	2 –	5 –	30	7-7=0 К	30-30=0
A2	3 10	6 –	1 110	8 –	0	К
A3	9 –	3 70	6 –	2 70	0	К
Заявки bj	0	30	0	0	30
	К	7-7=0 К	К	К
bj'		30-30=0

В результаті одержано (m + n - 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

у.г.о.

У додатку 15 представлений текст процедури на алгоритмічної мові Delphi побудови опорного плану перевезень вантажу методом апроксимації Фогеля.

МЕТОДИ ЗНАХОДЖЕННЯ ОПТІМАЛЬНИХ ПЛАНІВ

ПЕРЕВЕЗЕНЬ ВАНТАЖУ

1. Симплексний метод оптимізації транспортних перевезень

Існує безліч методів оптимізації ТЗ, а точніше приведення до оптимального плану перевезень складеного раніше опорного (базисного) плану. До основних належать розподільний метод, метод потенціалів, метод диференційних рент.

Оскільки ТЗ є окремим випадком загальної задачі ЛП (ЗЗЛП), то до неї також цілком можливо застосувати всі стандартні методи її розв’язання (зокрема найвідоміший з них – симплексний метод), попередньо привівши ТЗ до вигляду задачі ЛП і врахувавши її специфічність. Для цього необхідно провести над математичною моделлю ТЗ ряд перетворень. Ці перетворення будемо здійснювати на конкретному прикладі ТЗ, а саме для m постачальників (m=3) і n споживачів продукції (n=4) (див. табл. 1).

а) спочатку запишемо вихідну систему рівнянь ТЗ у такому вигляді:

|| || || ||

b₁ b₂ b₃ b₄

де: x_ij – кількість продукції, відправленої від і-го постачальника до j-го споживача;

а_i – обсяг продукції наявної у і-го постачальника ( i=1, 2, 3);

b_j – обсяг продукції необхідної j-ому споживачу (j=1, 2, 3, 4).

б) подамо її у вигляді системи (т + n) лінійних рівнянь таким чином:

в) замінимо x₁₁ на x₁, x₁₂ на x₂, x₁₃ на x₃, . . ., x₃₄ на x₁₂. Маємо:

г) додамо, як того вимагає симплексний метод, до всіх рівнянь додаткові перемінні, які становитимуть початковий базисний розв’язок ТЗ:

У результаті цих перетворень ми утворили систему (т + п) лінійних рівнянь з (mп + т+ n) позитивними перемінними, розв’язати яку можна за допомогою симплекс-методу. Оскільки сума рівнянь системи в рядках дорівнює сумі рівнянь системи в стовпцях, то ми одержали лінійно-залежну систему рівнянь. Щоб привести її до нормального (лінійно-незалежного) виду, одне з рівнянь системи (переважно останнє) можна без шкоди для кінцевого результату розв’язку ТЗ відкинути. Тоді ми матимемо (т + п – 1) лінійних рівнянь і (mп + т+ n - 1) перемінних.

Необхідно також відзначити те, що у класичній ТЗ перевезти продукцію від усіх постачальників (а_i) потрібно так, щоб усі замовлення були виконані (b_j), а загальна вартість (L) транспортних перевезень була б мінімальною, тобто:

,

де: с₁ , с₂, ... с_k – вартість перевезення одиниці продукції від кожного постачальника до кожного споживача (k = 1,т п).

Розглянемо розв'язання ТЗ на конкретному прикладі, умови якого дані у вигляді ТТ (табл. 45) , де т = 3 , n = 4. Відповідно, кількість рівнянь становитиме (m + n – 1 ) = 6, кількість вихідних перемінних – (m × n) = 12 і кількість додаткових перемінних – (т + п – 1) = 6.

Таблиця 45

Дані ТЗ у вигляді ТТ

	B1	B2	B3	B4	Запаси ai
A1	c1 = 4 x1	c2 = 7 x2	c3 = 2 x3	c4 = 5 x4	100
A2	c5 = 3 x5	c6 = 6 x6	c7 = 1 x7	c8 = 8 x8	120
A3	c9 = 9 x9	c10 = 3 x10	c11 = 6 x11	c12 = 2 x12	140
Заявки bj	80	100	110	70	360

Запишемо умову нашої ТЗ у термінах ЗЗЛП.

Необхідно мінімізувати цільову функцію L = 4× x₁ +7 × x₂ +2 × x₃ +5 × x₄ +3 × x₅ + 6 × x₆ +1×x₇+8 × x₈ +9 × x₉ +3 × x₁₀ + 6 × x₁₁ +2×x₁₂,

за таких обмежень:

тобто кількість рівнянь становить 6, а кількість вихідних перемінних дорівнює 12.

Вводимо до обмежень нові змінні x₁₃, x₁₄, x₁₅, x₁₆, x₁₇, x₁₈. Значення відповідних коефіцієнтів впливу вибираємо набагато більші ніж існують. У нашому випадку приймемо за цю величину суму всіх коефіцієнтів при невідомих у початковій цільовій функції, тобто 56. Завдяки цьому перемінні x₁₃, x₁₄, x₁₅, x₁₆, x₁₇, x₁₈ з базисних поступово будуть переведені у вільні, що забезпечує тим самим мінімум цільової функції. Після введення нових перемінних маємо:

L = 4× x₁ +7 × x₂ +2 × x₃ +5 × x₄ +3 × x₅ + 6 × x₆ +1×x₇+8 × x₈ +9 × x₉ +3 × x₁₀ + 6 × x₁₁ +2×x₁₂+56 × x₁₃ +56 × x₁₄ +56 × x₁₅ + 56 × x₁₆ +56×x₁₇+56 × x₁₈, → min,

за обмежень

Остаточна кількість рівнянь k = 6; кількість перемінних l = 18.

За базисні обираємо x₁₃, x₁₄, x₁₅, x₁₆, x₁₇, x₁₈ і отримуємо перше базисне рішення X = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100, 120, 140, 80, 100, 110}, що забезпечує L = 56 × 100 + 56 × 120 +56 × 140 + 56 × 80 + 56 × 100 +56 × 110 = 36400 у.г.о.

Складемо першу симплекс-таблицю (СТ) – табл. 46. У першому рядку цієї таблиці знаходяться значення коефіцієнтів c_j при невідомих цільової функції; у першій графі СТ розташовані значення коефіцієнтів c_бі при базових невідомих цільової функції; друга графа містить самі базові невідомі х_бі; третя – значення базових невідомих b_бi (у першій СТ це значення правих частин останньої системи рівнянь) і частина СТ, що залишилася, крім останнього рядка, зайнята коефіцієнтами a_ij при невідомих також останньої системи рівнянь.

Останній рядок (індексний ряд) служить для розрахунків індексів ∆_j , що є характеристиками оптимальності отриманого плану. Індекси розраховуються за допомогою наступних формул:

Таблиця 46

Перша СТ

			4	7	2	5	3	6	1	8	9	3	6	2	56	56	56	56	56	56
cбі	хбі	bбі	х1	х2	х3	х4	х5	х6	х7	х8	х9	х10	х11	х12	х13	х14	х15	х16	х17	х18
56	х13	100	1	1	1	1	0	0	0	0	0	0	0	0	1	0	0	0	0	0
56	х14	120	0	0	0	0	1	1	1	1	0	0	0	0	0	1	0	0	0	0
56	х15	140	0	0	0	0	0	0	0	0	1	1	1	1	0	0	1	0	0	0
56	х16	80	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1	0	0
56	х17	100	0	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1	0
56	х18	110	0	0	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1
∆0 = 36400			∆1= 108	∆2=105	∆3=110	∆4=51	∆5=109	∆6=106	∆7=111	∆8=48	∆9=103	∆10=109	∆11= 106	∆12=54	∆13=0	∆14=0	∆15=0	∆16=0	∆17=0	∆18=0

Вважається, що отримане рішення х_бі є оптимальним, якщо .

Порахуємо значення індексів для першої СТ:

∆₀ = 56 × 100 + 56 × 120 +56 × 140 + 56 × 80 +56 × 100 + 56 × 110 = 36400 у.г.о.

∆₁ = 56 × 1 + 56 × 0 +56 × 0 + 56 × 1 +56 × 0 + 56 × 0 – 4 = 108

∆₂ = 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 1 + 56 × 0 – 7 = 105

∆₃ = 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 1 – 2 = 110

∆₄ = 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 5 = 51

∆₅ = 56 × 0 + 56 × 1 +56 × 0 + 56 × 1 +56 × 0 + 56 × 0 – 3 = 109

∆₆ = 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 1 + 56 × 0 – 6 = 106

∆₇ = 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 0 + 56 × 1 – 1 = 111

∆₈ = 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 8= 48

∆₉ = 56 × 0 + 56 × 0 +56 × 1 + 56 × 1 +56 × 0 + 56 × 0 – 9 = 103

∆₁₀ = 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 1 + 56 × 0 – 3 = 109

∆₁₁ = 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 0 + 56 × 1 – 6 = 106

∆₁₂ = 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 0 + 56 × 0 – 2 = 54

∆₁₃ = 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 56 = 0

∆₁₄ = 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 56 = 0

∆₁₅ = 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 0 + 56 × 0 – 56 = 0

∆₁₆ = 56 × 0 + 56 × 0 +56 × 0 + 56 × 1 +56 × 0 + 56 × 0 – 56 = 0

∆₁₇ = 56 × 0 + 56 × 0 +56 × 0 + 56 × 0 +56 × 1 + 56 × 0 – 56 = 0

∆₁₈ = 56 × 0 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 1 – 56 = 0

Очевидно, що базове рішення не є оптимальним, тому що усі індекси від ∆₁ до ∆₁₈ позитивні, тому продовжимо поліпшення (оптимізацію) базового плану далі.

У якості ключового стовпця, який містить внесену в базу вільну змінну, вибираємо стовпець х₇, що має максимальне позитивне значення ∆₇ = 111. Для визначення ключового рядка рахуємо відповідні відношення значень базових невідомих b_бi на не нульові значення елементів обраного ключового стовпця, а саме:

; і вибираємо з них мінімальне, тобто друге.

Тоді ключовим рядком буде шостий і він містить базову змінну х₁₈ , що виводиться з базису. Тобто змінна ключового шостого рядка базису х₁₈ має бути замінена на вільну змінну ключового стовпця х₇ , при цьому ключове число a₆₇ = 1 (це число відмічено у СТ більшим розміром). Складаємо нову СТ (див. табл. 47).

Спочатку введемо в базис замість змінної х₁₈ змінну х₇ зі значенням її коефіцієнта c₇ = 1 і розділимо всі елементи цього рядка на ключове число a₆₇ = 1. Після цього перерахуємо значення частини елементів таблиці, що залишилася, таким способом:

,

де: НЕ і СЕ – відповідно будь-який новий елемент (a_ij^н або b_i^н) з не ключового рядка і той же старий елемент (a_ij або b_i) СТ, що перетворюється;

ЕК_р і ЕК_ст – відповідно елементи ключового рядка і ключового стовпчику СТ, що перетворюється;

К – ключовий елемент СТ, що перетворюється (у нашому випадку для першої СТ це a₆₇).

Порахуємо як приклад по цій формулі нові значення b₂ , a₂₃ і a₂₇:

.

Інші елементи перенесемо в нову СТ без демонстрації аналогічних детальних розрахунків.

Як видно з таблиці 47 нове значення цільової функції дорівнює 24190 у.г.о., що значно менше попереднього її значення і, що, у свою чергу, свідчить про нормальний плин процесу оптимізації. Індексний рядок нової СТ містить позитивні елементи – це означає, що отримане значення не є оптимальним і план перевезень вимагає поліпшення. Відзначимо в СТ ключовий елемент a₂₅ і опускаючи всі розрахунки перейдемо до наступної СТ (див. табл. 48).

Таблиця 47

Друга СТ

			4	7	2	5	3	6	1	8	9	3	6	2	56	56	56	56	56	56
cбі	хбі	bбі	х1	х2	х3	х4	х5	х6	х7	х8	х9	х10	х11	х12	х13	х14	х15	х16	х17	х18
56	х13	100	1	1	1	1	0	0	0	0	0	0	0	0	1	0	0	0	0	0
56	х14	10	0	0	-1	0	1	1	0	1	0	0	-1	0	0	1	0	0	0	-1
56	х15	140	0	0	0	0	0	0	0	0	1	1	1	1	0	0	1	0	0	0
56	х16	80	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1	0	0
56	х17	100	0	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1	0
1	х7	110	0	0	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1
∆0 = 24190			∆1= 108	∆2=105	∆3= -1	∆4=51	∆5=109	∆6=106	∆7=0	∆8=48	∆9=103	∆10=109	∆11= -5	∆12=54	∆13=0	∆14=0	∆15=0	∆16=0	∆17=0	∆18= -111

Із цієї СТ також видно, що процес оптимізації триває (нове значення цільової функції дорівнює 23100), але в індексному рядку ще присутні позитивні елементи – це означає, що план перевезень вимагає подальшого поліпшення. Відзначимо також у СТ ключовий елемент a_5,10 і перейдемо до наступної СТ (див. табл. 49).

Таблиця 48

Третя СТ

			4	7	2	5	3	6	1	8	9	3	6	2	56	56	56	56	56	56
cбі	хбі	bбі	х1	х2	х3	х4	х5	х6	х7	х8	х9	х10	х11	х12	х13	х14	х15	х16	х17	х18
56	х13	100	1	1	1	1	0	0	0	0	0	0	0	0	1	0	0	0	0	0
3	х5	10	0	0	-1	0	1	1	0	1	0	0	-1	0	0	1	0	0	0	-1
56	х15	140	0	0	0	0	0	0	0	0	1	1	1	1	0	0	1	0	0	0
56	х16	70	1	0	1	0	0	-1	0	-1	1	0	1	0	0	-1	0	1	0	1
56	х17	100	0	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1	0
1	х7	110	0	0	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1
∆0 = 23100			∆1= 108	∆2=105	∆3= 108	∆4=51	∆5=0	∆6= -3	∆7=0	∆8= -61	∆9=103	∆10=109	∆11= 104	∆12=54	∆13=0	∆14= -109	∆15=0	∆16=0	∆17=0	∆18= -2

У цій таблиці також присутні позитивні елементи в індексному рядку, тому переходимо до нового СТ із новим ключовим елементом – a₄₁ (див. табл. 50).

Таблиця 49

Четверта СТ

			4	7	2	5	3	6	1	8	9	3	6	2	56	56	56	56	56	56
cбі	хбі	bбі	х1	х2	х3	х4	х5	х6	х7	х8	х9	х10	х11	х12	х13	х14	х15	х16	х17	х18
56	х13	100	1	1	1	1	0	0	0	0	0	0	0	0	1	0	0	0	0	0
3	х5	10	0	0	-1	0	1	1	0	1	0	0	-1	0	0	1	0	0	0	-1
56	х15	40	0	-1	0	0	0	-1	0	0	1	0	1	1	0	0	1	0	-1	0
56	х16	70	1	0	1	0	0	-1	0	-1	1	0	1	0	0	-1	0	1	0	1
3	х10	100	0	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1	0
1	х7	110	0	0	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1
∆0 = 12200			∆1= 108	∆2= -4	∆3= 108	∆4=51	∆5=0	∆6= -112	∆7=0	∆8= -61	∆9=103	∆10=0	∆11= 104	∆12=54	∆13=0	∆14=-109	∆15=0	∆16=0	∆17= -109	∆18= -2

У цій таблиці також присутні позитивні елементи в індексному рядку, тому переходимо до нового СТ із новим ключовим елементом – a_3,12 (див. табл. 51).

Таблиця 50

П’ята СТ

			4	7	2	5	3	6	1	8	9	3	6	2	56	56	56	56	56	56
cбі	хбі	bбі	х1	х2	х3	х4	х5	х6	х7	х8	х9	х10	х11	х12	х13	х14	х15	х16	х17	х18
56	х13	30	0	1	0	1	0	1	0	1	-1	0	-1	0	1	1	0	-1	0	-1
3	х5	10	0	0	-1	0	1	1	0	1	0	0	-1	0	0	1	0	0	0	-1
56	х15	40	0	-1	0	0	0	-1	0	0	1	0	1	1	0	0	1	0	-1	0
4	х1	70	1	0	1	0	0	-1	0	-1	1	0	1	0	0	-1	0	1	0	1
3	х10	100	0	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1	0
1	х7	110	0	0	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1
∆0 = 4640			∆1= 0	∆2= -4	∆3= 0	∆4=51	∆5=0	∆6= -4	∆7=0	∆8= 47	∆9= -5	∆10=0	∆11= -4	∆12=54	∆13=0	∆14= -1	∆15=0	∆16= -108	∆17= -109	∆18= -110

У цій таблиці також присутні позитивні елементи в індексному рядку, тому переходимо до нового СТ із новим ключовим елементом – a_1,4 (див. табл. 52).

Отримана симплекс-таблиця містить усі , завдяки чому можна стверджувати, що отримане рішення є оптимальним, тобто: х₁ = 70; х₂ = 0; х₃ = 0; х₄ = 30; х₅ = 10; х₆ = 0; х₇ = 110; х₈ = 0; х₉ = 0; х₁₀ = 100; х₁₁ = 0; х₁₂ = 40; х₁₃ = 0; х₁₄ = 0; …; х₁₈ = 0, що забезпечує L_opt = 950 у.г.о.

Представимо одержаний оптимальний план перевезень вантажу для нашого прикладу у вигляді ТТ (табл. 53).

Таблиця 51

Шоста СТ

			4	7	2	5	3	6	1	8	9	3	6	2	56	56	56	56	56	56
cбі	хбі	bбі	х1	х2	х3	х4	х5	х6	х7	х8	х9	х10	х11	х12	х13	х14	х15	х16	х17	х18
56	х13	30	0	1	0	1	0	1	0	1	-1	0	-1	0	1	1	0	-1	0	-1
3	х5	10	0	0	-1	0	1	1	0	1	0	0	-1	0	0	1	0	0	0	-1
2	х12	40	0	-1	0	0	0	-1	0	0	1	0	1	1	0	0	1	0	-1	0
4	х1	70	1	0	1	0	0	-1	0	-1	1	0	1	0	0	-1	0	1	0	1
3	х10	100	0	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1	0
1	х7	110	0	0	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1
∆0 = 2480			∆1= 0	∆2= 50	∆3= 0	∆4=51	∆5=0	∆6= 50	∆7=0	∆8= 47	∆9= -59	∆10=0	∆11= -58	∆12=0	∆13=0	∆14= -1	∆15=-54	∆16= -108	∆17= -55	∆18= -110

Таблиця 52

Сьома СТ

			4	7	2	5	3	6	1	8	9	3	6	2	56	56	56	56	56	56
cбі	хбі	bбі	х1	х2	х3	х4	х5	х6	х7	х8	х9	х10	х11	х12	х13	х14	х15	х16	х17	х18
5	х4	30	0	1	0	1	0	1	0	1	-1	0	-1	0	1	1	0	-1	0	-1
3	х5	10	0	0	-1	0	1	1	0	1	0	0	-1	0	0	1	0	0	0	-1
2	х12	40	0	-1	0	0	0	-1	0	0	1	0	1	1	0	0	1	0	-1	0
4	х1	70	1	0	1	0	0	-1	0	-1	1	0	1	0	0	-1	0	1	0	1
3	х10	100	0	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1	0
1	х7	110	0	0	1	0	0	0	1	0	0	0	1	0	0	0	0	0	0	1
∆0 = 950			∆1= 0	∆2= -1	∆3= 0	∆4= 0	∆5=0	∆6= -1	∆7=0	∆8= -4	∆9= -8	∆10=0	∆11= -7	∆12=0	∆13=-51	∆14= -52	∆15=-54	∆16= -57	∆17= -55	∆18= -59

Таблиця 53

Оптимальний план перевезень вантажу у вигляді ТТ

	B1	B2	B3	B4	Запаси ai
A1	c1 = 4 x1=70	c2 = 7 x2=0	c3 = 2 x3=0	c4 = 5 x4=30	100
A2	c5 = 3 x5=10	c6 = 6 x6=0	c7 = 1 x7=110	c8 = 8 x8=0	120
A3	c9 = 9 x9=0	c10 = 3 x10=100	c11 = 6 x11=0	c12 = 2 x12=40	140
Заявки bj	80	100	110	70	360

Нижче показаний фрагмент роботи програми (її текст на алгоритмічної мові Delphi представлений у додатку 16), яка реалізує рішення ТЗ для нашого прикладу симплексним методом. Зокрема на рис. 2. представлена діалогова форма по уведенню розмірності ТЗ, приведенню ТЗ до загальної задачі лінійного програмування, уведенню першої СТ і виконанню відповідних розрахунків нульової ітерації, а на рис. 3 – остання результуюча форма, що містить дані останньої СТ.

Рис. 2. Перша СТ

Рис. 3. Остання СТ

2. Розподільний метод оптимізації транспортних перевезень

Процес пошуку оптимального плану перевезень розподільним методом транспортної задачі розглянемо на конкретному прикладі. Нехай опорний план, отриманий за допомогою методу північно-західного кута, є такий, що наведено в таблиці 54. (Особливо відзначимо, що цей план не вироджений, тобто кількість перевезень вантажу дорівнює m+n+1. Ця обставина для розподільного методу має істотне значення, на чому ми зупинимося пізніше).

Таблиця 54

Вихідна ТТ

	B1	B2	B3	B4	Запасиai
A1	4 80	7 20	2	5	100
A2	3	6 80 	1 + 40	8	120
A3	9	3 +	6  70	2 70	140
Заявки bj	80	100	110	70	360

Після складання опорного плану стає питання, чи є цей план перевезень оптимальним ? Скоріше за все ні, тому що ми не звертали уваги на існуючі вартості перевезень одиниці вантажу від до , що значно відрізняються одна від одної.

Простежимо, як буде змінюватися план перевезень (якщо він не є оптимальним) з оцінкою кожного разу поточного значення загальної вартості перевезень. Імовірніше усього, що ця вартість має поступово зменшуватися за рахунок поліпшення плану перевезень, а спочатку вона становить:

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

Для кожного такого контуру знаходимо вартісну характеристику переміщення одиниці вантажу в незайняту клітинку (), не змінюючи баланс сум перевезень в рядках та стовпчиках. Для переміщення, наприклад, 1 одиниці вантажу (о.в.) в отримуємо збільшення вартості на у.г.о., але для збереження балансу вантажів в рядках і стовпчиках транспортної таблиці зменшуємо на 1 о.в. в клітинці , що викличе зменшення вартості перевезень на у.г.о.. Оскільки зменшується на 1 о.в., додамо в клітинку також 1 о.в., що викличе збільшення вартості перевезення на . Однак збільшення на 1 о.в. повинно призвести до зменшення на 1 о.в., тобто до зменшення вартості перевезень на . Це зменшення буде скомпенсоване раніше проведеним додаванням 1 о.в. в незайняту клітинку . Таким чином, додавання 1 о.в. в незайняту клітинку призведе до зміни вартості на величину вартісної характеристики :

Іншими словами, переміщення одиниці вантажу (або будь-якого об’єму) по контуру не викличе зміни вартості перевезень, тобто така модернізація початкового плану недоцільна. Відзначимо, що для незайнятої клітинки c_ij приймається завжди зі знаком “+”, потім за мірою просування по контуру (або в одну, або в іншу сторону – напрям проходження контуру не має значення) c_ij приймають послідовно знаки “–” потім “+”.

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

Визначаємо для всіх незайнятих клітинок:

; ;

; ;

; .

Таким чином, доцільно перерозподілити обсяги перевезень базового плану по контуру з метою завантаження клітинки , яка має . Будуємо цей контур з виказанням знаків, що послідовно міняються і позначають додавання або зменшення об’ємів перевезень по даному контуру (див. табл. 54).

Об’єм вантажу, що переміщається, визначається як мінімальний з негативних об’ємів по даному контуру (). Таким чином, переміщення вантажу по даному контуру дозволить максимально завантажити клітинку і повністю розвантажити клітинку . Очевидно, що при цьому стане рівним (80 – 70) = 10, а стане рівним (40 + 70) = 110. Інші значення для даного контуру ; .

Очевидно, що загальна вартість перевезень повинна при цьому змінитися на:

і має бути рівною

Щоб перевірити скоректований план на оптимальність, будуємо таблицю 55, що аналогічна таблиці 54 для отримання нового плану, і знову перевіряємо його на оптимальність за допомогою вартісних характеристик незайнятих клітинок.

Для отриманого плану перевезень маємо:

; ;

; ;

; .

Таблиця 55