Транспортна задача методом потенціалів. Приклад рішення

Вартість доставки одиниці вантажу з кожного пункту відправлення у відповідні пункти призначення задана матрицею тарифів

 

1

2

3

4

Запаси

1

1

2

4

3

6

2

4

3

6

7

8

3

3

2

8

2

10

Потреби

4

6

8

8

 

Перевіримо необхідна і достатня умова розв'язання задачі.
∑a = 6 + 8 + 10 = 24
∑b = 4 + 6 + 8 + 8 = 26
Як видно, сумарна потреба вантажу в пунктах призначення менше запасів вантажу на базах. Отже, модель вихідної транспортної задачі є відкритою. Щоб отримати закриту модель, введемо додаткову (фіктивну) потреба, рівним 2 (26—24). Тарифи перевезення одиниці вантажу з бази в усі магазини вважаємо дорівнюють нулю.
Занесемо вихідні дані в розподільну таблицю.

 

1

2

3

4

Запаси

1

1

2

4

3

6

2

4

3

6

7

8

3

3

2

8

2

10

4

0

0

0

0

2

Потреби

4

6

8

8

 

Етап I. Пошук перший опорного плану.
1. Використовуючи метод найменшої вартості, побудуємо перший опорний план транспортної задачі.
Суть методу полягає в тому, що з усієї таблиці вартостей вибирають найменшу, і в клітку, яка їй відповідає, поміщають менше з чисел ai, або bj.
Потім, з розгляду виключають або рядок, що відповідає постачальнику, запаси якого повністю витрачені, або стовпець, відповідний споживачеві, потреби якого повністю задоволені, або і рядок і стовпець, якщо витрачені запаси постачальника і задоволені потреби споживача.
З решти таблиці вартостей знову вибирають найменшу вартість, і процес розподілу запасів продовжують, поки всі запаси не будуть розподілені, а потреби задоволені.
Шуканий елемент дорівнює 1
Для цього елемента запаси рівні 6, потреби 4. Оскільки мінімальним є 4, то віднімаємо його.
x11 = min(6,4) = 4.

1

2

4

3

6 - 4 = 2

x

3

6

7

8

x

2

8

2

10

x

0

0

0

2

4 - 4 = 0

6

8

8

0

Шуканий елемент дорівнює 2
Для цього елемента запаси рівні 2, потреби 6. Оскільки мінімальним є 2, то віднімаємо його.
x12 = min(2,6) = 2.

1

2

x

x

2 - 2 = 0

x

3

6

7

8

x

2

8

2

10

x

0

0

0

2

0

6 - 2 = 4

8

8

0

Шуканий елемент дорівнює 2
Для цього елемента запаси рівні 10, потреби 4. Оскільки мінімальним є 4, то віднімаємо його.
x32 = min(10,4) = 4.

1

2

x

x

0

x

x

6

7

8

x

2

8

2

10 - 4 = 6

x

x

0

0

2

0

4 - 4 = 0

8

8

0

Шуканий елемент дорівнює 2
Для цього елемента запаси рівні 6, потреби 8. Оскільки мінімальним є 6, то віднімаємо його.
x34 = min(6,8) = 6.

1

2

x

x

0

x

x

6

7

8

x

2

x

2

6 - 6 = 0

x

x

0

0

2

0

0

8

8 - 6 = 2

0

Шуканий елемент дорівнює 6
Для цього елемента запаси рівні 8, потреби 8. Оскільки мінімальним є 8, то віднімаємо його.
x23 = min(8,8) = 8.

1

2

x

x

0

x

x

6

x

8 - 8 = 0

x

2

x

2

0

x

x

x

0

2

0

0

8 - 8 = 0

2

0

Шуканий елемент дорівнює 0
Для цього елемента запаси рівні 2, потреби 2. Оскільки мінімальним є 2, то віднімаємо його.
x44 = min(2,2) = 2.

1

2

x

x

0

x

x

6

x

0

x

2

x

2

0

x

x

x

0

2 - 2 = 0

0

0

0

2 - 2 = 0

0

 

1

2

3

4

Запаси

1

1[4]

2[2]

4

3

6

2

4

3

6[8]

7

8

3

3

2[4]

8

2[6]

10

4

0

0

0

0[2]

2

Потреби

4

6

8

8

 

2. Підрахуємо число зайнятих клітин таблиці, їх 6, а має бути m + n - 1 = 7. Отже, опорний план є виродженим.
Будуємо новий план.
Значення цільової функції для цього опорного плану одно:
F(x) = 1*4 + 2*2 + 6*8 + 2*4 + 2*6 + 0*2  = 76
Шуканий елемент дорівнює 2
Для цього елемента запаси рівні 6, потреби 6. Оскільки мінімальним є 6, то віднімаємо його.
x12 = min(6,6) = 6.

x

2

x

x

6 - 6 = 0

4

x

6

7

8

3

x

8

2

10

0

x

0

0

2

4

6 - 6 = 0

8

8

0

Шуканий елемент дорівнює 2
Для цього елемента запаси рівні 10, потреби 8. Оскільки мінімальним є 8, то віднімаємо його.
x34 = min(10,8) = 8.

x

2

x

x

0

4

x

6

x

8

3

x

8

2

10 - 8 = 2

0

x

0

x

2

4

0

8

8 - 8 = 0

0

Шуканий елемент дорівнює 3
Для цього елемента запаси рівні 2, потреби 4. Оскільки мінімальним є 2, то віднімаємо його.
x31 = min(2,4) = 2.

x

2

x

x

0

4

x

6

x

8

3

x

x

2

2 - 2 = 0

0

x

0

x

2

4 - 2 = 2

0

8

0

0

Шуканий елемент дорівнює 4
Для цього елемента запаси рівні 8, потреби 2. Оскільки мінімальним є 2, то віднімаємо його.
x21 = min(8,2) = 2.

x

2

x

x

0

4

x

6

x

8 - 2 = 6

3

x

x

2

0

x

x

0

x

2

2 - 2 = 0

0

8

0

0

Шуканий елемент дорівнює 6
Для цього елемента запаси рівні 6, потреби 8. Оскільки мінімальним є 6, то віднімаємо його.
x23 = min(6,8) = 6.

x

2

x

x

0

4

x

6

x

6 - 6 = 0

3

x

x

2

0

x

x

0

x

2

0

0

8 - 6 = 2

0

0

Шуканий елемент дорівнює 0
Для цього елемента запаси рівні 2, потреби 2. Оскільки мінімальним є 2, то віднімаємо його.
x43 = min(2,2) = 2.

x

2

x

x

0

4

x

6

x

0

3

x

x

2

0

x

x

0

x

2 - 2 = 0

0

0

2 - 2 = 0

0

0

 

1

2

3

4

Запаси

1

1

2[6]

4

3

6

2

4[2]

3

6[6]

7

8

3

3[2]

2

8

2[8]

10

4

0

0

0[2]

0

2

Потреби

4

6

8

8

 

2. Підрахуємо число зайнятих клітин таблиці, їх 6, а має бути m + n - 1 = 7. Отже, опорний план є виродженим.
Будуємо новий план.
Значення цільової функції для цього опорного плану одно:
F(x) = 2*6 + 4*2 + 6*6 + 3*2 + 2*8 + 0*2  = 78
Шуканий елемент дорівнює 2
Для цього елемента запаси рівні 10, потреби 6. Оскільки мінімальним є 6, то віднімаємо його.
x32 = min(10,6) = 6.

1

x

4

3

6

4

x

6

7

8

3

2

8

2

10 - 6 = 4

0

x

0

0

2

4

6 - 6 = 0

8

8

0

Шуканий елемент дорівнює 1
Для цього елемента запаси рівні 6, потреби 4. Оскільки мінімальним є 4, то віднімаємо його.
x11 = min(6,4) = 4.

1

x

4

3

6 - 4 = 2

x

x

6

7

8

x

2

8

2

4

x

x

0

0

2

4 - 4 = 0

0

8

8

0

Шуканий елемент дорівнює 2
Для цього елемента запаси рівні 4, потреби 8. Оскільки мінімальним є 4, то віднімаємо його.
x34 = min(4,8) = 4.

1

x

4

3

2

x

x

6

7

8

x

2

x

2

4 - 4 = 0

x

x

0

0

2

0

0

8

8 - 4 = 4

0

Шуканий елемент дорівнює 3
Для цього елемента запаси рівні 2, потреби 4. Оскільки мінімальним є 2, то віднімаємо його.
x14 = min(2,4) = 2.

1

x

x

3

2 - 2 = 0

x

x

6

7

8

x

2

x

2

0

x

x

0

0

2

0

0

8

4 - 2 = 2

0

Шуканий елемент дорівнює 6
Для цього елемента запаси рівні 8, потреби 8. Оскільки мінімальним є 8, то віднімаємо його.
x23 = min(8,8) = 8.

1

x

x

3

0

x

x

6

x

8 - 8 = 0

x

2

x

2

0

x

x

x

0

2

0

0

8 - 8 = 0

2

0

Шуканий елемент дорівнює 0
Для цього елемента запаси рівні 2, потреби 2. Оскільки мінімальним є 2, то віднімаємо його.
x44 = min(2,2) = 2.

1

x

x

3

0

x

x

6

x

0

x

2

x

2

0

x

x

x

0

2 - 2 = 0

0

0

0

2 - 2 = 0

0

 

1

2

3

4

Запаси

1

1[4]

2

4

3[2]

6

2

4

3

6[8]

7

8

3

3

2[6]

8

2[4]

10

4

0

0

0

0[2]

2

Потреби

4

6

8

8

 

2. Підрахуємо число зайнятих клітин таблиці, їх 6, а має бути m + n - 1 = 7. Отже, опорний план є виродженим.
Будуємо новий план.
Значення цільової функції для цього опорного плану одно:
F(x) = 1*4 + 3*2 + 6*8 + 2*6 + 2*4 + 0*2  = 78
Шуканий елемент дорівнює 2
Для цього елемента запаси рівні 10, потреби 8. Оскільки мінімальним є 8, то віднімаємо його.
x34 = min(10,8) = 8.

1

2

4

x

6

4

3

6

x

8

3

2

8

2

10 - 8 = 2

0

0

0

x

2

4

6

8

8 - 8 = 0

0

Шуканий елемент дорівнює 1
Для цього елемента запаси рівні 6, потреби 4. Оскільки мінімальним є 4, то віднімаємо його.
x11 = min(6,4) = 4.

1

2

4

x

6 - 4 = 2

x

3

6

x

8

x

2

8

2

2

x

0

0

x

2

4 - 4 = 0

6

8

0

0

Шуканий елемент дорівнює 2
Для цього елемента запаси рівні 2, потреби 6. Оскільки мінімальним є 2, то віднімаємо його.
x12 = min(2,6) = 2.

1

2

x

x

2 - 2 = 0

x

3

6

x

8

x

2

8

2

2

x

0

0

x

2

0

6 - 2 = 4

8

0

0

Шуканий елемент дорівнює 2
Для цього елемента запаси рівні 2, потреби 4. Оскільки мінімальним є 2, то віднімаємо його.
x32 = min(2,4) = 2.

1

2

x

x

0

x

3

6

x

8

x

2

x

2

2 - 2 = 0

x

0

0

x

2

0

4 - 2 = 2

8

0

0

Шуканий елемент дорівнює 3
Для цього елемента запаси рівні 8, потреби 2. Оскільки мінімальним є 2, то віднімаємо його.
x22 = min(8,2) = 2.

1

2

x

x

0

x

3

6

x

8 - 2 = 6

x

2

x

2

0

x

x

0

x

2

0

2 - 2 = 0

8

0

0

Шуканий елемент дорівнює 6
Для цього елемента запаси рівні 6, потреби 8. Оскільки мінімальним є 6, то віднімаємо його.
x23 = min(6,8) = 6.

1

2

x

x

0

x

3

6

x

6 - 6 = 0

x

2

x

2

0

x

x

0

x

2

0

0

8 - 6 = 2

0

0

Шуканий елемент дорівнює 0
Для цього елемента запаси рівні 2, потреби 2. Оскільки мінімальним є 2, то віднімаємо його.
x43 = min(2,2) = 2.

1

2

x

x

0

x

3

6

x

0

x

2

x

2

0

x

x

0

x

2 - 2 = 0

0

0

2 - 2 = 0

0

0

 

1

2

3

4

Запаси

1

1[4]

2[2]

4

3

6

2

4

3[2]

6[6]

7

8

3

3

2[2]

8

2[8]

10

4

0

0

0[2]

0

2

Потреби

4

6

8

8

 

У результаті отриманий перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
2. Підрахуємо число зайнятих клітин таблиці, їх 7, а має бути m + n - 1 = 7. Отже, опорний план є невиродженим.
Значення цільової функції для цього опорного плану одно:
F(x) = 1*4 + 2*2 + 3*2 + 6*6 + 2*2 + 2*8 + 0*2  = 70
Етап II. Поліпшення опорного плану.
Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
u1 + v1 = 1; 0 + v1 = 1; v1 = 1
u1 + v2 = 2; 0 + v2 = 2; v2 = 2
u2 + v2 = 3; 2 + u2 = 3; u2 = 1
u2 + v3 = 6; 1 + v3 = 6; v3 = 5
u4 + v3 = 0; 5 + u4 = 0; u4 = -5
u3 + v2 = 2; 2 + u3 = 2; u3 = 0
u3 + v4 = 2; 0 + v4 = 2; v4 = 2

 

v1=1

v2=2

v3=5

v4=2

u1=0

1[4]

2[2]

4

3

u2=1

4

3[2]

6[6]

7

u3=0

3

2[2]

8

2[8]

u4=-5

0

0

0[2]

0

Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi > cij
(1;3): 0 + 5 > 4; ∆13 = 0 + 5 - 4 = 1
Вибираємо максимальну оцінку вільної клітини (1;3): 4
Для цього в перспективну клітку (1;3) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-».

 

1

2

3

4

Запаси

1

1[4]

2[2][-]

4[+]

3

6

2

4

3[2][+]

6[6][-]

7

8

3

3

2[2]

8

2[8]

10

4

0

0

0[2]

0

2

Потреби

4

6

8

8

 

Цикл наведено в таблиці (1,3; 1,2; 2,2; 2,3; ).
З вантажів хij стоять у мінусових клітинах, вибираємо найменше, тобто у = min (1, 2) = 2. Додаємо 2 до обсягів вантажів, що стоять у плюсових клітинах і віднімаємо 2 з Хij, стоять у мінусових клітинах. У результаті отримаємо новий опорний план.

 

1

2

3

4

Запаси

1

1[4]

2

4[2]

3

6

2

4

3[4]

6[4]

7

8

3

3

2[2]

8

2[8]

10

4

0

0

0[2]

0

2

Потреби

4

6

8

8

 

Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
u1 + v1 = 1; 0 + v1 = 1; v1 = 1
u1 + v3 = 4; 0 + v3 = 4; v3 = 4
u2 + v3 = 6; 4 + u2 = 6; u2 = 2
u2 + v2 = 3; 2 + v2 = 3; v2 = 1
u3 + v2 = 2; 1 + u3 = 2; u3 = 1
u3 + v4 = 2; 1 + v4 = 2; v4 = 1
u4 + v3 = 0; 4 + u4 = 0; u4 = -4

 

v1=1

v2=1

v3=4

v4=1

u1=0

1[4]

2

4[2]

3

u2=2

4

3[4]

6[4]

7

u3=1

3

2[2]

8

2[8]

u4=-4

0

0

0[2]

0

Опорний план є оптимальним, оскільки всі оцінки вільних клітин задовольняють умові ui + vi <= cij.
Мінімальні витрати складуть:
F(x) = 1*4 + 4*2 + 3*4 + 6*4 + 2*2 + 2*8 + 0*2  = 68