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

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

71
рассмотрения одну переменную и одно ограничение.
Критерий для идентификации решений систем однородных
линейных неравенств с минимальным набором активных
ограничений.
Рассмотрим две системы однородных линейных неравенств.
Одна из них относится к системе ограничений для вектора переменных
n
R
x
∈ :
0,0 ≥
=
x
Ax
. (18)
Другая система неравенств относится к системе ограничений на
вектор переменных
m
R
u ∈ :
0≥
Τ
u
A
. (19)
Теорема 3.7 приобретает вид критерия для идентификации решения
систем (18) и (19) с минимальным набором активных ограничений.
Теорема 3. Решение
x
системы линейных неравенств (18) является
решением данной системы с минимальным набором активных
ограничений, если у системы (19) существует решение
u, при котором
выполняется условие дополняющей нежесткости в строгой форме
njuAx
j
j
,...,1,0})(,max{ =>
Τ
. (20)
Решение
u системы (19) будет решением данной системы с
минимальным набором активных ограничений, если существует решение
x
системы (18), при котором выполняется условие дополняющей
нежесткости в строгой форме (20).
Критерии для идентификации решений с минимальным набором
активных ограничений в общем случае.
Применим теорему 3 к системе
линейных неравенств
0
1
=
−
+n
bxAx
,
0,0
1
≥≥
+n
xx .
Данная система имеет решение с
0
1
>
+n
x
в том и только том случае, если
разрешима система неравенств
0, ≥
=
x
b
Ax
. (21)
Из теоремы 3 получаем критерий
Теорема 4. Пусть система (21) непротиворечива. Решение
x
системы линейных неравенств (21) будет иметь минимальный набор
активных ограничений в том и только том случае, если существует
решение
u системы неравенств
0,0
=
≥
ΤΤ
ubuA , (22)
такое, что 
рассмотрения одну переменную и одно ограничение.
    Критерий для идентификации решений систем однородных
линейных неравенств с минимальным набором активных
ограничений. Рассмотрим две системы однородных линейных неравенств.
Одна из них относится к системе ограничений для вектора переменных
x ∈ Rn :
                           Ax = 0,      x ≥ 0.                            (18)
    Другая система неравенств относится к системе ограничений на
вектор переменных u ∈ R m :
                           AΤu ≥ 0 .                                      (19)
    Теорема 3.7 приобретает вид критерия для идентификации решения
систем (18) и (19) с минимальным набором активных ограничений.
    Теорема 3. Решение x системы линейных неравенств (18) является
решением данной системы с минимальным набором активных
ограничений, если у системы (19) существует решение u , при котором
выполняется условие дополняющей нежесткости в строгой форме
                           max{x j , ( AΤ u ) j } > 0,   j = 1,..., n .   (20)

    Решение u системы (19) будет решением данной системы с
минимальным набором активных ограничений, если существует решение
x системы (18), при котором выполняется условие дополняющей
нежесткости в строгой форме (20).
    Критерии для идентификации решений с минимальным набором
активных ограничений в общем случае. Применим теорему 3 к системе
линейных неравенств
                           Ax − bxn+1 = 0 ,
                           x ≥ 0,    xn+1 ≥ 0 .
Данная система имеет решение с xn+1 > 0 в том и только том случае, если
разрешима система неравенств
                           Ax = b, x ≥ 0 .                                (21)
    Из теоремы 3 получаем критерий
    Теорема 4. Пусть система (21) непротиворечива. Решение x
системы линейных неравенств (21) будет иметь минимальный набор
активных ограничений в том и только том случае, если существует
решение u системы неравенств
                           AΤ u ≥ 0, b Τ u = 0 ,                          (22)
такое, что


                                     71

Страницы