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

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

  1. На довільному кроці методу, для кожного рядка та стовпця обчислюється різниця ("штраф") між значеннями найменшої вартості та вартості, наступної за величиною. Якщо ж виявиться, що в рядку чи стовпці містятся дві комірки з однаковими мінімальними значеннями тарифів, то беремо саме їх. В такому випадку різниця буде дорівнює нулю.
  2. Обчислені штрафи записуються у додаткові рядки та стовпі транспортоної таблиці.
  3. Виокремлюємо рядок чи стовпець з найбільшим "штрафом" (якщо їх є декілька, то обираємо довільний з них).
  4. У виокремленому на попередньому кроці рядку чи стовпці, обираємо комірку з найменшою вартістю.
  5. Для обраної комірки встановлюємо величину перевезунь, аналогічно методу мінімального елемента, після чого, повторюємо всі вищеописані дії знову, тільки вже не враховуючи заповнені клітини.

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

Побудова опорного плану транспортної задачі методом Фогеля — приклад:

На три бази поступив товар в кількості 160, 140 і 170 одиниць відповідно. Цей груз потрібно перевезти в чотири пункти призначення , потреби яких становлять 120, 50, 190, 110. Тарифи на перевезення одиниці продукції записані в наступній таблиці.

Таблиця тарифів на перевезення

Для побудови опорного плану транспортної задачі методом Фогеля, на першому кроці доповнимо транспортну таблицю додатковим рядком і стовпцем. Далі, згідно алгоритму, заповнимо їх комірки обчисленими для кожного рядка та стовпця "штрафами".

Побудова опорного плану транспортоної задачі Крок 1

Максимальне значення такої різниці на першому кроці відповідає четвертому стовпцю і означає, що у разі, коли не буде задоволена потреба четвертого пункту призначення перевезенням продукції від першого пункту відправлення за ціною 2 у. о. за одиницю товару, то на наступних кроках вартість перевезення може бути на 4 у. о. більшою. Тобто інакше може статися, що потребу четвертого пункту необхідно буде задовольняти перевезенням продукції від третього відправника, що призведе до збільшення вартості цього перевезення в 3 рази. Водночас для всіх інших пунктів призначення та пунктів відправлення такі різниці є меншими. Отже, найдоцільніше на першому кроці заповнити комірку . Після цього потреби пункту повністю задоволені, і всі комірки четвертого стовпчика виключаємо з подальших розрахунків різниць по рядках і стовпцях, після чого переходимо до наступного кроку.

Побудова опорного плану транспортоної задачі Крок 2

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

Побудова опорного плану транспортоної задачі Крок 3

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

Побудова опорного плану транспортоної задачі Крок 4

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

Побудова опорного плану транспортоної задачі Крок 5

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

Метод Фогеля алгоритм

Матеріал був корисним, поділись в соціальних мережах:

Коментарі

2 коментаря по темі “Побудова опорного плану транспортної задачі методом Фогеля”
  1. Василь пише:

    Здрастуйте!

    Дякую за змістовний матеріал і як пораду до поліпшення стилю картинки однорядкових формул з індексами типу А1В3 записуйте у вигляді html: A1B3

  2. admin пише:

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

Якщо тобі сподобалась дана тема, залиш свій коментар