А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 9
Текст из файла (страница 9)
5.1. Âîçüìå� äâ� ïðÿìû� lj1 � lj2 , ïðîõîäÿùè� ÷åðå� òî÷ê� (p01 , v) � èìåþùè� óãëîâû� êîýôôèöèåíò� kj1 ≥0, kj2 ≤ 0. Ðàññìîòðè� óðàâíåíè� kj1 q ∗ + kj2 (1 − q ∗ ) = 0. (5.2) Îí� èìåå� ðåøåíè� q ∗ , ïðèíàäëåæàùå� îòðåçê� [0,1]. È� (5.2) ñëåäóåò, ÷ò� óãëîâî� êîýôôèöèåí� ïðÿìî� lj1 (p1 )q ∗ + lj2 (p1 )(1 − q ∗ ) ðàâå� íóëþ.
Ñìåøàííà� ñòðàòåãè� âòîðîã� ⎧ èãðîê� ∗j = j1 , q ,0 0 ∗q : qj = 1 − q , j = j2 ,⎩0,j = 6 j1 , j2 , îïòèìàëüíà, ïîñêîëüê� ïð� âñå� p1 ∈ [0, 1] A(p, q 0 ) = lj1 (p1 )q ∗ + lj2 (p1 )(1 − q ∗ ) = v. á) p0 1 = 0. � ýòî� ñëó÷à� ÷èñòà� ñòðàòåãè� 2 ïåðâîã� èãðîê� ÿâëÿåòñ� îïòèìàëüíîé. Ïîêàæåì, ÷ò� � âòîðîã� èãðîê� òàêæ� èìååòñ� ÷èñòà� îïòèìàëüíà� ñòðàòåãèÿ. Äåéñòâèòåëüíî, íàéäåòñ� ïðÿìà� lj1 , ïðîõîäÿùà� ÷åðå� òî÷ê� (0, v) � èìåþùà� óãëîâî� êîýôôèöèåí� kj1 ≤ 0.
Âûáèðà� ÷èñòó� ñòðàòåãè� j1 , âòîðî� èãðî� í� ïîçâîëè� ïåðâîì� âûèãðàò� áîëüøå, ÷å� v, ïîñêîëüê� A(p, j1 ) = lj1 (p1 ) ≤ v ïð� âñå� p1 ∈ [0, 1]. Èòàê, ìàòðèö� èãð� èìåå� ñåäëîâó� òî÷ê� (2, j1 ). â) p01 = 1. � ýòî� ñëó÷àå, àíàëîãè÷íî� á), ìàòðèö� èãð� òàêæ� èìåå� ñåäëîâó� òî÷êó. −1 −2 3 Ïðèìå� 5.2. Ðåøè� èãð� � ìàòðèöå� A = .
2 4 1 Ïîñòðîè� òð� ïðÿìû� (ðèñ. 5.2) l1 (p1 ) = (−1)p1 + 2(1 − p1 ) = 2 − 3p1 ,l2 (p1 ) = (−2)p1 + 4(1 − p1 ) = 4 − 6p1 ,l3 (p1 ) = 3p1 + 1(1 − p1 ) = 1 + 2p1 ,íàéäåì, ÷ò� ìàêñèìó� íèæíå� îãèáàþùå� äîñòèãàåòñ� � p0 1 = 1/5 − òî÷ê� ïåðåñå÷åíè� ïðÿìû� l1 � l3 . 41ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�4 � J2 v 1 0 � l2Jl3 JJZJZJZ Z JZJZJ� ZJZl1 0 1 1p1 = 5Jp1 Ðèñ.
5.2 Çíà÷åíè� èãð� v = l1 (p01 ) = 7/5 � p0 = (1/5, 4/5). Çäåñ� j1 = 3, k3 = 2, j2 = 1, k1 = −3. È� óðàâíåíè� 2q ∗ + (−3)(1 − q ∗ ) = 0 íàõîäè� q ∗ = 3/5. Îòñþä� q 0 = (2/5, 0, 3/5) − îïòèìàëüíà� ñòðàòåãè� âòîðîã� èãðîêà. Ñäåëàéò� ïðîâåðê� óñëîâè� (∗) òåîðåì� 4.1 � äë� íàéäåííîã� ðåøåíè� (p0 , q 0 , v). Óïðàæíåíè� 5.3. Íàéäèò� âñ� îïòèìàëüíû� ñòðàòåãè� èãðîêî� � èãð� 3 1 0� ìàòðèöå� A = . 0 1 3 Òåïåð� ðàññìîòðè� èãð� � m × 2-ìàòðèöå� A.
Ñìåøàííà� ñòðàòåãè� q = (q1 , 1 − q1 ) âòîðîã� èãðîê� îïðåäåëÿåòñ� âåëè÷èíî� q1 ∈ [0, 1]. Çíà÷åíè� èãðû, ñîãëàñí� ñëåäñòâè� òåîðåì� 4.2 0 , ïðåäñòàâèì� � âèä� v = min max A(i, q) = min max [ai1 q1 + ai2 (1 − q1 )]. q∈Q 1≤i≤m 0≤q1 ≤1 1≤i≤m Ïîýòîì� íåîáõîäèì� ïîñòðîèò� âåðõíþ� îãèáàþùó� max li (q1 ) ñåìåé1≤i≤m ñòâ� ïðÿìû� li (q1 ) = ai1 q1 +ai2 (1−q1 ), i = 1, ..., m, � íàéò� í� îòðåçê� [0,1] òî÷ê� q10 å� ìèíèìóìà.
Îí� áóäå� ñîîòâåòñòâîâàò� îïòèìàëüíî� ñìåøàííî� ñòðàòåãè� âòîðîã� èãðîêà. Îïòèìàëüíà� ñòðàòåãè� ïåðâîã� èãðîê� ñòðîèòñ� � èñïîëüçîâàíèå� óðàâíåíèÿ, àíàëîãè÷íîã� (5.2). III. Ñâåäåíè� ðåøåíè� ìàòðè÷íî� èãð� � ïàð� äâîéñòâåííû� çàäà� ëèíåéíîã� ïðîãðàììèðîâàíèÿ. Ñâåäåíè� ðåøåíè� ìàòðè÷íî� èãð� � çàäà÷à� ëèíåéíîã� ïðîãðàììèðîâàíè� − íàèáîëå� ýôôåêòèâíû� ïðèåì, ïîçâîëÿþùè� èñïîëüçîâàò� àëãîðèò� ñèìïëåêñ-ìåòîäà.
42 5. Ìåòîä� ðåøåíè� ìàòðè÷íû� èã�Áå� ïîòåð� îáùíîñò� áóäå� ïðåäïîëàãàòü, ÷ò� çíà÷åíè� ìàòðè÷íî� èãð� v ïîëîæèòåëüíî. Ñîãëàñí� ñëåäñòâè� òåîðåì� 4.2 0 , îí� ïðåäñòàâèì� � âèä� mPv = max min A(p, j) = max min pi aij . p∈P 1≤j≤np∈P 1≤j≤n i=1 Ââåäå� âñïîìîãàòåëüíó� ïåðåìåííó� u � çàïèøå� çàäà÷� íàõîæäåíè� ìàêñèìèí� êà� çàäà÷� ëèíåéíîã� ïðîãðàììèðîâàíè� v = max u, ãä� (u,p)∈BB = {(u, p) | mPpi aij ≥ u, j = 1, ..., n, i=1 mPpi = 1, pi ≥ 0, i = 1, ..., m}. i=1 Äåéñòâèòåëüíî, ïð� ôèêñèðîâàííî� p ∈ P ìàêñèìàëüíî� çíà÷åíè� u ïð� îãðàíè÷åíèÿ� (u, p) ∈ B ðàâí� min A(p, j). 1≤j≤n Ïîñêîëüê� v > 0, ìîæí� ñ÷èòàòü, ÷ò� u ïðèíèìàå� ïîëîæèòåëüíû� çíà÷åíèÿ.
Ñäåëàå� çàìåí� ïåðåìåííû� zi = pi /u, z = (z1 , ..., zm ). Òîãäà, ó÷èòûâà� îãðàíè÷åíè� (u, p) ∈ B, ïîëó÷è� mXzi = 1/u, i=1 mXaij zi ≥ 1, j = 1, ..., n, zi ≥ 0, i = 1, ..., m. i=1 Îòñþä� 1 v = max u = � , m(u,p)∈B 0zi i=1 ãä� z − îïòèìàëüíî� ðåøåíè� çàäà÷� ëèíåéíîã� ïðîãðàììèðîâàíè� 0 mXzi → min i=1 mXaij zi ≥ 1, j = 1, ..., n, zi ≥ 0, i = 1, ..., m.
(I) i=1 Ï� z 0 íàõîäè� çíà÷åíè� èãð� � îïòèìàëüíó� ñìåøàííó� ñòðàòåãè� ïåðmPâîã� èãðîêà: v = 1/zi 0 , p0 = vz 0 . i=1 Àíàëîãè÷í� ìîæí� ïîëó÷èòü, ÷ò� 1 v = min max A(i, q) = � , nq∈Q 1≤i≤m wj 0j=1 43ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�ãä� w0 − îïòèìàëüíî� ðåøåíè� çàäà÷� ëèíåéíîã� ïðîãðàììèðîâàíè� nXwj → max j=1 nXaij wj ≤ 1, i = 1, ..., m, wj ≥ 0, j = 1, ..., n.
(II) j=1 Çäåñ� q 0 = vw0 − îïòèìàëüíà� ñìåøàííà� ñòðàòåãè� âòîðîã� èãðîêà. Çàäà÷� (I) � (II) äâîéñòâåíí� îäí� ï� îòíîøåíè� � äðóãîé. Îòìåòè� ñâîéñòâ� äîïîëíÿþùå� íåæåñòêîñò� äë� îïòèìàëüíû� ðåøåíè� z 0 � w0 çàäà� (I) � (II) : nP1) zi 0 > 0 ⇒ aij wj 0 = 1; 2) wj 0 > 0 ⇒ j=1 mPaij zi 0 = 1.i=1 Îí� íåïîñðåäñòâåíí� âûòåêàå� è� óòâåðæäåíè� òåîðåì� 4.3 � ïîñë� çàìåí� ïåðåìåííû� p0 = vz 0 , q 0 = vw0 . 0 3 4 Ïðèìå� 5.3. Ðåøèò� èãð� � ìàòðèöå� A = .
Îòìåòèì, ÷ò� 2 1 −3 ñòðàòåãè� p = (1/2, 1/2) îáåñïå÷èâàå� ïåðâîì� èãðîê� ïîëîæèòåëüíû� âûèãðûø. Ïîýòîì� v > 0. Âûïèøå� çàäà÷� ëèíåéíîã� ïðîãðàììèðîâàíè� z1 + z2 → min 2z2 ≥ 1, 3z1 + z2 ≥ 1, 4z1 − 3z2 ≥ 1, (I) z1 , z2 ≥ 0; w1 + w2 + w3 → max 3w2 + 4w3 ≤ 1, 2w1 + w2 − 3w3 ≤ 1, (II) w1 , w2 , w3 ≥ 0. Èñïîëüçó� ãðàôè÷åñêè� ïîñòðîåíè� í� ïëîñêîñòè, íåòðóäí� íàéòè, ÷ò� z 0 = (5/8, 1/2) − îïòèìàëüíî� ðåøåíè� çàäà÷� (I). Îòñþä� v = 1/(z10 + z20 ) = 8/9,p 0 = vz 0 = (5/9, 4/9).
44 5. Ìåòîä� ðåøåíè� ìàòðè÷íû� èã�Íàéäå� îïòèìàëüíî� ðåøåíè� w0 çàäà÷� (II). Ïîñêîëüê� z10 , z20 > 0 �3z10 + z20 > 1, ï� ñâîéñòâ� äîïîëíÿþùå� íåæåñòêîñò�3w20 + 4w30 = 1, 2w10 + w20 − 3w30 = 1, w20 = 0.Ïîýòîì� w0 = (7/8, 0, 1/4), q 0 = vw0 = (7/9, 0, 2/9).IV. Íåîáõîäèìû� óñëîâè� äë� êðàéíè� îïòèìàëüíû� ñìåøàííû� ñòðàòåãèé.
Çäåñ� ðàññìàòðèâàåòñ� êîìáèíàòîðíîã� òèï� àëãîðèò� ðåøåíè� èãðû, îñíîâàííû� í� ïåðåáîð� ïîäìàòðè� ìàòðèö� A. Îïðåäåëåíèå. Ïóñò� Z − âûïóêëî� ìíîæåñòâ� åâêëèäîâ� ïðîñòðàíñòâà. Òî÷ê� z 0 ∈ Z íàçûâàåòñ� êðàéíå� òî÷êî� ìíîæåñòâ� Z, åñë� í� ñóùåñòâóå� òàêè� òî÷å� z � =6 z 0� ∈ Z � òàêîã� ÷èñë� 0 < λ < 1, ÷ò� 0� 00z = λz + (1 − λ)z .
Äðóãèì� ñëîâàìè, êðàéíÿ� òî÷ê� âûïóêëîã� ìíîæåñòâ� Z í� ÿâëÿåòñ� âíóòðåííå� òî÷êî� íèêàêîã� îòðåçêà, ñîåäèíÿþùåã� äâ� òî÷ê� ýòîã� ìíîæåñòâà. Íåòðóäí� âèäåòü, ÷ò� êðàéíÿ� òî÷ê� í� ìîæå� áûò� âíóòðåííå� òî÷êî� ìíîæåñòâ� Z .
Îäíàê� í� âñÿêà� ãðàíè÷íà� òî÷ê� ìíîæåñòâ� Z ÿâëÿåòñ� êðàéíå� òî÷êî� ýòîã� ìíîæåñòâà. Íàïðèìåð, � êâàäðàò� êðàéíèì� òî÷êàì� ÿâëÿþòñ� òîëüê� åã� âåðøèíû. Óïðàæíåíè� 5.4. Ïóñò� Z − âûïóêëû� êîìïàê� åâêëèäîâ� ïðîñòðàíñòâ� � z 0 ∈ Argmax |z|2 . Äîêàæèòå, ÷ò� z 0 − êðàéíÿ� òî÷ê� ìíîæåñòâ� z∈Z Z. Óïðàæíåíè� 5.5. Ïóñò� h(z) − ëèíåéíà� ôóíêöèÿ, îïðåäåëåííà� í� âûïóêëî� êîìïàêò� Z åâêëèäîâ� ïðîñòðàíñòâà. Äîêàæèòå, ÷ò� h(z) äîñòèãàå� ìàêñèìóì� � íåêîòîðî� êðàéíå� òî÷ê� ìíîæåñòâ� Z.
Åñë� ìíîæåñòâ� Z − ìíîãîãðàííèê, ò� åã� êðàéíè� òî÷ê� íàçûâàþòñ� âåðøèíàìè. Âåðíåìñ� � èãð� � ìàòðèöå� A � ðàññìîòðè� ìíîæåñòâ� îïòèìàëüíû� ñìåøàííû� ñòðàòåãè� ïåðâîã� èãðîê� mPP 0 = {p0 ∈ P |p0i aij ≥ v, j = 1, ..., n},i=1ãä� v − çíà÷åíè� ìàòðè÷íî� èãðû. Íåòðóäí� âèäåòü, ÷ò� P 0 − ìíîãîãðàííè� åâêëèäîâ� ïðîñòðàíñòâà. Îïðåäåëåíèå. Êðàéíå� îïòèìàëüíî� ñìåøàííî� ñòðàòåãèå� ïåðâîã� èãðîê� áóäå� íàçûâàò� âåðøèí� ìíîãîãðàííèê� P 0 . 45 ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�Ìíîæåñòâ� îïòèìàëüíû� ñìåøàííû� ñòðàòåãè� âòîðîã� èãðîê�nPQ0 = {q 0 ∈ Q | aij qj 0 ≤ v, i = 1, ..., m} j=1 òàêæ� ÿâëÿåòñ� ìíîãîãðàííèêî� � åã� âåðøèí� − êðàéíè� îïòèìàëüíû� ñìåøàííû� ñòðàòåãèè.
Òåîðåì� 5.2. Ïóñò� � èãð� � ìàòðèöå� A = (aij )m×n çíà÷åíè� v 6= 0. Òîãä� äë� ëþáî� ïàð� p0 , q 0 êðàéíè� îïòèìàëüíû� ñìåøàííû� ñòðàòåãè� èãðîêî� íàéäåòñ� òàêà� íåâûðîæäåííà� ïîäìàòðèö� A = (ail jt )k×k ìàòðèö� A, ÷ò� âûïîëíåí� óñëîâè� kXp 0 il ail jt kX= v, t = 1, ..., k, l=1 kXp 0 il = 1, (5.3) qj0 t = 1. (5.4) l=1 ail jt qj0 t kX= v, l = 1, ..., k, t=1 t=1 Äîêàçàòåëüñòâî. Îïðåäåëè� ñëåäóþùè� ìíîæåñòâ� ÷èñòû� ñòðàòåãè� èãðîêîâ: nPI1 = {i | p0 i > 0}, I2 = {i | aij qj 0 = v}, J1 = {j | qj 0 > 0}, J2 = {j | j=1 mPp0 i aij = v}.
i=1 È� ñâîéñòâ� äîïîëíÿþùå� íåæåñòêîñò� (òåîðåì� 4.3 0 ) ñëåäóåò, ÷ò� I1 ⊂ I2 , J1 ⊂ J2 . Áå� ïîòåð� îáùíîñò� áóäå� ñ÷èòàòü, ÷ò� I1 = {1, ..., r}, I2 = {1, ..., d}, J1 = {1, ..., s}, J2 = {1, ..., h}, ãä� r ≤ d � s ≤ h. Ýòîã� âñåãä� ìîæí� äîáèòüñ� ïîäõîäÿùå� ïåðåñòàíîâêî� ñòðî� � ñòîëáöî� ìàòðèö� A. Ðàññìîòðè� ïîäìàòðèö� à = (aij )d×h ìàòðèö� A. Äîêàæåì, ÷ò� ïåðâû� r ñòðî� ìàòðèö� à ëèíåéí� íåçàâèñèìû. Ïðåäïîëîæè� ïðîòèâíîå. Òîãä� íàéäóòñ� òàêè� ÷èñë� αi , i = 1, ..., r, í� âñ� ðàâíû� íóëþ, ÷ò� rXαi aij = 0, j = 1, ..., h. (5.5) i=1 Ïîêàæåì, ÷ò� ïð� ýòî� rXαi = 0. i=1 46(5.6) 5. Ìåòîä� ðåøåíè� ìàòðè÷íû� èã�Äåéñòâèòåëüíî, è� (5.5) � è� îïðåäåëåíè� ìíîæåñòâ� I2 ñëåäóåò, ÷ò� h XrrhrXXXX0 00 = ( αi aij )qj = αi ( aij qj ) = vαi .
j=1 i=1 i=1 j=1 i=1 6 0, îòñþä� ñëåäóå� (5.6). ×òîá� ïðèäò� � ïðîòèâîðå÷èþ, Ïîñêîëüê� v =ðàññìîòðè� íåíóëåâî� âåêòî� α = (α1 , ..., αr , 0, ..., 0) ∈ E m � ïð� ε =6 0 ε 0 îïðåäåëè� âåêòî� p = p + εα. È� (5.6) ñëåäóåò, ÷ò� ñóìì� êîìïîíåí� âåêòîð� pε ðàâí� åäèíèö� � ïð� äîñòàòî÷í� ìàëî� ε ýò� êîìïîíåíò� ìîæí� ñäåëàò� íåîòðèöàòåëüíûìè.
Òàêè� îáðàçîì, ïð� ìàëî� ε âåêòî� pε ÿâëÿåòñ� ñìåøàííî� ñòðàòåãèå� ïåðâîã� èãðîêà. Ïîêàæåì, ÷ò� ïð� äîñòàòî÷í� ìàëî� ε ñòðàòåãè� pε îïòèìàëüíà. Äåéñòâèòåëüíî, èñïîëüçó� (5.5) � îïðåäåëåíè� ìíîæåñòâ� J2 , ïð� ìàëî� ε ïîëó÷è� (mmrX� � = v, j=1,...,h,A(p ε , j) = p εi aij = p 0 i aij + εαi aij > v, � > h.
i=1 i=1 i=1 Ñëåäîâàòåëüíî, ñìåøàííà� ñòðàòåãè� pε ïð� ìàëû� ε îïòèìàëüíà. Íàêîíåö, p0 = (pε + p−ε )/2, ÷ò� ïðîòèâîðå÷è� îïðåäåëåíè� ñòðàòåãè� p0 . Àíàëîãè÷í� äîêàçûâàåòñÿ, ÷ò� ïåðâû� s ñòîëáöî� ìàòðèö� à ëèíåéí� íåçàâèñèìû. Îáîçíà÷è� ÷åðå� k ðàí� ìàòðèö� Ã. È� äîêàçàííîã� âûòåêàåò, ÷ò� k ≥ max[r, s]. Áå� ïîòåð� îáùíîñò� ìîæí� ñ÷èòàò� áàçèñíûì� ïåðâû� k ñòðî� � ïåðâû� k ñòîëáöî� ìàòðèö� Ã. Í� è� ïåðåñå÷åíè� ñòîè� íåâûðîæäåííà� ïîäìàòðèö� A = (aij )k×k . Äë� ýòî� ïîäìàòðèö� ñïðàâåäëèâ� ðàâåíñòâ� kXp0 i aij = v, j = 1, ..., k, i=1 kXkXp0 i = 1, i=1 aij qj 0 = v, i = 1, ..., k, j=1 kXqj 0 = 1, j=1 êîòîðû� ïðåäñòàâëÿþ� ñîáî� ñèñòåì� (5.3) � (5.4), åñë� âåðíóòüñ� � èñõîäíî� íóìåðàöè� ñòðî� � ñòîëáöîâ. Óïðàæíåíè� 5.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
