Решение задачи линейного программирования в симплексных таблицах. Правила построения симплексных таблиц
Рассмотрим схему построения на примере.
Пример 1:
3Х1+Х2 £ 4
Х1+3Х2 £ 4
Хj³0, j=1,...,4
Zmax=2+X1+2X2
Чтобы решить данную задачу линейного программирования симплексным методом, она должна быть представлена в канонической форме, система ограничений приведена к единичному базису, свободные члены уравнений должны быть неотрицательны .
Как видим, задача не приведена к канонической форме и к единичному базису. Поэтому вводим дополнительные переменные Х3 и Х4.
3Х1+Х2+Х3=4
Х1+3Х2+Х4=4
Хj³0, j=1,...,4
Zmax=2+X1+2X2 +0 × Х3 +0 × Х4
Составим первую симплексную таблицу. Она представляет собой форму выражения первого опорного плана. Коэффициенты стоящие в Z- строке, показывают как изменяется значение целевой функции при единичном изменении соответствующей свободной переменной. И называются эти коэффициенты оценкой или индексомэтой свободной переменной. А сама строка Z называется индексной или оценочной.
1. В первом столбце перечисляют базисные переменные.
2. Во второй столбец записывают оценки базисных переменных, указанные в целевой функции.
3. В третьем столбце указывают свободные члены.
4. В остальных столбцах таблицы записывают коэффициенты при свободных переменных по соответствующим уравнениям.
5. Над рабочей частью таблицы перечисляют свободные переменные.
6.Сверху над свободными переменными помещают оценки свободных переменных, указанные в целевой функции. Над столбцом свободных членов записывают свободный член целевой функции (если таковой имеется) с противоположным знаком.
7. Оценки Z – строки рассчитывают по формуле:
(2)
m
a0j=S Ciaij - Cj
i=1
где j=1, 2,…,n
aij – коэффициенты j –ого столбца,
Ci - коэффициенты при базисных переменных в уравнении Z,
Cj - коэффициенты при свободных переменных в уравнении Z.
Определение оптимальности плана. Построение новой симплексной таблицы
В симплексных таблицах формальным признаком оптимальности является содержание оценочной строки.
Ключевая теорема симплексного метода (Z на максимум):
Если после выполнения очередной итерации:
1) найдется хотя бы одна отрицательная оценка , а в столбце , где она стоит, есть хотя бы один положительный элемент , то опорное решение можно улучшить , выполнив следующую итерацию ;
2) найдется хотя бы одна отрицательная оценка , столбец которой не содержит положительных элементов , то функция Z неограниченна в области допустимых решений (Zmax ®+¥);
3) все оценки окажутся неотрицательными , то достигнуто оптимальное решение .
Согласно данной теоремы:
1. Просматриваются оценки Z - строки. Если они все неотрицательны, то получено оптимальное решение при решении на максимум целевой функции, если все оценки £ 0, то получено оптимальное решении при решении на минимум целевой функции.
2. Если оптимальное решение не получено, то выбирается разрешающий столбец по наибольшей по абсолютной величине отрицательной оценке Z - строки при решении на максимум и по наибольшей положительной оценке при решении на минимум целевой функции.
3. Составляются симплексные отношения - отношения свободных членов к положительным коэффициентам разрешающего столбца. Минимальное из этих отношений ( min íai 0/ aipý) определит разрешающую строку. Коэффициент, находящийся на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом.
Если в разрешающем столбце нет ни одного положительного коэффициента , то задача не имеет решения по причине неограниченности целевой функции (Zmax®+¥ ,Zmin®-¥ ).
4. Осуществляется переход к новой таблице, где базисная переменная заменяется на свободную, соответствующую разрешающему столбцу.
5. Бывший разрешающий элемент заменяется обратным по величине (1/ аqp).
6. Все остальные элементы бывшего разрешающего столбца делятся на разрешающий элемент и меняют знаки на противоположный.
Если в бывшем разрешающем столбце в какой-то строке стоял “0”, то эта строка переносится в следующую таблицу без изменений.
7. Все остальные элементы бывшей разрешающей строки делятся на разрешающий элемент .
Если в бывшей разрешающей строке в каком-то столбце стоял “0”, то этот столбец переносится в следующую таблицу без изменений.
8. Остальные элементы таблицы пересчитываются по правилу “прямоугольника”:
aqj. . . (aqp) i =1,2,..... j=0,1,..... , т.е. и столбцов свободных
членов.
9. Осуществляется контроль за правильностью расчетов для элементов Z-строки по формуле (2).
10. Если ошибок нет, то алгоритм повторяется с пункта 1.
В первой симплексной таблице нашего примера все коэффициенты оценочной строки отрицательны. Следовательно, согласно теореме, план (на максимум целевой функции) не является оптимальным и требует улучшения.
В последнем столбце рассчитывают симплексные отношения.
Таблица 2.1
Симплексная таблица (исходное опорное решение)
Св.П
Cj
-2
Б.П.
Ci
ai0
X1
X2
ai0/aip
X3
X4
(3)
4/3<
Z
-1
-2
Исходное опорное решение: Х1(0,0,4,4); Zmax=2
Во второй симплексной таблице меняем местами базисную переменную X4 и свободную X2.
На месте бывшего разрешающего элемента запишем обратную величину, т.е. 1/3.
Все остальные элементы разрешающей строки в новой таблице вычислим путем деления на разрешающий элемент: 4/3; 1/3.
Все остальные элементы бывшего разрешающего столбца определим путем деления на разрешающий элемент. Результат запишем в новую таблицу с противоположным знаком: -1/3; 2/3.
Все остальные элементы таблицы вычислим по правилу «прямоугольника».
Проверим правильность заполнения Z – строки по формуле (2).
а00 = 0 × 8/3 + 2 × 4/3 – (-2) = 14/3
а01 =0 × 8/3 + 2 × 1/3 – 1 = -1/3
а02 =0 ×(-1/3) + 2 × 1/3 – 0 = 2/3
Так как в оценочной строке есть еще отрицательные оценки, оптимальное решение не получено, можем записать только опорное решение:
X2( 0,4/3,8/3,0) Zmax=14/3
По тому же алгоритму пересчитываем коэффициенты четвертой таблицы.
Таблица 2.3.
Третья симплексная таблица
Св.П
Cj
-2
Б.П.
Ci
ai0
X3
X4
X1
3/8
-1/8
X2
-1/8
3/8
Z
1/8
5/8
Все оценки неотрицательны, следовательно, получено оптимальное решение Хопт(1,1,0,0) Zmax=5
Пример2
Задача решалась на максимум функции (Z® max). На последнем шаге была получена следующая таблица.
Таблица 2.4.
Последняя симплексная таблица
Св.П
Cj
Б.П.
Ci
ai0
X3
X2
X1
-1
X4
-1/2
Z
-2
В разрешающем столбце нет ни одного положительного элемента, следовательно, Zmax®+¥ ,т.е. задача линейного программирования не имеет решения по причине неограниченности целевой функции Z сверху.
Если среди оценок свободных переменных в последней симплексной таблице есть, хотя бы одна оценка равная нулю, то задача имеет альтернативное решение, т.е. хотя бы два оптимальных решения .Для этих решений экстремальное значение функции будет одинаковое. Чем больше будет нулевых оценок, тем больше - оптимальных решений .
3Х1+Х2 £ 4
3Х1+Х2+Х3=4