Системы линейных неравенств. Зоркальцев В.И - 78 стр.

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

78
0),( =uxf , (13)
и выполняются условия дополняющей нежесткости
0)( =ugx
j
j
, n
j
,...,1
=
. (14)
Существуют оптимальные решения
x
X
∈
, uU
∈
для которых
условия дополняющей нежесткости выполняются в строгой форме
(())0
jj
xgu
+
> , n
j
,...,1
=
. (15)
Доказательство. Из альтернатив (6), (7) и соотношений XX⊆ ,
UU⊆
следует утверждения для первых трех ситуаций.
Осталось доказать утверждения для четвертого из рассматриваемых
случаев, когда
∅≠X ,
∅
≠
U
. Тогда
∅
=
X
,
∅
=
U
, что следует из
альтернатив (6), (7). При
x
X∈ , uU
∈
, из (5), поскольку 0
x
≥ и () 0gu ≥
вытекает неравенство (12), согласно которому
TT
cx bu≥ .
Из (12) следует, что
X ≠∅
,
U
≠
∅
. Обозначим
min ,dcxxX
Τ
=
∈
оптимальное значение целевой функции задачи (1). Рассмотрим систему
линейных неравенств
b
Ax
=
, (16)
dxxc
n
=
+
+
Τ
1
, (17)
0≥
x
, 0
1
≥
+n
x , (18)
относительно вектора переменных
n
x
R
∈
и дополнительной переменной
1n
x
+
.
Из условия X ≠∅ и определения d следует, что система (16) – (18)
имеет решение. Для любого ее решения
n
x
R
∈
,
1n
x
+
, вектор
x
будет
оптимальным решением задачи (1),
x
X
∈
и при этом
1
0
n
x
+
=
.
Последнее по теореме 4.2 (Минковского-Фаркаша) означает
существование решения у следующей системы линейных неравенств
относительно вектора переменных
m
uR
∈
и дополнительной переменной
1m
u
+
:
1
0
m
Au cu
Τ
+
+
≤ , (19)
1
0
m
bu du
Τ
+
+
= , (20)
1
1
m
u
+
=
− . (21)
Для любого решения этой системы, составляющего вектор
1m
uR
+
∈ и 
                             f ( x, u ) = 0 ,                           (13)
и выполняются условия дополняющей нежесткости
                             x j g j (u ) = 0 , j = 1,..., n .          (14)

    Существуют оптимальные решения x ∈ X , u ∈U для которых
условия дополняющей нежесткости выполняются в строгой форме
                             ( x j + g j (u )) > 0 , j = 1,..., n .     (15)

    Доказательство. Из альтернатив (6), (7) и соотношений X ⊆ X ,
U ⊆ U следует утверждения для первых трех ситуаций.
    Осталось доказать утверждения для четвертого из рассматриваемых
                                           ~        ~
случаев, когда X ≠ ∅ , U ≠ ∅ . Тогда X = ∅ , U = ∅ , что следует из
альтернатив (6), (7). При x ∈ X , u ∈U , из (5), поскольку x ≥ 0 и g (u ) ≥ 0
вытекает неравенство (12), согласно которому cT x ≥ bT u .
    Из (12) следует, что X ≠ ∅ , U ≠ ∅ . Обозначим
                             d = min c Τ x, x ∈ X
оптимальное значение целевой функции задачи (1). Рассмотрим систему
линейных неравенств
                             Ax = b ,                                   (16)
                             c Τ x + xn +1 = d ,                        (17)
                             x ≥ 0 , xn+1 ≥ 0 ,                         (18)
относительно вектора переменных x ∈ R n и дополнительной переменной
xn+1 .
       Из условия X ≠ ∅ и определения d следует, что система (16) – (18)
имеет решение. Для любого ее решения x ∈ R n , xn+1 , вектор x будет
оптимальным решением задачи (1), x ∈ X и при этом xn+1 = 0 .
       Последнее по теореме 4.2 (Минковского-Фаркаша) означает
существование решения у следующей системы линейных неравенств
относительно вектора переменных u ∈ R m и дополнительной переменной
um+1 :
                             AΤu + cum+1 ≤ 0 ,                          (19)
                             b Τu + dum+1 = 0 ,                         (20)
                                      um+1 = −1 .                       (21)
    Для любого решения этой системы, составляющего вектор u ∈ R m+1 и


                                        78

Страницы