Загальна постановка транспортної задачі

Транспортною задачею називається ЗЛП наступного вигляду:

Відзначимо наступну особливість транспортної задачі як ЗЛП спеціального вигляду: система рівнянь розбита на дві групи (5.2) і (5.3) так, що кожна змінна входить рівно в одне рівняння групи з коефіцієнтом 1.

Рівняння (5.2) називаються горизонтальними, рівняння (5.3) -вертикальними.

Будь-який набір значень змінних x_ij називається планом перевезень. План перевезень називається припустимим, оптимальним або опорним, якщо він є припустимим, оптимальним або опорним планом ЗЛП (5.1 - 5.4).

Транспортна задача, як і будь-яка задача лінійного програмування, може бути вирішена симплекс-методом. Однак
завдяки зазначеній вище особливості транспортної задачі, для неї
існують більш прості методи рішення, один із яких – метод
потенціалів - ми вивчимо.

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

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

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

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

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

Нехай є транспортна задача (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

ПП ПВ	В₁	В₂	В₃	В₄	Запаси
А₁	10⁴	15 ³	⁵	⁷
А₂	²	5¹	0⁸	⁶
А₃	0 ⁴	⁹	30³	15 ²
Потреби					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

Пп Пв	В₁	В₂	В₃	Запаси
А₁	²	³	¹
А₂	⁴	²	⁵
А₃	³	²	⁶
Потреби				150=150

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

Таблиця 5.4

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

⇐ Предыдущая 3 4 5 6 789 10 11 12 Следующая ⇒