Знаходження початкового опорного плану транспортної задачі методом плаваючих зон

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

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

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

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

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

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

Отже, на основі вище сказаного можна зробити висновок, що алгоритм методу плаваючих зон зводиться до пошуку перевантажених зон і закріплення за ними об'єктів. Потім такі зони виключаються, і вирішується, по суті, нова задача — в якій фігурують пункти відправлення та пункти призначення, потреби яких не задоволені.

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

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

Метод плаваючих зон приклад

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

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

Побудова опорного плану транспортної задачі методом плаваючих зон - Ітерація №1

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

Побудова опорного плану транспортної задачі методом плаваючих зон - Ітерація №2

В результаті виконання даного кроку ми отримали одну зону, запаси якої не вичерпано, що свідчить про те, що здійснювати розподіл об'єктів немає сенсу, тому задовольняємо потреби об'єктів 1−4 у відповідності з їх потребами і таким чином отримаємо початковий опорний план заданої транспортної задачі. Відмітимо, що загальна вартість перевезень згідно побудованого плану, як і при використанні методу Фогеля, дорівнює умовних одиниць.

Побудова опорного плану транспортної задачі методом плаваючих зон - Ітерація №3

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

Метод плаваючих зон алгоритм

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

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