Алгоритм симплекс-метода.

I.По условию задачи составляется математическая модель.

II.Составленная модель преобразуется к канонической форме.

Предполагаем, что все дополнительные переменные имеют тот же знак, что и свободные члены. В противном случае используют М-метод, который будет рассмотрен ниже.

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

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

V.Если критерий оптимальности не выполнен, то наибольший по модулю определяет разрешающий столбец .

Составляют оценочные отношения каждой строки по следующим правилам:

1) , если и имеют разные знаки;

2) , если и ;

3) , если ;

4) 0, если и ;

5) , если и имеют одинаковые знаки.

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

VI.Переходят к следующей таблице по правилам:

1) В левом столбце записывают новый базис: вместо базисной переменной переменную ;

2) В столбцах, соответствующих базисным переменным, проставляют нули и единицы: 1 – против «своей» базисной переменной, 0 – против «чужой» базисной переменной, 0 – в последней строке для всех базисных переменных;

3) Новую строку с номером получают из старой делением на разрешающий элемент ;

4) Все остальные элементы вычисляем по правилу прямоугольника:

Далее переходят к п.IV.

Пример 1. Решить следующую ЗЛП симплексным методом

Решение.

Получаем, что базисные переменные – .

начальное опорное решение, .

Составим таблицу

Таблица 1

Базисные переменные	Свободный член	Переменные	Оценочное отношение
x1	x2	x3	x4	x5	x6
x3
x4
x5
x6
Z		-2	-3

После преобразований получаем таблицу

Таблица 2

Базисные переменные	Свободный член	Переменные	Оценочное отношение
x1	x2	x3	x4	x5	x6
x3						-3
x4						-1		5,5
x2
x6
Z		-2

Из таблицы 2 видим, что

Переходим к следующей таблице

Таблица 3

Базисные переменные	Свободный член	Переменные	Оценочное отношение
x1	x2	x3	x4	x5	x6
x1						-3
x4				-2
x2
x6				-3				12/9
Z						-3

Из таблицы 3 следует, что

Таблица 4

Получаем, что