Визначення початкового рішення транспортної задачі.
Транспортна задача (задача Монжа — Канторовича) — задача про оптимальний план перевезення продукту (-тів) із пунктів відправлення до пунктів споживання. Розробка і використання оптимальних схем вантажних потоків дозволяють знизити витрати на перевезення. ТЗ по теорії складності обчислень є NP-складною або входить в клас складності NP. Коли сумарний обсяг пропозицій (вантажів, наявних в пунктах відправки) не дорівнює загальному обсягу попиту на товари (вантажі), які потрібні пунктам споживання, то транспортна задача називається незбалансованою.Специфічними для транспортної задачі є такі дві обставини:
-
кожна із змінних входить в два рівняння системи (1)-(2),
-
всі коефіцієнти при змінних приймають лише два значення 0 або 1.
Умови 1) і 2) дозволили розробити для вирішення транспортної задачі алгоритми, суттєво простіші, ніж симплексний метод, що є одним з основних методів вирішення задач лінійного програмування. Найвідомішими з цих алгоритмів є метод потенціалів і угорський метод.Метод потенціалів — це метод послідовного покращення плану (перевезень) з використанням другої теореми двоїстості для перевірки оптимальності.Угорський метод — це метод послідовної побудови допустимого плану, який автоматично виявляється оптимальним. В основі угорського алгоритму лежить метод чергування ланцюгів.
-
Содержание
- Теоретичні питання
- Загальна задача лінійного програмування (злп).
- Постановка задачі. Побудова математичної моделі. Форми представлення злп.
- Графічний метод розв’язання задачі лінійного програмування.
- Симплекс-метод розв’язання задачі лінійного програмування.
- Алгоритм симплекс-метода.
- Теорія двоїстості. Двоїста задачі лінійного програмування.
- Співвідношення між прямою та двоїстою злп.
- Транспортні моделі. Визначення транспортної моделі. Методи розв’язання транспортної задачі.
- Визначення початкового рішення транспортної задачі.
- Метод північно-західного кута.
- Метод мінімального елементу.
- Транспортні моделі. Визначення оптимального рішення.
- Сітьові моделі.
- Цілочислове програмування.