Закрита транспортна задача
Транспортна задача - одна з поширених завдань лінійного програмування.
Її мета - розробка найбільш раціональних шляхів і способів транспортування товарів, усунення надмірно далеких, зустрічних, повторних перевезень. Все це скорочує час просування товарів, зменшує витрати підприємств, фірм, пов'язані зі здійсненням процесів постачання сировиною, матеріалами, паливом, обладнанням і т.д.
У загальному вигляді завдання можна представити таким чином: в m пунктах виробництва A1, A2. Am є однорідний вантаж в кількості відповідно a1, a2, ..., am.
Цей вантаж необхідно доставити в n пунктів призначення B1, В2, .... Вn в кількості відповідно b1, b2. bn.
Вартість перевезення одиниці вантажу (тариф) з пункту Ai в пункт Bj дорівнює cij.
Потрібно скласти план перевезень, що дозволяє вивезти всі вантажі і має мінімальну вартість.
Залежно від співвідношення між сумарними запасами вантажу і сумарними потребами в ньому транспортні завдання можуть бути закритими і відкритими.
Визначення 1. Якщо
то задача називається закритою.
Позначимо через xij кількість вантажу, що перевозиться з пункту Ai в пункт Bj.
Розглянемо закриту транспортну задачу. Її умови запишемо в розподільну таблицю, яку будемо використовувати для знаходження рішення (табл. 23.1).
Математична модель закритої транспортної задачі має вигляд
Оптимальним вирішенням завдання є матриця
задовольняє системі обмежень і доставляє мінімум цільової функції.
Транспортна задача як завдання лінійного програмування може бути вирішена симплексним методом, однак наявність великої кількості змінних і обмежень робить обчислення громіздкими. Тому для вирішення транспортних завдань розроблений спеціальний метод, що має ті ж етапи, що і симплексний метод, а саме:
- знаходження вихідного опорного рішення;
- перевірка цього рішення на оптимальність;
- перехід від одного опорного рішення до іншого.