Решение cимплекс-методом

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

Таблица 1.2.

Первая симплекс-таблица

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

Таблица 1.3.

Первая симплекс-таблица с учетом отношений

Базисные переменные	Переменные x y s1 s2 s3	Правая Часть b	Отношения b/ элемент ведущего столбца
S1 S2 S3	3* 0 1 0 0 0 2 0 1 0 1 1 0 0 1		27/3 = 9 ведущая строка 30/0 = 20/1 = 20
Целевая функция P	-2 -1 0 0 0

Ведущий столбец х

Шаг 3. Выберем среди полученных отношений наименьшее положительное отношение. В нашем случае оно равно 9. Соответствующая ему строка s₁ является ведущей. Пересечение ведущего столбца и ведущей строки дает ведущий элемент 3, в приведенной выше табл. 1.3 он отмечен знаком " *".

Шаг 4. Разделим все элементы ведущей строки на ведущий элемент, 3. Заменим все элементы ведущей строки на полученные новые значения (табл. 1.4) Обозначение ведущей строки s₁ заменим на обозначение ведущего столбца x. Новые переменные, соответствующие обозначениям строк, — это базисные переменные второго базисного решения.

Таблица 1.4.

Вторая симплекс-таблица

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

Обозначим через R_i i-ю строку. Соотношение " Новая R₃ = Прошлая R₃ - Новая R₁" означает, что новые элементы строки 3 были получены вычитанием элементов новой ведущей строки (строка 1) из соответствующих элементов ведущей строки 3 предыдущего шага. Выполненные операции перечислены в крайнем правом столбце табл. 1.4.

Шаг 6. Шаги 2-5 повторяются до тех пор, пока не будет достигнута неотрицательность всех элементов в строке целевой функции.

Таблица 1.5.

Вторая симплекс-таблица с отношениями

Базисные переменные	Переменные x y s1 s2 s3	Правая часть b	Отношения b/ элемент ведущего столбца
x s2 s3	1 0 1/3 0 0 0 2 0 1 0 0 1* -1/3 0 1		9/0 = 30/2 = 15 11/1 = 11 ведущая строка
Целевая функция P	0 -1 2/3 0 0

Ведущий столбец у

Таблица 1.6.

Третья, итоговая, симплекс-таблица

Теперь все элементы в строке целевой функции либо положительны, либо равны нулю, следовательно, представленное в данной таблице решение является оптимальным.

Чтобы дать интерпретацию итоговой симплекс-таблице, обратим сначала внимание на значения ее крайних элементов.

Таблица 1.7.