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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

xA = b (b 6= 0)
m x a
1
, ..., a
m
a
1
, ..., a
m
m
xA = 0
xA = 0 ⇔ ξ
1
a
1
+ · · · + ξ
m
a
m
= 0 x = (ξ
1
, ..., ξ
m
)
ξ
1
ba
1
+ · · · + ξ
m
ba
m
= e
n+1
ba
i
= (a
i
, 1) e
n+1
= (0, ..., 0, 1) ∈
R
n+1
ξ
1
+ · · · + ξ
m
= 1, ξ
i
> 0
m
ba
1
, ..., ba
m
x
o
= (ξ
o
1
, ..., ξ
o
m
)
ξ
o
i
= 0
ξ
o
1
= 0 µ, ν > 0 x
0
= µx −νx
o
m
1
o
ξ
0
i
= µξ
i
−νξ
o
i
> 0 i = 1, ..., m 2
o
j ξ
0
j
= µξ
j
−νξ
o
j
= 0 3
o
ξ
0
1
+· · · +ξ
0
m
= 1
µξ
i
> νξ
o
i
θ = µ/ν > ξ
o
i
/ξ
i
θ = max{ξ
o
i
/ξ
i
}
m
P
i=1
(µξ
i
− νξ
o
i
) = 1 µ − ν = 1
m
P
i=1
ξ
i
=
m
P
i=1
ξ
o
i
= 1
θ = µ/ν µ − ν = 1 µ = θ/(θ − 1), ν = 1/(θ − 1)
θ > 1
m
P
i=1
ξ
i
=
m
P
i=1
ξ
o
i
= 1
k
ξ
o
i
> ξ
i
max{ξ
o
i
/ξ
i
} > 1 µξ
i
= νξ
o
i
+ ξ
0
i
i = 1, ..., m x = 1/θx
o
+ (θ − 1)/θx
0
x
o
x
0
L L ∩ P
 Áàçèñíîå ðåøåíèå  çàâèñÿùåå îò ëèíåéíî íåçàâèñèìîé ñèñòåìû ñòðîê.
 Ï1. Åñëè xA = b (b 6= 0) èìååò íåîòðèöàòåëüíîå ðåøåíèå, òî îíî èìååò è áàçèñíîå
íåîòðèöàòåëüíîå ðåøåíèå.
     Äîêàçàòåëüñòâî. Èíäóêöèÿ ïî m . Ìîæíî ñ÷èòàòü, ÷òî x çàâèñèò îò âñåõ a1 , ..., am

è ÷òî a1 , ..., am ëèíåéíî çàâèñèìû. Âåêòîð êîýôôèöèåíòîâ ýòîé çàâèñèìîñòè è äàííîå
ðåøåíèå ïîçâîëÿþò ñêîìáèíèðîâàòü íîâîå íåîòðèöàòåëüíîå ðåøåíèå, êîòîðîå áóäåò
çàâèñèòü îò ìåíüøåãî, ÷åì m ñòðîê è ïîòîìó ìîæíî ïðèìåíèòü èíäóêöèîííîå ïðåä-
ïîëäæåíèå.          
 Ï2. Ìíîæåñòâî íåîòðèöàòåëüíûõ ðåøåíèé xA = 0 åñòü êîíå÷íûé êîíóñ.
     Äîêàçàòåëüñòâî. xA = 0 ⇔ ξ1 a1 + · · · + ξm am = 0 (1), ãäå x = (ξ1 , ..., ξm ) . Ðàñ-

ñìîòðèì ñèñòåìó ξ1b                    am = en+1 (2), ãäå b
                        a1 + · · · + ξmb                   ai = (ai , 1) , à en+1 = (0, ..., 0, 1) ∈
R  n+1
          (ò.å. äîáàâèì ê (1): ξ1 + · · · + ξm = 1, ξi > 0 ). Êàæäîå ðåøåíèå (1) îòëè÷àåò-
ñÿ îò ðåøåíèÿ (2) ðàçâå ëèøü ÷èñëîâûì ìíîæèòåëåì. Ñëåäîâàòåëüíî, èç êîíå÷íîé
ïîðîæ- äåííîñòè ìíîæåñòâà ðåøåíèé ñèñòåìû (2) ñëåäóåò êîíå÷íàÿ ïîðîæäåííîñòü
ìíîæåñòâà ðåøåíèé ñèñòåìû (1). Ïîýòîìó óòâåðæäåíèå Ï2 âûòåêàåò èç ñëåäóþùåé
ëåììû.          
 Ë1. Âñÿêîå íåîòðèöàòåëüíîå ðåøåíèå ñèñòåìû (2) åñòü íåîòðèöàòåëüíàÿ ëèíåéíàÿ
êîìáèíàöèÿ áàçèñíûõ íåîòðèöàòåëüíûõ ðåøåíèé.
     Äîêàçàòåëüñòâî. Ïðèìåíèì ê ðåøåíèÿì (2) èíäóêöèþ ïî ÷èñëó ñòðîê, îò êîòî-

ðûõ çàâèñèò äàííîå ðåøåíèå. Ìîæåì ñ÷èòàòü, ÷òî îíî çàâèñèò îò âñåõ m ñòðîê. Åñëè
          am ëèíåéíî íåçàâèñèìû, òî äàííîå ðåøåíèå ñàìî áàçèñíîå. Åñëè æå çàâèñèìûå,
a1 , ..., b
b
òî ïî Ï1 ñóùåñòâóåò áàçèñíîå íåîòðèöà- òåëüíîå ðåøåíèå xo = (ξ1o , ..., ξm         o
                                                                                     ) , ó êîòîðîãî
õîòÿ áû îäíî ξi = 0 (èíà÷å îíî íå áûëî áû áàçèñíûì). Ïóñòü äëÿ îïðåäåëåííîñòè
                    o

ξ1o = 0 . Ïîäáåðåì µ, ν > 0 òàê, ÷òîáû x0 = µx − νxo òîæå áûëî íåîòðèöàòåëüíûì ðå-
øåíèåì ñèñòåìû (2), íî çàâèñÿùåì îò ìåíüøåãî, ÷åì m ÷èñëà ñòðîê. Äëÿ ýòîãî íóæ-
íî èìåòü 1o ξi0 = µξi −νξio > 0 äëÿ êàæäîãî i = 1, ..., m , 2o õîòÿ áû äëÿ îäíîãî çíà÷å-
íèÿ j ñòðîãîå ðàâåíñòâî ξj0 = µξj −νξjo = 0 è 3o ξ10 +· · ·+ξm    0
                                                                    = 1 . Äëÿ âûïîëíåíèÿ ïåð-
âûõ äâóõ óñëîâèé íóæíî ïîëîæèòü µξi > νξio , θ = µ/ν > ξio /ξi , ãäå θ = max{ξio /ξi } .
                       m                                            m        m
À ïîñëåäíåå äàåò         (µξi − νξio ) = 1 , ò.å. µ − ν = 1 (ò.ê.              ξio = 1 ). Èç äâóõ
                       P                                            P       P
                                                                      ξi =
                     i=1                                           i=1      i=1
ðàâåíñòâ θ = µ/ν è µ − ν = 1 èìååì µ = θ/(θ − 1), ν = 1/(θ − 1) . Îñòàåòñÿ óáåäèòü-
                                   m      m
ñÿ, ÷òî θ > 1 . Äåñòâèòåëüíî, ò.ê.          ξio = 1 è ÷èñëî íåíóëåâûõ ñëàãàåìûõ
                                   P      P
                                     ξi =
                                         i=1        i=1
â ïåðâîé ñóììå áîëüøå, ÷åì âî âòîðîé, òî äîëæåí íàéòèñü õîòÿ áû îäèí èíäåêñ k ,
äëÿ êîòîðîãî ξio > ξi , à çíà÷èò max{ξio /ξi } > 1 . Òàêèì îáðàçîì, èìååì µξi = νξio + ξi0
äëÿ âñåõ i = 1, ..., m . Îòñþäà x = 1/θxo + (θ − 1)/θx0 . Çäåñü ïðàâàÿ ÷àñòü åñòü
íåîòðèöàòåëüíàÿ ëèíåéíàÿ êîìáèíàöèÿ íåîòðèöàòåëüíûõ áàçèñíûõ ðåøåíèé (2), ò.ê.
xo  áàçèñíîå ðåøåíèå ïî ïîñòðîåíèþ, à x0  íåîòðèöàòåëüíàÿ ëèíåéíàÿ êîìáèíà-
öèÿ íåîòðèöàòåëüíûõ áàçèñíûõ ðåøåíèé ïî ïðåäïîëîæåíèþ èíäóêöèè.               
 Ñ1. Åñëè L  ïîäïðîñòðàíñòâî, òî L ∩ P  êîíå÷íûé êîíóñ.


                                                4

Страницы