3.2.2. Табличный симплекс-метод
Процесс решения ЗЛП можно представить в виде последовательности заполняемых таблиц. Покажем это на примере.
Пример 3.5. Рассмотрим предыдущий пример 3.4. После выделения базиса заполняется таблица (табл. 3.1), где r – число базисных переменных, х1,…, хr – базисные переменные.
Таблица 3.1
Исходная таблица для симплекс-метод.
|
Базисные переменные |
Свободные члены |
x1 |
x2 |
|
xi |
|
xr |
xr+1 |
|
xj |
|
xn |
|
x1 |
b1 |
1 |
0 |
|
0 |
|
0 |
a1 r+1 |
|
a1 j |
|
a1n |
|
x2 |
b2 |
0 |
1 |
|
0 |
|
0 |
a2 r+1 |
|
a2 j
|
|
a2n
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xi |
bi |
0 |
0 |
|
1 |
|
0 |
ai, r+1 |
|
ai j
|
|
ai n
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xr |
bn |
0 |
0 |
0 |
0 |
0 |
1 |
ar, r+1 |
|
ar j
|
|
ar n
|
|
|
c0 |
0 |
0 |
– |
0 |
– |
0 |
c r+1 |
|
cj
|
|
cn
|
r – число базисных переменных
при минимизации по системе вида
и целевой функции вида (перенос через знак равенства свободных переменных):
+ с
r+1
x
r+1
+…+ c
j
x
j
+…+ c
n
x
n
= c0.
Для нашего случая имеем:
Исходная таблица имеет вид (табл. 3.2).
Таблица 3.2
Исходная таблица для симплекс-метода
|
Базисные переменные |
Свободные члены |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x |
1 |
1 |
0 |
0 |
1 |
-2 |
|
x2 |
2 |
0 |
1 |
0 |
-2 |
1 |
|
x3 |
3 |
0 |
0 |
1 |
3 |
1 |
|
|
0 |
0 |
0 |
0 |
-1 |
1 |
1
-
Выбирают разрешающий p-й столбец из условия: оценка с р >0 и хотя бы один элемент в этом столбце a i p >0 (в нашем случае р = 5).
-
Выбирают q-ю разрешающую строку из условия
для aip
> 0 (в нашем
случае: элемент a15
= -2 < 0 и
поэтому отношение
не рассматривается)
;
откуда q
= 2. -
Производят перерасчёт элементов q-й (2-й) разрешающей строки по формуле:
a'qk = a qk / a qp , k = 0, 1, …, n.
a’2k = a 2k / a 25, k = 0, 1, …, 5,
т.е. все элементы разрешающей строки делят на элемент а 25, находящийся на пересечении разрешающего столбца и разрешающей строки и полученные результаты размещают в новой таблице (табл. 3.3).
-
Вычисляют элементы всех остальных строк (при k
p)
по формуле
a'ik = a ik – a’qk a ip, i = 0, 1, …, r.
Иначе говоря, к каждой из остальных строк прибавляют вновь полученную разрешающую строку, умноженную на такое число, чтобы в клетках столбца для х5 появились нули, и записывают преобразованные строки на месте прежних в новой таблице (табл. 3.3). Базис в новой таблице изменится с х1, х2, х3 на х1, х5, х3. Далее все рассуждения повторяются.
Таблица 3.3
Таблица с новым базисом х1, х2, х3
|
Базисные переменные |
Свободные члены |
x1 |
x2 |
x3 |
x4 |
x5 |
||||||
|
x1 |
5 |
1 |
2 |
0 |
-3 |
0 |
||||||
|
x |
2 |
0 |
1 |
0 |
-2 |
1 |
||||||
|
x3 |
1 |
1/5 |
0 |
0 |
-1 |
-1/5 |
1 |
1/5 |
5 |
1 |
0 |
0 |
|
|
-2 |
0 |
-1 |
0 |
1 |
0 |
||||||
5
Для таблицы 3.3 разрешающий столбец с переменной х4, т. к. с4 = 1>0,
а34 = 5>0. В качестве разрешающей строки выбирается строка с базисной переменной х3, т. к. а34 = 5>0. Все элементы базисной строки нормируются делением на 5. С помощью вновь полученной базисной строки в разрешающем столбце с х4 формируются нули (см. табл. 3.4).
Таблица 3.4