Введение в теорию игр (сторонняя методичка) (Введение в теорию игр (сторонняя методичка).PDF), страница 8

Ñâåäåíèå ðåøåíèÿ ìàòðè÷íîé èãðû ê ïàðå äâîéñòâåííûõ çàäà÷ëèíåéíîãî ïðîãðàììèðîâàíèÿ.Ñâåäåíèå ðåøåíèÿ ìàòðè÷íîé èãðû ê çàäà÷àì ëèíåéíîãî ïðîãðàììèðîâàíèÿ − íàèáîëåå ýôôåêòèâíûé ïðèåì, ïîçâîëÿþùèé èñïîëüçîâàòüàëãîðèòì ñèìïëåêñ-ìåòîäà.42Ÿ 5. Ìåòîäû ðåøåíèÿ ìàòðè÷íûõ èãðÁåç ïîòåðè îáùíîñòè áóäåì ïðåäïîëàãàòü, ÷òî çíà÷åíèå ìàòðè÷íîéèãðû v ïîëîæèòåëüíî. Ñîãëàñíî ñëåäñòâèþ òåîðåìû 4.2 0 , îíî ïðåäñòàâèìî â âèäåmPv = max min A(p, j) = max minpi 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=1mPpi = 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=1mXaij zi ≥ 1, j = 1, ..., n, zi ≥ 0, i = 1, ..., m.i=1Îòñþäà1,v = max u = Pm(u,p)∈B0zii=1ãäå z − îïòèìàëüíîå ðåøåíèå çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ0mXzi → mini=1mXaij zi ≥ 1, j = 1, ..., n, zi ≥ 0, i = 1, ..., m.(I)i=1Ïî z 0 íàõîäèì çíà÷åíèå èãðû è îïòèìàëüíóþ ñìåøàííóþ ñòðàòåãèþ ïåðmPâîãî èãðîêà: v = 1/zi0 , p0 = vz 0 .i=1Àíàëîãè÷íî ìîæíî ïîëó÷èòü, ÷òî1v = min max A(i, q) = P,nq∈Q 1≤i≤mwj0j=143ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛãäå w0 − îïòèìàëüíîå ðåøåíèå çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿnXwj → maxj=1nXaij wj ≤ 1, i = 1, ..., m, wj ≥ 0, j = 1, ..., n.(II)j=1Çäåñü q 0 = vw0 − îïòèìàëüíàÿ ñìåøàííàÿ ñòðàòåãèÿ âòîðîãî èãðîêà.Çàäà÷è (I) è (II) äâîéñòâåííû îäíà ïî îòíîøåíèþ ê äðóãîé.Îòìåòèì ñâîéñòâî äîïîëíÿþùåé íåæåñòêîñòè äëÿ îïòèìàëüíûõ ðåøåíèé z 0 è w0 çàäà÷ (I) è (II) :nP1) zi0 > 0 ⇒aij wj0 = 1;2) wj0 > 0 ⇒j=1mPaij zi0 = 1.i=1Îíî íåïîñðåäñòâåííî âûòåêàåò èç óòâåðæäåíèÿ òåîðåìû 4.3 0 ïîñëå çàìåíû ïåðåìåííûõ p0 = vz 0 , q 0 = vw0 .0 3 4Ïðèìåð 5.3.

Ðåøèòü èãðó ñ ìàòðèöåé A =. Îòìåòèì, ÷òî2 1 −3ñòðàòåãèÿ p = (1/2, 1/2) îáåñïå÷èâàåò ïåðâîìó èãðîêó ïîëîæèòåëüíûéâûèãðûø. Ïîýòîìó v > 0. Âûïèøåì çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿz1 + z2 → min2z2 ≥ 1, 3z1 + z2 ≥ 1, 4z1 − 3z2 ≥ 1,(I)z1 , z2 ≥ 0;w1 + w2 + w3 → max3w2 + 4w3 ≤ 1, 2w1 + w2 − 3w3 ≤ 1,(II)w1 , w2 , w3 ≥ 0.Èñïîëüçóÿ ãðàôè÷åñêèå ïîñòðîåíèÿ íà ïëîñêîñòè, íåòðóäíî íàéòè, ÷òîz 0 = (5/8, 1/2) − îïòèìàëüíîå ðåøåíèå çàäà÷è (I).

Îòñþäàv = 1/(z10 + z20 ) = 8/9,p0 = 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 0 6= z 00 ∈ Z è òàêîãî ÷èñëà 0 < λ < 1, ÷òîz 0 = λz 0 + (1 − λ)z 00 .Äðóãèìè ñëîâàìè, êðàéíÿÿ òî÷êà âûïóêëîãî ìíîæåñòâà Z íå ÿâëÿåòñÿ âíóòðåííåé òî÷êîé íèêàêîãî îòðåçêà, ñîåäèíÿþùåãî äâå òî÷êè ýòîãîìíîæåñòâà. Íåòðóäíî âèäåòü, ÷òî êðàéíÿÿ òî÷êà íå ìîæåò áûòü âíóòðåííåé òî÷êîé ìíîæåñòâà Z . Îäíàêî íå âñÿêàÿ ãðàíè÷íàÿ òî÷êà ìíîæåñòâà Z ÿâëÿåòñÿ êðàéíåé òî÷êîé ýòîãî ìíîæåñòâà. Íàïðèìåð, ó êâàäðàòàêðàéíèìè òî÷êàìè ÿâëÿþòñÿ òîëüêî åãî âåðøèíû.Óïðàæíåíèå 5.4. Ïóñòü Z − âûïóêëûé êîìïàêò åâêëèäîâà ïðîñòðàíñòâà è z 0 ∈Argmax |z|2 .

Äîêàæèòå, ÷òî z 0 − êðàéíÿÿ òî÷êà ìíîæåñòâàz∈ZZ.Óïðàæíåíèå 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 qj0 ≤ v, i = 1, ..., m}j=1òàêæå ÿâëÿåòñÿ ìíîãîãðàííèêîì è åãî âåðøèíû − êðàéíèå îïòèìàëüíûåñìåøàííûå ñòðàòåãèè.Òåîðåìà 5.2. Ïóñòü â èãðå ñ ìàòðèöåé A = (aij )m×n çíà÷åíèå v 6= 0.Òîãäà äëÿ ëþáîé ïàðû p0 , q 0 êðàéíèõ îïòèìàëüíûõ ñìåøàííûõ ñòðàòåãèé èãðîêîâ íàéäåòñÿ òàêàÿ íåâûðîæäåííàÿ ïîäìàòðèöà A = (ail jt )k×kìàòðèöû A, ÷òî âûïîëíåíû óñëîâèÿkXp0il ail jtkX= v, t = 1, ..., k,l=1kXp0il = 1,(5.3)qj0t = 1.(5.4)l=1ail jt qj0tkX= v, l = 1, ..., k,t=1t=1Äîêàçàòåëüñòâî. Îïðåäåëèì ñëåäóþùèå ìíîæåñòâà ÷èñòûõ ñòðàòåãèé èãðîêîâ:nPI1 = {i | p0i > 0}, I2 = {i |aij qj0 = v},J1 = {j | qj0 > 0}, J2 = {j |j=1mPp0i 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=146(5.6)Ÿ 5.

Ìåòîäû ðåøåíèÿ ìàòðè÷íûõ èãðÄåéñòâèòåëüíî, èç (5.5) è èç îïðåäåëåíèÿ ìíîæåñòâà I2 ñëåäóåò, ÷òîh XrrhrXXXX000=(αi aij )qj =αi (aij qj ) = vαi .j=1 i=1i=1j=1i=1Ïîñêîëüêó v 6= 0, îòñþäà ñëåäóåò (5.6). ×òîáû ïðèäòè ê ïðîòèâîðå÷èþ,ðàññìîòðèì íåíóëåâîé âåêòîð α = (α1 , ..., αr , 0, ..., 0) ∈ E m è ïðè ε 6= 0îïðåäåëèì âåêòîð pε = p0 + εα. Èç (5.6) ñëåäóåò, ÷òî ñóììà êîìïîíåíòâåêòîðà pε ðàâíà åäèíèöå è ïðè äîñòàòî÷íî ìàëîì ε ýòè êîìïîíåíòûìîæíî ñäåëàòü íåîòðèöàòåëüíûìè. Òàêèì îáðàçîì, ïðè ìàëîì ε âåêòîðpε ÿâëÿåòñÿ ñìåøàííîé ñòðàòåãèåé ïåðâîãî èãðîêà.

Ïîêàæåì, ÷òî ïðèäîñòàòî÷íî ìàëîì ε ñòðàòåãèÿ pε îïòèìàëüíà. Äåéñòâèòåëüíî, èñïîëüçóÿ(5.5) è îïðåäåëåíèå ìíîæåñòâà J2 , ïðè ìàëîì ε ïîëó÷èì(mmrXXX= v, j=1,...,h,A(pε , j) =pεi aij =p0i aij + εαi aij> v, j > h.i=1i=1i=1Ñëåäîâàòåëüíî, ñìåøàííàÿ ñòðàòåãèÿ pε ïðè ìàëûõ ε îïòèìàëüíà. Íàêîíåö, p0 = (pε + p−ε )/2, ÷òî ïðîòèâîðå÷èò îïðåäåëåíèþ ñòðàòåãèè p0 .Àíàëîãè÷íî äîêàçûâàåòñÿ, ÷òî ïåðâûå s ñòîëáöîâ ìàòðèöû à ëèíåéíîíåçàâèñèìû. Îáîçíà÷èì ÷åðåç k ðàíã ìàòðèöû Ã.

Èç äîêàçàííîãî âûòåêàåò, ÷òî k ≥ max[r, s]. Áåç ïîòåðè îáùíîñòè ìîæíî ñ÷èòàòü áàçèñíûìèïåðâûå k ñòðîê è ïåðâûå k ñòîëáöîâ ìàòðèöû Ã. Íà èõ ïåðåñå÷åíèè ñòîèòíåâûðîæäåííàÿ ïîäìàòðèöà A = (aij )k×k . Äëÿ ýòîé ïîäìàòðèöû ñïðàâåäëèâû ðàâåíñòâàkXp0i aij = v, j = 1, ..., k,i=1kXkXp0i = 1,i=1aij qj0= v, i = 1, ..., k,kXqj0 = 1,j=1j=1êîòîðûå ïðåäñòàâëÿþò ñîáîé ñèñòåìû (5.3) è (5.4), åñëè âåðíóòüñÿ ê èñõîäíîé íóìåðàöèè ñòðîê è ñòîëáöîâ.Óïðàæíåíèå 5.6. Äîêàæèòå, ÷òî óñëîâèÿ (5.3) è (5.4) äîñòàòî÷íû äëÿòîãî, ÷òîáû îïòèìàëüíûå ñìåøàííûå ñòðàòåãèè p0 è q 0 áûëè êðàéíèìèîïòèìàëüíûìè.47ÃËÀÂÀ I.

ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛÏîêàæåì, ÷òî ñèñòåìà k + 1 ëèíåéíûõ óðàâíåíèé (5.3) îòíîñèòåëüíîk + 1 íåèçâåñòíûõ p0il , l = 1, ..., k, v ëèáî íå èìååò ðåøåíèÿ, ëèáî èìååòåäèíñòâåííîå ðåøåíèå. Äåéñòâèòåëüíî, ðàñøèðåííàÿ ìàòðèöà ñèñòåìû(5.3) èìååò âèä0ai1 j1 · · · aik j1 −1 · · · · · · · · · −10.ai1 j · · · ai j −10kk k1 ···101Íåòðóäíî âèäåòü, ÷òî åå ðàíã ðàâåí k + 1.

Åñëè ñèñòåìà (5.3) èìååò ðåøåíèå, òî ïî òåîðåìå Êðåíåêåðà-Êàïåëëè ðàíã ìàòðèöû ñèñòåìû òàêæåðàâåí k + 1 è îíà − íåâûðîæäåííàÿ. Îòñþäà ñëåäóåò åäèíñòâåííîñòüðåøåíèÿ ñèñòåìû (5.3).Âûïèøåì â ïîñëåäíåì ñëó÷àå ðåøåíèÿ ñèñòåì (5.3) è (5.4) â ÿâíîìâèäå. Äëÿ ýòîãî ââåäåì âåêòîðûp = (p0il , l = 1, ..., k), q = (qj0t , t = 1, ..., k), e = (1, ..., 1) ∈ E kè çàïèøåì ñèñòåìó (5.3) â ìàòðè÷íûõ îáîçíà÷åíèÿõpA = ve,p, e = 1.Óìíîæàÿ ïåðâîå ðàâåíñòâî ñïðàâà íà ìàòðèöó (A)−1 , âûðàçèì âåêòîð p−1÷åðåç v : p = ve(A) .

Ïîäñòàâëÿÿ ýòî âûðàæåíèå â óðàâíåíèåp, e = 1, ïîëó÷èìp= e(A)−11, v = .e(A)−1 , ee(A)−1 , eÀíàëîãè÷íî èç ñèñòåìû (5.4) íàõîäèòñÿq=(A)−1 e.(A)−1 e, eÓïðàæíåíèå 5.7. Ïðèâåäèòå ïðèìåð 2 × 2-ìàòðèöû A, äëÿ êîòîðîéñèñòåìà (5.3) íå èìååò ðåøåíèÿ.Ðàññìîòðèì òåïåðü àëãîðèòì ðåøåíèÿ ìàòðè÷íîé èãðû. Ïåðåáèðàåìâñå íåâûðîæäåííûå k × k -ïîäìàòðèöû A ìàòðèöû A, íà÷èíàÿ ñ k = 2.48Ÿ 5. Ìåòîäû ðåøåíèÿ ìàòðè÷íûõ èãðÄëÿ êàæäîé ïîäìàòðèöû A ðåøàåì ñèñòåìû óðàâíåíèé (5.3) è (5.4). Åñëèðåøåíèÿ íå ñóùåñòâóåò èëè íåêîòîðûå êîìïîíåíòûp0il , l = 1, ..., k, qj0t , t = 1, ..., kîòðèöàòåëüíû, òî ïåðåõîäèì ê ñëåäóþùåé ïîäìàòðèöå A.

Ïóñòü óêàçàííûå êîìïîíåíòû ðåøåíèé íåîòðèöàòåëüíû. Òîãäà îïðåäåëèì ñìåøàííûåñòðàòåãèè((0p,i=i,qj0t , j = jt ,lilp0 : p0i =q 0 : qj0 =0,i 6= il ;0,j 6= jt .Òåïåðü äëÿ òðîéêè (p0 , q 0 , v) íåîáõîäèìî ïðîâåðèòü óñëîâèå (∗) òåîðåìû 4.1 0 . Åñëè îíî âûïîëíåíî, òî èñêîìîå ðåøåíèå (p0 , q 0 , v) íàéäåíî. Âïðîòèâíîì ñëó÷àå ïåðåõîäèì ê ñëåäóþùåé ïîäìàòðèöå A.Ïðèìåð 5.4. Ðàññìîòðèì ìàòðèöó âèäà1 1 1 01 0 0 1A=0 1 0 00 0 1 100.11Çäåñü íåò ñëàáî äîìèíèðóåìûõ ñòðîê (äàæå íèêàêèìè âûïóêëûìè êîìáèíàöèÿìè − äîêàæèòå!) è ñëàáî äîìèíèðóþùèõ ñòîëáöîâ . Åñëè ïðèìåíèòü óêàçàííûé âûøå àëãîðèòì, òî ïîäìàòðèöà a11 a151 0A==a41 a450 1äàñò ðåøåíèå â ñìåøàííûõ ñòðàòåãèÿõp0 = (1/2, 0, 0, 1/2), q 0 = (1/2, 0, 0, 0, 1/2), v = 1/2.V.