Розв’язування транспортної задачі

Транспортну задачу можна розглядати як задачу лінійного програмування. Для її розв’язування придатний вже розглянутий симплекс-метод. Для кожної транспортної задачі можна вказати допустиму область, допустимий розв’язок та знаходити оптимальний шляхом заміни базисних змінних. Однак, велика кількість змінних (m x n) робить застосування симплекс-методу громіздким та нераціональним. Більш ефективним є застосування спеціального методу знаходження оптимального розв’язку – транспортного методу. Цей метод полягає в послідовному уточненні допустимого розв’язку.

Для застосування транспортного методу необхідно мати деякий початковий допустимий розв’язок. Його можна знайти за допомогою методу північно-західного кута. Розглянемо це правило на попередньому прикладі (Рис. 2.18).

					--	---	--	---	--	---	--
									--	---	--
				|		|
				|		|

Рис. 2.18. Знаходження допустимого розв’язку

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

Спочатку вибираємо верхню ліву клітинку. У ній повинна бути записана кількість товару, перевезеного з складу № 1 споживачу № 1. На цьому складі знаходиться 10 одиниць товару, а перший споживач може прийняти 15 одиниць. Тому весь товар з першого складу передаємо першому споживачеві, на цьому складі залишається 0 одиниць (залишок записуємо ліворуч в першому рядку, в клітинку першого рядка та першого стовпчика записуємо 15, решта клітинок першого рядка викреслюємо), а першому споживачу бракує ще 5 одиниць (недостачу записуємо вище в першому стовпчику). Цих 5 одиниць можемо йому передати зі складу № 2, на що вкажемо, заповнивши клітинку числом 5 у другому рядку та першому стовпчику (на складі № 2 тоді залишиться 10 одиниць, що відзначаємо в другому рядку ліворуч), а перший споживач товаром стане забезпечений (відзначаємо вище в першому стовпчику 0, а решту незаповнених клітинок першого стовпчика викреслюємо). На другому складі залишається ще 10 одиниць товару, з яких максимально можливу кількість – 5 передаємо споживачу № 2 (записуємо 5 у другому рядку та другому стовпчику), який тим самим вже забезпечений товаром (відзначаємо вище в другому стовпчику 0 та викреслюємо решту клітинок). Залишок – 5 одиниць з другого складу передаємо споживачу № 3, про що робимо відмітки у відповідних рядках та стовпчиках. Споживач № 3 внаслідок цього ще не повністю забезпечений. Тому йому передають товар у кількості 5 одиниць зі складу № 3. Після цього залишок на складі № 3 – 15 одиниць, який повністю забезпечує потреби споживача № 4. Таким чином, ми побудували допустимий розв’язок, знайшовши значення допустимих змінних x ₁₁=10, x ₂₁=5, x ₂₂=5, x ₂₃=5, x ₃₃=5, x ₃₄=15, решта змінних мають нульове значення.

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

		---	--	---	--	---	--		--
		|						|
		|						|
		|						|
			--	---	--	---	--

Рис. 2.19. Знаходження допустимого розв’язку з урахуванням вартостей.

Для знаходження допустимого розв’язку методом з урахуванням вартостей (Рис. 2.19) виберемо клітинку з найменшою вартістю перевезень min{ p_ij }= p ₁₄=1. Здійснимо перевезення зі складу № 1 до споживача № 4. Ми можемо перевезти 10 одиниць продукції, після чого склад № 1 стане порожнім. Викреслимо перший рядок. Після цього другу клітинку вибираємо з частини таблиці, яка залишилася також з мінімальною вартістю перевезень. Такою вартістю будуть p ₃₄= p ₃₁=2. Виберемо, наприклад, третій склад і четвертого споживача. Останній вже буде забезпечений товаром, тому викреслюємо четвертий стовпчик. У таблиці, що залишилася, найменшу вартість буде мати перевезення зі складу № 3 споживачу № 1 (p ₃₁=2). Тому перевозимо 15 одиниць та викреслюємо стовпчик № 1 та рядок № 3. Наступним перевезенням з найменшою вартістю буде зі складу № 2 до споживача № 3 (p ₂₃=4). Тут перевозимо 10 одиниць. І, нарешті, перевозимо товар зі складу № 2 до споживача № 2. Це останнє перевезення в кількості 5 одиниць. В результаті ми заповнили таблицю значеннями, які вказують скільки потрібно перевезти одиниць, звідки і куди.

Обчислимо вартості перевезення, отримані з допомогою методів північно-західного кута та з урахуванням вартостей:

K _{півн.-зах.}=10×4+5×9+5×7+5×4+5×3+15×2=185,

K _варт.=15×2+5×7+10×4+10×1+5×2=125.

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

Проте це ще не оптимальна (мінімальна) вартість. Для одержання оптимального розв’язку та відповідного йому плану перевезень застосовують транспортний метод, на якому зупинимося докладніше.

a 1

a 2

…

…

…

an

p 11

p 12

p 1 n

u 1

b 1

x 11

x 12

x 1 n

…

pm 1

pm 2

pmn

un

bm

xm 1

xm 2

xmn

v 1

v 2

vm

Рис. 2.20.

Нехай маємо деяку транспортну таблицю (Рис. 2.20) з допустимим розв’язком, одержаним будь-яким з розглянутих методів. Запишемо в таблиці значення вартостей лише таких перевезень, для яких заповнено клітинки з кількістю перевезень, для тих, що дорівнюють 0 вартості поки що не заповнюємо.

Запишемо значення потенціалів – чисел u_i та v_j у рядок та стовпчик після останніх рядка та стовпчика таблиці таким чином, щоб

p_ij=u_i+v_j, 1£ i £ n, 1£ j £ m. (2.13)

Система лінійних рівнянь (2.13) має m+n невідомих, її матриця може бути зведена до трикутного вигляду з рангом m+n –1. Для розв’язку цієї системи одну із змінних u_i чи v_j вибирають рівною 0, а решту послідовно знаходять.

Після знаходження потенціалів записуємо на незаповнені місця вартості за правилом

p’_ij= p_ij–u_i–v_j. (2.14)

Якщо всі одержані p’_ij ³0, тоді розв’язок оптимальний.

Якщо існують p’_ij <0, тоді вибираємо найменший з них та позначаємо клітинку знаком +. Змінна, що відповідає цій клітинці, повинна ввійти в базис. Крім неї позначимо знаками + та – клітинки, зайняті значеннями змінних x_ij так, щоб в кожному рядку та кожному стовпчику ще був один знак + та –.

Знаходимо М – мінімум чисел x_ij, позначених знаком – та забираємо з клітинки число М, залишивши її порожньою та записуючи його в початкову клітинку зі знаком +. Для інших клітинок число М віднімається від записаного (якщо знак –) та додається (якщо знак +).

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

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

Приклад. Знайти оптимальний розв’язок транспортної задачі (Рис. 2.21).

Рис. 2.21.

Знайдемо допустимий розв’язок транспортної задачі з урахуванням вартостей (рис. 2.22).

Рис. 2.22.

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

						-		+
						-2
						+		-
		-8		-4

Рис. 2.23.

Оскільки є від’ємні вартості, то розв’язок неоптимальний. Найменшою вартістю є –2 в клітинці на перетині першого рядка і другого стовпчика. Ставимо знак + в цій клітинці та в клітинці на перетині другого рядка та четвертого стовпчика, а – у клітинках другого рядка та третього стовпчика та третього рядка і четвертого стовпчика.

Модифікуємо транспортну таблицю (Рис. 2.24). У клітинках, позначених знаками – знаходимо мінімум записаних значень М =2. Клітинку з цим числом залишаємо незаповненою. Від іншої клітинки зі знаком – віднімаємо число М, а до кожної з клітинок зі знаками + додаємо число М. Решту значень переписуємо без зміни.

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

		-6		-2

Рис. 2.24.

Таким чином, найоптимальнішим буде перевезення, при якому кількості товару, перевезеного з i -го складу до j -го споживача будуть визначатися такими числами x ₁₃=12, x ₂₃=6, x ₂₄=8, x ₃₁=8, x ₃₂=6, x ₃₃=2.

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