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

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

Основні теоретичні відомості

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

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

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

Тоді при умові маємо закриту модель, а при умові – відкриту модель ТЗ.

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

План перевезень з вказанням запасів та потреб зручно записувати у вигляді таблиці (таблиця перевезень).

Пункти відправлення	Пункти призначення	Запаси
		...
			...
			...
...	...	...	...	...	...
			...
Потреби			...

Змінна означає кількість вантажу, який перевозиться з бази споживачу . Сукупність цих величин утворює матрицю перевезень.

Для розв’язку ТЗ необхідно, крім запасів та потреб знайти також і тарифи тобто вартість перевезень одиниці вантажу з бази споживачу .

Сукупність тарифів також утворює матрицю, яку можна об’єднати з матрицею перевезень та даними про запаси і потреби в одну таблицю.

Сума всіх витрат тобто вартість реалізації даного плану перевезень є лінійною функцією змінних , тобто

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

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

В першому випадку можемо виключити стовпчик, який містить заповнену клітину у другому випадку виключається стрічка, яка містить заповнену клітину.

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

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

Методи відшукання початкового опорного плану ТЗ

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

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

Метод мінімальної вартості. При цьому методі на кожному кроці заповнюється та клітина таблиці, яка має найменший тариф, якщо така клітина не єдина, то заповнюється будь-яка з них.

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

Нехай на три бази поступив однорідний вантаж в кількості 300т, 150т, 250т відповідно. Отриманий вантаж необхідно перевезти в п’ять пунктів – відповідно у кілкостях 170т, 110т, 100т, 120т, 200т. Відстані між пунктами відправлення і пунктами призначення вказані в таблиці: