Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

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

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

Розглянемо кілька особливостей відкритих транспортних задач з додатковими умовами.

1. Додаткова умова заборони перевезень від певного постачальника до певного споживача. В такому разі в оптимальному плані відповідні клітини обов’язково мають бути вільними ().

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

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

Розв’язуючи такого типу транспортну задачу, необхідно у відповідних клітинах також збільшити значення вартостей перевезень (ставиться досить велике число М).

3. Додаткова умова необхідності перевезення від і-го постачальника j-му споживачеві не менше kij одиниць продукції, тобто вводиться додаткове обмеження виду: .

Розв’язуючи транспортну задачу з такою додатковою умовою, необхідно змінити початкові умови: обсяг постачання kij відняти від обсягу запасу і-го постачальника () та від потреби j-го споживача . Знайдений оптимальний план транспортної задачі зі зміненими умовами (де використані значення ) коригується, враховуючи обмеження .

4. Додаткова умова необхідності перевезення від і-го постачальника j-му споживачеві не більше kij одиниць продукції, тобто вводиться додаткове обмеження виду: .

Для виконання такої додаткової умови необхідно в транспортну таблицю j-го споживача записати двічі. Один раз його потреби визначатимуться величиною kij, а другий раз — різницею . Витрати на перевезення одиниці продукції в обох стовпцях повинні бути однаковими за винятком клітини на перетині і-го постачальника і j-го споживача з потребою . У цій клітині ставиться досить велике число М. В такій постановці задача розв’язується відомими методами.

5. На практиці часто потрібно визначити оптимальний план перевезень неоднорідної продукції, тобто розв’язати багатопродуктову задачу. Її математична модель має такий вигляд:

де k — індекс виду продукції, що необхідно перевезти.

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

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

Таблиця 5.19

Сформулювати та розв’язати відповідну транспорту задачу з неодмінним виконанням таких умов:

1) повністю задовольнити потребу бензосховища B4;

2) за недопостачання бензину до сховища B2 згідно з договором передбачені штрафні санкції: 5 ум. од. за кожні 1000 т бензину;

3) у зв’язку з виконанням ремонтних робіт на трубопроводі постачання бензину із заводу А1 до сховища B1 тимчасово неможливе.

Розв’язання. Визначимо, до якого типу належить транспортна задача:

, .

За умовою ця транспортна задача є відкритою, незбалансованою. Зведення її до закритого типу потребує введення додаткового фіктивного постачальника А4 з продуктивністю а4 = 75 – 65 = 10 (тисяч тонн). Кількість бензину, що «відправляється» фіктивним заводом до бензосховищ, в оптимальному плані означатиме обсяг незадоволеного попиту в цьому пункті призначення. Тому для виконання першої додаткової вимоги задачі необхідно заблокувати клітинку фіктивного постачальника А4 та споживача B4, записавши в ній досить високу вартість перевезення М. Тоді можна бути впевненим, що в оптимальному плані транспортної задачі ця клітинка обов’язково буде незаповненою.

Виконання другої умови задачі забезпечується тим, що в рядку фіктивного постачальника у стовпчику B2 вартість транспортування 1000 т бензину дорівнюватиме 5 ум. од. замість нуля.

Оскільки неможливо транспортувати бензин від заводу А1 до сховища B1, то необхідно також заблокувати маршрут А1B1. Для цього в зазначеній клітинці замість С11 = 4 записуємо величину М.

З огляду на викладене табл. 5.20 з першим планом транспортної задачі має такий вигляд (початковий опорний план побудовано методом апроксимації Фогеля):

Таблиця 5.20

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

Після цього кроку заблокована клітинка А4B4 стає порожньою.

Дальше розв’язування задачі подано у вигляді табл. 5.21 та табл. 5.22.

В табл. 5.22 маємо оптимальний план транспортної задачі, де:

.

Zmin = 5 x 5 + 3 x 25 + 5 x 20 + 3 x 15 = 245 ум. од.

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

Альтернативний оптимальний план дістанемо, заповнивши клітинку А4В3 (для неї u4 + v3 = c43) згідно з таким циклом:

Тоді можна записати:

.

Zmin = 5 x 15 + 3 x 15 + 5 x 20 + 1 x 10 + 3 x 5 = 245 ум. од.

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

Існування двох альтернативних оптимальних планів розглянутої транспортної задачі розширює можливості стосовно остаточного прийняття рішення.