Транспортна задача з додатковими умовами

Вступ

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

Особливості відкритих транспортних задач з додатковими умовами

Розглянемо кілька особливостей відкритих транспортних задач з додатковими умовами.
1. Додаткова умова заборони перевезень від певного постачальника до певного споживача. В такому разі в оптимальному плані відповідні клітини обов’язково мають бути вільними Неможливо розібрати вираз (невідома помилка): (x_{ij}=0) .
Розв’язуючи транспортну задачу з додатковою умовою на заборону окремих постачань, необхідно у відповідних клітинах замінити значення вартостей перевезень одиниці продукції на деяке велике число (ставиться досить велике число М). Оскільки розглянуті вище методи розв’язання транспортних задач уможливлюють організацію перевезень у такий спосіб, що мінімізується загальна вартість витрат на транспортування, то це зумовить виключення з розгляду перевезень з надто великими вартостями, що і забезпечить виконання такої додаткової умови.
2. Додаткова умова перевезення за окремими маршрутами строго визначеного обсягу продукції, тобто виконання обов’язкових постачань. В оптимальному плані відкритої транспортної задачі з такою додатковою умовою клітини відповідних фіктивно введених постачальників чи споживачів мають бути вільними.
Розв’язуючи такого типу транспортну задачу, необхідно у відповідних клітинах також збільшити значення вартостей перевезень (ставиться досить велике число М).
3. Додаткова умова необхідності перевезення від і-го постачальника j-му споживачеві не менше Неможливо розібрати вираз (невідома помилка): k_{ij}

одиниць продукції, тобто вводиться додаткове обмеження виду: Неможливо розібрати вираз (невідома помилка): x_{ij}\ge k_{ij}

.
Розв’язуючи транспортну задачу з такою додатковою умовою, необхідно змінити початкові умови: обсяг постачання Неможливо розібрати вираз (невідома помилка): k_{ij}

відняти від обсягу запасу і-го постачальника Неможливо розібрати вираз (невідома помилка): (a_i^' = a_i - k_{ij})
та від потреби j-го споживача Неможливо розібрати вираз (невідома помилка): (b_j^' = b_j - k_{ij})

. Знайдений оптимальний план транспортної задачі зі зміненими умовами (де використані значення Неможливо розібрати вираз (невідома помилка): a_i^' , b_j^'

) коригується, враховуючи обмеження Неможливо розібрати вираз (невідома помилка): x_{ij}\ge k_{ij}

.
4. Додаткова умова необхідності перевезення від і-го постачальника j-му споживачеві не більше Неможливо розібрати вираз (невідома помилка): k_{ij}

одиниць продукції, тобто вводиться додаткове обмеження виду: Неможливо розібрати вираз (невідома помилка): x_{ij}\le k_{ij}

.
Для виконання такої додаткової умови необхідно в транспортну таблицю j-го споживача записати двічі. Один раз його потреби визначатимуться величиною Неможливо розібрати вираз (невідома помилка): k_{ij} , а другий раз — різницею Неможливо розібрати вираз (невідома помилка): b_j - k_{ij} = b_j^' . Витрати на перевезення одиниці продукції в обох стовпцях повинні бути однаковими за винятком клітини на перетині і-го постачальника і j-го споживача з потребою Неможливо розібрати вираз (невідома помилка): b_i^' . У цій клітині ставиться досить велике число М. В такій постановці задача розв’язується відомими методами.
5. На практиці часто потрібно оптимальний план перевезень неоднорідної продукції, тобто розв’язати багатопродуктову задачу. Її математична модель має такий вигляд:

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

Приклад

Три нафтопереробних заводи А1, А2 та А3 із максимальною щоденною продуктивністю відповідно 30, 20 і 15 тис. т бензину забезпечують чотири бензосховища B1, B2, B3, B4, щоденна потреба яких становить відповідно 10, 20, 25 та 20 тис. т. бензину. Бензин постачається до бензосховищ трубопроводами. Вартості перекачування 1000 т бензину від заводів до сховищ (в умовних одиницях) наведені в табл. 1.

Сформулювати та розв’язати відповідну транспорту задачу з неодмінним виконанням таких умов:
1) повністю задовольнити потребу бензосховища B4;
2) за недопостачання бензину до сховища B2 згідно з договором передбачені штрафні санкції: 5 ум. од. за кожні 1000 т бензину;
3) у зв’язку з виконанням ремонтних робіт на трубопроводі постачання бензину із заводу А1 до сховища B1 тимчасово неможливе.

Розв’язання. Визначимо, до якого типу належить транспортна задача:
За умовою ця транспортна задача є відкритою, незбалансованою. Зведення її до закритого типу потребує введення додаткового фіктивного постачальника А4 з продуктивністю а4 = 75 – 65 = 10 (тисяч тонн). Кількість бензину, що «відправляється» фіктивним заводом до бензосховищ, в оптимальному плані означатиме обсяг незадоволеного попиту в цьому пункті призначення. Тому для виконання першої додаткової вимоги задачі необхідно заблокувати клітинку фіктивного постачальника А4 та споживача B4, записавши в ній досить високу вартість перевезення М. Тоді можна бути впевненим, що в оптимальному плані транспортної задачі ця клітинка обов’язково буде незаповненою.
Виконання другої умови задачі забезпечується тим, що в рядку фіктивного постачальника у стовпчику B2 вартість транспортування 1000 т бензину дорівнюватиме 5 ум. од. замість нуля.
Оскільки неможливо транспортувати бензин від заводу А1 до сховища B1, то необхідно також заблокувати маршрут А1B1. Для цього в зазначеній клітинці замість С11 = 4 записуємо величину М.
З огляду на викладене табл. 2 з першим планом транспортної задачі має такий вигляд (початковий опорний план побудовано методом апроксимації Фогеля):

Отже, перший опорний план задачі неоптимальний. Найбільше порушення умови оптимальності відповідає порожнім клітинкам А4B1 та А4B3 таблиці. Оскільки обидві вони мають однакові коефіцієнти С41 = С43 = 0, то для заповнення можна вибрати будь-яку з них, наприклад, А4B1. Перехід до другого плану виконується за таким циклом:

Після цього кроку заблокована клітинка А4B4 стає порожньою. Дальше розв’язування задачі подано у вигляді табл. 3 та табл. 4

Література

http://fingal.com.ua/content/view/463/76/1/1/ ,
http://uk.wikipedia.org/wiki/Транспортна_задача