Математическое программирование и моделирование экономических процессов. Коробов П.Н. - 83 стр.

UptoLike

ВУЗ: 

СПбГЛТУ | Санкт-Петербург

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

Рубрика: 

83
Умножая равенство (2.2.84) на число 1/Θ и вычитая его почленно из равенства
(2.2.85), получаем
(
)
(
)
(
)
./...//
'
22
'
211
'
1
BAxAxAx
sss
=Θ−++Θ−+Θ−
λλλ
(2.2.86)
Но, по определению числа Θ, коэффициент при векторе A
s
в равенстве (2.2.86)
равен нулю, а все остальные неотрицательны.
Таким образом мы получили неотрицательное решение уравнения (2.2.82):
,0,...,0,/
,...;/,/
''''
1
'
1
''
1
2
'
2
''
21
'
1
''
1
==Θ−=
Θ−=Θ−=
−−−
nssss
xxxx
xxxx
λ
λλ
в котором положительные координаты соответствуют s – 1 векторам условий A
1
,
A
2
,…,A
s-1
.
Таким же образом мы можем построить неотрицательное решение уравнения (2.2.82), в
котором положительные координаты будут соответствовать s-2 векторам условий A
1
,
A
2
,…,A
s-2
. Продолжая этот процесс, мы дойдем до неотрицательного решения уравнения
(2.2.82) Х
0
=[х
0
1
, х
0
2
, . . ., х
'
k
, 0, . . ., 0] в котором положительные координаты х
0
1
, х
0
2
, . . .,
0
k
x будут связаны с независимым набором векторов условий A
1
, A
2
,…,A
k
(k ≤ m).
Следовательно, допустимый вектор Х
0
будет определять некоторое опорное решение.
Докажем, что опорное решение Х
0
=[х
0
1
, х
0
2
, . . ., х
'
k
, 0, . . ., 0] является
оптимальным.
Так как независимый набор векторов A
1
, A
2
,…,A
k
является частью совокупности
векторов A
1
, A
2
,…,A
k
,…,A
s
, то для него выполнены условия (2.2.83), т. е.
.,...,,
0
2
0
21
0
1 kk
cYAcYAcYA === (2.2.87)
Напишем для опорного решения Х
0
значение целевой функции (2.2.81):
.0...0...
1
0
2
0
21
0
1
0
nkkk
cccxcxcxCX ⋅++⋅++++=
+
Используя равенства (2.2.87), получим
.)...(
00
2
0
21
0
1
0
YAxAxAxCX
kk
+++=
Но так как вектор Х
0
допустимое решение задачи, то
,...
0
2
0
21
0
1
BAxAxAx
kk
=+++
следовательно
CX
0
=BY
0
.
Таким образом, для допустимых решений Х
0
и Y
0
соответственно прямой и
двойственной задач их целевые функции совпадают по величине, но тогда, по критерию
оптимальности, опорное решение Х
0
является оптимальным решением, и теорема
доказана.
Значение теоремы об опорных решениях в линейном программировании очень
велико. Она показывает, что оптимальное решение канонической задачи линейного
программирования следует искать среди конечного числа допустимых решений, а именно
среди опорных решений. Поэтому в принципе возможен следующий путь решения

Страницы