Поліпшуємо опорний план.

Для цього перерозподілимо вантаж: обираємо чорну клітинку з найменшим значенням С^’_ij­­­­­ - С_{ij­­­­­­}, тобто так як min {7-4, 4-2}= 2 = С^’_22­­, то обираємо клітинку (2;2) і утворюємо від неї ламану за правилом:

1. ламана повинна бути зв’язною, тобто з будь-якої її вершини можна перейти в другу по ланках ламаної;

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

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

Пересуваємо в обрану клітинку (2;2) вантаж, для цього:

1. вибираємо мінімальне значення серед клітин ламаної, що мають знак “-”. У нашому прикладі min = {65; 35} = 35.

2. з клітин, що мають знак “-” віднімаємо 35, в клітинки, що мають знак “+” 35 додаємо, отримуємо табл.6.

Таблиця 6.

Запаси в пунктах відправлення a­ij

Потреби в пунктах призначення b­j

U­i

85

--

+

U­1 = 0

35

+

--

U­2 = -2

-1

U3 = -5

М

-2

U4 = -6

V­j

V­1 = 7

V­2 = 4

V­3 = 6

V­4 = 6

Витрати С на перевезення для отриманого опорного плану становлять: С = 10*7+30*4+45*6+35*2+20*1=550 ум.од.

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

U₁ + V₁ = 7, U_1­ + V_2­ = 4, U₁ + V₃ = 6, U₂ + V₂ = 2, U₃ + V₃ = 1, U₄ + V₃ = 0, U₄ + V₄ = 0.

Задаємо U₁ = 0 і однозначно отримуємо, що V₁=7, V₂=4, V₃=6, V₄=6, U₂ =-2, U₃= -5, U₄ = -6.

Обчислюємо побічні вартості С^’_ij­ і порівнюємо їх з вартостями С_ij одиниці перевезень вантажу з i в j.

С^’_21­­­ = U­₂ + V­_1­ = -2+7 = 5 > 4, С^’₃₁ = U­₃ + V­_1­ = -5+7 = 2<5, С^’₄₁ = U­₄ + V­_1­ = -6+7 = 1<M (М – велике число)

С^’_32­­­ = U­₃ + V­_2­ = -5+4 = -1 < 2, С^’₄₂ = U­₄ + V­_2­ = -6+4 = -2<0, С^’₂₃ = U­₂ + V­_3­ = -2 +6= 4<6,

С^’_14­­­ = U­₁ + V­_4­ = 0+6 = 6< 8, С^’₂₄ = U­₂ + V­_4­ = -2+6 = 4<7, С^’₃₄ = U­₃ + V­_4­ = -5+6 = 1<5.

Опорний план не оптимальний, тому поліпшуємо його: вибираємо чорну клітинку (2;1) і переміщуємо вантаж min = {10; 35} = 10 по ламаній: (2;1)→(1;1)→(1;2)→ (2;2)→(2;1) за вказаним правилом. Отримуємо таблицю 7.

Таблиця 7.

Перевіримо знайдений план на оптимальність, складаємо систему рівнянь:

U₂ + V₁ = 4, U_1­ + V_2­ = 4, U₂ + V₂ = 2, U₁ + V₃ = 6, U₃ + V₃ = 1, U₄ + V₃ = 0, U₄ + V₄ = 0.

з якої поклавши U₁ = 0 однозначно знаходимо V₁=6, V₂=4, V₃=6, V₄=6, U₂ =-2, U₃= -5, U₄ = -6.

Обчислюємо С^’_ij­ та С_ij і порівнюємо ці величини.

С^’_11­­­ = U­₁ + V­_1­ = 0+6 = 6< 7, С^’₃₁ = U­₃ + V­_1­ = -5+6 = 1<5, С^’₄₁ = U­₄ + V­_1­ = -6+6 = 0<M (М – велике число)

С^’_32­­­ = U­₃ + V­_2­ = -5+4 = -1 < 2, С^’₄₂ = U­₄ + V­_2­ = -6+4 = -2<0, С^’₂₃ = U­₂ + V­_3­ = -2 +6= 4<6,

С^’_14­­­ = U­₁ + V­_4­ = 0+6 = 6< 8, С^’₂₄ = U­₂ + V­_4­ = -2+6 = 4<7, С^’₃₄ = U­₃ + V­_4­ = -5+6 = 1<5.

Серед С^’_{ij­ ­}немає таких, щоб С^’_ij­ <С_ij­, тому план – оптимальний.

Витрати С на перевезення для оптимального плану становлять:

С = 10*4+40*4+25*2+45*6+20*1=540 ум.од.

ЗАВДАННЯ ДЛЯ САМОСТІЙНОГО ВИКОНАННЯ