Запишем задачу в стандартном виде

z-3x1-2x2=0

x1+2x2+s1= 6;

2x1+x2+s2= 8;

-x1+x2+s3= 1;

x1+s4= 2,

где s1, s2, s3, s4 – дополнительные неотрицательные переменные, которые вводятся в правые»£части ограничений имеющих знак «и называются остаточными. Если задача линейного программирования является задачей оптимального распределения ограниченных ресурсов, и правые части каждого ограничения представляют запасы ресурсов, то значения остаточных переменных в любом решении показывают остаток этих ресурсов. Матрица системы ограничений содержит единичную матрицу порядка 4. Ее образуют коэффициенты при остаточных переменных, значит переменные s1, s2, s3, s4 будут базисными переменными, а x1, x2 – свободными или нулевыми.

Шаг 0. Заполняем начальную симплекс-таблицу.

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

Столбец симплекс-таблицы, соответствующий включаемой переменной, будем называть ведущим столбцом. В нашем случае включаем в базис переменную x1.

 

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

Строку симплекс-таблицы, соответствующую исключаемой переменной, будем называть ведущей строкой. В нашем случае исключаем из базиса переменную s2.

Шаг 3. Вычисляем новое базисное решение и переходим

к шагу 1.

Симплекс-таблица, соответствующая первой итерации:

Решение не оптимально. Включаем в базис x2 вместо s1. Вторая итерация:

Решение оптимально.