небазисні (додаткові записані в перший стовпець симплекса-таблиці а вихідні в перший рядок). При кожній ітерації елементи симплекс-таблиці перераховують за певними правилами.
Алгоритм симплекс-методу.
Підготовчий етап
Наводимо задачу ЛП до канонічного виду
F = a01x1 + a02x2 + ... a0nxn + b0? max
В
У разі якщо у вихідній задачі необхідно знайти мінімум - знаки коефіцієнтів цільової функції F змінюються на протилежні a0, n =-a0, n. Знаки коефіцієнтів обмежують умов зі знаком "?" Так само змінюються на протилежні. У разі якщо умова містить знак "?" - Коефіцієнти запишуться без змін. p> Крок 0. Складаємо симплексну таблицю, відповідну вихідної задачі:
x1x2 ... xn-1xnbF-a0 ,1-a0, 2 ...-a0, n-1-
Крок 1. Перевірка на допустимість. p align="justify"> Перевіряємо на позитивність елементи стовпця b (вільні члени):
1. Якщо серед них немає негативних то знайдено допустиме рішення (рішення відповідне одній з вершин багатогранника умов) і ми переходимо до кроку 2.
2. Якщо у стовпці вільних членів є негативні елементи то вибираємо серед них максимальний за модулем - він задає провідний рядок k. У цьому рядку так само знаходимо максимальний по модулю негативний елемент ak, l - він задає ведучий стовпець - l і є провідним елементом. Мінлива, відповідна провідною рядку виключається з базису, мінлива відповідна ведучому колонки включається в базис. Потім знову перераховуємо симплекс-таблицю згідно з правилами.
. Якщо ж серед вільних членів є негативні елементи - а у відповідному рядку - ні то умови задачі неспільні і рішень у неї немає.
. Якщо після перерахунку у стовпці вільних членів залишилися отріцаетельние елементи, то переходимо до першого кроку, якщо таких немає, то до другого.
Крок 2. Перевірка на оптимальність. p align="justify"> На попередньому етапі знайдено допустиме рішення. Перевіримо його на оптимальність:
1. Якщо серед елементів симплексного таблиці, находщіхся в рядку F (не беручи до уваги елемент b0 - поточне значення цільової функції) немає негативних, то знайдено оптимальне рішення.
2. Якщо в рядку F є негативні елементи те рішення вимагає поліпшення. Вибираємо серед негативних елементів рядка F максимальний по модулю (виключаючи значення функції b0) a0, l = min {a0, i}. Перший стовпець в якому він знаходиться буде ведучим. Для того, що б знайти провідну рядок, знаходимо відношення відповідного вільного члена і елемента з ведучого шпальти, за умови, що вони ненегативні.
/ak, l...
