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

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

28
() ().
I
yIx⊂
Это соотношение равносильно (14).
Задание 4. Доказать, что у любой совместной системы линейных
неравенств имеются решения с максимальным набором активных
ограничений.
Вектор
x
X∈ будем называть решением системы (1) с
минимальным набором активных ограничений
, если активные
ограничения у этой системы являются активными ограничениями для
любого другого решения из X , т.е. если для любого yX
∈
00
() ().
I
xIy⊆ (15)
Отметим, что решение с минимальным набором активных
ограничений является одновременно решением с
максимальным
набором неактивных ограничений
, т.е. таким, что при любом yX∈
() ().
I
yIx⊆
Это соотношение равносильно (15).
Задание 5. Доказать, что у совместной системы линейных
неравенств имеется решение с минимальным набором активных
ограничений и все такие решения имеют один и тот же набор активных
ограничений.
Задание 6. Доказать, что у системы линейных неравенств имеется
единственное решение с минимальным набором активных ограничений в
том и только том случае, если множество решений состоит из одного
вектора.
Пример 1. На рис. 2 представлено множество решений системы
линейных неравенств
12
12
1,
0, 0.
xx
xx
+
≥
≥≥
(16)
Множество решений данной системы является заштрихованной областью.
У этой системы неравенств имеются два решения с максимальным
набором активных ограничений – орты
12
10
,.
01
ee
⎡
⎤⎡⎤
==
⎢
⎥⎢⎥
⎣
⎦⎣⎦
Вся внутренность заштрихованной области состоит из решений данной
системы с минимальным набором активных ограничений. В данном
примере этот минимальный набор активных ограничений будет пустым
множеством – для всех решений внутри заштрихованной области все три
неравенства выполняются в форме строгих неравенств. 
                           I ( y ) ⊂ I ( x).
Это соотношение равносильно (14).
    Задание 4. Доказать, что у любой совместной системы линейных
неравенств имеются решения с максимальным набором активных
ограничений.
    Вектор x ∈ X будем называть решением системы (1) с
минимальным набором активных ограничений, если активные
ограничения у этой системы являются активными ограничениями для
любого другого решения из X , т.е. если для любого y ∈ X
                           I 0 ( x) ⊆ I 0 ( y ).               (15)
    Отметим, что решение с минимальным набором активных
ограничений является одновременно решением с максимальным
набором неактивных ограничений, т.е. таким, что при любом y ∈ X
                           I ( y ) ⊆ I ( x).
Это соотношение равносильно (15).
    Задание 5. Доказать, что у совместной системы линейных
неравенств имеется решение с минимальным набором активных
ограничений и все такие решения имеют один и тот же набор активных
ограничений.
    Задание 6. Доказать, что у системы линейных неравенств имеется
единственное решение с минимальным набором активных ограничений в
том и только том случае, если множество решений состоит из одного
вектора.
    Пример 1. На рис. 2 представлено множество решений системы
линейных неравенств
                            x1 + x2 ≥ 1,
                                                               (16)
                            x1 ≥ 0, x2 ≥ 0.
Множество решений данной системы является заштрихованной областью.

    У этой системы неравенств имеются два решения с максимальным
набором активных ограничений – орты
                                ⎡1 ⎤        ⎡0 ⎤
                           e1 = ⎢ ⎥ , e 2 = ⎢ ⎥ .
                                ⎣0⎦         ⎣1 ⎦
Вся внутренность заштрихованной области состоит из решений данной
системы с минимальным набором активных ограничений. В данном
примере этот минимальный набор активных ограничений будет пустым
множеством – для всех решений внутри заштрихованной области все три
неравенства выполняются в форме строгих неравенств.




                                28

Страницы