Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011
Χ = {X | X ≥ 0, B т X − Ln ≥ 0}, |
(2.42) |
||
т.е. многогранник Χ образуется из векторов X , для которых |
|
||
( fi , X ) ≥ 0 |
для |
i =1,..., m , |
(2.43) |
(b j , X ) ≥1 |
для |
j =1,..., n . |
(2.44) |
Конец вектора X лежит на границе множества Χ , если хотя бы |
|||
одно из этих соотношений является равенством. |
|
||
Аналогично можно рассмотреть множество |
|
||
Υ = {Y | Y ≥ 0, AY − Lm ≥ 0}. |
(2.45) |
||
Граница множества Υ состоит из точек, |
удовлетворяющих хотя |
||||
бы одному из m + n уравнений |
|
|
|
|
|
(ai ,Y ) =1 |
для |
i =1,..., m , |
(2.46) |
||
(e j ,Y ) = 0 |
для |
j =1,..., n , |
(2.47) |
||
а для внутренних точек выполняются неравенства |
|||||
(ai ,Y ) >1 |
для |
i =1,..., m , |
(2.48) |
||
(e j ,Y ) > 0 |
для |
j =1,..., n . |
(2.49) |
||
Легко убедиться, что Χ и |
Υ – это многогранники, у которых |
||||
имеются соответственно m и n бесконечных ребер. |
|||||
|
* |
* |
* |
|
|
Пример 2.1. Рассмотрим игру с матрицами выигрышей |
|||||
1.75 |
1.5 |
|
1.5 |
1.8 |
|
|
|
|
|
|
|
A1 = |
1.8 |
, |
B1 = |
|
. |
1.66 |
|
1.67 |
1 |
||
Выберем d = 2 , получим матрицы |
|
|
|||
0.25 |
0.5 |
|
0.5 |
0.2 |
|
|
|
|
|
|
|
A = |
0.2 |
, |
B = |
|
. |
0.34 |
|
0.33 |
|
1 |
|
Множество Υ , показанное на рис. 2.2, определяется следующими соотношениями:
0.25y1 + 0.5y2 −1 ≥ 0,
0.34 y1 + 0.2 y2 −1 ≥ 0,
y1 ≥ 0, y2 ≥ 0,
111
а множество Χ , показанное на рис. 2.3, – соотношениями: |
|
|||||
0.5x1 + 0.33x2 −1 ≥ 0, |
|
|
||||
|
|
|
|
−1 ≥ 0, |
|
|
0.2x1 + y2 |
|
|
||||
x |
≥ 0, x |
2 |
≥ 0. |
|
|
|
|
1 |
|
|
|
|
|
Y2 |
|
|
|
|
|
|
6 |
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
Yвн |
|
Yгр |
|
|
|
|
|
|
2 |
|
|
|
|
|
|
0 |
2 |
|
|
4 |
6 |
Y1 |
Рис. 2.2. Множество Υ : Yвн – внутренняя точка; Yгр – точка на границе
Заметим, что здесь и в дальнейшем используется важное предположение, сделанное при постановке задачи:
A > 0 и B > 0 .
Именно это условие гарантирует существование выпуклых открытых многогранников Χ и Υ .
112
Рис. 2.3. Множество Χ : |
X 0 , X 1 , X 2 |
– крайние точки; l, r |
– открытые ребра |
* * *
Пусть для любого X через p(X ) обозначено множество тех из векторов fi или b j , для которых
( fi , X ) = 0 или (b j , X ) =1. |
(2.50) |
Множество p(X ) может быть единственным образом записано в виде матрицы
p(X ) = ( p1 , p2 ,..., pr ) , |
(2.51) |
где pl (l =1,..., r) – это соответствующий определению вектор fi или b j .
113
Предположим, что матрица B удовлетворяет условию невырожденности: пусть столбцы матрицы C являются столбцами из матрицы (I, B) , где I – единичная матрица, тогда если C = p(X )
для некоторого X Χ, то ранг матрицы C равен числу ее столбцов. Рассмотрим следствия, вытекающие из предположения о невы-
рожденности.
Следствие 1. Если для некоторого X Χ множество p(X ) со-
держит |
m векторов, то X полностью определяется своими векто- |
|||||||
рами fi |
и b j . В этом случае |
X |
называется крайней точкой мно- |
|||||
жества Χ . |
|
|
|
|
|
|
|
|
Следствие 2. Пусть для X 0 Χ матрица p(X 0 ) |
имеет ранг r , |
|||||||
матрица |
p(X 0 ) есть матрица размером |
(m ×r) ( r |
может быть и |
|||||
равным нулю): |
|
|
|
|
|
|
|
|
|
p(X 0 ) = |
( p |
, p |
2 |
,..., p |
r |
) . |
(2.52) |
|
|
1 |
|
|
|
|
||
Ввиду того, что p1, p2 ,..., pr – линейно независимые векторы, можно присоединить к ним векторы pr+1, pr+2 ,..., pm так, чтобы матрица
D = ( p1 , p2 ,..., pm ) |
|
|
|
|
(2.53) |
||
была невырожденной. |
|
|
|
|
|
|
|
Существует обратная матрица |
|
|
|
|
|
|
|
(D−1 )т = ( p1, p2 ,..., pm ) . |
|
|
|
(2.54) |
|||
Это означает, что |
|
|
|
|
|
|
|
( pi , p j ) = δij = |
1 |
при |
i = j, |
|
|
|
(2.55) |
|
при |
i ≠ j. |
|
|
|
||
|
0 |
|
|
|
|
||
Теорема 2.3. Пусть X 0 Χ и p(X 0 ) = ( p , p |
2 |
,..., p |
r |
) . Сущест- |
|||
вует такая постоянная K , что при |
|
1 |
|
|
|||
|
|
|
|
|
|
||
m |
|
|
|
|
|
|
|
∑λ2i |
≤ K , |
|
|
|
|
(2.56) |
|
i=1
где λi ≥ 0 для 1 ≤ i ≤ r , точка X , определяемая соотношением
114
|
|
m |
|
X = X 0 |
+ ∑λi pi , |
(2.57) |
|
|
|
i=1 |
|
принадлежит множеству Χ . |
|
|
|
Доказательство. Пусть |
p – любой столбец матрицы (I, B). То- |
||
гда |
|
|
|
|
|
m |
|
( p, X ) = ( p, X 0 ) + ∑λi ( p, pi ) . |
(2.58) |
||
|
|
i=1 |
|
Рассмотрим два случая. |
|
|
|
1. Если p p(X 0 ) , т.е. |
p = pi , 1 ≤ i ≤ r . |
|
|
На основании следствия 2 имеем ( p, X ) = ( p, X 0 ) + λi . При этом
1, |
если p |
− столбец из B, |
(2.59) |
( p, X 0 ) = |
если p |
− столбец из I. |
|
0, |
|
По условию теоремы λi ≥ 0 , 1 ≤ i ≤ r , следовательно, ( p, X ) ≥
≥( p, X 0 ) и X является подмножеством Χ .
2.Если p p(X 0 ) , т.е. p – любой другой столбец из (I, B). В этом случае
1, |
если p |
− столбец из B, |
(2.60) |
( p, X 0 ) > |
если p |
− столбец из I. |
|
0, |
|
Пусть p – столбец из B , тогда ( p, X 0 ) =1 + α , где α > 0 . Выбрав λi , 1 ≤ i ≤ m , достаточно малыми, такими, чтобы
|
m |
|
|
|
∑λi ( p, pi ) |
≤ α, |
(2.61) |
|
i=1 |
|
|
получим ( p, X ) ≥1. |
|
||
По аналогии можно рассмотреть столбец матрицы I . Таким образом, при соответствующем выборе λi , 1 ≤ i ≤ m , из соотношения
( p, X 0 ) ≥ 0 следует, что ( p, X ) ≥ 0 , а из соотношения ( p, X 0 ) ≥1 следует, что ( p, X ) ≥1. Следовательно, X Χ.
Теорема доказана.
115