Решение. Реализация симплекс-метода значительно упрощается при использовании таблиц специального вида, называемых симплекс-таблицами

Симплекс-таблицы

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

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

(2.6)

Т.к. базисное решение является допустимым, то все . Целевая функция, выраженная через свободные переменные, имеет вид

.

Запишем коэффициенты системы (2.6) и целевой функции в таблицу следующим образом (табл. 2.1):

Таблица 2.1

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

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

.

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

.

Элемент , стоящий на пересечении разрешающих строки и столбца, называется разрешающим элементом.

Опишем процедуру перехода к новой симплекс-таблице и новому допустимому решению, увеличивающему значение целевой функции. Для построения новой симплекс-таблицы необходимо выполнить следующие операции:

1) поменять местами переменные и ;

2) на место разрешающего элемента поставить число ;

3) на остальных местах разрешающей строки записать соответствующие элементы исходной таблицы, деленные на разрешающий элемент;

4) на свободные места разрешающего столбца поставить со знаком
«-» соответствующие элементы исходной таблицы, деленные на разрешающий элемент;

5) остальные элементы вычислить по правилу прямоугольника (рис. 2.3):

.

Рис. 2.3. Правило прямоугольника

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

Пример 2.6. Решим задачу примера 2.1 с помощью симплекс-таблиц.

Х *= (6; 4; 0; 0; 1; 3); .