Теоретичні основи програмного забезпечення дослідження операцій

Загальна схема та класифікація кінцевих методів розв’язування задач лінійного програмування

До класу задач лінійного програмування відноситься велика кількість різноманітних завдань планування та управління, як, наприклад:

• 1) знаходження оптимального плану випуску продукції (оптимальний розподіл ресурсів);
• 2) оптимізація міжгалузевих потоків (планування виробництва різних видів продукції по галузях);
• 3) визначення оптимального раціону (оптимізація складу хімічної суміші);
• 4) транспортна задача (оптимальний розподіл потоків товарних поставок з транспортної мережі);
• 5) завдання про розміщення виробництва (планування з урахуванням витрат на виробництво і транспортування продукції);
• 6) задача про призначення (оптимальний розподіл різних видів транспортних засобів) та інші.

Кожен кінцевий метод характеризується трьома основними моментами, а саме:

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

На рисунку 2.1 представлена загальна схема кінцевого методу. Для розв’язаних задач лінійного програмування будь-який кінцевий метод дозволяє через кінцеве число ітерацій знайти точне рішення задачі.

Усі кінцеві методи поділяються на три групи:

• — метод послідовного поліпшення плану (метод А);
• — метод послідовного уточнення оцінок (метод В);
• — метод послідовного скорочення неув’язок (метод С).

Методи, А і В можуть бути реалізовані двома алгоритмами:

• — A? І (B ?І)? перший алгоритм методу A (B);
• — A? II (B ?II)? другий алгоритм методу A (B).

На рисунку 2.1 зображена загальна схема кінцевого методу [2].

Рисунок 2.1 — Загальна схема кінцевого методу.