Симплекс-таблицы
Реализация симплекс-метода значительно упрощается при использовании таблиц специального вида, называемых симплекс-таблицами.
Рассмотрим задачу линейного программирования в каноническом виде и предположим, что известно какое-либо допустимое базисное решение этой задачи. Без ограничения общности можно считать, что базисный минор, соответствующий неосновным (свободным) переменным задачи, расположен в первых т столбцах системы ограничений. Тогда с помощью эквивалентных преобразований систему можно привести к следующему виду:
(2.6)
Т.к. базисное решение является допустимым, то все . Целевая функция, выраженная через свободные переменные, имеет вид
.
Запишем коэффициенты системы (2.6) и целевой функции в таблицу следующим образом (табл. 2.1):
Таблица 2.1
Предположим, что задача линейного программирования решается на максимум. Рассмотрим строку, содержащую коэффициенты целевой функции, и проверим выполнение критерия оптимальности. Возможны следующие варианты:
|
|
1. В строке целевой функции нет положительных коэффициентов. Тогда в соответствии с изложенным ранее, найденное допустимое решение является оптимальным. Полагая переменные равными нулю, находим
.
2. В строке целевой функции есть положительный коэффициент . Выделим в таблице соответствующий столбец (он называется разрешающим или опорным). В соответствии с симплекс-методом переменную следует перевести в базисные, поскольку ее увеличение приведет к росту значения целевой функции. Рассмотрим ограничения, накладываемые на рост переменной . Если все коэффициенты разрешающего столбца системы ограничений неположительны, то ни одно из уравнений не накладывает ограничений на рост и, следовательно, целевая функция не ограничена сверху (). Если в столбце есть положительные коэффициенты, то в качестве разрешающей выбираем строку с минимальным оценочным отношением, т.е. находим номер k базисной переменной из условия
.
Элемент , стоящий на пересечении разрешающих строки и столбца, называется разрешающим элементом.
Опишем процедуру перехода к новой симплекс-таблице и новому допустимому решению, увеличивающему значение целевой функции. Для построения новой симплекс-таблицы необходимо выполнить следующие операции:
1) поменять местами переменные и ;
2) на место разрешающего элемента поставить число ;
3) на остальных местах разрешающей строки записать соответствующие элементы исходной таблицы, деленные на разрешающий элемент;
4) на свободные места разрешающего столбца поставить со знаком
«-» соответствующие элементы исходной таблицы, деленные на разрешающий элемент;
|
|
5) остальные элементы вычислить по правилу прямоугольника (рис. 2.3):
.
Рис. 2.3. Правило прямоугольника
Для полученной симплекс-таблицы снова проверяем критерий оптимальности и т.д.
Пример 2.6. Решим задачу примера 2.1 с помощью симплекс-таблиц.
х 1 | х 2 | b | х 1 | х 5 | b | |||||
х 3 | 18:3=6 | х 3 | -3 | 3:1=3 | ||||||
х 4 | 16:1=16 | ® | х 4 | -1 | 11:2=5,5 | |||||
х 5 | 5:1=5 | х 2 | ||||||||
х 6 | х 6 | 21:3=7 | ||||||||
F | 2 | 0 | F | -3 | -15 | |||||
х 3 | х 5 | b | х 3 | х 4 | b | |||||
х 1 | -3 | х 1 | -0,2 | 0,6 | ||||||
х 4 | -2 | 5:5=1 | ® | х 5 | -0,4 | 0,2 | ||||
х 2 | 5:1=5 | х 2 | 0,4 | -0,2 | ||||||
х 6 | -3 | 12:9=1,3 | х 6 | 0,6 | -1,8 | |||||
F | -2 | -21 | F | -0,8 | -0,6 | -24 |
Х *= (6; 4; 0; 0; 1; 3); .