Model Examen CO


Model examen Cercetari Operationale, partea a 2a, 7 februarie 2010 + rezolvari.
Multumiri doamnei profesoare Rodica Branzei, care a pus pe site atat subiectele, cat si rezolvarile.

***
Test 2 Cercetări Operaţionale
7 februarie 2010

1.Compania SD a dezvoltat un nou chip pentru computere care va face posibilă producerea unui nou computer, dacă compania doreşte aceasta. Alternativ, compania poate vinde drepturile corespunzătoare pentru 15 milioane de dolari. Dacă compania alege să construiască computere profitabilitatea depinde de abilitatea companiei să pună pe piaţă computerul în decursul primului an. Compania are acces suficient la pieţe de desfacere pentru vânzare cu amănuntul care îi garantează vânzări de 10.000 de computere. Pe de altă parte, dacă acest computer devine popular, compania poate vinde 100.000 de bucăţi. Costul punerii în funcţiune a unei linii de producţie este de 6 milioane de dolari, iar diferenţa dintre preţul de vânzare şi costul variabil al fiecărui computer este de 600 dolari.
(a)Pentru această problemă de decizie specificaţi care sunt alternativele de decizie, stările naturii şi tabelul de beneficii/profituri posibile.
(b)Fie p probabilitatea de a vinde 10.000 de computere. Desenaţi graficul corespunzător plăţilor aşteptate pentru fiecare dintre alternativele de decizie (în funcţie de p) şi precizaţi punctul critic. Explicaţi semnificaţia acestui punct.

2.Tabelul plăţilor (în mii de dolari) pentru o problemă de decizie este:

Alternative \ Stări ale naturii

S1 S2 S3

A1 4 0 0
A2 0 2 0
A3 3 0 1,

iar probabilităţile apriorice pentru stările naturii S1, S2, S3 sunt 0.2, 0.5 şi 0.3.

Faceţi analiza deciziei folosind criteriile “maximin”, “maximum likelihood” şi regula lui Bayes.

3.Considerăm o reţea cu o sursă, o destinaţie, un nod intermediar şi trei arce a1, a2, a3 cu capacităţile c1 = 30, c2 = 60, c3 = 100, respectiv, unde arcele a1 şi a2 conectează sursa cu nodul intermediar, iar arcul a3 conectează nodul intermediar cu destinaţia. Coaliţiile care pot utiliza arcele a1, a2, a3 sunt precizate prin intermediul jocurilor unanime cu mulţimea jucătorilor N = {1, 2, 3}: w1 = u{1, 3}, w2 = u{2, 3}, w3 = u{3}. Construiţi jocul cooperativ (N, v) corespunzător acestei situaţii. Este jocul (N, v) un joc balansat? Determinaţi valoarea Shapley Φ(v) a jocului; aparţine acest vector de plată sâmburelui C(v)?

4.Considerăm jocul de două persoane cu matricea plăţilor

-2 0 2
4 5 -3

(jucătorul 1 are două strategii pure, iar jucătorul 2 are trei strategii pure). Determinaţi un echilibru Nash în strategii mixte şi valoarea jocului (folosind metoda grafică sau metoda algebrică).
Scrieţi modelul de programare liniară pentru jucătorul 1. Cum poate fi folosit acest model pentru a determina strategia optimală a jucătorului 2 şi valoarea jocului?

***

Rezolvare Test CO, 1 februarie 2010

1a: 2,5p

Alternative/Stari
Vinde 10.000 Vinde 100.000
Produce computere 0 54
Vinde drepturi 15 15

1b: 2,5p Produce computere cand p≤ 0,722 si vinde drepturi cand p > 0,722.

2. 5p
Criteriul “maximin”: oricare alternativa (valoarea 0)
Criteriul “maximum likelihood”: A2 (starea S2 are probabilitate maxima) cu valoarea 2.
Regula lui Bayes: A2 (valoarea asteptata este maxima si egala cu 1)

3. Reprezentarea situatiei de tip flux: 1p
Construirea functiei caracteristice: 1p
v({i}) = 0, i = 1, 2, 3; v({1,2}) = 0, v({1,3}) = 30, v({2, 3}) = 60, v({1, 2, 3}) = 90.
Jocul este balansat (Main result 1 in cursul OR Games, flow games, deoarece jocurile unanime sunt jocuri balansate; alternativ folosind definitia samburelui jocului): 1p
Φ(v) = (15, 30, 45) apartine lui C(v): 2p

4. 5p
Echilibrul Nash in strategii mixte: ((7/11, 4/11), (5/11, 0, 6/11)), valoarea jocului = 2/11.

Max x3
− 2×1 + 4 x2 −x3 ≥ 0
5 x2 −x3 ≥ 0
2×1 − 3 x2 −x3 ≥ 0
x1 + x2 = 1
x1, x2 ≥ 0
(x3 ≥ 0 sau adaugarea unei constante pentru a avea toate platile pozitive).

Determinarea strategiei mixte optimale a jucatorului 2 si determinarea valorii jocului se face ori rezolvand duala problemei LP corespunzatore jucatorului 1 ori aplicand algoritmul simplex perechii de probleme duale.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: