Математическое программирование (линейное программирование). Киселева Э.В - 29 стр.

UptoLike

Рубрика: 

59 60
Тогда исходная таблица примет вид:
B
F
b
B
c
F
c
0
Первая строка таблицы соответствует уравнению:
bXFXB
FB
=
+ .
Напомним, что на первом шаге симплекс-метода необходимо
найти первоначальный опорный план (неотрицательное базисное
решение системы), для этого умножим обе части уравнения на
матрицу
1
B
слева (она существует, так как по предположению
B
невырожденная матрица). Получим
bBXFBXBB
FB
=+
111
.
Полагая 0
=
F
X , найдем значения базисных переменных:
bBX
B
=
1
( =
E
B
B
1
единичная матрица m-го порядка).
Если при этом 0
1
bB , то
(
)
T
bBX 0,
1
=
является первоначальным опорным планом.
Эти преобразования системы ограничений соответствуют
таблице:
E
F
B
1
bB
1
B
c
F
c
0
Вычислим значение целевой функции, соответствующее
опорному плану, подставив
X
в выражение
FFBB
XcXcZ += (вторая строка таблицы). Получим
()
bBcXZ
B
=
1
.
Рассматривая идею симплекс-метода, мы пришли к выводу,
что опорный план является оптимальным, если в целевой функ-
ции, выраженной
только через свободные переменные, все
коэффициенты неотрицательны.
Чтобы проверить полученный опорный план на оптималь-
ность, выразим целевую функцию через свободные переменные
F
X . Для этого умножим первую строку последней таблицы на
B
с и вычтем из второй строки, чтобы коэффициенты в строке
Z
при базисных неизвестных были равны 0. Получим таблицу:
E
F
B
1
bB
1
0
FBсс
BF
1
bBс
B
1
Обозначим через FBссr
BF
1
= вектор, состоящий из ко-
эффициентов при свободных неизвестных целевой функции. Со-
гласно рассуждениям, проведенным в п. 6.1, опорное решение
T
bBX )0,(
1
= будет оптимальным, если .0r Последняя строка
таблицы соответствует значению функции:
.bBсXFBссXZ
BFBFB
11
0
++=
В найденном опорном плане (при 0
=
F
X ) значение
)
bBсXZ
B
1
= .
Видим, что соответствующее значение находится в правом
нижнем углу таблицы
с противоположным знаком.
6.2.1. Алгоритм симплекс-метода
1. Запишем условия задачи:
=
=
n
j
jj
xcZ
1
min,
=++
=++
,bxaa
,bxaa
mnmnm
nn
K
KKKK
K
1
1111
njx
j
,1,0 =
в виде таблицы:
БП
х
1
... х
n
Свободный член
a
11
... a
1n
b
1
... ... ... ...
a
m1
... a
mn
b
m
Z c
1
... c
n
0
,