Відшукання початкового опорного плану перевезень

Існує декілька методів відшукування опорного плану транспортної задачі, серед них:

а) метод північно-західного кута;

б) метод мінімального елемента в рядку;

в) метод мінімального елемента.

Нехай є транспортна задача (5.1 - 5.4). Хоча в системі (5.2 - 5.3) m+n рівнянь, опорний план містить тільки m+n–1 базисних змінних. Це пояснюється тим, що одне з рівнянь є наслідком інших, і в жордановій формі m+ n–1 рівнянь.

Опишемо метод відшукання вихідного опорного плану, так званим методом північно-західного кута.

Візьмемо північно-західну клітинку (А_i,В_j). Проставимо в ній перевезення, що дорівнює min(a_i,b_j). Потім "зменшуємо" транспортну таблицю, керуючись правилами:

1) якщо a_i < b_j, то виключаємо з подальшого розгляду пункт відправлення (ПВ) А_i (і відповідний рядок); а в "меншій" таблиці потребу пункту призначення (ПП) В_j вважаємо рівною b_j - a_i;

2) якщо b_j <a_i, то виключаємо ПП В_j (і відповідний стовпець); в "меншій" таблиці вважаємо запас ПВ А_i рівним a_i - b_j;

3) якщо a_i = b_j, то:

а) якщо в таблиці тільки один ПВ А_i і один ПП В_j, то алгоритм зупиняється;

б) якщо в таблиці один ПВ А_i і декілька ПП, то виключаємо В_j, вважаючи в "меншій" таблиці запас пункту А_i рівним 0;

в) якщо в таблиці один ПП В_j і декілька ПВ, то виключаємо А_i, вважаючи в "меншій" таблиці потребу пункту В_j, рівною 0;

г) якщо в таблиці декілька ПВ і декілька ПП, то виключаємо або ПВ А_i, вважаючи в "меншій" таблиці потребу ПП В_j рівною 0, або виключаємо ПП В_j, вважаючи запас ПВ А_i рівним 0.

Подібні кроки проробляють доти, поки не будуть виключені всі рядки й стовпці.

У результаті застосування методу північно-західного кута деякі клітинки заповнені, деякі - ні. Заповнені клітинки називаються базисними (навіть якщо стоїть 0), незаповнені - вільними. Доведемо, що число базисних клітинок дорівнює m+ n-1.

Дійсно, на кожному кроці, крім останнього, виключаємо або рядок, або стовпець. На останньому кроці виключаємо і рядок, і стовпець. Оскільки число рядків і стовпців у сумі дорівнює m+n, то всього буде пророблено m + n -1 кроків, а на кожному кроці заповнюється одна клітинка, відтак число базисних клітинок дорівнюватиме m + n -1.

Скористаємося прикладом (табл. 5.2).

Таблиця 5.2

ПП ПВ	В1	В2	В3	В4	Запаси
А1	10^4	15 ^3	^5	^7
А2	^2	5^1	0^8	^6
А3	0 ^4	^9	30^3	15 ^2
Потреби					75=75

Розглянемо північно-західну клітинку транспортної таблиці - клітинку (1.1). Проставимо в ній перевезення x₁₁=min(a₁,b₁)=min(25,10)=10. Після цього потребу пункту В₁ повністю задоволено. Вилучаємо з таблиці перший стовпчик. В «меншій» транспортній таблиці запас пункту А₁ покладемо рівним 25 – 10 = 15. Розглянемо північно-західну клітинку нової «меншої» таблиці. Керуючись саме таким же правилом, проставимо в ній перевезення x₁₂= 15. Запас пункту А₁ вичерпаний, і ми вилучаємо перший рядок. В отриманій транспортній таблиці потреба пункту В₂ дорівнює 5. У північно-західну клітинку проставимо перевезення x₂₂=min(5,5)=5. При цьому одночасно вичерпано запас пункту А₂ і задоволено потребу пункту В₂.Переходячи до нової таблиці, не можна одночасно вилучити і стовпець, і рядок – потребує вилучення або стовпець, або рядок. Виключимо з таблиці, наприклад, стовпець. Другій рядок ще не виключений з таблиці, тому запас пункту А₂ покладемо рівним 0, тому у північно-західну клітинку ставимо перевезення x₂₃=min(30,0)=0. Після цього виключаємо із розгляду другій рядок. Далі покладемо x₃₃=min(30,45)=30, виключаємо третій стовпець, проставляємо x₃₄=15. Вихідний опорний план знайдено. Базисними змінними є х₁₁, х₁₂, х₂₂, х₂₃, х₃₃, х₃₄. Значення базисних змінних в опорному плані дорівнюють перевезенням, проставленим у відповідних клітках. Опорний план є вироджений, тому що х₂₃=0. Число базисних змінних дорівнює m+ n-1, тобто 3+4-1=6.

Метод північно-західного кута засвоюється дуже легко. Щоб переконатися в цьому, проробіть самостійно такий приклад (табл. 5.3.):

Таблиця 5.3

Пп Пв	В1	В2	В3	Запаси
А1	^2	^3	^1
А2	^4	^2	^5
А3	^3	^2	^6
Потреби				150=150

У вас повинен вийти результат, зафіксований у таблиці 5.4.

Таблиця 5.4

Пп   Пв	В1	В2	В3	Запасы
А1	40 -		+
А2	30 + -	2 30 - +
А3	+	- 10 +	- 40
Потребности				150 = 150

Дата добавления: 2014-01-07