- Поняття транспортної задачі. Відкриті та закриті типи завдань
- Рішення транспортної задачі: приклад постановки, основні методи
На сьогоднішній день безліч підприємств займаються перевезенням продукції для її подальшої реалізації. Тому велике значення має процес оптимізації вантажоперевезень з метою мінімізації витрат на доставку вантажів. Цим питанням займається лінійне програмування, точніше таке його напрямок, як рішення транспортної задачі . Це питання і буде розглянуто далі в статті.
Сподобалося? Додайте в закладки
Поняття транспортної задачі. Відкриті та закриті типи завдань
Почнемо з визначення транспортної задачі. Умовно кажучи, у вас є товар, розташований на кількох складах. Необхідно доставити товар декільком споживачам - це можуть бути магазини, ларьки на ринку і т.д. - при цьому у вас є вибір з кількох маршрутів. Кожен споживач має свою потребу в товарі, кому-то потрібно отримати, наприклад, 10 тонн вантажу, а кому-то вистачить і 5 тонн товару.
Ясно, що вартість перевезення буде відрізнятися в залежності від кількості вантажу, що перевозиться і дальності шляху. Мінімізувати потрібно сумарні витрати на перевезення вантажу. Введемо необхідні позначення, нехай $ n $ - кількість складів, а $ m $ - кількість точок призначення (споживачів). Через $ С (i, j) = c_ {ij} $ позначимо вартість перевезення однієї одиниці вантажу з $ i $ -го складу до $ j $ -го споживача.
При цьому $ a (i) = a_i $ означає запас вантажу у $ i $ -го складу, а $ b (j) = b_j $ - потреба відповідного споживача. Ясно, що загальна вартість перевезення обчислюється як сума всіх витрат на перевезення товару від кожного складу до кожного споживача. Нехай вас не лякає така загальна постановка задачі, якщо з якогось складу не можна перевезти товар, наприклад через невигідного розташування, то відповідний $ b $ можна встановити рівним нулю.
Тепер можна перейти до математичної формулюванні завдання. Мовою формул завдання прийме наступний вигляд: $$ \ sum_ {i = 1} ^ {m} \ sum_ {j = 1} ^ {n} c_ {ij} x_ {ij} \ to \ min $$ при наступних обмеженнях: $$ \ left \ {\ begin {array} {l} \ sum_ {j = 1} ^ {n} x_ {ij} = a_i, \\ \ sum_ {i = 1} ^ {m} x_ {ij} = b_j, \\ x_ {ij} \ geq 0, c_ {ij} \ geq 0, a_ {i} \ geq 0, b_ {j} \ geq 0, \\ i = 1,2, ..., m; j = 1,2, ..., n. \ End {array} \ right. $$ У такій постановці все ясно і подальших пояснень не потрібно. Залишається тільки вирішити транспортну задачу.
Існує два різновиди транспортної задачі - відкрита і закрита. Закрита завдання характеризується тим, що сумарна потреба всіх споживачів дорівнює сумарними запасами всіх складів. Тобто, весь товар на всіх складах буде реалізований повністю. Математично це пишеться як $$ \ sum_ {i = 1} ^ {m} a_i = \ sum_ {j = 1} ^ {n} b_j. $$
У відкритій завданню сумарна потреба і сумарні запаси не збігаються. Наприклад, якийсь склад не реалізується товар повністю, з'являються залишки продукції. В цьому випадку процес вирішення транспортної задачі трохи ускладнюється, потрібно ввести фіктивного постачальника або споживача з нульовими вартостями перевезення.
Рішення транспортної задачі: приклад постановки, основні методи
Розглянемо приклад постановки простий транспортної задачі.
У наступній таблиці наведено вартості перевезень одиниці товару з певного складу до певного споживача.
Наприклад, число 7 в останньому рядку означає, що на перевезення одиниці товару з складу №3 до заводу З витрачається сім умовних одиниць грошей. При цьому 350 + 350 + 500 = 350 + 350 + 250 + 250 = 1200. Отже, потреби заводів рівні запасам всіх складів - це закрита завдання.
Для того щоб вирішити транспортну задачу використовується безліч методів. Залежно від особливостей задачі використовуються метод потенціалів, диференціальних рент (для пошуку оптимального плану), метод північно-західного кута, метод найменшого елемента (для пошуку опорного плану) і т.д. До сих пір одним з найпопулярніших залишається симплексний метод в силу його універсальності. Цей метод добре реалізований в надбудові «Пошук рішення», доступною в стандартній програмі Excel. Досить активувати «Пошук рішення» і ввести умови, і ви отримаєте докладний рішення.
Докладні приклади: Транспортні задачі з рішеннями .
Дякую за ваші закладки та рекомендації
додатково:
Транспортна задача на замовлення. Тільки на відмінно.
Сподобалося?
