Лоїк Ірина

Науковий керівник: Леонтюк-Мельник О.В

Вінницький національний аграрний університет

Транспортна задача: постановка, види та методи вирішення

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

Використання розрахунків транспортних задач дозволяє скоротити транспортні витрати на 15-20% [4].

Транспортна задача (ТЗ) поділяється на два типи: ТЗ по критерію вартості – визначення плану перевезень, при якому вартість вантажу була б мінімальна; ТЗ по критерію часу – важливішим є виграш за часом.

Постановка транспортної задачі включає в себе:

1) множину постачальників ();

2) множину покупців (замовників) ;

3) матрицю початкових маршрутів перевезень від покупців до постачальників:

				…
				…
				…
				…
…	…	…	…	…	…
				…

– кількість вантажу (постачання), яке потрібно перевезти від -го постачальника до -го замовника;

4) нормовану матрицю транспортних перевезень по транспортних витратах:

=

– транспортні витрати по маршруту перевезень від -го постачальника до -го замовника;

5) функцію мети: (1)

За обмежень: ; ;

У розглянутій задачі має виконуватися умова:

Закрита модель (збалансована) транспортної задачі отримується, якщо виконується умова (5). Для відкритої моделі (незбалансована) згадана рівність (5) не витримується.

Будь-яке рішення ТЗ зветься розподілом постачання. Постачання не може бути від’ємним, тому мова може йти лише про припустимі рішення.

Якщо в задачі зазначається те, що із кожного пункту відправлення можна перевозити продукцію декількох видів, то при побудові моделі можна використовувати один з наступних варіантів: кожному виду продукції має відповідати одна транспортна матриця; всі види продукції представлені у одній спільній матриці з використанням тарифів, які заборонені, в клітинках, що зв’язують різні види продукції [2].

Опорний план є допустимим рішенням ТЗ і використовується в якості початкового базисного рішення при побудові оптимального рішення методом потенціалів. Існує три методи побудови опорних планів: метод північно-західного кута, метод мінімального елемента і метод Фогеля (дає найкраще рішення). Всі методи відрізняються один від одного лише способом вибору клітинки для заповнення, а саме заповнення відбувається однаково.

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

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

Метод Фогеля. На кожному кроці для кожної -тої стрічки (j-го стовпця) вираховуються штрафи () як різниця між двома найменшими тарифами стрічки (стовпця). Потім обирається максимальний штраф із стрічок та стовпців. У стрічці чи стовпці, що відповідає обраному штрафу, для заповнення обирається не викреслена клітинка з мінімальним тарифом. Якщо існує декілька однакових по величині максимальних тарифів, то у відповідних стрічках чи стовпцях обирається одна не викреслена клітинка з мінімальним тарифом. Якщо клітинок з мінімальним тарифом також декілька, то з них обирається клітинка () з максимальною сумою штрафів по -тій стрічці та j-му стовпцю [2].

Метод потенціалів. Кожному рядку i і кожному стовпцю j ставляться у відповідність числа (потенціали) і . Для кожної базисної змінної потенціали і задовольняють рівняння: =. Щоб знайти значення потенціалів з цієї системи рівнянь, потрібно присвоїти одному з них довільне значення і потім послідовно обчислювати значення інших потенціалів. Далі, використовуючи знайдені значення потенціалів, для кожної небазисной змінної обчислюються величини: =. Якщо всі ці числа є недодатними, то опорний план є оптимальним і розв'язування завершується. В іншому випадку, знаходиться найбільше додатнє значення і відповідна йому змінна вводиться в базис. Для визначення змінної, що виводиться з базису будується послідовність: , де – змінна, що вводиться в базис. При переході на кожному етапі одна координата залишається незмінною і, якщо при певному переході незмінною була перша координата, то на наступному − незмінною буде друга. Якщо зображувати перехід між змінними на транспортній таблиці стрілками, то вони можуть бути лише вертикальними чи горизонтальними, але не діагональними, і також після горизонтального переходу має йти вертикальний і навпаки. Побудувавши послідовність , можна записати значення відповідних змінних і знайти мінімальне значення серед чисел, що стоять на непарних позиціях. Потім це число слід додати до всіх змінних, що стоять на парних позиціях і відняти від всіх змінних, що стоять на непарних. Змінна якій відповідало найменше число виводиться з базиса.

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

Література:

1) Васильев Ф.П. Линейное програмирование / Ф.П. Васильев, А.Ю. Иваницкий – М.: Факториал Пресс, 2003. – 352с.

2) Лысак А.В., Голян В.В. Методы линейного проектирования в транспортных задачах // Інформаційно-керуючі системи на залізничному транспорті. – 2009. – №1. – С. 7-11.

3) Серая О.В. Стохастическая транспортная задача. Континуальная модель // Інформаційно-керуючі системи на залізничному транспорті. – 2009. – №1. – С. 18-21.

4) www.sworld.com.ua/index.php/ru/transportation-411/transport-and-logistics-411/11399-411-0015