Pelimallien käsite. Maksumatriisi

KÄYTÄNNÖN TYÖ №3

Peliteorian mallit

Pelimallien käsite

Peliteoria käsittelee erilaisten suositusten kehittämistä päätöksentekoon olosuhteissa konfliktitilanne. Matemaattisesti muodostettaessa konfliktitilanteita voidaan esittää kahden, kolmen tai useamman pelaajan pelinä, joista jokainen pyrkii maksimoimaan voittonsa toisen pelaajan kustannuksella. Konfliktitilanteen matemaattinen malli on ns peli, konfliktin osapuolet - pelaajia, ja konfliktin lopputulos on voittaa. Esittelemme jokaiselle viralliselle pelille määräyksiä, eli ehtojärjestelmä, joka määrittelee:

1. pelaajavaihtoehdot;

2. kuinka paljon tietoa kullakin pelaajalla on kumppanien käyttäytymisestä;

3. voitto, johon kukin toimintosarja johtaa.

Pääsääntöisesti voitto voidaan määrittää kvantitatiivisesti (esimerkiksi tappio - 0, voitto - 1, tasapeli - ½). Peli on ns höyrysauna, jos siihen osallistuu kaksi pelaajaa, ja useita jos pelaajia on enemmän kuin kaksi. Peli on ns nollasummapeli jos yhden pelaajan voitto on yhtä suuri kuin toisen tappio. Kutsutaan valitsemaan ja toteuttamaan yksi säännöissä määrätyistä toimista liikkua pelaaja. Liikkeet voivat olla henkilökohtaisia ​​ja satunnaisia. henkilökohtainen liike- pelaajan tietoinen valinta yhden mahdollisista toimista (siirto shakkipelissä), satunnainen liike- satunnaisesti valittu toiminto (kortin valinta sekoitettusta pakasta).

Pelaajan strategia kutsutaan sääntöjoukoksi, jotka määräävät hänen toiminnan valinnan jokaiselle henkilökohtaiselle liikkeelle tilanteesta riippuen. Peli on ns perimmäinen jos pelaajalla on rajallinen määrä strategioita, ja loputon- muuten.

Pelin ratkaisemiseksi tai löytämiseksi pelin päätös, jokaiselle pelaajalle tulee valita optimaalisuusehtoa täyttävä strategia, ts. yhden pelaajista on saatava maksimi voitto kun toinen pitää kiinni strategiastaan. Samaan aikaan toisella pelaajalla on oltava minimi tappio jos ensimmäinen pitää kiinni strategiastaan. Tällaisia ​​strategioita kutsutaan optimaaliseksi. tavoite Peliteoria on määrittää optimaalinen strategia jokaiselle pelaajalle. Optimaalista strategiaa valittaessa on luonnollista olettaa, että molemmat pelaajat käyttäytyvät etujensa kannalta järkevästi.

Maksumatriisi. Pelin alempi ja ylempi hinta

Harkitse rajallista paripeliä. Anna pelaaja MUTTA on m henkilökohtaisia ​​strategioita, joita me tarkoitamme A1, A2,…, Am. Anna pelaaja B saatavilla n henkilökohtaisia ​​strategioita, me tarkoitamme niitä B1, B2,…,Bn. He sanovat, että pelissä on ulottuvuus m´n. Seurauksena siitä, että pelaajat ovat valinneet minkä tahansa strategiaparin A i ja B j pelin lopputulos määräytyy yksiselitteisesti, ts. voittaa aij pelaaja MUTTA(positiivinen tai negatiivinen) ja tappio (- aij) pelaaja AT. Matriisi P=(a ij), jonka elementtejä ovat strategioita vastaavat voitot A i ja B j, kutsutaan maksumatriisi tai pelin matriisi.

Esimerkki - peli "Hae"

Pelaaja MUTTA voi piiloutua suojassa 1 - merkitään tämä strategia nimellä A 1 tai suojassa 2 - strategia A 2. Pelaaja AT voi etsiä ensimmäistä pelaajaa shelter 1 -strategiasta KOHDASSA 1, tai suojassa 2 - strategia IN 2. Jos pelaaja MUTTA asuu Holvissa 1 ja pelaaja löytää sen AT, eli pari strategiaa ollaan toteuttamassa (A 1, B 1), sitten pelaaja MUTTA maksaa sakkoja, ts. a 11=-1. Samoin saamme a 22=-1. Ilmeisesti strategiat (A 1, B 2) ja (A 2, B 1) anna pelaajalle MUTTA voitto 1, siis a 12=a 21=1. Siten saamme voittomatriisin

Harkitse peliä m´n matriisin kanssa P=(a ij) ja määrittää pelaajan parhaat strategiat MUTTA. Strategian valinta A i, pelaaja MUTTA pitäisi odottaa pelaajaa AT vastaa siihen jollakin strategioista Kirjassa j, josta pelaaja saa palkkion MUTTA minimaalinen (soitin AT yrittää "vahingottaa" pelaajaa MUTTA).

Merkitse a i pelaajan pienin voitto MUTTA strategiaa valittaessa A i kaikille mahdollisille pelaajastrategioille AT(pienin luku i-maksumatriisin rivi), ts. .

Kaikkien numeroiden joukossa a i valitse suurin: . Soitetaan a halvempi pelin hinta , tai maksimi voitto (maksimi ). se Pelaajan A taattu voitto mistä tahansa pelaajan B strategiasta. Näin ollen .

Maksimia vastaavaa strategiaa kutsutaan maksimistrategia. Pelaaja AT kiinnostunut vähentämään pelaajan voittoa MUTTA; strategian valinta B j, se ottaa huomioon A:n suurimman mahdollisen voiton. Merkitse .

Valitaan kaikista numeroista pienin ja soitetaan sille b pelin huippuhinta , tai minimi voitto (minimimax ). se taattu pelaajan B menetys minkä tahansa pelaajan A strategian osalta. Näin ollen .

Minimax-strategiaa kutsutaan minimax-strategia. Periaate, joka sanelee pelaajille varovaisimpien minimax- ja maximin-strategioiden valinnan, on ns. minimax-periaate.

tilastollisia pelejä

Monissa pelaamiseen johtavissa tehtävissä epävarmuutta aiheuttaa tiedon puute toimintaolosuhteista. Nämä olosuhteet eivät riipu toisen pelaajan tietoisista toimista, vaan objektiivisesta todellisuudesta, jota yleensä kutsutaan "luonnoksi". Tällaisia ​​pelejä kutsutaan peliksi luonnon kanssa (tilastopelit).

Tehtävä

Useiden vuosien käytön jälkeen teollisuuslaitteet ovat jossakin seuraavista tiloista: In 1 - laitteita voidaan käyttää seuraavan vuoden aikana ennaltaehkäisevän huollon jälkeen; B 2 - laitteiden häiriöttömän toiminnan varmistamiseksi tulevaisuudessa on tarpeen vaihtaa sen yksittäiset osat ja kokoonpanot; Kohdassa 3 - laite vaatii suuria korjauksia tai vaihtoa.

Vallitsevasta tilanteesta riippuen B 1, B 2, B 3 yrityksen johto voi tehdä seuraavat päätökset: A 1 - tehtaan asiantuntijoiden suorittama laitteiden korjaus, mikä vaatii asianmukaisia ​​kustannuksia a 1 = 6, a 2 = 10 ja 3 = 15 rahayksikköä ; A 2 - soita erityiselle korjaajaryhmälle, kustannukset ovat tässä tapauksessa b 1 \u003d 15, b 2 \u003d 9, b 3 \u003d 18 rahayksikköä; A 3 - vaihda laite uuteen, myymällä vanhentuneet laitteet sen jäännösarvoon. Tämän tapahtuman tulosten kokonaiskustannukset ovat vastaavasti 1 =13, 2 =24 ja 3 =12 rahayksikköä.

Harjoittele

1. Kun olet antanut kuvatulle tilanteelle pelisuunnitelman, tunnista sen osallistujat, osoita osapuolten mahdolliset puhtaat strategiat.

2. Laadi maksumatriisi, jossa selitetään matriisin elementtien a ij merkitys (miksi ne ovat negatiivisia?).

3. Selvitä, mitä päätöstä tulevan vuoden laitteiden käytöstä kannattaa suositella yrityksen johdolle tappioiden minimoimiseksi seuraavilla olettamuksilla: a) yrityksellä saatu kokemus vastaavien laitteiden käytöstä osoittaa että laitteiston ilmoitettujen tilojen todennäköisyydet ovat vastaavasti q 1 = 0,15; q2 = 0,55; q 3 \u003d 0,3 (käytä Bayes-testiä); b) kokemus osoittaa, että kaikki kolme mahdollista laitteiston tilaa ovat yhtä todennäköisiä (käytä Laplace-kriteeriä); c) laitteiston todennäköisyydestä ei voida sanoa mitään varmaa (käytä Waldin, Savagen, Hurwitzin kriteerejä). Parametrin arvo g=0,8 Hurwitz-kriteerissä asetetaan.

Ratkaisu

1) Kuvattu tilanne on tilastopeli.

Tilastomies on yrityksen johto, joka voi tehdä yhden seuraavista päätöksistä: korjata laitteet itse (strategia A 1), kutsua korjaajat (strategia A 2); vaihda laitteet uuteen (strategia A 3).

Toinen pelipuoli - luonto, otamme huomioon laitteiden kuntoon vaikuttavien tekijöiden yhdistelmän: laitteita voidaan käyttää ennaltaehkäisevän huollon jälkeen (ehto B 1); on tarpeen vaihtaa yksittäiset komponentit ja laitteen osat (tila B 2): se on tarpeen peruskorjaus tai laitteiden vaihto (tila B 3).

2) Laadi pelin voittomatriisi:

Maksumatriisielementti a ij näyttää yrityksen johtamisen kustannukset, jos valitulla strategialla A i laite on tilassa B j . Palkkausmatriisin elementit ovat negatiivisia, koska minkä tahansa valitun strategian osalta yrityksen johdon on kannettava kustannukset.

a) Laitteiston kaltaisessa yrityksessä kertynyt käyttökokemus osoittaa, että laitteiden tilojen todennäköisyydet ovat q 1 =0,15; q2 = 0,55; q 3 \u003d 0,3.

Esitetään voittomatriisi seuraavasti:

missä , (i=1,3)

Bayes-kriteerin mukaan optimaaliseksi pidetään puhdasta strategiaa A i, jolla tilastoitsijan keskimääräinen vahvistus maksimoidaan, ts. tarjoaa =max .

Bayesin optimaalinen strategia on strategia A1.

b) kokemus osoittaa, että kaikki kolme mahdollista laitteiston tilaa ovat yhtä todennäköisiä, ts. = 1/3.

Keskimääräiset voitot ovat:

1/3 * (-6-10-15) \u003d -31/3 "-10,33;

1/3*(-15-9-18) = -42/3 = -14;

1/3 * (-13-24-12) \u003d -49/3 "-16,33.

Laplacen mukaan optimaalinen strategia on A 1 .

c) laitteiston todennäköisyyksistä ei voida sanoa mitään varmaa.

Wald-kriteerin mukaan optimaalisena pidetään puhdasta strategiaa, joka takaa maksimaalisen voiton pahimmissa olosuhteissa, ts.

.

= max(-15, -18, -24) = -15.

Siten strategia A 1 on optimaalinen.

Rakennetaan riskimatriisi , jossa .

Pelaajan strategia on suunnitelma, jonka mukaan hän tekee valinnan missä tahansa tilanteessa ja mahdollisella asiatiedolla. Luonnollisesti pelaaja tekee päätöksiä pelin edetessä. Teoriassa voidaan kuitenkin olettaa, että pelaaja tekee kaikki nämä päätökset etukäteen. Sitten näiden päätösten kokonaisuus muodostaa hänen strategiansa. Mahdollisten strategioiden lukumäärästä riippuen pelit jaetaan äärellisiin ja äärettömiin. Peliteorian tehtävänä on kehittää suosituksia pelaajille, eli määrittää heille optimaalinen strategia. Optimaalinen strategia on strategia, joka pelin monta kertaa toistettaessa tarjoaa pelaajalle suurimman mahdollisen keskimääräisen voiton.

Yksinkertaisin strateginen pelityyppi on kahden hengen nollasummapeli (osapuolten voittosumma on nolla). Peli koostuu kahdesta siirrosta: pelaaja A valitsee yhden mahdollisista strategioistaan ​​Ai (i = 1, 2, m), ja pelaaja B valitsee strategian Bj (j = 1, 2, ., n), ja jokainen valinta tehdään täydellinen tietämättömyys toisen pelaajan valinnasta.

Pelaajan A tavoitteena on maksimoida funktio φ (Ai, Bj), pelaajan B tavoitteena on puolestaan ​​minimoida sama funktio. Jokainen pelaaja voi valita yhden niistä muuttujista, joista funktion arvo riippuu. Jos pelaaja A valitsee jonkin strategioista Ai, tämä ei sinänsä voi vaikuttaa funktion φ (Ai, Bj) arvoon.

Ai:n vaikutus φ:n (Ai, Bj) arvon suuruuteen on epävarma; varmuus tapahtuu vasta sen jälkeen, kun toinen muuttujan Bj pelaaja on valinnut φ:n (Ai, Bj) minimoinnin periaatteeseen. Tässä tapauksessa toinen pelaaja määrittää Bj:n. Olkoon φ (Ai, Bj)= aij. Tehdään matriisi A:

Matriisin rivit vastaavat strategioita Ai, sarakkeet vastaavat strategioita Bj. Matriisia A kutsutaan voitto- tai pelimatriisiksi. Matriisin elementti aij on pelaajan A voitto, jos hän valitsi strategian Ai, ja pelaaja B valitsi strategian Bj.

Anna pelaajan A valita jokin strategia Ai ; sitten pahimmassa tapauksessa (esimerkiksi jos valinta tulee kuuluisa pelaaja C) hän saa min aij:n suuruisen maksun. Tämän mahdollisuuden ennakoiden pelaajan A on valittava strategia maksimoidakseen vähimmäisvoittonsa:

a = max min aij

Arvoa a - pelaajan A taattua voittoa - kutsutaan pelin alhaisemmaksi hinnaksi. Strategiaa Ai0, joka varmistaa a:n vastaanottamisen, kutsutaan maximiniksi.

Pelaaja B, valitessaan strategian, lähtee seuraavasta periaatteesta: kun valitsee jonkin strategian Bj, hänen tappionsa ei ylitä matriisin j:nnen sarakkeen elementtien arvojen maksimiarvoa, ts. pienempi tai yhtä suuri kuin max aij

Ottaen huomioon asetettu max aij for erilaisia ​​merkityksiä j, pelaaja B valitsee luonnollisesti j:n arvon siten, että hänen maksimitappionsa β minimoidaan:

β = min miax aij

Arvoa β kutsutaan pelin ylemmiksi kustannuksiksi ja voittoa β vastaavaa strategiaa Bj0 minimax-strategiaksi.

Pelaajan A todellista voittoa kumppanien kohtuullisilla toimilla rajoittavat pelin alempi ja ylempi hinta. Jos nämä lausekkeet ovat yhtä suuret, ts.

Peliteoria on matemaattinen tieteenala, jonka aiheena ovat päätöksentekomenetelmät konfliktitilanteissa.

Tilanne on ns konflikti, jos siinä törmäävät useiden (yleensä kahden) vastakkaisia ​​tavoitteita tavoittelevan henkilön edut. Kumpikin osapuoli voi toteuttaa useita toimia saavuttaakseen tavoitteensa, ja toisen osapuolen menestys tarkoittaa toisen epäonnistumista.

Taloudessa konfliktitilanteet ovat hyvin yleisiä (toimittajan ja kuluttajan, ostajan ja myyjän, pankkiirin ja asiakkaan välinen suhde). Konfliktitilanteita löytyy monilta muilta alueilta.

Konfliktitilanteen synnyttää kumppanien etujen ero ja jokaisen halu tehdä optimaalisia päätöksiä, jotka toteuttavat asetetut tavoitteet suurimmassa määrin. Samanaikaisesti jokaisen on otettava huomioon omien tavoitteidensa lisäksi myös kumppanin tavoitteet ja otettava huomioon kumppanien tekemät tuntemattomat päätökset.

Yleensä konfliktitilanteita on vaikea analysoida suoraan useiden toissijaisten sisään tulevien tekijöiden vuoksi. Jotta konfliktitilanteen matemaattinen analyysi olisi mahdollista, sitä on yksinkertaistettava ottaen huomioon vain päätekijät. Yksinkertaistettua formalisoitua konfliktitilanteen mallia kutsutaan peli, konfliktin osapuolet - pelaajia ja konfliktin lopputulos - voittaa. Tyypillisesti voitto (tai tappio) voidaan ilmaista määrällisesti; Voit esimerkiksi arvioida tappion nollalla, voiton yhdellä ja tasapelin 1/2:lla.

Peli on kokoelma säännöt kuvailee pelaajien käyttäytymistä. Jokainen tapaus pelata peliä jollain tietyllä tavalla alusta loppuun on pelijuhlat. Kutsutaan valitsemaan ja toteuttamaan yksi säännöissä määrätyistä toimista liikkua pelaaja. Liikkeet voivat olla henkilökohtaisia ​​ja satunnaisia. henkilökohtainen liike- Tämä on pelaajan tietoinen valinta yhdestä mahdollisesta toiminnasta (esimerkiksi siirto shakkipelissä). Satunnainen liike- tämä on myös valinta yhdestä monista vaihtoehdoista, mutta tässä vaihtoehtoa ei valitse pelaaja, vaan jokin satunnainen valintamekanismi (kolikoiden heittäminen, kortin valitseminen sekoitettusta pakasta).

strategia Pelaaja on joukko sääntöjä, jotka määräävät hänen toimintojensa valinnan jokaiselle henkilökohtaiselle siirrolle tilanteesta riippuen.

Jos peli koostuu vain henkilökohtaisista liikkeistä, pelin lopputulos määräytyy, jos jokainen pelaaja on valinnut oman strategiansa. Jos pelissä on kuitenkin satunnaisia ​​liikkeitä, peli on luonteeltaan todennäköisyyspohjainen, eikä pelaajien strategioiden valinta vielä ratkaise pelin lopputulosta.

Vastaanottaja päättää peliin tai löytää ratkaisu peliin, jokaisen pelaajan on valittava ehtoja vastaava strategia optimaalisuus, nuo. yhden pelaajista on saatava maksimi voitto, kun toinen pitää kiinni strategiastaan. Samaan aikaan toisella pelaajalla on oltava minimi tappio jos ensimmäinen pitää kiinni strategiastaan. Tällaisia ​​strategioita kutsutaan optimaaliseksi. Optimaalisten strategioiden on täytettävä vakausehto, ts. kenenkään pelaajien pitäisi olla kannattamatonta luopua strategiastaan ​​tässä pelissä.

Peliteorian tavoitteena on määrittää kullekin pelaajalle optimaalinen strategia.

Harkitse rajallista paripeliä. Anna pelaaja MUTTA on m henkilökohtaisia ​​strategioita, joita me tarkoitamme A 1 , A2 , ..., Olen . Anna pelaaja AT saatavilla n henkilökohtaisia ​​strategioita, me tarkoitamme niitä B1 , B2 , ..., Bm . He sanovat, että pelissä on ulottuvuus m × n . Seurauksena siitä, että pelaajat ovat valinneet minkä tahansa strategiaparin

A i ja B j (i = 1, 2, ..., m; j = 1, 2, ..., n)

pelin lopputulos määräytyy yksiselitteisesti, ts. voittaa aij pelaaja MUTTA (positiivinen tai negatiivinen) ja tappio ( - aij ) pelaaja AT . Oletetaan, että arvot OU tunnetaan mistä tahansa strategiaparista (A i, B j ). Matriisi , jonka elementtejä ovat strategioita vastaavat voitot Ai ja Bj , kutsutaan maksumatriisi tai pelin matriisi. Yleinen muoto tällainen matriisi on esitetty taulukossa 3.1.

Taulukko 3.1

Tämän taulukon rivit vastaavat pelaajan strategioita MUTTA , ja sarakkeet ovat pelaajan strategioita AT . Tehdään voittomatriisi seuraavaa peliä varten.

Harkitse peliä m × n matriisin kanssa P = (a ij), i = 1, 2, ..., m; j = 1, 2, ..., n ja määrittää paras strategioista A 1 , A2 , ..., Olen . Strategian valinta Ai pelaaja MUTTA pitäisi odottaa pelaajaa AT vastaa siihen jollakin strategioista B j , josta pelaaja saa palkkion MUTTA minimaalinen (soitin AT yrittää "vahingottaa" pelaajaa MUTTA ). Merkitse a i , pelaajan pienin voitto MUTTA strategiaa valittaessa Ai kaikille mahdollisille pelaajastrategioille AT (pienin luku i-maksumatriisin rivi), ts.

Maksimia vastaavaa strategiaa kutsutaan maksimistrategia. Pelaaja AT kiinnostunut vähentämään pelaajan voittoa MUTTA ; strategian valinta B j , se ottaa huomioon suurimman mahdollisen voiton MUTTA . Merkitse

Minimaxia vastaavaa strategiaa kutsutaan minimax-strategiaksi. Periaate, joka sanelee pelaajille "varovaisimman" minimax- ja maximin-strategioiden valinnan, on ns. minimax-periaate. Tämä periaate seuraa järkevästä oletuksesta, että jokainen pelaaja pyrkii saavuttamaan vastustajan päinvastaisen tavoitteen. Määritetään pelin alempi ja ylempi hinta ja vastaavat strategiat ongelmassa.

Jos pelin ylä- ja alahinnat ovat samat, niin yleinen merkitys ylhäältä ja alempi hinta pelejä α = β = v nimeltään pelin nettohinta , tai pelin kustannuksella . Pelin hintaa vastaavat minimax-strategiat ovat optimaaliset strategiat, ja niiden kokonaisuus on optimaalinen ratkaisu , tai pelin päätös. Tässä tapauksessa pelaaja MUTTA saa suurimman takuun (riippumatta pelaajan käyttäytymisestä) AT ) voittaa v , ja soitin AT saavuttaa taatun vähimmäistason (riippumatta pelaajan käyttäytymisestä MUTTA ) tappio v . Ratkaisun peliin sanotaan olevan kestävyys , eli jos toinen pelaajista pitää kiinni optimaalisesta strategiastaan, toisen ei voi olla edullista poiketa optimaalisesta strategiastaan.

Pari puhtaat strategiat Ai ja B j antaa optimaalisen ratkaisun peliin jos ja vain jos vastaava elementti aij , on sekä sarakkeensa suurin että rivinsä pienin. Tällaista tilannetta, jos sellainen on, kutsutaan satulapiste (samanlainen kuin satulan pinta, joka kaartuu yhteen suuntaan ja alas toiseen suuntaan).

Varastonhallintamallin peruskäsitteet.

Sekä liiketoiminnassa että tuotannossa on yleinen käytäntö ylläpitää kohtuullinen materiaali- tai tarvikevarasto jatkuvuuden varmistamiseksi. tuotantoprosessi. Perinteisesti varastoa on pidetty väistämättöminä kustannuksina, sillä liian vähän varastoa on johtanut kalliisiin tuotantoseisokkeihin ja liian suuri varaston määrä vähentää pääomaa. Varastonhallinnan tehtävänä on määrittää varastotaso, joka tasapainottaa mainitut kaksi ääritapausta.

Harkitse varastonhallintamallien pääpiirteitä.

Kysyntä. Varastotuotteen kysyntä voi olla deterministinen(yksinkertaisimmassa tapauksessa - vakio ajassa) tai satunnainen. Kysynnän satunnaisuus kuvataan joko satunnaisella kysynnän hetkellä tai satunnaisella kysynnän määrällä deterministisinä tai satunnaisina aikoina.

Varaston täydennys. Varaston täydennys voidaan suorittaa joko määräajoin tietyin väliajoin tai varastojen loppuessa, ts. alentaa ne tietylle tasolle.

Tilausmäärä. Ajoittain tapahtuvan täydennyksen ja varastojen vahingossa loppumisen yhteydessä tilauksen määrä voi riippua tilauksesta, joka on havaittu tilaushetkellä. Tilaus tehdään yleensä samalle summalle, kun varasto saavuttaa tietyn tason - ns tilauspisteet.

Toimitusaika. Idealisoiduissa varastonhallintamalleissa oletetaan, että tilattu täydennys toimitetaan varastoon välittömästi. Muissa malleissa otetaan huomioon toimitusten viivästyminen kiinteällä tai satunnaisella aikavälillä.

Toimituskulut. Pääsääntöisesti oletetaan, että kunkin toimituksen hinta koostuu kahdesta osasta - kertaluonteisista kustannuksista, jotka eivät riipu tilatun erän tilavuudesta, ja kustannuksista, jotka riippuvat (useimmiten lineaarisesti) erän tilavuudesta.

varastointikustannukset. Useimmissa varastonhallintamalleissa varaston määrä katsotaan käytännössä rajattomaksi ja varastoitujen varastojen määrää käytetään kontrollimuuttujana. Samalla oletetaan, että kunkin varastoyksikön varastoinnista aikayksikköä kohden peritään tietty maksu.

Alijäämäsakko. Mikä tahansa varasto luodaan pulaa ehkäisemään tiettyä tyyppiä tuotteita palvelujärjestelmässä. Varaston puute oikeaan aikaan johtaa tappioihin, jotka liittyvät laitteiden seisokkiin, epäsäännölliseen tuotantoon jne. Näitä tappioita kutsutaan alijäämäsakko.

varastonimikkeistö. Yksinkertaisimmissa tapauksissa oletetaan, että varastossa on samantyyppisiä tuotteita tai homogeenista tuotetta. Enemmässä vaikeita tapauksia harkittu usean tuotteen varasto.

Varastojärjestelmän rakenne. Täysin kehittynyt matemaattisia malleja yksinäinen makea. Käytännössä on kuitenkin myös monimutkaisempia rakenteita: hierarkkiset varastojärjestelmät, joilla on erilaiset täydennysajat ja tilausten toimitusajat, mahdollisuus pörssinvaihtoon saman hierarkiatason varastojen välillä jne.

Hyväksytyn varastonhallintastrategian tehokkuuden kriteeri on kustannus (kustannus)toiminto, jotka edustavat varastossa olevan tuotteen toimittamisen, sen varastoinnin ja sakkojen kokonaiskustannuksia.

Varastonhallinta koostuu sellaisen varaston täydentämisen ja kulutuksen strategian löytämisestä, jossa kustannusfunktio saa minimiarvon.

Olkoon funktiot , ja ilmaisevat vastaavasti:

Varaston täydentäminen,

varastojen kulutus,

Varastotuotteen kysyntä

jonkin aikaa.

Varastonhallintamallit käyttävät yleensä näiden funktioiden aikajohdannaisia, , , joita kutsutaan vastaavasti

Peli on ns nollasummapeli, tai antagonistinen, jos yhden pelaajista voitto on yhtä suuri kuin toisen tappio, ts. pelin tehtävän suorittamiseksi riittää, että ilmoitetaan yhden niistä arvo. Jos nimetään a- voittaa yksi pelaajista, b on toisen voitto, sitten nollasummapelissä b = - a, joten riittää harkitsemaan esim. a.

Kutsutaan valitsemaan ja toteuttamaan yksi säännöissä määrätyistä toimista liikkua pelaaja. Liikkeet voivat olla henkilökohtaisia ​​ja satunnaisia.

henkilökohtainen liike- Tämä on pelaajan tietoinen valinta yhdestä mahdollisesta toiminnasta (esimerkiksi siirto shakkipelissä).

Satunnainen liike on satunnaisesti valittu toiminto (esimerkiksi kortin valinta sekoitettusta pakkasta). Otan työssäni huomioon vain pelaajien henkilökohtaiset liikkeet.

strategia Pelaajaa kutsutaan sarjaksi sääntöjä, jotka määräävät hänen toimintonsa valinnan kullekin henkilökohtaiselle siirrolle tilanteesta riippuen. Yleensä pelin aikana pelaaja tekee jokaisessa henkilökohtaisessa liikkeessä valinnan tilanteen mukaan. Periaatteessa on kuitenkin mahdollista, että pelaaja tekee kaikki päätökset etukäteen (vastauksena mihin tahansa tilanteeseen). Tämä tarkoittaa, että pelaaja on valinnut tietyn strategian, joka voidaan antaa sääntöluettelon tai ohjelman muodossa. (Joten voit pelata peliä tietokoneella). Peli on ns perimmäinen jos jokaisella pelaajalla on rajallinen määrä strategioita, ja loputon- muuten.

Pelin ratkaisemiseksi tai ratkaisun löytämiseksi peliin on jokaisen pelaajan valittava strategia, joka täyttää ehdon optimaalisuus, eli yhden pelaajista on saatava maksimi voitto kun toinen pitää kiinni strategiastaan. Samaan aikaan toisella pelaajalla on oltava minimi tappio jos ensimmäinen pitää kiinni strategiastaan. Sellainen strategioita nimeltään optimaalinen. Optimaaliset strategiat on myös tyydytettävä vakaustila, eli kenenkään pelaajien pitäisi olla kannattamatonta luopua strategiastaan ​​tässä pelissä.

Peliteorian tarkoitus: optimaalisen strategian määrittäminen kullekin pelaajalle. Optimaalista strategiaa valittaessa on luonnollista olettaa, että molemmat pelaajat käyttäytyvät etujensa kannalta järkevästi.

Antagonistisia pelejä, joissa jokaisella pelaajalla on rajallinen joukko strategioita, kutsutaan nimellä matriisipelejä. Tämä nimi selittyy seuraavalla mahdollisuudella kuvata tämän tyyppisiä pelejä. Teemme suorakaiteen muotoisen taulukon, jossa rivit vastaavat ensimmäisen pelaajan strategioita, sarakkeet vastaavat toisen strategioita ja taulukon solut rivien ja sarakkeiden leikkauskohdassa vastaavat pelin tilanteita. Jos laitamme jokaiseen soluun ensimmäisen pelaajan voiton vastaavaan tilanteeseen, saamme pelin kuvauksen tietyn matriisin muodossa. Tätä matriisia kutsutaan pelin matriisi tai maksumatriisi.

Samaa lopullista antagonistista peliä voidaan kuvata eri matriiseilla, jotka eroavat toisistaan ​​vain rivien ja sarakkeiden järjestyksessä.

Harkitse peliä m x n matriisin kanssa Р = (a ij), i = 1,2, ... , m, j = 1,2, ... , n ja määrittää paras strategioista A 1, A 2, ..., A m. Strategian valinta A i pelaaja MUTTA pitäisi odottaa pelaajaa AT vastaa siihen jollakin strategioista B j, josta pelaaja saa palkkion MUTTA minimaalinen (soitin AT yrittää "vahingottaa" pelaajaa MUTTA). Merkitse a i, pelaajan pienin voitto MUTTA strategiaa valittaessa A i kaikille mahdollisille pelaajastrategioille AT(pienin luku i-th voittomatriisin rivi), ts.

a i = aij , j = 1,...,n.

Kaikkien numeroiden joukossa a i (i = 1,2, ... , m ) valitse suurin. Soitetaan a halvempi pelin hinta tai suurin voitto (maximin). Tämä on pelaajalle taattu voitto. MUTTA mille tahansa pelaajan strategialle AT. Tämän seurauksena, i = 1,... , m; j = 1,...,n

Maksimia vastaavaa strategiaa kutsutaan maksimaalinen strategia. Pelaaja AT kiinnostunut vähentämään pelaajan voittoa MUTTA; strategian valinta B j, se ottaa huomioon suurimman mahdollisen voiton MUTTA.

Merkitse: β i = aij , i = 1,... , m

Kaikkien numeroiden joukossa B j valitse pienin ja soita β pelin huippuhinta tai minimax voitto (minimax). Tämä on pelaajalle taattu tappio. AT.

Näin ollen i = 1,... , m; j = 1,...,n.

Minimax-strategiaa kutsutaan minimax-strategia.

Periaate, joka sanelee pelaajille "varovaisimman" minimax- ja maximin-strategioiden valinnan, on ns. minimax-periaate. Tämä periaate seuraa järkevästä oletuksesta, että jokainen pelaaja pyrkii saavuttamaan vastustajan päinvastaisen tavoitteen.

Luento 9 Pelimallien käsite. Maksumatriisi.

§ 6 PELITEORIAN OSIA

6.1 Pelimallien käsite.

Konfliktitilanteen matemaattinen malli on ns peli , konfliktiin osallistuvia osapuolia pelaajia ja konfliktin lopputulos voittaa .

Esittelemme jokaiselle viralliselle pelille määräyksiä , nuo. ehtojärjestelmä, joka määrittää: 1) vaihtoehdot pelaajien toimille; 2) kuinka paljon tietoa kullakin pelaajalla on kumppanien käyttäytymisestä; 3) voitto, johon kukin toimintosarja johtaa. Tyypillisesti voitto (tai tappio) voidaan ilmaista määrällisesti; Voit esimerkiksi arvioida tappion nollalla, voiton yhdellä ja tasapelin 1/2:lla. Pelin tulosten kvantifiointia kutsutaan maksu .

Peli on ns höyrysauna , jos mukana on kaksi pelaajaa ja useita , jos pelaajia on enemmän kuin kaksi. Otamme huomioon vain paripelit. Niitä pelaa kaksi pelaajaa MUTTA ja AT, joiden intressit ovat vastakkaiset, ja pelissä tarkoitamme sarjaa toimia MUTTA ja AT.

Peli on ns nollasummapeli tai antagonistinen skoy , jos yhden pelaajista voitto on yhtä suuri kuin toisen tappio, ts. molempien osapuolten maksujen summa on nolla. Pelin tehtävän suorittamiseksi riittää, että ilmoitetaan yhden niistä arvo . Jos nimetään a- voittaa yksi pelaajista, b – toisen voitto, sitten nollasummapeliin b= –a, joten riittää pohtimaan esim a.

Kutsutaan valitsemaan ja toteuttamaan yksi säännöissä määrätyistä toimista liikkua pelaaja. Liikkeitä voi olla henkilökohtainen ja satunnainen . henkilökohtainen liike – se on pelaajan tietoinen valinta yhdestä mahdollisesta toiminnasta (esimerkiksi siirto shakkipelissä). Jokaisen henkilökohtaisen liikkeen mahdollisia vaihtoehtoja säätelevät pelisäännöt ja se riippuu molempien osapuolten aikaisempien liikkeiden kokonaismäärästä.

Satunnainen liike – se on satunnaisesti valittu toiminta (esimerkiksi kortin valitseminen sekoitettusta pakkasta). Jotta peli olisi matemaattisesti määritelty, pelin sääntöjen tulee määritellä jokaiselle satunnaiselle siirrolle todennäköisyysjakauma mahdollisia tuloksia.

Jotkut pelit voivat koostua vain satunnaisista liikkeistä (ns. puhtaat onnenpelit) tai vain henkilökohtaisista liikkeistä (shakki, tammi). Suurin osa korttipeleistä kuuluu sekatyyppisiin peleihin, eli ne sisältävät sekä satunnaisia ​​että henkilökohtaisia ​​liikkeitä. Seuraavassa tarkastellaan vain pelaajien henkilökohtaisia ​​liikkeitä.

Pelit luokitellaan paitsi liikkeiden luonteen (henkilökohtainen, satunnainen) mukaan, myös kunkin pelaajan käytettävissä olevan tiedon luonteen ja määrän mukaan toisen toiminnasta. Erityinen peliluokka ovat niin sanotut "pelit täydelliset tiedot». Peli täydellisellä tiedolla Peliksi kutsutaan peliä, jossa jokainen pelaaja jokaisessa henkilökohtaisessa siirrossa tietää kaikkien aikaisempien liikkeiden tulokset, sekä henkilökohtaiset että satunnaiset. Esimerkkejä peleistä, joissa on täydellistä tietoa, ovat shakki, tammi ja kuuluisa peli"Ristinolla". Suurin osa käytännönläheisistä peleistä ei kuulu täydellisen tiedon sisältävien pelien luokkaan, koska vastustajan toimista tuntematon on yleensä olennainen osa konfliktitilanteita.

Yksi peliteorian peruskäsitteistä on konsepti strategioita .

strategia Pelaajaa kutsutaan sarjaksi sääntöjä, jotka määräävät hänen toimintonsa valinnan kullekin henkilökohtaiselle siirrolle tilanteesta riippuen. Yleensä pelin aikana pelaaja tekee jokaisessa henkilökohtaisessa liikkeessä valinnan tilanteen mukaan. Periaatteessa on kuitenkin mahdollista, että pelaaja tekee kaikki päätökset etukäteen (vastauksena mihin tahansa tilanteeseen). Tämä tarkoittaa, että pelaaja on valinnut tietyn strategian, joka voidaan antaa sääntöluettelon tai ohjelman muodossa. (Joten voit pelata peliä tietokoneella). Peli on ns perimmäinen , jos jokaisella pelaajalla on rajallinen määrä strategioita, ja loputon .– muuten.

Vastaanottaja päättää peli , tai löytää pelin päätös , jokaisen pelaajan on valittava strategia, joka täyttää ehdot optimaalisuus , nuo. yhden pelaajista on saatava maksimi voitto, kun toinen pitää kiinni strategiastaan, samalla toisella pelaajalla on oltava minimi tappio , jos ensimmäinen noudattaa strategiaansa. Tällaisia ​​strategioita kutsutaan optimaalinen . Optimaalisten strategioiden on myös täytettävä ehto kestävyys , nuo. kenenkään pelaajien pitäisi olla kannattamatonta luopua strategiastaan ​​tässä pelissä.

Jos peliä toistetaan tarpeeksi monta kertaa, pelaajat eivät välttämättä ole kiinnostuneita voittamisesta ja häviämisestä jokaisessa pelissä, akeskimääräinen voitto (tappio) kaikissa puolueissa.

Peliteorian tavoitteena on määrittää kullekin pelaajalle optimaalinen strategia.

6.2. Maksumatriisi. Pelin alempi ja ylempi hinta

Lopeta peli, jossa pelaaja MUTTA Sillä on t strategiat ja pelaaja B - s strategioita kutsutaan peliksi.

Harkitse peliä
kaksi pelaajaa MUTTA ja AT("me" ja "vastustaja").

Anna pelaaja MUTTA on t henkilökohtaisia ​​strategioita, joita me tarkoitamme
. Anna pelaaja AT saatavilla n henkilökohtaisia ​​strategioita, me tarkoitamme niitä
.

Anna kummankin puolen valita tietty strategia; meille se tulee olemaan , vihollisen puolesta . Seurauksena siitä, että pelaajat ovat valinneet minkä tahansa strategiaparin ja (
) pelin lopputulos määräytyy yksiselitteisesti, ts. voittaa pelaaja MUTTA(positiivinen tai negatiivinen) ja häviäminen
pelaaja AT.

Oletetaan, että arvot tunnetaan mistä tahansa strategiaparista ( ,). Matriisi
,
, jonka elementtejä ovat strategioita vastaavat voitot ja , nimeltään maksumatriisi tai pelin matriisi. Tämän matriisin rivit vastaavat pelaajan strategioita MUTTA, ja sarakkeet ovat pelaajan strategioita B. Näitä strategioita kutsutaan puhtaiksi.

Peli Matrix
näyttää:

Harkitse peliä
matriisin kanssa

ja määrittää paras strategioista
. Strategian valinta , pelaaja MUTTA pitäisi odottaa pelaajaa AT vastaa siihen jollakin strategioista , josta pelaaja saa voittoa MUTTA minimaalinen (soitin AT yrittää "vahingottaa" pelaajaa A).

Merkitse pelaajan pienin voitto MUTTA strategiaa valittaessa kaikille mahdollisille pelaajastrategioille AT(pienin luku i-maksumatriisin rivi), ts.

(1)

Kaikkien numeroiden joukossa (
) valitse suurin:
.

Soitetaan
halvempi hinta ngra, tai suurin voitto (maxmin). Tämä on pelaajan A taattu voitto mistä tahansa pelaajan B strategiasta. Näin ollen

. (2)

Maksimia vastaavaa strategiaa kutsutaan maksimistrategia . Pelaaja AT kiinnostunut vähentämään pelaajan voittoa MUTTA, strategian valinta , siinä otetaan huomioon suurin mahdollinen voitto MUTTA. Merkitse

. (3)

Kaikkien numeroiden joukossa valitse pienin

ja soita pelin huippuhinta tai minimi voitto (minimax). Ego takaa pelaajan B menetyksen . Siksi,

. (4)

Minimax-strategiaa kutsutaan minimax-strategia.

Periaate, joka sanelee pelaajille "varovaisimman" minimax- ja maximin-strategioiden valinnan, on ns. minimax-periaate . Tämä periaate seuraa järkevästä oletuksesta, että jokainen pelaaja pyrkii saavuttamaan vastustajan päinvastaisen tavoitteen.

Lause.Pelin alempi hinta ei koskaan ylitä pelin ylempää hintaa.
.

Jos pelin ylä- ja alahinnat ovat samat, niin pelin ylemmän ja alemman hinnan kokonaisarvo
nimeltään pelin nettohinta, tai pelin hinta. Pelin hintaa vastaavat minimax-strategiat ovat optimaaliset strategiat , ja niiden kokonaisuus optimaalinen ratkaisu tai pelin päätös. Tässä tapauksessa pelaaja MUTTA saa suurimman takuun (riippumatta pelaajan käyttäytymisestä) AT) voittaa v, ja soitin AT saavuttaa taatun vähimmäistason (riippumatta pelaajan käyttäytymisestä MUTTA) häviämässä v. Ratkaisun peliin sanotaan olevan kestävyys , nuo. jos toinen pelaajista pitää kiinni optimaalisesta strategiastaan, toisen ei voi olla edullista poiketa optimaalisesta strategiastaan.

Jos joku pelaajista (esim MUTTA) pitäytyy optimaalisessa strategiassaan ja toisessa pelaajassa (AT) poikkeaa optimaalisesta strategiastaan ​​millään tavalla pelaajalle, joka teki poikkeaman, tästä ei voi koskaan olla hyötyä; tällainen poikkeama pelaajasta AT voi parhaimmillaan jättää voiton ennalleen. ja pahimmassa tapauksessa lisää sitä.

Päinvastoin, jos AT noudattaa optimaalista strategiaansa ja MUTTA poikkeaa omasta, niin siitä ei voi olla millään tavalla hyötyä MUTTA.

Pari puhdasta strategiaa ja antaa optimaalisen ratkaisun peliin jos ja vain jos vastaava elementti on sekä sarakkeensa suurin että rivinsä pienin. Tällaista tilannetta, jos sellainen on, kutsutaan satulapiste. Geometriassa kutsutaan pinnan pistettä, jolla on ominaisuus: samanaikainen minimi toisella koordinaatilla ja maksimi toisella. satula dot, analogisesti tätä termiä käytetään peliteoriassa.

Peli jota varten
, nimeltään satulapistepeli. Elementti , jolla on tämä ominaisuus, on matriisin satulapiste.

Joten jokaiselle satulapisteellä varustetulle pelille on olemassa ratkaisu, joka määrittää molemmille osapuolille optimaaliset strategiat, jotka eroavat seuraavista ominaisuuksista.

1) Jos molemmat osapuolet pitävät kiinni optimaalisista strategioistaan, keskimääräinen voitto on yhtä suuri kuin pelin nettokustannukset v, joka on sekä sen alempi että ylempi hinta.

2) Jos toinen osapuoli noudattaa optimaalista strategiaansa, kun taas toinen poikkeaa omastaan, poikkeava osapuoli voi vain hävitä tästä eikä voi missään tapauksessa lisätä voittoaan.

Satulankärjellä varustettujen pelien luokka kiinnostaa niin teoreettisesti kuin käytännönkin kannalta.

Peliteoriassa on todistettu, että erityisesti jokaisella täydellistä tietoa sisältävällä pelillä on satulakohta, ja näin ollen jokaisessa sellaisessa pelissä on ratkaisu, eli on olemassa pari optimaalista strategiaa toiselle ja toiselle puolelle, mikä antaa keskimääräinen voitto, joka on yhtä suuri kuin pelin hinta. Jos peli, jossa on täydet tiedot, koostuu vain henkilökohtaisista liikkeistä, niin silloin, kun kumpikin osapuoli soveltaa omaa optimaalista strategiaansa, sen on aina päätyttävä varsin selkeään lopputulokseen, nimittäin pelin hintaa vastaavaan voittoon.