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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

n
P
i=1
a
i
= v min ξ
i
= ξ
n
(i = 1, ..., n)
n
P
i=1
(ξ
i
− ξ
n
)a
i
< x − ξ
n
v
n
P
i=1
(ξ
i
−
ξ
n
)α
in
< 0
y
A S ⊆ N = {1, 2, ..., n} : i /∈ S, j ∈
S ⇒ α
ij
= 0
i = i
1
→ i
2
→ · · · → i
m
= j
α
i
k+1
,i
k
6= 0 k = 1, 2, ..., m − 1 i ∈ N S
j ∈ N i
S
j /∈ S, k ∈ S α
jk
6= 0
i −→ k → j j /∈
S
i, j ∈ N
y = (η
1
, ..., η
n
) > 0 S = {i ∈ N | η
i
> 0}
S
i /∈ S a
i
y =
n
P
j=1
α
ij
η
j
=
P
j∈S
α
ij
η
j
= η
i
= 0 ⇒ α
ij
= 0
i /∈ S j ∈ S
A
y 6> 0 A
y, y
0
A Ay =
y, Ay
0
= y
0
⇒ A(y − λy
0
) = (y − λy
0
) λ > 0 y − λy
0
> 0
y − λy
0
6> 0 y − λy
0
y − λy
0
= 0
S T S ∩ T S ∪ T
i /∈ S ∩ T ⇒ i /∈ S i /∈ T j ∈ S ∩ T
α
ij
= 0
N = S
1
∪...∪S
k
∪T
S
i
T
                        n
 ìàòðèöà îáìåíà, òî          ai = v . Ìîæåì ñ÷èòàòü, ÷òî min ξi = ξn (i = 1, ..., n) . Èç
                        P
                        i=1
                                           n                                              n
äâóõ ïðèâåäåííûõ ñîîòíîøåíèé èìååì               (ξi − ξn )ai < x − ξn v .  ÷àñòíîñòè,
                                           P                                              P
                                                                                                (ξi −
                                           i=1                                            i=1
ξn )αin < 0 . Íî ýòî íåðàâåíñòâî íåâîçìîæíî, ò.ê. â åãî ëåâîé ÷àñòè ñòîèò âåëè÷èíà
çàâåäîìî íåîòðèöàòåëüíàÿ. Òàêèì îáðàçîì, îáðàçîì ïðåäïîëîæåíèå î íåñóùåñòâîâà-
íèè y íåâåðíî.      
 Îòíîñèòåëüíîñòü öåí  ðàâíîâåñíûé âåêòîð îïðåäåëÿåòñÿ ñ òî÷íîñòüþ äî ïîëîæè-
òåëüíîãî ìíîæèòåëÿ.
 Íåçàâèñèìîå (îòíîñèòåëüíî A ) ïîäìíîæåñòâî S ⊆ N = {1, 2, ..., n} : i ∈      / S, j ∈
S ⇒ αij = 0 .
 Íåïðèâîäèìàÿ ìàòðèöà îáìåíà. Íå ñóùåñòâóåò ñîáñòâåííûõ íåçàâèñèìûõ ïîäìíî-
æåñòâ.
 Ïîñëåäîâàòåëüíîñòü èíäåêñîâ i = i1 → i2 → · · · → im = j íàçîâåì ñâÿçóþùåé,
åñëè αik+1 ,ik 6= 0 äëÿ âñåõ k = 1, 2, ..., m − 1 .  Ëåììà. Ïóñòü i ∈ N è S 
ìíîæåñòâî âñåõ j ∈ N , ñ êîòîðûìè ó i èìååòñÿ ñâÿçóþùàÿ ïîñëåäîâàòåëüíîñòü.
Òîãäà S íåçàâèñèìîå ïîäìíîæåñòâî.
    Äîêàçàòåëüñòâî. Â ñàìîì äåëå, ïóñòü j ∈   / S, k ∈ S è αjk 6= 0 . Òîãäà ñóùåñòâóåò
ñâÿçóþùàÿ ïîñëåäîâàòåëüíîñòü i −→ k → j , ÷òî ïðîòèâîðå÷èò ïðåäïîëîæåíèþ j ∈          /
S     
 Ñëåäñòâèå (Ïðèçíàê íåïðèâîäèìîñòè). Äëÿ ëþáûõ äâóõ i, j ∈ N ñóùåñòâóåò
ñâÿçóþùàÿ ïîñëåäîâàòåëüíîñòü.
 Ëåììà 2. Åñëè y = (η1 , ..., ηn ) > 0  ðàâíîâåñíûé âåêòîð è S = {i ∈ N | ηi > 0} ,
òî S  íåçàâèñèìîå ïîäìíîæåñòâî.
                                                n
    Äîêàçàòåëüñòâî. Äëÿ i ∈ / S èìååì ai y =
                                               P            P
                                                   αij ηj =   αij ηj = ηi = 0 ⇒ αij = 0
                                                   j=1          j∈S
ïðè i ∈/ S è âñåõ j ∈ S . 
 Ò2. Åñëè A íåïðèâîäèìà, òî åå ðàâíîâåñíûé âåêòîð ïîëîæèòåëåí è åäèíñòâåíåí.
   Äîêàçàòåëüñòâî. Ïîëîæèòåëüíîñòü. Åñëè y 6> 0 , òî ïî ëåììå 2 A ïðèâîäèìà.

   Åäèíñòâåííîñòü. Ïóñòü y, y 0  äâà ðàâíîâåñíûõ âåêòîðà ìàòðèöû A . Ay =
y, Ay 0 = y 0 ⇒ A(y − λy 0 ) = (y − λy 0 ) . Ïîäáåðåì λ > 0 òàê, ÷òîáû y − λy 0 > 0
è y − λy 0 6> 0 . Òîãäà y − λy 0  íåïîëîæèòåëüíûé ðàâíîâåñíûé âåêòîð íåïðèâîäèìîé
ìàòðèöû îáìåíà. Ïîýòîìó y − λy 0 = 0 .       
 Íåïðèâîäèìîå íåçàâûèñèìîå ïîäìíîæåñòâî  íå ñîäåðæèò ñîáñòâåííûõ íåçàâèñè-
ìûõ ïîäìíîæåñòâ.
 Ë3. Åñëè S è T  íåçàâèñèìûå, òî S ∩ T è S ∪ T òîæå íåçàâèñèìûå.
   Äîêàçàòåëüñòâî. Ïóñòü i ∈      / S ∩ T ⇒ ëèáî i ∈
                                                   / S , ëèáî i ∈
                                                                / T ; åñëè j ∈ S ∩ T , òî
â ëþáîì ñëó÷àå αij = 0 .        
 Ñ1. Ðàçëè÷íûå íåïðèâîäèìûå ïîäìíîæåñòâà íå ïåðåñåêàþòñÿ è N = S1 ∪...∪Sk ∪T ,
ãäå Si  íåïðèâîäèìûå ïîäìíîæåñòâà, à T íå ñîäåðæèò íåçàâèñèìûõ ïîäìíîæåñòâ.
 Ïðèâåäåíèå ìàòðèöû ê áëî÷íîìó âèäó. Ïðèìåð.

                                            11

Страницы