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

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

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

транспортна задача метод мінімальної вартості, транспортна задача метод найменшої вартості, транспортна задача метод мінімального елемента

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

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

  • якщо ai < bj, то xij = ai, i-й рядок виключається з подальшого розгляду (запаси постачальника Aiповністю вичерпані), а потреби  споживача Bj зменшується на величину ai;
  • якщо ai > bj, то xij = bj, j-й стовпець виключається з подальшого розгляду (потреби споживача Bjповністю задоволені), а наявність вантажу ai постачальника Ai зменшується на величину ;
  • якщо ai = bj, то xij = ai = bj, i-й рядок та j-й стовпець виключаються з подальшого розгляду – даний варіант призводить до виродження вихідного плану.

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

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

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

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

транспортна задача метод мінімальної вартості, транспортна задача метод найменшої вартості, транспортна задача метод мінімального елемента

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

Вибиравши першу зних та скориставшись співвідношенням x23 = min(a2, b3) знайдемо значення об’єму перевезень від постачальника A2 до споживача B3:

Метод мінімальної вартості - крок №1

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

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

Метод мінімальної вартості - крок №2

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

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

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

Метод мінімальної вартості - крок №3

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

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

  • Метод мінімальної вартості - крок №4, рядок i = 1 виключається з подальшого розгляду, а потреби в продукції споживача B4 зменшуються на a1 = 80 одиниць: b4 = 50;
  • Метод мінімальної вартості - крок №5, стовпець j = 5 виключається з подальшого розгляду, а запаси продукції на складі номер 3 зменшуються на b5 = 40 одиниць: a3 = 120;
  • у частині таблиці що залишилася, змінним x32 та x34 відповідають комірки з мінімальними вартостями перевезень (c32 = c34 = 7), x32 = 70. Стовпець j = 2 виключається з подальшого розгляду, а наявність продукції на складі A3 зменшується на b2 = 70 одиниць: a3 = 50;
  • оскільки в транспортній таблиці залишився один рядок (i = 3) та один стовпець (j = 4) – це останній крок процесу, x34 = 50.

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

транспортна задача метод мінімальної вартості, транспортна задача метод найменшої вартості, транспортна задача метод мінімального елемента

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

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

транспортна задача метод мінімальної вартості, транспортна задача метод найменшої вартості, транспортна задача метод мінімального елемента

Ми в соціальних мережах

Залишити коментар

Your email address will not be published. Required fields are marked *

*