Рассчитывают и заполняют начальную симплекс-таблицу с допустимым единичным базисом, включая индексную строку

2. В качестве направляющего столбца выбирают A _j, для которого

.

3. Направляющая строка A _і выбирают из условия

4. Делают один шаг (итерацию) метода полного исключения Гаусса с направляющим элементом a_ij, для чего используют соотношения (2.2.16) - (2.2.18). В частности, элементы индексной строки новой таблицы вычисляют в соответствии с формулой

l =1,2,..., n.

Правильность вычислений контролируют по формулам непосредственного счета:

(2.2.23)

(2.2.24)

В столбце B _x новой таблицы заменяют x_i на x_j, а в столбце С c_i на c_j.

5. Если все a_0l ^{(k+ 1)}³0, l= 1,…, n, то новое базисное решение x_i= a_{i 0}^{(k+ 1)}, i Î I_б ^{(k+ 1)} – оптимально. В противном случае переходят к этапу 2 и выполняют очередную итерацию.

6. Второй, третий и четвертый этапы повторяют до тех пор, пока одна из итераций не закончится одним из двух исходов:

а) все a_0l ³0. Это признак (критерий) оптимальности базисного решения последней симплекс-таблицы;

б) найдется такой a_0j= D _j <0, что все элементы этого столбца a_rj £0,
r = 1, …, m. Это признак неограниченности целевой функции z= c_jx_j на множестве допустимых решений задачи.

Назовем некоторые особенности применения табличного симплекс-метода.

Если в качестве начального базиса выбирают базис из свободных переменных, для которых c_i =0, то оценки для всех небазисных переменных равны D_j = a_0j = –c_j, а соответствующее значение целевой функции

a ₀₀= c_ix_i =0, i Î I_б.

Отсутствие векторов с отрицательными оценками при решении задач максимизации является признаком оптимальности соответствующего базисного решения.

Если существует такой небазисный вектор, для которого оценка отрицательна, а все элементы этого столбца неположительны, то целевая функция задачи в области допустимых решений неограничена.

При решении задач минимизации в базис вводится вектор с наибольшей положительной оценкой, а отсутствие таких векторов является признаком оптимальности последнего базисного решения.