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

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

68
4.3 Критерий для идентификации решений систем линейных
неравенств с минимальным набором активных ограничений
Решения системы линейных неравенств с минимальным набором
активных ограничений.
Все ограничения системы линейных неравенств
для данного ее решения можно разбить на два класса. Некоторые из
ограничений выполняются в виде равенств. Эти ограничения называются
активными для данного решения. В частности, активными будут все
ограничения, априори заданные в форме условия-равенства.
Другие
ограничения будут выполняться в виде строгих неравенств. Их будем
называть неактивными ограничениями для данного решения.
Рассматриваемые здесь свойства систем линейных неравенств являются
обобщением свойств рассмотренных в разделе 2.1 системы вида (2.1).
Обозначим C – множество номеров ограничений некоторой системы,
т.е. это множество отдельных линейных уравнений и неравенств. Пусть
решения данной системы образуют некоторую область X из
n
R
. Для
вектора
x
X∈ обозначим ()
M
x , ( )Nx подмножества номеров активных и
неактивных ограничений:
() ()
M
xNxC
=
U
,
() ()Mx Nx
=
∅I
.
Например, для системы
12
12
1
1(1)
0(2)
1/2 (3)
xx
xx
x
+
≤
−≤
≥
при
*
(1/2,1/2)x = подмножество активных ограничений состоит из 1-го,
2-го и 3-го ограничений, т.е.
*
(){1,2,3}М x = , т.к. при подстановке
решения
*
(1/2,1/2)x = все ограничения системы обращаются в точные
равенства. Подмножество неактивных ограничений для решения
*
(1/2,1/2)x = является пустым, т.е.
*
()0Nx
=
/ .
В силу выпуклости
X
для любых
1
и
2
x
из
X
вектор
12
1
()
2
x
xx=+
также будет находиться в X . При этом
12
() ( ) ( )
M
xMx Mx= I ,
12
() ( ) ( )Nx Nx Nx= U ,
т.е. активными для вектора
x
будут только те ограничения, которые были
активными и для решения
1
, и решения
2
x
. Неактивными для
x
будут 
     4.3 Критерий для идентификации решений систем линейных
     неравенств с минимальным набором активных ограничений
     Решения системы линейных неравенств с минимальным набором
активных ограничений. Все ограничения системы линейных неравенств
для данного ее решения можно разбить на два класса. Некоторые из
ограничений выполняются в виде равенств. Эти ограничения называются
активными для данного решения. В частности, активными будут все
ограничения, априори заданные в форме условия-равенства. Другие
ограничения будут выполняться в виде строгих неравенств. Их будем
называть неактивными ограничениями для данного решения.
Рассматриваемые здесь свойства систем линейных неравенств являются
обобщением свойств рассмотренных в разделе 2.1 системы вида (2.1).
     Обозначим C – множество номеров ограничений некоторой системы,
т.е. это множество отдельных линейных уравнений и неравенств. Пусть
решения данной системы образуют некоторую область X из R n . Для
вектора x ∈ X обозначим M ( x) , N ( x) подмножества номеров активных и
неактивных ограничений:
                          M ( x) U N ( x) = C ,      M ( x) I N ( x) = ∅ .
Например, для системы
                               x1 + x2 ≤ 1 (1)
                               x1 − x2 ≤ 0 (2)
                                x1 ≥ 1/ 2 (3)
при x* = (1/ 2, 1/ 2) подмножество активных ограничений состоит из 1-го,
2-го и 3-го ограничений, т.е.           М ( x* ) = {1,2,3} , т.к. при подстановке
решения x* = (1/ 2, 1/ 2) все ограничения системы обращаются в точные
равенства. Подмножество неактивных ограничений для решения
x* = (1/ 2, 1/ 2) является пустым, т.е. N ( x* ) = 0/ .
     В силу выпуклости X для любых x1 и x 2 из X вектор
                               1
                           x = ( x1 + x 2 )
                               2
также будет находиться в X . При этом
                               M ( x) = M ( x1 ) I M ( x 2 ) ,
                               N ( x) = N ( x1 ) U N ( x 2 ) ,
т.е. активными для вектора x будут только те ограничения, которые были
активными и для решения x1 , и решения x 2 . Неактивными для x будут



                                          68

Страницы