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

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

90
Если 0)
~
( =ϕ u , то u
~
– решение альтернативной системы (2), (3).
Исходная система (1) не имеет решения.
Если 0)
~
( >ϕ u , то (как будет показано ниже) 0)
~
( >
δ
u , где
ubu
Τ
−=δ 1)( . (15)
Вектор
uA
u
x
~
)
~
(
1
~
Τ
δ
−
=
(16)
будет решением исходной системы (1).
Задачу (13) можно записать в виде
min)(
2
1
22
→δ+
∑
i
y , (17)
1,0 =δ+=+
Τ
Τ
ubyuA , (18)
где δ и компоненты вектора
m
Ry ∈ являются дополнительными
переменными. Решение этой задачи вместе с вектором u
~
составляют
)
~
(
~
,
~~
uuAy δ=δ−=
Τ
.
Заметим, что компоненты вектора u
~
вместе с величиной δ
~
являются
множителями Лагранжа ограничений задачи (17), (18). Из теоремы 3а
вытекает, что эта задача имеет то же решение, что и следующая система
линейных уравнений:
,1,0 =δ+=+
Τ
Τ
ubyuA (19)
0
=
δ
+
b
Ay
. (20)
Из теоремы 3а также следует, что система уравнений (19), (20) имеет
то же решение, что и следующая задача оптимизации:
min)(
2
1
22
→δ−δ+
∑
j
y , (21)
0
=
δ
−
−
b
Ay
. (22)
Вектор u
~
состоит из множителей Лагранжа ограничений данной задачи.
Для ее оптимального решения по теореме 3а
∑
δ=δ+
~
~
~
22
j
y .
Отсюда и из условия (22), в силу того что 0
≠
b , следует, что
0
~
1 ≥
δ
> .
Причем 0
~
=δ , если 0
~
=
j
y для всех n
j
...,,1
=
, т.е. если вектор u
~
является 
     Если ϕ(u~ ) = 0 , то u~ – решение альтернативной системы (2), (3).
Исходная система (1) не имеет решения.
     Если ϕ(u~ ) > 0 , то (как будет показано ниже) δ(u~ ) > 0 , где

                               δ(u ) = 1 − bΤu .                           (15)
Вектор
                                ~   −1
                                x = ~ AΤu~                                 (16)
                                   δ(u )
будет решением исходной системы (1).
      Задачу (13) можно записать в виде
                                1
                                  (∑ yi2 + δ2 ) → min ,                    (17)
                                2
                                AΤu + y = 0, bΤu + δ = 1 ,                 (18)
где δ и компоненты вектора y ∈ R m являются дополнительными
переменными. Решение этой задачи вместе с вектором u~ составляют
                           ~           ~
                           y = − AΤu~, δ = δ(u~ ) .
                                                           ~
     Заметим, что компоненты вектора u~ вместе с величиной δ являются
множителями Лагранжа ограничений задачи (17), (18). Из теоремы 3а
вытекает, что эта задача имеет то же решение, что и следующая система
линейных уравнений:
                                AΤu + y = 0, bΤu + δ = 1,                  (19)
                                Ay + δb = 0 .                              (20)
      Из теоремы 3а также следует, что система уравнений (19), (20) имеет
то же решение, что и следующая задача оптимизации:
                                1
                                  (∑ y 2j + δ2 ) − δ → min ,               (21)
                                2
                               − Ay − δb = 0 .                             (22)
Вектор u~ состоит из множителей Лагранжа ограничений данной задачи.
Для ее оптимального решения по теореме 3а
                                    ~ ~
                              ~
                               ∑
                              y 2 + δ2 = δ .
                                     j

Отсюда и из условия (22), в силу того что b ≠ 0 , следует, что
                                 ~
                              1> δ ≥ 0.
       ~
Причем δ = 0 , если ~
                    y j = 0 для всех j = 1, ..., n , т.е. если вектор u~ является


                                         90

Страницы