ВУЗ:
Составители:
120
⎪
⎪
⎩
⎪
⎪
⎨
⎧
−=+++−
=+++
=+++
++
++
++
Zxcxcz
bxaxax
bxaxax
nnmm
mnmnmmmm
nnmm
...
...
.........
...
11
11
111111
. (7.8)
Базисное решение этой канонической формы имеет вид
z=Z; x
1
=b
1
; x
2
=b
2
; x
m
=b
m
;
x
m+1
=x
m+2
=…=x
n
=0.
Если b
i
≥0, то базисное решение – допустимо.
Коэффициенты с
j
(j=m+1,...,n) позволяют судить о том, найден ли мини-
мум целевой функции, или надо продолжать оптимизацию. Если для некото-
рого допустимого базового решения с
j
≥0, то это решение х
j
есть решение за-
дачи линейного программирования. Величины с
j
называются относительны-
ми оценками.
Если же некоторый коэффициент с
j
<0, то значение z можно уменьшить
путем увеличения x
s
соответствующей переменной x
j
.
Если система (2) невырождена и один коэффициент с
j
<0, то всегда
можно найти допустимое базовое решение с меньшим значением целевой
функции. Если более одного коэффициента с
j
<0, то выбирается та перемен-
ная x
s
, которая имеет наибольший по модулю отрицательный коэффициент.
Относительная оценка в этом случае имеет вид c
s
=min c
j
<0 и служит для вы-
бора новой базисной переменной.
Выбрав переменную x
s
, увеличивают ее до тех пор, пока все остальные
внебазисные переменные не будут равны нулю. В этих условиях систему
(7.8) можно переписать в виде:
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎨
⎧
<+=
−=
−=
−=
0;
.......
222
111
sss
smsmm
ss
ss
cxcZz
xabx
xabx
xabx
. (7.9)
С увеличением x
s
уменьшается z. Ограничением на это уменьшение
служит неотрицательность базовых переменных. Если a
is
≤0 (i=1..m), то x
s
можно увеличивать неограниченно. Признаком неограниченности целевой
функции на допустимом множестве решений является следующее утвержде-
ние: если для некоторого базисного решения существует хотя бы одна внеба-
зисная переменная x
s
, для которой с
s
<0 и a
is
≤0, то целевая функция задачи ЛП
не ограничена снизу на допустимом множестве.
Из (3) следует, что если x
i
=0 и a
is
>0, то
is
j
s
a
b
x =
.
Страницы
- « первая
- ‹ предыдущая
- …
- 118
- 119
- 120
- 121
- 122
- …
- следующая ›
- последняя »
