Основы теории систем и системного анализа. Матвеев Ю.Н. - 76 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

76
уравнениями. Известно, что оптимальное решение ОЗЛП, если оно
существует, достигается в одной из вершин ОДР (опорной точке), где не
менее k = n-m переменных задачи равны нулю [10].
Выберем в ОЗЛП какие-то k переменных в качестве свободных и
выразим m базисных переменных через свободные.
Пусть свободные переменные имеют вид x
1
, x
2
, …, x
k
, тогда
базисные переменные запишем так:
⎪
⎪
⎩
⎪
⎪
⎨
⎧
++++=
++++=
+
+
+
+
=
+++++
+++
+
+
.
,22,11,
2,222,211,22
,
1,122,11
1,1
1
....
,....
....
nkknnnn
kkkkkkk
kkkkk
k
k
βxaxaxax
βxaxaxax
βxaxaxax
(2.32)
Положим,
0,.....,0,0
21
=
==
k
xxx . Получим
nnkkkk
xxx
β
β
β
=
=
=
++++
,.....,
2211
.
Это решение ОЗЛП. Оно допустимо, если все свободные члены
неотрицательные, т.е.
0,.....,0,0
21
≥≥≥
++ nkk
β
β
β
.
Предположим, что это так. Тогда полученное решение опорное.
Выясним, оптимально ли полученное решение?
Выразим линейную функцию W через свободные переменные x
1
, x
2
,
…, x
k
:
kk
xxxW
γ
γ
γ
γ
+
+
+
+= ...
22110
→
min. (2.33)
Для полученного опорного решения x
1
= 0, x
2
= 0, …, x
k
= 0;
0
γ
=W .
Посмотрим, нельзя ли улучшить (оптимизировать) решение, т.е.
уменьшить функцию W, увеличивая в положительную сторону какие-то
переменные x
1
, x
2
, …, x
k
. (Уменьшить их нельзя, т.к. они станут
отрицательными, что недопустимо по условиям ЛП).
Если все
kjγ
j
,1, =
в (2.33) неотрицательны (≥0), то при увеличении
каких-либо переменных x
1
, x
2
, …, x
k
в положительную сторону невозможно
уменьшить W (значение W будет возрастать). Следовательно, найденное
опорное решение
,,0,0,0
1121 ++
=
===
kkk
xxxx
β
nnkk
xx
β
β
=
=
++
,...,
22
является оптимальным и .
0
0
min
γ
=W
Вывод
Если в (2.33) все
kjγ
j
,1, = неотрицательны, то полученное ранее
опорное решение ОЗЛП является оптимальным. Наоборот, если среди
kjγ
j
,1, = есть отрицательные, то увеличение при них каких-то
переменных из x
1
, x
2
, …, x
k
приведет к уменьшению W, т.е. улучшит
решение. Например, пусть в (2.33)
0
1
≤
γ
. Значит, если увеличивать x
1
, т.е.
переходить от полученного опорного решения к другому, где 0
1
≠x , а

Страницы