Визначення початкового рішення транспортної задачі.

Транспортна задача (задача Монжа — Канторовича) — задача про оптимальний план перевезення продукту (-тів) із пунктів відправлення до пунктів споживання. Розробка і використання оптимальних схем вантажних потоків дозволяють знизити витрати на перевезення. ТЗ по теорії складності обчислень є NP-складною або входить в клас складності NP. Коли сумарний обсяг пропозицій (вантажів, наявних в пунктах відправки) не дорівнює загальному обсягу попиту на товари (вантажі), які потрібні пунктам споживання, то транспортна задача називається незбалансованою.Специфічними для транспортної задачі є такі дві обставини:

1. кожна із змінних входить в два рівняння системи (1)-(2),

2. всі коефіцієнти при змінних приймають лише два значення 0 або 1.

Умови 1) і 2) дозволили розробити для вирішення транспортної задачі алгоритми, суттєво простіші, ніж симплексний метод, що є одним з основних методів вирішення задач лінійного програмування. Найвідомішими з цих алгоритмів є метод потенціалів і угорський метод.Метод потенціалів — це метод послідовного покращення плану (перевезень) з використанням другої теореми двоїстості для перевірки оптимальності.Угорський метод — це метод послідовної побудови допустимого плану, який автоматично виявляється оптимальним. В основі угорського алгоритму лежить метод чергування ланцюгів.

10. Содержание

    • Теоретичні питання
    • Загальна задача лінійного програмування (злп).
    • Постановка задачі. Побудова математичної моделі. Форми представлення злп.
    • Графічний метод розв’язання задачі лінійного програмування.
    • Симплекс-метод розв’язання задачі лінійного програмування.
    • Алгоритм симплекс-метода.
    • Теорія двоїстості. Двоїста задачі лінійного програмування.
    • Співвідношення між прямою та двоїстою злп.
    • Транспортні моделі. Визначення транспортної моделі. Методи розв’язання транспортної задачі.
    • Визначення початкового рішення транспортної задачі.
    • Метод північно-західного кута.
    • Метод мінімального елементу.
    • Транспортні моделі. Визначення оптимального рішення.
    • Сітьові моделі.
    • Цілочислове програмування.