На відміну від методу північно-західного кута метод мінімальної вартості (також відомий як метод мінімального елемента) побудований на аналізі матриці вартості перевезень, тому дозволяє побудувати опорне рішення, яке є досить близьким до оптимального, або навіть відразу знайти оптимальний план. Алгоритм методу мінімальної вартості передбачає ряд однотипних кроків, на кожному з яких заповнюється саме та комірка транспортної таблиці, якій відповідає мінімальна вартість перевезення одиниці вантажу .
Представлення транспортної задачі у вигляді таблиці
Побудова вихідного опорного плану починають з визначення комірки, яка має найменшу вартість перевезень. Припустимо, що такою являється комірка, що міститься на перетині -го рядка та
-го стовпця. Тоді, із співвідношення
знаходимо значення об’єму перевезень від постачальника
до споживача
. Зазначимо, що при цьому, як і у випадку з методом північно-західного кута, можливі три варіанти:
- Якщо
, то
,
-й рядок виключається з подальшого розгляду (запаси постачальника
повністю вичерпані), а потреби
споживача
зменшується на величину
.
- Якщо
, то
,
-й стовпець виключається з подальшого розгляду (потреби споживача
повністю задоволені), а наявність вантажу
постачальника
зменшується на величину
.
- Якщо
, то
,
-й рядок та
-й стовбець виключаються з подальшого розгляду. Даний варіант призводить до виродження вихідного плану.
Далі, знову-таки, вибирають вільну комірку з найменшою вартістю, і заповнюють її. Обчислювальний процес методу мінімальної вартості продовжується до тих пір, поки всі запаси не будуть вичерпані і всі потреби – задоволені.
Зауваження: перевірка отриманого плану на виродженність і розстановка (в разі виродженості плану) нулів здійснюється так само, як описано для методу північно-західного кута.
Метод мінімального елемента – приклад:
Побудувати початковий опорний план перевезень транспортній задачі, заданої наступною таблицею:
Транспортна таблиця задачі
Отже, на перейшому кроці алгоритму, визначаємо комірки транспортної таблиці що містять мінімальну вартість перевезення. Зазначимо, що в даному випадку такими являються дві, а саме комірки, яким відповідають змінні та
(
). Вибиравши першу зних та скориставшись співвідношенням
знайдемо значення об’єму перевезень від постачальника
до споживача
:
. В результаті виконання даного кроку, стовпець номер три транспортної таблиці виключається з подальшого розгляду (потреби споживача
задоволені в повному обсязі), а наявність вантажу у постачальника
зменшується на величину
, тобто
.
Перейшовши до кроку номер два, задовольняємо потреби пункту призначення номер 5. В результаті отримаємо: , тобто за рахунок залишку запасів другого пункту відправлення ми, частково, задовольнили потреби і споживача
. Отже, рядок номер два транспортної таблиці виключається з розгляду, а потреби 5-го споживача зменшуються на величину
:
.
На третьому кроці, знову-таки, визначаємо комірки з мінімальними вартостями перевезень. В результаті будемо мати: . Звідси, задовольняємо потреби споживача
:
. Стовпець
виключається з подальшого розгляду, а запаси відправника номер один зменшуються на величину
:
.
Продовжуючи обчислювальний процес далі:
Крок 4: , рядок
виключається з подальшого розгляду, а потреби в продукції споживача
зменшуються на
одиниць:
.
Крок 5: , стовпець
виключається з подальшого розгляду, а запаси продукції на складі номер 3 зменшуються на
одиниць:
.
Крок 6: у частині таблиці що залишилася, змінним та
відповідають комірки з мінімальними вартостями перевезень (
),
. Стовпець
виключається з подальшого розгляду, а наявність продукції на складі
зменшується на
одиниць:
.
Крок 7: оскільки в транспортній таблиці залишився один рядок () та один стовпець (
) – це останній крок процесу,
.
на сьомому кроці, отримаємо кінцеву таблицю, у зайнятих комірках якої містяться числа, які приймаємо в якості початкового опорного плану транспортної задачі (з огляду на те, що кількість зайнятих комірок дорівнює являється невиродженим).
Транспортна таблиця з опорним планом мінімальної вартості
Вартість отриманого плану дорівнює умовних одиниць.