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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

R
m
x
1
, ..., x
n
x =
n
P
i=1
λ
i
x
i
n
P
i=1
λ
i
= 1
λ
i
> 0, i = 1, ..., 1
(0, ..., 0)
K R
m
x
1
, x
2
∈ K ⇒ λ
1
x
1
+ λ
2
x
2
∈ K
λ
1
, λ
2
> 0, λ
1
+ λ
2
= 1
x
1
, ..., x
k
x = λ
1
x
1
+· · ·+λ
k
x
k
, λ
1
+· · ·+λ
k
= 1, λ
i
> 0
X ⇔
lXm X
X
X ⇔ X = lXm
x K x = λ
1
x
1
+λ
2
x
2
; x
1
, x
2
∈
K, λ
1
, λ
2
> 0, λ
1
+ λ
2
= 1 ⇒ x = x
1
= x
2
K
b
K K =
l
b
Km
xA 6 b
xA 6 b
ex
e
A 6 0
e
A =
A 0
−b −1
!
(x, 1) x
X xA 6 b
e
X = (ec
1
) + · · · + (ec
r
) + (ea
1
) + · · · + (ea
s
) ec
i
= (c
i
, 1), i = 1, ..., r
ea
i
= (a
i
, 0), i = 1, ..., s c
i
A 6 b, i = 1, ..., r; a
i
A 6 0, i = 1, ..., s
K = lc
1
, ..., c
r
m C = (a
1
) + · · · + (a
s
) X = K + C
x ∈ X (x, 1) ∈
e
X (x, 1) = λ
1
ec
1
+· · ·+λec
r
+µ
1
ea
1
+· · ·+
µ
s
ea
s
= (λ
1
c
1
, λ
1
) + · · ·+ (λ
r
c
r
, λ
r
) + (µ
1
a
1
, 0) + · · · + (µ
s
a
s
, 0) = (λ
1
c
1
+ · · · + λ
r
c
r
+ µ
1
a
1
+
· · · + µ
s
a
s
, λ
1
+ · · · + λ
r
) λ
i
, µ
i
> 0 x = λ
1
c
1
+ · · · + λ
r
c
r
+ µ
1
a
1
+ · · · + µ
s
a
s
    6. Âûïóêëûå ìíîæåñòâà è ìíîãîãðàííèêè.
 Ñòðîãî ãîâîðÿ, â äàííîì ðàçäåëå (è ñëåäóþùåì) Rm íóæíî ðàññìàòðèâàòü êàê
àðèôìåòè÷åñêîå àôôèííîå ïðîñòðàíñòâîíà ìíîæåñòâå òî÷åê êîòîðîãî îïðåäåëåíà
                                                        n             n
îïåðàöèÿ  âûïóêëàÿ êîìáèíàöèÿ òî÷åê x1 , ..., xn : x =   λi xi , ãäå   λi = 1 è
                                                        P             P
                                                                                  i=1               i=1
λi > 0, i = 1, ..., 1 . Îäíàêî, äëÿ ïðîñòîòû òî÷êè îòîæäåñòâëÿþòñÿ ñ âåêòîðàìè
èñõîäÿùèìè èçíà÷àëà (0, ..., 0) , êîíöàìè êîòîðûõ ýòè òî÷êè ÿâëÿþòñÿ.
 Âûïóêëîå ïîäìíîæåñòâî K â ïðîñòðàíñòâå Rm : x1 , x2 ∈ K ⇒ λ1 x1 + λ2 x2 ∈ K
äëÿ ëþáûõ λ1 , λ2 > 0, λ1 + λ2 = 1 .
 Ñóììà è ïåðåñå÷åíèå âûïóêëûõ ïîäìíîæåñòâ åñòü âûïóêëîå ïîäìíîæåñòâî.
 Âûïóêëàÿ êîìáèíàöèÿ òî÷åê x1 , ..., xk : x = λ1 x1 +· · ·+λk xk , λ1 +· · ·+λk = 1, λi > 0
 Ë1. X  âûïóêëî ⇔ çàìêíóòî îòíîñèòåëüíî âçÿòèÿ âûïóêëîé êîìáèíàöèè.
 Âûïóêëàÿ îáîëî÷êà lXm ìíîæåñòâà X  âñåõ âûïóêëûõ êîìáèíàöèé òî÷åê èç
X.
 Âûïóêëûé ìíîãîãðàííèê  âûïóêëàÿ îáîëî÷êà êîíå÷íîãî ìíîæåñòâî.
 Ë2. Âûïóêëàÿ îáîëî÷êà  âûïóêëîå ìíîæåñòâî.
 Ñ1. X  âûïóêëî ⇔ X = lXm
 Âûïóêëîñòü è öåíòîð òÿæåñòè.
 Âåðøèíà (êðàéíÿÿ òî÷êà) x  âûïêêëîãî ìíîæåñòâà K : x = λ1 x1 + λ2 x2 ; x1 , x2 ∈
K, λ1 , λ2 > 0, λ1 + λ2 = 1 ⇒ x = x1 = x2 .
 Ò1. Åñëè K  âûïóêëûé ìíîãîãðàííèê è K        b  ìíîæåñòâî åãî âåðøèí, òî K =
  b .
lKm
    7. Ìíîæåñòâî ðåøåíèé ñèñòåìû ëèíåéíûõ íåðàâåíñòâ ïðîèçâîëüíîãî
âèäà.
 Ëåììà 1. Ìíîæåñòâî ðåøåíèé ïðîèçâîëüíîãî ëèíåéíîãî íåðàâåíñòâà xA 6 b åñòü
âûïóêëîå ìíîæåñòâî.
 Ïóñòü çàäàíî ëèíåéíîå íåðàâåíñòâî xA 6 b! (1). Ðàññìîòðèì ëèíåéíîå îäíîðîäíîå
                                                     A 0
íåðàâåíñòâî x      eA e 6 0 (2), ãäå A      e=                       .
                                                     −b −1
 Ëåììà 2. Âåêòîð (x, 1) ÿâëÿåòñÿ ðåøåíèåì (2) òîãäà è òîëüêî òîãäà, êîãäà x åñòü
ðåøåíèå (1).
 Òåîðåìà 4. Ìíîæåñòâî ðåøåíèé X ëþáîãî íåðàâåíñòâà xA 6 b ìîæåò áûòü
ïðåäñòàâëåíî êàê ñóììà âûïóêëîãî ìíîãîãðàííèêà è êîíå÷íîãî êîíóñà.
      Äîêàçàòåëüñòâî. Ïî òåîðåìå (2) ìíîæåñòâî ðåøåíèé ñèñòåìû (2) åñòü êîíå÷íûé

êîíóñ. Ïóñòü X        e = (e   c1 ) + · · · + (ecr ) + (ea1 ) + · · · + (eas ) , ãäå e ci = (ci , 1), i = 1, ..., r
è e  ai = (ai , 0), i = 1, ..., s . Òîãäà ci A 6 b, i = 1, ..., r; ai A 6 0, i = 1, ..., s . Ïóñòü
K = lc1 , ..., cr m è C = (a1 ) + · · · + (as ) . Èìååì X = K + C .
      Â ñàìîì äåëå, ïóñòü x ∈ X , òîãäà (x, 1) ∈ X                e è (x, 1) = λ1e    c1 +· · ·+λe  cr +µ1e a1 +· · ·+
µs eas = (λ1 c1 , λ1 ) + · · · + (λr cr , λr ) + (µ1 a1 , 0) + · · · + (µs as , 0) = (λ1 c1 + · · · + λr cr + µ1 a1 +
· · · + µs as , λ1 + · · · + λr ) , ãäå λi , µi > 0 . Îòñþäà x = λ1 c1 + · · · + λr cr + µ1 a1 + · · · + µs as

                                                          7

Страницы