MODELE DE OPTIMIZARE CUMODELE DE OPTIMIZARE CU [620488]

MODELE DE OPTIMIZARE CUMODELE DE OPTIMIZARE CU
JOCURI MATRICEALE

Elemente de teoria jocurilor
il î i d d i i î f f d lPrimele încercăr i de studiu matemat ic în acest sens au fost făcute de Pasca l,
Fermat, Jaques, Daniel și Nicolas Bernoulli în secolul al XVIII -lea când ,
lâ d îi l d l j i l d dt i t i d lț i i plecându-se în spec ial de la jocurile de noroc, au determinat o s e r ie de relații
care țin mai mult de teoria probabilității. În secolul al XIX-l ea au început să fi e
t di t it țiil d fli t î d i l i ă â d l ă i l l studiate situațiile de con flict în domen iul econom ic apărând lucrări ca ce leale
lui Pareto și Walras (1838). Abia în 1921 și ulterior în 1923 E . Borel a publica t
studii referitoare la teoria jocurilor fiind considerat întemeietorul a cestei teorii studii referitoare la teoria jocurilor fiind considerat întemeietorul acestei teorii .
Contribuții esențiale la dezvoltarea acestor modele a avut John v on
Neumann care în 1928 af o r m u l a tot e o r e m ăd eb a z ă( t e o r e m ad em i n m a x )a Neumann care, în 1928 , a formulat o teoremă de bază (teorema de minmax) a
Teoriei jocurilor și ulterior în 1944 împreună cu Oskar Morgens tern au publica t
Theory of Games and Economic Behaviour ”moment ce a marcat începutul „Theory of Games and Economic Behaviour , moment ce a marcat începutul
unei dezvoltări continue a acestei teorii.

Jocuri matriceale
l bi d di bili d l d l Teoria jocuri lor a r e c a o biect de stu diu sta bilirea meto delor de alegere a
celei mai bune soluții în situații conflictuale care pot interv eni între doi sau ma i
lți b t ți î fi di t ti t d li ă i ămulți com batanți în care fiecare dintre aceș tia au pu tere de ana liză și urm ăresc
atingerea propriilor scopuri.

Definiție Teoria jocurilor este teoria matematică care modelează situațiil e
conflictuale. O situație conflictual ă este caracterizată în general printr-un siste m
de reguli precise, în care se întâlnesc două sau mai multe părț i a căror activitat e
urmărește atingerea unui anumit scop și în care interesele părț ilor sunt contrare.

Principalele trăsături ale situațiilor conflictuale sunt:
1) caracterul rațional al părților;1) caracterul rațional al părților;
2) opoziția de interese a părților.

Jocuri matriceale
Definiție Prin joc se înțelege un model al unei situații conflictuale. Un joc est e
caracterizat de două componente fundamentale, și anume:
1) este un proces constituit dintr-o succesiune de acțiuni executa te dup ă
anumite reguli de către factori raționali numiți jucători (părți,
adversari, inamici, parteneri ),care iau câte o decizie, dintr-o mulțim e
dată de alternative;
2) o regulă de terminare a jocului și de repartiție a câștigului pe car e
fiecare jucător îl primește.

Să presupunem că jucătorul A va avea ca alternative mulțimea A = {a1, a2, …,
a}jucătorul Bmulțimea de alternative B={bb b}și așa mai departe am}, jucătorul B mulțimea dealternative B = {b1,b2, …,bn}și așa mai departe .
În momentul luării deciziei fiecare jucător va alege un anumit mod d e
acțiune ai  A, i = 1, 2, …, m, bj  B, j = 1, 2, …, n și așa mai departe .
Utilitatea alegerii unui anume mod de acțiune de către un jucător se apreciază Utilitatea alegerii unui anume mod de acțiune de către un jucător se apreciază
prin valoarea unei funcții numite funcție de câștig.
De exemplu, dacă jucătorul A folosește modul de acțiune ai  A, jucătorul B
modul de acțiune bBși așa mai departe atunci funcția de câștig a primului modul de acțiune bj Bși așa mai departe , atunci funcția de câștig a primului
jucător este f1(ai, bj, …), a celui de-al doilea jucător este f2(ai, bj, …) și așa ma i
departe .

Clasificarea jocurilor
Din punct de vedere al câștigului:
)j iă ădă l f(b)+f(b)+ a) jocuri cu sumă constantă, dacă are loc f1(ai,bj,…)+f2(ai,bj,…)+… = c ,
 ai A, bjB,…, cR, c fiind suma pusă în joc;
b) jocuri cu sum ă nulă: dacă c = 0. La sfârșitul jocului ce a câștigat u n
jă t i d t i l l ț ijucător au p ierdut ceilalți;

2) După numărul modurilor de acțiune ale fiecărui jucător:
a) jocuri finite dacă fiecare din mulțimile modurilor de acțiune A, B, C, ….
ale jucătorilor A, B, C, … sunt finite;
b) jocuri infinite dacă cel puțin o mulțime a modurilor de acțiune A, B, C, …
este infinită.

3) După numărul jucătorilor – cu 2, 3 sau mai mulți jucători. N u înțelege m
prin jucător neapărat o persoană, ci acea mulțime ai cărei memb ri au
același interesacelași interes .

4) După informația de care dispune fiecare jucător:
a) jocuri cu informa ție complet ă î n c a z u l i n c a r e f i e c a r e j u c ă t o r
îd f ă j l i ( d l jl dh ) cunoaște întreaga desfășurare a jocului (de exemp lu,jocul de șah);
b) jocuri cu informa ție incomplet ă în care jucătorii nu cunosc variantel e
de acțiune ale celorlalți ju cători (jocul de cărți).

Jocuri matriceale
Defini ție Un joc cu doi jucători cu sumă nulă se nume ște joc matriceal. ț jj ș j

Această categorie de jocuri are calitatea de a exprima foarte c lar noțiune a
de soluție a jocului care interesează de fapt în contextul luării deciziei optime.

Definiție Pentru a reprezenta un joc matriceal se întocmește o matrice nu mită
matricea câ știgurilor sau de plăți a jocului.

Fie f1 : ABR, f2 : ABR. Notăm cu f1(ai, bj) funcția de câștig a
jucătorului A în cazul când acesta folosește modul de acțiune ai, iar jucătorul B
fl dl d i bf(b)fii d f i d â i j ă l i Bî folosește mo dul de acț iune bj, f2(ai,bj)fiind funcția de câștig a jucătorului Bîn
aceeași situație.
Fiind un joc cu sumă nulă înseamnă că are loc relația f1(ai, bj) + f 2(ai, bj) = 0 ,
adică câștigul jucătorului A este pierdere pentru jucătorul B.
Presupunem că jucătorul A are m moduri de acțiune deci A = {a1, a2, …, am},
iar jucătorul Barenmoduri de acțiune deci B={b1b2 bm}Notăm cu cij iar jucătorul B are n moduri de acțiune , deci B {b1,b2,…,bm}.Notăm cu cij
câștigul jucătorului A când acesta folosește modul de acțiune ai, iar jucătorul B
modul de acțiune bj, atunci f1(ai, bj) = c ij.

Jocuri matriceale
Putem întocmi matricea de plăți a unui joc într- un tabel dat în forma de mai jos:

Tabelul nr. 1 Matricea de pl ăți
B b1 b2 … bj … bn A b1 b2 … bj … bn
a1 c 11 c 12 … c 1j … c 1n
a2 c 21 c 22 … c 2j … c 2n
.
.
.. .
.. .
.. .
.. .
.. .
.. .
. . . . . . . .
ai c i1 c i2 … c ij … c in
. . . . . . .
.
. .
. .
. .
. .
. .
. .
.
am c m1 c m2 … c mj … c mn

Un joc matriceal se poate scrie în forma  = (A, B, C), unde prin C a fost
notată matricea de plăți sau  = (A, B, f ), f fiind funcția de câștig.

Exemplu
(Jocul Morra practicat în Roma antică) Doi jucători arată simultan 1 sau 2 (Jocul Morra practicat în Roma antică) Doi jucători arată simultan 1 sau 2
degete de la mâna stângă spunând în același timp numărul de deg ete pe care
crede că le arată celălalt jucător. Dacă niciunul dintre jucăto ri nu ghicește sau
dacă ghicesc amândoi câștigul este nul Dacă ghicește numai unul dintre dacă ghicesc amândoi ,câștigul este nul. Dacă ghicește numai unul dintre
jucători, atunci acesta câștigă suma degetelor arătate, iar cel ălalt pierde aceeași
sumă. Să se întocmească matricea de plăți și să se analizeze ca re sunt modurile
d ți f bil t fi j ătde acțiune favora bile pen tru fiecare jucător.

Rezolvare Matricea de plăți este:

Tabelul nr. 2 Matricea de pl ăți pentru Jocul Morra
B
A (1,1) (1,2) (2,1) (2,2)
(1,1) 0 2 –3 0
( 1 , 2 ) – 2 0 0 3
(2 1) 3 0 0 –4 (2,1) 3 0 0 4
(2,2) 0 –3 4 0

Exemplu
În paranteze s-a trecut pe prima poziție numărul degetelor arăt ate de fiecar e
jucător, iar pe poziția a doua numărul de degete pe care fiecare jucător crede c ă
le va arăta celălalt.
Ce se observă din această matrice de plăți?
Dacă jucătorul A dorește să aibă un câștig cât mai mare, va juca variant a
(2, 2), dar în acest caz riscă să aibă o pierdere mare de –3 puncte. Aceast ă
variantă este însă mai bună decât modul de acțiune (1, 1).
Dă d ă i l ji ( 1 2) â d i d Dacă dorește s ă nu r iște așa mu lt, va juca var ianta (1,2) când pierderea s a
poate fi de cel mult –2 puncte, aceasta fiind mai bună decât var ianta (2, 1) cân d
ll i âti i ă ă i dă i lt la ace lași câștig riscă să piardă mai mult.

Jocuri matriceale
La analiza unui joc vom considera că jucătorul A va urmări întotdeaun a
obținerea unui câștig cât mai mare și-l vom numi jucător maximizant ,iar
jucătorul B va urmări obținerea unei pierderi minime, numindu-l jucător
minimizant.

Notăm cu i, mi1 , câștigul minim al jucătorului A când alege modu l
de acțiune ai și cu j
, nj1 , pierderea maximă a jucătorului B când aleg e
modul de acțiune bj. Notăm cu I și J mulțimea indicilor modurilor de acțiune ,
adică I = {1, 2, …, m} și J = {1, 2, …, m}. Putem scrie deci:

Ii i Ii,cminijJji 

 .

Cum jucătorul A caută maximizarea câștigului său, va alege maximu l
dintre valorile i. Această valoare o vom nota v1ș i o n u m i m valoare a
inferioară a jocului (valoare maxmin) , fiind câștigul minim sigur al jucătorului A.
Are loc deci:

v1 = ijIiiIicmin max max
Jj
 
 . (1)

Jocuri matriceale
Pentru jucătorul Bam notat cuj
, nj1 ,pierderea sa maximă care este Pentru jucătorul B am notat cu j
, nj1 , pierderea sa maximă care este
egală cu

Jjcmax 
 Jj,cmaxijIij  

 .

Jucătorul B dorește minimizarea pierderii sale și va ale ge minimul dintr e
valorile j
. Această valoare o notăm cu v2și o numim valoarea superioar ă a joculu i
(valoarea minmax ), fiind pierderea maximă sigură a jucătorului B, aceasta fiind

v2 = ijIiJjjJjcmaxmin min
 
 . (2)

Altfel scrise valorile v1șirespectiv v2sunt egale cu: Altfel scrise , valorile v1șirespectiv v2sunt egale cu:

v1 = jiBbAab,afminmax
j i 1;

v2 = jiAaBbb,af maxmin
i j 1.

Jocuri matriceale
Tabelul nr. 3 Matricea de pl ăți cu valorile v 1 și v2
B B
A b1 b 2 … b j … b n i
a1 c 11 c 12 … c 1j … c 1n 1
 a2 c 21 c 22 …c 2j …c 2n 2
.
. .
. .
. .
. .
. .
. .
. .
.
. . . . . . . .
ai c i1 c i2 … c ij … c in i
. . . . . . . .
.
. .
. .
. .
. .
. .
. .
. .
.
am c m1 c m2 … c mj … c mn m
j
 1 2 … j
 n v1
v2

Teoremă Fie v1 valoarea interioară a jocului și v2 valoarea sa superioară. Atunci
are loc relația

v1  v2. (3)

Jocuri matriceale
Defini țieÎn cazul în care are loc relația v1=v2atunci această valoare comună o Defini ție În cazul în care are loc relația v1v2, atunci această valoare comună o
numim valoarea jocului ș i o n o t ă m c u v. U n j o c p e n t r u c a r e a r e l o c r e l a ț i a
v1 = v 2 = v se numește joc cu punct- șa.

Propoziție Dacă v1 = v 2 = v, atunci exist ă (i0, j0)  I × J astfel încât


0 ,1 j ibaf 
0 0 ,1 j ibaf j ibaf ,
0 1 ,  JIji , . (4 ) 
0 1 j i 
0 0 1 j ij i0 1

Teoremă O condiție necesară și suficientă ca

b f b f jiBbAab,afminmax
j i 1 = j iAaBbb,af maxmin
i j1 (5)

este ca jocul să fie cu punct -șa. Dacă (,j iba )este perechea de alter native este ca jocul să fie cu punct șa. Dacă (
0 0,j iba ) este perechea de alternative
pentru care are loc relația (4), atunci

baf =v (6) 
0 0 ,1 j ibaf = v, (6)

v fiind valoarea comună a celor doi membri din egalitatea (5).

Jocuri matriceale
Defini ție Se nume ște punct de echilibru al unui joc matriceal (de doi jucători c u ț șp j( j
sumă nulă) o pereche de alternative (
0 0 ,j iba ) pentru care are loc relația (6).

Un joc poate avea mai multe puncte de echilibru toate asigurând însăUn joc poate avea mai multe puncte de echilibru toate asigurând însă
aceeași valoare a jocului.

Definiți eFie(ABC)un joc matriceal cu punct -saSe numește soluție a Definiți e Fie (A, B, C)un joc matriceal cu punct sa. Se numește soluție a
jocului orice element din mulțimea punctelor de echilibru.

Jocurile matriceale pot fi deci de două tipuri: Jocurile matriceale potfi deci de două tipuri:

a) cu puncte-șa, dacă are loc v1 = v 2;

b) fără puncte-șa, dacă v1 < v 2.

Exemplu
Fie un joc matriceal care are matricea de plăți de mai jos.

B
Ab1 b 2 b 3
a1 1 –3 2
a2 210
a3 1 3 4

Săse verifice dac ăacesta este un joc fărăpunct șa Să se verifice dacăacesta este un joc fărăpunct -șa.

Rezolvare Vom determina valorile maxmin și respectiv minmax ale celor doi jucători

B B
A b1 b 2 b 3 i
a1 1 –3 2 –3
a2 2 1 0 0 a2 2 1 0 0
a3 1 3 4 1
j
 2 3 4 1
2

Având în vedere valorile obținute, jocul nu este cu punct-șa.

Exemplu
Fie un joc matriceal care are matricea de plăți de mai jos.

B
A b1 b 2 b 3 b 4
a1 037 1 8
a2 5 4 6 5
a3 16 1 2 20

Săse verifice dac ăacesta este un joc cu punct -șa. Să se verifice dacăacesta este un joc cu punct șa.

Rezolvare Vom determina valorile maxmin și respectiv minmax a l e c e l o r d o i
jucători

B
A b1 b 2 b 3 b 4 i
a1 0 3 7 18 0
5 4 6 5 4 a2 5 4 6 5 4
a3 16 1 2 20 1
j
 16 4 7 20 4
4

Jocul are punct-șa deoarece v1 = v 2 = v = 4. Modurile de acțiune optime
pentru cei doi jucători sunt a1 pentru jucătorul A și respectiv b2 pentru jucătorul B.

Strategii mixte ale jucătorilor
Fie jocul matriceal ( A,B,C)în care matricea de pl ăție s t ed et i p u l mxn. Fie jocul matriceal (A,B,C) în care matricea de plăți este de tipul m x n.
Vom nota cu xi, mi1 , probabilitatea ca jucătorul A să aleagă modul d e
acțiune ai și cu yj, nj1 , probabilitatea ca jucătorul B să aleagă modul d e
i b acțiune bj.

Definiție Vectorul x = (x1, x2, …, xm), cu toate componentele pozitive și c u
+++ 1se n mește tti i t ăajc ă t o rli ANotăm c X x1+x2+…+xm = 1, se numește strategie mixtă a jucător ului A. Notăm cu X
mulțimea strategiilor mixte ale jucătorului A.

Definiți eVectorul y=(y1y2 y) cu toate componentele po zitive șic u Definiți e Vectorul y =(y1,y2,…,yn), cu toate componentele pozitive și cu
y1+y2+…+y n = 1, se numește strategie mixt ă a jucătorului B. Notăm cu Y
mulțimea strategiilor mixte ale jucătorului B.

Deci, putem scrie:
X = { x=(x1, x2, …, xm)mR / x 1+x2+…+x m = 1}
și
Y = { y=(y1, y2, …, yn)nR / y1+y2+…+y n = 1}.

Strategii mixte ale jucătorilor
Acest lucru se poate reprezenta în matricea de plăți așa cum se poate vedea
mai jos:
Tabelul nr. 4 Matricea de pl ăți extinsă
y y1 y2 yj y y y1 y2 … yj … yn
x B
A b1 b 2 … b j … b n
x1 a1 c 11 c12 …c 1j …c 1n
x2 a2 c 21 c 22 … c 2j … c 2n
. . . . . . . .
.
. .
. .
. .
. .
. .
. .
. .
.
xi ai ci1 ci2 cij cin xi ai ci1 ci2 … cij … cin
.
. .
. .
. .
. .
. .
. .
. .
.
. . . . . . . .
xm am c m1 c m2 … c mj … c mn

Strategii mixte ale jucătorilor
mn
Definiție Funcția F(x, y) = 
m
in
jj i ij yxc
11se numește câștig mediu al jucătorulu i
Acând acesta folosește strategia mixtă x, iar jucătorul Bstrategia mixtă y. A când acesta folosește strategia mixtă x, iar jucătorul B strategia mixtă y.
Definiție ~= (A, B, F) se numește extensia aleatoare a jocului .
Având introduse noțiunile de strategie și câștig mediu, putem d efini
noțiunile de mai jos.
Definiție Se numește câștigul mediu minim sigur al jucătorului A valoarea
F1(x0) = max F1(x)= max minF(x, y). (7) ()
Xx()
Xx Yy(y) ()
Strategia x0 care asigură acest lucru se numește strategie maxmin pentru
jucătorul A.
Se numește pierderea medie maxim ă sigură a jucătorului B valoarea
F2(y0) =
Yymin
 F2(y) =
Yymin
 Xxmax
 F(x, y). (8)
0Strategia y0 care asigură acest lucru se numește strategie minmax pentru
jucătorul B.

Strategii mixte ale jucătorilor
Vom nota cu
F() (9) v1 =
Xxmax
 Yymin
 F(x, y) (9)
valoarea maxmin și cu
v=minmax F(xy) (10) v2 =
Yymin
 Xxmax
 F(x, y) (10)
valoarea minmax .

Propoziție Fie v1 valoarea maxmin a jocului și v2 valoarea minmax a acestui a
date de relațiile (9) și (10 ). Atunci are loc relația
v1  v2. (11)

Definiție În cazul în care în relația (11) este egalitate, adică v1 = v 2, atunc i
valoarea lor comună o notăm cu v și se numește valoarea jocului .
Î0 0În acest caz spunem că jocul este cu punct-șa, iar perechea ( x0, y0) determinată c u
relațiile (7) și (8), care sunt în acest caz strategii optime pentru jucătorii A și
respectiv B, se numește punct de echilibru.

Prin urmare F(x0, y0) va fi valoarea jocului care este unică. Un joc poat e
avea mai multe puncte de echilib ru, însă toate au aceeași valoa re a jocului.

Rezolvarea jocurilor matriceale cu punct-șa
Fie un joc matriceal a cărui matrice de plăți este C, jucătorii AșiBavând Fie un joc matriceal a cărui matrice de plăți este C, jucătorii Ași B având
strategiile mixte x și respectiv y. Avem deci

ma aax … 2 1,
nb bby … 2 1.

 mx xxx … 2 1, 

 ny yyy … 2 1.
Dacă vom considera că jucătorul A alege modul de acțiune ai cu
probabilitatea l și celelalte moduri de acțiune cu probabilitatea 0 putem scrie: probabilitatea l și celelalte moduri de acțiune cu probabilitatea 0,putem scrie:



0 … 1 … 0 0 … … 2 1 m i i a a aax .
Definiție O strategie x = (x1, x2,…, xm) pentru care există un indice Ii astfe l
încât xi = 1 se numește strategie pur ă a jucătorului A. Elementele unei strategi i
pure xisunt elementele bazei canonice din RmÎn cazul în care jucătorul A pure x sunt elementele bazei canonice din R. În cazul în care jucătorul A
folosește strategia pură xi, iar jucătorul B strategia y, câștigul sperat de jucătoru l
A este
F(xi, y) = 
m
ii iiyc
1 (12)

Rezolvarea jocurilor matriceale cu punct-șa
Teoremă Dacă = (A,B,C) u n joc matriceal cu punct- șa de ti pul m x n, (,,)j p șp
atunci v1 = v 2 = v și au loc următoarele afirmații:
1° un element 00jic al matricei C este valoarea jocului dacă și numai dac ă
i i i v1=jiJjc0min
 și v2=0minijIic
;
2° dacă elementul 00jic al matricei C este valoarea jocului, atunc i
n m j iRR y x 0 0, este o soluție optimă a acestuia.

Din această teoremă rezultă metoda de rezolvare a jocurilor matriceale c u
punct-șa care presupune parcurgerea următorilor pași:
1) se determină valoarea inferioară ( v1) și superioară ( v2) a jocului;
2) în cazul în care v1=v2,valoarea jocului v este valoarea lor comună ; ) 1 2, j ;
3) se caută soluția jocului determinând indici Ii0 și Jj0 pentru care
jiJjcmin
0= v 1 și
0ijIicmin
= v 2;
4) punând x0 = 0ix și y0 = 0jy, rezultă că ( x0, y0) este o soluție optimă a
jocului.

Exemplu
Să se rezolve jocul matriceal a cărui matrice de plăți este:
B
A b1 b 2 b 3
a1 1 4 5
a2 2 3 4
a3 0 1 2

Rl Vd i l i l făii ăjli Rezolvare Vom determ ina va lorile inferioarăși respect iv superioarăa jocului:
B
A b1 b2 b 3 j
a1 14 5 1
a2 2 3 4 2
a3 0 1 2 0
i 4 5 2
2

C 2lj l
2
Cum v1 = v 2 = v =2, rezu ltă că jocul este cu punct-șa.
Strategia optimă pentru jucătorul A va fi x0 = (0, l, 0), iar pentru jucătorul B
va fi y0 = (l, 0, 0).

Rezolvarea jocurilor matriceale fără punct-șa
Sunt situații când se poate observa foarte ușor că unele moduri de a cțiune
sunt dezavanta joase pentru jucătorul A sau B.
Exemplu Se dă jocul matriceal a cărui matrice de plăți este:
Bb b b bA b1 b2 b3 b4
a1 –1 2 1 0
a2 431 1 2
a3 –2 0 1 2

Să se analizeze alternativele celor doi jucători.
Rezolvare Se observă că fiecare element de pe linia 2 este mai mare sau e gal cu
elementul corespunzător de pe linia 1. Prin urmare, pentru jucătorul A linia 1 este
neconvenabilă față de linia 2 și în concluzie se poate elimina acțiunea a1 obținând
o nouă matrice de plăți:
B
Ab1 b 2 b 3 b 4 A
a2 4 3 1 1
a3 –2 0 1 2

Rezolvarea jocurilor matriceale fără punct-șa
Pentru jucătorul B care dorește să-și minimizeze pierderile modul de
acțiune b3 este mai convenabil decât b4. Astfel se va obține următoarea formă
simplificată a matricei de plăți:

B
Ab1 b 2 b 3
a2 4 3 1
a3 –20 1

Definiție Spunem că o linie (coloană) domină o altă linie (coloană) dacă toate
elementele ei sunt mai mari sau egale decât ale celeilalte elementele ei sunt mai mari sau egale decât ale celeilalte .

Propoziție (Principiul domin ării) Dacă într-un joc matriceal o linie este
dominată de altă linie atunci ea poate fi eliminată din joc De asemenea dacă dominată de altă linie, atunci ea poate fi eliminată din joc. De asemenea , dacă
într-un joc matriceal o coloană domină o altă coloană, atunci e a poate fi
eliminată din joc.

Scopul aplicării acestui principiu este de a simplifica matricea de pl ăți,
reducându-se astfel volumul calculelor.