[ Рішення задач методом північно-західного кута рапределітельного мінімального і максимального ] | |||||
Потреба | 25 | 19 | 24 | 28 |
|
Робимо зрушення по циклу на 4, додаючи цю величину до вантажу в клітинах зі знаком "плюс" і віднімаючи її від вантажу в клітинах зі знаком "мінус".
У результаті переміщення по циклу отримаємо новий план:
Постачальник | Споживач | Запаси вантажу | |||
B1 | B2 | B3 | B4 | ||
A1 |
1 21
7
3
6
21 | ||||
A2 |
7
1 19
1 7
4
26 | ||||
A3 |
3
3
7 17
3 8 25 | ||||
A4 |
1 4
3
5
5 20 24 | ||||
Потреба | 25 | 19 | 24 | 28 |
|
Вартість перевезень Z = 294
Значення цільової функції змінилося на 56 одиниць в порівнянні з попереднім етапом.
Етап 2
Вважаючи потенціал U1 = 0, визначаємо інші потенціали зі співвідношення Ui + Vj = Ci, j (i = 1.. M, j = 1.. N), переглядаючи всі зайняті клітини.
Потенціали Ui, Vj:
U1 = 0 V1 = C1 ,1-U1 = 1 U4 = C1 ,4-V1 = 0 V4 = C4 ,4-U4 = 5 U3 = C4 ,3-V4 = - 2 V3 = C3 ,3-U3 = 9 U2 = C3 ,2-V3 = - 8 V2 = C2 ,2-U2 = 9 Визначаємо значення оцінок Si, j = Ci, j-(Ui + Vj) для всіх вільних клітин
S1, 2 = c1, 2 - (u1 + v2) = - 2.
S1, 3 = c1, 3 - (u1 + v3) = - 6.
S1, 4 = c1, 4 - (u1 + v4) = 1.
S2, 1 = c2, 1 - (u2 + v1) = 14.
S2, 4 = c2, 4 - (u2 + v4) = 7.
S3, 1 = c3, 1 - (u3 + v1) = 4.
S3, 2 = c3, 2 - (u3 + v2) = - 4.
S4, 2 = c4, 2 - (u4 + v2) = - 6.
S4, 3 = c4, 3 - (u4 + v3) = - 4.
Якщо є кілька кліток з одним і тим же найменшим значенням оцінки, то з них вибирається клітина, що має найменший тариф. Найбільш потенційної є клітина (1,3). Для неї оцінка дорівнює - 6. Будуємо для неї цикл, позначаючи клітини циклу знаками "плюс" і "мінус". Робимо зрушення по циклу на величину перевезень в 17 одиниць, додаючи цю величину до вантажу в клітинах зі знаком "плюс" і віднімаючи її від вантажу в клітинах зі знаком "мінус". У результаті переміщення по циклу отримаємо новий план:
Вартість перевезень Z = 192 Значення цільової функції змінилося на 102 одиниць в порівнянні з попереднім етапом. Етап 3 Вважаючи потенціал U1 = 0, визначаємо інші потенціали зі співвідношення Ui + Vj = Ci, j (i = 1.. M, j = 1.. N), переглядаючи всі зайняті клітини. Потенціали Ui, Vj: U1 = 0 V1 = C1 ,1-U1 = 1 V3 = C1 ,3-U1 = 3 U4 = C1 ,4-V1 = 0 U2 = C3 ,2-V3 = - 2 V2 = C2 ,2-U2 = 3 V4 = C4 ,4-U4 = 5 U3 = C4 ,3-V4 = - 2 Визначаємо значення оцінок Si, j = Ci, j-(Ui + Vj) для всіх вільних клітин S1, 2 = c1, 2 - (u1 + v2) = 4. S1, 4 = c1, 4 - (u1 + v4) = 1. S2, 1 = c2, 1 - (u2 + v1) = 8. S2, 4 = c2, 4 - (u2 + v4) = 1. S3, 1 = c3, 1 - (u3 + v1) = 4. S3, 2 = c3, 2 - (u3 + v2) = 2. S3, 3 = c3, 3 - (u3 + v3) = 6. S4, 2 = c4, 2 - (u4 + v2) = 0. S4, 3 = c4, 3 - (u4 + v3) = 2.
| 4 | 2 | 6 |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A4 |
| 0 | 2 |
|
Так як всі оцінки Si, j> = 0, то отриманий план є оптимальним.
Транспортна задача вирішена.
Постачальник | Споживач | Запаси вантажу | |||
B1 | B2 | B3 | B4 | ||
A1 |
1 4
7
3 17
6
21 | ||||
A2 |
7
1 19
1 7
4
26 | ||||
A3 |
3
3
7
3 25 25 | ||||
A4 |
1 21
3
5
5 3 24 | ||||
Потреба | 25 | 19 | 24 | 28 |
|
Вартість перевезень F = 192
Метод мінімального елемента
1111 33333 квітні 1955 6777
Пункт призначення Пункт відправлення | 1 | 2 | 3 | 4 | Запаси | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1 | 1 21 | 7 - | 3 - | 6 - | 21
Z = 1 × 22 +1 × 19 +1 × 7 +3 × 25 +1 × 4 +5 × 17 × 3 +5 = 226, у методі північно-західного кута вартість перевезення була вищою і становила 350. Розподільний метод Розподільний метод являє собою набір таких дій: спочатку будується вихідний опорний план перевезень по одному з вищевикладених правил, а потім послідовно проводиться його поліпшення до отримання оптимального. Для цього для кожної вільної клітини будують замкнутий цикл. Якщо в матриці перевезень міститься опорний план, то для кожної вільної клітини можна утворити і до того ж лише один замкнутий цикл, у якому цю вільну клітину і деяку частину занятиx клітин. Тарифи в клітинах, що знаходяться в непарних вершинах циклу, беремо зі знаком плюс, а в парних - зі знаком мінус. За кожному циклу підраховуємо алгебраїчну суму S ij тарифів. Якщо замкнутий цикл має вигляд: (i, j) -> (k, j) -> (k, l) -> (t, l) -> ... -> (U, v) -> (i, v), то S ij = C ij - C kj + C kl - C tl + ... + C uv - C iv, де (i, j) - вільна клітина. Якщо алгебраїчна сума S ij негативна, то шляхом зміни значень, що стоять в клітинах замкнутого циклу, можна отримати план з меншим значенням цільової функції. Критерієм оптимальності при знаходженні мінімуму функції служить неотрицательности алгебраїчних сум S ij. Якщо зазначена вимога не дотримано, план не оптимальний і підлягає поліпшення. Обчислення при вирішенні транспортної задачі розподільчим методом ведуться за наступним алгоритмом: вихідні дані завдання розташовують у розподільній таблиці; будують вихідний опорний план за правилом "північно-західного кута", або за правилом "мінімального елемента", або методом Фогеля; при цьому повинні виявитися зайнятими r = m + n-1 клітин. Однак, якщо опорний план є виродженим, то ця умова не дотримується. Для збереження числа зайнятих клітин r = m + n-1 незмінним проробляють наступні кроки: в таблиці відшукують клітку, що має мінімальний тариф і не утворить циклу з зайнятими клітинами, поміщають в неї базисний нуль і вважають її надалі зайнятою. Процес пошуку таких клітин триває до тих пір, поки число зайнятих клітин не стане рівним m + n-1; роблять оцінку першої вільної клітини шляхом побудови замкнутого циклу і обчислення з цього циклу величини S ij. Якщо S ij <0, то переходять до наступного пункту алгоритму; переміщують по циклу кількість вантажу, рівне найменшому з чисел, розміщених у парних клітинах циклу (у клітках зі знаком мінус). Далі повертаються до пункту с. Якщо S ij> = 0, то оцінюють наступну вільну клітину, і т.д., поки не виявлять клітку з негативною оцінкою. Серед всіх клітин з Оцінка менше нуля потрібно знайти клітину з найбільшим порушенням оптимальності, тобто клітку з найменшою оцінкою. Якщо, нарешті, оцінки всіх вільних клітин виявляться невід'ємними, то оптимальне рішення знайдено.
(1,2) = c 1,2 - c 1,1 + c 4,1 - c 4,3 + c 2,3 - c 2,2 = 2 (1,3) = c 1,3 - c 1 , 1 + c 4,1 - c 4,3 = - 2 (1,4) = c 1,4 - c 1,1 + c 4,1 - c 4,4 = 1 (2,1) = c 2 , 1 - c 2,3 + c 4,3 - c 4,1 = 10 (2,4) = c 2,4 - c 2,3 + c 4,3 - c 4,4 = 3 (3,1 ) = c 3,1 - c 3,4 + c 4,4 - c 4,1 = 4 (3,2) = c 3,2 - c 3,4 + c 4,4 - c 4,3 + c 2,3 - c 2,2 = 0 (3,3) = c 3,3 - c 3,4 + c 4,4 - c 4,3 = 4 (4,2) = c 4,2 - c 4 , 3 + c 2,3 - c 2,2 = - 2 найменша перевезення 17, робимо зрушення
(1,2) = c 1,2 - c 1,3 + c 2,3 - c 2,2 = 4 (1,4) = c 1,4 - c 1,1 + c 4,1 - c 4 , 4 = 1 (2,1) = c 2,1 - c 2,3 + c 1,3 - c 1,1 = 8 (2,4) = c 2,4 - c 2,3 + c 1, 3 - c 1,1 + c 4,1 - c 4,4 = 1 (3,1) = c 3,1 - c 3,4 + c 4,4 - c 4,1 = 4 (3,2) = c 3,2 - c 3,4 + c 4,4 - c 4,1 + c 1,1 - c 1,3 + c 2,3 - c 2,2 = 2 (3,3) = c 3 , 3 - c 3,4 + c 4,4 - c 4,1 + c 1,1 - c 1,3 = 6 (4,2) = c 4,2 - c 4,1 + c 1,1 - c 1,3 + c 2,3 - c 2,2 = 0 (4,3) = c 4,3 - c 4,1 + c 1,1 - c 1,3 = 2 Оптимальний план вийшов розподільчим методом, аналогічний оптимальному плану, отримано методом потенціалів |