Jo lielāks ir spēles izmaksu matricas lielums, jo sarežģītāka ir analīze. Tāpēc, pirms izlemt kādu matricas spēle Pirmkārt, ir ieteicams izslēgt spēlētāju dominējošās stratēģijas (ja tādas ir), tādējādi samazinot maksājumu matricas dimensiju. Bet pat tad, ja tiek izslēgtas dominējošās stratēģijas, katram spēlētājam joprojām var būt vairāk nekā divas tīras stratēģijas (w, lpp> 2), ja nevar izmantot grafiski analītisko metodi.

Ir izstrādāta salīdzinoši vienkārša metode, kas sastāv no matricas spēles reducēšanas līdz problēmai lineārā programmēšana, ko savukārt var atrisināt ar labi zināmām metodēm (piemēram, simplekso metodi) vai izmantojot neskaitāmus datormodelēšanas rīkus (piemēram, izmantojot moduli “Solution Search” MS Excel).

Kā pirmo reizi parādīja J. fon Neimans, kurš ir ne tikai spēļu teorijas veidotājs, bet arī viens no lineārās programmēšanas teorijas izstrādātājiem, jebkura beigu spēle divu personu nulles summu var attēlot kā lineāru programmēšanas problēmu. Šo metodi var pielietot jebkurām matricas spēlēm, arī vienkāršām, kuru risinājums tika apspriests iepriekšējā punktā.

Lai apsvērtu matricas spēles reducēšanas metodi līdz lineārai programmēšanas problēmai, ir jāiepazīstas ar citu matricas spēļu īpašību, ko sauc afīna noteikums. Optimālas stratēģijas matricu spēlēs A un B, kuru maksājumu matricu elementi ir saistīti ar vienlīdzību

Kur X> 0 un p ir jebkurš reāls skaitlis, tiem ir vienādas līdzsvara situācijas (vai nu tīrā, vai jauktā stratēģijā), un spēļu cenas atbilst šādam nosacījumam: vB = XvA+ r.

Šim noteikumam ir praktiska nozīme, jo daudzi matricas spēļu risināšanas algoritmi ir balstīti uz pieņēmumu, ka visi izmaksas matricas elementi ir pozitīvi, kas, savukārt, garantē pozitīvu spēles cenu. Gadījumā, ja matricā ir nepozitīvi elementi, visiem matricas elementiem var pievienot jebkuru skaitli, kas ir lielāks par matricas negatīvo elementu maksimālo absolūto vērtību.

Mēs pieņemam, ka cena spēlei ar maksājumu matricu Txp pozitīvs (un > 0). Ja tas tā nav, tad saskaņā ar afīna likumu vienmēr ir iespējams izvēlēties tādu skaitli p, lai, to pievienojot visiem izmaksas matricas elementiem, tiktu iegūta matrica ar pozitīviem elementiem un tādējādi nodrošinātu cenas pozitīvu vērtību. no spēles. Šajā gadījumā abu spēlētāju optimālās jauktās stratēģijas nemainās.

No optimālās jauktās stratēģijas definīcijas izriet, ka pirmais spēlētājs, ievērojot savu optimālo jaukto stratēģiju, uzvarēs ne mazāk kā o par jebkuru otrā spēlētāja stratēģiju (ieskaitot tīrās), bet otrais spēlētājs, ievērojot savu optimālo stratēģiju. jaukta stratēģija, zaudēs ne vairāk kā o jebkurai stratēģijai pirmais spēlētājs (ieskaitot tīrās). No tā izriet, ka jauktas stratēģijas X = = (x v x t), y = (y v ..., plkst n) attiecīgi pirmajam un otrajam spēlētājam un spēles cenai o ir jāapmierina attiecības

Sadalīsim visus vienādojumus un nevienādības šajās sistēmās ar un (to var izdarīt, jo ar pieņēmumu o > 0) un ieviesīsim apzīmējumu:

Tad saņemam

Tā kā pirmais spēlētājs cenšas maksimāli palielināt spēles izmaksas, izvēloties vērtības x [y tad apgrieztā vērtība 1/o ir jāsamazina, izvēloties r g Tādējādi pirmās problēmas atrisināšana ir šādu nenegatīvu vērtību atrašana R., 2=1,..., ka pie kura

Tā kā otrais spēlētājs cenšas atrast šādas vērtības y) un tāpēc qy lai spēles izmaksas būtu minimālas, tad otrās problēmas risinājums samazinās līdz šādu nenegatīvu vērtību atrašanai q jy j = 1, ..., p y pie kura

Tādējādi ir iegūtas duālās lineārās programmēšanas (LP) uzdevumi, kurus var atrisināt, piemēram, izmantojot simplekso metodi.

Atrisinot šīs problēmas, mēs iegūstam vērtības p®, i = 1,t q® y j = 1,..., P.

Tad no nosacījuma tiek noteikta spēles cenas o vērtība

Optimālas jauktas stratēģijas, t.i. x® un r/?, iegūst ar formulām

Piemērs 4.7. Apsveriet spēles “Cīņa par tirgiem” variantu. Divi konkurējoši uzņēmumi A un B nolemj finansēt trīs inovatīvus tehniskos projektus. Katrs uzņēmums var ieguldīt 100 dsn. vienības Uzņēmums B cenšas ieņemt tirgu, kurā uzņēmums A tradicionāli ir bijis līderis. Vienādu projektu izstrādes un attīstības gadījumā uzņēmums A strādās ar peļņu, bet uzņēmums B cietīs zaudējumus. Ja investīcijas tiks novirzītas dažādiem projektiem, uzņēmums A cietīs zaudējumus, kas saistīti ar tirgus pārdali, un uzņēmuma B peļņa atbildīs uzņēmuma A zaudējumiem. Jāatrod optimālas stratēģijas uzņēmumiem. Uzņēmuma A peļņa dažādās stratēģiskās situācijās ir parādīta tabulā:

Risinājums iekšā MS Excel

Atrisināsim problēmu, izmantojot programmu MS Excel. Uz galdu MS Excel tiek ieviesti spēles maksājumu matricas elementi un, izmantojot MIN() un MAX() funkcijas, minimālais un maksimālās vērtības attiecīgi pa rindām un kolonnām, tad, izmantojot tās pašas funkcijas, tiek atrasts maximin un minimax (4.2. tabula). Tā kā šīs vērtības nesakrīt, spēlē nav seglu punkta, t.i. to nevar atrisināt ar tīrām stratēģijām. Spēles cenas vērtībai ir jābūt diapazonā (-5; 10).

4.2. tabula

Seglu punkta pārbaude spēlē

Lai izmantotu algoritmu spēles risināšanai, reducējot to līdz lineārai programmēšanas problēmai, mēs izmantojam afīnu likumu. Izmantojot MIN() funkciju, atrodam maksājumu matricas elementu minimālo vērtību (-20). Šī skaitļa modulis ir definēts kā ABS(MHH(...)). Izmantojot afīnu transformāciju ar parametriem X = 1 un p = 20 iegūstam jaunu maksājumu matricu (4.3. tabula).

4.3. tabula

Spēles samazināšana līdz lineārai programmēšanas problēmai

Pa labi no maksājumu matricas ir patvaļīgi norādīti nepieciešamie mainīgie R.(šajā posmā var norādīt jebkuras vērtības). Šūnās zem maksājumu matricas vērtības tiek noteiktas, izmantojot funkciju SUMPRODUCT().

kas tiks izmantoti LI problēmas ierobežojumos. Šīs vērtības ir nejauši atlasītas p t ir norādīti tabulā. 4.3.

Šūnā, kas apzīmēta kā “Mērķa funkcija”, ievadiet formulu SUM(...), kas atbilst mērķa funkcijas izteiksmei.

Šūnā ar nosaukumu “Spēles cena” ievadiet formulu, lai noteiktu spēles cenu, izmantojot mērķa funkcijas vērtību:

Šūnās, kas atzīmētas kā x tas tiek ieviestas formulas, lai apgriezti pārveidotu mainīgos un atrastu nepieciešamos pirmā spēlētāja jauktās stratēģijas elementus x i= u Pj.

Pirmās lineārās programmēšanas problēmas formulēšana: atrodiet vērtību

ES arī nē RU nodrošina minimālu funkciju skaitu YjPi * pip apstākļos ^ a ij p i > 1,

Lineārās programmēšanas problēmas risinājums tiek veikts, izmantojot programmas moduli “Risinājumu meklēšana”. MS Excel(šī moduļa izmantošana jau ir apspriesta 2. nodaļā). Laukā “Iestatīt mērķa šūnu” ir norādīta tās šūnas adrese, kurā ir mērķa funkcijas vērtība; izvēlieties režīmu “Vienāds ar: minimālo vērtību”. Laukā “Šūnu maiņa” ir norādīts vēlamo mainīgo lielumu masīvs r g Noklikšķinot uz pogas “Pievienot” un atlasot masīvu, kas atbilst uzdevuma ierobežojumiem, laukā “Ierobežojumi” tiek iestatīts atbilstošais nosacījums. Noklikšķinot uz pogas “Parametri”, tiek atvērts dialoglodziņš “Risinājuma meklēšanas parametri”, kurā tiek atlasīti parametri “Lineārais modelis” un “Nenegatīvās vērtības”; pārējo parametru vērtības paliek nemainīgas. Pēc loga “Risinājumu meklēšanas opcijas” aizvēršanas (izmantojot LABI) Noklikšķinot uz pogas “Palaist” logā “Meklēt risinājumu”, tiek uzsākts iteratīvs LP problēmas risinājuma meklēšanas process.

Šī procesa beigās tiek parādīts logs “Risinājumu meklēšanas rezultāti”. Ja visi problēmas nosacījumi ir formulēti pareizi, visi dati, formulas un parametri ievadīti pareizi, logā tiks parādīts “Risinājums atrasts. Ir ievēroti visi ierobežojumi un optimāluma nosacījumi. Šajā gadījumā, lai saglabātu risinājumu, jums jānoklikšķina LABI. Aprēķinu rezultāti ir parādīti tabulā. 4.4.

Līdzīgi LP problēma tiek atrisināta arī otrajam spēlētājam (4.5. tabula). Lūdzu, ņemiet vērā, ka iekš šajā gadījumā tehniskajām ērtībām nepieciešamo mainīgo lielumu masīvs ir sakārtots rindā (tā kā otrā spēlētāja stratēģijas atbilst izmaksu matricas kolonnām), un šūnas ar ierobežojumiem ir sakārtotas kolonnā. Problēma tiek atrisināta maksimāli un formulēta šādi: atrodiet vērtības q jt

nodrošina maksimālu funkcionalitāti? es)* max P R I nosacījumi ^ a i) q- q) > 0.

4.4. tabula

LP problēmas risināšanas rezultāti pirmajam spēlētājam

LP problēmas risināšanas rezultāti otrajam spēlētājam

4.5. tabula

Afīna likuma iepriekšējas piemērošanas gadījumā spēles cenas patieso vērtību iegūst, atņemot skaitli p, kas tika izmantots, lai kalibrētu izmaksas matricas elementus. Spēles gala risinājums:

Rezultāti liecina, ka uzņēmuma A optimālā stratēģija ir investīcijām paredzēto līdzekļu sadale proporcijās 29, 60 un 11%, t.i. 29, 60 un 11 dienas. vienības Šajā gadījumā uzņēmums A gūs peļņu ne mazāk 0,5 den. vienības Uzņēmums A saņems minimālo peļņas vērtību (0,5 naudas vienības), ja uzņēmums B ievēros savu optimālo projekta investīciju stratēģiju, proti, 39, 25, 36%, t.i. investēt projektos 39, 25 un 36 den. vienības attiecīgi. Ja uzņēmums B novirzās no šīs stratēģijas (pievērš citu ieguldījumu modeli), uzņēmuma A peļņa palielināsies.

Risinājuma analīze liecina, ka uzņēmumam B šī spēle ir nerentabla (paredzamie zaudējumi ir aptuveni 0,5 naudas vienības). Savukārt, ja uzņēmums B šos zaudējumus uzskata par salīdzinoši nenozīmīgiem salīdzinājumā ar sava mērķa sasniegšanu - ienākšanu tradicionāli uzņēmuma A kontrolētajā tirgū, tad, ievērojot savu optimālo investīciju sadales stratēģiju, uzņēmums B zaudēs ne vairāk kā 0,5 den. vienības Ja uzņēmums A uzvedas neracionāli, tad uzņēmuma B zaudējumi samazināsies.

Tādējādi jebkuru matricas spēli var atrisināt, reducējot spēli līdz divām lineārās programmēšanas problēmām. Tomēr tas prasa lielu aprēķinu apjomu, kas palielinās līdz ar tīro spēlētāju stratēģiju skaitu. Tāpēc, pirmkārt, izmantojot dominējošo stratēģiju izslēgšanas metodi, ja iespējams, ir jāsamazina tīro spēlētāju stratēģiju skaits. Izņēmums vājš dominējošās stratēģijas var novest pie dažu risinājumu zaudēšanas. Ja vien spēcīgi dominējošās stratēģijas, tad spēles risinājumu kopums nemainīsies. Tad visos gadījumos jāpārbauda seglu punkta esamība, t.i. nosacījuma izpildes pārbaude min a- = min ma ha...

Ja tas atbilst, tad spēlētājiem ir tīri optimālas stratēģijas, un risinājums tiek iegūts automātiski. Pretējā gadījumā optimālās stratēģijas tiks sajauktas. Vienkāršām matricas spēlēm, kur vismaz vienam no spēlētājiem ir tikai divas stratēģijas, var izmantot grafiski analītiskā risinājuma metodi, kas aprakstīta sadaļā 4.2. Vairāk izaicinošas spēles ir nepieciešams izmantot metodi spēles reducēšanai līdz lineārai programmēšanas problēmai un atbilstošus rīkus šīs problēmas risināšanai.

Noslēdzot šo sadaļu, mēs atzīmējam, ka izmaksu matricas vienkāršošana, izslēdzot dominējošās stratēģijas, ir svarīga, ja spēle tiek atrisināta manuāli. Ja optimālo stratēģiju atrašanai izmanto datoru, tad pūles un laiks, kas pavadīts, meklējot dominējošās stratēģijas, var tikt izniekoti, jo sākotnējās un vienkāršotās matricas skaitliskā analīze tiek veikta, izmantojot vienu un to pašu algoritmu, un aprēķina laika atšķirība ir nenozīmīga. .

Mēs pārbaudām, vai maksājumu matricai ir seglu punkts. Ja jā, tad mēs rakstām spēles risinājumu tīrās stratēģijās, ja nē, tad turpinām analizēt matricu.

Mēs noņemam dominējošās rindas un kolonnas, ja tādas ir. Viņu vietā spēlētāju optimālajās stratēģijās atbilstošās sastāvdaļas būs vienādas ar nulli.

H. Matricas spēli risinām, izmantojot kādu no labi zināmajām metodēm: lineārās programmēšanas metodes, aptuveno metodi vai grafiski (ja vismaz vienam no spēlētājiem ir tikai divas tīras stratēģijas).

Jebkuru matricas spēli var reducēt uz simetrisku duālās lineārās programmēšanas problēmu pāri, kas nozīmē, ka simpleksa metodi var izmantot, lai atrastu optimālas spēlētāju stratēģijas un spēļu cenas.

Pielāgota risinājuma piemērs.

Piemērs. Atrodiet spēles risinājumu, ko sniedz izmaksu matrica

Vispirms pārbaudīsim, vai matricai ir seglu punkts. Pirmās rindas mazākais elements -3 nav lielākais trešajā kolonnā; otrās rindas mazākais elements -1 nav lielākais elements pirmajā kolonnā; visbeidzot, trešās rindas mazākais elements 2 ir arī lielākais trešajā kolonnā. Līdz ar to matricai ir seglu punkts (3, 3), kurā atrodas elements A zz = 2. Tas nozīmē, ka spēlei ir risinājums tīrās stratēģijās, proti:

- pirmā spēlētāja optimālā stratēģija;

- otrā spēlētāja optimālā stratēģija;

v= 2 - spēles cena.

Piemērs. Atrodiet spēles risinājumu, ko sniedz izmaksu matrica

.

Matricā nav seglu punkta, tāpēc spēlei ir risinājums jauktās stratēģijās.

Pārbaudīsim, vai matricā ir dominējošās rindas un kolonnas. Tā kā visi pirmās rindas elementi nav lielāki par atbilstošajiem trešās rindas elementiem, dominē pirmā rinda un to var dzēst. Varat arī noņemt trešo kolonnu, kas dominē otrajā, kā arī piekto kolonna, kas dominē pirmajās trīs kolonnās. Rezultātā mēs iegūstam matricu

Pievienojot visiem matricas elementiem A", piemēram, skaitlis c = 3, mēs iegūstam matricu

.

kura visi elementi nav negatīvi, bet otrās rindas elementi ir stingri pozitīvi.

Izveidosim simetrisku duālu uzdevumu pāri, lai sākotnējā problēma būtu standarta maksimizācijas problēma, šīs problēmas koeficientu matrica sakrīt ar izmaksu matricu A",· un koeficienti nezināmajiem mērķfunkcijā un nevienādību brīvajos terminos būtu vienādi ar vienu.

Atrisināsim 1. uzdevumu, izmantojot simplekso metodi. Tas tiek sniegts vispārīga uzdevuma veidā. Samazināsim to līdz galvenajam, izmantojot papildu nezināmos x 4 ≥0, x 5 ≥0. Rezultātā mēs iegūstam šādu problēmu.

x j ≥ 0 (j = 1,…,5),

f(X) = x 1 + x 2 + x 3 → tah.

Problēma ir kanoniska un, pielietojot tai simpleksās metodes algoritmu, iegūstam formas simpleksas tabulas

No pamata mainīgo kolonnas un indeksa rindas mēs izrakstām optimālos plānus divu problēmu pārim, proti:

f(X*)= g(Y*)=

No duālo uzdevumu risinājumiem iegūstam spēles cenu un spēlētāju optimālās stratēģijas spēlē ar matricu A":

v" = = ;

=v" = = ;

= v" = =

Matricas spēle A" būs tādas pašas optimālās stratēģijas Un , tāpat kā matricas spēle A", un spēles cena

v"= v"- c = - 3 = .

Un visbeidzot, oriģinālajai spēlei ar matricu A ir optimālas stratēģijas

P*= Un Q*=

un spēles cena v= v"= .

Optimālas stratēģijas R* Un J* mēs ieguvām no optimālajām stratēģijām Un , dzēsto rindu un kolonnu vietā pievienojot nulles.

Spēles risinājuma pareizību var pārbaudīt, izmantojot stratēģijas optimizācijas kritēriju. Lai to izdarītu, atrasto optimālo stratēģiju sastāvdaļas ir jāaizvieto nevienādībās M(P i , Q*) ≤ v≤ M(P*, Q j) R* Un J*, tīro stratēģiju sastāvdaļas R i (i = 1, 2, 3) un J j (j = 1, 2, 3, 4, 5)

un spēles cena v = .

Ņemiet vērā, ka spēles teorijas problēma ir jāsamazina līdz divu LP problēmu pārim tikai tad, ja visi elementi vismaz viena maksājumu matricas rinda stingri pozitīvs . Šajā gadījumā abām problēmām būs optimāli plāni, no kuriem var iegūt spēlētāju optimālās stratēģijas. Pretējā gadījumā sākotnējā uzdevumā mērķa funkcija var izrādīties neierobežota, un duālajā uzdevumā nebūs viena plāna. Tātad, nākamajā piemērā, ja mēs izveidojam duālu problēmu pāri spēlē ar matricu

,

tad 1. uzdevumā mērķa funkcija netiks ierobežota no augšas uz plānu kopas, un 2. uzdevumā plānu nebūs vispār, tomēr, kā redzējām iepriekš, spēle ar matricu A" ir risinājums.

Pirmā spēlētāja (spēlētāja) optimālā jauktā stratēģija A) ir forma

,

otrā spēlētāja optimāla jaukta stratēģija (spēlētājs B) ir šāda forma:

.

Tā kā šī matricas spēle tika vienkāršota, noņemot acīmredzami nerentablas stratēģijas, un tās galīgais risinājums ir šāds:

Spēļu risināšana grafiski.

Grafiskā metode ir piemērojama spēlēm, kurās vismaz vienam spēlētājam ir tikai divas stratēģijas.

1. piemērs.

Spēlei nav seglu punkta. Optimālais risinājums būtu jāmeklē jaukto stratēģiju jomā. Konstruēsim segmentus plaknē, kas atbilst otrā spēlētāja stratēģijām.

Spēlētāja A izmaksas apakšējā robeža ir pārtrauktā līnija IN 3 HF 4 ,. Stratēģijas IN 3 , Un IN 4 ir spēlētāja B aktīvās stratēģijas. To krustošanās punkts UZ nosaka spēlētāju optimālās stratēģijas un spēles cenu. Otrajam spēlētājam nav izdevīgi izmantot stratēģijas IN 1 Un IN 2 , plkst 1 = y 2 = 0. Spēles risinājums tiek reducēts līdz spēles risinājumam ar (2x2) matricu.

x 1 = 2/5, X 2 = 3/5; y 3 = 3/5, plkst 4 = 2/5; v = 11/5.

Atbilde.

X (2/5, 3/5) un Y (0, 0,3/5, 2/5), spēles cena ir v = 11/5.

ja pirmais spēlētājs ar varbūtību 2/5 izmantos pirmo stratēģiju un ar varbūtību 3/5 otro, tad ar pietiekamu lielos daudzumos spēlēs ar šo matricu, viņa laimests vidēji būs vismaz 11/5;

ja otrais spēlētājs izmanto trešo stratēģiju ar varbūtību 3/5, ceturtais ar varbūtību 2/5 un neizmanto pirmo un otro stratēģiju, tad ar pietiekami lielu spēļu skaitu ar doto matricu viņa zaudējums vidējais būs ne vairāk kā 11/5.

2. piemērs. Atrodi matricas doto spēles risinājumu

Spēlei nav seglu punkta. Optimālais risinājums būtu jāmeklē jaukto stratēģiju jomā. Konstruēsim segmentus plaknē, kas atbilst pirmā spēlētāja stratēģijām.

Spēlētāja B zaudējuma augšējā robeža ir pārtrauktā līnija A 1 CA 4 . Stratēģijas A 1 Un A 2 ir spēlētāja A aktīvās stratēģijas. To krustošanās punkts UZ nosaka spēlētāju optimālās stratēģijas un spēles cenu. Pirmajam spēlētājam nav izdevīgi pielietot stratēģijas A 3 Un A 4 , tāpēc to izmantošanas varbūtība ir nulle, t.i. X 2 = x 3 = 0. Spēles risinājums tiek reducēts līdz spēles atrisinājumam ar matricu (2x2)

Izmantojot formulas (1)–(3), mēs atrodam optimālās stratēģijas un spēles cenu:

X 1 = 7/8, X 4 = 1/8; plkst 1 = 3/8, plkst 2 = 5/8; v = 27/8.

Atbilde. Optimālas jauktas spēlētāju stratēģijas

X (7/8, 0, 0, 1/8) un Y (3/8, 5/8), spēles cena ir v = 27/8.

Šī atbilde nozīmē sekojošo:

ja pirmais spēlētājs ar varbūtību 7/8 izmanto pirmo stratēģiju, ar varbūtību 1/8 ceturto un neizmanto otro un trešo stratēģiju, tad ar pietiekami lielu spēļu skaitu ar doto matricu viņa laimesti vidējais rādītājs būs vismaz 27/8;

ja otrais spēlētājs izmanto pirmo stratēģiju ar varbūtību 3/8 un otro ar varbūtību 5/8, tad ar pietiekami lielu spēļu skaitu ar šo matricu viņa zaudējums vidēji būs ne vairāk kā 27/8.

Datortehnoloģiju izmantošana tēmas “Antagonistiskās spēles” izpētē.

Lai atrisinātu matricas spēli grafiski, tiek izmantots Microsoft Word un Microsoft Excel, savukārt matricas spēles risināšanai, izmantojot lineārās programmēšanas metodes, tiek izmantota Microsoft Excel opcija “Meklēt risinājumu”. Aprēķiniem iespējams izmantot arī programmu MATLAB, kas ir augsta līmeņa tehniskā skaitļošanas valoda un interaktīva vide algoritmu izstrādei, datu vizualizācijai un analīzei un skaitliskiem aprēķiniem.

Uzdevumu iespējas patstāvīgam darbam.

Atrodiet optimālās spēles stratēģijas un cenu, ko dod maksājumu matrica A.

Plānot.

6.1. Saikne starp matricas spēlēm un lineāro programmēšanu.

6.2. Algoritms matricas spēļu risināšanai, izmantojot lineāro programmēšanu.

Saikne starp matricas spēlēm un lineāro programmēšanu

Spēļu teorija ir cieši saistīta ar lineāro programmēšanu, jo katru galīgo divu cilvēku nulles summas spēli var attēlot kā lineāras programmēšanas problēmu. G. Dancigs norāda, ka spēļu teorijas radītājs J. Fon Noimans, kurš pirmais lineārajā programmēšanā ieviesa simplekso metodi (1947), izveidoja šīs attiecības un tālāk pamatoja un attīstīja dualitātes jēdzienu lineārajā programmēšanā.

Pieņemsim, ka mums tiek dota divu cilvēku spēle, ko nosaka izmaksu matrica . Tad pirmā spēlētāja optimālo jaukto stratēģiju nosaka apstākļi

, . (6.1)

Šo problēmu var formulēt kā lineāras programmēšanas problēmu. Ļaujiet

Pēc tam var sastādīt problēmas matemātisko modeli pirmajam spēlētājam. Pamatojoties uz otrā spēlētāja tīrajām stratēģijām, spēles mērķa funkcija ir:

(6.2)

saskaņā ar ierobežojumiem

Otrajam spēlētājam problēma ir uzrakstīta kā

, .

Vidējā attiecība:

Tad problēma būs formā

(6.3)

saskaņā ar ierobežojumiem

.

Problēma otrajam spēlētājam (6.3) ir dubultā problēma ar pirmo spēlētāju (6.2). Otrajam spēlētājam problēmu var atrisināt, piemēram, izmantojot standarta simplekso metodi, bet pirmajam spēlētājam - izmantojot duālo simpleksa metodi. Metodes izvēli nosaka tas, kurai problēmai ir mazāk ierobežojumu, kas savukārt ir atkarīgs no katra spēlētāja tīro stratēģiju skaita.

Problēmas (6.2) matemātisko modeli var vienkāršot, sadalot visus ( n+ 1) ierobežojumi uz v. Tas ir iespējams ar v Nr 0. Kad v= 0, ieteicams visiem izmaksas matricas elementiem pievienot jebkuru pozitīvu skaitli, kas garantē modificētās spēles pozitīvo vērtību. Spēles faktisko vērtību iegūst, šo pozitīvo skaitli atņemot no modificētās vērtības. Ja v < 0, то надо сменить знаки неравенств.

Ticot v> 0, ierobežojumu sistēmu var uzrakstīt:

Ticot X i = x i / v un ja v® max, tad 1/ v® min, iegūstam formas lineārās programmēšanas uzdevumu

saskaņā ar ierobežojumiem

.

Līdzīgi, pamatojoties uz pirmā spēlētāja tīrajām stratēģijām vai saskaņā ar duālu uzdevumu sastādīšanas noteikumiem, ņemot par sākotnējo pirmā spēlētāja matemātisko modeli, otrā spēlētāja matemātiskais modelis tiek uzrakstīts formā.

saskaņā ar ierobežojumiem

,

Kur S(Y)maks = L(X)min = 1/v, Yj = y j/n.

Iepriekš minētie piemēri spēles risināšanai ar jauktām stratēģijām skaidri ilustrē matricas spēļu teorētiskos principus un manuālo aprēķinu sarežģītību pat ar 2x2 matricu. Lai automatizētu aprēķinus, varat izmantot programmatūras produktus, kuru aprēķina metodes pamatā ir lineāro vienādojumu sistēmas atrisināšana http://www.uchimatchast.ru/.

Jebkuru ierobežotu divu cilvēku nulles summas spēli var attēlot kā lineāru programmēšanas problēmu. Šajā gadījumā problēmu ir iespējams atrisināt gan ar tīru, gan jauktu stratēģiju. Tīras stratēģijas gadījumā vienas no stratēģijām varbūtība būs vienāda ar vienu, bet pārējo stratēģiju iespējamība, protams, būs vienāda ar nulli.

Spēlētāja A stratēģiju optimālās varbūtības var noteikt, atrisinot šādu maksimumu uzdevumu.

Formulēsim matricas spēles problēmu. Divi konkurējoši uzņēmumi A un B ražo produkciju. Lai palielinātu pārdošanas apjomu, produkts tiek piegādāts dažādos iepakojumos. Uzņēmums A izmanto kartonu A1, celofānu A2, plastmasu A3. Uzņēmums B izmanto tos pašus iepakojuma materiālus. Tomēr uzņēmumi izmantoja Dažādi iepakojuma dizains. Uzņēmums A reģistrēja klientu pieplūduma pieaugumu/samazinājumu atkarībā no produkta iepakojuma un konkurenta B uzvedības stratēģijas. Šī statistika ir parādīta tabulā.

Problēmas risinājuma pamatā ir katra spēlētāja labākā rezultāta iegūšana no sliktākā, ko var iegūt ar noteiktu uzvedības stratēģiju. No parādītās tabulas izriet, ka šo problēmu nevar atrisināt, pamatojoties uz tīrām stratēģijām (nav seglu punkta). Problēmas risinājums ir no -2 līdz 2. Šajā gadījumā ir jauktas stratēģijas, un, tā kā spēlētājam A stratēģiju skaits ir trīs, šo problēmu var atrisināt, izmantojot lineāro programmēšanu (LP), izmantojot algebrisko metodi. Jāatzīmē, ka šo problēmu nevar atrisināt grafiski, jo katram spēlētājam ir vairāk nekā divas stratēģijas.

Saskaņā ar tabulā sniegtajiem datiem LP problēma spēlētājam A tiek uzrakstīta šādi

maksimizēt:
(maksimālais klientu skaits), ievērojot šādus ierobežojumus:

5.3.3.1. LP problēmas atrisināšana, izmantojot simplekso metodi

Ievedīsim ierobežojumu sistēmu kanoniskā formā, lai to izdarītu, nevienādības ir jāpārveido vienādībās, pievienojot papildu mainīgos. Ja transformētajā nevienādībā ir zīme ≥, tad, pārejot uz vienādību, visu tās koeficientu un brīvo terminu zīmes mainās uz pretējo. Tad sistēma tiks uzrakstīta šādi:

Mēs turpinām sākotnējās simpleksa tabulas veidošanu. Mērķa funkcijas koeficientus ievada tabulas F rindā. Tā kā mums jāatrod mērķfunkcijas maksimums, tabulā tiek ievadīti koeficienti ar pretēju zīmi

No uzdevuma datiem izveidojam sākotnējo simpleksa tabulu.

Tā kā brīvo terminu ailē nav negatīvu elementu, ir atrasts reāls risinājums. Līnija M satur negatīvus elementus, kas nozīmē, ka iegūtais risinājums nav optimāls. Definēsim vadošo kolonnu. Lai to izdarītu, rindā M atradīsim negatīvo elementu ar maksimālo absolūto vērtību - tā ir -1. Galvenā rinda būs tā, kurai brīvā vārda attiecība pret vadošās kolonnas atbilstošo elementu ir minimāla . Vadošā līnija ir R 1 un vadošais elements ir 1.

Mūsu apkopotajā tabulā brīvo terminu kolonnā ir negatīvi elementi, starp kuriem mēs atrodam maksimālo moduli - šis ir elements: -3, tas nosaka vadošo rindu - X 11. Šajā rindā mēs atrodam arī maksimālo negatīvo elementu modulī: -5 tas atrodas kolonnā X 5, kas būs vadošā kolonna. Mainīgais, kas atrodas pirmajā rindā, tiek izslēgts no bāzes, un mainīgais, kas atbilst vadošajai kolonnai, ir iekļauts bāzē. Pārrēķināsim simpleksa tabulu:

Mūsu apkopotajā tabulā brīvo terminu kolonnā ir negatīvi elementi, starp kuriem mēs atrodam maksimālo moduli - šis ir elements: -4,4, tas nosaka vadošo rindu - X 10. Šajā rindā mēs atrodam arī maksimālo negatīvo elementu modulī: -7.6 tas atrodas kolonnā X 4, kas būs vadošā kolonna. Mainīgais, kas atrodas pirmajā rindā, tiek izslēgts no bāzes, un mainīgais, kas atbilst vadošajai kolonnai, ir iekļauts bāzē. Pārrēķināsim simpleksa tabulu:

Mūsu apkopotajā tabulā brīvo terminu kolonnā ir negatīvi elementi, starp kuriem mēs atrodam maksimālo moduli - šis ir elements: -2.11, tas nosaka vadošo rindu - X 9. Šajā rindā mēs atrodam arī maksimālo negatīvo elementu modulī: - 2,82 tas atrodas kolonnā X 2, kas būs vadošā kolonna. Mainīgais, kas atrodas pirmajā rindā, tiek izslēgts no bāzes, un mainīgais, kas atbilst vadošajai kolonnai, ir iekļauts bāzē. Pārrēķināsim simpleksa tabulu:

Tā kā rindā F nav negatīvu elementu, tika atrasts optimālais risinājums F = -0,75 ar vienādām mainīgajām vērtībām: X 2 = 0,75, X 4 = 0,4, X 5 = 0,29, X 3 = 0, 3.

Saskaņā ar tabulā sniegtajiem datiem LP problēma spēlētājam B tiek uzrakstīta šādi:

maksimizēt:
(minimālais klientu skaits), ievērojot šādus ierobežojumus:

Ievedīsim ierobežojumu sistēmu kanoniskā formā, lai to izdarītu, nevienādības ir jāpārveido vienādībās, pievienojot papildu mainīgos.

Ja transformētajā nevienādībā ir zīme ≥, tad, pārejot uz vienādību, visu tās koeficientu un brīvo terminu zīmes mainās uz pretējo.

Tad sistēma tiks uzrakstīta šādi:

Mēs turpinām sākotnējās simpleksa tabulas veidošanu. Mērķa funkcijas koeficientus ievada tabulas F rindā.

Tā kā starp sākotnējo nosacījumu kopu bija vienādības, mēs ieviesām mākslīgos mainīgos R. Tas nozīmē, ka simpleksa tabulai jāpievieno papildu rinda M, kuras elementi tiek aprēķināti kā vienādības nosacījumu atbilstošo elementu summa. (tie, kas pēc reducēšanas uz kanonisku formu satur mākslīgos mainīgos R), kas ņemti ar pretējo zīmi.

No uzdevuma datiem izveidojam sākotnējo simpleksa tabulu.

Tā kā brīvo terminu ailē nav negatīvu elementu, ir atrasts reāls risinājums. Līnija M satur negatīvus elementus, kas nozīmē, ka iegūtais risinājums nav optimāls. Definēsim vadošo kolonnu. Lai to izdarītu, rindā M atrodam maksimālo negatīvo elementu absolūtā vērtībā - tas ir -1. Galvenā rinda būs tā, kurai brīvā vārda attiecība pret atbilstošo vadošās kolonnas elementu ir minimāla. Vadošā līnija ir R 1 un vadošais elements ir 1.

Mūsu apkopotajā tabulā brīvo terminu kolonnā ir negatīvi elementi, starp kuriem mēs atrodam maksimālo moduli - šis ir elements: -3, tas nosaka vadošo rindu - X 9. Šajā rindā mēs atrodam arī maksimālo negatīvo elementu modulī: -6 tas atrodas kolonnā X 5, kas būs vadošā kolonna. Mainīgais, kas atrodas pirmajā rindā, tiek izslēgts no bāzes, un mainīgais, kas atbilst vadošajai kolonnai, ir iekļauts bāzē. Pārrēķināsim simpleksa tabulu:

Virknē M nav negatīvu elementu. Apskatīsim līniju F, kurā ir negatīvi elementi, tas nozīmē, ka iegūtais risinājums nav optimāls. Definēsim vadošo kolonnu. Lai to izdarītu, rindā F atrodam maksimālo negatīvo elementu absolūtā vērtībā - tas ir -1. Galvenā rinda būs tā, kurai brīvā vārda pozitīvā attiecība pret vadošās kolonnas atbilstošo elementu ir minimāla. Galvenā līnija ir X 11, un vadošais elements ir: 1,83.

Virknē M nav negatīvu elementu. Apskatīsim līniju F, kurā ir negatīvi elementi, tas nozīmē, ka iegūtais risinājums nav optimāls. Definēsim vadošo kolonnu. Lai to izdarītu, rindā F atrodam maksimālo negatīvo elementu absolūtā vērtībā - tas ir -3,92. Galvenā rinda būs tā, kurai brīvā vārda pozitīvā attiecība pret vadošās kolonnas atbilstošo elementu ir minimāla. Galvenā līnija ir X 10, un vadošais elements ir: 9,75.

Tā kā virknē F nav negatīvu elementu, ir atrasts optimālais risinājums. Tā kā sākotnējā problēma bija atrast minimumu, optimālais risinājums ir virknes F brīvais termins, kas ņemts ar pretējo zīmi. Optimālais risinājums tika atrasts F=-0,75 ar vienādām mainīgo vērtībām: X 5 =0,53, X 4 =0,12, X 2 =0,75, X 3 =0,35.

Aprēķini parādīja. Spēles vērtība gan no spēlētāja A puses, gan no spēlētāja B ir vienāda un vienāda ar -0,75.

Nulles summas spēle, kurā katra spēlētāja rīcībā ir ierobežots stratēģiju kopums. Matricas spēles noteikumus nosaka maksājumu matrica, kuras elementi ir pirmā spēlētāja laimesti, kas vienlaikus ir arī otrā spēlētāja zaudējumi.

Matricas spēle ir antagonistiska spēle. Pirmais spēlētājs saņem maksimālo garantēto (neatkarīgi no otrā spēlētāja uzvedības) laimestu, kas vienāds ar spēles cenu, otrais spēlētājs sasniedz minimālo garantēto zaudējumu.

Zem stratēģija tiek saprasts kā noteikumu (principu) kopums, kas nosaka darbības izvēli katram spēlētāja personīgajam gājienam atkarībā no esošās situācijas.

Tagad par visu kārtībā un detalizēti.

Maksājumu matrica, tīras stratēģijas, spēles cena

IN matricas spēle tās noteikumi ir noteikti maksājumu matrica .

Apsveriet spēli, kurā ir divi dalībnieki: pirmais spēlētājs un otrais spēlētājs. Ļaujiet pirmajam spēlētājam būt viņa rīcībā m tīras stratēģijas un otrā spēlētāja rīcībā - n tīras stratēģijas. Tā kā spēle tiek izskatīta, tad likumsakarīgi, ka šajā spēlē ir uzvaras un ir zaudējumi.

IN maksājumu matrica elementi ir skaitļi, kas izsaka spēlētāju uzvaras un zaudējumus. Uzvaras un zaudējumus var izteikt punktos, naudas daudzumā vai citās vienībās.

Izveidosim maksājumu matricu:

Ja pirmais spēlētājs izvēlas i- tīrā stratēģija un otrais spēlētājs - j tīrā stratēģija, tad pirmā spēlētāja izmaksa būs aij vienības, un arī otrā spēlētāja zaudējums ir aij vienības.

Jo aij + (- a ij) = 0, tad aprakstītā spēle ir nulles summas matricas spēle.

Vienkāršākais matricas spēles piemērs ir monētu mešana. Spēles noteikumi ir šādi. Pirmais un otrais spēlētājs met monētu, un rezultāts ir vai nu galvas, vai astes. Ja "galvas" un "galvas" vai "astes" vai "astes" tiek izmesti vienlaicīgi, tad pirmais spēlētājs laimēs vienu vienību, bet citos gadījumos viņš zaudēs vienu vienību (otrais spēlētājs laimēs vienu vienību) . Tās pašas divas stratēģijas ir otrā spēlētāja rīcībā. Atbilstošā maksājumu matrica būs šāda:

Spēles teorijas uzdevums ir noteikt pirmā spēlētāja stratēģijas izvēli, kas garantētu viņam maksimālo vidējo uzvaru, kā arī otrā spēlētāja stratēģijas izvēli, kas garantētu viņam maksimālo vidējo zaudējumu.

Kā jūs izvēlaties stratēģiju matricas spēlē?

Vēlreiz apskatīsim maksājumu matricu:

Vispirms noteiksim laimesta summu pirmajam spēlētājam, ja viņš izmanto i tīrā stratēģija. Ja pirmais spēlētājs izmanto i tīro stratēģiju, tad ir loģiski pieņemt, ka otrais spēlētājs izmantos tik tīru stratēģiju, kuras dēļ pirmā spēlētāja peļņa būtu minimāla. Savukārt pirmais spēlētājs izmantos tik tīru stratēģiju, kas viņam nodrošinātu maksimālu uzvaru. Pamatojoties uz šiem nosacījumiem, pirmā spēlētāja laimesti, ko mēs apzīmējam kā v1 , zvanīja maksimālais laimests vai zemāka spēles cena .

Plkst attiecībā uz šīm vērtībām pirmajam spēlētājam jārīkojas šādi. Katrā rindā pierakstiet minimālā elementa vērtību un atlasiet no tiem maksimālo. Tādējādi pirmā spēlētāja laimests būs maksimālais no minimālā. Līdz ar to nosaukums - maximin win. Šī elementa rindas numurs būs tīrās stratēģijas numurs, kuru izvēlas pirmais spēlētājs.

Tagad noteiksim zaudējumu summu otrajam spēlētājam, ja viņš izmanto j stratēģija. Šajā gadījumā pirmais spēlētājs izmanto savu tīro stratēģiju, kurā otrā spēlētāja zaudējums būtu maksimāls. Otrajam spēlētājam ir jāizvēlas tīra stratēģija, kurā viņa zaudējums būtu minimāls. Otrā spēlētāja zaudējums, ko mēs apzīmējam kā v2 , zvanīja minimālais zaudējums vai spēles augstākā cena .

Plkst problēmu risināšana par spēles izmaksām un stratēģijas noteikšana Lai noteiktu šīs vērtības otrajam spēlētājam, rīkojieties šādi. Katrā kolonnā pierakstiet maksimālā elementa vērtību un atlasiet no tām minimālo. Tādējādi otrā spēlētāja zaudējums būs minimums no maksimālā. No šejienes arī nosaukums - minimax win. Šī elementa kolonnas numurs būs otrā spēlētāja izvēlētās tīrās stratēģijas numurs. Ja otrais spēlētājs izmanto "minimax", tad neatkarīgi no pirmā spēlētāja stratēģijas izvēles viņš zaudēs ne vairāk kā v2 vienības.

1. piemērs.

.

Lielākais no mazākajiem rindu elementiem ir 2, tā ir spēles zemākā cena, tai atbilst pirmā rinda, tāpēc pirmā spēlētāja maksimālā stratēģija ir pirmā. Mazākais no lielākajiem kolonnu elementiem ir 5, tā ir spēles augšējā cena, tai atbilst otrā kolonna, tāpēc otrā spēlētāja minimax stratēģija ir otrā.

Tagad, kad esam iemācījušies atrast spēles zemāko un augšējo cenu, maximin un minimax stratēģijas, ir pienācis laiks iemācīties formāli definēt šos jēdzienus.

Tātad pirmā spēlētāja garantētā uzvara ir:

Pirmajam spēlētājam ir jāizvēlas tīra stratēģija, kas viņam nodrošinātu maksimālo minimālo laimestu. Šis pieaugums (maksimums) tiek apzīmēts šādi:

.

Pirmais spēlētājs izmanto savu tīro stratēģiju, lai otrā spēlētāja zaudējums būtu maksimāls. Šis zaudējums ir norādīts šādi:

Otrajam spēlētājam ir jāizvēlas sava tīrā stratēģija, lai viņa zaudējums būtu minimāls. Šis zudums (minimax) ir norādīts šādi:

.

Vēl viens piemērs no tās pašas sērijas.

2. piemērs. Dota matricas spēle ar izmaksu matricu

.

Nosakiet pirmā spēlētāja maximin stratēģiju, otrā spēlētāja minimālo stratēģiju, spēles zemāko un augšējo cenu.

Risinājums. Pa labi no maksājumu matricas tās rindās izrakstām mazākos elementus un atzīmējam no tiem maksimālo, bet zem matricas - lielākie elementi kolonnās un atlasiet mazāko no tiem:

Lielākais no mazākajiem rindu elementiem ir 3, tā ir spēles zemākā cena, tai atbilst otrā rinda, tāpēc pirmā spēlētāja maksimālā stratēģija ir otrā. Mazākais no lielākajiem kolonnu elementiem ir 5, tā ir spēles augšējā cena, tai atbilst pirmā kolonna, tāpēc otrā spēlētāja minimax stratēģija ir pirmā.

Seglu punkts matricas spēlēs

Ja spēles augšējā un apakšējā cena ir vienāda, tad tiek uzskatīts, ka matricas spēlei ir seglu punkts. Ir arī otrādi: ja matricas spēlei ir seglu punkts, tad matricas spēles augšējā un apakšējā cena ir vienāda. Atbilstošais elements ir gan mazākais rindā, gan lielākais kolonnā un ir vienāds ar spēles cenu.

Tādējādi, ja , tad ir pirmā spēlētāja optimālā tīrā stratēģija un otrā spēlētāja optimālā tīrā stratēģija. Tas ir, vienādas zemākās un augšējās spēles cenas tiek sasniegtas, izmantojot vienu un to pašu stratēģiju pāri.

Šajā gadījumā matricas spēlei ir risinājums tīrās stratēģijās .

3. piemērs. Dota matricas spēle ar izmaksu matricu

.

Risinājums. Pa labi no maksājumu matricas mēs tās rindās izrakstīsim mazākos elementus un atzīmēsim no tiem maksimālo, bet zem matricas - lielākos elementus kolonnās un atlasīsim minimālo no tiem:

Spēles zemākā cena sakrīt ar spēles augšējo cenu. Tādējādi spēles cena ir 5. Tas ir. Spēles cena ir vienāda ar seglu punkta vērtību. Pirmā spēlētāja maxin stratēģija ir otrā tīrā stratēģija, bet otrā spēlētāja minimax stratēģija ir trešā tīrā stratēģija. Šai matricas spēlei ir risinājums tīrās stratēģijās.

Atrisiniet matricas spēles problēmu pats un pēc tam apskatiet risinājumu

4. piemērs. Dota matricas spēle ar izmaksu matricu

.

Atrodiet spēles zemāko un augšējo cenu. Vai šai matricas spēlei ir seglu punkts?

Matricas spēles ar optimālu jauktu stratēģiju

Vairumā gadījumu matricas spēlei nav seglu punkta, tāpēc atbilstošajai matricas spēlei nav risinājumu tīrās stratēģijās.

Bet tam ir risinājums optimālās jauktās stratēģijās. Lai tos atrastu, jums jāpieņem, ka spēle tiek atkārtota pietiekami daudz reižu, lai, pamatojoties uz pieredzi, varētu uzminēt, kura stratēģija ir labāka. Tāpēc lēmums ir saistīts ar varbūtības un vidējā (matemātiskās cerības) jēdzienu. Galīgajā risinājumā ir gan seglu punkta analogs (tas ir, spēles apakšējās un augšējās cenas vienlīdzība), gan tām atbilstošo stratēģiju analogs.

Tātad, lai pirmais spēlētājs saņemtu maksimālo vidējo uzvaru un otrajam spēlētājam būtu minimāls vidējais zaudējums, tīras stratēģijas jāizmanto ar noteiktu varbūtību.

Ja pirmais spēlētājs izmanto tīras stratēģijas ar varbūtībām , tad vektors tiek saukta par jauktu pirmā spēlētāja stratēģiju. Citiem vārdiem sakot, tas ir tīru stratēģiju “maisījums”. Šajā gadījumā šo varbūtību summa ir vienāda ar vienu:

.

Ja otrais spēlētājs izmanto tīras stratēģijas ar varbūtībām , tad vektors tiek saukta par otrā spēlētāja jaukto stratēģiju. Šajā gadījumā šo varbūtību summa ir vienāda ar vienu:

.

Ja pirmais spēlētājs izmanto jauktu stratēģiju lpp, un otrais spēlētājs - jaukta stratēģija q, tad tam ir jēga paredzamā vērtība pirmā spēlētāja uzvara (otrā spēlētāja zaudējums). Lai to atrastu, jums jāreizina pirmā spēlētāja jauktās stratēģijas vektors (kas būs vienas rindas matrica), izmaksas matrica un otrā spēlētāja jauktās stratēģijas vektors (kas būs vienas kolonnas matrica):

.

5. piemērs. Dota matricas spēle ar izmaksu matricu

.

Nosakiet pirmā spēlētāja uzvaras (otrā spēlētāja zaudējuma) matemātisko cerību, ja pirmā spēlētāja jauktā stratēģija ir , bet otrā spēlētāja jauktā stratēģija ir .

Risinājums. Atbilstoši formulai, kas paredz pirmā spēlētāja uzvaras (otrā spēlētāja zaudējuma) matemātisko cerību, tā ir vienāda ar pirmā spēlētāja jauktās stratēģijas vektora, maksājumu matricas un otrā spēlētāja jauktās stratēģijas vektora reizinājumu:

Pirmais spēlētājs tiek saukts par tādu jauktu stratēģiju, kas nodrošinātu viņam maksimālo vidējo peļņu, ja spēle tiktu atkārtota pietiekami daudz reižu.

Optimāla jaukta stratēģija otrais spēlētājs tiek saukts par tādu jauktu stratēģiju, kas nodrošinātu viņam minimālu vidējo zaudējumu, ja spēle tiktu atkārtota pietiekami daudz reižu.

Pēc analoģijas ar maksimuma un minimuma apzīmējumu tīru stratēģiju gadījumā optimālās jauktās stratēģijas tiek apzīmētas šādi (un ir saistītas ar matemātisko cerību, tas ir, pirmā spēlētāja uzvaras un otrā spēlētāja zaudējuma vidējo vērtību):

,

.

Šajā gadījumā funkcijai E ir seglu punkts , kas nozīmē vienlīdzību.

Lai atrastu optimālas jauktas stratēģijas un seglu punktu, tas ir, atrisināt matricas spēli jauktās stratēģijās , jums ir jāsamazina matricas spēle līdz lineārai programmēšanas problēmai, tas ir, līdz optimizācijas problēmai, un jāatrisina atbilstošā lineārās programmēšanas problēma.

Matricas spēles reducēšana līdz lineārai programmēšanas problēmai

Lai atrisinātu matricas spēli jauktās stratēģijās, jums ir jākonstruē taisna līnija Lineārās programmēšanas problēma Un divkāršs uzdevums. Duālā uzdevumā tiek transponēta paplašinātā matrica, kas glabā ierobežojumu sistēmas mainīgo koeficientus, brīvos terminus un mainīgo koeficientus mērķa funkcijā. Šajā gadījumā sākotnējā uzdevuma mērķa funkcijas minimums tiek saskaņots ar duālās problēmas maksimumu.

Mērķa funkcija tiešā lineārā programmēšanas uzdevumā:

.

Ierobežojumu sistēma tiešā lineārā programmēšanas uzdevumā:

Duālās problēmas mērķa funkcija ir:

.

Ierobežojumu sistēma dubultajā problēmā:

Tiešās lineārās programmēšanas problēmas optimālais plāns tiek apzīmēts ar

,

un duālās problēmas optimālo plānu apzīmē ar

Atbilstošo optimālo plānu lineārās formas mēs apzīmējam ar un ,

un tās jāatrod kā atbilstošo optimālo plānu koordinātu summas.

Saskaņā ar iepriekšējās rindkopas definīcijām un optimālo plānu koordinātām ir spēkā šādas pirmā un otrā spēlētāja jauktās stratēģijas:

.

Teorētiskie matemātiķi to ir pierādījuši spēles cena tiek izteikts šādi, izmantojot optimālo plānu lineārās formas:

,

tas ir, tā ir optimālo plānu koordinātu summu apgrieztā vērtība.

Mēs, praktizētāji, varam izmantot šo formulu tikai, lai atrisinātu matricas spēles jauktās stratēģijās. Patīk formulas optimālu jaukto stratēģiju atrašanai attiecīgi pirmais un otrais spēlētājs:

kurā otrie faktori ir vektori. Kā mēs jau definējām iepriekšējā punktā, optimālās jauktās stratēģijas ir arī vektori. Tāpēc, reizinot skaitli (spēles cenu) ar vektoru (ar optimālo plānu koordinātām), iegūstam arī vektoru.

6. piemērs. Dota matricas spēle ar izmaksu matricu

.

Atrodiet spēles cenu V un optimālas jauktas stratēģijas un .

Risinājums. Mēs izveidojam lineāras programmēšanas problēmu, kas atbilst šai matricas spēlei:

Mēs iegūstam tiešās problēmas risinājumu:

.

Mēs atrodam optimālo plānu lineāro formu kā atrasto koordinātu summu.