в17
.docxB1 |
B2 |
B3 |
Запаси |
|
A1 |
5 |
5 |
6 |
30 |
A2 |
7 |
2 |
4 |
80 |
A3 |
1 |
3 |
2 |
20 |
A4 |
4 |
3 |
5 |
40 |
Потреби |
60 |
80 |
20 |
|
Перевіримо необхідна і достатня умова розв'язання задачі.
∑a = 30 + 80 + 20 + 40 = 170
∑b = 60 + 80 + 20 = 160
Як видно, сумарна потреба вантажу в пунктах призначення менше запасів вантажу на базах. Отже, модель вихідної транспортної задачі є відкритою. Щоб отримати закриту модель, введемо додаткову (фіктивну) потреба, яка дорівнює 10 (170-160). Тарифи перевезення одиниці вантажу до цього магазину вважаємо дорівнюють нулю.
Занесемо вихідні дані в розподільну таблицю.
|
B1 |
B2 |
B3 |
B4 |
Запаси |
A1 |
5 |
5 |
6 |
0 |
30 |
A2 |
7 |
2 |
4 |
0 |
80 |
A3 |
1 |
3 |
2 |
0 |
20 |
A4 |
4 |
3 |
5 |
0 |
40 |
Потреби |
60 |
80 |
20 |
10 |
|
Етап I. Пошук першого опорного плану.
Використовуючи метод найменшої вартості, побудуємо перший опорний план транспортної задачі.
Шуканий елемент дорівнює c31 = 1. Для цього елемента запаси рівні 20, потреби 60. Оскільки мінімальним є 20, то віднімаємо його.
x31 = min(20,60) = 20.
5 |
5 |
6 |
0 |
30 |
7 |
2 |
4 |
0 |
80 |
1 |
x |
x |
x |
20 - 20 = 0 |
4 |
3 |
5 |
0 |
40 |
60 - 20 = 40 |
80 |
20 |
10 |
|
Шуканий елемент дорівнює c22=2. x22 = min(80,80) = 80.
5 |
5 |
6 |
0 |
30 |
x |
2 |
x |
x |
80 - 80 = 0 |
1 |
x |
x |
x |
0 |
4 |
3 |
5 |
0 |
40 |
40 |
80 - 80 = 0 |
20 |
10 |
|
Шуканий елемент дорівнює c41=4. x41 = min(40,40) = 40.
5 |
5 |
6 |
0 |
30 |
x |
2 |
x |
x |
0 |
1 |
x |
x |
x |
0 |
4 |
3 |
x |
x |
40 - 40 = 0 |
40 - 40 = 0 |
0 |
20 |
10 |
|
Шуканий елемент дорівнює c13=6. x13 = min(30,20) = 20.
5 |
5 |
6 |
0 |
30 - 20 = 10 |
x |
2 |
x |
x |
0 |
1 |
x |
x |
x |
0 |
4 |
3 |
x |
x |
0 |
0 |
0 |
20 - 20 = 0 |
10 |
|
Шуканий елемент дорівнює c14=0. x14 = min(10,10) = 10.
5 |
5 |
6 |
0 |
10 - 10 = 0 |
x |
2 |
x |
x |
0 |
1 |
x |
x |
x |
0 |
4 |
3 |
x |
x |
0 |
0 |
0 |
0 |
10 - 10 = 0 |
|
Далі, згідно з алгоритмом, шукаємо елементи серед які викреслених.
5 |
5 |
6 |
0 |
30 |
7 |
2 |
4 |
0 |
80 |
1 |
3 |
2 |
0 |
20 |
4 |
3 |
5 |
0 |
40 |
60 |
80 |
20 |
10 |
|
Шуканий елемент дорівнює c33 = 2, але тому що обмеження виконані, то x33 = 0.
Шуканий елемент дорівнює c42 = 3, але тому що обмеження виконані, то x42 = 0.
|
B1 |
B2 |
B3 |
B4 |
Запаси |
A1 |
5 |
5 |
6[20] |
0[10] |
30 |
A2 |
7 |
2[80] |
4 |
0 |
80 |
A3 |
1[20] |
3 |
2[0] |
0 |
20 |
A4 |
4[40] |
3[0] |
5 |
0 |
40 |
Потреби |
60 |
80 |
20 |
10 |
|
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
2. Підрахуємо число зайнятих клітин таблиці, їх 7, а має бути m + n - 1 = 7. Отже, опорний план є невироджених.
Значення цільової функції для цього опорного плану:
F(x) = 6*20 + 0*10 + 2*80 + 1*20 + 4*40 = 460
Етап II. Поліпшення опорного плану.
Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vj. по зайнятих клітинам таблиці, в яких ui + vj = cij, вважаючи, що u1 = 0.
u1 + v3 = 6; 0 + v3 = 6; v3 = 6
u3 + v3 = 2; 6 + u3 = 2; u3 = -4
u3 + v1 = 1; -4 + v1 = 1; v1 = 5
u4 + v1 = 4; 5 + u4 = 4; u4 = -1
u4 + v2 = 3; -1 + v2 = 3; v2 = 4
u2 + v2 = 2; 4 + u2 = 2; u2 = -2
u1 + v4 = 0; 0 + v4 = 0; v4 = 0
|
v1=5 |
v2=4 |
v3=6 |
v4=0 |
u1=0 |
5 |
5 |
6[20] |
0[10] |
u2=-2 |
7 |
2[80] |
4 |
0 |
u3=-4 |
1[20] |
3 |
2[0] |
0 |
u4=-1 |
4[40] |
3[0] |
5 |
0 |
Опорний план є оптимальним, так все оцінки вільних клітин задовольняють умові ui + vj ≤ cij.
Мінімальні витрати складуть: F (x) = 6 * 20 + 0 * 10 + 2 * 80 + 1 * 20 + 4 * 40 = 460
Згідно отриманого плану, маємо, що від постачальника А1 не було вивезено 10 одиниць продукції, з умов задачі маємо, що для постачальника А1 вартість зберігання одиниці такої продукції дорівнює 7 ум. од.. Звідси маємо, що вартість зберігання нерозподіленої продукції дорівнює 70 ум. од.