Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
Transcript of Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
1/143
EMIL SIMION MIRCEA ANDRAIU
BAZELE MATEMATICE ALE
DECIZIILOR MANAGERIALE
CIBERNETICA MC
2010
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
2/143
Colecia Matematici aplicate
EMIL SIMION MIRCEA ANDRAIU
BAZELE MATEMATICE ALE
DECIZIILOR MANAGERIALE
CIBERNETICA MC
2010
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
3/143
Referenti tiinifici: Prof. univ. dr. Daniela Hincu
Colegiul tiintific:
Prof. univ. dr. Lucian Albu
Prof. univ. dr. Constantin Virgil Negoi
Prof. univ. dr. Marin Andreica
Prof. univ. dr. Florina Bran
Prof. univ. dr. Daniela Hincu
Prof. univ. dr. ing. Florin Ionescu
Prof. univ. dr. Sorin Cruceru
Prof. univ. dr. Gheorghe Sabau
Prof. univ. dr. Ion Partachi
Prof. univ. dr. Ion Pargaru
Conf. univ. dr. Romulus Andreica
Editura CIBERNETICA Bucureti 2010ISBN: 978-606-8288-10-9
E-mail: [email protected]
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
4/143
Bazele matematice ale deciziilormanageriale
Emil Simion
Universitatea din Bucuresti
e-mail: [email protected]
Mircea Andrasiu
Universitatea Wales, Bucuresti
e-mail:mircea [email protected]
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
5/143
Cuprins
1 PROGRAMARE LINIARA 1
1.1. Folosirea eficienta a resurselor limitate . . . . . . . . . . . . . . . . . 11.2. Forme ale problemelor de programare liniara . . . . . . . . . . . . . 3
1.3. Algoritmul simplex (Dantzig) . . . . . . . . . . . . . . . . . . . . . . 5
1.4. Duala unei probleme de programare liniara . . . . . . . . . . . . . . 7
1.5. Problema de transport . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6. Aplicatii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 PROGRAMARE DINAMICA 15
2.1. Forma unei probleme de optimizare secventiala . . . . . . . . . . . . 15
2.2. Teorema de optim . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3. Programare dinamica regresiva . . . . . . . . . . . . . . . . . . . . . 18
2.3.1. Ecuatiile programarii dinamice regresive . . . . . . . . . . . . 182.3.2. Algoritmul rezolvarii problemelor de programare regresiva . 19
2.3.3. Aplicatii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4. Programare dinamica progresiva . . . . . . . . . . . . . . . . . . . . 25
2.4.1. Ecuatiile programarii dinamice progresive . . . . . . . . . . . 25
2.4.2. Algoritmul rezolvarii problemelor de programare progresiva . 26
2.4.3. Aplicatii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 TEORIA JOCURILOR 31
3.1. Notiuni introductive . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2. Principiul minimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3. Strategii mixte si valoarea jocului . . . . . . . . . . . . . . . . . . . . 333.4. Teorema fundamentala a teoriei jocurilor . . . . . . . . . . . . . . . 34
3.5. Rezolvarea jocurilor matriceale . . . . . . . . . . . . . . . . . . . . . 35
3.5.1. Formularea problemei de optimizare . . . . . . . . . . . . . . 35
3.5.2. Reducerea la probleme de programare liniara . . . . . . . . . 36
3.6. Aplicatii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
v
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
6/143
CUPRINS vi
4 TEORIA DECIZIILOR STATISTICE 42
4.1. Prezentarea problemelor . . . . . . . . . . . . . . . . . . . . . . . . . 424.2. Strategii Bayes si strategii minimax . . . . . . . . . . . . . . . . . . . 43
4.3. Cazul efectuarii unor experiente unice . . . . . . . . . . . . . . . . . 44
4.4. Decizii optime n caz de incertitudine . . . . . . . . . . . . . . . . . . 46
4.4.1. Criteriul lui Hurwicz . . . . . . . . . . . . . . . . . . . . . . . 46
4.4.2. Criteriul lui Savage . . . . . . . . . . . . . . . . . . . . . . . . 46
4.4.3. Criteriul Bayes-Laplace . . . . . . . . . . . . . . . . . . . . . 47
4.4.4. Criteriul lui Wald . . . . . . . . . . . . . . . . . . . . . . . . 47
4.5. Aplicatii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5 TEORIA GRAFURILOR 515.1. Grafuri orientate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2. Algoritmul lui Kaufmann . . . . . . . . . . . . . . . . . . . . . . . . 52
5.3. Algoritmul lui Chen . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.4. Algoritmul lui Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.5. Algoritmul Bellman-Kalaba . . . . . . . . . . . . . . . . . . . . . . . 55
5.6. Algoritmul lui Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.7. Arbori minimali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.7.1. Algoritmul lui Kruskal . . . . . . . . . . . . . . . . . . . . . . 58
5.8. Aplicatii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6 PROBLEME DE TRANSPORT 71
6.1. Problema clasica de transport . . . . . . . . . . . . . . . . . . . . . . 71
6.1.1. Formularea problemei . . . . . . . . . . . . . . . . . . . . . . 71
6.1.2. Algoritmul de transport (adaptarea algoritmului simplex) . . 72
6.1.3. Determinarea unui program de baza initial . . . . . . . . . . 73
6.1.4. Degenerare si ciclare . . . . . . . . . . . . . . . . . . . . . . . 74
6.1.5. Variante ale problemei de transport . . . . . . . . . . . . . . 75
6.1.6. Algoritmul simplex modificat . . . . . . . . . . . . . . . . . . 76
6.1.7. Aplicatii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.2. Flux maxim intr-o retea de transport . . . . . . . . . . . . . . . . . . 86
6.2.1. Retele de transport . . . . . . . . . . . . . . . . . . . . . . . . 86
6.2.2. Algoritmul Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . 86
6.2.3. Problema de transport ca problema de flux maxim . . . . . . 89
6.2.4. Aplicatii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
7/143
CUPRINS vii
7 TEORIA STOCURILOR 100
7.1. Formularea modelului matematic . . . . . . . . . . . . . . . . . . . . 1007.2. Modele deterministe . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.2.1. Model de stocare a unui produs cu cerere constanta, perioadaconstanta de reaprovizionare si fara lipsa de stoc . . . . . . . 101
7.2.2. Model de stocare a unui produs cu cerere constanta, perioadaconstanta de reaprovizionare si cu posibilitatea lipsei de stoc 102
7.2.3. Model de stocare a unui produs cu cerere constanta, perioadaconstanta de reaprovizionare si fara lipsa de stoc, luand nconsiderare si costul de achizitie . . . . . . . . . . . . . . . . 105
7.2.4. Model de stocare a mai multor produse . . . . . . . . . . . . 1067.3. Modele probabiliste . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
7.3.1. Model de stocare a unui produs cu cerere aleatoare, cu pierderen cazul surplusului de stoc, cu cheltuieli suplimentare n cazullipsei de stoc si cu cost de stocare neglijabil . . . . . . . . . . 107
7.3.2. Model de stocare a unui produs cu cerere aleatoare, cu costde stocare si cost de penalizare pentru lipsa de stoc . . . . . 110
7.4. Aplicatii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
ANEXE 120
BIBLIOGRAFIE 131
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
8/143
Capitolul 1
PROGRAMARE LINIARA
1.1. Folosirea eficienta a resurselor limitate
O problema practica ce apare frecvent n activitatea de conducere economica esteurmatoarea. Sunt disponibile mai multe resurse (materii prime, forta de munca,resurse financiare) n cantitati limitate. Cu ajutorul acestor resurse se pot desfasuramai multe activitati economice. Problema consta n determinarea nivelurilor ac-tivitatilor luate n considerare care sa se ncadreze n limitarile precizate ale resur-selor si sa asigure satisfacerea optima a unui anumit criteriu.
Sa notam cu i, 1 i m, tipul resursei si cu bi cantitatea de resursa de tipuli care este disponibila. Vom nota prin j, 1 j n, tipul activitatii (procesuluide subproductie) si prin xj nivelul (necunoscut) la care urmeaza sa se desfasoareaceasta activitate. In sfarsit, vom nota prin aij cantitatea de resursa de tipul i,1 i m,necesara pentru producerea unei unitati din produsul realizat n procesulde productie de tipul j, 1 j n, (n general, activitatea de tipul j ). Presupunemaici ca aij depinde numai de tipul resursei si de tipul procesului de productie si nude nivelul la care urmeaza sa se desfasoare aceasta activitate.
Cu notatiile introduse, rezulta ca putem exprima cantitatea totala de resursa detipul i care va fi efectiv utilizata n procesele de productie:
ai1x1+ ai2x2+ . . . + ainxn.
Cum nu putem consuma resursa de tipuli mai mult decat cantitatea disponibilabi, rezulta ca trebuie satisfacute conditiile:
nj=1
aijxj bi, 1 i m. (1.1)
1
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
9/143
FOLOSIREA EFICIENT A A RESURSELOR LIMITATE 2
Deoarecexj reprezinta nivelul la care se desfasoara activitatea de tipul j, rezulta
ca trebuie sa fie de asemenea satisfacute conditiile:
xj 0, 1 j n. (1.2)Inegalitatile 1.1 sunt numite restrictiileproblemei, iar 1.2 sunt numite conditiile
de nenegativitateale problemei. Sistemul de inegalitati liniare poate avea o infinitatede solutii, o solutie unica sau nici o solutie (sistem incompatibil). Cazul cel maifrecvent pentru problemele practice corect puse este cazul n care sistemul 1.1, 1.2 areo infinitate de solutii. Prin urmare este posibil sa organizam procesele de productiepentru fabricarea sortimentelor de tipul j, 1 j n, ntr-o infinitate de moduri,respectand conditiile 1.1 de folosire a resurselor limitate.
Adoptarea unei variante de plan se face pe baza unor criterii economice, cum arfi: venitul realizat, beneficiul realizat, cheltuielile de productie, productia fizica, con-sumurile de materii prime si materiale, consumurile de energie etc. Vom presupunen cele ce urmeaza ca putem formula un singur criteriu pe baza caruia adoptamdecizia. Mai mult, vom presupune ca acest criteriu este reprezentat din punct devedere matematic de o functie liniara. Un exemplu de astfel de criteriu se obtine nmodul urmator. Daca notam prin cj beneficiul unitar adus de activitatea de tipul
j, 1 j n, atunci este clar ca beneficiul total este:n
j=1
cjxj. (1.3)
Problema care se pune este de a afla solutiile sistemului de inegalitati liniare1.1, 1.2 care asigura obtinerea valorii maxime pentru beneficiul total 1.3. Cu altecuvinte, din punct de vedere matematic se cere rezolvarea problemei:
supn
j=1cjxj
nj=1
aijxj bi, 1 i m,xj 0, 1 j n,
care este numitaproblema de programare liniarasau program liniar. Functia liniarace se doreste maximizata se numeste functie obiectivsau functia criteriusau, nca,
functia de eficient aa problemei.Problema mentionata poate fi rezolvata cu ajutorul algoritmului simplex sau
simplex dual. Acesta este prezentat pe larg n literatura de specialitate (Zidaroiu). Oserie de produse soft ca MATLABsauMAPLEau rutine specializate de rezolvarea problemelor de optimizare cu a jutorul acestor metode. Din acest motiv, omitemprezentarea rezolvarii complete a problemelor prin aceste metode.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
10/143
FORME ALE PROBLEMELOR DE PROGRAMARE LINIAR A 3
1.2. Forme ale problemelor de programare liniara
Forma standarda unei probleme de programare liniara este:
min(max)cxAx= bx 0
Remarcam ca o problema de maxim se poate transforma ntr-o problema de minimprin folosirea formulei max(f) = min(f).
Forma canonicaa unei probleme de programare liniara este:
min cxAx
b
x 0sau
max cxAx bx 0
Sintaxa MAPLE de scriere a formei canonice pentru problema de maxim este:
> standardize(multime de restrictii);
sau> convert(multime de restrictii,stdle); .
O restrictie a unei probleme de programare liniara este numitaconcordantadacaeste o inegalitate de tipul pentru problema de minim si o inegalitate de tipulpentru problema de maxim.
Forma mixtaa unei probleme de programare liniara contine restrictii si sub formade ecuatii.
Deoarece prin operatii matematice orice problema de programare liniara se poateaduce n forma canonica a problemei, pentru cazul de minim vom lucra numai cuastfel de probleme, adica cu probleme n forma canonica.
Definitia 1.2.1. Fie problema de programare liniara n forma standard atuncimultimea programeloreste definita ca:
P = {x Rn|Ax= b, x 0}.Un punct de minim global al functiei obiectiv z =c
x pe multimea programelorP este numit solutie optima, iar multimea programelor optime ale problemei va finotata cu:
P = {x P| minxP
c
x= c
x}.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
11/143
FORME ALE PROBLEMELOR DE PROGRAMARE LINIAR A 4
Definim solutia de baza a sistemului Ax= b ca o solutiex
Rn careia compo-
nentelor sale nenule i corespund coloane liniar independente. Daca B este o bazaformata cu coloanele aj1, . . . , ajm ale matricei A atunci sistemul de ecuatiiAx = bse poate scrie n forma explicita:
xB =B1b B1RxR
n care R este matricea obtinuta din A prin eliminarea coloanelorj1, . . . , jm.Notand:
B1b=xB, B1aj =yBj , 1 j n,rezulta ca:
xB =xB jR
yBj xj
sauxBi =x
Bi
jR
yBijxj, i B
undeB = {j1, . . . , jm} siR = {1, . . . , n} B. Solutia de baza corespunzatoare bazeiBestexB =xB sixR =0. Este clar ca aceasta solutie de baza este un program dacaeste ndeplinita conditia:
B1b 0.O bazaB care verifica inegalitatea de mai sus se numeste baza primal admisibila.
In problemele practice o astfel de baza se determina prin metoda bazei artificiale.De foarte multe ori nsa, aceasta este disponibila direct, baza primal admisibila fiind
matricea unitate.Avem urmatoarea teorema numita teorema fundamentala a programarii liniare.
Teorema 1.2.1. i) Daca problema de programare liniara:
min(max)cxAx= bx 0
are un program optim, atunci ea are un program de baza.ii) Daca problema de mai sus are un program optim, atunci ea are un program
optim de baza.
Algoritmul fundamental pentru rezolvarea problemelor de programare liniaramentionate se numeste algoritmul simplex primalsi a fost elaborat deGeorge Dantzign anul 1951. Algoritmul este descris n orice carte fundamentala de programareliniara si este implementat n majoritatea softurilor matematice de prelucrare dedate.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
12/143
ALGORITMUL SIMPLEX (DANTZIG) 5
1.3. Algoritmul simplex (Dantzig)
Pentru rezolvarea problemelor de programare liniara s-a impus algoritmul simplexdatorat lui G.B. Dantzig (1951). Aceasta metoda ne permite sa exploram n modsistematic multimea programelor de baza a unei probleme de programare liniaran forma standard prin trecerea de la un program de baza la un program de bazavecin, care este cel put in la fel de bun ca cel precedent. Metoda furnizeaza, deasemenea, criterii pentru punerea n evidenta a situatiei cand problema are optiminfinit precum si a cazului n care multimea programelor este vida.
PAS 0. Se pune problema de optimizat n forma standard:
infcTxAx= b,
x 0.(Daca problema are restrictii de forma unor inegalitati, atunci se transforma maintai toate inegalitatile n inegalitati de tipul ; scazandu-se variabilele artificialey,problema de maxim se va transforma n problema de minim etc.). Aeste o matricecumlinii si n coloane pentru care avemrang(A) = = m < n.Vom nota cuz functiaobiectiv adica z = cTx.
PAS 1. Se determina o bazaBprimal admisibila (fie este disponibila direct fie sedetermina cu ajutorul bazei artificiale prin metoda celor doua faze) si se calculeaza:
xB=B1b,
zB=cTB
xB,yBj =B
1aj, 1 j n,zBj cj, 1 j n.
Aceste valori se trec n tabelul simplex (tabelul 2.1) dupa care trecem la pasulurmator.
Vom nota cuB multimea indicilor j care determina matricea B si prin R ={1, . . . , n} B. Tabelul simplex initial are forma:
TABELUL 2.1c1 . . . cj . . . cn
V.B. V.V.B. x1 . . . xj . . . xn
c
B
x
B xB
y
B
1 . . . y
B
j . . . y
B
nz zB zB1 c1 . . . zBj cj . . . zBn cn
PAS 2. Daca zBj cj 0j R, ne oprim (STOP): xBeste program optim.In caz contrar se determina multimea (nevida):
R+= {j R|zBj cj >0}
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
13/143
ALGORITMUL SIMPLEX (DANTZIG) 6
si se trece la pasul urmator.
PAS 3. Daca exista j R+ pentru care yBj 0 ne oprim (STOP): problemaare optim infinit. In caz contrar, determinamk R+ cu criteriul de intrare n baza:
maxj
(zBj cj) =zBk ck
si r B+= {i B|yBik > 0} cu criteriul de iesire din baza:
miniB+
(xBiyBik
) = xBryBrk
ElementulyBrk se numeste pivot. Se trece la pasul urmator.
PAS 4. Se considera baza B obtinuta din B prin nlocuirea coloanei ar cucoloanaak, si se calculeaza valorile (prin formula de schimbare a bazei adica regula de
transformare a tabelului simplex)x
B, z
B, y
Bj , z
Bjcj si se trece la Pasul 2 nlocuind
peste tot baza B cu bazaB.
Calculele pot fi simplificate prin folosirea regulilor de transformare a tabeluluisimplex:
i) elementele situate pe linia pivotului se mpart la pivot;ii) elementele situate pe coloana pivotului devin zero, cu except ia pivotului care
devine 1;iii) celelalte elemente se transforma dupa regula dreptunghiului: daca ne ima-
ginam dreptunghiul a carui diagonala este determinata de elementul yBij care tre-
buie transformat si pivotul yBrk , atunci noua valoareyB
ijse obtine mpartind la pivot
diferenta dintre produsul elementelor yBijyB
rk situate pe diagonala considerata mai
sus si produsul yBrjyB
ik situat pe cealalta diagonala a dreptunghiului.
Observatii. i) Daca la sfarsitul algoritmului zBj cj < 0j R atunci solutiaproblemei este unica.
ii) Este posibil ca n cadrul algoritmului simplex sa apara fenomenul de ciclare(prin trecerea de la o baza la alta sa ajung ntr-o baza deja procesata). Exista maimulte tehnici de evitare a acestui fenomen asupra carora nu ne vom opri nsa.
iii) Se poate da si o interpretare geometrica a solut iilor unei probleme de progra-
mare liniara n cazul bidimensional. Domeniul de admisibilitate poate fi:-un poligon convex, iar cel putinunul dintre varfurile sale este solutiea problemei
de optimizare. Se poate ntampla ca solutia sa fie o latura a poligonului convex cedetermina domeniul de definitie, n acest caz avemmai multe solutii;
-un domeniu nemarginit, caz n care problema areoptim infinit;-multimea vida, caz n care problema de optimizare nu are solutie.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
14/143
DUALA UNEI PROBLEME DE PROGRAMARE LINIAR A 7
1.4. Duala unei probleme de programare liniara
Avand o problema de programare liniara, problema construita dupa urmatoarelereguli se numeste problema duala:
a) termenii liberi din problema primala devin coeficienti ai functiei obiectiv nproblema duala;
b) coeficientii functiei obiectiv din problema primala devin termeni liberi n prob-lema duala;
c) o problema de maximizare (minimizare) devine o problema de minimizare(maximizare);
d) matricea coeficientilor sistemului de restrictii din problema duala este trans-pusa matricei coeficientilor sistemului de restrictii primale;
e) variabile duale (primale) asociate unor restrictii primale (duale) concordantesunt supuse conditiilor de nenegativitate;
f) variabile primale (duale) asociate unor restrictii duale (primale) care suntrestrictii neconcordante sunt supuse conditiei de nepozitivitate;
g) variabile duale (primale) asociate unor restrictii primale (duale) care suntecuatii nu sunt supuse nici unei conditii privind semnul.
Remarcam ca duala unei probleme n forma canonica este tot n forma canonica.
Enuntam n continuare teorema fundamentala a dualitatii:
Teorema 1.4.1. Fiind dat cuplul de probleme duale:
min cx
Ax bx 0
si
max byAy cy 0
una si numai una din afirmatiile urmatoare este adevarat a:
a) ambele probleme au programe. In acest caz, ambele probleme au programeoptime si valorile optime ale functiilor obiectiv coincid;
b) una din probleme are programe, iar cealalta nu are. In acest caz, problemacare nu are programe are optim infinit;
c) nici una din probleme nu are programe.
Exista un algoritm numitalgoritmul simplex dualcare rezolva problema primalaprin intermediul problemei duale. Acelasi lucru putem sa-l afirmam si despre algo-ritmul simplex primal care rezolva problema primala, dupa care pune n evidenta
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
15/143
PROBLEMA DE TRANSPORT 8
solutia problemei duale. Programul MAPLE are o procedura de constructie a dualei.
Sintaxa acesteia este:
> dual(functia liniara, multime de restrictii, nume variabila duala);
1.5. Problema de transport
Sa presupunem ca exista m centre de aprovizionare (depozite) si n centre deconsum (beneficiari). Un produs omogen este depozitat n cantitatileai, 1 i m,n centrele de aprovizionare si este cerut n cantitatile bj, 1 j n, la beneficiari.Vom presupune ca sunt ndeplinite conditiile:
ai 0, 1 i m, bj 0, 1 j n,a1+ . . . + am= b1+ . . . + bn.
(1.4)
Cu alte cuvinte, presupunem ca disponibilitatile si cererile sunt nenegative, iardisponibilitatea egaleaza cererea totala. O astfel de problema de transport se numesteproblema de transport echilibrata.
Problema consta n organizarea transportului de la depozite la beneficiari astfelncat sa se obtina cheltuieli minime de transport.
Sa notam cu xij cantitatea (necunoscuta) care urmeaza sa fie transportata de ladepozitul i la beneficiarul j. Cantitatea ce se transporta de la depozitul i la totibeneficiarii trebuie sa egaleze disponibilitatea de la depozitul respectiv, adica:
nj=1
xij =ai, 1 i m. (1.5)
Analog, cererea totala la beneficiarul j trebuie sa fie egala cu cantitatea care setransporta de la toate depozitele la acest beneficiar, adica:
mi=1
xij =bj, 1 j n. (1.6)
Evident, cantitatile transportate sunt nenegative, adica:
xij 0, 1 i m, 1 j n. (1.7)Sistemul de inegalitati liniare 1.5-1.7 are n conditiile 1.4 o infinitate de solutii.
Ca si n cazul precedent, pentru adoptarea unui plan de transport vom introduceun nou criteriu economic. Sa notam pentru aceasta prin cij costul transportuluiunei unitati din produsul considerat de la depozitul i la beneficiarulj ; evident, si n
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
16/143
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
17/143
APLICATII 10
> obiectiv:= 2
x1+ 3
x2+ x3;
> restrictii:= {x1 + x2 + 3 x4>= 3, 2 x2 + 5x3 + 4 x4= 5, x1 + x3 minimize(obiectiv, restrictii union x1>= 0, x2 >= 0, x4
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
18/143
APLICATII 11
Exercitiul 1.6.5. Sa se minimizeze expresia 2x1+ 3x2 cu sistemul de restrictii:
x1 x2+ x3 = 1,x1+ x2 x4 = 1,x1 2x2+ x5= 1,2x1+ x3 x4= 2,xi 0, i= 1, . . . , 5.
Raspuns. In urma aplicarii algoritmului simplex primal obtinem solutia x1 =1, x2 = 0, x
3= 0, x
4 = 0, x
5= 0, iar valoarea minima a functiei obiectiv z
= 2.
Exercitiul 1.6.6. Rezolvati problema urmatoare:
min(x1
+ 6x2
),2x1+ x2 3,x1+ 3x2 4,x1, x2 0.
Raspuns. Vom rezolva problema grafic. Se va reprezenta ntr-un sistem de axede coordonate domeniul de admisibilitate. Pe acelasi grafic reprezentam si ecuatiax1+ 6x2= 0. Obtinem figura 1.1.
Figura 1.1: Domeniul de admisibilitate si functia obiectiv.
Vom duce drepte paralele cux2 = 16x1pana se intersecteaza cu domeniul de ad-misibilitate. Prima dreapta care realizeaza aceasta intersectie ne furnizeaza minimulfunctiei obiectiv zmin= 4.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
19/143
APLICATII 12
Solutia optima este x1= 4, x2= 0.
Exercitiul 1.6.7. Gasiti minimul functiei 2x1+ 3x2+ x3 cu restrictiile:
x1+ x2+ 3x4 3,2x2+ 5x3+ 4x4 = 5,x1+ x3 2,x1, x2, x3, x4 {0, 1}.
Exercitiul 1.6.8. Sa se rezolve problema de programare liniara n forma stan-dard:
min(2x1+ 3x2),
x1 x2+ x3= 1,x1+ x2 x4= 1,x1 2x2+ x5 = 1,2x1+ x3 x4 = 2,xi 0, 1 i 5.
Raspuns. Pentru rezolvarea problemei prin metoda simplex primal vom rezolvamai ntai problema:
min(x6+ x7+ x8),x1 x2+ x3+ x6= 1,
x1+ x2 x4+ x7= 1,x1 2x2+ x5 = 1,2x1+ x3 x4+ x8= 2,xi 0, 1 i 8.
(s-au introdus variabilele ecartx6, x7, x8 n restrictiile problemei initiale, cu exceptiacelei de a treia restrictie, unde variabia x5 este asociata unui vector unitar al ma-tricei coeficientilor). Baza primal admisibila este formata din coloanele matricei Acorespunzatoare variabilelor x6, x5, x7, x8. Tabelul simplex asociat 2.2 este:
TABELUL 2.2
V.B. V.V.B. x1 x2 x3 x4 x5 x6 x7 x8x6 1 1 1 1 0 0 1 0 0x7 1 1 1 0 1 0 0 1 0x5 1 1 2 0 0 1 0 0 0x8 2 2 0 1 1 0 0 0 1
4 4 0 2 2 0 0 0 0
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
20/143
APLICATII 13
Vectorul care intra n baza este evident a1 conform criteriului de intrare n
baza. Dupa cum ne indica criteriul de iesire din baza, oricare dintre variabilelede baza poate parasi baza: pentru a face o alegere, vom elimina din baza vectorulcoespunzator variabilei x6, adica a
6. Obtinem deci tabelul simplex 2.3:
TABELUL 2.3
V.B. V.V.B. x1 x2 x3 x4 x5 x6 x7 x8x1 1 1 1 1 0 0 1 0 0x7 0 0 2 1 1 0 1 1 0x5 0 0 1 1 0 1 1 0 0x8 0 0 2 1 1 0 2 0 1
0 0 4
2
2 0
4 0 0
Se observa ca tabelul simplex 2.3 obtinut ne arata ca valoarea functiei obiectiveste nula. Toate variabilele artificiale sunt nule, darx7 si x8 sunt nca variabile debaza. Se vede usor ca variabila x7 poate fi eliminata din baza si nlocuita cu x2,deoarece pivotul yB72 = 2 este nenul. Dupa calcule se obtine tabelul simplex 2.4:
TABELUL 2.4
V.B. V.V.B. x1 x2 x3 x4 x5 x6 x7 x8x1 1 1 0 1/2 1/2 0 1/2 1/2 0x2 0 0 1 1/2 1/2 0 1/2 1/2 0x5 0 0 0 3/2 3/2 1 3/2 1/2 0x8 0 0 0 0 0 0 2 2 1
0 0 0 0 0 0 2 2 0
Variabila artificiala x8nu mai poate fi eliminata dintre variabilele de baza, deoarecetoti coeficientii y8j, 1 j 5, sunt egali cu zero. Acest fapt ne arata ca ecuatiaa patra din problema initiala este o consecinta a celorlalte patru ecuatii (ecuatia apatra este suma primelor doua ecuatii, situatie ce putea fi observata de la nceput).In acest caz, ecuatia a patra poate fi neglijata si deci linia a patra a tabelului sim-plex poate fi eliminata; partea ramasa a tabelului simplex nu mai contine variabileartificiale de baza si, ca urmare, prima faza este terminata.
Vom trece acum la faza a doua a metodei, adic a la rezolvarea problemei initiale,
folosind drept baza initiala ultima baza obtinuta din tabelul 2.4, dupa eliminareaultimei linii.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
21/143
APLICATII 14
Tabelul simplex corespunzator este tabelul 2.5:
TABELUL 2.5
V.B. V.V.B. x1 x2 x3 x4 x5x1 1 1 0 1/2 1/2 0x2 0 0 1 1/2 1/2 0x5 0 0 0 3/2 1/2 1z 2 0 0 1/2 5/2 0
Deoarece zj cj 0 pentru totij, 1j 5, rezulta ca am obtinut programuloptim de baza (degenerat): x1 = 1, x
2 = 0, x
3 = 0, x
4 = 0, x
5 = 0, iar valoarea
optima a functiei obiectiv este z = 2.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
22/143
Capitolul 2
PROGRAMARE DINAMICA
2.1. Forma unei probleme de optimizare secventiala
Programarea dinamicaeste o metoda de rezolvare a unei clase de probleme, alcaror model matematic prezinta caracteristicile unui sistem secvential. Intr-o astfelde problema, la fiecare faza t T , cu T R, se alege o solutie (decizie, strategie,politica) xt dintr-o multime de solutii admisibileXt, Xt Mnt, unde M R iarnt N, putandu-se de fiecare data masura eficienta (sau utilitatea) ut a solutieialese. Problema de optimizareconsta n determinarea solutiei globale x = (xt)tTcare optimizeaza ofunctie eficient a globalafcare este definita cu ajutorulfunctiilorde eficient a partiala ut, t
T. Evolutia sistemului este descrisa si de familia pa-
rametrilor de stare (st)tT a caror lege de variatie este cunoscuta si dependentade deciziile alese (daca legea este determinista avem o problema de programare di-namica determinista, iar daca legea este probabilista avem o problema deprogramarestochastica). Sa notam cuSt multimea starilor la momentul t.
Definitia 2.1.1. (Caracteristicile unui sistem secvential.) O functies : T Stcus(t) =st t T, st St se numeste traiectoria, corespunzatoare deciziei globalex = (xt)tT, a sistemului secvential. Aceasta descrie starea sistemului de-a lungulntregii perioade de timp T, n conditiile alegerii deciziei x.
Avem n general:
xt = xt(st)uti :Sti1 Xti R, uti =uti(sti , xti)ti :Sti1 Xti Sti , ti =ti(sti1 , xti).
Traiectoria s depinde de starea initialast0 =s0 St0, t0 fiind momentul initial.
15
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
23/143
FORMA UNEI PROBLEME DE OPTIMIZARE SECVENTIAL A 16
Definitia 2.1.2. Se numeste traiectorie optima traiectoria s corespunzatoare
unei decizii optime xcare optimizeaza functia obiectiv.
Tehnica programarii dinamice consta n determinarea solutiilor optime globale sia valorii optime a functiei obiectiv, prin rezolvarea secventiala a unor probleme deoptimizare asociate problemei initiale, dar mult mai simple decat aceasta deoareceoptimul se calculeaza dupa o singura variabila. Bellmana formulat n 1957 principiuloptimalitatii: o conditie necesara ca o traiectorie s sa fie optima este cat1, t2T, t1< t2, s
|[t1,t2]sa fie traiectorie optima a sistemului restrictionat la intervalul[t1, t2],candst1 =s
(t1) adicaorice substrategie a unei strategii optime este ea nsasioptima.
Pentru a fixa ideile, n cele ce urmeaza, vom presupune ca avem de a face cu o
problema de minimizare, toate consideratiile fiind valabile fara nici un fel de restrictiisi pentru problema de maxim. Forma generala a unei probleme de optimizare (min-imizare) ce urmeaza a fi rezolvata prin aceasta tehnica este urmatoarea:
min{f(u1(s0, x1), . . . , un(sn1, xn))|x1 X1(s0), . . . , xn Xn(sn1)}si= i(si1, xi), i= 1, nsi Si, i= 1, n.
Problema de optimizare astfel definita se numeste efectiv decompozabila adicavectorul de stare si, la iesirea din faza i, nu depinde decat de vectorul de stare si1si de decizia xi, luata n faza i. Functiile ui suntfunctiile de eficient ala faza i cand
se ia decizia xi stiind ca vectorul de stare este si.Toate elementele descriptive ale unei probleme de optimizare sunt determinate
de o decizie aleasa si de starea initiala s0:
s1= 1(s0, x1) =1(s0, x1), u1(s0, x1) =
u1 (s0, x1), x1 X1(s0) =
X1(s0)
s2 = 2(1(s0, x1), x2) =2 (s0, x1, x2), u2(s1, x2),
u2(1(s0, x1), x2) =
u2(s0, x1, x2), x2 X2(1(s0, x1)) =X2(s0, x1)
...........................................
si = i(i1(s0, x1, x2, . . . , xi1), xi) =i(s0, x1, x2, . . . , xi),
ui(si1, xi) = ui(i1(s0, x1, x2, . . . , u xi1), xi) =
ui(s0, x1, . . . , xi),
xi Xi(i1(s0, x1, x2, . . . , xi1))=
Xi(s0, x1, . . . , xi1) pentrui = 2, n.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
24/143
TEOREMA DE OPTIM 17
Functia obiectiv se scrie:
f(u1(s0, x1),
u2 (s0, x1, x2), . . . ,
un(s0, x1, . . . , xn)) =
f (s0, x1, . . . , xn).
Definitia 2.1.3. O solutie (decizie) x(s0) = (x1(s0), . . . , x
n(s0)) admisibila se
spune ca este optima relativ la starea initiala s0 pentru o problema de optimizaresub forma secventiala, daca:
f (s0, x1(s0), . . . , x
n(s0)) = min{
f (s0, x1, . . . , x
n)|x1
X1(s0), . . . ,
. . . , xiXi(s0, x1, . . . , xi1), i= 1, n}.
Rezolvarea unei probleme de optimizare pusa n forma secventiala consta ngasirea unei solutii x(s0) = (x
1(s0), . . . , x
n(s0)), n functie de starea initiala s0,
astfel ncat functia de eficienta globala f sa fie optima.
2.2. Teorema de optim
Pentru a formula teorema de optim trebuie sa definim mai ntai notiunea defunctie decompozabila. In esenta, acest lucru nseamna ca problema se poate de-scompune ntr-un numar de faze.
Definitia 2.2.1. O functie f : D = S X Y R, unde X, Y si S suntmultimi nevide se numeste decompozabila daca exista functiileu, v: D R,u fiindconstanta n raport cu variabila y Y(existau : SX Rastfel ncatu (s,x,y) =u(s, x), (s,x,y) D) si o functie F :u(D)v(D) R, F(, .) monoton crescatoarepentru fiecare u(D), astfel ncat f(s,x,y) = =F(u(s, x), v(s,x,y))(s,x,y) D.
Teorema 2.2.1. ( Teorema de optim). DacaFeste decompozabila si dac a existapentru orices S:
minx,y f(s,x,y); minx F(u(s, x), miny v(s,x,y));minx miny f(s,x,y),
atunci pentru orices S avem:
minx,y
f(s,x,y) = minx
F(u(s, x), miny
v(s,x,y)).
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
25/143
PROGRAMARE DINAMIC A REGRESIV A 18
2.3. Programare dinamica regresiva
2.3.1. Ecuatiile programarii dinamice regresive
Pentru a pune sub forma unui algoritm problema secventiala trebuie sa existe oanume legatura de tip recursiv ntre functiile de eficienta trunchiate ale procesuluila fazele i:
fni+1(ui(si1, xi), . . . , un(sn1, xn)) =
=Fni+1(ui(si1, xi), fni(ui+1(si, xi+1), . . . , un(sn1, xn)),
unde prin fni+1 s-a notat functia de eficient a asociata procesului de decizie trun-chiat la fazele i, i+ 1, . . . , n pentru i = 1, 2, . . . , n
1, cu f1(un) = un si fn = f.
Aceasta proprietate se numeste proprietatea de decompozabilitatea functiei obiectiv.Ecuatia se rescrie:
fni+1(si1, xi, . . . , xn) = Fni+1(ui(si1, xi),
fni(i(si1, xi),
xi+1, . . . , xn)),
i= 1, n 1, si1 Si1, xi Xi(si1), xn Xn(sn1),
cuf1=un si
fn=
f=f.
Aplicam teorema de optim functiilor
fni+1
pentrui = 1, 2, . . . , n
1 :
min{
fni+1(si1, xi, . . . , xn)|xi, . . . , xn} =minxi
Fni+1(ui(si1, xi), min{fni(i(si1, xi), xi+1, . . .
. . . , xn)|xi+1, . . . , xn}).
Notam cu gni+1(si1) = min{fni+1(si1, xi, . . . , xn)|xi, . . . , xn}, valoarea optim-
ului procesului de decizie trunchiat la fazele i, i + 1, . . . , n . Avem:
gni(si1) =gni(i(si1, xi))
si obtinem:
gni+1(si1) = minxi
Fni+1(ui(si1, xi), gni(i(si1, xi)), i= 1, n 1cu
g1(sn1) = minxi
un(sn1, xn).
Aceste ecuatii se numesc ecuatiile programarii dinamice regresive.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
26/143
PROGRAMARE DINAMIC A REGRESIV A 19
2.3.2. Algoritmul rezolvarii problemelor de programare regre-
siva
Elementele prezentate n paragrafele precedente ne permit sa elaboram urmatorulalgoritm de rezolvare a problemelor de optimizare dinamice regresive.
PAS 0. Problema matematica se codifica sub forma unei probleme de pro-gramare liniara, punandu-se n evidenta functia obiectiv si sistemul de restrictiicorespunzator.
PAS 1. Se pune problema sub forma unui proces secvent ial de decizie urma-rindu-se urmatoarele elemente:
i) forma functionala a functiilor de transfer i: Si1 Xi Si:
si= i(si1, xi), i= 1, n.
ii) spatiul starilor posibile: S0, S1, . . . , S n;iii) spatiul deciziilor: Xi(si1);iv) functiile partiale de eficientaui(si1, xi), i= 1, 2, . . . , n;
v) functiile obiectiv ale proceselor trunchiate la fazele i, i+1, . . . , n:
fi(xi, . . . , xn)pentrui = 1, 2, . . . , n.
PAS 2. Se rezolva problema din faza n, adica se calculeaza:
min{f1(sn1, xn)|xn Xn(sn1)}
= min{un(sn1, xn)|xn Xn(sn1)} =g1(sn1),unde sn1 este parametru.
Deci pentrusn1 Sn1 se determina xn1(sn1) Xn(sn1), astfel ncat:
g1(sn1) =un(sn1, xn1(sn1)).
Se atribuie contorului i valoarea n1. Acest contor are semnificatia fazei i aprocesului secvential.
PAS 3. Se rezolva problema din faza i a carei necunoscuta este xi, iar si1este parametru. Deci pentrusi1 Si1, se determina valorile xi (si1) Xi(si1)pentru care:
gni+1(si1) = Fni+1(ui(si1, xi (si1)), gni(i(si1, x
i (si1)))
= min{fni+1(si1, xi, . . . , xn)|xi Xi(si1)}.
actualizeaza i := i + 1.PAS 4. Daca i >1 goto PAS 3.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
27/143
PROGRAMARE DINAMIC A REGRESIV A 20
Se determina x1(s0) si avem:
f (s0, x1(s0), . . . , x
n(s0)) =
min{
fn(s0, x1, . . . , xn)|x1, . . . , xn} = gn(s0), pentrus0 S0,
unde x2(s0) =x2(1(s0, x
1(s0)), etc.
PAS 5. Se optimizeaza pe multimea vectorilor initiali pentru a aflas0:
f (s0, x1(s
0), . . . , x
n(s
0)) = min
s0S0gn(s0) =gn(s
0),
atins pentru starea initiala s0.
PAS 6. Se scrie solutia optima:
x = (x1, . . . , xn)
unde x1 = x1(s
0), x
2 = x
2(1(s0, x
1(s0)), etc.
2.3.3. Aplicatii
Exercitiul 2.3.1. O unitate comerciala trebuie sa raspunda unei cereri de 25unitati dintr-un anumit tip de produs, cerere esalonata pe o perioada de 4 luni. La
nceputul fiecarei luni, unitatea se poate aproviziona cu orice cantitate din produsulrespectiv, la un pret ce variaza de la luna la luna, conform datelor din tabelul 3.1:
TABELUL 3.1
luna i 1 2 3 4
cererea 5 7 5
pret 12 10 9 10
Sa se determine politica optima de reaprovizionare a unitatii cu produsul respec-tiv, astfel ncat toate cererile sa fie satisfacute, stiind ca n depozitul respectiv segasesc la nceputul primei luni 3 unitati de produs si ca nu pot fi pastrate n depozit
mai mult de 9 unitati de produs, iar la sfarsitul ultimei luni toate produsele au fostvandute. Parametruleste un numar real strict pozitiv.
Raspuns.
Pas 0. Deoarece cererea trebuie sa fie de 25 unitati avem: 5 + 7 + + 5 = = 25deci = 8. Se codifica problema:
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
28/143
PROGRAMARE DINAMIC A REGRESIV A 21
Se noteaza cuxi numarul de unitati comandate la nceputul luniii si cusi stocul
existent la sfarsitul lunii i. Functia de minimizat este:
12x1+ 10x2+ 9x3+ 10x4,
putem deci presupune ca = 1 avand grija ca la final sa nmultim valoarea optimaa functiei obiectiv cu .
Avem: 3 + x1+ x2+ x3+ x4= 25 sau x1+ x2+ x3+ x4= 22.3 + x1 9 si 3 + x1 5 0 deci x1 [2, 6],3 + x1 5 + x2 9 si 3 + x1 5 + x2 7 0 deci x1+ x2 [9, 11],3+x15+x27+x3 9 si 3+x15+x27+x38 0 decix1+x2+x3 [17, 18]3 + x1 5 + x2 7 + x3 8 + x4 9 (echivalent cu 5 9 inegalitate care spune
ca dupa ce s-a efectuat comanda la nceputul lunii a 4-a mai este de satisfacut ocerere de 5 unitati de produs) si 3 + x1 5 + x2 7 + x3 8 + x4 5 = 0 (ecuatiece constituie o verificare partiala).
Problema de minimizat devine:
min(12x1+ 10x2+ 9x3+ 10x4)2 x1 69 x1+ x2 114 x4 5x1+ x2+ x3+ x4 = 22.
Pas 1. Se determina spatiul starilor Si, i= 0, 4:
s0= 3 S0= {3},s1= s0+ x1 5 =x1 2 S1= [0, 4],s2= s1+ x2 7 =x1+ x2 9 S2 = [0, 2],s3= s2+ x3 8 =x1+ x2+ x3 17 S3= [0, 1],s4= s3+ x4 5 =x1+ x2+ x3+ x4 17 5 = 0 S4= {0}.Se determina spatiul deciziilor Xi(si1), i= 1, n:x1 X1(s0) = [5 s0, 9 s0] = [2, 6],x2 X2(s1) = [7 s1, 9 s1],x3 X3(s2) = [8 s2, 9 s2],x4 X4(s3) = {5 s3}Functiile de transfer: i(si1, xi), i= 1, n:
1(s0, x1) =s0+ x1 5,2(s1, x2) =s1+ x2 7,3(s2, x3) =s2+ x3 8,4(s3, x4) =s3+ x4 5 = 0.Functiile partiale de eficienta sunt:u1(s0, x1) = 12x1,
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
29/143
PROGRAMARE DINAMIC A REGRESIV A 22
u2(s1, x2) = 10x2,
u3(s2, x3) = 9x3,u4(s3, x4) = 10x4, si functiile de eficienta ale proceselor de decizie trunchiate la
fazele{i , . . . , 4} (pentrui = 1, . . . , 4) sunt:
f4= 12x1+ 10x2+ 9x3+ 10x4,f3= 10x2+ 9x3+ 10x4,f2= 9x3+ 10x4,f1= 10x4.
Pas 2. Se rezolva problema:
min{
f1 (sn1, xn)|xn Xn(sn1)} = min{u4(s3, x4)|x4 X4(s3)} == min{10x4|x4 {5 s3}} = 10(5 s3) = 50 10s3,
minim atins pentru x4(s3) = 5 s3.Pas 3/4. Se rezolva problema:
min{
f3|x3 X3(s2)} = min{9x3+ 50 10s3|x3 [8 s2, 9 s2]}= min{9x3+ 50 10(s2+ x3 8)|x3 [8 s2, 9 s2]}= min{x3 10s2 + 130|x3 [8 s2, 9 s2]} =(9 s2) 10s2 + 130 =
= 121 9s2,minim atins pentru x3(s2) = 9 s2.Se rezolva problema:min{
f2|x2 X2(s1)} = min{10x2+ 121 9s2|x2 [7 s1, 9 s1]}= min{10x2+ 121 9(s1+ x2 7)|x2 [7 s1, 9 s1]}= min{x2 9s1 +184|x2 [7 s1, 9 s1]} = 7 s1 9s1 + 184 = = 10s1 +191,minim atins pentru x2(s1) = 7 s1.Se rezolva problema:
min{
f1|x1 X1(s0)} = min{12x1+ 191 10s1|x1 [2, 6]}= min{12x1+ 191 10(s0+ x1 5)|x1 [2, 6]}= min{2x1 10s0+ 241|x1 [2, 6]} = 243 10s0,minim atins pentru x1(s
0) = 2, s
0= 3.
Pas 5. Avem:s1= s
0+ x
1 5 = 0 deci x2(s1) = 7,
s2= s1+ x
2 7 = 0 deci x3(s2) = 9,
s3= s2+ x
3 8 = 1 deci x4(s3) = 4.
Pas 6. Solutia optima x = (2, 7, 9, 4) iar traiectoria optima este s = =(0, 0, 1, 0).
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
30/143
PROGRAMARE DINAMIC A REGRESIV A 23
Exercitiul 2.3.2. Un depozit trebuie sa raspunda unei cereri de marfa totale de
unitati de produs de la m beneficiari (cererea fiecarui beneficiar este de i unitatide produs). Daca costul de aprovizionare si transport al unei unitati de produs labeneficiarul i este i, iar depozitul dispune initial de unitati de produs si dacaacesta nu poate detine n stoc mai mult de unitati de produs sa se determinepolitica optima de reaprovizionare cu produsul respectiv astfel ncat toate cererilesa fie satisfacute. La final mai exista n stoc unitati de produs.
Indicatie. Se noteaza cuxi numarul de unitati de produs comandate la nceputullivrariii si cusi stocul existent dupa livrareai. Problema de programare ce trebuierezolvata este:
minmi=1
iximi=1
xi= + ,ji=1
i ji=1
xij1i=1
i+ j= 1, m,xi 0i= 1, m.
unde =mi=1
i. Se vor pune n evidenta functiile reciproce de transfer, functiile
partiale de eficienta, functiile de eficienta ale proceselor trunchiate, spatiul starilorsi spat iile de decizie.
Problema se va rezolva prin metoda programarii regresive n n faze.
Exercitiul 2.3.3. Sa se gaseasca o planificare optima unei investitii de 5 mil-ioane dolari pentru construirea a trei obiective cunoscand randamentele investitiilorpe obiective, asa cum sunt prezentate n tabelul 3.2.
TABELUL 3.2
Investitii Obiectiv 1 Obiectiv 2 Obiectiv 3
0 0 0 0
1 0, 20 0, 23 0, 19
2 0, 35 0, 34 0, 373 0, 51 0, 50 0, 49
4 0, 68 0, 63 0, 65
5 0, 75 0, 79 0, 80
Raspuns. Modelul matematic al problemei este:
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
31/143
PROGRAMARE DINAMIC A REGRESIV A 24
max(r1(x1) + r2(x2) + r3(x3))x1+ x2+ x3 = 5,xi {0, 1, 2, 3, 4, 5}, i= 1, 2, 3, 4, 5.
In vederea rezolvarii problemei cu ajutorul programarii dinamice, se pune maintai problema sub forma unui proces secvential de decizie. Pentru realizarea acestuiscop, se noteaza cu si, i = 1, 2, 3, suma investita n primul obiectiv, n primul si aldoilea, si respectiv suma investita n cele trei obiective. Avem: s0= 0, s1 = s0 + x1,s2= s1+ x2, s3= s2+ x3.
Folosind aceste egalitati, obtinem cu ajutorul sistemului de restrictii, S0 ={0},S1
= S2
={
0, 1, 2, 3, 4, 5}
, S3
={
5}
.X1(s0) = {0, 1, 2, 3, 4, 5}, X2(s1) = {0, . . . , 5 s1}, X3(s2) = {5 s2}.Remarcam ca avem urmatoarele functii de transfer:1(s0, x1) =s0+ x1, 2(s1, x2) =s1+ x2, 3(s2, x3) =s2+ x3.Functiile partiale de eficienta, precum si functiile de decizie ale proceselor de
decizie trunchiate la fazele{i , . . . , 3} (pentrui = 1, . . . , 3) sunt urmatoarele:u1(s0, x1) =r1(x1), u2(s1, x2) =r2(x2), u3(s2, x3) =r3(x3),
f3=r1(x1) + r2(x2) + r3(x3),
f2=r2(x2) + r3(x3),
f1=r3(x3).Se constata ca problema este decompozabila regresiv cuFi(, ) = +, unde
i= 2, 3. Se trece acum la rezolvarea problemelor de optim corespunz atoare fiecareifaze, folosind ecuatiile programarii regresive si obtinem:
Faza 3. Avem:
g1(s2) = max{r3(x3)|x3 X3(s2)} =r3(5 s2),obtinut pentru x3(s2) = 5 s2.
Faza 2. Avem:
g2(s1) = max{r2(x2) + g1(s1+ x2)|x2 X2(s1)}= max{r2(x2) + r3(5 s1 x2)|x2 X2(s1)}.
Avem
g2(0) = max{0, 80;0, 88;0, 83;0, 87;0, 82;0, 79} = 0, 88 pentrux2(0) = 1;g2(1) = max{0, 65;0, 72;0, 71;0, 69;0, 63} = 0, 72 pentru x2(1) = 1;g2(2) = max{0, 49;0, 60;0, 53;0, 50} = 0, 60 pentrux2(2) = 1;g2(3) = max{0, 37;0, 42;0, 34} = 0, 42 pentru x2(3) = 1;g2(4) = max{0, 19;0, 23} = 0, 23 pentrux2(4) = 1;g2(5) = max{0} = 0 pentru x2(5) = 1.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
32/143
PROGRAMARE DINAMIC A PROGRESIV A 25
Faza 1. Avem:
g3(s0) = max{r1(x1) + g2(s0+ x1)|x1 X1(s0)}= max{0, 88;0, 92;0, 95;0, 93;0, 91;0, 75} = 0, 95,
obtinut pentru x1(s0) = 2,undes
0= s0 = 0.Avem n continuare, s
1 = =s
0+x
1= 2,
de undex2(s1) = 1;s
2 = s
1+x
2= 3,de undex
3(s
2) = = 5s2 = 2;s3= s2+s3= 5.
In concluzie, am obtinut: max(r1(x1) + r2(x2) + r3(x3)) = 0, 95, pentru solutiaoptima unica x = (x1, x
2, x
3) = (2, 1, 2), iar traiectoria optima a procesului este
s = (2, 3, 5).
2.4. Programare dinamica progresiva2.4.1. Ecuatiile programarii dinamice progresive
Procedura iterativa descrisa n paragraful anterior este valabila fara nici o restrictieasupra starii initiale sau finale. Aceste doua stari au n mod evident, roluri impor-tante, asa cum s-a vazut pentru starea s0. In timp ce s1, . . . , sn1 sunt stari deintrare si iesire, s0 este numai stare de intrare pentru faza 1 a problemei, iar snnumai stare de iesire pentru faza n a problemei.
Din punct de vedere matematic singurul lucru care deosebestes0de sneste sensulde parcurs adoptat pentru procedura de rezolvare, sens care a fost impus de ecuat iile:
si= i(si1, xi), i= 1, n,
ce conduc la o procedura de rezolvare de la ultima faza spre prima faza a problemei,altfel spus, am mers spre trecut. In anumite probleme se pot pune restrictii asuprastarilor s0 si/sausn.
Daca s0 este impusa, optimizarea din ultima faza a problemei conduce la unsingur gn(s0) deoarece s0 nu mai este parametru, iar n faza 1 luam direct s0 =s
0.
Deci schema propusa este viabila.Daca sn este impusa, adica sn = s
n cu s
n dat, trebuie ca starea initiala s0 si
solutia optimax(s0) sa satisfaca relatia:
sn = n(n1(. . . 2(1(s0, x1(s0)), x
2(s0)), . . . , x
n(s0)).
Aceasta relatie nu poate fi verificata decat la sfarsitul procedurii, lucru care sporestetimpul de procesare. Metoda de reducere la cazul precedent este mult mai eficace,daca vom reusi sa schimbam sensul n care au fost facute calculele adica sa mergemspre viitor prin folosirea functiilor reciproce de transfer:
si1=i(si, xi), i= 1, n.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
33/143
PROGRAMARE DINAMIC A PROGRESIV A 26
Functiile elementare de eficientaui,pentrui = 1, . . . , n ,respectiv functia obiectiv
globala f, devin ui(i(si, xi), xi) =ui(si, xi), pentru i = 1, . . . , n , respectiv:
f(u1(s0, x1), . . . , un(sn1, xn)) = f(u1(s1, x1), . . . ,
un(sn, xn))
=
f (sn, x1, . . . , xn),
unde de data aceasta, n mod similar cu ceea ce s-a aratat anterior, toate elementeledescriptive ale problemei pot fi exprimate ca functie de decizie aleasa si starea s0.
Similar se defineste decompozabilitatea progresiva si se ajunge la ecuatiile pro-gramarii dinamice progresive.
2.4.2. Algoritmul rezolvarii problemelor de programare progre-siva
Elementele prezentate n paragrafele precedente ne permit sa elaboram urmatorulalgoritm de rezolvare a problemelor de optimizare dinamice progresive.
PAS 0. Problema matematica se codifica sub forma unei probleme de pro-gramare liniara, punandu-se n evidenta functia obiectiv si sistemul de restrictiicorespunzator.
PAS 1. Se pune problema sub forma unui proces secvential de decizie avandu-sen vedere urmatoarele elemente:
i) forma functionala a functiilor reciproce de transfer i:Si Xi Si1:
si1=i(si, xi), i= 1, n.
ii) spatiul starilor posibile: S0, S1, . . . , S n;
iii) spatiul deciziilor:Xi(si);
iv) functiile partiale de eficientaui(si, xi), i= 1, 2, . . . , n;
v) functiile obiectiv ale proceselor secventiale trunchiate la fazele 1, . . . , i :
fi(x1, . . . , xi) pentrui = 1, 2, . . . , n.
PAS 2. Se rezolva problema din faza 1, adica se calculeaza:
min{
f1(s1, x1)|x1X1(s1)} = min{u1(s1, x1)|x1X1 (s1)} =g1(s1),
unde sn1 este parametru. Deci pentrus1 S1 se determina valoarea x1(sn)X1
(s1), astfel ncat:
g1(s1) =u1(s1, x
1(s1)).
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
34/143
PROGRAMARE DINAMIC A PROGRESIV A 27
Se atribuie contorului i valoarea 2. Acest contor are semnificatia fazeii a procesului
secvential.PAS 3. Se rezolva problema din faza i a carei necunoscuta este xi, iar si este
parametru. Deci pentrusi Si, se determina xi (si) Xi(si) astfel ncat:
gi(si) =Fi(
ui(si, x
i (si)), gi1(
i(si, x
i (si))).
actualizeaza i := i + 1;PAS 4. Daca i < n goto PAS 3.PAS 5. Se determina xn(sn) Xn(sn) cusn= sn si avem:
f (sn, x
1(s
n), . . . , x
n(s
n)) = min{
fn(sn, x1, . . . , xn)|x1, . . . , xn} =gn(s
n),
unde xn1(sn1) =x
n1 = x
n1(n(s
n, x
n)), etc.
PAS 6. Se scrie solutia optima:
x = (x1, . . . , xn)
unde xn = xn(s
n), x
n1= x
n1(n(s
n, x
n)), etc.
Observatii. i) Daca starile s0 sau sn sunt cunoscute, se merge de la starea ne-cunoscuta spre starea cunoscuta.
ii) Daca ambele stari sunt impuse si daca se pot defini functiile de transfer atatntr-un sens cat si n celalalt atunci se poate opta pentru oricare dintre cele dou ametode de rezolvare, adica progresiv sau regresiv.
2.4.3. Aplicatii
Exercitiul 2.4.1. Aplicatia similara celei de la paragraful de aplicatii core-spunzator programarii dinamice regresive.
Raspuns. Pasul 0 este identic cu cel de la rezolvarea aplicatiei de la capitolulprogramarii regresive.
Pasul 1. Se determina functiile reciproce de transfer:
1(s1, x1) =s1 x1+ 5,2(s2, x2) =s2 x2+ 7,3(s3, x3) =s3 x3+ 8,4(s4, x4) =s4 x4+ 5,Functiile partiale de eficienta sunt:u1(s1, x1) = 12x1,
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
35/143
PROGRAMARE DINAMIC A PROGRESIV A 28
u2(s2, x2) = 10x2,
u3(s3, x3) = 9x3,u4(s4, x4) = 10x4,
Functiile de eficienta ale proceselor trunchiate la fazele 1, . . . , i (pentru i =1, . . . , 4) sunt:
f1= 12x1,
f2= 12x1+ 10x2,
f3= 12x1+ 10x2+ 9x3,
f4= 12x1+ 10x2+ 9x3+ 10x4.
Noile spatii de decizie se determina succesiv:
Dins0= 3 rezulta s1 x1+ 5 = 3 saux1= s1+ 2 de unde x1 {s1+ 2},dins1 [0, 4] rezultas2 x2+ 7 [0, 4] de unde x2 [s2+ 3, s2+ 7],dins2 [0, 2] rezultas3 x3+ 8 [0, 2] de unde x3 [s3+ 6, s3+ 8],dins3 [0, 1] rezultas4 x4+ 5 [0, 1] de unde x4 [s4+ 4, s3+ 5].Pas 2. Se rezolva problema din faza 1 adica se calculeaza:
min{
f1|x1X1(s1)} = min{12x1|x1 {s1+ 2}} = 12s1+ 24,minim atins pentru x1(s1) =s1+ 2.
Pas 3/4. Se rezolva problema:
min{
f2|x2X2(s2)} = min{12x1+ 10x2|x2 [s2+ 3, s2+ 7]}= min{10x2+ 12s1+ 24)|x2 [s2+ 3, s2+ 7]}= min{10x2+ 12(s2 x2+ 7) + 24)|x2 [s2+ 3, s2+ 7]}= min{2x2+ 12s2+ 108|x2 [s2+ 3, s2+ 7]}= 2(s2+ 7) + 12s2+ 108 = 10s2+ 94,minim atins pentru x2(s2) =s2+ 7.
Se rezolva problema:
min{
f3|x3X3(s3)} = min{12x1+ 10x2+ 9x3|x3 [s3+ 6, s3+ 8]}= min{9x3+ 10s2+ 94|x3 [s3+ 6, s3+ 8]}= min{9x3+ 10(s3 x3+ 8) + 94|x3 [s3+ 6, s3+ 8]}= min{x3+ 10s3+ 174|x3 [s3+ 6, s3+ 8]}=
s3
8 + 10s3+ 174 = 9s3+ 166,
minim atins pentru x3(s3) = s3+ 8.
Se rezolva problema:
min{
f4|x4X4(s4)} = min{12x1+ 10x2+ 9x3+ 10x4|x4 [s4+ 4, s3+ 5]}= min{10x4+ 9s3+ 166|x4 [s4+ 4, s3+ 5]}= min{10x4+ 9(s4 x4+ 5) + 166|x4 [s4+ 4, s3+ 5]}
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
36/143
PROGRAMARE DINAMIC A PROGRESIV A 29
= min
{x4+ 9s4+ 211
|x4
[s4+ 4, s3+ 5]
}= 10s4+ 215 = 215,minim atins pentru x4(s
4) = s
4+ 4 = 4, unde s
4= 0.
Pas 5. Avem:s3= s
4 x4+ 5 = 1 si x3= s3+ 8 = 9,
s2= s3 x3+ 8 = 0 si x2= s2+ 7 = 7,
s1= s2 x2+ 7 = 0 si x1= s1+ 2 = 2.
Pas 6. Solutia optima este:x = (2, 7, 9, 4), iar traiectoria optima s = (0, 0, 1, 0), deci s-a obtinut aceeasi
solutie ca n rezolvarea problemei prin metoda regresiva.
Exercitiul 2.4.2. Un depozit trebuie sa raspunda unei cereri de marfa totale de
unitati de produs de la m beneficiari (cererea fiecarui beneficiar este de i unitatide produs). Daca costurile de transport al unei unitati de produs la beneficiarul ieste i si daca depozitul dispune initial de unitati de produs, iar daca acesta nupoate detine n stoc mai mult deunitati de produs sa se determine politica optimade reaprovizionare cu produsul respectiv astfel ncat toate cererile sa fie satisfacute.In final depozitul nu mai are nici o cantitate n stoc.
Indicatie. Vom nota cuxinumarul de unitati de produs comandate la nceputullivrariii si cusi stocul existent dupa livrareai. Problema de programare ce trebuierezolvata este:
minmi=1
iximi=1
xi= ,ji=1
i ji=1
xjj1i=1
i+ j= 1, m,xi 0i= 1, m.
unde =mi=1
i. Se vor pune n evidenta functiile reciproce de transfer, functiile
partiale de eficienta, functiile de eficienta ale proceselor trunchiate, spatiul starilorsi spat iile de decizie.
Problema se poate rezolva si prin programare dinamica progresiva n n faze sievident si prin metoda programarii dinamice regresive sau cu ajutorul algoritmilorsimplex primal ori simplex dual prin aducerea acesteia la forma standard.
Exercitiul 2.4.3. Rezolvati numeric prin programare dinamica regresiva si pro-gresiva problema anterioara pentrum = 3, = 25 (1= 10, 2 = = 8, 3= 7), 1=
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
37/143
PROGRAMARE DINAMIC A PROGRESIV A 30
3, 2 = 10, 3 = 4, = 3 si = 10. Aplicati pentru rezolvarea problemei algoritmul
simplex primal. Scrieti duala problemei de programare liniara asociata. Rezolvatiprogramul dual.
Indicatie. Aplicand exercitiul precedent restrictia a doua devine:
1 x1 ,
sau 10 3 x1 10 3 deci x1= 7. Restrictia a treia devine:
1+ 2 x1+ x2 1+ ,
sau 10 + 8
3
3 + x2
10 + 10
3 deci 12
x2
20 etc.
Exercitiul 2.4.4. Generalizati problema de la exercitiul 3.4.2 la o problema cun depozite. Rezolvati aceasta problema prin metoda programarii dinamice si apoiprin metoda de rezolvare a problemelor clasice de transport.
Exercitiul 2.4.5. Un tren de marfa cu capacitatea maxima z trebuie sa trans-porte diferite cantitati deNmarfuri diferite. Sa notam cuvivaloarea celui de ali-leatip de marfa si cu wi greutatea sa. Sa se determine ncarcatura de valoare maxima.Aplicatie numerica N = 3, z = 100 t, v1 = 10$, v2 = 30$, v3 = 5$, w1 = 150 t,w2 = 20 t, w3= 30 t.
Indicatie. Daca notam cu xi numarul articolelor din marfa i care sunt ncarcateatunci problema de programare liniara de rezolvat este:
maxNi=1
xivi,
Ni=1
xiwi z,xi 0, i= 1, N .
Problema se poate rezolva prin metodele programarii dinamice sau cu algoritmulsimplex.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
38/143
Capitolul 3
TEORIA JOCURILOR
3.1. Notiuni introductive
De foarte multe ori suntem pusi n fata unor situatii conflictuale a caror evolutieulterioara depinde de deciziasauplanul adoptat, numita si strategie. Prin termenulde evolutiese ntelege modificarea unei functii obiectiv numita n acest caz functiede pierdere sau castig, deci prin joc n cele ce urmeaza se ntelege acea situatiecare functioneaza dupa reguli bine definite, n care doua sau mai multe elemente de-cizionale, numitejucatori, aleg o decizie dintr-o multime de variante bine specificate.Deoarece jocurile de care ne vom ocupa au la baza aceste elemente decizionale, ele se
vor numi jocuri strategice. Spunem despre strategia unui joc ca este ostrategie puradaca unul dintre adversari alege una din cele m variante dupa care jocul se opreste.Strategia mixta presupune continuarea partidei, iar alegerea variantei se face cu oanumita probabilitate. Fiecare din partile implicate n joc urmareste optimizareafunctiei obiectiv, iar strategia care realizeaza aceasta optimizare se numeste strategieoptima.
Din punct de vedere al castigului jocurile se clasifica n:
-jocuri cu suma nula: sunt acele jocuri n care suma pierderilor fiecarui jucatoreste egala cu suma castigurilor tuturor jucatorilor;
-jocuri fara suma nula: sunt acele jocuri n care o parte din pierderea si/sau
castigul unui jucator nu se regaseste la ceilalti jucatori.O alta clasificare este dupa cardinalul numarului de strategii: jocuri finite sau
infinite.
Fie X si Y strategiile pure a doi jucatori, fie a X si b Ystrategii pure alesede catre acestia. Vom nota cuLa(a, b) si Lb(a, b) pierderile corespunzatoare fiecarui
jucator, castigul fiind considerat o pierdere negativa. Suma pierderilor celor doi
31
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
39/143
PRINCIPIUL MINIMAX 32
jucatori este:
La(a, b) + Lb(a, b).
Daca jocul este cu suma nula atunci La(a, b) + Lb(a, b) = 0.Jocurile de tip poker sunt jocuri cu suma nula, iar jocurile de tip Casino sunt
fara suma nula (se platesc impozite catre stat sau se platesc taxe catre proprietaruljocului). Formalizand cele definite avem:
Definitia 3.1.1. Se numestejoctripletulJ= (X , Y , L) undeX= {a1, . . . , am}si Y ={b1,...,bn} sunt multimile de strategii pure ale celor doi jucatori, iar L :X Y R este functia de castig care se poate exprima sub forma matriceala:
Q= q11 ... q 1n... ... ...
qm1 ... q mn
n care qij =L(ai, bj), i = 1, m , j = 1, n. Forma matriceala a unui joc se numesteforma normala. Matricea jocului este alcatuita n raport cu jucatorul A numit
jucator maximizant. Jucatorul B se va numi jucator minimizant, iar matricea sa vaavea elementeleqij.
Exemplul 3.1.1. Jocul consta n aruncarea monedei n care fiecare jucatorpoate alege, independent de celalalt stema S sau banul B. Daca alegerile coin-cid, atunci jucatorul 2 primeste de la jucatorul 1 sumax. In caz contrar jucatorul 1
primeste de la jucatorul 2 sumax. Matricea jocului este:
Q=
x x
x x
.
3.2. Principiul minimax
Teoria jocurilor are ca rol elaborarea unor planuri rat ionale de actiune pentrucazurile conflictuale. Astfel, principiul adoptat este principul minimizarii pierderiimaxime numit si principiul minimax. Jucatorul A actioneaza astfel ncat sa maxi-mizeze cel mai mic castig pe care-l poate obtine de la jucatorul B, iar jucatorul B
actioneaza astfel ncat sa minimizeze pierderea sa maxima.Valoarea:
= maxi
minj
qij
se numeste valoarea inferioara a jocului si reprezinta cel mai mic castig pe careA lpoate avea de la B , iar valoarea:
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
40/143
STRATEGII MIXTE SI VALOAREA JOCULUI 33
= minj
maxi
qij
se numestevaloarea superioara a joculuisi reprezinta cea mai mare pierdere pe careB o poate avea.
Jocurile pentru care = se numesc jocuri cu punct sa, iar valoarea comuna aacestor doua valori se numeste valoarea jocului. Elementul care realizeaza aceastaegalitate se numeste punct sa.
O strategie ai a jucatorului A se numeste dominantapentru strategia aj dacaqik qjk pentru orice k = 1, n.Strategiile dominate vor fi eliminate din joc de catreA (acesta doreste sa castige cat mai mult) strategiile dominante ale lui B vor fi
eliminate din politica sa pentru ca duc la pierderi mai mari.
3.3. Strategii mixte si valoarea jocului
Jocurile cu punct sa reprezinta o clasa particulara de jocuri si se pune n modnatural ntrebarea daca, n ipoteza repetarii partidelor, nu se poate gasi o strategieprin care jucatorul A sa obtina un castig mai mare decat cel asigurat prin criteriulminimax. Vom numi strategie mixta o combinatie probabilista de strategii pure.Strategiile mixte au dublu rol:
1. de a mpiedica adversarul sa cunoasca strategia aleasa;
2. de a mari castigul garantat de valoarea inferioara a jocului.FieX= (x1,...,xm)
vectorul probabilitatilor cu care jucatorulAalege strategiilepure{a1,...,am} si Y = (y1,...,yn) vectorul probabilitatilor cu care jucatorul Balege strategiile pure{b1,...,bn}. Avem:
xi 0, i= 1, mmi=1
xi= 1,
si
yj 0, j = 1, nn
j=1 yj = 1.
Castigul mediu realizat de catre A cand el foloseste strategia mixta X, iar Bstrategia bj va fi:
M(X, j) =mi=1
qijxi.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
41/143
TEOREMA FUNDAMENTAL A A TEORIEI JOCURILOR 34
Similar, castigul mediu realizat de A cand el foloseste strategia ai,iar B foloseste
strategia mixtaY va fi:
M(i, Y) =n
j=1
qijyj.
Valoarea medie a joculuiva fi:
M(X, Y) =n
j=1
mi=1
qijxiyj =mi=1
nj=1
qijxiyj,
sau matriceal:M(X, Y) =X
QY.
3.4. Teorema fundamentala a teoriei jocurilor
Teorema 3.4.1. (Valoarea inferioara si valoarea superioara a jocului). FieX,Y submultimi ale luiR si fieL: X Y R. Daca exista marimile:
maxxX
[minyY
L(x, y)],
minyY
[maxxX
L(x, y)],
atunci:maxxX
[minyY
L(x, y)] minyY
[maxxX
L(x, y)].
Definitia 3.4.1. (Punct sa). Punctul (x0, y0) este punct sa al functiei L daca:
L(x, y0) L(x0, y0) L(x0, y).
Teorema 3.4.2. (Conditii necesare si suficiente pentru existenta punctelor sa).FieX, Y submultimi ale luiR si fieL: X Y R. Daca exista marimile:
maxxX
[minyY
L(x, y)],
minyY
[maxxX
L(x, y)],
atunci conditia necesara si suficienta caL sa aib a punctul(x0, y0) punct sa este:
maxxX
[minyY
L(x, y)] = minyY
[maxxX
L(x, y)] =L(x0, y0).
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
42/143
REZOLVAREA JOCURILOR MATRICEALE 35
Teorema 4.4.2 ne spune: conditia necesara si suficienta ca L sa aiba punctul
(x0, y0) punct sa este ca valoarea inferioara a jocului sa fie egala cu valoarea sasuperioara.
Teorema 3.4.3. (Teorema fundamentala a teoriei jocurilor). Fie jocul J =(X , Y , L). Atunci exista o perecheX0, Y0 de strategii mixte optime astfel ncat:
maxXSm
[ minYSn
M(X, Y)] = minYSn
[ maxXSm
M(X, Y)] =M(X0, Y0) =v,
unde Sm si Sn sunt submultimi ale spatiilor euclidiene m-dimensionale respectivn-dimensionale.
Valoareav se numeste valoarea jocului.
Observatii. i) Un joc nu poate avea decat o singura valoare, chiar daca are maimulte strategii optime mixte.
ii) Conditia necesara si suficienta ca v sa fie valoarea jocului si X0, Y0 sa fiestrategii mixte este ca:
M(i, Y0) v M(X0, j), 1 i m, 1 j n.
3.5. Rezolvarea jocurilor matriceale
3.5.1. Formularea problemei de optimizare
Fie un joc cu matricea Q = (qij). Daca jucatorul A foloseste strategiile pure aicu probabilitatile xi, i = 1, . . . , m atunci acesta poate spera un castig de cel putinv, care este egal cu valoarea jocului adica:
x
Q vmi=1
xi= 1
xi 0, i= 1, m
unde v = (v , . . . , v)
iar a b def ai bii.Similar, daca jucatorul B utilizeaza strategiile pure bj cu probabilitatile yj ,
1 j n, el se poate astepta la o pierdere cel mult egala cu valoarea v a jocului:
Qy vn
j=1yj = 1
yj 0, j = 1, n
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
43/143
APLICATII 36
3.5.2. Reducerea la probleme de programare liniara
Pentru a transforma cele doua sisteme n modele de programare liniara este nece-sar ca valoarea joculuiv sa fie strict pozitiva. In acest sens se pot folosi urmatoareleobservatii:
i) daca fiecarui element al matricei Q i se adauga o constanta k, atunci valoareajocului devine v + k, iar strategiile mixte raman neschimbate;
ii) daca fiecare element al matriceiQse nmulteste cu constantak, atunci valoareajocului devine vk, iar strategiile mixte optime raman neschimbate.
Deci prin folosirea adecvata a observatiilor amintite se poate presupune v = 1.Problemele de rezolvat devin folosind notatiaXi= xi/v:
min(
mi=1 Xi)
QX 1Xi 0, i= 1, m
si
max(n
j=1Yj)
QY 1Yj 0, j= 1, n.
Cele doua probleme de programare liniara sunt n forma canonica si sunt dualeuna alteia. Acestea se pot rezolva prin metodele simplex sau simplex-dual. Se poate
apela pentru rezolvarea acestor probleme la programele specializate existente pepiata software.
3.6. Aplicatii
Exercitiul 3.6.1. Se considera jocul n forma matriceala:
TABELUL 4.1
A/B b1 b2 b3 b4 b5
a1 3 5 4 2 1a2 2 3 1 0 1a3 4 1 1 0 3a4 5 0 3 2 4
Matricea jocului este alcatuita n raport cu jucatorul A (maximizant).
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
44/143
APLICATII 37
i) Sa se calculeze valoarea inferioara si valoarea superioara a jocului.
ii) Are jocul punct sa?iii) Aflati strategiile mixte optime ale celor doi jucatori.
Raspuns. Matricea jocului fiind alcatuita n raport cu jucatorul A, care estejucator maximizant, acesta doreste sa castige cat mai mult si va elimina din jocstrategiile dominate. Avem a4 a3 deci strategia a3 va fi eliminata din joc decatre jucatorul A. Deoarece b1 b4 si b3 b4 atunci jucatorul B elimina din jocstrategiile b1 si b3 (conduc la pierderi mai mari). Astfel jocul se reduce la matricearedusa Q:
Q=
5 2 13 0
1
0 2 4
.
Valoarea inferioara a jocului este:
= maxi
minj
qij = 0,
si valoarea superioara a jocului este:
= minj
maxi
qij = 2.
Deoarece < jocul nu are punct sa. Valoarea jocului v
[0, 2].
Problema de programare liniara pe care trebuie sa o rezolve jucatorul A este:
min(v)5x1+ 3x2 v2x1+ 2x3 vx1 x2+ 4x3 vx1+ x2+ x3= 1x1, x2, x3 0,
sau daca se noteaza Xi =xi/v pentru i = 1, 2, 3 obtinem problema de programareliniara:
min(X1+ X2+ X3)5X1+ 3X2 12X1+ 2X3 1X1 X2+ 4X3 1X1, X2, X3 0.
Similar, problema de programare liniara corespunzatoare jucatorului B este:
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
45/143
APLICATII 38
max(Y1+ Y2+ Y3)5Y1+ 2Y2+ Y3 13Y1 Y2 12Y2+ 4Y3 1Y1, Y2, Y3 0.
Cele doua probleme de programare liniara sunt duale una alteia. Rezolvareaacestora se poate face cu ajutorul algoritmului simplex primal sau dual. Pentrurezolvarea cu ajutorul programului MAPLEa acestora sintaxa este pentru jucatorulA (maximizant):
> with(simplex) :
> minimize(x + y+ z, 5 x + 3 y >= 1, 2 x + 2 z >= 1,x y+ 4 z >= 1, N ON N EGATIV E);Solutia este: x= 0, y = 1/3, z= 1/2.iar respectiv pentru jucatorul B (minimizant):> maximize(x + y+ z, 5 x + 2 y+ z
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
46/143
APLICATII 39
TABELUL 4.2
A/B 5% 0% +5%5% 2 4 40% 1 0 3
+5% 3 2 0
Ce strategie mixta va adopta firma A n fata concurentei?
Exercitiul 3.6.3. Se considera jocul n forma matriceala:
TABELUL 4.3
A/B b1 b2 b3 b4 b5a1 3 5 4 2 a2 2 3 0 a3 4 0 3a4 5 0 3 2 4
Matricea jocului este alcatuita n raport cu jucatorul A (maximizant), iar esteun parametru real strict pozitiv.
i) Sa se calculeze valoarea inferioara si valoarea superioara a jocului.
ii) Are jocul punct sa?iii) Aflati strategiile mixte optime ale celor doi jucatori.
Exercitiul 3.6.4. Se considera jocul de doua persoane n forma matriceala:
TABELUL 4.4
A/B b1 b2 b3a1 0 a2 0 a3 0
Matricea jocului este alcatuita n raport cu jucatorul A, (maximizant) iar sisunt parametri reali strict pozitivi.
i) Sa se calculeze valoarea inferioara si valoarea superioara a jocului.
ii) Are jocul punct sa?
iii) Aflati strategiile mixte optime ale celor doi jucatori.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
47/143
APLICATII 40
Exercitiul 3.6.5. Sa se determine o pereche de strategii optime si valoarea
urmatorului joc matriceal: 3 6 1 45 2 4 2
1 4 3 5
.
Raspuns. Se va scrie problema de optimizare pentru primul jucator si se rezolvaaceasta. Valoarea jocului va fi 13/4.
Exercitiul 3.6.6. Se considera jocul n forma matriceala (n raport cu jucatorulA):
TABELUL 4.5A/B b1 b2 b3 b4
a1 2 3 0 1
a2 1 2 4 3
a3 0 2 3 2
a4 2 3 0 1
i) Sa se determine valoarea inferioara si valoarea superioara a jocului.
ii) Determinati, daca exista, punctul sa al jocului.iii) Sa se determine strategiile mixte ale celor doi jucatori.
Raspuns. Valoarea inferioara a jocului este 1, iar valoarea superioara este 2.Valoarea jocului este 8/5.
Exercitiul 3.6.7. Folosind criteriul minimax, sa se rezolve un joc matriceal deordinul 3 3 a carui matrice este:
C=
1 3 32 0 3
2 1 0
.
Specificati si valorile inferioara si superioara a jocului. Cum se modifica aceste
strategii daca ultima linie a matricei Cse nmulteste cu ? Pentru ce valoare a luijocul are punct sa?
Raspuns. Valoarea inferioara a jocului este:
= maxi
minj
qij = 0,
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
48/143
APLICATII 41
si valoarea superioara a jocului este:
= minj
maxi
qij = 2.
Strategia optima (mixta) a primului jucator este unica si este egala cu:
x1 = 1
3, x2=
2
3, x3= 0.
Valoarea jocului (aceasta este unica) este egala cuv = 1.Strategia optima a celui de-al doilea jucator nu este unica. O strategie optima
este spre exemplu:
y1= 15
, y2= 35
, y3= 15
,
o alta strategie optima este:
y1= 0, y2=2
3, y3=
1
3.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
49/143
Capitolul 4
TEORIA DECIZIILOR
STATISTICE
4.1. Prezentarea problemelor
Situatiile reale necesita adoptarea unor decizii ce trebuie determinate utilizanddiverse criterii. Spre deosebire de statistica matematica clasica, care se ocupa dedezvoltarea unor teorii si tehnici de inferenta asupra parametrului, utilizand numaiinformatia de selectie, teoria deciziilor statistice combina informatia de selectie cualte doua aspecte importante legate deconsecintele posibileale adoptarii unei decizii
si de informatia a prioricu privire la parametrul .Cunoasterea consecintelor posibile ale adoptarii diferitelor decizii presupune o
exprimare cantitativa a castigului sau pierderii produse pentru fiecare decizie posi-bila si pentru diferitele valori posibile ale parametrului. Functia astfel obtinuta, cedepinde de decizia adoptata si de parametrul , apare n literatura de specialitatesub diferite denumiri ca functie castigsau functie utilitate.
Informatia a priori cu privire la parametrul se obtine din alte surse decat cele denatura statistica ce implica problema de decizie respectiva. Este o informatie care seobtine dintr-o experienta trecuta cu privire la situatii similare ce implica parametrul. Aceasta informatie a priori este cuantificata printr-o distributie de probabilitatecu privire la parametrul . Problema existentei acestei distributii este o problema
destul de discutata. Abordarea teoriei deciziilor prin intermediul unei distributii apriori corespunde abordarii bayesiane. Problemele legate de teoria deciziilor pot fincadrate n cadrul teoriei jocurilor ceea ce justifica prezentarea acestui capitol dupacapitolul corespunzator teoriei jocurilor. Decidentul poate avea sau nu posibilitateaefectuarii unor experiente a priori luarii deciziei: avem de a face cu decizii faraexperienta a priori, decizii cu experient a unica(sau decizii cu volum de esantionaj
42
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
50/143
STRATEGII BAYES SI STRATEGII MINIMAX 43
dat, n care decizia se ia dupa efectuarea tuturor observatiilor) si decizii secventiale
(pe baza observatiei se poate decide efectuarea unei noi observat ii sau luarea uneidecizii corespunzatoare). Astfel paragrafele 5.2 si 5.3 ale acestui capitol abordeazastrategiile de luare a deciziilor n situatiile n care nu avem experiente a priori,respectiv situatia unei experiente de volum fixat. Deciziile se pot lua n conditiide risc (dispunem de informatie a priori cu privire la starea parametrului ) saun conditii de incertitudine. Astfel paragraful 5.4 prezinta o serie de criterii pentrualegerea deciziilor optime n caz de incertitudine.
4.2. Strategii Bayes si strategii minimax
Pentru a fixa ideile sa presupunem ca multimea parametrilor de stare (necunos-cuta) este finita ={1, . . . , m}. Sa presupunem ca avem o informatie a prioridespre data de distributia de probabilitate a priori (). Aceasta distributie senumeste strategie mixta. Sa presupunem ca avem multimea strategiilor pure:
A= {a1,...,an}.
Sa notam prinL(, a) valoarea functiei de pierdere:
L: A R+,
care este pierderea obtinuta daca se adopta deciziaa si starea parametrului este .
Pierderea medieeste definita ca:
L(, a) =M[L(, a)] =
L(, a)(), pentru orice a A.
Numimstrategie Bayesactiunea cea mai favorabilaa care minimizeaza pierdereamedie, adica a pentru care:
L(, a) = minaA
L(, a).
Numimstrategie minimax actiunea cea mai favorabilaa care minimizeaza pier-derea maxima, adicaa pentru care:
max
L(, a) = minaA
max
L(, a).
Daca nu ne limitam numai la strategiile pure, atunci vom folosi o combinat iede strategii pure alese dupa o lege de probabilitate. Aceasta strategie se numestestrategie mixta.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
51/143
CAZUL EFECTU ARII UNOR EXPERIENTE UNICE 44
Fie(a) = ((a1),...,(am)) distributia de probabilitate care defineste probabili-
tatea cu care se folosesc strategiile purea1,...,am. In general, dispunem de o multimede strategii mixte:
H= {1(a),...,p(a)}.Atunci pierderile medii sunt date de:
L(, ) =M,a(L(, a)) =
aA
L(, a)()(a).
In acest caz trebuie gasita acea strategie mixta H pentru care pierderilemedii sa fie minime:
L(,
) = minHL(, ),
sau acea strategie mixta Hpentru care pierderile maxime sa fie minime:
max
L(, ) = minH
max
L(, ).
4.3. Cazul efectuarii unor experiente unice
Sa presupunem ca decidentul, pentru a-si largi cunostintele despre starile naturii,opteaza pentru efectuarea unei experiente unice (de exemplu, pentru a estima influ-enta unui anumit tip de medicament asupra unei categorii de pacienti, se poate face
o experienta unica ce consta n masurarea zilnica, timp de mai multe luni, a uneiconcentratii, dintr-un anumit tip de compus proteic, pentru mpacienti din categoriarespectiva).
FieZspatiul rezultatelorz1,...,zlale experientei. Fiecarui rezultatz Zobtinutcand starea i corespunde o probabilitate determinata dep(z|),care satisfacerelatiile:
p(z|) 0, pentru orice z ZzZ
p(z|) = 1.
Definitia 4.3.1. Tripletul format din spatiul rezultatelor experientei Z, spa-tiul starilor naturii si distributia conditionata p(z|) definita pe Z pentru fiecare , se numeste spatiu de esantionaj. Vom nota acest lucru cuE= (Z, , p).
Definitia 4.3.2. Se numeste functie de decizie functia d : Z A, si asociazafiecarui rezultat zk Zo actiune aj A, j= 1, n.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
52/143
CAZUL EFECTU ARII UNOR EXPERIENTE UNICE 45
Pierderea suferita n cazul n care starea parametrului este i, i = 1, m este
data de:L(i, aj) =L(i, d(zk)) =Lzk(i, d).
Pentru un dat, rezultatulz al experientei va fi o variabila aleatoare determinata deprobabilitatea conditionatap(z|),deci si pierderile Lz(, d) sunt variabile aleatoaresi se vor realiza cu aceeasi probabilitate.
Definitia 4.3.3. Numim functie de riscfunctia : D R data de:
(, d) =M[Lz(, d)] =zZ
Lz(, d)p(z|),
si reprezinta valorea medie a pierderii pe spatiul rezultatelor Z.
Se a junge la concluzia ca spatiul deciziilorD joaca n problema strategiei n cazulefectuarii unei experiente unice, acelasi rol ca spatiul A n problema strategiei faraexperiente. Deci metodele de rezolvare ale celor doua tipuri de probleme vor fiasemanatoare.
Se pot aborda strategii mixte (d) definite pe spatiul D. Functia de risc este nacest caz:
(, ) = M[(, d)] =dD
(, d)(d)
=dD
zZ
Lz(, d)p(z|)(d).
Principul minimax consta din alegerea acelei strategii (d) pentru care risculmediu este cel mai mic, n cazul n care starea parametrului este cea mai defavo-rabila. Strategia (d) se alege astfel ncat:
(, ) = min
max
(, ),
iar valoarea corespuzatore a riscului se numeste risc minimax.Principul lui Bayesminimizeaza riscul mediu definit de:
(, d) =
(, d)().
Strategia pura d se alege astfel ncat:
(, d) = mindD
(, d).
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
53/143
DECIZII OPTIME N CAZ DE INCERTITUDINE 46
4.4. Decizii optime n caz de incertitudine
Pana n acest punct au fost tratate procesele de decizii n conditii de risc, ceeace reprezinta faptul ca sunt cunoscute (sau se pot determina) probabilitatile cores-punzatoare parametrului .
In continuare ne vom ocupa de procesele de decizie desfasurate n condit ii deincertitudine, deci cand nu se cunosc probabilitatile corespunzatoare lui . Faptulca atitudinea fata de decizie este subiectiva face ca n teoria deciziilor sa nu existecriterii universal valabile. Vom prezenta cateva criterii de alegere a deciziei n caz deincertitudine, precizand ca aplicarea lor poate duce la rezultate diferite. Un mod dea alege o decizie ar putea fi acela al alegerii strategiei indicate ca rezultat al aplicariimai multor criterii.
Sa consideram situatia n care dispunem dem strategii pure a1, . . . , am,iar para-metrul are n stari posibile1, . . . , m.Elementulqij va reprezenta castigul realizatdaca se adopta actiunea ai si starea parametrului este j, i= 1, m , j = 1, n.
4.4.1. Criteriul lui Hurwicz
Criteriul lui Hurwicz sau criteriul optimismului alege ca strategie optima aceaactiune ai care corespune la:
maxi
[Qi+ (1 )qi],
unde [0, 1] se numesteoptimismul decidentului,iar qi= = minj
qij si Qi= maxj
qij.
4.4.2. Criteriul lui Savage
Criteriul lui Savagesaucriteriul regreteloralege ca strategie optima acea actiuneai care corespune la:
minj
maxi
bij = maxi
minj
bij,
(daca nu se poate alege o strategie pura, adica matricea nu are punct sa, se va deter-mina o strategie mixta optima), unde matricea regretelor(diferenta dintre castigulrealizat prin luarea unei decizii fara a cunoaste starea naturii si cel realizat daca secunosteau aceste stari) este definita ca:
bij = maxk
qkj qij, i= 1, m , j= 1, n.
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
54/143
APLICATII 47
4.4.3. Criteriul Bayes-Laplace
Criteriul lui Bayes-Laplacealege ca strategie optima acea actiune ai care core-spunde la:
maxi
[1
n
nj=1
qij],
adica se presupune ca toate starile naturii au aceeasi probabilitate.
4.4.4. Criteriul lui Wald
Criteriul lui Waldalege, daca jocul are punct sa, ca strategie optima acea actiuneai care corespune la principiul minimax. Daca jocul nu are punct sa, atunci se
determina strategia mixta optima cu probabilitatile x1,...,xm care maximizeaza:
minj
[mi=1
qijxi].
4.5. Aplicatii
Exercitiul 4.5.1. O linie de fabricare a cimentului poate folosi ca materie prim atrei tipuri de nisip ai carui parametri sunt1, 2,respectiv3.Se stie ca linia tehno-logica poate folosi n medie 60% din primul tip, 30% din al doilea tip si 10% dinal treilea tip si ca poate functiona n trei regimuri a1, a2 si a3. Pierderile reflectand
calitatea sunt date n tabelul 5.1.
TABELUL 5.1
() a1 a2 a31 0, 6 0 2
2 0, 3 0, 5 2 1
3 0, 1 1 3
Sa se calculeze pierderile medii corespunzatoare repartitiei a priori. Care estestrategia optima n sensul lui Bayes?
Raspuns. Pierderile medii corespunzatoare probabilitatii a priori sunt:
L(, a1) = 0 0, 6 + 0, 5 0, 3 + 1 0, 1 = 0, 25
L(, a2) = 0, 6 + 2 0, 3 + 0, 1 = 1, 3
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
55/143
APLICATII 48
L(, a3) = 2 0, 6 + 1 0, 3 + 3 0, 1 = 1, 8.
Strategia Bayes este acea actiune care minimizeza pierderea medie adica strategia
a1 daca 526
sau strategia a2 daca 526
.
Remarcam ca pentru = 5
26avem doua strategii optime si anume a1 si a2.
Exercitiul 4.5.2. Aceeasi problema ca la 5.5.1. ca de aceasta data dispunemde o strategie mixta cu frecventele 20%, 30%, respectiv 50%.
Exercitiul 4.5.3. Se considera jocul contra naturii n forma matriceala:
TABELUL 5.2
A/B 1 2 3 4 5a1 3 5 4 2 1a2 2 3 1 0 1a3 4 1 1 0 3a4 5 0 3 2 4
Matricea jocului este alcatuita n raport cu jucatorul statistician A (maximizant)si reprezinta castigurile realizate de acesta.
Sa se aplice criteriile lui Hurwicz, Savage, Bayes si Wald pentru alegerea decizieioptime.
Raspuns. i) Pentru aplicareacriteriului lui Hurwicz:
TABELUL 5.3
1 2 3 4 5 Qi qi Qi+ (1 )qia1 3 5 4 2 1 4 5 9 5a2 2 3 1 0 1 3 1 4 1a3 4 1 1 0 3 4 1 5 1
a4 5 0 3 2 4 5 0 5determinam:
maxi
[Qi+ (1 )qi] = 5unde [0, 1]. Deci strategia optima estea4.
ii) Pentru aplicarea criteriului lui Savage se determina matricea regretelor:
-
8/13/2019 Deciziilor Manageriale-Bazele Matematice Ale Deciziilor Manageriale
56/143
APLICATII 49
TABELUL 5.4
(bij) 1 2 3 4 5 minj
bij
a1 2 8 0 0 3 0
a2 3 0 3 2 5 0
a3 1 4 3 2 1 1
a4 0 3 1 0 0 0
maxi
bij 3 8 3 2 5 5\1
Se observa faptul ca jocul nu are punct sa si deci vom determina strategia mixtacu ajutorul algoritmului simplex primal sau dual. Solutia problemei atasate se poaterezolva cu ajutorul programului MAPLE,iar sintaxa pentru aceasta este:
> with(simplex) :> minimize(x+ y + z +w, 2 x+ 3 y + z >= 1, 8 x+ 4 z + 3 w >=1, 3 y+ 3 z >= 1,
2 y+ 2 z >= 1, 3 x + 5 y+ z >= 1,N ON N EGATIVE);solutia problemei fiind x = 0, y = 1/4, z = 1/4, w = 0. Aceasta conduce la
strategia mixta optima:
x1= 0, x2=1
2, x3=
1
2, x4= 0.
iii) Pentru aplicarea criteriului lui Bayes-Laplace vom considera echiprobabilestarile i :
TABELUL 5.5
1 2 3 4 5 1n
nj=1
qij
a1 3 5 4 2 1 1a2 2 3 1 0 1 1a3 4 1 1 0 3 7/5a4 5 0 3 2 4 14/5
deci statisticianul va alege strategia a4 deoarece aceasta maximizeaza:
1
n
n
j=1
qij.
iv) Pentru aplicareacriteriului lui Wald,deoarece jocul nu are punct sa statisti-cianul va alege o strategie mixta cu probabilitatile x1,...,xm care maximizeaza:
minj
[mi=1