Метод мінімального елемента

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

Розглянемо умову попереднього прикладу (таблиця 4.2).

Покладемо х₂₃ = 120 і запишемо це значення у відповідну клітинку таблиці 4.4. Виключимо тимчасово з розгляду стовпець В₃.

В частині таблиці, що залишилася з трьома рядками і з чотирма стовпцями В_1, В₂, В₃ і В₅, клітинка з найменшим значенням тарифу С₂₅ знаходиться на перетині рядка А₂ і стовпця В₅. Покладемо х₂₅ = 60 і внесемо це значення у відповідну клітинку таблиці 4.4.

Тимчасово виключимо з розгляду рядок А₂. Так як тариф 2 зустрічається у клітинках тричі, то доцільно вибрати тариф С₁₄. Покладемо х₁₄ = 130, стовпець В₄ виключаємо з розгляду. Після цього з врахуванням мінімальних тарифів заповнюємо стовпець В₅: х₃₅ = 40 і стовпець В₁: x₁₁ = 10. Знову розглядаємо частину таблиці, що залишилася. В ній мінімальний тариф С_ij знаходиться в клітинці на перетині рядка А₃ і стовпця В₂, що дорівнює 7. Заповнимо приведеним вище способом цю клі-

Таблиця 4.4

Пункти відправлення	Пункти призначення	Запас
В1	В2	В3	В4	В5
А1
А2
А3
Потреби

клітинку і аналогічно заповнюємо (у відповідній послідовності) клітинку, що знаходиться на перетині рядка А₃ і стовпця В₁. В результаті отримаємо опорний план:

.

При даному плані перевезень загальна вартість транспортування складає:

f = 2·10 + 9·50 + 7·70 + 1·120 + 2·130 + 1·60 + 2·40 = 1480.

Метод апроксимації Фогеля

При визначенні оптимального плану транспортної задачі методом апроксимації Фогеля на кожній ітерації по всіх стовпцях і по всіх рядках знаходять різницю між двома записаними в них мінімальними тарифами. Ці різниці записують в спеціально відведених для цього рядку та стовпці в таблиці умови задачі. В рядку (чи в стовпці), де максимальна різниця, визначають мінімальний тариф. Клітинку, в якій він записаний, заповнюють на даній ітерації.

Якщо мінімальний тариф однаковий для декількох клітинок даного рядка (стовпця), то для заповнення вибирають ту клітинку, яка знаходиться в стовпці (рядку), що відповідає найбільшій різниці між двома мінімальними тарифами, які знаходяться в даному стовпці (рядку).

Приклад. Використовуючи метод апроксимації Фогеля, знайдемо опорний план попередньої задачі (таблиця 4.2).

Розв'язання

Для кожного рядка і стовпця таблиці умови знайдемо різницю між двома мінімальними тарифами, записаними в даному рядку або стовпці та помістимо їх у відповідному додатковому стовпці або в додатковому рядку таблиці. Так в рядку А₁ мінімальний тариф дорівнює 2, який зустрічається двічі, тому різниця дорівнює 0.

Аналогічна ситуація і в рядку А₂ з мінімальними тарифами 1. В рядку А₃ мінімальні тарифи 3 і 2. Отже, різниця між ними: 3 – 2 = 1. Аналогічно отримуємо різницю в стовпці В₁: 8 – 2 = 6. Розрахувавши всі ці різниці, бачимо, що найбільша з них відповідає стовпцю В₁. Таким чином, необхідно заповнити клітинку, що знаходиться на перетині рядка А₁ та В₁, тому що в ній найменша ціна. Заповнивши її, ми тим самим задовольнили потреби пункту В₁, тому виключаємо з розгляду стовпець В₁ і будемо вважати запаси пункту А₁ рівними 140 – 60 = 80 одиниць. Після цього визначимо наступну клітинку для заповнення. Знову знаходимо різниці між мінімальними тарифами в кожному з рядків і стовпців, що залишились. Запишемо їх відповідно в другому додатковому стовпці і рядку таблиці 4.5. Як видно з цієї таблиці, найбільша різниця (в даному випадку однакова) буде в стовпцях В₃ і В₄. Вибираємо той стовпець, в якому найменший мінімальний тариф. Це буде стовпець В₃. На перетині цього стовпця з рядком А₂ визначаємо клітинку з мінімальним тарифом і заповнюємо її з врахуванням потреб пункту В₃ та запасів пункту А₂, виключаємо з розгляду стовпець В₃ і будемо вважати запаси пункту А₂ рівними 180 – 120 = 60 одиниць.

Продовжимо ітераційний процес, послідовно заповнюючи клітинки, що знаходяться на перетині рядка А₃ і стовпця В₅, рядка А₁ та стовпця В₄, рядка А₂ і стовпця В₂, рядка А₃ і стовпця В₄, рядка А₃ і стовпця В₂.

Таблиця 4.5

Пункти відправлення	Пункти призначення	Запас	Різниці по рядках
В1	В2	В3	В4	В5
А1
А2
А3									5(3)
Потреби
Різниці по стовпцях	6(1)
-		2(2)
-		-
-		-	2(4)	-
-	3(5)	-		-

В результаті отримаємо опорний план:

.

При цьому плані загальна вартість перевезення така:

f = 2·60 + 4·60 + 7·10 + 1·120 + 2·80 + 7·50 + 2·100 = 1260.

Як правило, використання методу апроксимації Фогеля дозволяє отримати опорний план, близький до оптимального, або сам оптимальний план.