Симплексные таблицы
Практические расчеты с использованием симплекс метода – на компьютере. Если вручную, то используются симплекс-таблицы. Будем решать задачу на максимум.
После введения добавочных переменных систему уравнений и лин функцию записывают в виде, который называется расширенной системой: (Слайд 2)
а11*Х1
+ а12*Х2 + … + а1n*Xn
+ Xn+1
= В1
а21*Х1 + а22*Х2 + … + а2n*Xn + Xn +2 = В2 …………………………………………………………….
аm1*Х1 + аm2*Х2 + … + аmn*Xn + Xn +m = Вm
F – c1X1 – c2X2 - … - cnXn = 0
Предполагаем, что все добавочные переменные имеют тот же знак, что и свободные члены, в противном случае используется М-метод (рассмотрим дальше).
Исходную расширенную систему заносим в первую симплексную таблицу. Последняя строка таблицы, в которой уравнение целевой функции – оценочная. В левом столбце таблицы – основные переменные (базис), в первой строке – все переменные (отмечая при этом основные), во втором столбце – свободные члены. Последний столбец – для оценочных отношений. В рабочую часть таблицы (начиная с третьего столбца и второй строки) занесены коэффициенты Aij.
Проверим выполнения критерия оптимальности (при макс – наличие отриц коэффициентов в последней строке, т.к. они с «-»). Если их нет, то достигнут максимум (его значение – в левом нижнем углу таблицы), основные переменные – значение второго столбца, неосновные = 0, т.е. оптимальное БР.
Если критерий оптим не выполнен. То наибольший по модулю отрицательный коэффициент в последней строке определяет разрешающий столбец.
Составляем оценочные отношения каждой строки по правилам:
Bi/Aij, если Bi и Aij одного знака и Aij не = 0, Bi не = 0.
, если Bi и Aij разного знака и Aij не = 0, Bi не = 0.
0, если Bi = 0 и Aij > 0.
, если Bi = 0 и Aij < 0.
, если Aij = 0.
Определяем min по I для {Bi/Aij}. Если конечного минимума нет, то нет конечного оптимума. Если минимум конечен, то выбирается строка q, на которой он достигается (любая, если их несколько), называется разрешающей строкой. На пересечении разрешающий элемент Aqs.
Переходим к следующей таблице по правилам:
в левом столбце записываем новый базис: вместо основной переменной Xq – переменную Xs;
в столбцах, соответствующих основным переменным, проставляем: 1 – против «своей основной переменной, 0 – против «чужой основной переменной, 0 – в последней строке для всех основных переменных;
новую строку с номером q получаем из старой делением на разрешающий элемент Aqs;
все остальные новые элементы Aij вычисляем по правилу прямоугольника: (Слайд 3)
Далее перейти к п. III алгоритма.
Пример (решали как пример симплекс-метода):
-
F=2x1 + 3х2 max
при ограничениях:
х1 + 3х2 <= 18 2х1 + х2 <= 16
х2 <= 5
3x1 <= 21
х1, х2 >= 0
Расширенная система имеет вид:
х1 + 3х2 + х3 = 18
2х1 + х2 + х4 = 16
х2 + х5 = 5
3x1 + х6 = 21
х1, х2, х3, х4, х5, х6 >= 0
F - 2x1 - 3х2 = 0
Таблицы:
Базис |
Свободный член |
Переменные |
Оценочное отношение |
|||||
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
|||
Х3 |
18 |
1 |
3 |
1 |
0 |
0 |
0 |
18/3 |
Х4 |
16 |
2 |
1 |
0 |
1 |
0 |
0 |
16 |
Х5 |
5 |
0 |
1 |
0 |
0 |
1 |
0 |
5 |
Х6 |
21 |
3 |
0 |
0 |
0 |
0 |
1 |
¥ |
F |
0 |
-2 |
-3 |
0 |
0 |
0 |
0 |
|
Базис |
Свободный член |
Переменные |
Оценочное отношение |
|||||
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
|||
Х3 |
3 |
1 |
0 |
1 |
0 |
-3 |
0 |
3 |
Х4 |
11 |
2 |
0 |
0 |
1 |
-1 |
0 |
11/2 |
Х2 |
5 |
0 |
1 |
0 |
0 |
1 |
0 |
¥ |
Х6 |
21 |
3 |
0 |
0 |
0 |
0 |
1 |
7 |
F |
15 |
-2 |
0 |
0 |
0 |
3 |
0 |
|
Базис |
Свободный член |
Переменные |
Оценочное отношение |
|||||
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
|||
Х1 |
3 |
1 |
0 |
1 |
0 |
-3 |
0 |
¥ |
Х4 |
5 |
0 |
0 |
-2 |
1 |
5 |
0 |
5/5 |
Х2 |
5 |
0 |
1 |
0 |
0 |
1 |
0 |
5/1 |
Х6 |
12 |
0 |
0 |
-3 |
0 |
9 |
1 |
12/9 |
F |
21 |
0 |
0 |
2 |
0 |
-3 |
0 |
|
Базис |
Свободный член |
Переменные |
Оценочное отношение |
|||||
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
|||
Х1 |
6 |
1 |
0 |
-1/5 |
3/5 |
0 |
0 |
|
Х5 |
1 |
0 |
0 |
-2/5 |
1/5 |
1 |
0 |
|
Х2 |
4 |
0 |
1 |
2/5 |
-1/5 |
0 |
0 |
|
Х6 |
3 |
0 |
0 |
3/5 |
-9/5 |
0 |
1 |
|
F |
24 |
0 |
0 |
4/5 |
3/5 |
0 |
0 |
|