ТЕМА 6. ПОСТАНОВКА ТРАНСПОРТНОЇ ЗАДАЧІ. ЗНАХОДЖЕННЯ ЇЇ ПОЧАТКОВОГО РОЗВ’ЯЗКУ.

6.1. Визначення транспортної моделі та область її застосування.

Термін «транспортна задача» (ТЗ) об'єднує групу спеціальних ЗЛП, що відносяться до класу сітьових моделей. Згадана модель вперше була використана для складання найбільш економічного плану перевезень однорідної продукції з пунктів постачання до пунктів споживання; звідси - її назва. Проте область застосування моделей ТЗ є набагато ширшою: ці моделі використовуються для розвязання задач управління запасами, упорядкування змінних графіків роботи, призначення службовців на робочі місця, розподілу робіт між верстатами, регулювання витрат води у водоймищах та багатьох інших.

Розглянемо класичну однопродуктову модель ТЗ. Нехай потрібно перевезти продукцію певного виду з m вихідних пунктів до n пунктів призначення з мінімальними транспортними витратами. При цьому відомі обсяги виробництва в кожному вихідному пункті ai, обсяги споживання (попит) у кожному пункті призначення bj, вартість перевезення одиниці продукції з i-го пункту до j-го cij. (i=  ; j= ). Шуканими величинами (змінними) xij виступають обсяги перевезень продукції з пункту i до пункту j. Задача являє собою ЗЛП із цільовою функцією і системою обмежень, що наведені нижче.

z=  (6.1)

 (6.2)

Перша група m обмежень відбиває той факт, що обсяг продукції, вивезеної з будь-якого i-го пункту, не може перевищувати обсягу виробництва в цьому пункті. Друга група n обмежень указує на те, що сумарний обсяг поставок до кожного j-го пункту, не може бути меншим від рівня споживання в цьому пункті.

Якщо сумарні обсяги виробництва й споживання рівні (ai=bj) , всі обмеження задачі являють собою рівняння. У протилежному випадку модель є відкритою.

Приклад 6.1. Заводи деякої автомобільної фірми розташовані в пунктах А, В, С. Основні центри розподілу продукції зосереджені в пунктах D і Е. Обсяги виробництва вказаних трьох заводів складають відповідно 1000, 1500 і 1200 автомобілів на квартал. Розміри попиту дорівнюють 2300 і 1400 автомобілів відповідно. Вартість перевезення одного автомобіля по залізниці на 1 км шляху складає 0,08 г.о. Матриця відстаней між заводами і центрами розподілу наведена в табл. 6.1.

Таблиця 6.1. Матриця відстаней

          D         E

А       1000     2690

В       1250     1350

С       1275     850

Помноживши відстані між пунктами на вартість перевезення в розрахунку на 1 км шляху (0,08 г.о.), одержимо значення транспортних витрат Cij на перевезення одного автомобіля з i-го пункту в j-й:

C11=80; C12=215; C21=100; C22=108; C31=102; C32=68.

Лінійна оптимизаційна модель задачі матиме такий вигляд:

z=80x11+ 215x12+100x21+108x22+102x31+68x32®max

 

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

Кожний рядок транспортної таблиці відповідає i-му вихідному пункту; кожний стовпець - j-му пункту призначення. В лівому верхньому куті кожної клітини таблиці (крім клітин, розташованих в останньому рядку та останньому стовпчику) знаходиться величина Cij - витрати на перевезення одиниці продукції від i-го постачальника j-му споживачу. Останній рядок таблиці містить обсяги попиту на продукцію в пунктах споживання (ai), останній стовпчик - обсяги виробництва продукції у вихідних пунктах (bj). У правій нижній комірці табл. 5.2 записані значення загального обсягу продукції, що є у постачальників (Sai=3700 одиниць) та загальної потреби споживачів (Sbj=3700 одиниць).