Линейные неравенства. Ермолаев Е.В. - 6 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

L
xA = 0 L ∩ P
xA 6 0
C xA 6 0
L = R
m
A = {y | y = xA, x ∈ R
m
} L ∩ N = (y
1
) + · · · + (y
k
) y
i
=
x
i
A, i = 1, ..., k C
1
= (x
1
) + · · · + (x
k
) C
2
xA = 0 C = C
1
+ C
2
exA 6 0 ey = exA ∈ L ∩ N
ey =
k
P
i=1
λ
i
y
i
=
k
P
i=1
λ
i
x
i
A, λ
i
> 0 (ex −
k
P
i=1
λ
i
x
i
)A = 0 ⇒ ex −
k
P
i=1
λ
i
x
i
A ∈ C
2
xA 6 0
C = (a
1
) + · · · + (a
k
) = {y ∈ R
m
|y = Ax, x > 0}
C
∗
= {x ∈ R
m
|xA 6 0}
C
∗
= {y ∈ R
m
|y = Bx, x > 0} C
∗
∗
= {x ∈ R
m
|xB 6 0} = C C
C
1
C
2
C
1
+ C
2
, C
1
∩ C
2
C
∗
C
1
⊆ C
2
⇒ C
∗
2
⊆ C
∗
1
(C
1
+ C
2
)
∗
= C
∗
1
∩ C
∗
2
(C
1
∩ C
2
)
∗
= C
∗
1
+ C
∗
2
C
∗∗
= C
C
1
+C
2
C
∗
C = P A
C
∗
AX 6 0
C
1
∩ C
2
C
1
C
2
C
∗
1
, C
∗
2
C
1
∩ C
2
= C
∗
1
∗
∩ C
∗
2
∗
= (C
∗
1
+ C
∗
2
)
∗
C
∗
1
+ C
∗
2
= (C
∗
1
+ C
∗
2
)
∗
∗
= (C
∗
1
∗
∩ C
∗
2
∗
)
∗
= (C
1
∩ C
2
)
∗
x C x 6= x
1
+ x
2
x
1
, x
2
∈ C
xA 6 0
    Äîê-âî. Âñÿêîå ïîäïðîñòðàíñòâî L åñòü ìíîæåñòâî ðåøåíèé íåêîòîðîé ñèñòåìû
xA = 0 , à ìíîæåñòâî íåîòðèöàòåëüíûõ ðåøåíèé ýòîé ñèñòåìû åñòü L ∩ P . 
 Òåîðåìà 2. Ìíîæåñòâî ðåøåíèé íåðàâåíñòâà xA 6 0  êîíå÷íûé êîíóñ.
    Äîêàçàòåëüñòâî. Ïóñòü C  ìíîæåñòâî ðåøåíèé ñèñòåìû xA 6 0 . Îïðåäåëèì

L = Rm A = {y | y = xA, x ∈ Rm } è L ∩ N = (y1 ) + · · · + (yk ) (ïî Ñ1.). Ïîëîæèì yi =
xi A, i = 1, ..., k è C1 = (x1 ) + · · · + (xk ) ; C2  ïîäïðîñòðàíñòâî ðåøåíèé óðàâíåíèÿ
xA = 0 . Òîãäà C = C1 + C2 . Äåéñòâìòåëüíî, ïóñòü x            eA 6 0 , òîãäà ye = x
                                                                                   eA ∈ L ∩ N
         k           k                                   k                       k
è ye =                 λi xi A, λi > 0 , îòñþäà (e                                 λi xi A ∈ C2 .
        P           P                                   P                       P
           λi y i =                                 x−     λi xi )A = 0 ⇒ x e−
       i=1        i=1                                 i=1                       i=1

 Ñëåäñòâèå 2. Âñÿêèé êîíå÷íûé êîíóñ åñòü ìíîæåñòâî âñåõ ðåøåíèé îäíîðîäíîãî
íåðàâåíñòâà âèäà xA 6 0 .
    Äîêàçàòåëüñòâî. Ïóñòü C = (a1 ) + · · · + (ak ) = {y ∈ R |y = Ax, x > 0} 
                                                                  m

êîíå÷íûé êîíóñ. Òîãäà C ∗ = {x ∈ Rm |xA 6 0}  ìíîæåñòâî ðåøåíèé îäíîðîäíîé
ñèñòåìû ëèíåéíûõ íåðàâåíñòâ.  ñèëó òåîðåìû 2 ïîñëåäíåå åñòü êîíå÷íûé êîíóñ,
ò.å. C ∗ = {y ∈ Rm |y = Bx, x > 0} . Ïîýòîìó C ∗ ∗ = {x ∈ Rm |xB 6 0} = C , ò.ê. C
êîíå÷íûé êîíóñ.        
 Òåîðåìà 3. (Òåîðåìà î çàìêíóòîñòè ìíîæåñòâà êîíå÷íûõ êîíóñîâ). Åñëè C1 è
C2  êîíå÷íûå êîíóñû, òî êîíå÷íûìè ÿâëÿþòñÿ òàêæå C1 + C2 , C1 ∩ C2 è C ∗ . Ïðè
ýòîì èìåþò ìåñòî
    i) C1 ⊆ C2 ⇒ C2∗ ⊆ C1∗ ,
    ii) (C1 + C2 )∗ = C1∗ ∩ C2∗ ,
    iii) (C1 ∩ C2 )∗ = C1∗ + C2∗ ,
    iv) C ∗∗ = C .
    Äîêàçàòåëüñòâîâî. Êîíå÷íîñòü C1 +C2 ñëåäóåò èç îïðåäåëåíèÿ êîíå÷íîñòè. Ñâîé-

ñòâà i), ii) ñïðàâåäëèâû äëÿ ëþáûõ êîíóñîâ, à iv) åñòü óòâåðæäåíèå òåîðåìû äâîéñò-
âåííîñòè. Êîíå÷íîñòü C ∗ ñëåäñòâèå òåîðåìû 2. Äåéñòâèòåëüíî, ïóñòü C = P A 
êîíå÷íûé êîíóñ; òîãäà C ∗ åñòü ìíîæåñòâî ðåøåíèé íåðàâåíñòâà AX 6 0 , êîòîðîå
ÿâëÿåòñÿ êîíå÷íûì êîíóñîì ïî òåîðåìå 2. Êîíå÷íîñòü C1 ∩ C2 ñëåäóåò èç òîëüêî
÷òî äîêàçàííîãî, ò.ê. åñëè C1 è C2  êîíå÷íûå êîíóñû, òî C1∗ , C2∗ êîíå÷íûå êî-
íóñû, è ïî (ii) C1 ∩ C2 = C1∗ ∗ ∩ C2∗ ∗ = (C1∗ + C2∗ )∗ òîæå êîíå÷íûé êîíóñ. Íàêîíåö,
C1∗ + C2∗ = (C1∗ + C2∗ )∗ ∗ = (C1∗ ∗ ∩ C2∗ ∗ )∗ = (C1 ∩ C2 )∗ . 
   5. Çàîñòðåííûå êîíóñû. Êðàéíèå âåêòîðû è ðåøåíèÿ.
 Êðàéíèé âåêòîð x âûïóêëîãî êîíóñà C : x 6= x1 + x2 äëÿ ëèíåéíî íåçàâèñèìûõ
x 1 , x2 ∈ C .
 Êðàéíåå ðåøåíèå ñèñòåìû xA 6 0 åñòü êðàéíèé âåêòîð êîíóñà ðåøåíèé.
 Ïðèìåðû êîíå÷íûõ êîíóñîâ áåç êðàéíèõ âåêòîðîâ (ïðîñòðàíñòâà è ïîëóïðîñòðàí-
ñòâà, çà èñêëþ÷åíèåì ïðÿìûõ è ïîëóïðÿìûõ).
 Êîíå÷íûé êîíóñ íàçûûâàåòñÿ çàîñòðåííûì, åñëè îí åñòü ñóììà ñâîèõ êðàéíèõ


                                               5

Страницы