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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

λ
1
+ · · · + λ
r
= 1 x = y + z y = λ
1
c
1
+ · · · + λ
r
c
r
∈ K
z = µ
1
a
1
+ · · · + µ
s
a
s
∈ C = {x|xA 6 0}
K C
xA 6 b
K = la
1
, ..., a
r
m, C = (c
1
) + · · · + (c
s
) ea
i
=
(a
i
, 1), i = 1, ..., r ec
i
= (c
i
, 0), i = 1, ..., s
e
C = (ea
1
) + · · · +
(ea
r
) + (ec
1
) + · · · + (ec
s
)
xA 6 0
e
C
ex
e
A 6 0
e
A
t
(0, −1)
e
A =
A 0
−b −1
!
ex ∈
e
C =⇒ ex = (x, ξ) ξ > 0
ex ∈
e
C ex = (x, 1)
x ∈ K + C ex = λ
1
(a
1
, 1) + · · · + λ
r
(a
r
, 1) + µ
1
(c
1
, 0) + · · · + µ
s
(c
s
, 0)
λ
i
, µ
i
> 0 (x, 1) = (λ
1
a
1
+ · · · + λ
r
a
r
+ µ
1
c
1
+ · · · + µ
s
c
s
, λ
1
+ · · · + λ
r
)
x = λ
1
a
1
+ · · · + λ
r
a
r
+ µ
1
c
1
+ · · · + µ
s
c
s
λ
1
+ · · · + λ
r
= 1 y = λ
1
a
1
+ · · · + λ
r
a
r
∈
K, z = µ
1
c
1
+ · · · + µ
s
c
s
∈ C x = y + z
x ∈ K + C ex = (x, 1) ∈
e
C x = y + z
y = λ
1
a
1
+ · · · + λ
r
a
r
, λ
i
> 0, λ
1
+ · · · + λ
r
= 1 z = µ
1
c
1
+ · · · + µ
s
c
s
, µ
i
> 0
(x, 1) = (λ
1
a
1
+ · · · + λ
r
a
r
+ µ
1
c
1
+ · · · + µ
s
c
s
, λ
1
+ · · · + λ
r
) = λ
1
(a
1
, 1) + · · · +
λ
r
(a
r
, 1) + µ
1
(c
1
, 0) + · · · + µ
s
(c
s
, 0) = λ
1
ea
1
+ · · · + λ
r
ea
r
+ µ
1
ec
1
+ · · · + µ
s
ec
s
x x
e
A 6 b (x, 1) ∈
e
C
xA 6 0
xA 6 b
xA 6 0
e
A m + 1 A
xA = 0 xA 6 0
e
A (A, 0)
e
X
e
X = (ec
1
)+· · ·+
(ec
s
)
ex = (x, ξ) ex
e
A = (xA − ξb, −ξ) 6 0 −ξ 6 0
ξ > 0 ex = (x, 0) ex
e
A = (xA, 0) 6 0 xA 6 0
x = 0 ec
i
= (c
i
, 1), i =
1, ..., s C = lc
1
, ..., c
s
m
C x
0
A 6 b ex
0
= (x
0
, 1))
ex
0
= λ
1
e
1
+ · · · + λ
s
e
s
λ
i
> 0, i = 1, ..., s
x
0
= λ
11
+ · · · + λ
ss
λ
1
+ · · · + λ
s
= 1
X R
m
µ > 0
x = (ξ
i
) ∈ X |ξ
i
| 6 µ
è λ1 + · · · + λr = 1 . Òàêèì îáðàçîì, x = y + z , ãäå y = λ1 c1 + · · · + λr cr ∈ K è
z = µ1 a1 + · · · + µs as ∈ C = {x|xA 6 0} . 
 Òåîðåìà 5. Ñóììà âûïóêëîãî ìíîãîãðàííèêà K è êîíå÷íîãî êîíóñà C âñåãäà
ÿâëÿåòñÿ ìíîæåñòâîì âñåõ ðåøåíèé íåêîòîðîãî ëèíåéíîãî íåðàâåíñòâà âèäà xA 6 b .
     Äîêàçàòåëüñòâî. Ïóñòü K = la1 , ..., ar m, C = (c1 ) + · · · + (cs ) . Ïîëîæèì e          ai =
(ai , 1), i = 1, ..., r , e   ci = (ci , 0), i = 1, ..., s è ðàññìîòðèì êîíóñ C  e = (ea1 ) + · · · +
(e
 ar ) + (e                cs ) . Òàê êàê âñÿêèé êîíå÷íûé êîíóñ åñòü ìíîæåñòâî âñåõ ðåøåíèé
          c1 ) + · · · + (e
îäíîðîäíîãî íåðàâåíñòâà âèäà xA 6 0 , òî â íàøåì ñëó÷àå C                 e åñòü ìíîæåñòâî ðåøå-
íèé íåðàâåíñòâà x        eAe 6 0 äëÿ íåêîòîðîé ìàòðèöû A         e . Ïðè ýòîì ìîæíî ñ÷èòàòü, ÷òî
                                                                                !
                                                                        A    0
ïîñëåäíèé ñòîëáåö â íåé èìååò âèä t(0, −1) , ò.å. A             e=                . Â ñàìîì äåëå,
                                                                        −b −1
ò.ê. ïî ïîñòðîåíèþ èìååì x           e∈C   e =⇒ x e = (x, ξ) , ãäå ξ > 0 , òî äîáàâëåíèå ñîîòâåò-
ñòâóþùåãî íåðàâåíñòâà íå èçìåíèò ìíîæåñòâî ðåøåíèé. Åñëè x                  e∈C e è xe = (x, 1) , òî
x ∈ K + C . Äåéñòâèòåëüíî, x            e = λ1 (a1 , 1) + · · · + λr (ar , 1) + µ1 (c1 , 0) + · · · + µs (cs , 0) ,
ãäå λi , µi > 0 , ò.å. (x, 1) = (λ1 a1 + · · · + λr ar + µ1 c1 + · · · + µs cs , λ1 + · · · + λr ) ; îòêóäà
x = λ1 a1 + · · · + λr ar + µ1 c1 + · · · + µs cs è λ1 + · · · + λr = 1 , ò.å. y = λ1 a1 + · · · + λr ar ∈
K, z = µ1 c1 + · · · + µs cs ∈ C è x = y + z .
    Îáðàòíî, åñëè x ∈ K + C , òî x             e = (x, 1) ∈ C e . Â ñàìîì äåëå, ïóñòü x = y + z , ãäå
y = λ1 a1 + · · · + λr ar , λi > 0, λ1 + · · · + λr = 1 è z = µ1 c1 + · · · + µs cs , µi > 0 ; òîãäà
èìååì (x, 1) = (λ1 a1 + · · · + λr ar + µ1 c1 + · · · + µs cs , λ1 + · · · + λr ) = λ1 (a1 , 1) + · · · +
λr (ar , 1) + µ1 (c1 , 0) + · · · + µs (cs , 0) = λ1e
                                                    a1 + · · · + λ r e                         cs . Ïî ëåììå 2
                                                                              c 1 + · · · + µs e
                                                                     ar + µ 1 e
x åñòü ðåøåíèå íåðàâåíñòâà xA              e 6 b òîãäè è òîëüêî òîãäà, êîãäà (x, 1) ∈ C              e. 

      Ïðåäëîæåíèå 1. Åñëè xA 6 0 èìååò òîëüêî íóëåâîå ðåøåíèå, òî ìíîæåñòâî
ðåøåíèé xA 6 b åñòü âûïóêëûé ìíîãîãðàííèê.
     Äîêàçàòåëüñòâî. Ïóñòü xA 6 0 èìååò òîëüêî íóëåâîå ðåøåíèå. Òîãäà ñòðîêè

ìàòðèöû A     e ëèíåéíî íåçàâèñèìû è åå ðàíã ðàâåí m + 1 (ñòðîêè A íåçàâèñèìû, ò.ê.
èíà÷å xA = 0 (à çíà÷èò è xA 6 0 ) èìååò íåíóëåâîå ðåøåíèå; êðîìå òîãî, î÷åâèäíî,
äîïîëíèòåëüíàÿ ñòðîêà â A       e íå çàâèñèò îò (A, 0) ). Ïî ïðåäëîæåíèþ 1.5 ìíîæåñòâî
ðåøåíèé X     e åñòü çàîñòðåííûé êîíóñ, ò.å. ñóììà êðàéíèõ íàïðàâëåíèé X         e = (ec1 )+· · ·+
 cs ) . Ïðè ýòîì êàæäîå íåíóëåâîå ðåøåíèå ñèñòåìû (2) èìååò ïîñëåäíþþ êîîðäèíàòó
(e
> 0. Â ñàìîì äåëå, ïóñòü x     e = (x, ξ) ; òîãäà x  e = (xA − ξb, −ξ) 6 0 ; îòêóäà −ξ 6 0 ,
                                                    eA
ò.å. ξ > 0 ; ïóñòü x e = (x, 0)  ðåøåíèå (2): òîãäà x    eAe = (xA, 0) 6 0 , îòêóäà xA 6 0 è,
ñëåäîâàòåëüíî, x = 0 ïî îïðåäåëåíèþ. Ïîýòîìó ìîæíî ñ÷èòàòü, ÷òî e                ci = (ci , 1), i =
1, ..., s . Óáåäèìñÿ, ÷òî ìíîæåñòâî ðåøåíèé (1) â äàííîì ñëó÷àå åñòü C = lc1 , ..., cs m .
 ñèëó ëåììû C ëåæèò â ìíîæèñòâå ðåøåíèé (1). Ïóñòü x0 A 6 b ; òîãäà x              e0 = (x0 , 1))
åñòü ðåøåíèå (2) è ïîòîìó x       e0 = λ1e1 + · · · + λses , ãäå λi > 0, i = 1, ..., s . Îòñþäà
x0 = λ11 + · · · + λss è λ1 + · · · + λs = 1 . 
 Ìíîæåñòâî X â Rm íàçûâàåòñÿ îãðàíè÷åííûì, åñëè ñóùåñòâóåò µ > 0 òàêîå, ÷òî
äëÿ âñåõ x = (ξi ) ∈ X èìååì |ξi | 6 µ .

                                                        8

Страницы