40. Характеристика методу розв’язання транспортної задачі

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

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

Задача

Чотири підприємства для виробництва своєї продукції використовують сировину, яка знаходиться у трьох постачальників. Запаси сировини у постачальників відповідно рівні: у 1-го постачальника – 160 од., у 2-го постачальника – 140 од., у 3-го постачальника – 170 од. Потреби підприємств в сировині відповідно складають: 1-го підприємства – 120 од., 2-го підприємства – 50 од., 3-го підприємства – 190 од., 4-го підприємства – 110 од. Тарифи перевезень сировини від постачальників до підприємств наведені в таблиці:

Таблиця 41.1.

	Підприємство 1	Підприємство 2	Підприємство 3	Підприємство 4
Постачальник 1	7 грн.	8 грн.	1 грн.	2 грн.
Постачальник 2	4 грн.	5 грн.	9 грн.	8 грн.
Постачальник 3	9 грн.	2 грн.	3 грн.	6 грн.

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

Спочатку перевіримо, чи є дана транспортна задача відкритою чи закритою. Для цього порівнюють суму потреб підприємств із сумою можливостей постачальників. Якщо суми рівні, то задача є закритою, якщо ні – то відкритою. Відкриту задачу необхідно привести до закритої. Для цього у випадку перевищення можливостей постачальників над потребами підприємств вводять фіктивне підприємство, потреби якого дорівнюють різниці сум можливостей постачальників і потреб підприємств. Тариф перевезень від постачальників до фіктивного підприємства приймають рівним m (m=1000000), а у випадку перевищення потреб підприємств над можливостями постачальників вводять фіктивного постачальника, можливість якого дорівнює різниці сум потреб підприємств і можливостей постачальників; тариф перевезень від фіктивного постачальника до підприємств приймають рівним 0. У нашому прикладі задача є закритою (160+140+170=120+50+190+110=470). Далі розв‘язують задачу, використовуючи наступний алгоритм:

1. Складають математичну модель задачі: цільову функцію й систему обмежень.

2. Методом північно-західного кута або мінімального тарифу находять початковий план перевезень.

3. Розподільчим методом або методом потенціалів находять оптимальний план перевезень.

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

Таблиця 41.2.

	Підприємство 1	Підприємство 2	Підприємство 3	Підприємство 4
Постачальник 1			50 од.	110 од.
Постачальник 2	120 од.	20 од.
Постачальник 3		30 од.	140 од.

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

При такому плані перевезень транспортні витрати будуть мінімальними і складатимуть:

F(X)min=50*1+110*2+120*4+20*5+30*2+140*3=1330 (грн.)

На практиці транспортна задача, як правило, розв’язується із застосуванням ЕОМ.

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