Составители:
Выразим первые т переменных х
1
, х
2
, ..., х
т
через остальные c помощью уравнений 9.29:
...., 2, 1, ,0
,...
..................................................................
,...
,...
12 ,11 ,
212 ,211 ,222
112 ,111 ,111
mip
xqxqxqpx
xqxqxqpx
xqxqxqpx
i
nmnmmmmmmmm
nnmmmm
nnmmmm
=≥
++++=
++++=
+
+
+
+
=
++++
++++
++++
(9.30)
Переменные x
1
, x
2
, ..., x
m
называются базисными, а вектор {x
1
, x
2
, ..., x
m
} — базисом; x
m+1
, x
m+2
, ..., x
n
—
свободные переменные.
Используя соотношения (9.30), можно выразить линейную целевую функцию через свободные переменные:
....
110 nnmm
xdxddf
+
+
+
=
++
(9.31)
Процесс оптимизации начнём с некоторого начального (опорного) решения, например при нулевых значениях
свободных переменных. Тогда получим
.0 ..., ,0 , ..., ,
111
=
=
=
=
+ nmmm
xxpxpx (9.32)
При этом целевая функция (9.31) принимает значение f
(0)
= d
0
.
Дальнейшее решение задачи симплекс-методом распадается на ряд этапов, заключающихся в том, что от
одного решения нужно перейти к другому с таким условием, чтобы целевая функция не возрастала. Это
достигается выбором нового базиса и значений свободных переменных.
Выясним, является ли опорное решение (9.32) оптимальным. Для этого проверим, можно ли уменьшить
соответствующее этому решению значение целевой функции f = d
0
при изменении каждой свободной
переменной. Поскольку x
i
> 0, то мы можем лишь увеличивать их значения. Если коэффициенты d
m+1
, ..., d
n
в
формуле (9.31) неотрицательны, то при увеличении любой свободной переменной х
т+1
, ..., х
п
целевая функция
не может уменьшиться. В этом случае решение 9.32 окажется оптимальным.
Пусть теперь среди коэффициентов формулы (9.31) хотя бы один отрицательный, например d
m+1
< 0. Это
означает, что при увеличении переменной x
m+1
целевая функция уменьшается по сравнению со значением d
0
,
соответствующим решению 9.32. Поэтому в качестве нового опорного выбирается решение при следующих
значениях свободных параметров:
.0 ..., ,0 ,
2
)1(
11
===
+++ nmmm
xxxx
(9.33)
При этом базисные переменные, вычисляемые по формулам ((9.30), равны
. ..., 2, 1, ,
)1(
11 ,
mixqpx
mmiii
=+=
++
(9.34)
Если все коэффициенты q
i,m+1
неотрицательны, то x
m+1
можно увеличивать неограниченно; в этом случае не
существует оптимального, решения задачи. Однако на практике такие случаи, как правило, не встречаются.
Обычно среди коэффициентов g
i, m+1
имеются отрицательные, а это влечет за собой угрозу сделать некоторые
переменные x
i
в 9.34 отрицательными из-за большого значения
.
)1(
1
+m
x
Следовательно, переменную x
m+1
можно
увеличивать лишь до тех пор, пока базисные переменные остаются неотрицательными. Это и является
условием выбора значения
.
)1(
1
+m
x
Его можно записать в виде
. ..., 2, 1, ,0
)1(
11 ,
mixqp
mmii
=≥+
++
(9.35)
Среди всех отрицательных коэффициентов q
i,m+1
найдем наибольший по модулю. Пусть его значение равно Q,
а соответствующее ему значение р
i
равно Р. Тогда из (9.35) получим максимально возможное значение пере-
меной
1+m
x на данном шаге оптимизации:
(
)
,0 ,0 /
)1(
1
<<−=
+
QPQPx
m
(9.36)
и новое опорное решение запишем в виде
.0 ..., ,0 ,
, ..., ,
21
1 ,1 ,111
==−=
−=−=
++
++
nmm
mmmmm
xx
Q
P
x
q
Q
P
pxq
Q
P
px
(9.37)
Полученное значение целевой функции f
(1)
меньше предыдущего, поскольку в данной формуле второй член
правой части больше нуля (d
m+l
< 0, Q < 0, Р > 0).
На этом заканчивается первый шаг оптимизации. Теперь нужно сделать второй шаг, используя аналогичную
процедуру. Для этого необходимо выбрать новый базис, принимая в качестве базисных переменных
параметры x
1
, ..., x
m-1
, х
т+1
. После второго шага мы либо найдем новые оптимальные значения переменных и
соответствующее им значение целевой функции f
(2)
< f
(1)
, либо покажем, что решение 9.36 является
оптимальным. В любом случае после конечного числа шагов мы придем к оптимальному решению. Еще раз
Страницы
- « первая
- ‹ предыдущая
- …
- 142
- 143
- 144
- 145
- 146
- …
- следующая ›
- последняя »
