Розв’язання транспортної задачі методом мінімальної вартості

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

Метод мінімальної вартості.

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

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

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

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

Далі, знову-таки, розглядається і заповнюється вільна комірку з найменшою вартістю.

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

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

Транспортна задача методом найменшої вартості – розв’язування прикладів.

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

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

Вибиравши першу зних та скориставшись співвідношенням  знайдемо значення об’єму перевезень від постачальника  до споживача :

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

Перейшовши до кроку номер два, задовольняємо потреби пункту призначення номер 5. В результаті отримаємо:

Тобто, за рахунок залишку запасів другого пункту відправлення ми, частково, задовольнили потреби і споживача .

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

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

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

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

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

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

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

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