2. Табличний симплекс - метод
Основна ідея симплекс-методу полягає в переході від одного допустимого базисного рішення до іншого таким чином, що значення цільової функції при цьому безперервно зростають (для задач максимізації).
Припустимо, що обмеження задачі зведено до такого виду, що в матриці А є одинична подматріца і всі вільні члени позитивні. Іншими словами, нехай матриця обмежень має вигляд
A1x1 + ... + Anxn + e1xn + e1xn + 1 + ... + emxn + m = A0 = [ai0],
де
для всіх i = 1, 2,., n.
Застосуємо одну ітерацію методу повного виключення до розширеної матриці обмежень Ap = [A1, ..., An, e1, ..., em, A0].
Нехай aij - направляючий елемент перетворення на даній ітерації. Тоді в результаті перетворень відповідно до (1.10) отримаємо нові значення вільних членів:
Досліджуємо вираження (2.1) і з'ясуємо умови, при яких 
для всіх l, тобто нове базисне рішення буде також допустимим.
за припущенням 
, тоді
якщо 
, тоді , оскільки 
.
якщо 
, то
буде більше нуля при всіх l = 1, 2, ..., m тоді і тільки тоді, коли
Перетворення Гауса називають симплексним перетворенням, коли направляючий елемент визначають за такими правилами:
a) спрямовує стовпець j вибирають з умови, що в ньому є хоча б один позитивний елемент;
б) направляє рядок i вибирають так, щоб відношення 
було мінімально за умови, що aij> 0.
При такому перетворенні в базис вводиться вектор Aj і виводиться вектор Аi. Тепер треба визначити, як вибрати вектор, що вводиться в базис, щоб при цьому значення цільової функції збільшилася.
Для цього використовують так звані оцінки векторів 
:
де 
- безліч індексів базисних векторів; xij - визначають з умови
величини 
рівні симплекс -разніцам для змінних {xj} з протилежним знаком. Отже, для того щоб значення цільової функції збільшилася, необхідно вибрати направляючий стовпчик Аj з найбільшою за модулем негативною оцінкою, тобто
Для вирішення завдання симплекс-методом на кожній ітерації заповнюють симплекс-таблицю 2.1 .
Останній рядок таблиці - індексна - служить для визначення направляючого стовпця. її елементи визначають за формулою (2.3). Очевидно, для всіх базисних векторів {Ai} i = 1,., M оцінки 
.
Значення цільової функції a00 визначається зі співвідношення
У стовпці Bx записуємо базисні змінні {xi} i = 1, ..., m. Їх значення визначаються стовпчиком вільних членів ai0, тобто
Напрямні рядок Ai і стовпець Aj вказуються стрілками. Якщо в якості направляючого елемента обраний aij, то перехід від даної симплекс-таблиці до наступної визначається співвідношеннями (1.8) - (1.10).
Отже, алгоритм вирішення задачі ЛП табличним симплекс-методом складається з етапів.
1. Розраховують і заповнюють початкову симплекс-таблицю з допустимим одиничним базисом, включаючи індексний рядок.
2. В якості направляючого стовпця вибирають Aj, для якого
3. Напрямна рядок Aі вибирають з умови
4. Роблять один крок (ітерацію) методу повного виключення Гаусса з напрямних елементом aij, для чого використовують співвідношення (1.8) - (1.10). Зокрема, елементи індексного рядка нової таблиці обчислюють відповідно до формули
Правильність обчислень контролюють за формулами безпосереднього рахунку: В стовпці Bx нової таблиці замінюють xi на xj, а в стовпці С ci на cj.
5. Якщо все 
, То нове базисне рішення 
- оптимально. В іншому випадку переходять до етапу 2 і виконують чергову ітерацію.
6. Другий, третій і четвертий етапи повторюють до тих пір, поки одна з ітерацій не закінчиться одним з двох випадків:
а все 
. Це ознака (критерій) оптимальності базисного рішення останньої симплекс-таблиці;
б) знайдеться такий 
, Що всі елементи цього шпальти 
. Це ознака необмеженості цільової функції 
на безлічі допустимих рішень задачі.
Назвемо деякі особливості застосування табличного симплекс-методу.
Якщо в якості початкового базису вибирають базис з вільних змінних, для яких ci = 0, то оцінки для всіх небазисних змінних рівні 
, А відповідне значення цільової функції
Відсутність векторів з негативними оцінками при вирішенні задач максимізації є ознакою оптимальності відповідного базисного рішення.
Якщо існує такий небазисной вектор, для якого оцінка негативна, а всі елементи цього шпальти непозитивні, то цільова функція задачі в області допустимих рішень необмежена.
При вирішенні завдань мінімізації в базис вводиться вектор з найбільшою позитивною оцінкою, а відсутність таких векторів є ознакою оптимальності останнього базисного рішення.
