Транспортна задача лінійного програмування

Під назвою транспортна задача поєднується широке коло задач з єдиною математичною моделлю.

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

Однак, звичайна транспортна задача має велике число змінних і розв’язання її в такий спосіб може виявитись занадто громіздким.

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

Перш ніж перейти до розгляду основних методів розв’язання транспортної задачі, визначимо принципи її формулювання.

Нехай маємо m пунктів відправлення вантажів (постачальників) A1, A2, A3,..., Am, на яких зосереджені запаси якого-небудь однорідного вантажу в обсягах a1, a2, a3,..., am одиниць відповідно.

Величини Ai, при цьому, визначають максимально можливі розміри вивозу вантажу з пунктів відправлення.

Сумарний запас вантажу у постачальників становить a1 + a2 + a3 +...+ am одиниць.

Крім того, є n пунктів призначення (споживачів) B1, B2, B3,..., Bn, які подали заявки на поставку вантажу в обсягах b1, b2, b3,..., bn одиниць. Сумарна величина заявок становить b1 + b2 + b3 +...+ bn.

Вартість перевезення однієї одиниці вантажу від постачальника Ai до споживача Bj подані як лементи матриці C (транспортні тарифи):

Матриця тарифів

Тоді, транспортна задача формулюється наступним чином: необхідно скласти оптимальний план перевезень, тобто знайти такі значення об’єму перевезень xij, щоб вивести всі вантажі від постачальників, задовольнити заявки всіх споживачів і забезпечити мінімальні транспортні витрати на перевезення вантажу.

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

Математична модель транспортної задачі полягає в мінімізації функції:

Цільова функція транспортної задачі

при умовах:

Структура системи обмежень транспортної задачі

Будь-яке невід’ємне рішення системи лінійних рівнянь (2), (3), яке визначається матрицею X, називається планом перевезень транспортної задачі.

План перевезень, що має не більше m + n - 1 відмінних від нуля змінних xij, називається опорним.

Якщо число відмінних від нуля компонент в опорному плані, в точності, дорівнює m + n - 1, то план перевезень називається невироджених, якщо менше цього числа, то виродженим.

План перевезень X*, при якому функція (1) приймає своє мінімальне значення, називається оптимальним планом транспортної задачі.

На практиці при перевезенні вантажів можуть виникати такі ситуації:

Кількість одиниць вантажу у постачальників відповідає заявками або попиту з боку споживачів:

Збалансована транспортна задача

Зазначимо, що така транспортна задача є збалансованою, а її математична модель (записується у вигляді (1) – (4)) – закритою.

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

Незбалансована транспортна задача

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

Математична модель транспортної задачі такого типу буде мати вигляд:

Відкрита транспортна задача, відкрита модель транспортної задачі, транспортна задача математична модель

Кількість вантажу у всіх постачальників менша за потреби в даному вантажі у всіх споживачів:

Незбалансована транспортна задача

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

Відкрита транспортна задача, відкрита модель транспортної задачі, транспортна задача математична модель

Зазначимо, що математичні моделі (7) та (9) називаються відкритими, а відповідні їм задачі – незбалансованими. В даному випадку, їх необхідно звести до закритого типу.

У разі перевищення загального попиту над запасами (випадок 3) це здійснюється шляхом введення фіктивного (умовного) постачальника Am+1 з ресурсним запасом:

Транспортна задача, транспортна задача лінійного програмування

Якщо ж загальні запаси постачальників перевищують попит споживачів (випадок 2), то до закритого типу задача зводиться за допосогою введення фіктивного (умовного) споживача  з потребами:

Транспортна задача, транспортна задача лінійного програмування

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

Виходячи з того, що транспортна задача відноситься до класу задач лінійного програмування, то стратегія її рішення аналогічна:

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

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

Для знаходження початкового плану перевезень транспортної задачі існує декілька методів, а саме:

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

В загальному випадку метод Фогеля дає найкраще рішення, а спосіб північно-західного кута – найгірше. Однак метод північно-західного кута простіше реалізується і потребує меншого обсягу обчислень.

Найпоширенішими серед методів визначення оптимального плану транспортної зачі, є наступні:

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

Від цієї трудомісткої роботи нас позбавляє метод потенціалів.

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

Заводи деякої автомобільної фірми (постачальники) розташовані в містах A1, A2, A3. Основні центри розподілу продукції (споживачі) зосереджені в містах B1, B2.

Обсяг виробництва зазначених трьох заводів дорівнює a1 = 100, a2 = 130, a3 = 120 автомобілів щоквартально.

Величини квартального попиту в центрах розподілу становлять b1 = 230, b2 = 140 автомобілів відповідно.

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

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

Отже, як видно з вихідних даних задачі, сумарне виробництво автомобілів становить a1 + a2 + a3 = 350 одиниць за квартал, а сумарна потреба всіх пунктів розподілу становить b1 + b2 = 370 одиниць відповідно.

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

Для встановлення балансу введемо додатковий фіктивний завод A4 з щоквартальним обсягом виробництва a4 = 20 автомобілів.

Фіктивні тарифи c41 та c42, при цьому, прирівняємо до нуля, так як перевезення в дійсності здійснюватися не будуть.

Далі, позначимо кількість автомобілів, що перевозяться з -го заводу в j-й центр розподілу через xij і, для зручності, представимо умову задачі у вигляді транспортної таблиці.

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

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

Цільова функція транспортної задачі

невідомі величини якої повинні задовольняти наступним обмеженням:

Структура системи обмежень транспортної задачі

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

Також математичну модель слід доповнити умовою невід’ємності змінних:

Структура системи обмежень транспортної задачі

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

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

*