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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

x
1
(x
1
, 0)
y
1
A
1
y
1
6 0 by
1
> 0 a
m
y
1
6 0 y
1
a
m
y
1
> 0
m−1
P
i=1
ξ
i
a
i
= b
a
i
= −(a
m
y
1
)a
i
+ (a
i
y
1
)a
m
, i = 1, ..., m − 1
b = −(a
m
y
1
)b + (by
1
)a
m
a
i
b
m−1
X
i=1
ξ
i
a
i
−
1
a
m
y
1
"
m−1
X
i=1
ξ
i
(a
i
y
i
) − by
1
#
a
m
= b,
x
i
= ξ
i
, i = 1, ..., m − 1, x
m
=
P
m−1
i=1
ξ
i
(a
i
y
i
) −
by
1
y
a
i
y > 0, i = 1, ..., m − 1 by < 0 y = (a
m
y)y
i
−
(a
m
y
1
)y a
i
y = a
i
y > 0 i = 1, ..., m − 1 by = by < 0 a
m
y = 0
y
C = (a
1
) + · · · + (a
n
)
C = {y ∈ R
m
| y = Ax, x > 0} = AP
u
1
, ..., u
k
L L = (u
1
)+· · ·+
(u
k
) + (−u
1
) + · · · + (−u
k
) L = (u
0
) + (u
1
) + · · · + (u
k
) u
0
= −u
1
− · · · − u
k
x = ξ
1
u
1
+ · · · + ξ
k
u
k
x = η
0
u
0
+ η
1
u
1
+ · · · + η
k
u
k
ξ
i
= η
i
− η
0
η
i
= η
0
+ ξ
i
> 0 η
0
> 0
C C
∗
∗
= C
C
∗
∗
⊇ C C = P A b /∈ C
xA = b, x > 0 Ay 6 0, by > 0
b /∈ C
∗
∗
C = {x ∈ R
m
| xA 6 0} C
∗
= AP = {y ∈ R
m
| y = Ax, x > 0}
K = {y ∈ R
m
| y = Ax, x > 0} K
∗
= C ⇒
K
∗
∗
= K = C
∗
xA = b (b 6= 0) a
i
1
, ..., a
i
k
ξ
1
a
1
+ · · · + ξ
m
a
m
= b (ξ
o
1
, ..., ξ
o
m
)
a
i
1
, ..., a
i
k
ξ
o
j
= 0 j /∈ {i
1
, ..., i
k
}
íåîòðèöàòåëü- íîå ðåøåíèå x1 , òî (x1 , 0) áóäåò íåîòðèöàòåëüíûì ðåøåíèåì ñèñòåìû
(1). Ïîýòîìó (3) íåîòðèöàòåëüíîãî ðåøåíèÿ íå èìååò è ïî ïðåäïîëîæåíèþ èíäóêöèè
ñóùåñòâóåò y1 òàêîé, ÷òî A1 y1 6 0 , à by1 > 0 . Åñëè ïðè ýòîì am y1 6 0 , òî y1 
èñêîìîå ðåøåíèå (2). Ïîýòîìó áóäåì ñ÷èòàòü, ÷òî am y1 > 0 .
                                     m−1
    Âòîðàÿ âñïîìîãàòåëüíàÿ ñèñòåìà         ξ i ai = b (4), ãäå
                                      P
                                            i=1
    ai = −(am y1 )ai + (ai y1 )am , i = 1, ..., m − 1 ,
    b = −(am y1 )b + (by1 )am .
Ñèñòåìà (4) òîæå íå èìååò íåîòðèöàòåëüíîãî ðåøåíèÿ. Äåéñòâèòåëüíî, çàìåíÿÿ â (4)
ai è b ïî èõ îïðåäåëåíèþ, ïîëó÷èì
                        m−1
                                            "m−1                  #
                        X              1      X
                             ξ i ai −             ξ (ai yi ) − by1 am = b,
                        i=1
                                      am y1 i=1 i

ò.å. (1) èìååò íåîòðèöàòåëüíîå ðåøåíèå xi = ξ i , i = 1, ..., m − 1, xm = m−1
                                                                             P
                                                                               i=1 ξ i (ai yi ) −
by1 . Ïðèìåíÿÿ èíäóêöèîííîå ïðåäïîëîæåíèå ê óðàâíåíèþ (4), ïîëó÷èì âåêòîð y ,
äëÿ êîòîðîãî ai y > 0, i = 1, ..., m − 1 è by < 0 . Òåïåðü ïîëîæèì y = (am y)yi −
(am y1 )y . Òîãäà ai y = ai y > 0 äëÿ i = 1, ..., m − 1 , by = by < 0 è am y = 0 (íåïîñðåä-
ñòâåííàÿ ïðîâåðêà), ò.å. y  ðåøåíèå ñèñòåìû (2).            
   3. Êîíå÷íûå êîíóñû.
 Êîíå÷íûé êîíóñ  íåîòðèöàòåëüíàÿ ëèíåéíàÿ îáîëî÷êà êîíå÷íîãî ìíîæåñòâà (ïî-
ðîæäåí êîíå÷íûì ÷èñëîì) âåêòîðîâ, ò.å. C = (a1 ) + · · · + (an )  êîíå÷íàÿ ñóììà
ïîëóïðÿìûõ, èëè C = {y ∈ Rm | y = Ax, x > 0} = AP  ãîìîìîðôíûé îáðàç
íåîòðèöàòåëüíîãî îðòàíòà.
 Ë1. Ëèíåíîå ïîäïðîñòðàíñòâî åñòü êîíå÷íûé êîíóñ.
    Äîêàçàòåëüñòâîâî. Åñëè u1 , ..., uk  áàçèñ ïîäïðîñòðàíñòâà L , òî L = (u1 )+· · ·+

(uk ) + (−u1 ) + · · · + (−uk ) (èëè L = (u0 ) + (u1 ) + · · · + (uk ) , ãäå u0 = −u1 − · · · − uk ;
äåéñòâèòåëüíî, ïóñòü x = ξ1 u1 + · · · + ξk uk , òîãäà x = η0 u0 + η1 u1 + · · · + ηk uk , ãäå
ξi = ηi − η0 , ò.å. ηi = η0 + ξi > 0 , åñëè η0 > 0 âûáðàòü äîñòàòîñíî áîëüøèì).
 Ï2. (Òåîðåìà äâîéñòâåííîñòè.) Åñëè C  êîíå÷íûé êîíóñ, òî C ∗ ∗ = C .
    Äîêàçàòåëüñòâîâî. Óæå áûëî äîêàçàíî: ÷òî C                ⊇ C . C = P A . Ïóñòü b ∈ / C , ò.å.
                                                         ∗∗

xA = b, x > 0 íå èìååò ðåøåíèÿ. Ïî òåîðåìå 1 èìååì ðåøåíèå Ay 6 0, by > 0 .
Ýòî îçíà÷àåò, ÷òî b ∈     / C ∗∗ . 
 Ñ1. Ïóñòü C = {x ∈ Rm | xA 6 0} ; òîãäà C ∗ = AP = {y ∈ Rm | y = Ax, x > 0} .
    Äîêàçàòåëüñòâîâî. Ïóñòü K = {y ∈ R | y = Ax, x > 0} ; òîãäà K
                                                  m                                   ∗
                                                                                        = C ⇒
K ∗∗ = K = C ∗ . 
   4. Ìíîæåñòâî ðåøåíèé ñèñòåìû ëèíåéíûõ îäíîðîäíûõ íåðàâåíñòâ.
 Çàâèñèìîñòü ðåøåíèÿ óðàâíåíèÿ xA = b (b 6= 0) îò ñèñòåìû ñòðîê ai1 , ..., aik . Ýòî
óðàâíåíèå ìîæíî çàïèâàòü â âèäå ξ1 a1 + · · · + ξm am = b . Ðåøåíèå (ξ1o , ..., ξm
                                                                                 o
                                                                                   ) çàâèñèò
îò ñòðîê ai1 , ..., aik , åñëè ξjo = 0 , äëÿ âñÿêîãî j ∈
                                                       / {i1 , ..., ik } .

                                                  3

Страницы