ВУЗ:
Составители:
Рубрика:
141
.m...,,2,1i,0p
,xq...xqxqpх
,
,xq...xqxqpх
,xq...xqxqpх
i
nmn2m2m,21m1m,mmm
nn22m2m,21m1m,222
nn12m2m,11m1m,111
=≥
⋅++⋅+⋅+=
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
⋅++⋅+⋅+=
⋅
+
+
⋅
+
⋅
+
=
++++
++++
++++
(110)
Переменные х
1
, х
2
, …, х
m
называются
базисными
, а
вектор
{х
1
, х
2
, …, х
m
} –
базисным
; х
m+1
, х
m+2
, … , х
n
–
свободные переменные
.
Используя соотношения (110), можно выразить линейную целевую функ-
цию f (108) через свободные перемещенные:
f = d
0
+ d
m+1
⋅
x
m+1
+ … + d
n
х
n
. (111)
Процесс оптимизации начнем с некоторого начального (опорного) реше-
ния, например, при нулевых значениях свободных переменных. Тогда получим
х
1
= р
1
, …, х
m
= p
m
, x
m+1
= 0, …, x
n
= 0. (112)
При этом целевая функция (111) примет значение f
(0)
= d
0
.
Дальнейшее решение задачи симплекс-методом распадается на ряд этапов,
заключающихся в том, что от одного решения нужно перейти к другому с та-
ким условием, чтобы целевая функция не возрастала. Это достигается выбором
нового базиса и значений свободных переменных.
Выясним, является ли опорное решение (112) оптимальным. Для этого
проверим, можно ли уменьшить соответствующее этому решению значение це-
левой функции f = d
0
, при изменение каждой свободной переменной.
Так как x
i
≥ 0, то можно лишь увеличивать их значения.
Если коэффициенты d
m+1
, …, d
n
в формуле (111) неотрицательны, то при
увеличении любой свободной переменной х
m+1
, …, х
n
целевая функция не мо-
жет уменьшиться. В этом случае
решение
(112) окажется
оптимальным
.
Пусть теперь среди коэффициентов формулы (111) хотя бы один отрица-
тельный, например d
m+1
< 0. Это означает, что при увеличении переменной х
m+1
целевая функция уменьшается по сравнению со значением d
0
, соответствую-
щим решению (112). Поэтому в качестве нового опорного выбирается решение
при следующих значениях свободных параметров:
х
m+1
= х
)1(
1m
+
, х
m+2
= 0, …, х
n
= 0. (113)
При этом базисные перемещенные, вычисляемые по (110), равны
x
i
= p
i
+ q
i, m+1
⋅
x
)1(
1m
+
, i = 1, 2, …, m. (114)
Если все коэффициенты q
i, m+1
неотрицательны
, то х
m+1
можно увеличи-
вать неограниченно; в этом случае не существует оптимального решения зада-
чи. Но такие случаи на практике не встречаются.
Обычно среди коэффициентов q
i, m+1
имеются отрицательные
, что вле-
чет за собой угрозу сделать некоторые базисные перемещенные х
i
в (114) отри-
