21 .Алгоритм симплексного методу для задач лінійного програмування.
Графічний метод для визначення оптимального плану задач лінійного програмування доцільно застосовувати лише для задач із двома змінними. За більшої кількості змінних необхідно застосовувати інший метод. З властивостей розв’язків задачі лінійного програмування відомо: оптимальний розв’язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв’язків. Тому найпростіший спосіб відшукання оптимального плану потребує перебору всіх кутових точок (допустимих планів задачі, які ще називають опорними). Порівняння вершин багатогранника можна здійснювати тільки після відшукання якоїсь однієї з них, тобто знайшовши початковий опорний план. Кожний опорний план визначається системою m лінійно незалежних векторів, які містяться в системі обмежень задачі з n векторів A1, A2,….,An!
Отже, загальна кількість опорних планів визначається кількістю комбінацій:
Задачі, що описують реальні економічні процеси, мають велику розмірність, і простий перебір всіх опорних планів таких задач є дуже складним, навіть за умови застосування сучасних ЕОМ. Тому необхідне використання методу, який уможливлював би скорочення кількості обчислень. 1949 року такий метод був запропонований американським вченим Дж. Данцігом — так званий симплексний метод, або симплекс-метод.
Ідея цього методу полягає в здійсненні спрямованого перебору допустимих планів у такий спосіб, що на кожному кроці здійснюється перехід від одного опорного плану до наступного, який за значенням цільової функції був би хоча б не гіршим за попередній. Значення функціонала при переході змінюється в потрібному напрямку: збільшується (для задачі на максимум) чи зменшується (для задачі на мінімум).
Процес розв’язання задачі симплекс-методом має ітераційний характер: однотипні обчислювальні процедури (ітерації) повторюються у певній послідовності доти, доки не буде отримано оптимальний план задачі або з’ясовано, що його не існує.
Отже, симплекс-метод — це ітераційна обчислювальна процедура, яка дає змогу, починаючи з певного опорного плану, за скінченну кількість кроків отримати оптимальний план задачі лінійного програмування.
Отже в загальному випадку алгоритм розв’язування задачі лінійного програмування симплекс-методом складається з п’яти етапів:
1. Визначення початкового опорного плану задачі лінійного програмування.
2. Побудова симплексної таблиці.
3. Перевірка опорного плану на оптимальність за допомогою оцінок . Якщо всі оцінки задовольняють умову оптимальності, то визначений опорний план є оптимальним планом задачі. Якщо хоча б одна з оцінок не задовольняє умову оптимальності, то переходять до нового опорного плану або встановлюють, що оптимального плану задачі не існує.
4. Перехід до нового опорного плану задачі виконується визначенням розв’язувального елемента та розрахунком нової симплексної таблиці.
5. Повторення дій починаючи з пункта 3.
- 1. Загальна економіко-математична модель задачі лінійного програмування. Допустимий та оптимальний план задачі лінійного програмування.
- 2. Завдання економетричного дослідження.
- 3. Двоїстість у лінійному програмуванні. Економічний зміст двоїстих оцінок.
- 4. Правила побудови двоїстих задач.
- 5. Геометрична інтерпретація задачі лінійного програмування.
- 6. Означення економетричної моделі.
- 7. Метод множників Лагранжа розв'язування нелінійних задач оптимізації.
- 8. Симплексний метод зі штучним базисом. Ознака оптимальності плану зі штучним базисом.
- 9. Етапи побудови економетричної моделі.
- 10. Довірчі інтервали значень парної лінійної функції регресії із заданою надійністю .
- 11 .Довірчі інтервали параметрів парної лінійної функції регресії із заданою надійністю .
- 12. Довірчі інтервали прогнозного значення парної лінійної функції регресії із заданою надійністю .
- 13. Алгоритм графічного методу розв'язування задач лінійного програмування.
- 14. Перша основна теорема двоїстості.
- 15. Друга основна теорема двоїстості.
- 16. Третя основна теорема двоїстості.
- 17. Довірчі інтервали для прогнозного значення Yp загальної лінійної економетричної моделі із заданою надійністю .
- 18. Оператор оцінювання 1мнк.
- 19. Економічна та математична постановка задачі дрібно-лінійного програмування.
- 20. Графічний метод розв'язування задач дрібно лінійного програмування.
- 21 .Алгоритм симплексного методу для задач лінійного програмування.
- 22. Метод розв'язування задачі дрібно лінійного програмування у загальному вигляді.
- 27. Постановка транспортної задачі.
- 28. Методи розв'язання транспортної задачі.
- 29. Методи знаходження початкового опорного плану транспортної задачі.
- 30. Порівняльна характеристика задач лінійного і нелінійного програмування.
- 1. Загальна економіко-математична модель задачі лінійного програмування. Допустимий та оптимальний план задачі лінійного програмування.
- 2. Завдання економетричного дослідження.