Для отримання одиничної матриці необхідно до кожного рівняння в системі обмежень задачі додати одну змінну . Ці змінні називають штучними.
- (2) не містить жодного одиничного вектора:
(4)
Задачу з системою обмежень (4) називають розширеною, або М-задачею.
У результаті процедур симплексних перетворень виключалися з базису штучні змінні – їх вводять у цільову функцію з від’ємними коефіцієнтами:
()
- процедура симплексного методу одразу вилучає відповідні змінні з базису і забезпечує знаходження плану, в якому всі штучні змінні .
- якщо в оптимальному плані розширеної задачі існує хоча б одне значення , то це означає, що початкова задача не має розв’язку, тобто система обмежень несумісна.
- у таблиці оцінкові рядки поділені на дві частини-рядки: (m+2)-му рядку записують коефіцієнти з М,
(m+1)-му — ті, які не містять М.
Вектор, який підлягає включенню до базису, визначають за (m+2) рядком.
Ітераційний процес по (m+2) рядку проводять до повного виключення всіх штучних змінних з базису, потім процес визначення оптимального плану продовжують за (m+1) рядком.
Теорема 1. Якщо в оптимальному плані розширеної задачі штучні змінні , то план є оптимальним планом початкової задачі.
Випадки.
1. Якщо в оцінковому рядку останньої симплексної таблиці оцінка відповідає вільній (небазисній) змінній, то це означає, що ЗЛП має альтернативний оптимальний план.
2. Якщо при переході у симплекс-методі від одного опорного плану задачі до іншого в напрямному стовпчику немає додатних елементів , то це означає, що цільова функція задачі лінійного програмування є необмеженою й оптимальних планів не існує.
3. Якщо для опорного плану задачі лінійного програмування всі оцінки задовольняють умову оптимальності, але при цьому хоча б одна штучна змінна є базисною і має додатне значення, то це означає, що система обмежень задачі несумісна й оптимальних планів такої задачі не існує.