Решение

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

Таблица 1.2.

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

Базисные переменные	Переменные x y s1 s2 s3.	Правая часть b
s1 s2 s3	3 0 1 0 0 0 2 0 1 0 1 1 0 0 1	27 30 29
Целевая функция, P	-2 –1 0 0 0	0

Шаг 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 30 20	27/3 = 9 ведущая строка 30/0 = 20/1 = 20
Целевая функция P	-2 -1 0 0 0	0

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

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

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

Таблица 1.4.

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

Базисные переменные	Переменные X y s1 s2 s3	Правая часть b
x s2 s3	1 0 1/3 0 0 0 2 0 1 0 0 1 -1/3 0 1	9 30 11	Новая R1 = прошлая R1 + ведущий элемент (3) Новая R2 = прошлая R2 – 0 х Новая R1 Новая R3 = прошлая R3 – 1 х Новая R1
Целевая функция P	0 -1 2/3 0 0	18	Новая P = прошлая P – -- (-2) х Новая R1

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

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

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

Таблица 1.5.