4.2 Метод мінімального елемента
Суть метода мінімального елемента полягає у виборі клітинки з мінімальним тарифом. Слід відмітити, що цей метод, як правило, дозволяє знайти опорний план транспортної задачі, при якому загальна вартість перевезень вантажу менша, ніж загальна вартість перевезень при плані, знайденому для даної задачі за допомогою методу північно-західного кута. Тому найбільш доцільно опорний план транспортної задачі знаходити методом мінімального елемента.
Розглянемо умову попереднього прикладу (таблиця 4.2).
Покладемо х23 = 120 і запишемо це значення у відповідну клітинку таблиці 4.4. Виключимо тимчасово з розгляду стовпець В3.
В частині таблиці, що залишилася з трьома рядками і з чотирма стовпцями В1, В2, В3 і В5, клітинка з найменшим значенням тарифу С25 знаходиться на перетині рядка А2 і стовпця В5. Покладемо х25 = 60 і внесемо це значення у відповідну клітинку таблиці 4.4.
Тимчасово виключимо з розгляду рядок А2. Так як тариф 2 зустрічається у клітинках тричі, то доцільно вибрати тариф С14. Покладемо х14 = 130, стовпець В4 виключаємо з розгляду. Після цього з врахуванням мінімальних тарифів заповнюємо стовпець В5: х35 = 40 і стовпець В1: x11 = 10. Знову розглядаємо частину таблиці, що залишилася. В ній мінімальний тариф Сij знаходиться в клітинці на перетині рядка А3 і стовпця В2, що дорівнює 7. Заповнимо приведеним вище способом цю клі-
Таблиця 4.4
Пункти відправлення |
Пункти призначення |
Запас |
||||
В1 |
В2 |
В3 |
В4 |
В5 |
||
А1 |
2 |
3 |
4 |
2 |
4 |
140 |
10 |
|
|
130 |
|
||
А2 |
8 |
4 |
1 |
4 |
1 |
180 |
|
|
120 |
|
60 |
||
А3 |
9 |
7 |
3 |
7 |
2 |
160 |
50 |
70 |
|
|
40 |
||
Потреби |
60 |
70 |
120 |
130 |
100 |
480 |
клітинку і аналогічно заповнюємо (у відповідній послідовності) клітинку, що знаходиться на перетині рядка А3 і стовпця В1. В результаті отримаємо опорний план:
.
При даному плані перевезень загальна вартість транспортування складає:
f = 2·10 + 9·50 + 7·70 + 1·120 + 2·130 + 1·60 + 2·40 = 1480.
4.3 Метод апроксимації Фогеля
При визначенні оптимального плану транспортної задачі методом апроксимації Фогеля на кожній ітерації по всіх стовпцях і по всіх рядках знаходять різницю між двома записаними в них мінімальними тарифами. Ці різниці записують в спеціально відведених для цього рядку та стовпці в таблиці умови задачі. В рядку (чи в стовпці), де максимальна різниця, визначають мінімальний тариф. Клітинку, в якій він записаний, заповнюють на даній ітерації.
Якщо мінімальний тариф однаковий для декількох клітинок даного рядка (стовпця), то для заповнення вибирають ту клітинку, яка знаходиться в стовпці (рядку), що відповідає найбільшій різниці між двома мінімальними тарифами, які знаходяться в даному стовпці (рядку).