Відмінності між версіями «Симплекс-метод розв’язування задач ЛП. Перехід від одного опорного плану до іншого»
Ярослав (обговорення • внесок) |
Ярослав (обговорення • внесок) |
||
| Рядок 11: | Рядок 11: | ||
Розглянемо задачу лінійного програмування, записану в канонічній формі: | Розглянемо задачу лінійного програмування, записану в канонічній формі: | ||
| − | <center><math>\max \,F=c_{1} x_{1} +c_{2} x_{2} +...+c_{n} x_{n} | + | <center><math>\max \,F=c_{1} x_{1} +c_{2} x_{2} +...+c_{n} x_{n} </math></center> |
| Рядок 24: | Рядок 24: | ||
Не порушуючи загальності, допустимо, що система рівнянь містить перші m одиничних векторів. Отримаємо: | Не порушуючи загальності, допустимо, що система рівнянь містить перші m одиничних векторів. Отримаємо: | ||
| − | <center><math>\max \,F=c_{1} x_{1} +c_{2} x_{2} +...+c_{n} x_{n} </math></center> | + | <center><math>\max \,F=c_{1} x_{1} +c_{2} x_{2} +...+c_{n} x_{n}~~~~~~(1) </math></center> |
Версія за 11:04, 4 травня 2012
СИМПЛЕКСНИЙ МЕТОД РОЗВ’ЯЗУВАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ
Задачі, що описують реальні економічні процеси, мають велику розмірність, і простий перебір всіх опорних планів таких задач є дуже складним, навіть за умови застосування сучасних ЕОМ. Тому необхідне використання методу, який уможливлював би скорочення кількості обчис¬лень. 1949 року такий метод був запропонований американським вченим Дж.Данцігом – так званий симплексний метод, або симплекс-метод. Ідея методу полягає в здійсненні спрямованого перебору допустимих планів у такий спосіб, що на кожному кроці здійснюється перехід від одного опорного плану до наступного, який за значенням цільової функції був би хоча б не гіршим за поперед¬ній. Значення функціонала при переході змінюється в потрібному напрямку: збільшується (для задачі на максимум) чи зменшується (для задачі на мінімум). Процес розв’язання задачі симплекс-методом має ітераційний характер: однотипні обчислювальні процедури (ітерації) повторюються у певній послідовності доти, доки не буде отримано оптимальний план задачі або з’ясовано, що його не існує. Отже,симплекс-метод – це ітераційна обчислювальна процедура, яка дає змогу, починаючи з певного опорного плану, за скінченну кількість кроків отримати оптимальний план задачі лінійного програмування.
1.1 Початковий опорний план
Розглянемо задачу лінійного програмування, записану в канонічній формі:
Не порушуючи загальності, допустимо, що система рівнянь містить перші m одиничних векторів. Отримаємо:
Загалом алгоритм розв’язування задачі лінійного програмування симплекс-методом складається з п’яти етапів:
1. Визначення початкового опорного плану задачі лінійного програмування.
2. Побудова симплексної таблиці.
3. Перевірка опорного плану на оптимальність за допомогою оцінок . Якщо всі оцінки задовольняють умову оптимальності, то визначений опорний план є оптимальним планом задачі. Якщо хоча б одна з оцінок не задовольняє умову оптимальності, то переходять до нового опорного плану або встановлюють, що оптимального плану задачі не існує.
4. Перехід до нового опорного плану задачі здійснюється визначенням розв’язувального елемента та розрахунками елементів нової симплексної таблиці.
5. Повторення дій, починаючи з п.3. Далі ітераційний процес повторюють, доки не буде визначено оптимальний план задачі. У разі застосування симплекс-методу для розв’язування задач лінійного програмування можливі такі випадки. 1. Якщо в оцінковому рядку останньої симплексної таблиці оцінка відповідає вільній (небазисній) змінній, то це означає, що задача лінійного програмування має альтернативний оптимальний план. Отримати його можна, вибравши розв’язуваль¬ний елемент у зазначеному стовпчику таблиці та здійснивши один крок симплекс-методом.
2. Якщо при переході у симплекс-методі від одного опорного плану задачі до іншого в напрямному стовпчику немає додатних елементів , тобто неможливо вибрати змінну, яка має бути виведена з базису, то це означає, що цільова функція задачі лінійного програмування є необмеженою й оптимальних планів не існує.
3. Якщо для опорного плану задачі лінійного програмування всі оцінки задовольняють умову оптимальності, але при цьому хоча б одна штучна змінна є базисною і має додатне значення, то це означає, що система обмежень задачі несумісна.
