Для применения этого метода ЗЛП должна быть сформулирована в канонической форме (2.12)-(2.14), причем матрица системы уравнений должна содержать единичную подматрицу размером т x т. В этом случае очевиден начальный опорный план (неотрицательное базисное решение).

Для определенности предположим, что первые т векторов матрицы системы уравнений составляют единичную матрицу. Тогда первоначальный опорный план очевиден -

Проверка на оптимальность опорного плана проходит с помощью критерия (признака) оптимальности, переход к другому опорному плану - с помощью преобразований Жордана - Гаусса и с использованием признака оптимальности.

Полученный опорный план снова проверяется на оптимальность и т.д. Процесс заканчивается за конечное число шагов, причем на последнем шаге либо выявляется неразрешимость задачи (конечного оптимума нет), либо получается оптимальный опорный план и соответствующее ему оптимальное значение целевой функции.

Признак оптимальности заключается в следующих двух теоремах.

Теорема 2.3. Если для некоторого вектора, не входящего в базис, выполняется условие

(2.22)

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

а) если все компоненты вектора, подлежащего вводу в базис, неположительны, то ЗЛП не имеет решения (целевая функция неограничена);

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

Теорема 2.4. Если для всех векторов выполняется условие

то полученный опорный план является оптимальным.

На основании признака оптимальности в базис вводится вектор A_r,, давший минимальную отрицательную величину симплекс-разности:

Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор А_р который дает минимальное положительное оценочное отношение

(2.23)

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

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

Для использования приведенной выше процедуры симплекс-метода к минимизации линейной функции следует искать максимум функции , затем полученный максимум взять с противоположным знаком. Это и будет искомый минимум исходной ЗЛП.

Следует заметить, что зацикливание в симплекс-методе может иметь место также и в случае так называемого вырождения. При т ограничениях ЗЛП значения т базисных переменных, как правило, положительны, а значения остальных п - т свободных переменных всегда равны нулю. Однако возможно равенство нулю одной или нескольких базисных переменных; такой план называется вырожденным.

Вычисляемые по формуле (2.22) величины ∆_j называются симплексными разностями, или оценками, соответствующих переменных.

Так как в основе симплекс-метода лежит метод Жордана - Гаусса для системы линейных уравнений канонической формы ЗЛП, то при расчетах рекомендуется визуально проверять выполнение вытекающих из этого признаков: столбцы базисных векторов в симплексных таблицах имеют вид соответствующих столбцов единичной матрицы, а оценки базисных переменных всегда равны нулю.

Строка А_r называется направляющей, столбец А_к и элемент a_rk - направляющими (последний называют также разрешающим элементом и в сиплекс-таблицах выделяют рамкой).

Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по формулам

(2.24)

а элементы любой другой i-й строки пересчитываются по формулам

(2.25)

В соответствии с (2.24) и (2.25) значения базисных переменных нового опорного плана (показатели графы "план") рассчитываются по формулам

Таким образом, пересчет симплексных таблиц по формулам (2.24) и (2.25) проводится с помощью двух вычислительных процедур.

Процедура 1. Элементы вновь вводимой строки получаются путем деления элементов выводимой строки предыдущей таблицы на разрешающий (выделенный рамкой) элемент.

Процедура 2. Элементы других строк рассчитываются на базе преобразований Жордана - Гаусса, при этом целесообразно использовать так называемое правило прямоугольного треугольника. Суть этого правила заключается в том, что для расчета некоторого элемента новой таблицы (кроме элементов вновь вводимой строки) нужно выделить три числа:

1) соответствующий элемент (т.е. стоящий на том же месте) предыдущей таблицы;

2) элемент этой же строки предыдущей таблицы, стоящий в направляющем столбце;

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

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

Рассмотрим алгоритм симплекс-метода на конкретной задаче.

Пример 2.7. Для производства продукции типа П, и П₂ предприятие использует два вида сырья: С, и С₂ Данные об условиях производства продукции приведены в табл. 2.1.

Таблица 2.1