Составители:
Рубрика:
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−
= будет оптимальным, если .0≥r Последняя строка
таблицы соответствует значению функции:
(
)
.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
,
Страницы
- « первая
- ‹ предыдущая
- …
- 27
- 28
- 29
- 30
- 31
- …
- следующая ›
- последняя »
