Транспортна задача

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

Постановка задачі

Нехай у пунктах ${\displaystyle A_{1},A_{2},\ldots ,A_{m}}$ виробляється деякий однорідний продукт, причому обсяг виробництва цього продукту в пункті ${\displaystyle A_{i}}$ дорівнює ${\displaystyle a_{i}}$ одиниць, ${\displaystyle i=1,\ldots ,m.}$ Зроблений у пунктах виробництва продукт повинен бути доставлений до пунктів споживання ${\displaystyle B_{1},B_{2},\ldots ,B_{n},}$ причому обсяг споживання в пункті ${\displaystyle B_{j}}$ складає ${\displaystyle b_{j}}$ одиниць продукту. Вважається, що транспортування готової продукції можливе з будь-якого пункту виробництва в будь-який пункт споживання і транспортні витрати, що припадають на перевезення одиниці продукту з пункту ${\displaystyle A_{i}}$ в пункт ${\displaystyle B_{j},}$ складають ${\displaystyle c_{ij}}$ грошових одиниць. Задача полягає в організації такого плану перевезень, при якому сумарні транспортні витрати були б мінімальними.

Формально задача ставиться наступним чином. Нехай ${\displaystyle x_{ij}}$— кількість продукту, що перевозиться з пункту ${\displaystyle A_{i}}$ в пункт ${\displaystyle B_{j}.}$ Потрібно визначити сукупність з mn величин ${\displaystyle x_{ij},}$ які відповідають умовам:

1. ${\displaystyle \sum _{j=1}^{n}x_{ij}=a_{i}\quad \forall i}$
2. ${\displaystyle \sum _{i=1}^{m}x_{ij}=b_{j}\quad \forall j}$
3. ${\displaystyle x_{ij}\geq 0\quad \forall i\forall j}$

і для яких лінійна форма ${\displaystyle z=\sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}}$ набуває найменшого значення.

Група обмежень (1)-(2) пов'язана з тою обставиною, що обсяг вивезеного з кожного пункту виробництва продукту в точності дорівнює обсягу виробленого в цьому пункті продукту, а обсяг ввезеного в пункт споживання продукту відповідає його потребі. За цих обмежень необхідною і достатньою умовою для розв'язності транспортної задачі є виконання умови балансу:

${\displaystyle \sum _{i=1}^{m}a_{i}=\sum _{j=1}^{n}b_{j}}$

Приклад

Умови транспортної задачі зручно записувати за допомогою таблиці, що називається транспортною таблицею. Подана нижче таблиця відображає задачу з трьома пунктами виробництва ${\displaystyle A_{1},A_{2},A_{3},}$ що виробляють 15, 25 і 10 одиниць товару і чотирма пунктами споживання ${\displaystyle B_{1},B_{2},B_{3},B_{4},}$ попит в яких рівний, відповідно 5, 15, 15 і 15. На перетині рядка ${\displaystyle A_{i}}$ і ${\displaystyle B_{j}}$ подається значення ${\displaystyle c_{ij}}$ — вартість транспортування товару з пункту i в пункт j. Для даної задачі, наприклад ${\displaystyle c_{23}}$ рівне 9, тобто транспортування одиниці товару з пункту ${\displaystyle A_{2}}$ в пункт ${\displaystyle B_{3}}$ коштує 9 грошових одиниць.

	${\displaystyle B_{1}\,}$	${\displaystyle B_{2}\,}$	${\displaystyle B_{3}\,}$	${\displaystyle B_{4}\,}$	Кількість
${\displaystyle A_{1}\,}$	10	2	20	11	15
${\displaystyle A_{2}\,}$	12	7	9	20	25
${\displaystyle A_{3}\,}$	4	14	16	18	10
Кількість	5	15	15	15

Розв'язування

Специфічними для транспортної задачі є такі дві обставини:

1. кожна із змінних ${\displaystyle x_{ij}}$ входить в два рівняння системи (1)-(2),
2. всі коефіцієнти при змінних ${\displaystyle x_{ij}}$ приймають лише два значення 0 або 1.

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

Метод потенціалів — це метод послідовного покращення плану (перевезень) з використанням другої теореми двоїстості для перевірки оптимальності.

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

Початковий опорний план

Для початку розв'язування слід визначити початковий опорний план, тобто значення ${\displaystyle x_{ij}}$, що задовольняють умови (1)-(3), при чому лише щонайбільше n + m + 1 з них є ненульовими і не обов'язково досягається мінімум лінійної функції ${\displaystyle z=\sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}.}$ Найпоширенішими методами пошуку початкових опорних планів є метод північно-західного кута, метод найменшої вартості і метод Фогеля.

Метод північно-західного кута

Виконання починається з верхньої лівої клітини (Північно-західного кута) транспортної таблиці, тобто зі змінної ${\displaystyle x_{11}.}$

Крок 1. Змінній ${\displaystyle x_{11}}$ присвоюється максимальне значення, що допускається обмеженнями на попит і пропозицію.

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

Крок 3. Якщо не викреслено тільки один рядок або тільки один стовпець, процес зупиняється. В іншому випадку переходимо до клітини праворуч, якщо викреслять стовпець, або до клітини знизу, якщо викреслена рядок. Потім повертаємось до першого етапу.

Наприклад для попереднього прикладу початковий опорний план буде рівним:

	${\displaystyle B_{1}\,}$	${\displaystyle B_{2}\,}$	${\displaystyle B_{3}\,}$	${\displaystyle B_{4}\,}$	Кількість
${\displaystyle A_{1}\,}$	5	10			15
${\displaystyle A_{2}\,}$		5	15	5	25
${\displaystyle A_{3}\,}$				10	10
Кількість	5	15	15	15

В даній таблиці на перетині рядка ${\displaystyle A_{i}}$ і ${\displaystyle B_{j}}$ подано значення ${\displaystyle x_{ij}}$ в початковому опорному плані (пустим клітинам відповідає значення нуль).

Метод найменшої вартості

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

Наприклад для попереднього прикладу початковий опорний план буде рівним:

	${\displaystyle B_{1}\,}$	${\displaystyle B_{2}\,}$	${\displaystyle B_{3}\,}$	${\displaystyle B_{4}\,}$	Кількість
${\displaystyle A_{1}\,}$		15			15
${\displaystyle A_{2}\,}$		0	15	10	25
${\displaystyle A_{3}\,}$	5			5	10
Кількість	5	15	15	15

Метод Фогеля

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

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

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

Крок З.

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

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

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

г) У всіх інших випадках необхідно перейти до кроку 1.

Метод потенціалів

У методі потенціалів кожному рядку i і кожному стовпцю j транспортної таблиці ставляться у відповідність числа (потенціали) ${\displaystyle u_{i}}$ і ${\displaystyle v_{j}}$. Для кожної базисної змінної ${\displaystyle x_{ij},}$ потенціали ${\displaystyle u_{i}}$ і ${\displaystyle v_{j}}$ задовольняють рівнянню:

${\displaystyle u_{i}+v_{j}=c_{ij}\,}$

Щоб знайти значення потенціалів з цієї системи рівнянь, потрібно присвоїти одному з них довільне значення (зазвичай вважають ${\displaystyle u_{1}=0}$) і потім послідовно обчислювати значення інших потенціалів.

Далі, використовуючи знайдені значення потенціалів, для кожної небазисної змінної обчислюються величини ${\displaystyle u_{i}+v_{j}-c_{ij}}$.

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

${\displaystyle x_{ij}\to x_{i_{1}j_{1}}\to x_{i_{2}j_{2}}\to \ldots \to x_{ij},}$

де ${\displaystyle x_{ij}}$ — змінна, що вводиться в базис, а всі інші змінні є базисними. Окрім цього в цій послідовності при переході на кожному етапі одна координата залишається незмінною і якщо при певному переході незмінною була перша координата, то на наступному незмінною буде друга. Якщо зображувати перехід між змінними на транспортній таблиці стрілками між відповідними клітинами це означає, що переходи можуть бути лише вертикальними чи горизонтальними, але не діагональними, і також після горизонтального переходу має йти вертикальний і навпаки.

Після побудови послідовності ${\displaystyle x_{ij}\to x_{i_{1}j_{1}}\to x_{i_{2}j_{2}}\to \ldots \to x_{ij},}$ можна записати значення відповідних змінних і знайти мінімальне значення серед чисел, що стоять на непарних позиціях. Наступним кроком це число слід додати до всіх змінних, що стоять на парних позиціях і відняти від всіх змінних, що стоять на непарних. Змінна якій відповідало найменше число виводиться з базиса.

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

Приклад

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

Спершу обчислюємо значення потенціалів:

${\displaystyle u_{1}+v_{2}=2,\,}$

${\displaystyle u_{2}+v_{2}=7,\,}$

${\displaystyle u_{2}+v_{3}=9,\,}$

${\displaystyle u_{2}+v_{4}=20,\,}$

${\displaystyle u_{3}+v_{1}=4,\,}$

${\displaystyle u_{3}+v_{4}=18,\,}$

Взявши ${\displaystyle u_{1}=0}$ можна одержати інші значення потенціалів:

${\displaystyle u_{2}=5,u_{3}=3,v_{1}=1,v_{2}=2,v_{3}=4,v_{4}=15\,}$

Для небазисних змінних порахуємо ${\displaystyle u_{i}+v_{j}=c_{ij}:}$

${\displaystyle u_{1}+v_{1}-c_{11}=-9\,}$

${\displaystyle u_{1}+v_{3}-c_{13}=-16\,}$

${\displaystyle u_{1}+v_{4}-c_{14}=4\,}$

${\displaystyle u_{2}+v_{1}-c_{21}=-6\,}$

${\displaystyle u_{3}+v_{2}-c_{32}=-9\,}$

${\displaystyle u_{3}+v_{3}-c_{33}=-9\,}$

Серед одержаних значень є одне додатне, тому опорний план не є оптимальним, і змінну ${\displaystyle x_{14}}$ потрібно ввести в базис. Далі будується цикл ${\displaystyle x_{14}\to x_{24}\to x_{22}\to x_{12}\to x_{14}}$ і відповідні значення змінних 0, 10, 0, 15, 0. Найменше значення серед чисел на парних позиціях рівно 10, отже слід додати 10 до значень ${\displaystyle x_{14}}$ і ${\displaystyle x_{22}}$ (що стоять на непарних позиціях в послідовності) і відняти 10 від ${\displaystyle x_{24}}$ і ${\displaystyle x_{12}}$ що стоять на непарних позиціях в послідовності). Після цих змін одержується новий опорний план, що зображується в таблиці:

	${\displaystyle B_{1}\,}$	${\displaystyle B_{2}\,}$	${\displaystyle B_{3}\,}$	${\displaystyle B_{4}\,}$	Кількість
${\displaystyle A_{1}\,}$		5		10	15
${\displaystyle A_{2}\,}$		10	15		25
${\displaystyle A_{3}\,}$	5			5	10
Кількість	5	15	15	15

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

${\displaystyle x_{12}=5,\,x_{14}=10,\,x_{22}=10,\,x_{23}=15,\,x_{31}=5,\,x_{34}=5.}$ Для інших змінних значення рівні нулю.

Найменше значення цільової функції:

${\displaystyle z=\sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}=5\cdot 2+10\cdot 11+10\cdot 7+15\cdot 9+5\cdot 4+5\cdot 18=435}$

Узагальнення

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

Багатоіндексні транспортні задачі при збереженні загальної проблеми мінімізації транспортних витрат враховують неоднорідність вантажу (продуктів виробництва) і неоднорідність транспортних засобів.

Література

• Таха, Хемди А., Введение в исследование операций, 7-е издание.: Пер. с англ. — Москва: Издательский дом "Вильяме", 2005. — 912 с.
• Юдин Д.Б., Гольштейн Е.Г., Задачи и методы линейного программирования: Задачи транспортного типа. — Москва, 2010. — 184 с.
• Транспортна задача. Математична модель транспортної задачі (mathros.net.ua)