BISP_ID_UI_5
description
Transcript of BISP_ID_UI_5
Unitatea de învăţare 5
TEORIA JOCURILOR.
TEORIA ECHIPAMENTELOR
Obiectivele unităţii de învăţare: • însuşirea cunoştinţelor teoretice privind elementele de bază ale
teoriei jocurilor şi ale teoriei echipamentelor; • înţelegerea şi însuşirea principalelor metode de rezolvare a
problemelor de tip jocuri matriceale şi cu startegie mixtă şi a problemei timpului optim de înlocuire a unui echipament (utilizând un model determinist, discret sau continuu);
• însuşirea cunoştinţelor de bază şi deprinderilor practice necesare pentru aplicarea jocurilor matriceale şi a teoriei echipamentelor în situaţii specifice ingineriei sistemelor de producţie;
• dezvoltarea aptitudinilor de identificare a situaţiilor din conducerea optimală a sistemelor de producţie în care pot fi aplicate teoria jocurilor sau echipamentelor.
Cuprinsul unităţii de învăţare:
5.1. Elemente de teoria jocurilor 2 5.1.1. Formularea problemei. Clasificări 2 5.1.2. Jocuri matriceale 3 5.1.3. Jocuri cu strategie mixtă 6
Teste de autoevaluare (secţiunea 5.1) 8 Problemă propusă (secţiunea 5.1) 8
5.2. Elemente de teoria echipamentelor 9 5.2.1. Problema timpului optim de înlocuire a unui echipament
– model determinist 9 5.2.2. Modele aleatoare discrete pentru determinarea duratei
optime de viaţă a unui echipament 13 Teste de autoevaluare (secţiunea 5.2) 15 Probleme propuse (secţiunea 5.2) 16
Bibliografie 17 Soluţia problemelor propuse 17
Conf. dr. ing. Andrei Dumitrescu
2
5.1. Elemente de teoria jocurilor
În cele ce urmează, continuăm prezentarea unora din metodele cercetării
operaţionale (a se vedea secţiunea 1.5). Astfel, vor fi prezentate în continuare elementele de bază din teoria jocurilor.
Teoria jocurilor modelează situaţiile conflictuale (de competiţie), cum ar fi: competitivitatea în economie, conflictele militare, politice sau din domeniul afacerilor. Teoria jocurilor, abordată succint în cadrul acestei secţiuni, a fost dezvoltată ca teorie matematică, pornind de la studiul jocurilor propriu-zise, de către J. von Neumann, spre sfârşitul celui de-al doilea război mondial.
5.1.1. Formularea problemei. Clasificări Problema tipică a teoriei jocurilor se poate formula astfel: Doi sau mai
mulţi adversari pot influenţa pe anumite căi desfăşurarea unor evenimente, fiecare având unele interese (sau preferinţe), care nu pot coincide pentru această desfăşurare.
Principalele elemente ale unei probleme de teoria jocurilor sunt următoarele:
• numărul de jucători (adversari); jucătorul reprezintă o unitate de decizie (o persoană sau un grup de persoane cu interese identice / o echipă) ale cărei interese sunt în contradicţie cu ale oricărui alt jucător în cel puţin o situaţie; pot exista jocuri cu doi sau mai mulţi (n) adversari;
• strategia unui jucător, ce reprezintă o specificaţie completă a deciziilor acelui jucător şi a acţiunilor sale în condiţiile unei mulţimi particulare de decizii ale celorlalţi jucători; mulţimea strategiilor unui jucător îi defineşte complet acţiunile în toate eventualităţile imaginabile ale unui joc;
• funcţia de retribuţie, ce reprezintă câştigul pentru fiecare jucător şi este funcţie de strategia sa şi a celorlalţi jucători (depinde de eficienţa strategiei sale); pentru a exista un joc, acest câştig nu trebuie să fie indiferent jucătorilor; de exemplu, în cazul unui joc cu doi adversari, funcţia de retribuţie pentru un jucător, A, este suma obţinută de A de la celălalt jucător, B (dacă A pierde jocul, această funcţie va lua valori negative).
În cazul unui joc cu n jucători, se notează cu pi câştigul jucătorului i, 1 ≤ i ≤ n, fiind date strategiile tuturor celor n jucători. Un astfel de joc este numit cu sumă nulă dacă se îndeplineşte condiţia:
∑=
n
iip
1 = 0 . (5.1)
Se pune problema stabilirii unor criterii care să permită alegerea deciziilor (strategiei) optime (celor mai potrivite) pentru fiecare jucător în parte.
Jocurile studiate se pot clasifica după următoarele trei criterii:
Bazele Ingineriei Sistemelor de Producţie 5. Teoria jocurilor. Teoria echipamentelor
3
• în funcţie de modalitatea de stabilire a strategiei – joc cu decizii libere (cu alegerea conştientă a strategiei) şi joc cu decizii întâmplătoare (de exemplu, stabilite ca rezultat al aruncării unui zar);
• în funcţie de informaţia disponibilă – joc cu informaţie completă (dacă jucătorii cunosc deciziile adversarilor, cum este cazul unui joc de şah) sau cu informaţie incompletă (de exemplu, în cazul unui joc de cărţi);
• în funcţie de numărul de strategii ale jucătorilor – joc finit (dacă numărul strategiilor este finit) sau infinit (mulţimea strategiilor este infinită).
Observaţie. Unele situaţii din ingineria economică în care este necesară luarea unei decizii (cum ar fi analiza investiţiei, înlocuirea unui echipament, controlul calităţii unui produs/serviciu), pot fi tratate ca un joc cu doi jucători, A şi B, numit joc împotriva Naturii (Lumii), în care A este factorul de decizie uman, iar B este „Natura”, ce oferă mai multe situaţii posibile, fiecare fiind asimilată unei strategii. Dezavantajul acestui mod de abordare se exprimă prin constatarea că este greu de acceptat ca „Natura” să „acţioneze” astfel încât factorul uman să obţină cel mai slab rezultat (cum este cazul unui joc cu doi adversari umani), jocul acestei fiind mai degrabă întâmplător.
În subsecţiunile ce urmează, vom analiza doar cazul unui joc finit, cu doi adversari, A şi B, cu sumă nulă (câştigul realizat de un jucător este egală cu pierderea celuilalt jucător). Un astfel de joc se numeşte joc matriceal. Un joc finit, cu doi jucători, dar fără sumă nulă, se numeşte bimatriceal.
5.1.2. Jocuri matriceale Considerăm un joc matriceal, cu doi jucători (adversari), notaţi A şi B.
Fie a1, a2, …, am mulţimea strategiilor jucătorului A, notată A = {ai | 1 ≤ i ≤ m}. Fie b1, b2, …, bn mulţimea strategiilor jucătorului B, notată B = {bj | 1 ≤ j ≤ n}.
Funcţia de retribuţie pentru jucătorul A, notată cij = f(ai, bj), 1 ≤ i ≤ m, 1 ≤ j ≤ n, reprezintă câştigul obţinut de jucătorul A dacă el adoptă strategia ai, iar B adoptă strategia bj. Jucătorul A va urmări maximizarea lui cij, pe când B va urmări minimizarea acestuia. Funcţia de retribuţie pentru jucătorul B este egală şi de semn contrar: cij’ = - cij.
Se construieşte matricea C = [ cij ], numită matricea plăţilor (a funcţiei de retribuţie) pentru jucătorul A. Dacă A adoptă strategia ai, indiferent de strategia adoptată de B, îşi va asigura un câştig minim garantat egal cu:
( )ijnjc
≤≤1min .
Decizia optimă a jucătorului A corespunde maximizării acestui câştig garantat, adică:
( )⎥⎦⎤
⎢⎣⎡
≤≤≤≤ ijnjmic
11minmax .
Dacă jucătorul B adoptă strategia bj, indiferent de strategia adoptată de A, va înregistra o pierdere maximă garantată egală cu:
( )ijmic
≤≤1max .
Conf. dr. ing. Andrei Dumitrescu
4
Decizia optimă a jucătorului B corespunde minimizării acestui câştig garantat (cea care oferă cea mai mică pierdere maximă):
nj≤≤1min [ ( )ijmi
c≤≤1
max ] .
Se poate demonstra că există relaţia:
( )⎥⎦⎤
⎢⎣⎡
≤≤≤≤ ijnjmic
11minmax ≤
nj≤≤1min [ ( )ijmi
c≤≤1
max ] (5.2)
Dacă, în relaţia de mai sus, simbolul „≤” devine „=”, cele două cantităţi fiind egale cu
00 jic , atunci (0i
a , 0j
b ) este strategia optimă pură (pentru ambii adversari), (i0, j0) se numeşte punct de echilibru al matricei C a câştigurilor, v =
00 jic reprezintă valoarea jocului pentru A (pentru B, valoarea jocului va fi -
00 jic ), jocul se numeşte strict determinat (cu strategii pure) şi, în plus, are loc inegalitatea:
0ijc ≤ 00 jic ≤ jic
0 , oricare ar fi i ≠ i0, j ≠ j0 . (5.3)
Aplicaţia 5.1: Să se rezolve jocul matriceal caracterizat de următoarea matrice C a câştigurilor pentru jucătorul A:
C = ⎟⎟⎟
⎠
⎞
⎜⎜⎜
⎝
⎛
−132154203
.
Rezolvare: Strategiile jucătorului A, a1, a2, a3, corespund liniilor matricei C, iar strategiile lui B, b1, b2, b3, corespund coloanelor matricei C.
Câştigul minim garantat al jucătorului A dacă adoptă strategia a1 va fi:
( )jjc131
min≤≤
= min (3, 0, 2) = 0 .
Dacă A va adopta strategiile a2, respectiv a3, va obţine câştigul garantat minim:
( )jjc231
min≤≤
= min (4, 5, 1) = 1 ,
( )jjc331
min≤≤
= min (2, 3, -1) = -1 .
Strategia optimă pentru A va fi a2, ce corespunde maximizării câştigului garantat:
( )⎥⎦⎤
⎢⎣⎡
≤≤≤≤ ijjic
3131minmax = max (0, 1, -1) = 1 = c23 .
Pierderea maximă garantată a lui B, corespunzătoare strategiei b1, respectiv b2, b3, este:
( )131max ii
c≤≤
= max (3, 4, 2) = 4 ,
( )231max ii
c≤≤
= max (0, 5, 3) = 5 ,
( )331max ii
c≤≤
= max (2, 1, -1) = 2 .
Bazele Ingineriei Sistemelor de Producţie 5. Teoria jocurilor. Teoria echipamentelor
5
Strategia optimă pentru B va fi b3, ce corespunde minimizării pierderii garantate:
31
min≤≤ j[ ( )iji
c31
max≤≤
]= min (4, 5, 2) = 2 = c13 .
Se observă că matricea C nu prezintă punct de echilibru.
Aplicaţia 5.2: Să se rezolve jocul matriceal caracterizat de următoarea matrice C a câştigurilor pentru jucătorul A:
C =
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜
⎝
⎛
−−−−−−
−−−−−−−
−−
−−−−−−−−
1863046167117221130510258713224101034940790
127103143852171119403265819
Rezolvare: Dacă A va adopta, pe rând, strategiile a1, a2, a3, a4, a5, a6, a7, respectiv a8, va obţine următoarele câştiguri garantate minime:
( )jjc181
min≤≤
= min (-9, -1, 8, -5, 6, 2, -3) = -9 ,
( )jjc281
min≤≤
= min (4, -9, 11, -1, -7, 1, -2, 5) = -9 ,
( )jjc381
min≤≤
= min (8, 3, 4, 1, 3, 10, 7, 12) = 1 ,
( )jjc481
min≤≤
= min (0, 9, -7, 0, -4, 9, 4, 3) = -7 ,
( )jjc581
min≤≤
= min (-10, 0, -1, -4, -2, 2, -3, 1) = -10 ,
( )jjc681
min≤≤
= min (7, -8, 5, -2, 10, 5, 0, 3) = -8 ,
( )jjc781
min≤≤
= min (11, -2, 2, -7, 1, -1, 7, 6) = -7 ,
( )jjc881
min≤≤
= min (1, 6, -4, 0, -3, 6, 8, -1) = -4 .
Strategia optimă pentru A va fi a3, ce corespunde maximizării câştigului
garantat: ( )⎥⎦⎤
⎢⎣⎡
≤≤≤≤ ijjic
8181minmax = max (-9, -9, 1, -7, -10, -8, -7, -4) = 1 = c34 .
Pierderile maxime garantate ale lui B, corespunzătoare strategiilor b1, respectiv b2, b3, b4, b5, b6, b7, b8, sunt următoarele:
( )181max ii
c≤≤
= max (-9, 4, 8, 0, -10, 7, 11, 1) = 11 ,
( )281max ii
c≤≤
= max (-1, -9, 3, 9, 0, -8, -2, 6) = 9 ,
( )381max ii
c≤≤
= max (8, 11, 4, -7, -1, 5, 2, -4) = 11 ,
( )481max ii
c≤≤
= max (-5, -1, 1, 0, -4, -2, -7, 0) = 1 ,
( )581max ii
c≤≤
= max (6, -7, 3, -4, -2, 10, 1, -3) = 10 ,
Conf. dr. ing. Andrei Dumitrescu
6
( )681max ii
c≤≤
= max (2, 1, 10, 9, 2, 5, -1, 6) = 10 ,
( )781max ii
c≤≤
= max (-3, -2, 7, 4, -3, 0, 7, 8) = 8 ,
( )881max ii
c≤≤
= max (0, 5, 12, 3, 1, 3, 6, -1) = 12 .
Strategia optimă pentru B va fi b4, ce corespunde minimizării pierderii
garantate: 81
min≤≤ j[ ( )iji
c81
max≤≤
]= min (11, 9, 11, 1, 10, 10, 8, 12) = 1 = c34 .
Se observă că matricea C prezintă punctul de echilibru (3, 4), iar jocul este strict determinat, deoarece:
( )⎥⎦⎤
⎢⎣⎡
≤≤≤≤ ijjic
8181minmax =
81min
≤≤ j[ ( )iji
c81
max≤≤
]= 1 = c34 .
În plus, a3 este strategia optimă pură pentru jucătorul A, b4 este strategia optimă pură pentru jucătorul pentru B, iar valoarea jocului pentru A este v = 1 (pentru B, valoarea jocului este egală cu -1).
5.1.3. Jocuri cu strategie mixtă Considerăm acelaşi joc matriceal ca în subsecţiunea precedentă, cu
deosebirea că fiecărei strategii posibile a celor doi jucători i se asociază o probabilitate de alegere.
Astfel, dacă jucătorul A decide să aleagă strategiile a1, a2, …, am cu probabilităţile x1, x2, …, xm, se spune că el şi-a fixat strategia mixtă definită de vectorul X = (x1, x2, …, xm). Mulţimea strategiilor mixte ale lui A, notată A, este:
A = { X | X = (x1, x2, …, xm), 11
=∑=
m
iix , xi ≥ 0, 1 ≤ i ≤ m } (5.4)
Mulţimea definită de relaţia (5.4) de mai sus conţine aşa-numitele strategii pure: astfel, strategia pură i0 se obţine pentru xi = 1 – dacă i = i0 – şi xi = 0 – dacă i ≠ i0.
Analog, dacă jucătorul B decide să aleagă strategiile b1, b2, …, bn cu probabilităţile y1, y2, …, yn, se spune că el şi-a fixat strategia mixtă definită de vectorul Y = (y1, y2, …, yn). Mulţimea strategiilor mixte ale lui B, notată B, este:
B = { Y | Y = (y1, y2, …, yn), 11
=∑=
n
jjy , yj ≥ 0, 1 ≤ j ≤ n } (5.5)
Mulţimea definită de relaţia (5.5) conţine, de asemenea, strategii pure: astfel, strategia pură j0 se obţine pentru yj = 1, dacă j = j0 , şi yj = 0, dacă j ≠ j0.
Dacă adoptă strategia mixtă X, jucătorul A va obţine, indiferent de strategia adoptată de către B, următorul câştig mediu sigur:
∑=
≤≤⋅
m
iiijnj
xc11
min .
Analog, dacă jucătorul B adoptă strategia mixtă Y, el va suferi, indiferent de strategia adoptată de către A, pierderea medie sigură:
∑=≤≤
⋅n
jjijmi
yc11
max .
Dacă jucătorul A adoptă strategia X, iar jucătorul B adoptă strategia Y, câştigul mediu al lui A este:
Bazele Ingineriei Sistemelor de Producţie 5. Teoria jocurilor. Teoria echipamentelor
7
F(X, Y) = ∑∑= =
⋅⋅m
i
n
jjiij yxc
1 1
. (5.6)
Strategiile optime X şi Y , care se numesc soluţii ale jocului, au proprietatea că:
( ) ( ) ( )YXFYXFYXF ,,, ≤≤ pentru ∈∀X A , ∈∀Y B . (5.7)
Existenţa lor este asigurată de teorema lui Neumann. Se numeşte valoare a jocului numărul ( )YXFv ,= , ce reprezintă câştigul
maxim posibil pentru jucătorul A, dacă B joacă raţional. În caz contrar, A va câştiga mai mult.
Sunt posibile următoarele trei situaţii: v > 0 (câştig mediu net pentru A); v < 0 (pierdere medie netă pentru A); v = 0 (joc imparţial).
Principalele metode de rezolvare ale unei probleme din teoria jocurilor cu strategie mixtă sunt: cea algebrică; a aproximaţiilor succesive; utilizarea programării liniare (prin intermediul unei perechi de programe duale).
Vom prezenta în continuare, pe scurt, doar ultima metodă. Astfel, oricărui joc matricial i se poate asocia o pereche de programe duale şi reciproc – oricărui program liniar i se poate asocia un joc matricial.
Din punctul de vedere al jucătorului A, se urmăreşte maximizarea valorii v şi obţinerea vectorului (strategiei mixte) ( )mxxxX ,...,, 21= ca soluţie a programului liniar:
mixx
njvxc
yxcv
i
m
ii
m
iiij
m
i
n
jjiij
≤≤≥=
≤≤≥⋅
=⋅⋅=
∑
∑
∑∑
=
=
= =
1,0,1
1,
max
1
1
1 1
(5.8)
Din punctul de vedere al jucătorului B, se urmăreşte minimizarea valorii v şi obţinerea vectorului (strategiei mixte) ( )nyyyY ,...,, 21= ca soluţie a programului liniar:
njyy
mivyc
yxcv
j
n
jj
n
jjij
n
j
m
ijiij
≤≤≥=
≤≤≤⋅
=⋅⋅=
∑
∑
∑∑
=
=
= =
1,0,1
1,
min
1
1
1 1
(5.9)
Este evident că al doilea program liniar (5.9) prezentat mai sus este dualul primului program liniar (5.8).
Conf. dr. ing. Andrei Dumitrescu
8
Teste de autoevaluare (secţiunea 5.1)
1. Care este formularea tipică a unei probleme de teoria jocurilor? 2. Imaginaţi o situaţie concretă care poate fi modelată printr-un joc
împotriva Naturii. 3. Cum se defineşte strategia unui jucător în teoria jocurilor? 4. Explicaţi, utilizând câte un exemplu, diferenţa dintre un joc cu sumă
nulă şi un joc fără sumă nulă. 5. Ce reprezintă un joc matriceal? Indicaţi un exemplu concret. 6. În ce condiţii se poate spune că un joc matriceal este strict
determinat? Ce reprezintă strategiile pure? 7. Ce este un joc cu strategie mixtă? Indicaţi o aplicaţie a acestuia. 8. Cum poate fi asociată o problemă de programare liniară unui joc cu
strategie mixtă?
Problemă propusă (secţiunea 5.1) Să se rezolve jocul matriceal caracterizat de următoarea matrice C a
câştigurilor pentru jucătorul A:
C = ⎟⎟⎟
⎠
⎞
⎜⎜⎜
⎝
⎛
−−
−
401482
357 .
Bazele Ingineriei Sistemelor de Producţie 5. Teoria jocurilor. Teoria echipamentelor
9
5.2. Elemente de teoria echipamentelor În această secţiune, vor fi prezentate succint elementele de bază din
teoria echipamentelor. În condiţiile în care fiecare unitate (sistem) de producţie este dotată cu o
mare varietate de echipamente (utilaje, dispozitive, maşini, piese etc.), care lucrează în condiţii diferite şi sunt caracterizate prin moduri foarte diverse de comportare la uzură, s-au realizat intense cercetări pentru descoperirea unor metode adecvate de menţinere a acestor echipamente în condiţii cât mai bune de funcţionare. Astfel de cercetări au condus la constituirea unei noi teorii în cercetarea operaţională – teoria echipamentelor, constituită ca o metodă de rezolvare a problemelor legate de mentenanţa, repararea şi înlocuirea echipamentelor (probleme ce depind de modul de comportare la uzură).
Una din principalele probleme ale teoriei echipamentelor, care va fi abordată cu precădere în continuare, este cea a determinării duratei optime de viaţă a unui echipament dat. Această problemă se poate rezolva aplicându-se fie un model determinist, mai simplu, fie un model aleator.
Aplicarea teoriei echipamentelor în cadrul sistemelor de producţie are drept scop final stabilirea unei anumite politici de mentenanţă, aprovizionare şi înlocuire.
Politica de mentenanţă, aprovizionare şi înlocuire a echipamentelor reprezintă, prin definiţie, ansamblul măsurilor luate pentru buna funcţionare a echipamentelor (utilajelor, maşinilor etc.) din dotarea unei societăţi (unităţi) de producţie.
Această politică, care trebuie să se bazeze exclusiv pe criterii de optim tehnico-economic, se compune din următoarele acţiuni:
• întreţinerea curentă a echipamentelor; • înlocuirea pieselor uzate (care se execută sistematic); • repararea pieselor uzate; • verificări periodice ale echipamentelor.
Pentru toate aceste acţiuni, este necesar să se stabilească intervalul optim de timp la care ele se desfăşoară. Acest optim rezultă de regulă din condiţia minimizării cheltuielilor aferente, combinată însă cu cea a maximizării siguranţei în funcţionare (exploatare).
5.2.1. Problema timpului optim de înlocuire a unui echipament – model determinist
Definiţie: Durata de viaţă a unui echipament, numită şi timp de înlocuire, reprezintă intervalul de timp dintre momentul punerii sale în serviciu (în funcţiune) şi cel al înlocuirii sale. Definiţie: Durata economică de viaţă a echipamentului (timpul optim de înlocuire) este cea corespunzătoare criteriului de optimizare ales, de obicei cel al minimizării cheltuielilor totale (sau al maximizării profitului).
Considerăm întâi un model determinist discret, aplicabil în cazul unui proces discret, caracterizat prin înlocuirea echipamentelor la anumite intervale de timp. Acest model utilizează următoarele elemente de cost:
Conf. dr. ing. Andrei Dumitrescu
10
a − preţul de achiziţionare (cumpărare) al echipamentului; ci − cheltuielile de utilizare a sa la începutul perioadei i; vi − preţul său de vânzare la sfârşitul perioadei i.
Evaluarea costurilor ci şi vi se realizează la intervale de timp egale (o săptămână, o lună, un an etc.), care definesc perioadele de timp i.
Se presupune, de asemenea că: preţul de vânzare al unui echipament scade întotdeauna în timp,
pe măsură ce creşte durata sa de funcţionare, conform relaţiei:
v1 ≥ v2 ≥ … ≥ vn ≥ … ; (5.10)
cheltuielile de utilizare cresc odată cu durata de funcţionare, mai ales datorită uzurii (ipoteză care însă nu este valabilă pentru orice echipament):
c1 ≤ c2 ≤ … ≤ cn ≤ …. (5.11)
Modelul de calcul prezentat nu este însă aplicabil dacă cele două ipoteze (5.10) şi (5.11) de mai sus nu se verifică.
Dacă echipamentul este înlocuit la sfârşitul perioadei n, cheltuielile totale medii (corespunzătoare unei perioade i, 1 ≤ i ≤ n) se pot calcula astfel:
)....(121 nnn vccca
nx −++++= (5.12)
Criteriul de optimizare considerat este minimizarea acestor cheltuieli, adică: nnn
xx ˆ][min = , unde n̂ este durata optimă de viaţă a echipamentului
(exprimată prin numărul de perioade de timp de funcţionare a sa). Pentru calculul mai rapid al cheltuielilor xn, în funcţie de xn-1, se poate
utiliza următoarea relaţie de recurenţă, ce se deduce uşor din (5.12):
)(1
1111 +++ −++⋅
+= nnnnn vvcxn
nx (5.13)
Determinarea duratei optime, n̂ , se bazează pe utilizarea inegalităţilor:
,1ˆ1ˆˆˆ ++ −+< nnnn vcvx (5.14)
care se obţine din condiţia: nx ˆ < 1ˆ+nx ;
nnnn vcvx ˆˆ1ˆˆ −+> − , (5.15)
care rezultă din condiţia: nx ˆ < 1ˆ−nx . Demonstrarea inegalităţilor (5.14) şi (5.15) este prezentată sintetic prin
relaţiile incluse mai jos:
• pentru (5.14) nnnnnn
nnnnnn
xxnvvcxnxnvvcxnxn
ˆˆ1ˆ1ˆˆ
ˆ1ˆˆ1ˆˆ1ˆ
ˆˆ)1ˆ(ˆ)1ˆ(
+⋅>+++⋅⇒⋅+>−++⋅=⋅+
++
+++
) ;
• pentru (5.15)
nnnn
nnnnnn
nnnnnn
nnnnn
xvvcxxnvvcxn
xnvvcxnxnvvcxnxn
ˆˆ1ˆˆ
ˆˆˆ1ˆˆˆ
ˆˆ1ˆˆˆ1ˆ
ˆ1ˆˆ1ˆˆ
ˆˆ)1ˆ(ˆ)1ˆ(
)1ˆ(ˆ
<−+⇒⇒−⋅>+−−⋅⇒
⋅−>+−−⋅=⋅−⇒−++⋅−=⋅
−
−
−−
−−
.
Dacă se defineşte şi următoarea mărime:
yn = vn+cn+1-vn+1 , (5.16)
Bazele Ingineriei Sistemelor de Producţie 5. Teoria jocurilor. Teoria echipamentelor
11
atunci relaţiile (5.14) şi (5.15) devin, respectiv:
nx yx ˆˆ < , 1ˆˆ −> nn yx .
Aplicaţia 5.2: Preţul de cumpărare al unui echipament este a = 1000 €. Preţul de vânzare al echipamentului la sfârşitul a n săptămâni (perioade) de funcţionare este (exprimat în €): vn = a / (n+1) .
Cheltuielile de utilizare a echipamentului aferente săptămânii n sunt (exprimate în €): cn = 150 + 50n .
Se cere să se determine în a câta săptămână este indicat să se înlocuiască echipamentul (durata economică a vieţii echipamentului, exprimată în săptămâni), dacă se urmăreşte minimizarea cheltuielilor medii săptămânale.
Rezolvare: Se observă că: v1 > v2 > ... > vn >... ; c1 < c2 <... < cn < ... .
Ca urmare, condiţiile (5.10) şi (5.11) sunt îndeplinite, iar cheltuielile totale medii pe o perioadă i, 1≤ i ≤ n, în cazul înlocuirii la sfârşitul săptămânii n, se pot calcula conform modelului prezentat, utilizând relaţia (5.12) pentru x1 şi relaţia de recurenţă (5.13) pentru celelalte valori xn, dacă n ≥ 2:
5003
2503333005582)2(31
5,5582
333500250700)1(21
7005002001000)(11
32323
21212
111
=−++⋅
=−++⋅⋅=
=−++
=−++⋅⋅=
=−+=−+⋅=
vvcxx
vvcxx
vcax
………………………………………………………… Rezultatele complete ale calculului mărimilor vn, cn şi xn, pentru
1 ≤ n ≤ 9, sunt indicate în tabelul 5.1.
Tabelul 5.1. n 1 2 3 4 5 6 7 8 9
cn
vn
200
500
250
333
300
250
350
200
400
167
450
143
500
125
550
111
600
100
xn
yn
700
417
558
383
500
400
475
438
467
474
468
518
475
564
486
611
500
659
Observând valorile obţinute pentru xn, rezultă: 467)(min915 ==
≤≤ nnxx € ,
deci durata optimă este: n̂ = 5 săptămâni. Pentru a rezolva mai rapid problema, se pot utiliza inegalităţile (5.14) şi
(5.15) de mai sus, introducând în tabelul 5.1 şi mărimea yn. Valoarea optimă, n̂ , se obţine comparând, pentru fiecare perioadă n, xn
cu yn şi yn-1. Astfel, ne putem opri cu calculul la 5ˆ =n , pentru care:
xn = 467 < yn = 474, xn = 467 > yn-1= 438 (şi nu la n =9).
Pentru cazul unui model (proces de înlocuire al unui echipament) determinist continuu, se consideră că echipamentul considerat poate fi înlocuit
Conf. dr. ing. Andrei Dumitrescu
12
la orice moment. Un astfel de proces de înlocuire este caracterizat de următoarele elemente de cost:
A − preţul de achiziţionare al echipamentului, β(t) − costul cumulat de utilizare al echipamentului (incluzând
reparaţiile şi mentenanţa) până la momentul t, α(t) − preţul vânzare al echipamentul la momentul t.
Modelul presupune, în mod analog cu modelul discret prezentat anterior, că funcţia β(t) este crescătoare şi derivata sa este:
β’(t) = b(t) ≥ 0 , (5.17)
iar funcţia α(t) este descrescătoare şi derivata sa este:
α’(t) = a(t) ≤ 0. (5.18)
În plus, există inegalităţile (pentru t = 0):
α(0) ≤ A , β(0) ≥ 0 . (5.19)
Dacă echipamentul considerat iese din serviciu la momentul t = T, cheltuiala totală aferentă este dată de relaţia:
p(T) = A + β(T) - α(T) . (5.20)
În schimb, cheltuiala medie (cea pe care dorim să o minimizăm), pentru acelaşi moment T, se determină astfel:
x(T) = p(T)/T . (5.21)
Dacă se consideră drept criteriu de optimizare minimizarea cheltuielilor medii şi se notează cu T̂ valoarea optimă a timpului de înlocuire (durata optimă de viaţă) al echipamentului, aceasta se obţine din condiţia de minim pentru funcţia x(T): min x(T).
Această condiţie se obţine pentru x’(T) = 0, ecuaţie a cărei soluţie este T . Efectuând derivarea funcţiei x(T), din ecuaţia (5.21) rezultă succesiv:
[p’(T) T – p(T)] / T2 = 0 ⇒ [β’(T) - α’(T)] T - β(T) + α(T) – A = 0 ⇒ ⇒ b(T) – a(T) = [A + β(T) - α(T)] / T ⇒ b(T) – a(T) = x(T) .
Dacă b’(T) > 0 şi a’(T) < 0, rezultă că:
p”(T) = b’(T) - a’(T) > 0 , (5.22)
iar soluţia T a ecuaţiei x’(T) = 0 este un punct de minim, deci corespunde duratei optime T̂ .
Ca modele pentru funcţiile β(t) şi α(t), s-au propus funcţii exponenţiale, liniare sau liniare pe domenii (de exemplu, pentru α(t), α(t)=0 pentru t > ao).
Aplicaţia 5.3: Preţul de achiziţie al unui echipament este A = 1000 €. Costul cumulat de utilizare este dat de funcţia următoare: β(t) = B t2 / 2 , unde B = 20 €/an/an. Echipamentul nu poate fi vândut, deoarece preţul de vânzare în orice moment t este zero [ α(t) ≡ 0 ]. Se cere să se determine durata optimă de viaţă a echipamentului, T̂ .
Rezolvare: Se determină funcţiile: a(t) = α’(t) ≡ 0 ; b(t) = β’ (t) = B t ;
p(T) = A + 0,5 B T2 ; x(T) = [ A + 0,5 B T2 ] / T .
Bazele Ingineriei Sistemelor de Producţie 5. Teoria jocurilor. Teoria echipamentelor
13
Se rezolvă apoi ecuaţia x’(T) 0, echivalentă cu b(T) – a(T) = x(T). Pentru cazul studiat, rezultă succesiv:
b(T) = x(T) ⇒ B T = [A + 0,5 B T2] / T ⇒ ⇒ B T2 = A + 0,5 B T2 ⇒ A = 0,5 B T2 ,
iar soluţia aplicaţiei este:
1020100022
=⋅
=⋅
=B
AT ani .
Aceeaşi soluţie se obţine şi dacă se calculează direct derivata lui x(T):
x’(T) = [ (B T) T - (A + 0,5 B T2) ] / T2 = (0,5 B T2 - A) / T2 ...
Deoarece p”(T) = b’(T) = B = 20 > 0, soluţia T este un punct de minim, deci corespunde duratei optime T̂ . Ca urmare T̂ = 10 ani.
Aplicaţia 5.4 (funcţii exponenţiale): Costul cumulat de utilizare şi preţul de vânzare ale unui echipament sunt date respectiv de funcţiile:
β(t) = d (ekt – 1) , α(t) = A e-ct , unde c, d, k > 0,
iar A > d este preţul de achiziţie al echipamentului. Să se determine ecuaţia a cărei soluţie este durata optimă de viaţă a echipamentului, T̂ .
Rezolvare: Se obţin întâi funcţiile:
a(t) = α’(t) = - c A e-ct < 0 ; b(t) = β(t) = k d ekt > 0 ; p(T) = A + d (ekT – 1) – A e-cT ; x(T) = [A (1 - e-cT) + d (ekT – 1)] / T.
Ecuaţia a cărei soluţie poate fi durata optimă este:
b(T) – a(T) = x(T) ⇒ ⇒ k d ekT + c A e-cT = [ A (1 - e-cT) + d (ekT – 1) ] / T ⇒ ⇒ d (k T ekT + 1 - ekT) = A (1 - e-cT- c T e-ct) ⇒ ⇒ d / A = [e-cT (1 + c T) – 1 ] / [ekT (1 – k T) – 1 ] .
Pentru ca soluţia ecuaţiei de mai sus să fie durata optimă de viaţă a echipamentului studiat, trebuie îndeplinită condiţia:
p”(T) = k2 d ekt + c2 A e-ct > 0.
5.2.2. Modele aleatoare discrete pentru determinarea duratei optime de viaţă a unui echipament
În cazul unui astfel de model, durata de viaţă a unui echipament se defineşte ca fiind intervalul de timp T, dintre punerea sa în serviciu şi apariţia unei avarii grave.
Mărimea T este definită ca o variabilă aleatoare discretă, ce poate lua valorile 0, 1, …, i, …, cu probabilităţile pi, care reprezintă probabilitatea de avariere a echipamentului în perioada (ziua, luna, anul etc.) i. Aceste probabilităţi prezintă proprietăţile:
pi > 0 , ∑∞
=
=0
.1i
ip (5.23)
Conf. dr. ing. Andrei Dumitrescu
14
Echipamentele pot fi considerate nereparabile (consumabile), dacă odată defecte nu mai este posibilă repararea lor, sau nu, în caz contrar. Se pot, de asemenea, face delimitări între avariile majore şi cele minore.
De asemenea, modelul se poate completa prin introducerea unei limite a duratei de viaţă (funcţionare) a echipamentului, τ (practic, se impune condiţia: T ≤ τ), care ar putea corespunde uzurii sale morale.
Se defineşte siguranţa în funcţionare a echipamentului ca fiind probabilitatea de funcţionare fără avarii pentru un interval de timp dat.
Această probabilitate se mai numeşte probabilitate de supravieţuire şi se notează Ui. Astfel, dacă se consideră perioada 0 - i,
∑∞
+=
=>=1
)(ij
ji piTPU . (5.24)
Din relaţia de definiţie de mai sus, rezultă imediat:
pi = Ui-1 – Ui . (5.25)
Se defineşte apoi riscul de avarie (numit şi nesiguranţă) ca fiind probabilitatea de apariţie a unei avarii în primele i perioade de funcţionare:
∑=
−==≤=i
jiji UpiTPF
0 1)( . (5.26)
Se defineşte, de asemenea, rata avariilor în cursul perioadei i, ri, ca fiind probabilitatea condiţionată de a avea o avarie în perioada i, dacă echipamentul depăşeşte „vârsta” i-1 (T > i-1):
1)1()1()11(
−
=−>≤<−
=−>≤<−=i
ii U
piTP
iTiPiTiTiPr . (5.27)
Din relaţiile de mai sus rezultă:
∏ ∏=
−
=
−=−=i
j
i
jjiiji rrprU
1
1
1
)1( ),1( . (5.28)
Modul de variaţie tipic al mărimilor Ui şi ri este ilustrat în figura 5.1. În această figură, se disting următoarele trei perioade principale în „viaţa” unui echipament: I – perioada de rodaj (caracterizată printr-o rată ridicată a avariilor, datorate defectelor de fabricaţie); II – perioada de funcţionare normală; III – perioada de uzură avansată (caracterizată de o rată a avariilor cu creştere continuă).
Fig. 4.1. Curba de uzură a unui echipament
Ui, ri ri Ui Perioada Perioada Perioada I II III
0 t
Bazele Ingineriei Sistemelor de Producţie 5. Teoria jocurilor. Teoria echipamentelor
15
Dacă rata avariilor este constantă (ri = r = constant), aplicând relaţiile prezentate rezultă:
1)1( ,)1( −−=−= ii
ii rrprU . (5.29)
În acest caz, durata de viaţă, T , este caracterizată printr-o lege de repartiţie geometrică.
Dacă rata avariilor, ri, este crescătoare, pot fi aplicate următoarele legi de distribuţie pentru variabila aleatoare T:
• legea binomială:
0 ,10 ,0 , ,)1( 1 ≥<<>Ν∈−= − ipnnppCp niini , (5.30)
• legea lui Poisson:
0 ,0 ,! / ≥>= − iiep ii λλ λ . (5.31)
Durata medie a vieţii echipamentului considerat reprezintă, de fapt, valoarea medie a variabilei aleatoare T:
∑ ∑∞
=
∞
=
=⋅=1 0
.i i
ii UpiT (5.32)
Corespunzător ratei avariilor, se determină o rată de [re]aprovizionare, Ri, care reprezintă necesarul de aprovizionat / reaprovizionat pentru perioada i, în funcţie de necesităţile de înlocuire a echipamentelor uzate.
Se poate, de asemenea, defini o politică de [re]aprovizionare, în următoarele variante:
• înlocuirea după vârstă, care constă în înlocuirea echipamentului în caz de avarie sau dacă a ajuns la vârsta limită τ, ceea ce implică determinarea valorii optime a lui τ, τ̂ , din condiţia minimizării cheltuielilor;
• înlocuirea în bloc, care constă în înlocuirea la apariţia avariei sau la momentele de timp τ, 2τ, ..., kτ, unde k ≥ 1;
• înlocuirea periodică cu o „reparaţie minimă” a avariei, care constă în înlocuirea periodică la momentele kτ, iar dacă apare o avarie în intervalul (k-1)τ ≤ t ≤ kτ, se va efectua o numai o „reparaţie minimă”.
În încheiere, precizăm că un model aleator discret se poate extinde la unul continuu, cu ajutorul noţiunii de densitate de probabilitate.
Teste de autoevaluare (secţiunea 5.2)
1. Care este semnificaţia noţiunii de echipament în teoria echipamentelor?
2. Cum se defineşte durata optimă de viaţa a unui echipament? Pe baza cărui criteriu se determină această durată?
3. Care este criteriul de optimizare utilizat în teoria echipamentelor? 4. Descrieţi pe scurt algoritmul de determinare a duratei optime de viaţă
a unui echipament utilizând un model determinist discret.
Conf. dr. ing. Andrei Dumitrescu
16
5. Când credeţi că se foloseşte un model discret şi când unul continuu în teoria echipamentelor? Exemplificaţi.
6. Care este avantajul utilizării, în teoria echipamentelor, a unui model aleator în locul unui model determinist?
7. Cum se defineşte siguranţa în funcţionare a unui echipament? Dar riscul de avarie?
8. Care sunt variantele posibile ale unei politici de aprovizionare?
Probleme propuse (secţiunea 5.2)
1. Preţul de achiziţionare al unui echipament este a = 1500 lei (noi). Preţul de vânzare al echipamentului la sfârşitul a n ani de funcţionare este:
vn = 1000 / n (exprimat în lei noi) . Cheltuielile de utilizare a echipamentului aferente anului n sunt:
cn = 100 + 30 n (exprimat în lei noi) . Se cere să se determine în a câtelea an este indicat să se înlocuiască
echipamentul (durata economică a vieţii echipamentului, exprimată în ani), dacă se urmăreşte minimizarea cheltuielilor medii anuale.
2. Preţul de achiziţie al unui echipament este A = 250 lei (noi). Costul cumulat de utilizare este dat de funcţia următoare:
β(t) = 10 t2 + 13 t (exprimată în lei) . Echipamentul nu poate fi vândut, deoarece preţul de vânzare în orice
moment t este zero. Se cere să se determine durata optimă de viaţă a echipamentului, T̂ .
Bazele Ingineriei Sistemelor de Producţie 5. Teoria jocurilor. Teoria echipamentelor
17
Bibliografie
1. Baciu, A., Pascu, A., Puşcaş, E., Aplicaţii ale cercetării operaţionale,
Editura Militară, Bucureşti, 1988. 2. Bărbatu, Gh., Ionescu, V., Cercetarea operaţională în întreprinderile
industriale, Editura Tehnică, Bucureşti, 1981. 3. Dumitrescu, A., Bazele ingineriei sistemelor, Editura Universităţii
din Ploieşti, 2005. 4. Dumitrescu, I., ş.a., Aplicaţii inginereşti ale calculatoarelor, Vol. 2 –
Optimizări, Editura Didactică şi Pedagogică, Bucureşti, 1976. 5. Maliţa, M., Zidăroiu, C., Matematica organizării, Editura Tehnică,
Bucureşti, 1971. 6. Nica, V., Ciobanu, Gh., ş.a., Cercetări operaţionale, Vol. I, Ed.
Matrix Rom, Bucureşti, 1998. 7. Oprişan, Gh., Simion, E., Elemente de cercetări operaţionale şi
criptologie, Editura Politehnica Press, Bucureşti, 2002. 8. Rendi, Dorina-Marieta, Metode ale cercetării operaţionale:
programare liniară, teoria jocurilor, teoria grafurilor, Editura Orizonturi Universitare, Timişoara, 2002.
9. Saaty, T.L., Mathematical Methods of Operational Research, McGraw Hill, 1959.
10. Vrânceanu, Gh., Mititelu, Şt., Probleme de cercetare operaţională, Editura Tehnică, Bucureşti, 1978.
Soluţiile problemelor propuse
Secţiunea 5.1
Strategia optimă pentru jucătorul A este a3, iar pentru jucătorul B, b3. Jocul nu este strict determinat (C nu prezintă punct de echilibru).
Secţiunea 5.2
1. Timpul optim de înlocuire este: n̂ = 9 ani.
2. Durata optimă de viaţă este: T̂ = 5 ani.