Metode Matematice de Optimizare a Problemelor de Transport Si a Deciziilor in Intreprinderile...

203
CUPRINS INTRODUCERE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 CAP.1 PROGRAMARE LINIARĂ . . . . . . . . . . . . . . . . . . . . .4 1.1 Consideraţii generale . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Soluţiile unei probleme de programare liniară . . . . . . 7

description

Metode Matematice de Optimizare a Problemelor de Transport Si a Deciziilor in Intreprinderile Industriale

Transcript of Metode Matematice de Optimizare a Problemelor de Transport Si a Deciziilor in Intreprinderile...

Metode Matematice de Optimizare a Problemelor de Transport si a Deciziilor in Intreprinderile Industriale

CUPRINS INTRODUCERE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3CAP.1 PROGRAMARE LINIAR . . . . . . . . . . . . . . . . . . . . .41.1 Consideraii generale . . . . . . . . . . . . . . . . . . . . . . . . . .41.2 Soluiile unei probleme de programare liniar . . . . . . 71.3 Bazele matematice ale metodei simplex primal pentru

rezolvarea problemelor de programare liniar. . . . . . 13Probleme de programare liniar propuse spre

rezolvare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35Probleme de programare liniar cu aplicaii n

procesul de producie propuse spre rezolvare . . . . . . 391.4 Modele liniare de tip transport. Folosirea programrii

liniare n optimizarea planului de transport . . . . . . . .45Probleme de tip transport propuse spre rezolvare. . . .67CAP.2 OPTIMIZAREA DECIZIILOR PRIN METODE

MATEMATICE . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 70 2.1 Probleme rezolvate de decizie n condiii de

certitudine. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .70 Probleme propuse spre rezolvare . . . . . . . . . . . . . . . . 84 2.2 Probleme rezolvate de decizie n condiii de

incertitudine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .92 Probleme propuse spre rezolvare. . . . . . . . . . . . . . . . 96

2.3 Probleme de decizie n condiii de risc . . . . . . . . .100 2.3.1 Arbori cu probabiliti simple. . . . . . . . . . . . . 100

2.3.2 Arbori cu probabiliti condiionate . . . . . . . .111BIBLIOGRAFIE SELECTIV. . . . . . . . . . . . . . . . . . . . . . .122

INTRODUCERE

Prezentul material ajuttor ofer posibilitatea nelegerii de ctre studeni a utilizrii modelelor economico-matematice n organizarea i conducerea produciei.

nainte de prezentarea metodelor i tehnicilor matematice de optimizare a activitilor folosite n managementul produciei industriale, se impune s facem urmtoarele precizri : n primul rnd, plecm de la considerentul c elementele de algebr liniar studiate n anul I sunt cunoscute, insistndu-se mai mult pe nelegerea semnificaiilor matematice i economice ale aspectelor prezentate.

n al doilea rnd, limbajul pe care l-am folosit nu este strict riguros matematic, prefernd un limbaj mai descriptiv, bazat pe exemplificri, menit s asigure o nelegere mai bun i mai profund a textului.

n al treilea rnd, contieni de faptul c multe dintre probleme sunt prezentate prea sumar, justificm aceasta prin spaiul restrns al actualului material ajuttor precum i prin dorina noastr de a oferii studenilor o imagine ct mai cuprinztoare asupra posibilitilor pe care le are matematica i utilizarea acesteia n economie. Lista bibliografic de la sfritul fiecrui capitol ntregete cunotinele prezentate aici.

3CAPITOLUL 1

PROGRAMARE LINIAR

1.1 CONSIDERAII GENERALEO problem de programare liniar sete format din dou pri distincte, i anume :

un numr de restricii liniare :

fi(x1,..,xn)bi, i=1,,k,

fj(x1,..,xn)=bj, j=k+1,..,p, (1.1)

fe(x1,..,xn)be, e=p+1,..,m,

xk0, k=1,2,...,n,

care exprim condiiile problemei;

- o funcional liniar, f(x1,..,xn), obiectivul problemei (maximizarea sau minimizarea acesteia).

Problemele economice care conduc la modele de programare liniar sunt prezentate n curs i, ca atare nu le mai relum aici. Din aspectele prezentate n curs, a rezultat c modelul matematic al unei probleme de programare liniar, izvort din practica de producie, este n general de forma: n

[max] sau [min] z=cj xj (1.2) j=1

4 n aij xj = di , i=1,,m; (1.3)

j=1 xj 0, j=1,,n . (1.4)

Vom numi form standard a unei probleme de programare liniar, forma urmtoare :

n

[max] sau [min] z=cj xj (1.5) j=1 n aij xj = di , i=1,,m; (1.6)

j=1 xj 0, j=1,,n . (1.7)

Aadar, o problem de programare liniar este prezentat sub form standard atunci cnd restriciile sale sunt numai egaliti, iar variabilele ce intr n model sunt toate pozitive.

Reamintim c o restricie de forma (1.3), care nu e de tip egalitate, poate fi adus la forma unei egaliti, fie prin adugarea unei mrimi pozitive fie prin scderea unei mrimi pozitive.

5

Pentru a ne obinui cu limbajul utilizat, mai precizm c problema de programare liniar (P.L.) se spune c are form canonic dac toate restriciile (1.6) sunt inegaliti de acelai sens. Aadar, o problem de (P.L.) se prezint sub form canonic, atunci cnd toate restriciile problemei au semnul ( cnd se urmrete maximizarea funciei obiectiv, sau cnd toate restriciile problemei au semnul ( cnd trebuie minimizat funcia obiectiv, n ambele cazuri variabilele (necunoscutele) problemei fiind nenegative.

O problem de (P.L.) este pus sub forma standard de lucru dac :

este sub form standard ; n matricea coeficienilor exist o matrice unitate de dimensiune egal cu numrul restriciilor;

termenii liberi ai restriciilor sunt nenegativi.

O alt form, mai concentrat, de scriere o reprezint aa- zisa form matriceal, adic:

[max] sau [min] z = CX (1.8)

AX = d (1.9)

X 0 , unde (1.10)

6

a11 . a1n

A = (aij) i= 1, . . . . .,m =

j = 1, . . . . .,n am1 amn

x1X = x2, C = (c1, c2, , cn)

xn

d1 d = d2 dn

1.2 SOLUIILE UNEI PROBLEME DE PROGRAMARE LINIAR

n studiul rezolvrii metodelor de programare liniar, se pornete de la forma standard. S considerm, deci, modelul problemei de programare liniar sub form standard:

[max/min] z = CX, (1.11)

(M) AX =b, (1.12)

X 0 (1.13)

7

n care matricea A are m linii i n coloane. Presupunem, n plus, c sistemul restriciilor (1.12) are cel puin o soluie, n caz contrar rezolvarea modelului pierzndu-i sensul.

Dac rangul matricei A ar fi mai mic dect m, sistemul restriciilor fiind totui compatibil, o parte dintre ecuaiile cuprinse n (1.12) ar fi consecine ale celorlalte, deci ar putea fi nlturate. De aceea vom considera nc de la nceput c rangul matricei A este egal cu m. De asemenea, vom considera c numrul variabilelor n este strict mai mare dect numrul restriciilor m, aceast condiie evitnd unicitatea soluiei sistemului de restricii.

Vom numi simplu, soluie a modelului (M), un vector coloan X, n-dimensional, care verific sistemul de restricii (1.12). Dac, n plus, vectorul X verific i condiiile de nenegativitate (1.13) se spune c el reprezint o soluie realizabil a modelului (M). n acest fel, rezolvarea modelului poate fi urmrit n spaiul vectorial n-dimensional, numit i spaiul soluiilor. n cele ce urmeaz, convenim s notm cu M mulimea soluiilor realizabile ale modelului (M).

Exemplul 3.1. S considerm, pentru exemplificare, 8

urmtoarele restricii ale unui model de programare liniar:x1 + 2x2 + x3 + 2x4 = 8

2x1 + x2 + x3 + 3x4 = 9

Soluia X1 =(3 2 1 0)t a acestui sistem este o soluie realizabil a modelului, deoarece nu are nici o component strict negativ. n schimb, soluia X2 = (3 3 3 1)t este o soluie nerealizabil a modelului, avnd componenta x3 strict negativ (nu verific condiia corespunztoare de nenegativitate).

n construirea algoritmului de rezolvare a modelelor de programare liniar, vom ine seam ndeosebi de natura diferitelor componente ale soluiilor, de a fi nule sau nu. n acest scop, s considerm spaiul vectorial m-dimensional, numit spaiul restriciilor, n care considerm cei n vectori-coloan ai matricei A, notai prin aj , j=1, . . . , n precum i vectorul b, al termenilor liberi. Cu aceste notaii, sistemul de restricii (1.12) poate fi scris sub forma vectorial (1.14), unde componentele x1, x2, x3, . . . . , xn, ale unei soluii oarecare X, sunt mrimi scalare nedeterminate:

x1 a1 + x2 a2 + x3 a3 + . . . . . + xn an = b (1.14)

9

n acest fel, fiecare component xj, j= 1, 2, 3, . . . . , n, a unei soluii, se ataeaz unui vector coloan aj din matricea A.

Dac rangul matricei A este egal cu m, exist cel puin o grup de m vectori dintre acetia, ce formeaz o baz n Rm . Dac n soluia X numai componentele xj1, xj2, . . . , xjm ce corespund vectorilor din baza B, sunt diferite de zero, aceast soluie se numete soluie de baz a modelului (M).

Componentele unei soluii de baz pot fi de dou tipuri, i anume:

componentele ce corespund la vectori ce nu fac parte din baza respectiv, numite i componente nebazice, acestea fiind toate egale cu zero (prin definiie);

componente ce corespund la vectorii din baz, numite i componente bazice, dintre acestea fcnd parte toate acele componente ale soluiei ce sunt diferite de zero.

Din cele de mai sus, rezult c o soluie de baz se poate determina fixnd mai nti m vectori-coloan din matricea A, care s formeze o baz n Rm, dup care efectum urmtoarele operaii:

10

nlocuim n sistemul restriciilor toate variabilele ce corespund vectorilor ce nu fac parte din baza considerat, prin zero; rezolvm sistemul tip Cramer rmas, obinnd astfel i valorile componentelor bazice.

Din definiia soluiei de baz, deducem c o astfel de soluie poate avea cel mult m componente diferite de zero, aceste componente n mod obligatoriu la vectori-coloan liniari independeni ai matricei A. n cazul cnd o soluie de baz are mai puin de m componente diferite de zero, se zice c ea este degenerat, n caz contrar ea fiind nedegenerat.

Exemplul 3.2. Fie urmtorul sistem de restricii, aparinnd unui model de programare liniar:

x1 + x2 + x3 + x4 + 3x5 = 6,

x1 + 3x2 + 2x3 + 3x4 + x5 = 12

Soluia X1 = ( 3 3 0 0 0 )t este o soluie de baz realizabil i nedegenerat, avnd dou componente nenule pozitive, ce corespund la vectorii a1 i a2 din R2, i anume:

1 1

a1 = 1 i a2 = 3

11Pe de alt parte, soluia X2 = ( 15 0 0 0 3 )t este o soluie de baz nerealizabil i nedegenerat, ce corespunde bazei

B2 = {a1,a5}. n sfrit, soluia X3 = ( 0 0 6 0 0 )t este o soluie de baz i degenerat, avnd o singur component nenul, n cazul nostru strict pozitiv. Se poate observa c aceast soluie poate corespunde la mai multe baze, ca de exemplu, B3 = {a1,a3} ,

B4 = {a3,a4} etc..

n continuare, prezentm cteva rezultate teoretice legate de soluiile problemei de programare liniar care simplific, cutarea soluiilor optime.

Menionm, fr demonstraie, urmtoarele teoreme:

Teorema 3.1. Mulimea soluiilor realizabile, corespunztoare unui model de programare liniar, este o mulime convex.Teorema 3.2. Dac funcia de eficien a unui model de programare liniar are optim finit, valoarea optim este atins cel puin ntr-un vrf al mulimii soluiilor realizabile.Teorema 3.3. Dac funcia de eficien a unui model de programare liniar are optim finit, atunci mulimea soluiilor optime ale acestui model este o mulime convex, iar vrfurile ei se afl printre vrfurile mulimii soluiilor realizabile ale modelului.

12

Conform teoremelor prezentate, determinarea soluiilor optime ale unui model de programare liniar ar putea fi fcut calculnd i corectnd mai nti toate soluiile de baz ale modelului (acestea fiind n numr limitat, numrul lor fiind cel mult egal cu Cnm) pentru a extrage pe cele realizabile ce maximizeaz, respectiv minimizeaz funcia de eficien (funcia obiectiv). Un astfel de procedeu cere un volum mare de calcule, mai ales n cazul unui model de dimensiuni mari, cnd el devine practic imposibil.

1.3 BAZELE MATEMATICE ALE METODEI SIMPLEX PRIMAL PENTRU REZOLVAREA PROBLEMELOR DE PROGRAMARE LINIAR

Metoda simplex primal, sau metoda mbuntirilor succesive, evit cercetarea exhaustiv a tuturor soluiilor de baz ale unui model de (P.L.), construind succesiv soluii realizabile de baz din ce n ce mai bune ale modelului pn cnd este obinut o soluie de baz optim. Evident, prin soluie mai bun vom nelege o soluie care d pentru funcia de eficien o valoare mai mare, respectiv mai mic dect cele precedente, dup 13

cum funcia de eficien trebuie s devin maxim, respectiv minim. n descrierea i justificarea metodei algoritmului simplex primal, ne vom referi iniial la un model de (P.L.) n care funcia de eficien trebuie s devin maxim, model de forma urmtoare: n

[max] z = ( cj xj (1.15)

n j=1

(M) ( aj xj = b (1.16)

j=1 x ( 0 (1.17)

S presupunem c dispunem de o soluie realizabil de baz a modelului, notat cu X, soluie pe care o putem considera, fr a micora generalitatea raionamentelor ce urmeaz, corespunznd bazei formate din vectorii a1, a2, . . . , am, baza nsi fiind notat cu B. Pentru sistematizarea calculelor, toi vectorii-coloan aj, j = 1,2,,n precum i vectorul b al termenilor liberi n baza B, XB se pot trece ntr-un tabel de forma celui ce urmeaz: 14 Tabelul 1.1

CBBXBc1c2C3. .. . . .. . . .. . .. . . .. .cn

a1a2A3. .. . . .. . . .. . .. . . .. .an

C1a1x1(11(12(13 ... . . .. . . .. . .. . . ..(1n

C2a2x2(21(22(23 ... . . .. . . .. . .. . . ..(2n

:::::: ... . . .. . . .. . .. . . ...:

:::::: ... . . .. . . .. . .. . . ...:

:::::: ... . . .. . . .. . .. . . ...:

:::::: ... . . .. . . .. . .. . . ...:

cmamxm(m1(m2(m3. . . .. . . .. . .. . . .(mn

fj_F1f2f3. . . .. . . .. . .. . . .fn

Astfel, baza este trecut pe coloana marcat cu B, componentele fiecrui vector aj , j = 1,2,,n se gsesc n tabel pe coloanele corespunztoare acestor vectori. Pentru uniformitate, n tabel s-au notat i componentele vectorilor din baz sub forma general, dei ei apar n particular ca vectori unitari.

Pentru scopuri legate de calculele ce urmeaz a fi efectuate, tabelul mai conine deasupra vectorilor aj, j = 1,2,,n, coeficienii cj din funcia de eficien, ce corespund variabilelor ataate acestor vectori. De asemenea, tabelul conine i o coloan suplimentar CB, cu coeficienii cj corespunztori variabilelor 15

ataate vectorilor din baz. Aceast din urm coloan reprezint, sub form transpus, un vector-linie m-dimensional, ce are drept componente acele componente ale vectorului C ce corespund vectorilor din baza B, n ordinea indicat de baz.

CB = (c1,c2,,cm) (1.18)

n calculele ce urmeaz a fi prezentate, legate de testarea optimalitii, sau de mbuntire a soluiei X, cu ocazia calculelor apar anumite sume ce pot fi ataate vectorilor aj,

j=1,,n, sume pe care le vom nota convenional prin fj i care au urmtoarele expresii:

m

fj = ( ck (kj , j=1,2,3,,n. (1.19)

k=1

Aceste sume, jucnd un rol deosebit de important n aplicarea algoritmului simplex, se ataeaz tabelului 1.1, sub forma unei linii suplimentare.

De observat c fiecare cantitate fj se obine practic prin nsumarea produselor dintre fiecare element al coloanei CB i elementul corespunztor de pe coloana aj a tabelului 1.1.

Expresia matriceal a cantitilor fj este deci urmtoarea:

16

fj = CB aj , j=1,2,3,,n. (1.20)

S redm cele de mai sus pe un exemplu numeric.

Exemplul 4.1. Fie modelul de (P.L.):

[max] z = 2x1+3x2+x3+4x4 x1 + x3+2x4=8,

x2+2x3+x4=10,

xj 0, j=1,2,3,4

Se observ c modelul de (P.L.) este pus sub forma standard de lucru, ceea ce nseamn c:

este sub forma standard;

n matricea coeficienilor exist o matrice unitate de dimensiune egal cu numrul restriciilor; termenii liberi ai restriciilor sunt nenegativi.CBBXB2 3 1 4

a1 a2 a3 a4

2

3a1a28

101 0 1 2

0 1 2 1

Fj2 3 8 7

f1= 21+30 =2 ; f2= 20+31 =3 ; f3= 21+32 =8 ; f4= 22+31 =7

17

Prezentm, n continuare, fr demonstraie urmtoarele teoreme:

Teorema 4.1. (Testul de optimalitate a soluiei sau criteriul optim). Dac pentru o soluie realizabil de baz X, a unui model de programare liniar, avem cj - fj ( 0, j=1,2,3,,n, n cazul modelului de maxim respectiv fj - cj ( 0, j=1,2,3,,n, n cazul modelului de minim, atunci soluia X este optim.

n cadrul tabelului de programare liniar vom nota diferenele cu (j = cj - fj ( 0 pentru problema de maxim, respectiv (j = fj - cj ( 0 pentru cea de minim.

Teorema 4.2. (Criteriul de mbuntire a soluiei). Fiind dat o soluie de baz realizabil X, nedegenerat, a unui model de programare liniar, dac exist cel puin un indice j, j=1,2,,n, pentru care s avem cj - fj > 0, n cazul unui model de maxim, respectiv fj - cj , n cazul unui model de minim, atunci se poate determina o alt soluie realizabil de baz Y, care s dea o valoare mai bun dect X pentru funcia de eficien, iar baza corespunztoare soluiei Y s difere de baza corespunztoare soluiei X printr-un singur vector.

Prezent, n continuare, urmtorul tabel complet al unui model de (P.L.):

18

Tabelul 1.2.

CBB

XB

c1 c2 . . . . . . . cm . . . . . . . cj . . . . . . . . cn

a1 a2. . . . . . . . am . . . . . . aj. . . . . . . . an

c1a1X1(11 (12. . . . . . . (1m. . . . . . .(1j. . . . . . . (1n

c2a2X2(21 (22. . . . . . . (2m. . . . . . .(2j. . . . . . .(2n

:::: : : : :

ciaixi(i1 (i2. . . . . . . (im. . . . . . . (ij . . . . . . (in

:::: : : : :

cmamxm(m1 (m2. . . . . . .(mm. . . . . . .(mj. . . . . . (mn

(j=cj-fjc1-f1 c2-f2.. . . . . cm-fm . . . . .cj-fj . . cn-fn

Se observ c, fa de tabelul 1.1, am renunat la linia fj, nlocuind-o cu (j.

Pentru a continua algoritmul simplex deci pentru a mbuntii soluia cu care am pornit, trebuie s tim:

ce vector nebazic poate intra n combinaie cu m-1 vectori bazici, pentru a forma mpreun o baz mai bun;

ce vector bazic este nlocuit cu vectorul nebazic gsit.

Conform celor artate mai sus, vectorul aj, cruia i corespunde o diferen (j strict pozitiv, este cel ce urmeaz s intre n noua baz, fapt indicat printr-o sgeat alturat coloanei acestui vector. Aadar, vom alege pe oricare din vectorii nebazici pentru19

care diferena (j = cj-fj >0, de preferat (dar nu obligatoriu) pe cel pentru care diferena pozitiv (j este cea mai mare. Dac sunt mai multe diferene maxime egale, se alege oricare dintre ele.

De asemenea, pe coloana B a tabelului, este menionat n mod special vectorul ai ce urmeaz s ias din baz, fapt ilustrat de sgeata ce se gsete n dreptul lui.

Pentru a gsi vectorul ce trebuie eliminat din baz se face raportul, component cu component, ntre coloana XB i coloana care intr aj, mprirea fcndu-se numai la componentele strict pozitive ale lui aj i se alege raportul cel mai mic, pentru ca noua soluie s aib componentele nenegative.

Elementul (ij, care apare ncercuit n tabelul 1.2 i care se gsete la intersecia coloanei vectorului aj, ce urmeaz s intre n baz, cu linia vectorului ai, ce iese din baza B, se numete pivot.

Componenta yi, ce urmeaz s ia locul componentei xi, se obine prin mprirea acesteia la pivot, celelalte componente bazice ale soluie Z determinndu-se din tabelul 1.2, prin regula ilustrat n figura 1.1, cunoscut sub numele de regula dreptunghiului.20

Urmtoarele expresii permit calculul componentelor noii soluii de baz Y : xi

yj = (1.21)

(ij

yk = xk - yj(kj = xk - xi (kj, pentru k=1,2,,i-1,i+1,..,m (1.22)

(ij

n legtur cu aceste relaii, se impun condiiile: xi 0 (1.23)

(ij

xk (ij - xi (kj

0, pentru k=1,2,,i-1,i+1,i+2,,m (1.24)

(ij

xi (ij

Tabel vechi

xk (kj

xi yj =

(ij

xk (ij xi (kj Tabel nou

yk =

(ij

Fig. 1.1 Calculul componentelor soluiei Y

Deoarece prin ipotez avem xi > 0, inegalitatea (1.23) impune condiia (ij > 0, adic pivotul trebuie s fie strict pozitiv.

21

Precizm mai sus c, pentru a gsi vectorul ce trebuie eliminat din baz, se face raportul, component cu component, ntre coloana XB i coloana vectorului aj care intr n baz. Ilustrarea acestor operaii este prezentat n figura 1.2.

x1 (1j x1/(1j x2 (2j x2/(2j

xm (mj xm/(mjFig 1.2. Operaiile efectuate pentru gsirea vectorului ce trebuie eliminat din baz

De remarcat este faptul c acolo unde componenta (kj ( 0 raportul nu se face, iar dintre rapoartele ultimei coloane ne oprim la cel mai mic, acesta indicnd linia vectorului ai ce urmeaz a fi eliminat din baza B. Aceast regul poart numele de criteriu de ieire din baz.

Algoritmul simplex este deci un algoritm iterativ, n care sunt cercetate succesiv soluii realizabile de baz din ce n ce mai bune, pornind de la o soluie realizabil de baz oarecare, pn cnd este obinut o soluie optim.

22

Etapele ce trebuie parcurse la o iteraie oarecare, cnd se dispune de o soluie X, sunt urmtoarele:

Etapa nti ( Verificarea optimalitii )

Cu ajutorul unui tabel de forma tabelului 1.1 se calculeaz cantitile fj, j=1,,n, apoi diferenele (j = cj - fj, n cazul modelului de maxim, respectiv (j = fj - cj, n cazul modelului de minim. Dac toate aceste diferene sunt nepozitive, soluia cercetat X este potim i algoritmul ia sfrit. n caz contrar, se trece la etapa urmtoare.

Etapa a doua (mbuntirea soluiei)

Aplicnd criteriul de intrare n baz, se determin mai nti un vector aj, a crui diferen (j este strict pozitiv, n cazul cnd exist mai multe diferene de acest fel alegndu-se cea mai mare dintre ele. Apoi, pentru aplicarea criteriului de ieire din baz, se fac rapoartele xi /(ij, dintre care cel mai mic determin un vector ai, ce urmeaz s prseasc baza. n sfrit, determinnd pivotul, formulele (1.21) i (1.22) dau posibilitatea completrii tabelului corespunztor noii soluii mbuntite. Aplicarea acestor formule se poate face prin urmtoarele operaii succesive:

se completeaz coloana B cu vectorii ce formeaz noua baz;23

se mparte linia pivotului la pivot; se completeaz coloanele corespunztoare vectorilor din noua baz, acetia devenind vectori unitari;

se calculeaz celelalte elemente, aplicnd regula dreptunghiului.S ilustrm funcionalitate algoritmului pe un exemplu numeric.

Exemplul 4.2 Fie modelul de (P.L.):

[max] z = 5x1+7x2+2x3+2x4 x1+3x2 - x3+0x4=40

-x2+2x3+ x4=10

xj 0, j=1,2,3,4

Completm urmtorul tabel:

CBBXB5 7 2 2

a1 a2 a3 a4

5

2a1a440

101 3 -1 0

0 -1 2 1

/(j2200 -6 3 0

5

2a1a245

51 5/2 0 1/2

0 -1/2 1 1/2

/(j2350 -9/2 0 -3/2

24

Deoarece pe linia diferenelor (j, exist o diferen strict pozitiv (c3-f3=3), deducem c soluia realizabil x nu verific criteriul de optim. n tabel s-a fcut efectiv trecerea la o soluie realizabil de baz mai bun, prin efectuarea urmtoarelor operaii:

dintre rapoartele 40/-1 i 10/2 se consider numai cel corespunztor celei de-a doua linii; deoarece prima component a vectorului a3 este negativ fapt ilustrat i n figura1.3; urmeaz c vectorul a4 este cel care trebuie s ias din baz;

XB a3

40 -1 10 2 5

Fig 1.3 Calculul rapoartelor xm/(mj

pivotul, ncercuit n tabel, s-a determinat la intersecia coloanei a3 cu linia a4;

s-au nscris, n coloana B, vectorii ce formeaz noua baz, respectiv a1 i a3;25 s-a mprit linia a doua prin 2 (pivotul), rezultatele trecndu-se pe linia a doua din iteraia a doua; celelalte elemente de pe linia nti a iteraiei a doua s-au calculat cu ajutorul regulii dreptunghiului;

s-a completat coloana CB cu coeficienii c1 i c3, corespunztori vectorilor din noua baz.

Componentele bazice ale noii soluii se citesc pe coloana XB, ele fiind urmtoarele: x1=45, x2=0, x3=5, x4=0. Prin urmare, noua soluie are forma urmtoare:

X(=(45,0,5,0), iar Zmax=235

Pentru testarea optimalitii acestei noi soluii s-au calculat n tabel diferenele cj-fj. Deoarece nu mai exist nici o diferen strict pozitiv, deducem c soluia X este optim i aplicarea algoritmului simplex a luat sfrit.

S ne ocupm acum de operaiile premergtoare aplicrii operaiilor cerute de algoritmul simplex. Pentru a putea ncepe aplicarea algoritmului simplex, n scopul gsirii soluiei optime pentru un model de (P.L.), trebuie s fie ndeplinite dou condiii i anume:

a) modelul s fie sub forma standard de lucru (cu restricii de tip egaliti);

26

b) s dispunem de o soluie realizabil de baz, pe care o vom numi soluie iniial.

n privina condiiei (a), precizm c orice restricie scris sub form de inegalitate se poate pune sub forma unei egaliti dac se adopt o variabil suplimentar, numit variabil de compensare. Pentru ca aceast variabil de compensare s se supun i ea condiiilor de nenegativitate, ea se adaug cu coeficientul +1 dac inegalitatea are sensul ( i cu coeficientul 1 dac inegalitatea are sensul ( .

n ceea ce privete condiia (b), determinarea unei soluii realizabile de baz iniiale constituie uneori o parte important a rezolvrii modelului, pentru aceasta existnd metode speciale.

n continuare se prezint nc trei exemple numerice rezolvate.

Exemplul 4.3 Fie modelul de (P.L.):

[max] f = 2x1+3x2+x3+4x4

x1 + x3+2x4=8

x2+2x3 + x4=10

xj ( 0, j=1,2,3,427

Completm urmtorul tabel:

CBBXB2 3 4 1

A1 a2 a3 a4

2

3a1a28

101 0 1 2

0 1 2 1

/(j460 0 -7 -3

S explicm, pe scurt, cum s-au obinut rezultatele pe linia (j: 28+310=46

c1-f1=2-(21+30)=2-2=0

c2-f2=3-(20+31)=3-3=0

c3-f3=1-(21+32)=1-8=-7 etc.

Cum toate diferenele sunt negative sau zero, avem soluie optim finit (8,10,0,0), f max=46.

Exemplul 4.4 Fie modelul de (P.L.):

[max]f=2x1+x2+3x3+5x4+9x5x1+2x3+x4+3x5=15

x2+x3+2x4+x5=12

xj0, j=1,2,3,4,5

Construind tabelul simplex vom gsi pornind de la soluia de baz x1=15, x2=12, x3=x4=x5=0

28CBBXB2 1 3 5 9

a1 a2 a3 a4 a5

2

1a1a215

121 0 2 1 3

0 1 1 2 1

/(j420 0 -2 1 2

9

1A5A25

71/3 0 2/3 1/3 1

-1/3 1 1/3 5/3 0

/(j52-2/3 0 -10/3 1/3 0

9

5A5A418/5

21/52/5 -1/5 3/5 0 1

-1/5 3/5 1/5 1 0

/(j267/5-3/5 -1/5 -17/5 0 0

Algoritmul simplex a luat sfrit, soluia optim fiind xopt=(0,0,0,21/5,18/5), creia i corespunde f max=267/5.

Exemplul 4.5 Fie modelul de (P.L.):

[min]f = 2x1+x2+3x3+5x4-x5 2x1+x2+ x3 = 4

x1+ 2x3+ x5 = 7

3x1+ 2x3+x4 = 10

xj0, j=1,2,3,4,5

29

CBBXB2 1 3 5 -1

a1 a2 a3 a4 a5

1

-1

5A2a5a44

7

102 1 1 0 0

1 0 2 0 1

3 0 2 1 0

/(j47+14 0 6 0 0

2

-1

5a1a5a42

5

41 1/2 0 0

0 -1/2 3/2 0 1

0 -3/2 1/2 1 0

/(j190 -7 -1 0 0

Dup cum rezult din tabel, pe linia (j s-au fcut diferenele fj-cj, deoarece este o problem de minim. Soluia optim este xopt=(2,0,0,4,5), cruia i corespunde fmin=19.

Prezentm, n continuare, cteva observaii legate de aplicarea algoritmului simplex .

Observaia 4.1. Criteriul de ieire din baz, aa cum am precizat mai nainte, cere ca vectorul care intr n baz s conin cel puin o component pozitiv. Dac din criteriul de optim rezult c soluia nu este optim i vectorul care trebuie s intre n baz nu are nici o component pozitiv, atunci problema nu admite optim finit (optimul este infinit).

Observaia 4.2. n cazul cnd n tabelul simplex optim avem diferene nule i n dreptul altor vectori care nu fac parte din baza 30

optim, problema admite soluie optim multipl. Pentru a gsi i alte soluii optime se continu algoritmul simplex introducnd n baz unul din vectorii din afara bazei cruia i aparine o diferen nul.

Precizm, naintea exemplului 4.3,c determinarea unei soluii realizabile de baz iniiale necesit - n anumite cazuri - aplicarea unor metode speciale. n acest sens prezentm n continuare una dintre metode i anume metoda coeficienilor de penalizare.

Dup ce modelul a fost adus la forma standard, avem grij ca toi termenii liberi s fie nenegativi, n caz contrar schimbm semnele unora dintre resticii. Apoi, scriind matricea A a sistemului de restricii, observm ce vectori unitari se gsesc printre coloanele ei. n cazul n care matricea A conine toi cei m vectori unitari, acetia formeaz baza iniial cutat. Dac matricea A nu conine toi cei m vectori unitari (eventual nici unul), introducem unele variabile suplimentare numite variabile artificiale, totdeauna cu coeficieni egali cu +1, n anumite restricii convenabil alese, pn cnd matricea sistemului de restricii va conine m vectori-coloan unitari.

31

Deoarece variabilele artificiale stric vechiul echilibru al restriciilor (care erau egaliti), vom obine astfel un model numit model lrgit ,ale crui soluii nu corespund totdeauna cu soluiile modelului ce trebuie rezolvat. Evident, pentru ca o soluie a modelului lrgit s ofere i o soluie a modelului iniial, trebuie ca n ea toate variabilele artificiale s fie nule. Astfel, vom cuta s form anularea variabilelor artificiale, prin introducerea acestora n funcia de eficien cu coeficieni egali cu +M, n cazul unui model de minim, respectiv cu coeficieni egali cu M, n cazul unui model de maxim, M, coeficientul de penalizare , fiind considerat ca un numr arbitrar foarte mare. Rolul acestor termeni suplimentari din funcia de eficien este acela de a nu lsa aceast funcie s-i ating valoarea minim, respectiv valoarea maxim, pn cnd nu se anuleaz toate variabilele artificiale. Este limpede c dac, prin aplicarea algoritmului, s-a ajuns la o soluie optim a modelului lrgit, fr ca toate variabilele artificiale s aib valori nule n aceast soluie, modelul iniial este imposibil.

De obicei, n calcule, nu particularizm valoarea lui M, dar pe parcursul aplicrii algoritmului simplex l privim ca pe un 32

numr suficient de mare (n raport cu celelalte valori numerice din model).

Deoarece valorile variabilelor artificiale trebuie s fie nule, orice vector artificial care a ieit din baz nu va mai fi cercetat pentru o eventual introducere n baz, deci nu se va mai calcula diferena (j, corespunztoare lui, putnd renuna la coloana acelui vector din tabel.

S redm cele de mai sus printr-un exemplu numeric.

Exemplul 4.6 Se d urmtorul model de (P.L.):[min]f = x1+2x2+2x3+x4 x1+x2+2x3+ x4=10

2x1+ x2+2x3+2x4=12

x1+3x2+2x3+2x4=16

xj0, j=1,2,3,4

Modelul lrgit n cazul de fa va fi :[min]f = x1+2x2+2x3+x4+MU1+MU2+MU3 x1+ x2+2x3+ x4+U1=10

2x1+ x2+2x3+2x4+U2=12

x1+3x2+2x3+2x4+U3=16

xj0, j=1,2,3,4, Uk 0, k=1,2,3

33iar tabloul simplex corespunztor este:CBBXB1 2 2 1M M M

a1 a2 a3 a4U1 U2 U3

M

M

MU1U2U310

12

161 1 2 1

2 1 2 2

1 3 2 21 0 0

0 1 0

0 0 1

/(j38M4M-1 5M-2 6M-2 5M-10 0 0

2

M

Ma3U1U25

2

61/2 1/2 1 1/2

1 0 0 1

0 2 0 11/2 0 0

1 0 0 1

/(j8M+10M 2M-1 0 2M 0 0

2

1

Ma3a4U24

2

40 1/2 1 0

1 0 0 1

-1 2 0 0 0

0

1

/(j4M+10-M 2M-1 0 0 0

2

1

2a3

a4

a23

2

21/4 0 1 0

1 0 0 1

-1/2 1 0 0

/(j12-1/2 0 0 0

Deci xopt=(0,2,3,2) i fmin=12

34

PROBLEME DE PROGRAMARE LINIAR PROPUSE SPRE REZOLVARE

1. [max]f =2x1+x2+x3+3x4+2x5+9x6 x1+x4+2x5+ x6 =10

x2+x4+ x5+2x6 =20

x3+x4+3x5+3x6=30

xj0, j=1,2,3,4,5,6

R: xopt=(0,0,0,0,0,10); fmax=90

2. [max]f=2x1+x2+3x3+5x4+9x5 x1+2x3+ x4+3x5=15

x2+ x3+2x4+ x5 =12

xj0, j=1,2,3,4,5

R: xopt=(0,0,0,21/5,18/5); fmax=267/5

3. [max]f=2x1+x2+6x3+5x4+7x5+11x6+3x7 x1+ x3+ x4+ x5+3x6+2x7 =18

x2+ x3+2x4+3x5+2x6+ x7 =24

xj0, j=1,2,3,4,5,6,7

R: xopt=(0,6,18,0,0,0,0); fmax=114

354. [max]f=x1+x2+3x3+5x4+5x5+7x6 x1+ x3+2x4+ x5+2x6=14

x2+ x3+ x4+2x5+3x6=18

xj0, j=1,2,3,4,5,6

R: xopt=(0,0,0,10/3,22/3,0); fmax=160/3

5. [max]f=-x1+2x2+x3+3x4-x5-2x6 x1+x2+2x3+3x5=15

2x2+x3+x4+5x5=20

x2+2x3+x5+x6 =10

xj0, j=1,2,3,4,5,6

R: xopt=(5,0,5,15,0,0); fmax=456. [max]f=x1+2x2+3x3+x4

1

x1- x3+ x4=1

2

x2+x3 - x4 =1

xj0, j=1,2,3,4

R: optim infinit

36

7. [max]f=2x1+3x2+2x3 x1+ x2+2x3 4

2x1+ x2+ x3 2

x1-3x2+2x3 5

xj0, j=1,2,3

R: xopt=(0,2,0); fmax=6

8. [min]f=5x1+2x2+x3+x4+3x5 3x1+ x3+2x4 =20

x1+ x2+3x4 =10

5x1+ x4+ x5 =1

xj0, j=1,2,3,4,5 R: xopt=(0,7,18,10); fmin=33

9. [max]f=3x1+4x2+2x3+x4 2x1+2x3+x410

3x1+2x2+ x4 6

x1+2x2+x3+4x4 12

xj0, j=1,2,3,4

R: xopt=(0,3,5,0); fmax=22

3710.[min]f=x1+2x2+2x3+x4 x1+2x2+2x3+x4 =10

2x1+x2+2x3+2x4 =12

x1+2x2+2x3+2x4=44/3

xj0, j=1,2,3,4

R: xopt=(0,8/3,0,14/3); fmin=10

11.[min]f=x1+2x2+2x3+x4 x1+2x2+2x3+x4 =10

2x1+x2+2x3+2x4=12

x1+2x2+2x3+2x4=16

xj0, j=1,2,3,4

R: Problema nu are soluie, deoarece conine i o variabil artificial nenul.

12.[max]f=3x1+2x2+x3+5x4+2x5 x1+2x2+x3+3x4+x5=10

2x1+x2+x3+x4+3x5 =4

xj0, j=1,2,3,4,5 R: xopt=(2/5,0,0,16/5,0); fmax=86/5

38

PROBLEME DE PROGRAMARE LINIAR CU APLICAII N PROCESUL DE PRODUCIE PROPUSE SPRE REZOLVARE

1. n cadrul unei secii de producie trebuie executate dou produse A i B, fiecare cu prelucrri pe trei utilaje (U1,U2,U3). Timpul unitar pe produs i pe main, timpul total disponibil pe fiecare grup de utilaj i beneficiul pe unitatea de produs sunt prezentate n tabelul de mai jos.

Denumire

utilajTimpul unitar de main pe produs (min)Timpul total disponibil pe grup de utilaj (min)

AB

U19109000

U21268400

U31959500

Beneficiu

(u.m)20

25

Se cere s se determine cantitile executate din fiecare produs, astfel nct s se obin un beneficiu maxim pe baza datelor din tabel.

39

Indicaie. Modelul matematic al problemei este:

[max]f=20x1+25x29x1+10x2 9000

12x1+6x2 8400

19x1+5x2 9500

xj0, j=1,2

Se transform inegalitile n egaliti prin introducerea variabilelor de compensare i se pornete algoritmul simplex.

2. Un atelier de prelucrri mecanice este specializat n prelucrarea de seturi de piese ce urmeaz a fi prelucrate lunar n condiiile realizrii unui beneficiu total lunar maxim.

Datele privind normele de timp tij (min/set piese), fondurile de timp disponibile Tdi (min/lun) i beneficiul planificat bj (u.m/set piese) sunt prezentate n tabelul de mai jos: Tipuri de

produse

Gr. de j

utilajeitijTdi

AB

11199900

27128400

36169600

bj90100

403. Se cere un program optim de fabricaie pentru trei utilaje principale din cadrul unui atelier de sudur care realizeaz seturi de piese sudate necesare fabricrii la a trei tipodimensiuni de subansamble n condiiile realizrii unui beneficiu maxim la nivel

de atelier i a ncrcrii maxime a celor trei utilaje analizate. Datele referitoare la normele de timp (tig), fondurile de timp disponibile (Fdi) i beneficiul planificat (bg) sunt prezentate n tabelul de mai jos:

Tipuri de

subans.g Tipuri de

utilajeitigFdi

ABC

1

2

31

1

21

3

14

2

2200

200

200

bg203050

4. Se cere modelul matematic care s conduc la minimizarea resturilor materiale. Se dau bare de 7 metrii din care trebuie debitate urmtoarele repere: 20 buc. repere a 5m;

21 buc. repere a 3m; 22 buc. repere a 2m.41

Datele sunt sistematizate n tabelul de mai jos:

Tipul

barelorNr. procedeelor de debitareCantitatea necesar de piese (buc)

1234

5m100020

3m021021

2m102322

Rest0101

5. ntr-o secie de produse format din trei ateliere se realizeaz patru tipuri de aparate. Se cere s se determine cantitatea optim pe lun din fiecare tip de aparat n condiiile realizrii unui beneficiu maxim la nivel de secie i ncrcrii maxime a capacitii de producie disponibile.

Se cunosc urmtoarele date: normele de timp (tij), fondurile de timp disponibile (Fdi) i beneficiul planificat (bj). Datele sunt prezentate n tabelul de mai jos: Tipuri de aparate

Ateliere (j) (i)tij(ore/aparat)Fdi(ore/lun)

ABCD

1

2

315

25

10

35

20

15

159

202700

3100

1250

bj12015016050

426. n cadrul unui atelier de prelucrri mecanice care are patru grupe de utilaje se realizeaz tipurile de piese: a,b,c,d. Normele de timp (tig) pentru fiecare tip de pies i fondurile de timp disponibile ale grupelor de utilaje (Fdi) sunt prezentate n tabelul de mai jos. Se cere s se determine numrul de piese/lun din fiecare tip pentru a asigura beneficiul maxim/lun, cunoscndu-se beneficiul unitar (bg).

Tipuri de piese

(g)

Grupa de utilaje (i)tig(ore/pies)tdi(ore/spt.)

aBcd

1

2

3

40,5

2

4

21

0

4

44

2

1

00

6

1

1130

180

240

200

bg(um/lun)5611

7. n vederea realizrii unui dispozitiv de sudat trebuie debitate bare de oel unidimensionale cu lungimea de 8m. Din debitare rezult repere i resturi. Se cere modelul matematic care s conduc la minimizarea costurilor. Datele sunt prezentate n tabelul urmtor:

43

Lungimea

pieselor(m)Posibiliti de debitareCantitatea necesar

123456

4

3

22

0

00

2

10

0

41

1

01

0

20

1

230

32

31

Resturi000101

8. Un atelier dispune de patru grupe de maini unelte A,B,C,D, pe care se pot prelucra patru produse diferite. S se determine care produse trebuie s se execute i n ce condiii pentru a se asigura ncrcarea maxim a utilajelor. Fondul de timp disponibil pe fiecare grup de utilaj, ca i normele de timp pe unitatea de produs i pe utilaj, sunt prezentate n tabelul de mai jos:

Norma de timp

unitar pe

utilaje

ProdusulA

B

C

D

P12415

P24121

P33241

P46862

Fondul de timp disponibil400380410390

441.4 MODELE LINIARE DE TIP TRANSPORT. FOLOSIREA PROGRAMRII LINIARE N OPTIMIZAREA PLANULUI DE TRANSPORT

FORMULAREA PROBLEMEI

n activitatea de conducere, organizare si planificare se ntlnesc o serie de probleme privind repartizarea unor cantiti de la unitile furnizoare la cele consumatoare. Astfel, pentru elaborarea planului de transport intern la o ntreprindere se pune problema de a repartiza anumite cantiti privind un anumit material de la depozite (furnizori) la uniti de producie secii, ateliere (consumatori). Aceast repartizare trebuie fcut n aa fel nct s se asigure costuri minime de transport.

Modelul general al unei probleme de transport, atunci cnd existentul la furnizori este egal cu necesarul la beneficiari (problem de tip echilibrat), este format din urmtoarele relaii:

m n

[min]f = ( ( cij xij (1.25)

i=1 j=145 n

( xij = ai , i=1,2,,m (1.26)

j=1

m

( xij = bj , j=1,2,,n (1.27)

i=1 m n

( ai = ( bj (1.28)

i=1 j=1

xij 0 (1.29)

n care: ai cantitile existente la cei m furnizori

bj necesarul la cei n consumatori

xij cantitatea de material transportat de la furnizorul i la beneficiarul j

cij costul unitar al materialului transportat de la furnizorul i la beneficiarul j

Rezolvarea acestei probleme de transport nseamn a gsi din mulimea sistemului de restricii (1.26), (1.27), n condiiile relaiei (1.28), acea soluie care minimizeaz relaia (1.25).

O problem de transport se rezolv n dou etape. n cadrul primei etape se determin o soluie iniial a problemei, iar n cazul celei de-a doua etape se efectueaz optimizarea acesteia.

46Pentru determinarea unei soluii de baz se pot folosii diferite procedee, cum sunt: procedeul colului de Nord-Vest (al diagonalei principale), procedeul diferenelor maxime, procedeul costurilor minime, procedeul elementului minim pe linie, procedeul elementului minim pe coloan.

Pentru optimizarea soluiei de baz, n cadrul etapei a doua se pot folosi, de asemenea, mai multe metode, cum sunt: metoda distributiv, metoda potenialelor, metoda stepping-stone (treapt-scar).

Dintre procedeele i metodele enumerate vom utiliza n cadrul primei etape procedeul colului de Nord-Vest, iar n cea de-a doua etap metoda distributiv.

REZOLVAREA UNEI PROBLEME DE TIP TRANSPORT ECHILIBRAT

S considerm c o ntreprindere trebuie s aprovizioneze o anumit materie prim, pe care o are n trei depozite (A,B i C), patru fabrici pe care le subordoneaz, conform tabelului de mai jos:

47

ntreprinderi

Depozite1234Cantitatea

disponibil

A54211300

B25451300

C3324700

Cantitatea necesar100012008003003300

Depozitele A i B au un disponibil din materia prim dat de cte 1300 tone, iar depozitul C un disponibil de 700 tone. Corespunztor prevederilor coninute n planul de aprovizionare tehnico-material, prima fabric are nevoie de o cantitate de 1000 tone, fabrica a doua de 1200 tone, fabrica a treia de 800, tone iar fabrica a patra de 300 tone. Distanele de la depozite la fabrici sunt prezentate n acelai tabel.

Etapa IFolosirea procedeului colului de Nord-Vest sau a diagonalei principale se prezint n urmtorul tabel:

48

DepozitentreprinderiCantitatea existent n depozite

1234

A54211300

1000300

B

25451300

900400

C

2324700

400300

Cantitatea

nec. pe ntrep.100012008003003300

n colurile din dreapta sunt trecute distanele. Potrivit procedeului colului Nord-Vest se pornete de la csua A-1 situat n colul Nord-Vest al matricei la care a fost repartizat cantitatea maxim de materie prim ce poate fi luat de la depozitul A pentru a acoperi necesarul acesteia. Dup ce se satisface cantitatea necesar la A-1 (1000 tone), cele 300 tone ce mai rmn nc la depozitul A se repartizeaz la csua A-2, epuizndu-se prin aceasta cantitatea existent n acest depozit.

49

La fabrica 2, unde sunt necesare 1200 tone, s-au repartizat 300 tone la depozitul A n csua A-2 i 900 tone n csua B-2 de la depozitul B, unde mai rmn disponibile 400 tone.

La fabrica 3, unde sunt necesare 800 tone, s-au repartizat 400 tone de la depozitul B n csua B-3 i 400 tone n csua C-3 de la depozitul C, unde mai rmn disponibile 300 tone.

La fabrica 4, unde sunt necesare 300 tone, se repartizeaz cele 300 tone disponibile existente n depozitul C n csua C-4.

Din analiza tabelului se constat c se pornete de la colul Nord-Vest, acoperindu-se cantitile necesare beneficiarilor, n mod complet, n ordinea lor, trecnd de la un furnizor la altul numai dup ce s-a terminat de repartizat cantitatea existent la un furnizor pe diferii beneficiari, n mod complet, ajungndu-se n final la colul Sud-Est, mergndu-se deci pe direcia diagonalei principale. De asemenea, se constat repartizarea ntregii cantiti existente la furnizori (pe linie) i satisfacerea cantitilor necesare la diferii consumatori (pe coloane).

NOT Pentru ca problema s poat fi rezolvat prin folosirea algoritmului problemei de transport, trebuie ca numrul csuelor ocupate s fie egal cu cel dat de expresia :

50

m + n 1 (1.30)

n care : m numrul de furnizori

n numrul de consumatori. n exemplul de fa, m + n 1 = 3 + 4 1 = 6. Din analiza soluiei de baz rezult c exist ase csue ocupate cu cantiti, ceea ce nseamn c problema poate fi rezolvat. Dac numrul csuelor neocupate era mai mic dect cel din relaia (1.30), atunci era necesar s se completeze csue libere cu zero pn la verificare relaiei dup o anumit regul.

Dup obinerea soluiei de baz se calculeaz volumul total de transport ce va trebui efectuat, fcnd suma tonelor/kilometri pentru toate csuele matricei unde au fost repartizate cantiti.

Vol. total=10005+3004+9005+4004+4002+3004=14300 tone/kilometri

Etapa a II-a - mbuntirea succesiv a soluiei de baz pn la obinerea variantei optime.

Pentru mbuntirea soluiei de baz se folosete metoda distributiv, potrivit creia se efectueaz transferuri ciclice ale unor cantiti repartizate dup unele contururi poligonale cu unghiuri drepte, astfel nct sumele cantitilor transferate pe linii 51

i coloane s nu modifice totalul disponibil (pe fiecare linie) pe furnizor i totalul necesar (pe coloane) la consumatori.

Pentru c exist attea posibiliti de mbuntire a soluiei de baz cte csue libere exist n matricea planului de transport, se va determina n prealabil csua cu cea mai mare perspectiv de mbuntire, prin folosirea procedeului ntocmirii ciclurilor csuelor libere. n acest sens se vor construi contururi poligonale, astfel nct un col s se afle ntr-o csu liber a matricei planului de transport a soluiei analizate, iar restul colurilor n csue unde exist deja repartizate cantiti. La conturul poligonal astfel format se trece n colul liber semnul +, iar dup aceea, n mod alternativ, semnele i + la celelalte coluri.

Odat cu aceasta se vor trece n fiecare col distanele corespunztoare. Ca regul, n fiecare csu nu se poate forma dect un unghi drept.

Dup construirea conturilor poligonale dup regulile amintite se face suma algebric a distanelor din coluri, lundu-se pentru fiecare distan semnul colului unde se afl. Se va considera csua cu cea mai mare perspectiv de mbuntire 52

aceea prin care nsumarea algebric a distanelor va avea cea mai mare valoare negativ.

Pentru exemplificare, pornim de la datele prezentate n cel de-al doilea tabel. ntruct n cadrul acestui plan exist ase csue libere, se vor construi ase contururi poligonale dup regulile artate anterior, efectundu-se suma algebric a distanelor. Fiecare csu se va nota printr-un simbol format din iniiala furnizorului (depozitului), corespunztor liniei pe care se situeaz csua, i cifra corespunztoare consumatorului (fabricii) de la coloana pe care se afl aceasta. Spre exemplu, A-3 va simboliza csua de pe linia depozitului A i coloanei fabricii a treia.

Csua A-3 va fi un dreptunghi cu colul liber n A-3 i cu celelalte coluri n A-2,B-2,B-3. Suma algebric va fi:2-4+5-4=-1

4 2 +

+

5 4

Pentru csua A-4 se formeaz un contur poligonal cu vrfurile n csuele A-4, A-2, B-2, B-3, C-3, C-4. Suma algebric este: 1-4+5-4+2-4= -4

53

4 1 + + 5 4

+

2 4Csua B-1 are conturul poligonal n colurile csuelor B-1, A-1, A-2, B-2. Suma algebric este : 4-5+2-5= -4

5 4 +

+

2 5

Conturul poligonal al csuei B-4 are colurile n B-4, B-3, C-3, C-4. Suma algebric este: 5-4+2-4= -1

4 5 +

+

2 4

Pentru csua C-1 conturul poligonal are colurile n csuele C-1, A-1, A-2, B-2, B-3, C-3. Suma algebric este: 3-5+4-5+4-2= -1

54

4 4 + 5 4

+ +

3 2

Conturul poligonal al csuei C-2 are colurile n C-2, B-2, B-3, C-3. Suma algebric este: 3-5+4-2=0

5 4 +

+

3 2

Din analiza sumelor algebrice obinute pentru cele ase contururi poligonale rezult aceeai valoare negativ maxim pentru csuele A-4 i B-1. nseamn c acestea reprezint csuele cu cea mai mare perspectiv de mbuntire a planului de transport. ntruct ambele csue au aceeai valoare negativ maxim, se trece la mbuntirea soluiei de baz prin efectuarea unor transferuri ciclice dup conturul poligonal al csuei B-1. n acest scop se trec n coluri, n loc de distane, cantitile corespunztoare repartizate prin soluia de baz a planului de transport, care trebuie mbuntit.

55

Pentru transferul ciclic se procedeaz astfel :

se analizeaz mrimea cantitilor de la colurile cu semnul negativ al conturului poligonal, identificndu-se cantitatea cea mai mic;

se adaug cantitilor existente la colurile cu semnul plus cantitatea minim de la colurile cu semnul minus, sczndu-se aceast cantitate de la colurile cu semnul minus;

se elaboreaz un nou plan de transport, n care se trec noile cantiti obinute prin efectuarea transferului ciclic n csuele corespunztoare colurilor conturului poligonal, toate celelalte csue rmnnd neschimbate, ca n soluia de baz;

pe baza noului plan se calculeaz volumul de transport, care trebuie s fie mai mic dect n varianta anterioar.

n felul acesta s-a obinut o nou variant de plan de transport, care la rndul ei trebuie mbuntit. n acest scop se folosesc aceleai operaii efectuate pentru mbuntirea soluiei de baz. mbuntirea variantelor de plan de transport se efectueaz pn n momentul n care, fcnd suma algebric a distanelor de pe conturul poligonal, nu se mai obin valori negative.

56

Continund problema propus, rezult c B-1 este o csu cu perspectiv de mbuntire a variantei de plan de transport. Se prezint conturul poligonal al acesteia, trecnd n loc de distane cantitile corespunztoare csuelor unde se afl colurile conturului. Constatm c la colurile cu semnul negativ, cantitatea cea mai mic este 900.

1000 300 +

+

900

Aceast cantitate se adun la colurile cu semnul + i se scade la colurile cu semnul -. n acest fel se obine un transfer ciclic de cantiti, aa cum se arat n conturul poligonal, care se reprezint nc odat, ns cu noile cantiti repartizate la coluri.

100 1200 +

+

900 0

n funcie de noile cantiti se ntocmete un plan de transport n care se trec cantitile obinute, toate celelalte csue rmnnd neschimbate. Planul de transport obinut este prezentat n tabelul urmtor:

57

DepozitentreprinderiCantitatea

disponibil

1234

A54211300

1001200

B

25451300

9000400

C

3324700

400300

Cantitate

necesar100012008003003300

Volumul de transport n noua variant este urmtorul:

1005+12004+9002+05+4004+4002+3004=10700 tone/kilometri.

n continuare se caut o nou variant de plan de transport, mbuntit fa de cea existent. n acest scop se folosete procedeul ciclurilor csuelor libere i pe aceast baz se determin csua cu cea mai mare perspectiv de mbuntire. Csuele libere n actualul plan sunt: A-3, A-4, B-4, C-1 i C-2. Pentru acesta se vor obine urmtoarele contururi poligonale:

Pentru A-3 colurile sunt situate n csuele A-3, A-2, B-2, B-3. Suma algebric este: 2-4+5-4= -1

58

4 2 +

+

5 4Pentru A-4 colurile sunt situate n csuele A-4, A-2, B-2, B-3, C-3, C-4. Suma algebric este: 1-4+5-4+2-4= -4

4 1 +

+

5 4

+

2 4

Pentru B-4 colurile sunt situate n csuele B-4, B-3, C-3, C-4. Suma algebric este: 5-4+2-4= -1

4 5

+

+

2 4

Pentru C-1 colurile sunt situate n csuele C-1, B-1, B-3, C-3. Suma algebric este: 4-2+3-2=3

2 4 +

+

3 259

Pentru C-1 colurile sunt situate n csuele C-2, B-2, B-3, C-3. Suma algebric este: 3-5+4-2=0

5 4 +

+

3 2

Csua cu cea mai mare perspectiv de mbuntire este A-4, care are suma algebric cu valoarea negativ cea mai mare.

1200 +

+

0 400

+

400 300

Ca urmare reprezentm conturul lui A-4 trecnd cantitile din planul de transport ce urmeaz a fi mbuntit n coluri. Cantitatea cea mai mic la colurile cu semn negativ (300) se va aduna i scdea conform regulii cunoscute. n felul acesta se obine urmtoarea repartizare:

900 300 +

+

300 100

+

700 0

60

Cu noua repartizare a cantitilor se ntocmete varianta de plan de transport, ca n tabelul urmtor:DepozitentreprinderiCantitatea

disponibil

1234

A54211300

100900300

B

25451300

900300100

C

3324700

7000

Cantitate

Necesar100012008003003300

Volumul de transport n noua variant este urmtorul:

1005+9004+3001+9002+3005+1004+7002+04=9500

tone/km.

n noua variant volumul de transport s-a redus de la 10700 tone/km la 9500 tone/km. n continuare se trece la mbuntirea acestei variante, calculndu-se ciclul csuelor libere (A-3, B-4, C-1, C-2).

Pentru A-3 colurile sunt situate n csuele A-3, A-2, B-2, B-3. Suma algebric este: 2-4+5-4= -1

61

4 2 +

+

5 4

Pentru B-4 colurile sunt situate n csuele B-4, B-3, C-3, C-4. Suma algebric este: 5 4 + 2 4 = 4

4 5

+

+

2 4

Pentru C1 colurile sunt situate n csuele C1, B1, B3,C3.Suma algebric este: 4 2 + 3 2 = 3

2 4

+

+

3 2

Pentru C2 colurile sunt situate n csuele C2, B2, B3,C3.Suma algebric este :3 5 + 4 2 = 0

5 4

+

+

3 2

62

Avnd dou csue cu aceeai valoare negativ maxim, A-3 i B-4,se consider csua cu cea mai mare perspectiv de mbuntire A-3. Se reprezint conturul poligonal al csuei A-3 cu cantitile corespunztoare din planul de transport la coluri:

900

+

+

300 100

Cantitatea de 100 tone fiind cea mai mici din colurile cu semnul minus este transferat ciclic. n felul acesta se obine urmtoarea repartizare:

800 100

+

+

400 0

Cu noua repartizare a cantitilor se ntocmete varianta de plan de transport, ca n tabelul urmtor:

63

DepozitentreprinderiCantitate

disponibil

1234

A54211300

100800100300

B

25451300

9004000

C

2324700

7000

Cantitate

necesar100012008003003300

Volumul de transport n noua variant este urmtorul:

1005+8004+1002+3001+9002+4005+04+7002+04==9400 tone/Km

n continuare se caut o nou variant de plan de transport, calculndu-se ciclul csuelor libere (B-4, C-1, C-2).

Pentru B-4, colurile sunt situate n csuele B-2, A-4, A3, B-3. Suma algebric este: 5 1 + 2 4 = 2

2 1

+

+

4 5

64

Pentru C-1, colurile sunt situate n csuele C-1, B-1, B-3, C-3. Suma algebric este: 3 2 + 4 2 = 0

2 4

+

+

3 2

Pentru C-2, colurile sunt situate n csuele C-2, B-2, B-3, C-3. Suma algebric este: 3 5 + 4 2 = 0

5 4

+

+

3 2

Analiznd ciclul csuelor libere, se constat c nu mai exist sume algebrice cu semnul minus. Aceasta nseamn c planul de transport elaborat nu mai poate fi mbuntit deci el reprezint varianta optim. Constatm c fa de volumul de transport prevzut n soluia de baz (14300 tone/Km), prin mbuntirile aduse s-a ajuns la varianta optim (9400tone/Km). Problema de transport rezolvat face parte din categoria problemelor de tip echilibrat, n care volumul total disponibil la furnizori este egal cu volumul necesar la diferii consumatori.

65

n practic se ntlnesc situaii n care soluia de plan de transport conine mai puin de m+n1locuri ocupate. n acest caz soluia obinut este degenerat. Pentru a elimina degenerarea i a face posibil calculul se pune zero ntr-o csu liber, considernd-o ca fiind ocupat, cu condiia ca n conturul poligonal ce se formeaz pentru efectuarea transferului csua respectiv s fie ntr-un vrf par.

De asemenea, sunt cazuri n care volumul disponibil total al furnizorului depete volumul necesarului total al consumatorilor. n aceast situaie se introduce o coloan suplimentar corespunztoare unui consumator fictiv, n care costurile unitare sunt egale cu zero, necesarul acestei coloane fiind egal cu diferena dintre cantitatea disponibil i necesarul real la consumatori. Pentru rezolvare, folosim metoda prezentat anterior, n coloana consumatorului fictiv evideniindu-se ns cantitile care rmn n stoc la furnizor.

n cazul cnd volumul necesarului total depete volumul disponibilului total, soluionarea se face n dou variante: dac exist sau nu prioriti n repartizarea cantitilor repartizate. Dac exist prioriti, se satisfac mai nti consumatorii cu prioriti, folosindu-se metoda cunoscut de rezolvare. 66

Dac nu exist prioriti, se introduce n problem un furnizor fictiv care urmeaz a expedia o cantitate egal cu diferena dintre volumul total necesar la consumatori i volumul real disponibil la furnizori, ajungndu-se astfel la cazul unei probleme de transport echilibrate ce se rezolv prin metode obinuite.

PROBLEME DE TIP TRANSPORT PROPUSE SPRE REZOLVARE

1. Considerm problema de transport dat de urmtorul tabel:

Furnizori

BeneficiariDisponibil

( t )

123

F12137

F25318

F32435

Necesar ( t )67720

Disponibilul furnizorilor, necesarul beneficiarilor i costurile unitare de transport (n lei) sunt prezentate n tabel. S se ntocmeasc planul optim de transport cu cheltuieli minime.

67

2. Se consider problema de transport pentru care datele sunt concentrate n tabelul de mai jos. Se solicit realizarea acelui plan de transport care s fie optim avnd drept criteriu de optimizare minimizarea cheltuielilor de transport (buc. Km).

NOT: Coeficienii aij din tabel semnific distanele de la depozitul i la ntreprinderea j, n Km.

DepozitentreprinderiDisponibil

(buc.)

1234

D1835210

D2416715

D3194325

Necesar (buc.)510201550

3. Fie problema de transport dat n urmtorul tabel:

FurnizoriBeneficiariDisponibil

( t )

1234

F1322470

F2123410

F3322120

Necesar ( t )50251510100

NOT: Coeficienii aij reprezint distanele de transport (Km).

68

4. n mod asemntor problemei nr. 3, considerm urmtoarea problem:

Beneficiari, j

Depozite, iB1B2B3Disponibil

( t )

D12137

D25318

D32435

Necesar ( t )67720

Coeficienii aij au aceeai semnificaie ca n problema nr. 3.

S se ntocmeasc planul optim de transport.69CAP.2OPTIMIZAREA DECIZIILOR PRIN METODE MATEMATICE

2.1. PROBLEME DE DECIZIE N CONDIII DE CERTITUDINE

PROBLEME REZOLVATE

1. Pentru dotarea forelor armate aeriene cu tehnic de lupt corespunztoare, se urmrete alegerea unui tip de avion din patru tipuri disponibile. Cele patru tipuri sunt comparate n funcie de urmtoarele criterii:

C1 - vitez maxim

C2 - plafon de zbor

C3 - ncrctura de rzboi

C4 armament

Cele patru tipuri de avioane avute n vedere sunt avioane din clasa vntoare/atac.1____________________________________________________

1.Datele au fost preluate din revista Flight International, 13 19 July, 1994/Combat Aircraft Directory.70

- Mirage 2000 produs n Frana de uzinele Dessault, avnd viteza maxim 2,2 mach, plafonul de zbor 16460 m, ncrctura de rzboi 6300 Kg i armamentul 230 mm, 4AAM,9;

- F 16C Fighting Falcon produs n SUA la Lockheed, avnd viteza maxim 2 mach, plafonul de zbor 18000 m, ncrctura de rzboi 5413 Kg i armamentul 120 mm, 2/4/6AAM,6;

- F 18C Hornet produs n SUA la McDonnell Douglas, avnd viteza maxim 1,8 mach, plafonul de zbor 15240 m, ncrctura de rzboi 8165 Kg i armamentul 120 mm, 4AAM,7;

- Mig 23 Flogger G produs n Rusia de Mikoyan, avnd viteza maxim 2,4 mach, plafonul de zbor 18000 m, ncrctura de rzboi 2000 Kg i armamentul 123 mm, 6AAM,8.

Consecinele fiecrei variante n raport cu criteriile decizionale sunt date n urmtorul tabel:

Criterii

VarianteC1C2C3C4

V12,21646063009

V221800054136

V31,81524081657

V42,41800020008

71Considernd c cele patru criterii sunt la fel de importante, s se rezolve problema prin metoda momentelor (Deutch Martin).

Rezolvare:

Pasul 1 Se normalizeaz matricea consecinelor.

Trebuie remarcat faptul c aceast metod, ca i altele, presupun mai nti o omogenizare a criteriilor prin metoda normalizrii. Notm cu matricea consecinelor normalizate. Un procedeu de normalizare prin transformare liniar utilizeaz urmtoarele formule:

- pentru criteriul de maxim

- pentru criteriul de minim

Revenind la problem i innd cont c toate criteriile sunt de maxim, formula dup care vor fi calculate consecinele normalizate este:72

Se obine urmtoarea matrice a consecinelor normalizate:

CjViC1C2C3C4

V10,660,440,701

V20,3310,550

V30010,33

V41100,66

Spre exemplificare, s calculm

n mod similar se calculeaz i ceilali rij.

Pasul 2 Pentru fiecare linie se calculeaz momentul linie cu formula:

73

Pasul 3 Se ordoneaz liniile matricei consecinelor normalizate n ordine cresctoare dup valorile momentelor linie, astfel:

CjViC1C2C3C4

V20,3310,550

V41100,66

V10,660,440,701

V30010,33

Pasul 4 - Pentru fiecare coloan a noii matrici se calculeaz momentul coloan

74

Pasul 5 - Se ordoneaz coloanele matricei n ordine cresctoare a valorilor momentelor coloan. Noua matrice a consecinelor normalizate este:

CjViC2C1C4C3

V210,3300,55

V4110,660

V10,440,6610,70

V3000,331

Pasul 6 - Se reia algoritmul de la pasul 2n cadrul unei noi iteraii.

75Iteraia a doua

Pasul 2 - Calculm momentele line:

Pasul 3 - Ordonm liniile matricei consecinelor normalizate:

CjViC2C1C4C3

V4110,660

V210,3300,55

V10,440,6610,70

V3000,331

Pasul 4 - Se determin valorile momentelor coloan:76

Pasul 5 - Se ordoneaz coloanele matricei n ordine cresctoare a valorilor momentelor coloan:

CjViC2C1C4C3

V4110,660

V210,3300,55

V10,440,6610,70

V3000,331

Se observ c ultimul tabel este identic cu cel anterior lui, deci nu mai este posibil o nou ordonare a liniilor i/sau coloanelor matricei. Aceast ultim ordonare a liniilor reprezint cea mai bun ierarhie a variantelor decizionale.

V4 Mig 23 Flogger G,

V2 F-16 Fighting Falcon,77

V1 Mirage 2000,

V3 F-18C Hornet.

2. n vederea realizrii unui obiectiv industrial, un agent economic trebuie s aleag o variant din cele trei posibile. Pentru fiecare variant se cunosc valoarea investiiei (mil.u.m.), precum i durata de realizare a investiiei (luni).

Valoarea investiieiDurata de realizare

V110040

V211030

V310433

Coef. de importan11

Sa se determine ierarhia optim a variantelor decizionale prin metoda TOPSIS.

Rezolvare:

Pasul 1 - Se determin matricea consecinelor normalizate:

cu

78Se aplic metoda de normalizare vectorial, astfel:

i se obine matricea:

Crit.

Var.C1C2

V10,320,39

V20,350,29

V30,330,32

Coef. de importan kj0,60,4

Pasul 2 - Se construiete matricea normalizat ponderat:

, cu Crit.

Var.C1C2

V10,1920,156

V20,2100,116

V30,1980,126

Pasul 3 - Se determin soluia ideal i soluia ideal negativ , unde:79

dac Cj este criteriu de maxim

dac Cj este criteriu de minim

EMBED Equation.3 Soluia ideal negativ:

dac Cj este criteriu de maxim

dac Cj este criteriu de minim

EMBED Equation.3

Pasul 4 - Se calculeaz distana ntre soluii, utiliznd relaiile:

80

EMBED Equation.3

Pasul 5 - Se calculeaz apropierea relativ de soluia ideal:

3. S se determine varianta optim a asimilrii n fabricaie a unui nou tip de main de sudat electric prin presiune, pentru care s-au elaborat trei variante de proiecte, diferite din punct de vedere al unor soluii constructive. n vederea alegerii variantei optime s-au selectat trei parametrii: preul (p), durata de asimilare (d) i cheltuielile de exploatare (ce), care sunt prezentate n tabelul urmtor:81 Criterii

Variante Pre

(mil. lei)Durata de asimilare

(luni)Cheltuieli de

exploatare (mil. lei)

V1200650

V23001030

V3250840

Ierarhizarea criteriilor se face prin stabilirea urmtorilor coeficieni de importan:

- pre: k1=0,5,

- durata de asimilare: k2=0,3,

- cheltuieli de exploatare: k3=0,2

Rezolvare:Calculul utilitilor presupune urmtoarele relaii:

- pentru criteriul maxim:

- pentru criteriul de minim: Varianta optim poate fi determinat n situaiile:

- cnd coeficienii de importan (kj) sunt identici 82

- cnd coeficienii de importan sunt diferii

Revenind la problema dat, se constat c toi parametrii reprezint criterii de minim. S calculm utilitile variantelor:

83

EMBED Equation.3

PROBLEME PROPUSE SPRE REZOLVARE

1. Se consider trei variante posibile de proiectare a unui dispozitiv i trei criterii de apreciere a consecinelor tehnicoeconomice: costul dispozitivului - c1 (mil. lei), productivitatea dispozitivului (nr. pies/or) - c2, costul prelucrrii-c3(mil. lei/disp.). Datele sunt prezentate n tabelul urmtor:

Criterii

Variante C1

(mil. lei)C2

(nr. piese/or)C3(mil. lei)

V1752066

V2601670

V3801860

Se cere varianta optim, obiectivele urmrite fiind minimizarea costului dispozitivului, costului prelucrrii i maximizarea productivitii dispozitivului.

Coeficienii de importan au valorile: k1=0,3; k2=0,5; k3=0,2.

84

2. Se consider un numr de patru variante posibile de sudare prin presiune a unui reper. Criteriile de decizie sunt: c1 - costul de producie al reperului (mii lei/reper); c2 - durata de asimilare a procesului (ore); c3 cheltuieli cu energia (mii lei/reper).

Criterii

Variante C1

(mil. lei/reper)C2

(ore)C3(mil. lei/reper)

V11008020

V21207515

V3906030

Se cere varianta optim, obiectivele urmrite fiind minimizarea costului de producie, duratei de asimilare i cheltuielilor cu energia.

Coeficienii de importan au valorile: k1=0,4; k2=0,3; k3=0,3.

3. Pentru asimilarea n fabricaie a unui nou produs n cazul unei firme industriale, conducerea acesteia trebuie s opteze pentru una din cele trei variante de proces tehnologic (V1, V2, V3) puse la punct de specialiti, care prezint urmtoarele consecine:

85

Criterii

Variante Profitul

(u. m.)Calitatea (niveluri cantitative)Durata ciclului de producie (unit. timp)

V1100I35

V2101II30

V3105III40

Ierarhizarea criteriilor se face prin acordarea de ctre conducerea firmei a urmtorilor coeficieni de importan: profit k1=0,3; calitate k2=0,5; ciclul de producie k3=0,2.

NOT: Primele dou criterii sunt de maxim, ultimul fiind de minim.

4. O firm industrial i propune analiza posibilitilor de cretere a flexibilitii produciei i de amplificare a adaptabilitii acesteia la cerinele pieei interne i externe. n acest sens, conducerea firmei solicit patru variante de aciune n condiiile a cinci criterii mai importante (profit total, aport valutar brut, gradul de ncrcare a capacitilor, producia net i producia marf), considerate criterii de maxim.

86

Cj ViProfitul total obinut (mil. lei)Aport valutar brut

(mil. $)Grad de ncrcare a capacitilor (%)Producia net total

(mil. lei)Producia marf total

(mil. lei)

V11900072708260000133000

V21800062408658000122000

V31920048008063000144000

V42120057758456450126000

Valorile coeficienilor de importan ai celor cinci criterii adoptate au fost stabilii n raport de poziia fiecruia n sistemul indicatorilor economico-financiari n perioada actual, astfel:

- profit: k1=0,30;

- aport valutar: k2=0,25;

- ncrcarea capacitilor: k3=0,10;

- producia net: k4=0,20;

- producia marf: k5=0,15.

5. O societate comercial i propune analiza posibilitilor de cretere a produciei realizate n vederea lansrii pe pia a unui nou produs, n condiiile n care trebuie s opteze pentru cea mai bun variant de asimilare dintre posibiliti (V1, V2, V3), prezentate n tabelul de mai jos:87Cj

ViBenef. anual (mil.lei)Prod. fizic

(buc/an)Cons. de mat. (Kg/buc)Cons. de energ. (KWh/buc)Chelt. gen. ale firmei (mil.lei)Rand.

n

proc.

de

prod. (%)Fiab.

prod.

(103ore de

bun

func.)

V1520065000125,51500853,5

V2480070000961300803

V3550075000104,51600924

S se optimizeze decizia luat n condiii de certitudine, cnd confidenii de importan ai criteriilor folosite se prezint astfel:

- beneficiul anual: k1=0,15;

- producia fizic: k2=0,20;

- consum materiale: k3=0,10;

- consum energie: k4=0,10;

- cheltuieli generale: k5=0,10;

- randament: k6=0,2;

- fiabilitate: k7=0,15.

6. Pentru asimilarea n fabricaie a unui nou produs conducerea unei firme industriale trebuie s opteze pentru una din cele trei variante de proces tehnologic care, n funciile de criteriile stabilite, prezint urmtoarele consecine:

88Cj

ViCifra de afaceri (mil.lei)Prof. tot. ob. (mil.lei)Cons. de mat. (Kg/prod)Calit. (niv.

calitativ)Prod. muncii (buc/

spt.)

Durata ciclului de prod.

(unit.timp)Acop. segm. de pia (%)

V119001100125I256075

V2170085095II185080

V321001200105III207570

S se optimizeze decizia privind alegerea noului produs cnd coeficienii de importan ai criteriilor folosite se prezint astfel:

- cifra de afaceri: k1=0,10;

- profitul total: k2=0,15;

- consum materiale: k3=0,10;

- calitate: k4=0,15;

- productivitate: k5=0,10;

- durata ciclului de producie: k6=0,1;

- segmentul de pia: k7=0,3.

7. O familie dorete s nchirieze un apartament cu dou camere. Din mulimea ofertelor de nchiriere au fost selectate patru, familia urmnd s se decid pentru una din ele n funcie de criteriile: distana fa de locul de munc, etajul la care se afl apartamentul, chiria lunar. De asemenea, familia este interesat 89

ca apartamentul s fie mobilat i s aib telefon. Pentru primul i pentru al patrulea criteriu, aprecierea variantelor decizionale se face pe baz de note, pe o scar de la 0 la 4. n cea ce privete al doilea criteriu, familia va prefera un apartament situat la un etaj inferior. Consecinele sunt date n matricea de mai jos:

Cj

ViC1C2C3C4

V1315000002

V2094200002

V3484600004

V40,150,150,40,3

NOT: Problema se va rezolva prin metoda utilitii globale, primul i al patrulea criteriu fiind de maxi, iar al doilea i al treilea fiind de minim.

8. Un colectiv de conducere format din trei decideni (D1, D2, D3) trebuie s opteze pentru una din cele trei variante (V1,V2,V3) de cretere a volumului produciei n cadrul unei firme. Cunoscnd c fiecare decident a ierarhizat variantele prin normalizarea consecinelor, ca n tabelul de mai jos, s se rezolve problema prin metoda momentelor (Deutch-Martin).

90 Decident

Variante D1D2D3

V10,3310,67

V20,670,331

V310,670,33

9. O firm dorete achiziionarea unui utilaj. Pentru acesta, firma are de ales ntre trei oferte de utilaje, analiza acestora fcndu-se n raport cu patru criterii decizionale. tiind c matricea decizional este:

Criterii

VarianteC1C2C3C4

V13005020500

V21706015400

V32104025450

i c primele trei criterii sunt de maximizare, iar ultimul de minimizare, se cere:

a) s se estimeze utilitile consecinelor i s se formuleze soluia problemei atunci cnd firma acord criteriilor coeficieni de importan: k1=0,4; k2=0,2; k3=0,1; k4=0,3;91

b) considernd c cele patru criterii sunt la fel de importante pentru firm, s se rezolve problema prin metoda momentelor (Deutch-Martin).

NOT: Punctul a) se va rezolva prin metoda utilitii globale.

2.2. PROBLEME DE DECIZIE N CONDIII DE INCERTITUDINE

PROBLEM REZOLVAT

Conducerea unei firme trebuie s opteze pentru introducerea n fabricaie a unui din cele trei produse (P1,P2,P3). ntruct nu dispune de informaii certe asupra cererii, cunoscnd doar c ar putea fi vndut oricare din cantitile: 100, 200, 300 i 400 buc. i c profitul aferent ar fi cel din tabelul de mai jos, se cere stabilirea produsului ce va fi inclus n fabricaie.92

- mil lei -

Cantiti

Variante100200300400

V115060078012000

V220045090017000

V3350500850011400

Rezolvare:

- Regula pesimist

, adic:

EMBED Equation.3

EMBED Equation.3 - Regula optimist

93

- Regula de optimalitate (Hurwicz)Presupunem

- Regula proporionalitii (Bayes Laplace)

94

- Regula minimizri regretelor (L. Savage)

Construim matricea regretelor:

Cantiti

Variante100200300400

V1200077205000

V215015076000

V3010005600

n matricea regretelor, fiecare element s-a obinut scznd din valoarea sa iniial elementul maxim pe coloan (diferena luat n valoare absolut), conform relaiei:

Centraliznd variantele optime obinute dup cele cinci reguli, ntocmim urmtoarea matrice:

95 Criterii

dec.

Var.PesimistOptimistHurwiczLaplaceSavage

V1

V2

V3

Analiznd tabelul se constat c V1 nu este agreat de nici un criteriu, deci va iei din discuie. Dei V3 este preferat de trei criterii, iar V2 de numai dou criterii, regula majoritii nu este totui relevant. Aadar, alegerea unei variante optime comport introducerea de filtre sau baraje suplimentare de selecie a deciziei, precum i anumite elemente legate de psihologia managerului i situaia economico-financiar a firmei.

PROBLEME PROPUSE SPRE REZOLVARE

1. Un posesor de capital dorete s-l valorifice prin investiie. n acest sens, solicit ca o organizaie de consultan n probleme financiare s-i elaboreze un studiu de oportunitate. n tabelul de mai jos este prezentat matricea de pli, ca o rezultant central a investigaiilor ntreprinse de contractant relativ la patru variante de soluionare a problemei. Plile reprezint ratele anuale de 96

recuperare a capitalului n variantele respective. Capitalul este de 100.000 $. Firma de consultan se oblig s indice varianta optim, garantnd soluia recomandat clientului. Ratele recuperrii capitalului pe variante ale rezolvrii problemei de investiii, n procente se prezint ca n tabelul urmtor:

Stare ec.

VarianteCretere economicRecesiuneInflaieStagnare

V1 investiie n sfera serviciilor154-27

V2 investiie n comer20-1022

V3 investiie n sfera bancar125-6-5

V4 investiie n afaceri imobiliare10-4154

2. Pentru realizarea unui produs industrial sunt posibile patru tehnologii distincte: T1,T2,T3,T4, concretizate n patru variante tehnologice. Conducerea firmei, la care se poate utiliza oricare din cele patru tehnologii, trebuie s aleag una din ele, innd cont c cererea pentru produsul realizat este cuprins ntre 8000i 14500 buci. Profiturile realizate prin aplicarea tehnologiilor sunt prezentate n tabelul de mai jos:97

- mil lei - Cj

Vi8000950011500120001300014500

V17200780010300110001280015500

V27800790010000105001130013500

V38200870011000112001180014600

V47000810011200123001400015000

3. n baza unui studiu de pia, referitor la bunuri de folosin ndelungat destinate populaiei, o firm urmrete s introduc n fabricaie unul din cele patru produse pe care i-a propus a le realiza n semestrul I al anului urmtor. Din studiu a rezultat o cerere variabil pentru acest produs cuprins ntre 1500 i 6000 produse i un profit aferent ce rezult din tabelul de mai jos:

- mil lei - Cj

Vi150018003000350042006000

V18509201020150022003000

V29609801000160019003300

V3800810920110028004000

V494013001600220030003800

Se cere s se stabileasc produsul ce va fi introdus n fabricaie, optimiznd decizia luat n condiii de certitudine. Se d =0,3.98

4. O firm trebuie s aleag unul din produsele sale cu una din cele patru variante tehnologice, n condiiile unei cereri variabile din acest produs, cuprins ntre 85000 buc. i 124000 buc., i a unui profit prezentat n tabelul urmtor:

- mil lei

Cj

Vi85.00092.000102.000115.000120.000124.000

V1920.000980.0001.250.0001.500.0002.100.0002.800.000

V2840.000910.000990.0001.600.0002.300.0003.100.000

V31.150.0001.400.0002.000.0003.100.0003.400.0004.300.000

V4780.000900.0001.350.0002.000.0003.150.0004.500.000

S se optimizeze decizia privind alegerea produsului n condiii de certitudine (=0,3).

5. Extinderea unei ntreprinderi presupune construirea unei noi secii de fabricaie. Necesitile produciei impun nceperea lucrrilor toamna, existnd trei variante de proiect (V1, V2, V3). Estimrile privind duratele de execuie (exprimate n luni) s-au fcut pentru trei stri ale naturii (S1 iarn uoar; S2 iarn obinuit; S3 iarn grea) i se prezint n tabelul urmtor:99 Sj

ViS1S2S3

V14,558

V24,05,56,5

V32,577,5

S se optimizeze decizia privind alegerea variantei de proiect. Se d =0,7.2.3. PROBLEME DE DECIZIE N CONDIII DE RISC

n scopul nelegerii soluionrii acestor tipuri de probleme, vom prezenta concret modaliti de rezolvare a acestora, lund n discuie mai multe situaii posibile. Vom utiliza n acest caz metoda arborilor de decizie.

2.3.1. Arbori cu probabiliti simple

n acest prim caz vom avea n vedere-n studiul soluionrii problemelor prin utilizarea arborilor de decizie probabilitile-simple, determinate obiectiv sau subiectiv.100

Probabilitile obiective sunt aplicabile n cazul proceselor repetitive, ele calculndu-se pe baz de date statistice referitoare la producerea evenimentelor.

Probabilitile subiective se stabilesc prin expertiz, pentru aceasta putndu-se lua o variabil aleatoare x cu distribuie uniform, . n cadrul acestui interval, expertul fixeaz un reper x* indicnd nivelul probabilitii cutate.

1. Un colectiv de cercetare dispune de condiii pentru abordarea a trei teme importante T1, T2 i T3, ns avnd o capacitate limitat nu poate aborda dect una dintre ele.

Prima tem de cercet