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

Для цього перерозподілимо вантаж: обираємо чорну клітинку з найменшим значенням С^’_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.

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

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

U­i

U­1 = 0

U­2 = -2

-1

U­3 = -5

М

-2

U­4 = -6

V­j

V­1 = 6

V­2 = 4

V­3 = 6

V­4 = 6

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

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 ум.од.

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

№№ 301 – 400 Знайти оптимальний розв’язок транспортної задачі, якщо задані витрати на перевезення одиниці вантажу від постачальників А₁, А₂, А₃ до споживачів В₁, В₂, В₃, В₄, запаси постачальників і потреби споживачів за даними таблиці.

Варіант	Запаси	Потреби споживачів	Витрати на перевезення одиниці вантажу
А1	А2	А3
А1	А2	А3	В1	В2	В3	В4	В1	В2	В3	В4	В1	В2	В3	В4	В1	В2	В3	В4
301.
302.
303.
304.
305.
306.
307.
308.
309.
310.
311.
312.
313.
314.
315.
316.
317.
318.
319.
320.
321.
322.
323.
324.
325.
326.
327.
328.
329.
330.
331.
332.
333.
334.
335.
336.
337.
338.
339.
340.
341.
342.
343.
344.
345.
346.
347.
348.
349.
350.
351.
352.
353.
354.
355.
356.
357.
358.
359.
360.
361.
362.
363.
364.
365.
366.
367.
368.
369.
370.
371.
372.
373.
374.
375.
376.
377.
378.
379.
380.
381.
382.
383.
384.
385.
386.
387.
388.
389.
390.
391.
392.
393.
394.
395.
396.
397.
398.
399.
400.

Дата добавления: 2014-10-15