Igra se zove igra sa nultom sumom, ili antagonistički, ako je dobitak jednog od igrača jednak gubitku drugog, tj. Za kompletan zadatak igre, dovoljno je navesti veličinu jedne od njih. Ako odredimo a- dobici jednog od igrača, b- dobitak drugog, zatim za igru ​​sa nultom sumom b = - a, stoga je dovoljno razmotriti npr. a.

Izbor i provedba jedne od radnji predviđenih pravilima naziva se napredak igrač. Pokreti mogu biti lični i nasumični.

Lični potez- ovo je svjestan izbor igrača jedne od mogućih radnji (na primjer, potez u partiji šaha).

Slučajni potez je nasumično odabrana radnja (na primjer, odabir karte iz promiješanog špila). U svom radu razmatraću samo lične poteze igrača.

Strategija Igrač je skup pravila koja određuju izbor njegove akcije pri svakom ličnom potezu, ovisno o trenutnoj situaciji. Obično tokom igre, svakim ličnim potezom, igrač pravi izbor u zavisnosti od konkretne situacije. Međutim, u principu je moguće da sve odluke igrač donosi unaprijed (kao odgovor na bilo koju situaciju). To znači da je igrač odabrao određenu strategiju, koja se može specificirati kao lista pravila ili program. (Na ovaj način možete igrati igru ​​pomoću računara.) Igra se zove krajnji, ako svaki igrač ima konačan broj strategija, i beskrajno- inače.

Da biste riješili igru, odnosno pronašli rješenje za igru, trebate odabrati strategiju za svakog igrača koja zadovoljava uvjet optimalnost, tj. jedan od igrača mora primiti maksimalna pobeda kada se drugi drži svoje strategije. U isto vrijeme, drugi igrač mora imati minimalni gubitak, ako se prvi drži svoje strategije. Takve strategije su pozvani optimalno. Optimalne strategije također moraju zadovoljiti stanje stabilnosti, tj. Mora da je nepovoljno za bilo kojeg igrača da napusti svoju strategiju u ovoj igri.

Svrha teorije igara: Određivanje optimalne strategije za svakog igrača. Prilikom odabira optimalne strategije, prirodno je pretpostaviti da se oba igrača ponašaju razumno u smislu svojih interesa.

Zovu se antagonističke igre u kojima svaki igrač ima konačan skup strategija matrične igre. Ovaj naziv se objašnjava sljedećom mogućnošću opisivanja igara ove vrste. Sastavljamo pravokutnu tabelu u kojoj redovi odgovaraju strategijama prvog igrača, stupci strategijama drugog, a ćelije tablice koje se nalaze na sjecištu redova i stupaca odgovaraju situacijama u igri. Ako dobitak prvog igrača u odgovarajućoj situaciji stavimo u svaku ćeliju, dobijamo opis igre u obliku određene matrice. Ova matrica se zove matrica igre ili matrica isplate.

Ista igra sa konačnim nultom sumom može se opisati različitim matricama, koje se međusobno razlikuju samo po redoslijedu redova i stupaca.

Razmotrite igru m x n sa matricom P = (a ij), i = 1,2, ... , m;j = 1,2, ... , n i odrediti najbolju među strategijama A 1, A 2, …, A m. Odabir strategije A i igrač A mora očekivati ​​da igrač INće odgovoriti koristeći jednu od strategija Bj, za koji je isplata za igrača A minimalno (igrač IN nastoji da "povredi" igrača A). Označimo sa a i, najmanji dobitak igrača A prilikom odabira strategije A i za sve moguće strategije igrača IN (najmanji broj V i-th liniju platne matrice), tj.

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

Među svim brojevima a i (i = 1,2, ... , m ) izaberite najveću. Hajde da pozovemo a najniža cijena igre ili maksimalni dobitak (maximin). Ovo je zagarantovana pobeda za igrača A za bilo koju strategiju igrača IN. Stoga, , i = 1,... , m; j = 1,..., n

Strategija koja odgovara maksiminu se zove maksimalna strategija. Player IN zainteresovani za smanjenje dobitaka igrača A; odabir strategije Bj, uzima u obzir maksimalnu moguću dobit za A.

Označimo: β i = a ij , i = 1,... , m

Među svim brojevima Bj izaberite najmanju i pozovite je β najviša cijena igre ili minimalna pobjeda (minimax). Ovo je zagarantovan gubitak za igrača IN.

dakle, i = 1,... , m; j = 1,..., n.

Poziva se strategija koja odgovara minimaksu minimax strategija.

Princip koji nalaže igračima da izaberu "najopreznije" minimax i maximin strategije naziva se princip minimaksa. Ovaj princip proizilazi iz razumne pretpostavke da svaki igrač teži da postigne cilj suprotan od cilja njegovog protivnika.

http://emm. *****/lect/lect5.html#vopros2

(bolje izgleda na internetu od ove kopije)

Elementi teorije igara

1. Osnovni pojmovi i definicije. Predmet teorije igara.
2. Igre sa nultom sumom. Rješenje je u čistim strategijama.
3. Rješavanje igara u mješovitim strategijama.
4. Geometrijska interpretacija igara.
5. Svođenje uparene igre na problem linearnog programiranja.
6. Opća shema za rješavanje uparenih igara sa nultom sumom.
7. Upotreba alternativnih kriterijuma za određivanje optimalnih strategija.

1. Osnovni pojmovi i definicije. Predmet teorije igara

Vrlo često u mom praktične aktivnosti osoba se mora suočiti s problemima u kojima je potrebno donijeti odluku u uslovima kada dvije ili više strana imaju različite ciljeve, a rezultati svake akcije zavise od aktivnosti partnera. Takve situacije, koje nastaju, na primjer, prilikom igranja šaha, dama ili domina, klasificiraju se kao konfliktno: Rezultat poteza svakog igrača zavisi od kontra poteza protivnika. Kakav će to biti odgovor nije poznato unaprijed, pa kažu da se odluka mora donijeti u uslovima neizvjesnosti. Cilj igre je da jedan od učesnika pobedi.

U ekonomiji se konfliktne situacije javljaju često i različite su prirode. To uključuje, na primjer, odnose između dobavljača i potrošača, kupca i prodavca, banke i klijenta. U ovim primjerima konfliktnu situaciju generira razlika u interesima partnera i želja svakog od njih da donese odluke koje u najvećoj mjeri ostvaruju svoje ciljeve. Pri tome, svako mora voditi računa ne samo o svojim ciljevima, već i o ciljevima svog partnera, te uzeti u obzir unaprijed nepoznate odluke koje će ti partneri donijeti.

Situacija se zove sukob, ako se radi o strankama čiji su interesi potpuno ili djelimično suprotni.

Postoje naučno utemeljene metode za racionalno rješavanje problema u konfliktnim situacijama. Takve metode razvija matematička teorija konfliktnih situacija, tzv teorija igara.

Igra- radi se o stvarnom ili formalnom sukobu u kojem postoje najmanje dva učesnika (igrača), od kojih svaki teži ostvarivanju vlastitih ciljeva.

Zovu se dozvoljene radnje svakog igrača usmjerene na postizanje određenog cilja pravila igre.

Igra se zove parna soba, ako uključuje dva igrača, i višestruko, ako je broj igrača veći od dva. U nastavku ćemo razmatrati samo igre parova. Ova igra uključuje dva igrača - A i B, čiji su interesi suprotni. Igra (proces igre) će se shvatiti kao niz radnji od strane A i B.

Kvantifikacija rezultata igre se zove plaćanje.

Zove se igra parova igra sa nultom sumom, ili antagonistički, ako je iznos uplata nula, odnosno dobitak jednog igrača jednak je gubitku drugog. U ovom slučaju, da biste dovršili zadatak igre, dovoljno je naznačiti jednu od količina. ako npr. a– dobitak jednog od igrača, b- dobitak drugog, zatim za igru ​​sa nultom sumom b = -a, stoga je dovoljno razmotriti npr. a.

U ovom kursu ćemo razmotriti uparene igre sa nultom sumom.

Izbor i provedba jedne od radnji predviđenih pravilima naziva se napredak igrač. Pokreti mogu biti lični i nasumični.

Lični potez je svjestan izbor igrača jedne od mogućih radnji (na primjer, potez u partiji šaha).

Slučajni potez je nasumično odabrana radnja (na primjer, odabir karte iz promiješanog špila).

U budućnosti ćemo razmatrati samo lične poteze igrača.

Strategija igrača je skup pravila koja određuju izbor njegove akcije pri svakom ličnom potezu, u zavisnosti od trenutne situacije.

Obično tokom igre, svakim ličnim potezom, igrač pravi izbor u zavisnosti od konkretne situacije. Međutim, u principu je moguće da igrač donosi odluke unaprijed (kao odgovor na bilo koju situaciju). To znači da je igrač odabrao određenu strategiju, koja se može specificirati kao lista pravila ili program.

Igra se zove krajnji, ako svaki igrač ima konačan broj strategija, i beskrajno- inače.

Zove se igračeva strategija optimalno, ako pruža igraču maksimalnu pobjedu (ili, što je isto, minimalni gubitak), pod uslovom da se drugi igrač pridržava svoje strategije.

Ako se igra ponovi mnogo puta, onda igrači mogu biti zainteresirani ne za pobjedu i poraz u svakoj određenoj igri, već za prosječna pobjeda (gubitak) u svim serijama.

Da bi riješio igru, odnosno pronašao rješenje za igru, potrebno je da svaki igrač odabere optimalnu strategiju.

dakle, predmet teorije igara predstavljaju metode za pronalaženje optimalnih strategija igrača.

Prilikom odabira optimalne strategije, prirodno je pretpostaviti da se oba igrača ponašaju razumno u smislu svojih interesa. Najvažnije ograničenje teorije igara je jedinstvenost isplate kao pokazatelja efikasnosti, dok u većini realnih ekonomskih problema postoji više od jednog indikatora efikasnosti. Osim toga, u ekonomiji, po pravilu, postoje zadaci u kojima interesi partnera nisu nužno antagonistički. Međutim, rješavanje igrica u prisustvu velikog broja učesnika sa usaglašenim interesima je mnogo teži zadatak.

Ograničićemo se na razmatranje uparenih igara sa nultom sumom.

2. Igre sa nultom sumom. Rješenje u čistim strategijama

Razmotrimo uparenu konačnu igru.

Neka igrač A ima m ličnih strategija: A1, A2, …, Am. Neka igrač B ima n ličnih strategija. Označimo ih B1, B2, …, Bn. U ovom slučaju igra ima dimenziju mxn..gif" width="39" height="17 src=">) ishod igre je jednoznačno određen, tj. pobjednički aij igrača A (pozitivan ili negativan) i gubitak (-aij) igrača IN.

Pretpostavimo da su vrijednosti aij poznate za bilo koji par strategija (Ai, Bj).

Matrica A = (aij), 230" style="width:172.5pt">

a11 a12 ... a1n
a21 a22 ... a2n

Matrica plaćanja takođe često predstavljen u obliku tabele (vidi tabelu 5.1).

Tabela 5.1 - Opšti oblik matrica plaćanja

Redovi matrice A odgovaraju strategijama prvog igrača, a stupci strategijama drugog.

Ove strategije se nazivaju cisto.

Primjer 5.1. Kreirajte matricu plaćanja za sledeća utakmica(igra "Traži").

Igrač A može se sakriti u jednom od dva skloništa (I ili II); igrač B traži igrača A, i ako ga nađe, dobija kaznu od 1 novčane jedinice od A, u suprotnom plaća igraču A 1 novčanu jedinicu.

Rješenje.

Da biste kreirali matricu plaćanja, trebali biste analizirati ponašanje svakog igrača. Igrač A se može sakriti u skloništu I - označimo ovu strategiju sa A1, ili u skloništu II - strategijom A2.

Igrač B može tražiti prvog igrača u skloništu I - strategija B1, ili u skloništu II - strategija B2. Ako se igrač A nalazi u skloništu I i igrač B ga tamo otkrije, tj. implementira se par strategija (A1, B1), tada igrač A plaća kaznu, tj. a11 = -1. Slično, a22 = -1.

Očigledno, kombinacije strategija (A1, B2) i (A2, B1) daju igraču A isplatu, jednako jedan, pa je a12 = a21 = 1.

Dakle, za igru ​​"Traži" veličina 2x2 dobijamo sljedeću matricu plaćanja:

A (skrivanje) =

Razmotrimo igru ​​veličine mxn sa matricom A = (aij), https://pandia.ru/text/78/456/images/image002_132.gif" width="39" height="17 src=">i odredimo najbolja među strategijama A1, A2, …, Am.

Prilikom odabira strategije Ai, igrač A mora očekivati ​​da će igrač B na nju odgovoriti jednom od strategija Bj za koju je isplata igrača A minimalna (igrač B nastoji da "povredi" igrača A).

Označimo MsoNormalTable">

Među brojevima https://pandia.ru/text/78/456/images/image010_40.gif" width="44" height="16 src=">) izabraćemo najveći. Pozovimo najniža cijena igre ili maksimalni dobici (maksimin). Ovo zagarantovana isplata igrača A za bilo koju strategiju igrača B.

Konačna formula se može napisati na sljedeći način:

Strategija koja odgovara maksiminu se zove maksiminska strategija.

Slično razmišljanje se može izvesti u odnosu na igrača B.

Igrač B je zainteresiran za smanjenje isplate igrača A.

Prilikom odabira strategije Bj uzima u obzir da će igrač A težiti maksimalnoj pobjedi.

Označimo https://pandia.ru/text/78/456/images/image015_30.gif" width="10" height="17 src=">.gif" width="58 height=23" height="23 " >i nazovimo najviša cijena igre ili minimax. Ovo minimalni garantovani gubitak za igrača B.

ovako:

Poziva se strategija koja odgovara minimaksu minimax strategija.

Princip koji nalaže igračima da odaberu "najopreznije" maksiminske i minimaks strategije naziva se princip minimaksa. Ovaj princip proizilazi iz razumne pretpostavke da svaki igrač teži da postigne cilj suprotan cilju njegovog protivnika.

Igrač bira svoje postupke, pod pretpostavkom da će neprijatelj djelovati na nepovoljan način, odnosno pokušat će „naškoditi“.

Vratimo se na primjer 5.1 i odredite donju i gornju cijenu igre u zadatku “Traži”.

Razmotrite matricu plaćanja:

Prilikom odabira strategije A1 (prvi red matrice), minimalna isplata je https://pandia.ru/text/78/456/images/image012_33.gif" width="10" height="8 src="> 2 = min (- 1; 1) = -1, postiže se kada igrač B koristi strategiju B2.

Garantujete sebi maksimalnu pobedu za bilo koju strategiju igrača B, tj..gif" width="10" height="8 src=">.gif" width="7" height="14">1 = max (-1 ; 1) = 1.

Slično tome, maksimalni gubitak igrača B kada odabere strategiju B2 (druga kolona) je 2 = max (1; -1) = 1.

Dakle, za bilo koju strategiju igrača A, zagarantovani minimalni gubitak igrača B je = min (1, 2) = min (1, 1) = 1 - gornja cijena igre.

Svaka strategija igrača B je minimaks.

Rezultate našeg razmišljanja sumiramo u tabeli 5.2, koja je matrica plaćanja sa dodatnim redom j i kolonom i. Na njihovoj raskrsnici ćemo zapisati gornju i donju cijenu igre.

Tabela 5.2 - Matrica plaćanja igre "Traži" sa dodatnim redom i kolonom

Dakle, u problemu koji se razmatra, donja i gornja cijena igre se razlikuju: https://pandia.ru/text/78/456/images/image017_28.gif" height="14 src=">.

Ako se gornja i donja cijena igre poklapaju, onda opšte značenje gornje i donje cijene v = https://pandia.ru/text/78/456/images/image017_28.gif" height="14 src=">se zove po čistoj cijeni igre, ili jednostavno po cijenu igre. Maksimin i minimaks strategije koje odgovaraju cijeni igre su optimalne strategije, i njihova ukupnost – optimalno rešenje, ili jednostavno rešenje igre.

U ovom slučaju igrač A prima maksimalni zagarantovani (nezavisno od ponašanja igrača B) dobitak v, a igrač B postiže minimalni zagarantovani (nezavisno od ponašanja igrača A) gubitak v. Kažu da rješenje za igru ​​ima održivost, tj. ako se jedan od igrača pridržava svoje optimalne strategije, onda ne može biti isplativo da drugi odstupi od svoje optimalne strategije.

Par čistih strategija Ai i Bj daje optimalno rešenje igre ako i samo ako je njen odgovarajući element aij i najveći u svom stupcu i najmanji u svom redu.

Ova situacija, ako postoji, zove se sedlo(slično površini sedla, koja se u jednom smjeru savija prema gore, a u drugom prema dolje).

Dakle, za igru ​​sa sedlom, pronalaženje rješenja uključuje odabir maksiminske i minimaks strategije, koje su optimalne.

Primjer 5.2. Odredite donju i gornju cijenu igre, koja je data sljedećom matricom isplate:

0,5 0,6 0,8 0,9 0,7 0,8 0,7 0,6 0,6

Rješenje.

Hajde da saznamo da li igra ima tačku sedla. Pogodno je rješenje provesti u tabeli. Tabela 5.3 uključuje matricu isplate igre, kao i dodatni red i kolonu koji ilustruju proces pronalaženja optimalnih strategija.

Tabela 5.3 - Matrica plaćanja primjera 5.2 sa dodatnim redom i stupcem

Hajde da damo neka objašnjenja.

Kolona https://pandia.ru/text/78/456/images/image012_33.gif" width="10" height="8 src=">1 = 0,5; 2 = 0,7; 3 = 0, 6 - minimalni brojevi u redovima.

Slično, https://pandia.ru/text/78/456/images/image017_28.gif" width="7 height=14" height="14">2 = 0,7; 3 = 0,8 - maksimalni brojevi u kolonama.

3. Rješavanje igara u mješovitim strategijama

Dakle, za igru ​​sa sedlom, pronalaženje rješenja sastoji se od odabira maksimin i minimaks strategija, koje su optimalne.

Ako igra nema sedlo, onda upotreba čistih strategija ne pruža optimalno rješenje za igru. Na primjer, u igri "Traži" ( primjer 5.1) nema sedla.

U ovom slučaju moguće je dobiti optimalno rješenje naizmjeničnim čistim strategijama.

Mješovita strategija za igrača A je korištenje čistih strategija A1, A2, …, Am sa vjerovatnoćama u1, u2, …, um.

Obično se mješovita strategija prvog igrača označava kao vektor: U = (u1, u2, ..., um), a strategija drugog igrača kao vektor: Z = (z1, z2, ..., zm).

Očigledno je da:

ui ≥ 0, , zj ≥ 0, , ui = 1, zj = 1.

Optimalno rješenje za igru(ili jednostavno - rešenje igre) je par optimalnih strategija U*, Z*, in opšti slučaj mješoviti, koji imaju sljedeće svojstvo: ako se jedan od igrača pridržava svoje optimalne strategije, onda ne može biti isplativo da drugi odstupi od svoje. Poziva se isplata koja odgovara optimalnom rješenju po cijenu igre v. Cijena igre zadovoljava nejednakost:

Sljedeća fundamentalna teorema teorije igara je tačna.

Neumannova teorema. Svaka igra s konačnim nultom sumom ima mješovito strateško rješenje..

Neka je U* = (, https://pandia.ru/text/78/456/images/image030_23.gif" width="15" height="17 src=">) i Z* = (, https:// pandia.ru/text/78/456/images/image033_22.gif" width="13" height="17 src=">) - par optimalnih strategija. Ako čista strategija je uključen u optimalnu mješovitu strategiju s vjerovatnoćom različitom od nule, onda se zove aktivan.

Teorema aktivnih strategija. Ako se jedan od igrača drži svoje optimalne mješovite strategije, onda isplata ostaje nepromijenjena i jednaka cijeni igre v, ako drugi igrač ne prelazi granice svojih aktivnih strategija..

Ova teorema ima sjajnu praktični značaj- pruža specifične modele za pronalaženje optimalnih strategija u odsustvu sedla.

Razmislite o igri veličine 2 x2 .

Takva igra je najjednostavniji slučaj konačne igre. Ako takva igra ima sedlo, onda je optimalno rješenje par čistih strategija koje odgovaraju ovoj tački.

Za igru ​​u kojoj nema sedla u skladu s Neumannovom teoremom, postoji optimalno rješenje i određeno je parom mješovitih strategija U* = (https://pandia.ru/text/78/456/images/image029_24 .gif" width="13 " height="17 src=">) i Z* = (, https://pandia.ru/text/78/456/images/image029_24.gif" width="13" height= "17"> = v. Uzimajući u obzir da je + = 1, dobijamo sistem jednačina:

Igračeva strategija je plan prema kojem on bira u svakoj mogućoj situaciji i sa svim mogućim činjeničnim informacijama. Naravno, igrač donosi odluke kako igra napreduje. Međutim, teoretski, može se pretpostaviti da sve ove odluke igrač donosi unaprijed. Tada cjelokupnost ovih odluka čini njegovu strategiju. U zavisnosti od broja mogućih strategija, igre se dijele na konačne i beskonačne. Zadatak teorije igara je da razvije preporuke za igrače, odnosno da odredi optimalnu strategiju za njih. Optimalna strategija je ona koja, kada se igra ponavlja mnogo puta, daje datom igraču maksimalni mogući prosječni dobitak.

Najjednostavniji tip strateške igre je igra sa nultom sumom za dvije osobe (zbir isplata strana je nula). Igra se sastoji od dva poteza: igrač A bira jednu od svojih mogućih strategija Ai (i = 1, 2, m), a igrač B bira strategiju Bj (j = 1, 2, ., n), a svaki izbor se vrši sa potpuno neznanje o izboru drugog igrača.

Cilj igrača A je da maksimizira funkciju φ (Ai, Bj), a cilj igrača B je da minimizira istu funkciju. Svaki igrač može izabrati jednu od varijabli o kojoj ovisi vrijednost funkcije. Ako igrač A odabere neku od strategija Ai, to samo po sebi ne može utjecati na vrijednost funkcije φ (Ai, Bj).

Utjecaj Ai na vrijednost φ (Ai, Bj) je neizvjestan; Sigurnost se javlja tek nakon izbora, na osnovu principa minimiziranja φ (Ai, Bj), od strane drugog igrača varijable Bj. U ovom slučaju, Bj određuje drugi igrač. Neka je φ (Ai, Bj)= aij. Kreirajmo matricu A:

Redovi matrice odgovaraju strategijama Ai, kolone strategijama Bj. Matrica A se naziva matrica isplate ili igre. Element aij matrice je isplata igrača A ako je izabrao strategiju Ai, a igrač B odabrao strategiju Bj.

Neka igrač A odabere neku strategiju Ai; zatim unutra najgorem slučaju(na primjer, ako izbor postane poznat igraču B), on će dobiti isplatu jednaku min aij. Predviđajući ovu mogućnost, igrač A mora odabrati strategiju kako bi maksimizirao svoju minimalnu isplatu a:

a = max min aij

Vrijednost a - zagarantovani dobitak igrača A - naziva se niža cijena igre. Strategija Ai0 koja osigurava dobijanje a naziva se maximin.

Igrač B, pri odabiru strategije, polazi od sljedećeg principa: pri odabiru određene strategije Bj, njegov gubitak neće premašiti maksimum vrijednosti elemenata j-te kolone matrice, tj. manji ili jednak max aij

Uzimajući u obzir skup max aij za različite vrijednosti j, igrač B će prirodno izabrati vrijednost j na kojoj je njegov maksimalni gubitak β minimiziran:

β = min miax aij

Vrijednost β naziva se gornja cijena igre, a strategija Bj0 koja odgovara isplati β naziva se minimax.

Stvarni dobici igrača A, uz razumne akcije partnera, ograničeni su donjom i gornjom cijenom igre. Ako su ovi izrazi jednaki, tj.

Teorija igara je matematička disciplina čiji su predmet proučavanja metode odlučivanja u konfliktnim situacijama.

Situacija se zove sukob, ako se sukobe interesi više (obično dvoje) osoba koje teže suprotstavljenim ciljevima. Svaka strana može preduzeti niz aktivnosti kako bi ostvarila svoje ciljeve, pri čemu uspjeh jedne strane podrazumijeva neuspjeh druge.

U ekonomiji se vrlo često javljaju konfliktne situacije (odnosi između dobavljača i potrošača, kupca i prodavca, bankara i klijenta). Konfliktne situacije se javljaju u mnogim drugim oblastima.

Konfliktnu situaciju generiše razlika u interesima partnera i želja svakog od njih da donese optimalne odluke koje u najvećoj meri ostvaruju svoje ciljeve. Pri tome, svako mora voditi računa ne samo o svojim ciljevima, već i o ciljevima svog partnera, te voditi računa o unaprijed nepoznatim odlukama koje će partneri donijeti.

Obično je konfliktne situacije teško direktno analizirati zbog brojnih sekundarnih faktora koji su uključeni. Da bi to bilo moguće matematička analiza konfliktna situacija, potrebno ga je pojednostaviti, uzimajući u obzir samo glavne faktore. Pojednostavljeni formalizovani model konfliktne situacije se naziva igra, strane uključene u sukob - igrači, a ishod sukoba je pobijediti. Obično se dobitak (ili poraz) može kvantifikovati; na primjer, možete procijeniti gubitak kao nula, pobjedu kao jedan, a neriješeno kao 1/2.

Igra je zbirka pravila, koji opisuje ponašanje igrača. Svaki slučaj igranja igre na neki specifičan način od početka do kraja predstavlja igra igra. Izbor i provedba jedne od radnji predviđenih pravilima naziva se napredak igrač. Pokreti mogu biti lični i nasumični. Lični potez- ovo je svjestan izbor igrača jedne od mogućih radnji (na primjer, potez u partiji šaha). Slučajni potez- ovo je također izbor jedne od mnogih opcija, ali ovdje opciju ne bira igrač, već neki mehanizam slučajni odabir(bacanje novčića, biranje karte iz promešanog špila).

Strategija Igračem se naziva skup pravila koja određuju izbor njegovih akcija pri svakom ličnom potezu, ovisno o trenutnoj situaciji.

Ako se igra sastoji samo od ličnih poteza, onda je ishod igre određen ako svaki igrač odabere svoju strategiju. Međutim, ako igra ima nasumične poteze, tada će igra biti vjerovatnoće po prirodi i izbor strategija igrača još uvijek neće konačno odrediti ishod igre.

Da bi odlučiti igre, ili pronaći rješenje za igru, treba izabrati strategiju za svakog igrača koja zadovoljava uvjet optimalnost, one. jedan od igrača mora primiti maksimalna pobeda, kada se drugi drži svoje strategije. U isto vrijeme, drugi igrač mora imati minimalni gubitak, ako se prvi drži svoje strategije. Takve strategije se nazivaju optimalnim. Optimalne strategije moraju zadovoljiti uslov stabilnosti, tj. Mora da je nepovoljno za bilo kojeg igrača da napusti svoju strategiju u ovoj igri.

Cilj teorije igara je odrediti optimalnu strategiju za svakog igrača.

Razmotrimo uparenu konačnu igru. Pustite igrača A ima m lične strategije, koje označavamo A 1 , A 2 , ..., Am . Pustite igrača IN dostupan n lične strategije, označimo ih B 1 , B 2 , ..., B m . Kažu da igra ima dimenzije m×n . Kao rezultat toga što igrači biraju bilo koji par strategija

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

Ishod utakmice je jasno određen, tj. dobitke a ij igrač A (pozitivan ili negativan) i gubitak ( - a ij ) igrač IN . Pretpostavimo da su vrijednosti OU poznat po bilo kojem paru strategija (A i ,B j ). Matrix , čiji su elementi dobici koji odgovaraju strategijama A i I Bj , zvao matrica plaćanja ili matrica igre. Opšti izgled takve matrice prikazan je u tabeli 3.1.

Tabela 3.1

Redovi ove tabele odgovaraju strategijama igrača A , a kolone su igračeve strategije IN . Kreirajmo matricu plaćanja za sljedeću igru.

Razmotrite igru m×n sa matricom P = (a ij), i = 1, 2, ..., m; j = 1, 2, ..., n i odrediti najbolju među strategijama A 1 , A 2 , ..., Am . Odabir strategije A i igrač A mora očekivati ​​da igrač IN će odgovoriti koristeći jednu od strategija Bj , za koji je isplata za igrača A minimalno (igrač IN nastoji da "povredi" igrača A ). Označimo sa αi , najmanji dobitak igrača A prilikom odabira strategije A i za sve moguće strategije igrača IN (najmanji broj u i red matrice plaćanja), tj.

Strategija koja odgovara maksiminu se zove maksiminska strategija. Player IN zainteresovani za smanjenje dobitaka igrača A ; odabir strategije Bj , uzima u obzir maksimalnu moguću dobit za A . Označimo

Strategija koja odgovara minimaxu naziva se minimax strategija. Princip koji nalaže igračima da izaberu "najopreznije" minimax i maximin strategije naziva se princip minimaksa. Ovaj princip proizilazi iz razumne pretpostavke da svaki igrač teži da postigne cilj suprotan od cilja njegovog protivnika. Odredimo donju i gornju cijenu igre i odgovarajuće strategije u problemu.

Ako su gornja i donja cijena igre iste, onda je ukupna vrijednost gornje i donje cijene igre α = β = v pozvao po čistoj cijeni igre , ili po cijenu igre . Minimaks strategije koje odgovaraju cijeni igre su optimalne strategije, a njihova ukupnost je optimalno rešenje , ili rešenje igre. U ovom slučaju igrač A dobija maksimum zagarantovanog (nezavisno od ponašanja igrača) IN ) dobitak v , i plejer IN postiže zagarantovani minimum (bez obzira na ponašanje igrača A ) gubitak v . Kažu da rješenje za igru ​​ima održivost , tj. Ako se jedan igrač drži svoje optimalne strategije, onda ne može biti isplativo za drugog da odstupi od svoje optimalne strategije.

Par čistih strategija A i I Bj daje optimalno rješenje igri ako i samo ako je odgovarajući element a ij , je i najveći u svojoj koloni i najmanji u svom redu. Ova situacija, ako postoji, zove se sedlo (slično površini sedla, koja se u jednom smjeru savija prema gore, a u drugom prema dolje).

Osnovni koncepti modela upravljanja zalihama.

I u poslovanju i u proizvodnji, uobičajena je praksa održavati razumne zalihe materijalna sredstva ili komponente kako bi se osigurao kontinuitet proizvodni proces. Tradicionalno, zalihe se posmatraju kao neizbježni trošak, s nivoima zaliha koji su preniski što dovodi do skupih zaustavljanja proizvodnje, a nivoi zaliha koji su previsoki dovode do “smrti” kapitala. Cilj upravljanja zalihama je da se utvrdi nivo zaliha koji balansira dva navedena ekstremna slučaja.

Razmotrimo glavne karakteristike modela upravljanja zalihama.

Potražnja. Potražnja za zalihama proizvoda može biti deterministički(u najjednostavnijem slučaju - konstanta u vremenu) ili nasumično. Slučajnost potražnje opisuje se ili slučajnim momentom potražnje ili slučajnim iznosom potražnje u determinističkim ili slučajnim vremenima.

Dopuna skladišta. Dopunjavanje skladišta može se vršiti ili periodično u određenim intervalima, ili po trošenju zaliha, tj. svodeći ih na određeni nivo.

Količina narudžbe. Uz periodično dopunjavanje i povremeno trošenje zaliha, količina narudžbe može zavisiti od stanja uočenog u trenutku narudžbe. Narudžbina se obično postavlja za isti iznos kada zaliha dostigne zadati nivo - tzv narudžbe bodova.

Vrijeme dostave. Idealizirani modeli upravljanja zalihama pretpostavljaju da se naručena dopuna odmah isporučuje u skladište. Drugi modeli uzimaju u obzir kašnjenja u isporukama za fiksni ili nasumični vremenski period.

Trošak dostave. U pravilu se pretpostavlja da se trošak svake isporuke sastoji od dvije komponente - jednokratnih troškova koji ne ovise o obimu naručene serije i troškova koji (najčešće linearno) zavise od količine serije.

Troškovi skladištenja. U većini modela upravljanja zalihama, zapremina skladišta se smatra praktično neograničenom, a zapremina uskladištenih zaliha služi kao kontrolna varijabla. Pretpostavlja se da se naplaćuje određena naknada za čuvanje svake jedinice zaliha po jedinici vremena.

Kazna za nedostatak. Svako skladište se stvara kako bi se spriječile nestašice određene vrste proizvoda u servisiranom sistemu. Nedostatak zaliha u pravo vrijeme dovodi do gubitaka povezanih sa zastojima opreme, neredovnom proizvodnjom itd. Ovi gubici se nazivaju kazna za deficit.

Nomenklatura dionica. U najjednostavnijim slučajevima pretpostavlja se da skladište skladišti zalihe sličnih proizvoda ili homogenog proizvoda. U više teški slučajevi se razmatra zaliha sa više stavki.

Struktura skladišnog sistema. Najpotpunije razvijeni matematički modeli jednog skladišta. Međutim, u praksi postoje i složenije strukture: hijerarhijski sistemi skladišta sa različiti periodi dopuna i rok isporuke porudžbina, uz mogućnost razmene zaliha između skladišta istog hijerarhijskog nivoa itd.

Kriterijum efektivnosti usvojene strategije upravljanja zalihama je funkcija troškova (troškovi), predstavlja ukupne troškove snabdijevanja zalihama proizvoda, njegovog skladištenja i troškove kazni.

Upravljanje zalihama se sastoji u pronalaženju strategije dopune i potrošnje zaliha u kojoj funkcija troškova poprima minimalnu vrijednost.

Neka funkcije , i izraziti redom:

obnavljanje zaliha,

Potrošnja zaliha

Potražnja za proizvodom koji se skladišti

na određeno vrijeme.

Modeli upravljanja zalihama obično koriste derivate ovih funkcija s obzirom na vrijeme, , , zvane, respektivno,

PRAKTIČNI RAD br. 3

Modeli teorije igara

Koncept modela igre

Teorija igara bavi se razvojem različitih vrsta preporuka za donošenje odluka u konfliktnoj situaciji. Matematički formirajući konfliktne situacije, one se mogu predstaviti kao igra dva, tri ili više igrača, od kojih svaki teži cilju da maksimizira svoj dobitak na račun drugog igrača. Matematički model naziva se konfliktna situacija igra, strane uključene u sukob – igrači, a ishod sukoba je pobijediti. Za svaku formalizovanu igru, pravila, tj. sistem uslova koji definišu:

1. opcije za akcije igrača;

2. količinu informacija koje svaki igrač ima o ponašanju svojih partnera;

3. dobit do koje vodi svaki niz akcija.

Po pravilu, dobici se mogu odrediti kvantitativno (na primjer, gubitak je 0, pobjeda je 1, remi je ½). Igra se zove parna soba, ako uključuje dva igrača, i višestruko, ako je broj igrača veći od dva. Igra se zove igra sa nultom sumom, ako je dobitak jednog od igrača jednak gubitku drugog. Izbor i provedba jedne od radnji predviđenih pravilima naziva se napredak igrač. Pokreti mogu biti lični i nasumični. Lični potez– svjestan izbor igrača jedne od mogućih radnji (potez u partiji šaha), nasumičan potez– nasumično odabrana akcija (odabir karte iz promiješanog špila).

Strategija igrača je skup pravila koja određuju izbor njegove akcije za svaki lični potez, u zavisnosti od trenutne situacije. Igra se zove krajnji, ako igrač ima konačan broj strategija, i beskrajno- inače.

Za rješavanje igre ili pronalaženje rešenje igre, treba izabrati strategiju za svakog igrača koja zadovoljava uslov optimalnosti, tj. jedan od igrača mora primiti maksimalna pobeda kada se drugi drži svoje strategije. U isto vrijeme, drugi igrač mora imati minimalni gubitak, ako se prvi drži svoje strategije. Takve strategije se nazivaju optimalnim. Svrha teorija igara je da odredi optimalnu strategiju za svakog igrača. Prilikom odabira optimalne strategije, prirodno je pretpostaviti da se oba igrača ponašaju razumno u smislu svojih interesa.

Matrica plaćanja. Donja i gornja cijena igre

Razmotrimo uparenu konačnu igru. Pustite igrača A ima m lične strategije, koje označavamo A 1, A 2,…, A m. Pustite igrača B dostupan n lične strategije, označimo ih B 1, B 2,…, B n. Kažu da igra ima dimenzije m´n. Kao rezultat toga što igrači biraju bilo koji par strategija A i I Bj Ishod utakmice je jasno određen, tj. dobitke a ij igrač A(pozitivan ili negativan) i gubitak (- a ij) igrač IN. Matrix R=(a ij), čiji su elementi dobici koji odgovaraju strategijama A i I Bj, zvao matrica plaćanja ili matrica igre.

Bj A i	B 1	B 2	…	Bn
A 1	a 11	a 12	…	a 1n
A 2	a 21	a 22	…	a 2n
…	…	…	…	…
Am	a m1	am 2		a mn

Primjer - igra "Traži"

Player A može se sakriti u skloništu 1 - označimo ovu strategiju kao A 1 ili u skloništu 2 - strategija A 2. Player IN može tražiti prvog igrača u skrovištu 1 – strategija U 1, ili u skloništu 2 - strategija U 2. Ako igrač A nalazi se u skloništu 1 i tamo ga otkriva igrač IN, tj. implementira se nekoliko strategija (A 1,B 1), zatim plejer A plati kaznu, tj. a 11=–1. Slično dobijamo a 22=–1. Očigledno je da su strategije (A 1,B 2) I (A 2, B 1) dati igraču A isplata je 1, dakle a 12=a 21=1. Tako dobijamo matricu plaćanja

Razmotrite igru m´n sa matricom R=(a ij) i odrediti najbolju među strategijama igrača A. Odabir strategije A i, igrač A mora očekivati ​​da igrač INće odgovoriti koristeći jednu od strategija U j, za koji je isplata za igrača A minimalno (igrač IN nastoji da "povredi" igrača A).

Označimo sa a i najmanji dobitak igrača A prilikom odabira strategije A i za sve moguće strategije igrača IN(najmanji broj u i red matrice plaćanja), tj. .

Među svim brojevima a i Odaberimo najveće: . Pozovimo a najniža cijena igre , ili maksimalni dobici (maximin ). Ovo zagarantovana isplata igrača A za bilo koju strategiju igrača B. dakle, .

Strategija koja odgovara maksiminu se zove maksiminska strategija. Player IN zainteresovani za smanjenje dobitaka igrača A; odabir strategije Bj, uzima u obzir maksimalnu moguću dobit za A. Označimo .

Od svih brojeva biramo najmanji i zovemo ga b najviša cijena igre , ili minimax pobjeda (minimax ). Ovo zagarantovan gubitak igrača B za bilo koju strategiju igrača A. dakle, .

Poziva se strategija koja odgovara minimaksu minimax strategija. Princip koji nalaže da igrači biraju najopreznije minimax i maximin strategije se naziva princip minimaksa.

Statističke igre

U mnogim zadacima koji dovode do igara neizvjesnost je uzrokovana nedostatkom informacija o uvjetima pod kojima se radnja izvodi. Ovi uslovi ne zavise od svjesnih radnji drugog igrača, već od objektivne stvarnosti, koja se obično naziva "prirodom". Takve igre se nazivaju igre s prirodom (statističke igre).

Zadatak

Nakon nekoliko godina rada, industrijska oprema se nalazi u jednom od sljedećih stanja: B 1 – oprema se može koristiti u narednih godinu dana nakon preventivnog održavanja; B 2 – za nesmetano funkcionisanje opreme u budućnosti potrebno je zameniti pojedine delove i sklopove; 3 – oprema zahtijeva velike popravke ili zamjenu.

U zavisnosti od trenutne situacije B 1, B 2, B 3, menadžment preduzeća može doneti sledeće odluke: A 1 - popravku opreme od strane fabričkih stručnjaka, što zahteva odgovarajuće troškove a 1 = 6, i 2 = 10, i 3 = 15 novčanih jedinica; A 2 - pozovite poseban tim servisera, troškovi će u ovom slučaju biti b 1 = 15, b 2 = 9, b 3 = 18 novčanih jedinica; A 3 – zamijeniti opremu novom, prodati zastarjelu opremu po preostaloj vrijednosti. Ukupni troškovi povezani sa rezultatima ovog događaja biće jednaki, respektivno, c 1 =13, c 2 =24, c 3 =12 novčanih jedinica.

Vježbajte

1. Dajući opisanoj situaciji šemu igre, identifikujte njene učesnike, naznačite moguće čiste strategije strana.

2. Kreirajte matricu plaćanja, objašnjavajući značenje elemenata a ij matrice (zašto su negativni?).

3. Saznajte koju odluku o radu opreme u narednoj godini preporučljivo je preporučiti menadžmentu preduzeća kako bi se gubici minimizirali pod sljedećim pretpostavkama: a) iskustvo stečeno u preduzeću u radu slične opreme pokazuje da vjerovatnoće navedenih stanja opreme su jednake, odnosno q 1 = 0,15; q 2 =0,55; q 3 =0,3 (primijeniti Bayesov kriterijum); b) postojeće iskustvo pokazuje da su sva tri moguća stanja opreme podjednako vjerovatna (primijeniti Laplaceov kriterijum); c) ništa se definitivno ne može reći o vjerovatnoći opreme (primijeniti Wald, Savage, Hurwitz kriterij). Zadana je vrijednost parametra g=0,8 u Hurwitzovom kriteriju.

Rješenje

1) Opisana situacija je statistička igra.

Statističar je menadžment preduzeća, koji može donijeti jednu od sljedećih odluka: samostalno popraviti opremu (strategija A 1), pozvati servisere (strategija A 2); zamijeniti opremu novom (strategija A 3).

Druga igračka strana, priroda, smatraće se skupom faktora koji utiču na stanje opreme: oprema se može koristiti nakon preventivnih popravki (uslov B 1); potrebno je zamijeniti pojedine jedinice i dijelove opreme (uslov B 2): potrebno velika renovacija ili zamjena opreme (stanje B 3).

2) Kreirajmo matricu plaćanja igre:

Element platne matrice a ij prikazuje troškove upravljanja preduzećem ako, sa izabranom strategijom A i, oprema završi u stanju B j. Elementi matrice plaćanja su negativni, jer će sa bilo kojom odabranom strategijom menadžment preduzeća morati da snosi troškove.

a) iskustvo stečeno u preduzeću u radu sa sličnom opremom pokazuje da su verovatnoće stanja opreme jednake q 1 = 0,15; q 2 =0,55; q 3 =0,3.

Predstavimo matricu plaćanja kao:

Statistika strategija, A i	Prirodna stanja B j
B 1	B 2	B 3
A 1	-6	-10	-15	-10,9
A 2	-15	-9	-18	-12,6
A 3	-13	-24	-12	-18,75
q j	0,15	0,55	0,3

gdje , (i=1.3)

Prema Bayesovom kriteriju, optimalnom čistom strategijom A i uzima se ona koja maksimizira prosječni dobitak statističara, tj. predviđeno =max .

Optimalna strategija prema Bayesu, strategija A 1 je.

b) postojeće iskustvo pokazuje da su sva tri moguća stanja opreme podjednako vjerovatna, tj. = 1/3.

Prosječni dobici su:

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

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

1/3*(-13-24-12) = -49/3 » -16,33.

Optimalna Laplaceova strategija je strategija A 1 .

c) ništa se definitivno ne može reći o vjerovatnoći opreme.

Prema Valdovom kriterijumu, za optimalnu se uzima čista strategija koja u najgorim uslovima garantuje maksimalan dobitak, tj.

.

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

Dakle, strategija A 1 je optimalna.

Hajde da napravimo matricu rizika, gde je .

Povratak