А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 54
Текст из файла (страница 54)
Ôóíêöè� pA (x) ïîëîæèòåëüí� îäíîðîäíà, ò.å. äë� ëþáîã� λ > 0 () λxtpA (λx) = λ inf > 0 ∈ A = λpA (x) ∀x ∈ E m .λtÄîêàæåì, ÷ò� ôóíêöè� pA (x) ñóáàääèòèâíà, ò.å. pA (x + y) ≤ pA (x) + pA (y) ∀x, y ∈ E m . Äåéñòâèòåëüíî, âîçüìå� x, y 6= 0. Âåêòî� x + ypA (x) xpA (y) y =· + · pA (x) + pA (y) pA (x) + pA (y) pA (x) pA (x) + pA (y) pA (y) 260(Π.1) Ïðèëîæåíè�ïðèíàäëåæè� ìíîæåñòâ� A, ïîñêîëüê� ÿâëÿåòñ� âûïóêëî� êîìáèíàöèå� âåêòîðî� pAx (x) , pAy (y) è� A.
Îòñþä� ïîëó÷àå� íåðàâåíñòâ� (Ï.1). Äîêàæåì, ÷ò� ôóíêöè� Ìèíêîâñêîã� íåïðåðûâíà. Äåéñòâèòåëüíî, äë� ëþáîã� x ∈ Oε0 x |x| |x|∈/ Oε0 ⇒ ≥ ε0 ⇒ pA (x) ≤. pA (x) pA (x) ε0 Îòñþä� ñëåäóåò, ÷ò� pA (x) íåïðåðûâí� � íóëå.
Íåïðåðûâíîñò� ôóíêöè� pA (x) � ëþáî� òî÷ê� x0 âûòåêàå� è� íåðàâåíñòâ� ( ñóáàääèòèâíîñò� ) |pA (x) − pA (x0 )| ≤ max[pA (x − x0 ), pA (x0 − x)] � å� íåïðåðûâíîñò� � íóëå. Ïóñò� âûïóêëû� êîìïàêò� A � B � E m ñîäåðæà� âíóòðåííè� òî÷êè. Òîãä� íàéäåòñ� âçàèìí� îäíîçíà÷íî� � íåïðåðûâíî� îòîáðàæåíè� (ãîìåîìîðôèçì) A í� B. Äîêàçàòåëüñòâî.
Áå� ïîòåð� îáùíîñò� áóäå� ñ÷èòàòü, ÷ò� íóë� ñîäåðæèòñ� � A ∩ B âìåñò� ñ� ñâîå� îêðåñòíîñòü� Oε0 . Îïðåäåëè� îòîáðàæåíè� pA (x)τ : A → B, τ (0) = 0, τ (x) = x, x 6= 0, pB (x)Òåîðåì� Ï.2. ãä� pA (x), pB (x) − ôóíêöè� Ìèíêîâñêîã� ìíîæåñò� A � B. Íåòðóäí� ïðîâåðèòü, ÷ò� pB (y) τ −1 (y) = y pA (y)− îòîáðàæåíèå, îáðàòíî� � τ. Ïîñêîëüê� ôóíêöè� pA (x), pB (x) íåïðåðûâíû, îòîáðàæåíè� τ (x) íåïðåðûâí� ïð� x =6 0.
Ïðîâåðè� íåïðåðûâíîñò� τ (x) � íóëå. Ìíîæåñòâ� B îãðàíè÷åí� � ïîýòîì� íàéäåòñ� òàêî� ÷èñë� α, ÷ò� äë� âñå� x ∈ B |x| ≤ α. Ïîñêîëüê� pBx(x) ∈ B, pB|x(|x) ≤ α. Äë� ëþáîã� âåêòîð� x ∈ Oε0 âûïîëíåí� íåðàâåíñòâ� pA (x) ≤ |x| (ñì. âûø� äîêàε0 çàòåëüñòâ� íåïðåðûâíîñò� ôóíêöè� pA (x)). Ñëåäîâàòåëüíî, äë� âñÿêîã� x ∈ Oε0 pA (x) α|x||x| ≤ |τ (x)| = .pB (x)ε0 Ï4. Ñèìïëåêñ� � òåîðåì� � íåïîäâèæíî� òî÷ê� Ïóñò� {x1 , ..., xn+1 } − ìíîæåñòâ� âåêòîðî� è� E m (n ≤ m), âûïóêëà� 261 Ïðèëîæåíè�îáîëî÷ê� êîòîðîã�K = {x ∈ Em | x = n+1Xi λi x ,i=1 n+1Xλi = 1, λi ≥ 0, i = 1, ..., n + 1}i=1 èìåå� ðàçìåðíîñò� n. Òîãä� ìíîæåñòâ� K íàçûâàåòñ� ñèìïëåêñîì, ïîðîæäåííû� âåðøèíàì� x1 , ..., xn+1 .
Äë� ñèìïëåêñ� K áóäå� òàêæ� èñïîëüçîâàò� îáîçíà÷åíè� K = x1 · · · xn+1 . Ðàçìåðíîñò� n îçíà÷àå� ëèíåéíó� íåçàâèñèìîñò� âåêòîðî� xn+1 − x1 , ..., xn+1 − xn . Îòñþä� âûòåêàåò, ÷ò� äë� âñÿêîã� x ∈ K êîýôôèöèåíò� λi (x), i = 1, ..., n + 1, � ðàçëîæåíè� x ï� xi îïðåäåëåí� îäíîçíà÷í� � ÿâëÿþòñ� íåïðåðûâíûì� ôóíêöèÿì� í� K. Âñÿêî� ìíîæåñòâî, ñîäåðæàùå� r ≤ n + 1 âåðøèí, ïîðîæäàå� (r − 1)ìåðíû� ñèìïëåêñ, íàçûâàåìû� ãðàíü� ñèìïëåêñ� K. Âåðøèí� x1 , ..., xn+1 ÿâëÿþòñ� íóëüìåðíûì� ãðàíÿìè. n-ìåðíà� ãðàí� ñîâïàäàå� � K.
Îäíî6 j, íàçûâàþòñ� ðåáðàì� ñèìïëåêñ� K. Äèàìåò� ìåðíû� ãðàí� xi xj , i = ñèìïëåêñ� K îïðåäåëÿåòñ� êà� ìàêñèìàëüíà� äëèí� åã� ðåáåð. Ïîäìíîæåñòâ� K 0 ñèìïëåêñ� K âèä� 0 K = {x ∈ Em | x = n+1Xi=1 i λi x ,n+1Xλi = 1, λi > 0, i = 1, ..., n + 1}i=1 íàçûâàåòñ� îòêðûòû� ñèìïëåêñîì, ïîðîæäåííû� âåðøèíàì� x1 , ..., xn+1 . Äë� îòêðûòîã� ñèìïëåêñ� áóäå� òàêæ� èñïîëüçîâàò� îáîçíà÷åíè� K 0 = x1 · · · xn+1 . Íóëüìåðíû� ñèìïëåêñ� ÿâëÿþòñ� îòêðûòûìè. Îòêðûòû� ðåáð� áóäå� îáîçíà÷àò� ÷åðå� xi xj . Ïóñò� ñèìïëåê� K òàêè� îáðàçî� ðàçáè� í� îòêðûòû� ïîïàðí� íåïåðåñåêàþùèåñ� ñèìïëåêñ� K1 , ..., Kp , ÷ò� ëþáà� îòêðûòà� ãðàí� êàæäîã� ñèìïëåêñ� Kj ïðèíàäëåæè� ðàçáèåíèþ.
Òàêî� ðàçáèåíè� íàçûâàåòñ� ñèìïëèöèàëüíûì. Ñèìïëåêñ� Kj , ïðèíàäëåæàùè� K 0 , îáðàçóþ� ðàçáèåíè� îòêðûòîã� ñèìïëåêñà. Í� ðèñ. Ï.1 ïðèâåäå� ïðèìå� ñèìïëèöèàëüíîã� ðàçáèåíè� äâóìåðíîã� ñèìïëåêñ� K í� äâ� äâóìåðíûõ, ïÿò� îäíîìåðíû� � ÷åòûð� íóëüìåðíû� îòêðûòû� ñèìïëåêñà. 262 Ïðèëîæåíè�b x2@@� @� b y@@� @� @� x3 x1 Ðèñ. Ï.1 Ñîîòâåòñòâóþùè� îòêðûòû� ñèìïëåê� K 0 ðàçáè� í� äâ� äâóìåðíû� � îäè� îäíîìåðíû� îòêðûòû� ñèìïëåêñà. Åñë� óäàëèò� è� ðàçáèåíè� íóëüìåðíû� ñèìïëåê� y, � ðåáð� x2 y � yx3 çàìåíèò� í� ðåáð� x2 x3 , ò� ïîëó÷è� ïðèìå� íåñèìïëèöèàëüíîã� ðàçáèåíèÿ.
Äë� ñèìïëèöèàëüíîã� ðàçáèåíè� π ÷åðå� δ(π) îáîçíà÷è� ìàêñèìàëüíû� äèàìåò� ñèìïëåêñîâ, âõîäÿùè� � π. n+1P i 1 Òî÷ê� n+1 x íàçûâàåòñ� áàðèöåíòðî� ñèìïëåêñ� K. Îïðåäåëè� i=1 ñèìïëèöèàëüíî� ðàçáèåíèå, íàçûâàåìî� áàðèöåíòðè÷åñêèì, êàæäî� ðåáð� êîòîðîã� ñîåäèíÿå� áàðèöåíòð� ãðàí� � íåêîòîðî� å� ïîäãðàí� ñèìïëåêñ� K. Äë� ñèìïëåêñ� x1 x2 îí� ñîñòîè� è� âåðøè� x1 , x2 , åã� áàðèöåíòð� b = 12 (x1 + x2 ) � äâó� îòêðûòû� ðåáå� x1 b � bx2 .
Ïðåäïîëîæèì, ÷ò� áàðèöåíòðè÷åñêî� ðàçáèåíè� îïðåäåëåí� äë� ëþáîã� ñèìïëåêñ� ðàçìåðíîñò� k ≤ n − 1. Îïðåäåëè� åã� äë� ñèìïëåêñ� K ðàçìåðíîñò� n c áàðèöåíòðî� b. Ïóñò� π � − ñåìåéñòâ� îòêðûòû� ñèìïëåêñîâ, âõîäÿùè� � áàðèöåíòðè÷åñêè� ðàçáèåíè� âñå� (n − 1)-ìåðíû� ãðàíå� ñèìïëåêñ� K. Âîçüìå� ïðîèçâîëüíû� ñèìïëåê� K � = y 1 · · · y l , l ≤ n è� π 0 .
Ïðåäïîëîæè� ïîèíäóêöèè, ÷ò� êàæäî� åã� ðåáð� y i y j ñîåäèíÿå� áàðèöåíòð� íåêîòîðî� ãðàí� � å� ïîäãðàí� ñèìïëåêñ� K. Íåòðóäí� âèäåòü, ÷ò� àíàëîãè÷íû� ñâîéñòâî� îáëàäàå� � ñèìïëåê� y 1 · · · y l b. Ñîâîêóïíîñò� âñå� òàêè� ñèìïëåêñî� y 1 · · · y l b � áàðèöåíò� b äîáàâè� � ñåìåéñòâ� π 0 . � ðåçóëüòàòåïîëó÷è� áàðèöåíòðè÷åñêî� ðàçáèåíè� π1 ñèìïëåêñ� K. n Ïîêàæåì, ÷ò� δ(π1 ) ≤ n+1 d, ãä� d − äèàìåò� ñèìïëåêñ� K. Äåéñòâèòåëüíî, âîçüìå� ëþáî� ðåáð� b0 b0� ðàçáèåíè� π1 , ãä� áå� ïîòåð� îáùíîñò� s+1b� = r+11 � i 0� 1 � jx , b = x , r < s ≤ n.
s + 1 i=1 r + 1 j=1 263Ïðèëîæåíè� Òîãä�s+1 1 X|b� − b00 | = (xi − b00 ) = s + 1i=1 s+1 r+1 11 � � i s(r + 1)d ndj = (x − x ) ≤ ≤ . s + 1 r + 1 (s + 1)(r + 1) n + 1i=1 j=1 n Èòàê, δ(π1 ) ≤ n+1 d. Åñë� êàæäû� ñèìïëåêñ, ïðèíàäëåæàùè� ðàçáèåíè� π1 , ïîäâåðãíóò� áàðèöåíòðè÷åñêîì� ðàçáèåíèþ, ïîëó÷è� ñèìïëèn 2öèàëüíî� ðàçáèåíè� π2 , äë� êîòîðîã� δ(π2 ) ≤ ( n+1 ) d. Ïîâòîðÿ� àíàëîãè÷íó� ïðîöåäóð� k ðàç, ïîëó÷è� ñèìïëèöèàëüíî� ðàçáèåíè� πk � n kδ(πk ) ≤ ( n+1 ) d.
Òåîðåì� Ï.3 (ëåìì� Øïåðíåðà). Ïóñò� π − ñèìïëèöèàëüíî� ðàçáèåíè� n-ìåðíîã� ñèìïëåêñ� K = x1 · · · xn+1 , � ôóíêöè� ν : K → {x1 , ..., xn+1 } óäîâëåòâîðÿå� óñëîâè� ν(x) ∈ {xi | λi (x) > 0} ∀x ∈ K. Òîãä� íàéäåòñ� òàêî� n-ìåðíû� ñèìïëåê� y 1 · · · y n+1 ðàçáèåíè� π, ÷ò� ν(y i ) = xi , i = 1, ..., n + 1. ×èñëî òàêèõ ñèìïëåêñîâ íå÷åòíî.
Äîêàçàòåëüñòâî. Äë� n = 0 óòâåðæäåíè� òåîðåì� î÷åâèäíî. Ïðåäïîëîæèì, ÷ò� îí� ñïðàâåäëèâ� äë� (n − 1)-ìåðíû� ñèìïëåêñîâ. Ïóñò� K1 , ..., Kp − n-ìåðíû� îòêðûòû� ñèìïëåêñû, âõîäÿùè� � ðàçáèåíè� π. Áóäå� ãîâîðèòü, ÷ò� (n−1)-ìåðíà� ãðàí� y 1 · · · y n ñèìïëåêñ� Kj = y 1 · · · y n+1 îòìå÷åíà, åñë� ν(y i ) = xi , i = 1, ..., n.
Åñë� ñèìïëåê� Kj óäîâëåòâîðÿå� óòâåðæäåíè� òåîðåìû, òî, ââèä� ðàâåíñò� ν(y i ) = xi , i = 1, ..., n + 1, î� èìåå� ðîâí� îäí� îòìå÷åííó� ãðàíü. Äåéñòâèòåëüíî, ëþáà� äðóãà� (n − 1)-ìåðíà� ãðàí� ñèìïëåêñ� Kj ñîäåðæè� âåðøèí� y n+1 . Í� ν(y n+1 ) = xn+1 � ýò� ãðàí� í� ÿâëÿåòñ� îòìå÷åííîé. Ïóñò� ñèìïëåê� Kj í� óäîâëåòâîðÿå� óòâåðæäåíè� òåîðåì� � èìåå� îòìå÷åííó� ãðàí� y 1 · · · y n . Òîãä� î� èìåå� ðîâí� äâ� îòìå÷åííû� ãðàíè.
Äåéñòâèòåëüíî, ï� ïðåäïîëîæåíè� ν(y i ) = xi , i = 1, ..., n � áå� ïîòåð� îáùíîñò� ν(y n+1 ) = x1 . Òîãä� (n − 1)-ìåðíû� ãðàí� y 1 · · · y n èy 2 · · · y n y n+1 ÿâëÿþòñ� îòìå÷åííûìè. Ïóñò� σj − ÷èñë� îòìå÷åííû� ãðàíå� ñèìïëåêñ� Kj . Ï� äîêàçàííîì� σj ∈ {0, 1, 2} � σj = 1 òîëüê� � òî� ñëó÷àå, êîãä� ñèìïëåê� Kj óäîâëåòâîðÿå� óòâåðæäåíè� òåîðåìû. Ïîýòîì� îñòàëîñ� äîêàçàòü, ÷ò� îáùå� pP÷èñë� îòìå÷åííû� ãðàíå� χ = σj íå÷åòíî.
� ýòî� ñëó÷à� îáÿçàòåëüí� j=1 íàéäåòñ� ñèìïëåê� Kj , óäîâëåòâîðÿþùè� óòâåðæäåíè� òåîðåìû. 264 Ïðèëîæåíè�Ïóñò� V = y 1 · · · y n − êàêàÿ-ëèá� (n − 1)-ìåðíà� îòìå÷åííà� îòêðûòà� ãðàí� ñèìïëåêñ� Kj . Åñë� V ⊂ K\K 0 , ò� V ïðèíàäëåæè� íåêîòîðî� (n − 1)-ìåðíî� ãðàí� ñèìïëåêñ� K � ÿâëÿåòñ� ãðàíü� åäèíñòâåííîã� nìåðíîã� ñèìïëåêñ� ðàçáèåíè� π. Ïð� ýòî� è� ðàâåíñò� ν(y i ) = xi , i = def 1, ..., n, ñëåäóåò, ÷ò� V ⊂ W = x1 · · · xn . Äåéñòâèòåëüíî, åñë� á� ãðàí� Vïðèíàäëåæàë� äðóãî� ãðàí� ñèìïëåêñ� K, ñêàæåì, x2 · · · xn+1 , ò� ï� îïðåäåëåíè� ôóíêöè� ν ðàâåíñòâ� ν(y 1 ) = x1 áûë� á� íåâîçìîæíî.
Ïóñò� V 6⊂ K\K 0 . Òîãä� V ÿâëÿåòñ� îáùå� ãðàíü� ðîâí� äâó� n-ìåðíû� ñèìïëåêñîâ, âõîäÿùè� � ðàçáèåíè� π � � ñóìì� χ îí� ó÷èòûâàåòñ� äâàæäû. Ñëåäîâàòåëüíî, ÷èñë� χ ñðàâíèì� ï� ìîäóë� 2 � ÷èñëî� (n − 1)-ìåðíû� ñèìïëåêñî� V = y 1 · · · y n ⊂ W, äë� êîòîðû� ν(y i ) = xi , i = 1, ..., n. Ï� èíäóêòèâíîì� ïðåäïîëîæåíèþ, ïðèìåíåííîì� � (n−1)-ìåðíîì� ñèìïëåêñ� W, ýò� ÷èñë� íå÷åòíî. Ïîýòîì� ÷èñë� χ òàêæ� íå÷åòíî.
Òåîðåì� Ï.4 (Êíàñòåð, Êóðàòîâñêèé, Ìàçóðêåâè÷). Ïóñò� çàìêíóòû� ïîäìíîæåñòâ� C1 , ..., Cn+1 ñèìïëåêñ� K = x1 · · · xn+1 óäîâëåòâîðÿþ� óñëîâè� xj1 · · · xjs ⊆ ∪s r=1 Cjr ∀ 1 ≤ j1 < j2 < ... < js ≤ n + 1. Òîãä� ìíîæåñòâ� C1 , ..., Cn+1 èìåþ� íåïóñòî� ïåðåñå÷åíèå. Äîêàçàòåëüñòâî.
Ðàññìîòðè� ïîñëåäîâàòåëüíîñò� {πk } ïîñòðîåííû� ðàíå� ñèìïëèöèàëüíû� ðàçáèåíè� ñèìïëåêñ� K, äë� êîòîðî� lim δ(πk ) = k→∞0. Îïðåäåëè� îòîáðàæåíè� ν : K → {x1 , ..., xn+1 } ñëåäóþùè� îáðàçîì. Äë� ëþáîã� x ∈ K ïóñò� {xj | λj (x) > 0} = {xj1 , ..., xjs }, j1 < j2 < ... < js . Òîãä� ï� óñëîâè� x ∈ ∪s r=1 Cjr . Ïîëîæè� ν(x) = xjt , ãä� t − ìèíè1 ìàëüíî� ÷èñëî, äë� êîòîðîã� x ∈ ∪t r=1 Cjr . Îòìåòèì, ÷ò� x ∈/ ∪t−r =1 Cjrè, ñëåäîâàòåëüíî, x ∈ Cjt .