Використання методу диференціальних рент для знаходження оптимального плану транспортної задачі

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

  1. У кожному стовпчику транспортної таблиці знаходимо мінімальний тариф. Знайдені тарифи позначаємо колами, що їх оточують, і заповнюємо відповідні комірки максимально можливими перевезеннями. Таким чином, отримуємо розподіл, що в загальному може не задовільняти обмеженням транспортної задачі (якщо отриманий таким чином розподіл задовільняє обмеженням задачі, то він вважається оптимальним, і алгоритм методу диференціальних рент на цьому закінчується).
  2. Скорочуємо нерозподілені поставки продукту так, щоб при цьому загальна вартість перевезень залишалась мінімальною. Для цього виконуємо наступні кроки:
    1. визначаємо надлишкові та недостатні рядки (рядок є недостатнім (від’ємним), якщо запаси відповідного пункту відправлення розподілені повністю, а потреби пунктів призначення не задоволені; рядок є надлишковим (додатним), якщо потреби задоволені і при цьому залишився товар у відповідному пункті відправлення);
    2. для кожного стовпчика знаходимо різницю між тарифами у колі та найближчим до нього тарифом, який записаний в надлишковому рядку. Якщо тариф у колі знаходиться в позитивному (надлишковому) рядк, то  різницю не визначаємо; серед різниць знаходимо найменшу – проміжну ренту;
    3. переходимо до нової таблиці – додаємо до відповідних тарифів, які знаходяться у від’ємних (недостатніх) рядках, проміжну ренту. Інші елементи не змінюємо.

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

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

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

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

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

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

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

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

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

metod_duf_rent5
Побудова оптимального плану транспортної задачі – ітерація перша (обчислення допоміжних рент)

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

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

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

Метод диференціальних рент алгоритм

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

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

*