Побудова опорного плану транспортної задачі методом мінімального елемента

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

Представлення транспортної задачі у вигляді таблиці

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

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

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

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

Метод мінімального елемента – приклад:

Побудувати початковий опорний план перевезень транспортній задачі, заданої наступною таблицею:

Транспортна таблиця задачі

Отже, на перейшому кроці алгоритму, визначаємо комірки транспортної таблиці що містять мінімальну вартість перевезення. Зазначимо, що в даному випадку такими являються дві, а саме комірки, яким відповідають змінні та (). Вибиравши першу зних та скориставшись співвідношенням знайдемо значення об’єму перевезень від постачальника до споживача : . В результаті виконання даного кроку, стовпець номер три транспортної таблиці виключається з подальшого розгляду (потреби споживача  задоволені в повному обсязі), а наявність вантажу у постачальника  зменшується на величину , тобто .

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

На третьому кроці, знову-таки, визначаємо комірки з мінімальними вартостями перевезень. В результаті будемо мати: . Звідси, задовольняємо потреби споживача : . Стовпець виключається з подальшого розгляду, а запаси відправника номер один зменшуються на величину : .

Продовжуючи обчислювальний процес далі:

Крок 4: , рядок виключається з подальшого розгляду, а потреби в продукції споживача зменшуються на одиниць: .

Крок  5: , стовпець виключається з подальшого розгляду, а запаси продукції на складі номер 3 зменшуються на одиниць: .

Крок 6: у частині таблиці що залишилася, змінним та відповідають комірки з мінімальними вартостями перевезень (), . Стовпець виключається з подальшого розгляду, а наявність продукції на складі зменшується на одиниць: .

Крок  7: оскільки в транспортній таблиці залишився один рядок () та один стовпець () – це останній крок процесу, .

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

Транспортна таблиця з опорним планом мінімальної вартості

Вартість отриманого плану дорівнює умовних одиниць.

Блок-схема алгоритму побудови опорного плану транспотрної задачі методом мінімального елемента