Опорний конспект лекцій з курсу Дослідження операцій Тема 10 Транспортні задачі лінійного програмування, НУДПСУ

Лекція №10. ТРАНСПОРТНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ. Критерій оптимальності базисного розв'язку транспортної задачі. Методи відшукання оптимального розв'язку

План

1. Економічні задачі, що легко зводяться до транспортної задачі.

2. Приклади задач транспортного типу.

3.5. Ускладнені задачі транспортного типу

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

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

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

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

3. Ряд транспортних маршрутів, за якими необхідно доставити вантажі, мають обмеження за пропускної спроможності. Якщо, наприклад, по маршруту A_iB_j можна провести не більш за q одиниць вантажу, то B_j -й стовпець матриці розбивається на два стовпці – B^*_j і B^**_j. У першому стовпці попит приймається рівним різниці між дійсним попитом b^*_j і обмеженням q: b^*_j = b_j – q, у другому – рівним обмеженню q, тобто b^**_j = q. Витрати c_ij в обох стовпцях однакові і дорівнюють даним, але в першому стовпці, в клітці, відповідній обмеженню i, замість дійсного тарифу c_ij ставиться штучно завищений тариф M (клітка блокується). Потім задача вирішується звичайним способом.

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

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

6. Необхідно максимізувати цільову функцію задачі транспортного типу. У цій ситуації при складанні опорного плану в першу чергу прагнуть заповнити клітки з найбільш високими значеннями показника c_ij. Вибір клітки, що підлягає заповненню при переході від одного допустимого плану до іншого, повинен проводитися не за мінімальною негативною різницею, а за максимальною позитивною різницею (с_ij – (a_i + b_j)). Оптимальним буде план, якому в останній таблиці супроводять вільні клітки з непозитивними елементами: всі різниці (с_ij – (a_i + b_j)) ≤ 0.

7. Необхідно в один час розподілити вантаж різного роду по споживачах. Задача даного типу називаються багатопродуктовими транспортними задачами. У цих задачах постачальники m родів вантажів розбиваються на m умовних постачальників, а споживачі n родів вантажів розбиваються на n умовних споживачів. З урахуванням цього розбиття складають повну транспортну таблицю. При цьому відмітимо, що деякі маршрути A_iB_j повинні бути блоковані (закриті), оскільки в даній постановці задачі вантажі різного роду не можуть замінювати один одного. Цим маршрутам A_iB_j повинна відповідати дуже висока вартість перевезення. Багатопродуктову задачу не завжди обов'язково описувати однією моделлю. Наприклад, якщо постачання вантажів різного роду незалежні, то й задачу можна представити у вигляді комплексу транспортних задач по кожному роду вантажу. Проте, якщо між вантажами різного роду існує зв'язок (наприклад, одні з вантажів можна замінити іншими), то в загальному випадку початкову модель (задачу) не вдається розбити на комплекс простих транспортних задач.

Розглянемо приклади задач транспортного типу.

Приклад 3.1. Одне фермерське господарство (A₁) має продовольче зерно двох видів: 3 тис. тонн – III класу і 4 тис. тонн – IV класу. Друге фермерське господарство (A₂) також має зерно двох видів: 5 тис. тонн – III класу і 2 тис. тонн – IV класу. Зерно повинне бути вивезене на два елеватори: на перший елеватор (B₁) необхідно поставити 2 тис. тонн пшениці III класу, 3 тис. тон пшениці IV класу та інші 2 тис. тонн пшениці будь-якого класу.

Аналогічно другий елеватор (B₂) повинен отримати 8,25 тис. тонн, з них пшениці – 1 тис. тонн III класу і 1,5 тис. тонн IV класу.

Вартість перевезення в г.о. 1 тонни зерна складає: з пункту A₁ в пункти B₁ і B₂ – 1 і 1,5 відповідно; з пункту A₂ в пункти B₁ і B₂ – 2 і 1 г.о. відповідно. Скласти оптимальний план перевезень.

Розв'язок

Кожного постачальника умовно розбиваємо на дві частини згідно до двох видів зерна (А³₁, А⁴₁, А³₂ і А⁴₂), аналогічно споживачів розбиваємо на три частини (пшениця III класу, IV класу і будь-який клас): В³₁ і В⁴₁, а також, В⁰₂. Потреби перевищують запаси, тому вводимо фіктивного постачальника A₃. Частину кліток в таблиці замикаємо великими числами М; наприклад, в клітці (1;2) ставимо велике число. Це означає, що постачальник А³₁ не може задовольнити споживача В⁴₁ пшеницею IV класу за рахунок наявної пшениці III класу.

З урахуванням зроблених зауважень складемо першу таблицю (табл. 3.6).

Таблиця 3.6. Початкові дані

Перевезення від фіктивного постачальника не проводяться, тому c₅₁ = c₅₂ + c₅₃ + c₅₄ + c₅₅ + c₅₆ = 0. Причому величина М набагато більше c_ij. Застосовуючи метод потенціалів, у результаті отримаємо таблицю з оптимальним розв'язком (табл. 3.7).

Таблиця 3.7. Оптимальний розв'язок

Аналіз розв'язку

Перший постачальник поставить на перший елеватор (B₁) пшеницю III класу (x₁₂ = 2); пшеницю IV класу (x₂₂ = 3), а також пшеницю будь-якого класу (III або IV) (x₁₃ = 1; x₂₃ = 1).

Другий постачальник (A₂) поставить на другий елеватор (B₂) пшеницю III класу (x₃₁ = 1), пшеницю IV класу (x₄₅ = 1,5) і частково будь-яку пшеницю (x₃₆ = 4; x₄₆ = 0,5). Потреба елеватора в будь-якій пшениці не задоволена на 1,25 тис. тон (x₅₆ = 1,25). Мінімальні витрати на перевезення склали: Z_min = 14 г.о.

Приклад 3.2. Модель виробництва з запасами. Фірма переводить свій головний завод на виробництво певного виду виробів, які випускатимуться в течію чотири місяців. Величини попиту протягом цих чотирьох місяців складають 100, 200, 180 і 300 виробів відповідно. У кожен місяць попит можна задовольнити за рахунок:

запасів виробів, що проведених минулого місяця, зберігаються для реалізації в майбутньому;

виробництва виробів протягом поточного місяця;

надлишку виробництва виробів в пізніші місяці в рахунок невиконаних замовлень.

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

Об'єм виробництва виробів міняється від місяця до місяця залежно від випуску інших виробів. У дані чотири місяці передбачається випуск 50, 180, 280 і 270 виробів відповідно.

Потрібно скласти план, що має мінімальну вартість виробництва і зберігання виробів.

Розв'язок

Задачу можна сформулювати як транспортну. Еквівалентність між елементами виробничої і транспортної систем встановлюється таким чином

Перед нами структура транспортної моделі. Для даної задачі вартість «перевезення» виробів з періоду i в період j виражається як.

З визначення c_ij виходить, що витрати в період i при реалізації продукції в той же період i (i = j) оцінюються тільки вартістю виробництва. Якщо в період i проводиться продукція, яка споживатиметься пізніше (i < j), то мають місце додаткові витрати, пов'язані із зберіганням. Аналогічне виробництво в i-й період в рахунок невиконаних замовлень (i > j) спричиняє за собою додаткові витрати у вигляді штрафу. Наприклад

с₁₁ = 4 г.о.,

c₂₄ = 4 + (0,5 + 0,5) = 5 г.о.,

c₄₁ = 4 + (2 + 2 + 2) = 10 г.о.

Початкова транспортна таблиця виглядає таким чином (табл. 3.8).

Таблиця 3.8. Оптимальний розв'язок

Приклад 3.3. Є три сорти паперу в кількості 10, 8 і 5 т, яку можна використовувати на те, що видало чотирьох книг тиражем 8000, 6000, 15000 і 10000 екземплярів. Витрата паперу на одну книгу складає: 0,6; 0,8; 0,4; 0,5 кг, а собівартість тиражу книги при використанні i-го сорту паперу задається наступною матрицею (г.о.).

Визначити оптимальний розподіл паперових резервів.

Розв'язок

Задача по своєму економічному сенсу не є транспортною, в той же час можна побудувати математичну модель, аналогічну транспортній задачі.

Потребі в папері легко визначити, знаючи тираж і витрату на одну книгу

8000*0,6 = 4,8 т;

15000*0,4 = 6 т;

8000*0,6 = 4,8 т;

10000*0,5 = 5 т.

Загальні запаси паперу складають 23 т, а загальні потреби – 20,5 т, тому необхідно в таблицю ввести фіктивний тираж B₅ з нульовими витратами. У зв'язку з тим, що складаємо модель щодо паперу, а матриця c_ij характеризує собівартість друкування книги, необхідно початкову матрицю перетворити щодо одиниці паперу (кожен стовпець матриці c_ij розділимо на кількість паперу, що доводиться на одну книгу).

Згідно викладеному складемо першу таблицю (табл. 3.9).

Таблиця 3.9. Початкові дані

Використовуючи метод потенціалів, отримаємо оптимальний розв'язок (табл. 3.10).

Таблиця 3.10. Оптимальний розв'язок

Аналіз розв'язку

Папери 1-го сорту в кількості 4,8 т витрачено на те, що видало другої книги; 2,8 т – на те, що видало четвертої книги; 2,4 т – не використано. Папери 2-го сорту витрачено: на першу книгу – 4,8 т; на те, що видало третьої книги 1 т; на те, що видало четвертої книги – 2,2 т; папір 3-го сорту використаний на те, що видало третьої книги в кількості 5 т.

Контрольні запитання

1. Які є методи підрахунку сум алгебри тарифів?

2. Що таке розподільний метод?

3. Що таке метод потенціалів?

4. Наведіть приклади економічних задач, що легко зводяться до транспортної задачі.

З повагою ІЦ “KURSOVIKS”!