У процесі перевірки умови оптимальності можливі такі випадки:
а) усі задовольняють умову оптимальності, і тоді визначений опорний план є оптимальним;
б) не всі задовольняють умову оптимальності, і тоді потрібно виконати перехід до наступного, нового опорного плану задачі.
4. Перехід від одного опорного плану до іншого виконується зміною базису, тобто виключенням з нього деякої змінної та введенням замість неї нової з числа вільних змінних задачі.
Змінна, яка включається до нового базису, відповідає тій оцінці , що не задовольняє умову оптимальності. Якщо таких оцінок кілька, серед них вибирають найбільшу за абсолютною величиною і відповідну їй змінну вводять до базису. Припустимо, що індекс зазначеної змінної Відповідний стовпчик симплексної таблиці називають напрямним.
Для визначення змінної, що має бути виключена з базису, знаходять для всіх додатних aik напрямного стовпчика величину . Вибирають найменше значення , яке вказує на змінну, що виводиться з базису. Припустимо, що це виконується для . Відповідний рядок симплексної таблиці називатиметься напрямним.
Перетином напрямного стовпчика та напрямного рядка визначається число симплексної таблиці ark, яке називають розв’язувальним елементом. За допомогою елемента ark і методу Жордана—Гаусса розраховують нову симплексну таблицю.
Далі ітераційний процес повторюють доти, доки не буде визначено оптимальний план задачі.
У разі застосування симплекс-методу для розв’язування задач лінійного програмування можливі такі випадки.
1. Якщо в оцінковому рядку останньої симплексної таблиці оцінка відповідає вільній (небазисній) змінній, то це означає, що задача лінійного програмування має альтернативний оптимальний план. Отримати