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

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

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

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

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

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

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

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

Початковий план транспортної задачі отриманий методом подвійної переаги

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

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

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

Побудова оптимального плану ТЗ розподільчим методом – Ітерація №1

Далі, знаходимо оцінки вільних комірок для другого плану і таким чином провіряємо його на оптимальність:

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

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

Побудова оптимального плану ТЗ розподільчим методом – Ітерація №2

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

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

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

Розподільчий метод алгоритм

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

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

*