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

UptoLike

ВУЗ: 

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

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

Рубрика: 

95
=+++
=+++
=+++
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
...
...............................................
;...
;...
2211
22222121
11212111
(2.2.122)
и условиями неотрицательности переменных
,0,...,0,0
21
≥≥≥
n
xxx (2.2.123)
определяет выпуклую многогранную область или выпуклый многогранник.
Действительно, каждое i-е уравнение в системе (2.2.122) можно заменить равносильной
системой, состоящей из двух неравенств:
≤+++
≥+++
....
;...
2211
2211
ininii
ininii
bxaxaxa
bxaxaxa
Таким образом, система т уравнений (2.2.122) и система неравенств (2.2.123)
равносильны системе 2т + п линейных неравенств и, следовательно, определяют
выпуклую многогранную область или выпуклый многогранник.
Докажем следующую теорему.
Теорема (о соответствии вершин опорным решениям). Опорное решение X
системы уравнений
x
1
A
1
+ x
2
A
2
+ ... +х
п
А
п
= В (2.2.124)
является одной из вершин области, определяемой системой (2.2.124) и условиями
неотрицательности неизвестных х
j
≥0, j = 1, 2, . . ., п, и, наоборот, каждая вершина
указанной области есть некоторое опорное решение системы (2.2.124).
Д о к а з а т е л ь с т в о. Предполагаем, что ранг системы (2.2.124) равен числу
m уравнений системы. Пусть точка Х
0
=
[
]
0,...,0,0,,...,,
00
2
0
1 k
xxx некоторое опорное
решение, связанное с независимой группой векторов условий А
1
, A
2
, ..., A
k
. Тогда имеем
тождество
....
0
2
0
21
0
1
BAxAxAx
kk
=+++ (2.2.125)
Допустим противное, что точка Х
0
не является вершиной выпуклой области М,
определяемой системой (2.2.124) и условиями неотрицательности неизвестных.
Тогда существуют различные точки Х
1
=
[
]
''
2
'
1
,...,,
n
xxx и Х
2
=
[
]
''''
2
''
1
,...,,
n
xxx ,
принадлежащие области М, такие, что
,10,)1(
21
0
<<+−=
λλλ
XXX
или в координатах:
.10,,...,2,1,)1(
'''0
<<=+−=
λλλ
njxxx
jjj
При j>k,
0
j
x
= 0, но тогда и
0
'''
==
jj
xx
при j>k, поскольку
λ
>0 и 1-
λ
>0.
Условия принадлежности точек X
1
и Х
2
области М принимают теперь вид:
....
;...
''
2
''
21
''
1
'
2
'
21
'
1
BAxAxAx
BAxAxAx
kk
kk
=+++
=+++
Вычитая почленно из второго равенства первое, получим
.0)(...)()(
'''
2
'
2
''
21
'
1
''
1
=−++−+−
kkk
AxxAxxAxx
Здесь по крайней мере один коэффициент
'''
jj
xx −
отличен от нуля, так как точки Х
1
и Х
2
различны. Отсюда следует, что векторы A
1
, А
2
, . . .,A
k
линейно зависимы вопреки
условию. Полученное противоречие показывает, что опорное решение системы (2.2.124)
является вершиной области М.

Страницы