Rezolvarea problemelor de programare liniară

CAPITOLUL 13

REZOLVAREA PROBLEMELOR DE PROGRAMARE LINIARÃ 13.1. Rezolvarea problemelor şi procesul de luare a deciziilor }n general, prin <problem[> se ]n\elege o dificultate care nu poate fi dep[=it[ ]n mod automat. Procesul de rezolvare a unei probleme poate fi definit ca procesul de identificare a diferen\elor dintre starea actual[ =i starea dorit[ a unei afaceri =i stabilirea ac\iunilor necesare pentru a rezolva aceast[ diferen\[. Pentru probleme destul de complicate care s[ justifice timpul =i efortul unei analize am[nun\ite, procesul de rezolvare a unei probleme implic[ parcurgerea urm[torilor pa=i:

1. Identificarea =i definirea problemei. 2. Determinarea unui set de solu\ii alternative. 3. Determinarea unui criteriu sau a unor criterii pentru evaluarea alternativelor. 4. Evaluarea alternativelor. 5. Alegerea unei alternative. 6. Implementarea alternativei alese. 7. Evaluarea rezultatelor =i verificarea dac[ a fost selectat[ o solu\ie satisf[c[toare. Luarea deciziilor este un termen ]n general asociat cu primele cinci etape ale procesului

de rezolvare a unei probleme. Astfel, prima etap[ ]n luarea unei decizii este identificarea =i definirea problemei, iar ultima etap[ este alegerea unei alternative, care de fapt este actul de luare a deciziei (figura 13.1). S[ consider[m urm[toarea situa\ie. Un absolvent de facultate ]=i caut[ un serviciu. Ca urmare a cererilor depuse, absolventul prime=te mai multe oferte situate ]n localit[\i diferite: Bucure=ti, Timi=oara, Constan\a, Bra=ov. Alternativele pentru acest caz de luare a deciziei sunt:

1. Acceptarea postului din Bucure=ti. 2. Acceptarea postului din Timi=oara. 3. Acceptarea postului din Constan\a. 4. Acceptarea postului din Bra=ov. Urm[torul pas al procesului de luare a deciziei este stabilirea criteriilor ce vor fi folosite

]n evaluarea alternativelor. Problemele decizionale ]n care obiectivul este de a g[si cea mai bun[ solu\ie ]n raport cu un singur criteriu se numesc decizii cu un singur obiectiv. Desigur, un criteriu important este salariul, dar pot exista =i alte criterii: posibilitatea de avansare, localitatea, posibilitatea de a avea o locuin\[. Problemele decizionale ]n care decizia este luat[ ]n func\ie de mai multe criterii se numesc decizii multicriteriale.

Urm[torul pas este evaluarea fiec[rei altenative ]n raport cu fiecare criteriu. Unele criterii sunt u=or de evaluat (cum ar fi salariul), altele pot fi evaluate pe baza unor factori subiectivi (poten\ialul de avansare, localitatea). }n general, la factorii subiectivi, pentru fiecare variant[ se acord[ un calificativ sau o not[. De foarte multe ori criteriile sunt contradictorii. O alternativ[ bun[ prin aplicarea unui criteriu poate s[ nu fie la fel de bun[ prin aplicarea celorlalte criterii.

Pentru evaluarea primului tip de criterii se folosesc metodele cantitative, pentru cel de al doilea tip, metodele calitative.

}n abordarea cantitativ[ analistul se va concentra asupra datelor asociate problemei =i va dezvolta un model matematic care va descrie obiectivele, restric\iile sau alte rela\ii care exist[ ]n problem[. Ulterior, prin utilizarea metodelor cantitative, analistul va face o alegere ]n func\ie de datele problemei.

Modelarea deciziilor utilizând foile de calcul

Analiza calitativ[ se bazeaz[ mai mult pe intui\ie =i experien\[. Dac[ managerul a avut experien\e similare, problema este relativ simpl[. Dac[ managerul nu are experien\[ ]n probleme similare sau problema este prea complex[, pentru luarea deciziei finale se recomand[ metodele cantitative.

Figura 13.1 – Procesul de luare a deciziei

13.2. Dezvoltarea modelelor Modelele sunt reprezent[ri ale unor obiecte sau situa\ii reale. Ele pot exista ]n mai multe forme. De exemplu, o machet[ a unui avion este o reprezentare a unui avion adev[rat. Similar, un camion de juc[rie este modelul unui camion adev[rat. Aceste dou[ exemple de modele sunt replici fizice ale obiectelor reale. Folosind terminologia adecvat[, ele sunt modele fizice sau modele iconice. O alt[ categorie de modele include obiectele care exist[ ]n form[ fizic[, dar nu au acela=i aspect ca =i obiectul modelat. Acestea sunt modelele analogice. Cutia de viteze a unui automobil este un model analogic: pozi\ia acului indic[ viteza automobilului. Un termometru este un alt model analogic pentru reprezentarea temperaturii. A treia categorie include acele modele care reprezint[ o problem[ sub forma unui set de rela\ii matematice. Aceste modele se numesc modele matematice. De exemplu, profitul total ob\inut prin v`nzarea unui produs poate fi calculat ]nmul\ind profitul unitar cu cantitatea v`ndut[. Dac[ x reprezint[ num[rul de unit[\i v`ndute, P profitul total, atunci pentru un profit

Definirea problemei

Identificarea alternativelor

Determinarea criteriilor

Evaluarea alternativelor

Analiza cantitativ[

Analiza calitativ[

Luarea deciziei

Rezolvarea problemelor de programare liniară

unitar de 1000 lei, modelul matematic care stabile=te profitul total ]n func\ie de v`nz[ri este Pˆ1000*x. Scopul utiliz[rii modelelor este realizarea unei interfe\e cu situa\ia real[ prin studierea =i analizarea modelului. De exemplu, un constructor de avioane poate testa un model fizic pentru a verifica caracteristicile de zbor ale unui avion adev[rat. Similar, un model matematic poate fi utilizat pentru a analiza ce profit va fi ob\inut dac[ un produs este v`ndut. Pentru cazul prezentat, dac[ vor fi v`ndute 30 de buc[\i (xˆ30), profitul ob\inut va fi de 30*1000ˆ30000 lei. Utilizarea modelelor matematice reduce cheltuielile =i timpul necesar pentru rezolvarea unei probleme reale. O machet[ de avion se construie=te mai repede =i este mai ieftin[ dec`t un avion real. La fel, prin utilizarea modelului matematic, se poate calcula rapid profitul ce poate fi ob\inut, f[r[ ca managerul s[ produc[ =i s[ v`nd[ cele x unit[\i. Modelele au =i avantajul reducerii riscului asociat, prin experimentarea unei situa\ii reale. Pentru exemplele prezentate se pot evita gre=elile de proiectare, care ar putea duce la pr[bu=irea avionului, sau se pot evita deciziile gre=ite care ar duce la pierderi de milioane de lei. Concluziile ob\inute depind de c`t de bine reprezint[ modelul situa\ia real[. Cu c`t modelul se apropie mai mult de cazul real, cu at`t rezultatele vor fi mai precise. }n continuare vor fi analizate numai modelele matematice. Principalele aspecte abordate se refer[ la utilizarea metodelor cantitative ]n procesul de luare a deciziei. Accentul este pus nu pe metodele propriu-zise, ci pe modul ]n care ele pot fi rezolvate utiliz`nd foile de calcul. 13.3. Modele matematice }n majoritatea cazurilor ]n care se ]ncearc[ rezolvarea unor probleme manageriale se constat[ c[ modul ]n care este structurat[ problema conduce la ob\inerea unui obiectiv specific (cum ar fi maximizarea unui profit sau minimizarea unui cost). De asemenea, se constat[ c[ de multe ori exist[ o serie de restric\ii sau constr`ngeri (cum ar fi capacitatea de produc\ie). Succesul folosirii analizei cantitative depinde de acurate\ea cu care obiectivul =i restric\iile sunt exprimate sub form[ de ecua\ii =i rela\ii matematice. Expresia matematic[ care descrie obiectivul problemei se nume=te func\ie obiectiv. De exemplu, ecua\ia Pˆ10*x poate fi func\ia obiectiv a unei firme care ]ncearc[ s[ maximizeze profitul. Rela\iile matematice care descriu constr`ngerile problemei se numesc restric\ii. Dac[ de exemplu pentru a produce o unitate de produs sunt necesare 5 ore =i ]ntr-o s[pt[m`n[ se lucreaz[ doar 40 de ore, atunci rela\ia 50*x�ˆ40 este o restric\ie de timp. 5*x reprezint[ timpul total necesar pentru a produce x unit[\i, care trebuie s[ fie mai mic sau egal cu cele 40 de ore disponibile. Problema de decizie este urm[toarea: C`te unit[\i trebuie produse ]ntr-o s[pt[m`n[ pentru a maximiza profitul? Modelul matematic al acestei probleme este:

restrictiixx

obiectivfunctiaxPMax

≥≤

=

040*5*10

Restric\ia x�ˆ0 este necesar[ deoarece nu se poate fabrica un num[r negativ de produse.

Modelarea deciziilor utilizând foile de calcul

13.4. Metoda programării liniare

Programarea liniar[ este o metod[ de rezolvare a problemelor de luare a deciziei. Urm[toarele tipuri de aplica\ii sunt specifice pentru rezolvarea lor cu ajutorul program[rii liniare:

1. Un manager trebuie s[ stabileasc[ pentru perioada urm[toare programul de produc\ie =i nivelul stocurilor astfel ]nc`t s[ fie satisf[cut[ cererea de pe pia\[ =i ]n acela=i timp vrea s[ minimizeze costul total de produc\ie =i costurile de stocare.

2. Un analist financiar trebuie s[ selecteze pentru un portofoliu de investi\ii cea mai bun[ combina\ie de ac\iuni =i obliga\iuni. Aceste investi\ii trebuie selectate astfel ]nc`t s[ se maximizeze eficien\a investi\iei.

3. Un director de marketing trebuie s[ stabileasc[ modul ]n care va distribui bugetul pentru publicitate ]n diverse medii: radio, televiziune, ziare =i reviste, astfel ]nc`t efectul reclamei f[cute s[ fie maxim.

4. O companie are depozite ]n c`teva ora=e din \ar[ =i prime=te comenzi de la clien\i din diverse localit[\i. Se pune problema determin[rii cantit[\ilor care vor fi trimise de la depozite spre clien\i astfel ]nc`t costurile totale de transport s[ fie minimizate.

Acestea sunt doar c`teva exemple ]n care programarea liniar[ a fost utilizat[ cu succes, dar lista poate continua. Ce au ]n comun aceste exemple este faptul c[ ele ]ncearc[ s[ minimizeze sau s[ maximizeze ceva. }n primul exemplu managerul vrea s[ minimizeze costurile; ]n exemplul 2 analistul financiar vrea s[ maximizeze eficien\a investi\iei; ]n exemplul 3 directorul de marketing trebuie s[ maximizeze eficien\a reclamei; ]n exemplul 4 trebuie minimizate cheltuielile de transport. }n toate problemele de programare liniar[, obiectivul este maximizarea sau minimizarea unor cantit[\i.

Toate problemele de programare liniar[ au =i o a doua proprietate: restric\iile care limiteaz[ gradul ]n care obiectivul poate fi realizat. }n exemplul 1 produc\ia este limitat[ de capacitatea de produc\ie =i ]n acela=i timp trebuie s[ satisfac[ cererea; ]n exemplul 2 analistul este limitat de suma disponibil[ =i tipul ac\iunilor existente; ]n exemplul 3 directorul de marketing este constr`ns de bugetul fixat =i de disponibilitatea mediilor de reclama; ]n exemplul 4 cantit[\ile ce pot fi transportate sunt limitate la disponibilul din fiecare depozit. Deci, restric\iile sunt o alt[ tr[s[tur[ general[ a fiec[rei probleme de programare liniar[. Exemplu

Firma ABC produce o varietate de produse chimice. }n cadrul unui proces de produc\ie, pentru a produce dou[ produse (un aditiv =i un solvent) sunt necesare trei tipuri de materii prime. Aditivul este v`ndut fabricilor de ulei =i este folosit la producerea a diverse tipuri de combustibil. Solventul este v`ndut combinatelor chimice =i este utilizat la fabricarea detergen\ilor. Pentru a fabrica aditivul =i solventul cele trei materii prime sunt amestecate ]n propor\iile indicate ]n tabelul 13.1.

Produs Aditiv Solvent

Material 1 2/5 ½ Material 2 0 1/5 Material 3 3/5

3/10 Tabelul 13.1 – Necesarul de materii prime pentru ob\inerea unei tone de adidiv/solvent

Rezolvarea problemelor de programare liniară

Pentru a ob\ine o ton[ de aditiv se amestec[ 2/5 tone de material 1=i 3/5 tone de material

3. O ton[ de solvent poate fi ob\inut[ prin amestecarea a ½ tone de material 1, 1/5 tone de material 2 =i 3/10 tone de material 3.

Produc\ia este limitat[ de disponibilitatea celor trei materii prime. }n prezent firma dispune de 20 tone de material 1, 5 tone de material 2 =i 21 tone de material 3. Prin natura procesului de produc\ie, materiile prime care nu sunt utilizate ]n procesul de produc\ie curent sunt considerate de=euri.

Fiecare ton[ de aditiv aduce un profit de 40$ , iar fiecare ton[ de solvent aduce un profit de 30$.

Managementul firmei ABC, dup[ analiza cererii de pe pia\[, a decis c[ pre\urile stabilite vor determina v`nzarea ]ntregii cantit[\ii produse (aditiv =i sovent). Formularea problemei Formularea problemei sau modelarea reprezint[ procesul de transpunere a problemei ]ntr-un model matematic. Modelarea problemei este o art[ care poate fi st[p`nit[ prin practic[ =i experien\[. De=i fiecare problem[ are caracteristici unice, multe probleme pot avea tr[s[turi comune. Ca urmare, pentru ]ncep[tori pot fi utile o serie de reguli ce pot fi aplicate pentru formularea unui model, reguli ce vor fi ilustrate ]n dezvoltarea modelului matematic pentru firma ABC. Acest exemplu a fost selectat pentru a introduce metoda program[rii liniare pentru c[ este u=or de ]n\eles. }n practic[ apar probleme mai complicate, care necesit[ o analiz[ mai profund[ pentru a identifica toate aspectele care trebuie incluse ]n model.

Primul pas este identificarea obiectivului =i a restric\iilor. }n cazul nostru obiectivul este maximizarea profitului total. Restric\iile se refer[ la cantit[\ile de materii prime disponibile, care limiteaz[ cantit[\ile de aditiv =i solvent ce pot fi produse. Restric\ia 1: cantitatea de material 1 utilizat[ trebuie s[ fie mai mic[ sau egal[ cu

cantitatea de material 1 disponibil[. Restric\ia 2: cantitatea de material 2 utilizat[ trebuie s[ fie mai mic[ sau egal[ cu

cantitatea de material 2 disponibil[. Restric\ia 3: cantitatea de material 3 utilizat[ trebuie s[ fie mai mic[ sau egal[ cu

cantitatea de material 3 disponibil[. Urm[torul pas este definirea variabilelor de decizie. Cele dou[ variabile de decizie

sunt: num[rul de tone de aditiv produse =i num[rul de tone de solvent produse. Not[m cu: A: cantitatea de aditiv produs[ (tone) S: cantitatea de solvent produs[ (tone) A =i S sunt variabile de decizie. Se scrie obiectivul utiliz`nd variabilele de decizie. Profitul total provine din dou[ surse:

v`nz[rile de aditiv =i v`nz[rile de solvent. Dac[ profitul ob\inut prin v`nzarea unei tone de aditiv este de 40$, atunci prin v`nzarea a A tone profitul va fi 40*A. La fel, dac[ profitul ob\inut prin v`nzarea unei tone de solvent este de 30$, atunci prin v`nzarea a S tone profitul va fi 40*S.

Profitul total ˆ 40A ‡ 30S Expresia matematic[ a obiectivului se nume=te func\ie obiectiv. }n cazul nostru

obiectivul este maximizarea profitului total, deci func\ia obiectiv va fi:

Modelarea deciziilor utilizând foile de calcul

Max ( 40A ‡ 30S )

Se scriu restric\iile utiliz`nd variabilele de decizie. Restric\ia 1. Deoarece o ton[ de aditiv este produs[ folosind 2/5 tone de material 1,

cantitatea de material 1 necesar[ pentru a produce A tone de aditiv este 2/5 * A. Pentru fiecare ton[ de solvent se folosesc ½ tone de material 1, deci cantitatea de material 1 necesar[ pentru a produce S tone de solvent este ½ * S. Astfel, cantitatea total[ de material 1 necesar[ este 2/5 * A ‡ ½ * S. Cantitatea disponibil[ de material 1 este de 20 tone, deci transpunerea sub form[ de ecua\ie a restric\iei 1 este:

2/5 * A ‡ ½ * S � ˆ20 Restric\ia 2. Deoarece la fabricarea aditivului nu este necesar materialul 1 se va lua ]n

lua ]n calcul doar cantitatea de material 2 utilizat[ la fabricarea solventului. Pentru fiecare ton[ de solvent se folosesc 1/5 tone de material 2, deci cantitatea de material 2 necesar[ pentru a produce S tone de solvent este 1/5 * S. Astfel, cantitatea total[ de material 2 necesar[ este 1/5 * S. Cantitatea disponibil[ de material 2 este de 5 tone, deci transpunerea sub form[ de ecua\ie a restric\iei 2 este:

1/5 * S �ˆ5 Restric\ia 3. Deoarece o ton[ de aditiv este produs[ folosind 3/5 tone de material 3,

cantitatea de material 3 necesar[ pentru a produce A tone de aditiv este 3/5 * A. Pentru fiecare ton[ de solvent se folosesc 3/10 tone de material 3, deci cantitatea de material 3 necesar[ pentru a produce S tone de solvent este 3/10 * S. Astfel, cantitatea total[ de material 3 necesar[ este 3/5 * A ‡ 3/10 * S. Cantitatea disponibil[ de material 3 este de 21 tone, deci transpunerea sub form[ de ecua\ie a restric\iei 3 este:

3/5 * A ‡ 3/10 * S �ˆ 21 P`n[ acum am specificat rela\iile matematice referitoare la constr`ngerile asociate celor

trei materii prime. Mai trebuie oare alte restric\ii? Poate firma ABC s[ produc[ un num[r negativ de tone de aditiv =i solvent? R[spunsul este evident nu. Deci pentru ca variabilele de decizie s[ nu aib[ valori negative mai sunt necesare dou[ restric\ii:

A �ˆ0 S �ˆ0

Modelul matematic al problemei este acum complet. At`t obiectivul c`t =i restric\iile au fost transformate ]ntr-un set de rela\ii matematice, set de rela\ii definit ca model matematic. Modelul matematic complet al problemei este:

Max ( 40A ‡ 30S ) 2/5 * A ‡ ½ * S�ˆ20 1/5 * S�ˆ5 3/5 * A ‡ 3/10 * S�ˆ21 A�ˆ0 S�ˆ0

Pentru rezolvarea problemei trebuie g[sit[ combina\ia optim[ (de A =i S) care s[ satisfac[ toate restric\iile =i ]n acela=i timp s[ conduc[ la o valoare a func\iei obiectiv care s[ fie mai mare sau egal[ dec`t orice valoare calculat[ cu o alt[ solu\ie posibil[. Dac[ func\ia obiectiv =i restric\iile sunt func\ii liniare ]n raport cu variabilele de decizie (variabilele de decizie apar numai la puterea I), atunci avem o problem[ de programare liniar[.

Rezolvarea problemelor de programare liniară

Pentru rezolvarea problemelor de programare liniar[ exist[ mai multe metode analitice: metoda Simplex, metoda grafic[. }n continuare vom prezenta modul ]n care pot fi rezolvate problemele de programare liniar[ utiliz`nd foile de calcul (Microsoft Excel). 13.5. Utilizarea foilor de calcul pentru rezolvarea problemelor de programare liniară Foile de calcul sunt instrumente utilizate frecvent pentru prelucrarea datelor ]n multe organiza\ii. Deoarece modelele matematice necesit[ de multe ori date care deja exist[ ]n alte foi de calcul, este important a ]n\elege modul ]n care o problem[ de programare liniar[ poate fi rezolvat[ cu ajutorul foilor de calcul. }n continuare vom ilustra modul ]n care se poate rezolva problema precedent[ folosind foile de calcul. }n acest scop va fi folosit programul de calcul tabelar Microsoft Excel. Un model de programare liniar[ transpus ]ntr-o foaie de calcul va con\ine urm[toarele elemente:

1. Celulele care con\in datele problemei. 2. Celulele pentru variabilele de decizie. 3. O celul[ care con\ine formula pentru calcularea func\iei obiectiv. 4. Celulele care con\in formulele pentru calcularea p[r\ii st`ngi a restric\iilor. 5. Celulele care con\in valorile p[r\ii drepte a restric\iilor.

Transpunerea problemei ]ntr-o foaie de calcul presupune parcurgerea urm[toarelor etape:

1. Introducerea datelor problemei ]n foaia de calcul. 2. Definirea celulelor care vor con\ine variabilele de decizie. 3. Definirea celulei care con\ine formula pentru func\ia obiectiv. 4. Definirea celulelor care con\in formulele din partea st`ng[ a restic\iilor. 5. Definirea celulelor care con\in valorile din partea dreapt[ a restric\iilor. }n figura 13.2 este prezentat[ solu\ia pentru problema prezentat[ anterior.

Figura 13.2 – Foaia de calcul utilizat[ pentru rezolvarea problemei

123456789

10

111213141516

171819202122

A B C DFirma ABC

Materiale Aditiv Solvent Cantitate disponibila Material 1 0.4 0.5 20 Material 2 0 0.2 5 Material 3 0.6 0.3 21Profit pe tona 40 30

Model

Aditiv SolventTone produse

Maximizarea profitului total =B8*B15+C8*C15

Restrictii Cantitati utilizate Cantitati disponibile Material 1 =B5*B15+C5*C15 <= =D5 Material 2 =B6*B15+C6*C15 <= =D6 Material 3 =B7*B15+C7*C15 <= =D7

Necesar de materiale

Variabile de decizie

Modelarea deciziilor utilizând foile de calcul

Remarca\i c[ foaia de calcul este alc[tuit[ din dou[ p[r\i: o parte con\ine datele problemei =i alta con\ine modelul. Un avantaj al separ[rii datelor de model este c[ se poate studia efectul modific[rii m[rimilor de intrare asupra modelului f[c`nd modific[ri doar ]n zona care con\ine date. Un alt avantaj este c[ analistul poate dezvolta modelul independent de datele disponibile.

}n continuare este prezentat fiecare pas al procedurii: Pasul 1: Introducerea datelor problemei. Datele problemei apar ]n partea superioar[ a

foii de calcul. Frac\iile care reprezint[ compozi\ia pentru ob\inerea unei tone de solvent =i aditiv au fost convertite ]n valori zecimale =i introduse ]n domeniul B5:C7. Valoarea 0.4 din celula B5 arat[ c[ fiecare ton[ de aditiv produs[ utilizeaz[ 0.4 tone de material 1, valoarea 0.5 din celula C5 arat[ c[ fiecare ton[ de solvent produs[ utilizeaz[ 0.5 tone de material 1, etc. Celulele D5:D7 con\in cantitatea disponibil[ din fiecare material, iar celulele B8 =i C8 con\in profitul ob\inut prin v`nzarea unei tone de aditiv (40$), respectiv solvent (30$).

Pasul 2: Definirea celulelor care vor con\ine variabilele de decizie. Celulele B15 =i

C15 con\in num[rul de tone de aditiv =i solvent produse. Pasul 3: Definirea celulei care con\ine formula func\iei obiectiv. Celula B17 con\ine

formula pentru calcularea func\iei obiectiv: ˆ B8*B15‡ C8*C15 (profiul unitar pe tona de aditiv * produc\ia de aditiv ‡ profiul unitar pe tona de solvent * produc\ia de solvent).

Pasul 4: Definirea celulelor care con\in formulele din partea st`ng[ a restric\iilor.

Celulele B20:B22 con\in formulele care indic[ cum se calculeaz[ partea st`ng[ a restric\iilor. Pentru materialul 1, ]n celula B20 se introduce formula ˆB5*B15‡C5*C15 (cantitatea de aditiv produs[*cantitatea de material 1 pentru a produce o ton[ de aditv ‡ cantitatea de solvent produs[*cantitatea de material 1 pentru a produce o ton[ de solvent). }n mod similar se vor introduce ]n celulele B21 =i B22 formulele pentru materialele 2 =i 3.

Pasul 5: Definirea celulelor care con\in valorile din partea dreapt[ a restric\iilor. }n

problema analizat[ valorile din partea dreapt[ a restric\iilor reprezint[ cantit[\ile de material disponibile, valori care deja sunt introduse ]n domeniul D5:D7. Pentru materialul 1, ]n celula D20 se introduce formla ˆD5, pentru matrialul 2, ]n celula D21 se introduce formula ˆD6, iar pentru materialul 3 ]n celula D22 se introduce formula ˆD7.

Un avantaj al folosirii foilor de calcul este c[ dac[ una din valorile din partea care

con\ine datele problemei se modific[, valorile din model se modific[ automat.. Pentru a determina solu\ia optim[ a problemei se va folosi Solver-ul din Excel. Pa=ii

urm[tori arat[ modul ]n care poate fi folosit Solver-ul pentru ob\inerea solu\iei optime pentru o problem[ de programare liniar[.

1. Se selecteaz[ meniul Tools. 2. Se aplic[ comanda Solver. 3. Caseta Solver Parameters se completeaz[ ]n modul urm[tor:

• Set Target Cell: B17 • Se selecteaz[ op\iunea Max. • By Changing Cells: B15:C15. • Se selecteaz[ butonul Add.

4. Caseta Add Constraint se completeaz[ astfel: • Cell Reference: B20:B22 • Se selecteaz[ operatorul ‹ ˆ

Rezolvarea problemelor de programare liniară

• Constraint: D20:D22 • Se selecteaz[ butonul OK.

5. C`nd caseta Solver Parameters apare din nou se selecteaz[ butonul Options. 6. }n caseta Solver Options se selecteaz[:

• Assume Linear Model. • Assume Non- Negative. • Butonul Ok.

7. C`nd caseta Solver Parameters apare din nou se selecteaz[ butonul Solve. 8. }n caseta Solver Results se selecteaz[ Keep Solver Solution. Se selecteaz[

butonul Ok pentru a genera solu\ia optim[, afi=at[ ]n celulele B15, C15. Solu\ia optim[ este 25 tone de aditiv =i 20 tone de solvent.

13.6. Analiza de senzitivitate şi interpretarea rezultatelor Problemele din lumea real[ au loc ]ntr-un mediu ]n continu[ schimbare. Pre\ul materiilor prime, salariile, cererea, oferta, valoarea ac\iunilor, etc. sunt valori care pot varia de la un moment la altul. Dac[ o problem[ de programare liniar[ este utilizat[ ]ntr-un astfel de mediu, ne putem a=tepta ca anumi\i coeficien\i ai problemei s[ se modifice ]n timp. Deci va trebui s[ determin[m cum afecteaz[ aceste schimb[ri solu\ia optim[ a problemei de programare liniar[ ini\ial[.

Cu analiza de senzitivitate se poate observa cum este afectat[ solu\ia optim[ de modific[ri ale coefiecien\ilor dintr-o problem[ de programare liniar[. Utiliz`nd analiza de senzitivitate se poate r[spunde la ]ntreb[ri de tipul:

1. Cum este afectat[ solu\ia optim[ de o modificare a unui coeficient din func\ia obiectiv?

2. Cum este afectat[ solu\ia optim[ de o modificare a valorii din partea dreapt[ a restric\iilor?

Deoarece obiectul analizei de senzitivitate este modul ]n care modific[rile specificate afecteaz[ solu\ia optim[, analiza nu poate ]ncepe p`n[ c`nd nu se ob\ine solu\ia problemei de programare liniar[ ini\ial[. Din aceast[ cauz[, analiza de senzitivitate este de multe ori numit[ =i analiz[ postoptimal[. Revenind la problema prezentat[ anterior:

Max ( 40A ‡ 30S )

2/5 * A ‡ ½ * S�ˆ20 Materialul 1 1/5 * S�ˆ5 Materialul 2 3/5 * A ‡ 3/10 * S�ˆ21 Materialul 3 A�ˆ0 S�ˆ0

Solu\ia optim[ Aˆ25 tone de aditiv =i Sˆ20 tone de solvent s-a ob\inut pentru cazul ]n care s-a considerat c[ profitul pe ton[ pentru aditiv este 40$, iar profitul pe ton[ pentru solvent este de 30$. Presupunem c[ datorit[ unor factori exteriori are loc o reducere a pre\urilor, ceea ce determin[ o sc[dere a profitului de la 30$ pe ton[ la 25$ pe ton[ pentru solvent. }n acest caz programul de produc\ie de 25 de tone de aditiv =i 20 de tone de solvent este ]n continuare cel mai bun? }n mod normal ar trebui s[ rezolv[m o nou[ problem[ de programare liniar[ cu func\ia obiectiv modificat[ 40*A‡25*S. Acest lucru nu este necesar, deoarece cu analiza de senzitivitate putem determina ]n ce limite poate varia profitul pe tona de aditiv f[r[ ca solu\ia

Modelarea deciziilor utilizând foile de calcul

optim[ s[ se modifice. Dac[ analiza de senzitivitate arat[ c[ 25 tone de aditiv =i 20 de tone de solvent r[m`ne solu\ia optim[ at`ta timp profitul pe tona de solvent variaz[ ]ntre 20$ =i 40$, agentul decizional poate considera c[ estimarea de 30$/ton[ este bun[. Dac[ analiza de senzitivitate arat[ c[ 25 de tone de aditiv =i 20 de tone de solvent r[m`ne solu\ia optim[ at`ta timp profitul pe tona de solvent variaz[ ]ntre 29.90$ =i 32$, managementul va trebui s[ reanalizeze acurate\ea estim[rii de 30$/tona de solvent. Domeniul de optimalitate pentru fiecare coeficient al func\iei obiectiv este domeniul de valori ]n care acest coeficient poate varia far[ a modifica solu\ia optim[. Managerul va trebui s[ analizeze cu aten\ie acei coeficien\i din func\ia obiectiv care au un domeniu de optimalitate ]ngust, deoarece o mic[ modificare a acestora poate modifica solu\ia optim[. Un alt aspect al analizei de senzitivitate se refer[ la modific[rile valorilor din partea dreapt[ a restric\iilor. Referindu-ne la aceea=i problem[, pentru solu\ia optim[ sunt utilizate ]n ]ntregime stocurile de material 1 =i 3. Ce se ]nt`mpl[ cu solu\ia optim[ =i profitul total dac[ se m[resc cantit[\ile disponibile de material 1 =i 3? Cu analiza de senzitivitate se poate determina cu c`t va cre=te profitul total dac[ cantitatea disponibil[ de material 1 sau 3 cre=te cu o ton[. Pentru ca programul Excel s[ furnizeze un raport pentru realizarea analizei de senzitivitate, c`nd se rezolv[ problema cu Solver-ul, ]n fereastra de dialog Solver Results, sec\iunea Reports, se selecteaz[ Sensitivity (vezi lec\ia 12). 13.7. Interpretarea raportului Excel pentru analiza de senzitivitate Raportul generat de Excel are structura prezentat[ ]n figura 13.3.

Figura 13.3 – Raportul de analiz[ de senzitivitate

Raportul are dou[ sec\iuni Adjustable Cells =i Constraints. }n sec\iunea Adjustable Cells se analizeaz[ coeficien\ii variabilelor de decizie din func\ia obiectiv, iar ]n sec\iunea Constraints sunt analizate valorile din partea dreapt[ a restric\iilor. Sec\iunea Adjustable Cells }n coloana Cell sunt afi=ate celulele care con\in coeficien\ii variabilelor de decizie din func\ia obiectiv, iar ]n coloana Name sunt afi=ate numele acestor celule. Coloana Final Value con\ine valorile optime pentru variabilele de decizie. Pentru problema analizat[ solu\ia este 25 de tone de aditiv =i 20 tone de solvent.

Coloana Reduced Cost. Pentru fiecare variabil[ de decizie, valoarea absolut[ din Reduced Cost arat[ c`t de mult trebuie s[ creasc[ (pentru problemele de maximizare) sau s[

Microsoft Excel 9.0 Sensitivity ReportWorksheet: Firma ABCReport Created: 28/07/2001 12:39:34 PM

Adjustable CellsFinal Reduced Objective Allowable Allowable

Cell Name Value Cost Coefficient Increase Decrease$B$15 Tone produse Aditiv 25 0 40 20 16$C$15 Tone produse Solvent 20 0 30 20 10

ConstraintsFinal Shadow Constraint Allowable Allowable

Cell Name Value Price R.H. Side Increase Decrease$B$20 Material 1 Cantitati utilizate 20 33.33333333 20 1.5 6$B$21 Material 2 Cantitati utilizate 4 0 5 1E+30 1$B$22 Material 3 Cantitati utilizate 21 44.44444444 21 9 2.25

Rezolvarea problemelor de programare liniară

scad[ (pentru problemele de minimizare) coeficientul variabilei de decizie din func\ia obiectiv astfel ]nc`t variabila de decizie respectiv[ s[ aib[ valoare pozitiv[. Dac[ o variabil[ de decizie este pozitiv[ ]n solu\ia optim[, costul redus este 0. Pentru problema analizat[ ambele variabile de decizie au valori pozitive =i costurile reduse sunt 0. Dac[ de exemplu pentru cantitatea de solvent s-ar fi ob\inut 0 ]n coloana Final Value =i –12.5 ]n coloana Reduced Cost, interpretarea ar fi urm[toarea: profitul pe tona de solvent ar trebui s[ creasc[ la 30‡12.50ˆ42.50 pentru ca ]n solu\ia optim[ variabila de decizie ata=at[ cantit[\ii de solvent s[ aib[ o valoare pozitiv[. Altfel spus, pentru a produce solvent ar trebui ca profitul pe tona de solvent s[ fie 42.50$. Coloana Objective Coefficient con\ine valorile coeficien\ilor variabilelor de decizie din func\ia obiectiv, iar coloanele Allowable Increase =i Allowable Decrease con\in valorile pe baza c[rora se poate calcula domeniu de optimalitate pentru coeficientul respectiv (cre=terea =i mic=orarea permis[). De exemplu, pentru aditiv:

602420401640

≤≤+≤≤−

Aditiv

Aditiv

CC

Deci dac[ profitul pe tona de aditiv variaz[ ]ntre 24 =i 60, solu\ia optim[ de 25 tone de aditiv =i 20 tone de solvent r[m`ne neschimbat[. Pentru solvent:

502020301030

≤≤+≤≤−

Solvent

Solvent

CC

Deci dac[ profitul pe tona de solvent variaz[ ]ntre 20 =i 50, solu\ia optim[ de 25 tone de aditiv =i 20 tone de solvent r[m`ne neschimbat[. Sec\iunea Constraints Coloana Cell indic[ celulele care con\in valorile din partea dreapt[ a restric\iilor, iar coloana Name con\ine numele acestor celule. Valorile din coloana Final Value sunt valorile restric\iilor (partea st`ng[) calculate pentru solu\ia optim[. Pentru problema analizat[ valorile din coloana Final Value indic[ cantit[\ile de material 1, 2 =i 3 necesare pentru a produce combina\ia optim[ de 25 de tone de aditiv =i 20 tone de solvent. Deci pentru solu\ia optim[ sunt necesare 20 tone de material 1, 4 tone de material 2 =i 21 tone de material 3. Valorile din coloana Constraint RH sunt valorile ini\iale ale problemei: 20 tone de material 1, 5 tone de material 2, 21 tone de material 3 (cantit[\ile disponibile). Pentru fiecare restric\ie abaterea reprezint[ diferen\a dintre valoarea din coloana Constraint RH =i valoarea din Final Value. Abaterea asociat[ materialului 1 este 20-20ˆ0 tone, pentru materialul 2: 5-4ˆ1 ton[, iar pentru materialul 3: 21-21ˆ0 tone. Deci materialele 1 =i 3 sunt utilizate ]n totalitate, iar din materialul 2 r[m`ne o ton[. Concluzia este c[ dac[ ar exista cantit[\i mai mari de material 1 sau 3 s-ar putea ob\ine un profit total mai mare. Modul ]n care modificarea acestor cantit[\i influen\eaz[ profitul este indicat ]n coloana Shadow Price (pre\uri umbr[). Pre\urile umbr[ arat[ cu c`t se modific[ (cre=tere/mic=orare) valoarea func\iei obiectiv la cre=terea/mic=orarea cu o unitate a valorii din partea dreapt[ a unei restric\ii. }n cazul nostru, pre\ul umbr[ de 33.33 pentru materialul 1 arat[ c[ o ton[ suplimentar[ de material 1 va cre=te profitul cu 33.33$. Deci, dac[ cantitatea disponibil[ de material 1 ar cre=te de la 20 la 21, ceilal\i coeficien\i r[m`n`nd constan\i, profitul total ar cre=te cu 33.33$, ceea ce ]nseamn[ 1600‡33.33ˆ1633.33$.

Similar, dac[ cantitatea disponibil[ de material 3 ar cre=te de la 21 la 22, ceilal\i coeficien\i r[m`n`nd constan\i, profitul total ar cre=te cu 44.44$, ceea ce ]nseamn[ 1600‡44.44ˆ1644.44$.

Modelarea deciziilor utilizând foile de calcul

Valoarea 0 a pre\ului umbr[ pentru materialul 2 arat[ c[ dac[ cantitatea disponibil[ de material 2 ar cre=te, valoarea func\iei obiectiv (profitul total) nu s-ar modifica.

Ultimele dou[ coloane Allowable Increase =i Allowable Decrease determin[ domeniul ]n care poate varia termenul din dreapta al unei restric\ii f[r[ a se modifica pre\urile umbr[. De exemplu, consider`nd restric\ia pentru materialul 1, termenul din partea dreapt[ are valoarea 20, cre=terea permis[ este 1.5 =i mic=orarea permis[ este de 6. +tim c[ cu un pre\ umbr[ de 33.33$ , o ton[ ]n plus de material 1 va cre=te valoarea func\iei obiectiv (profitul) cu 33.33$, iar reducerea cantit[\ii de material cu o ton[ va mic=ora valoarea func\iei obiectiv cu 33.33$. Valorile din Allowable Increase =i Allowable Decrease arat[ c[ pre\ul umbr[ de 33.33$ este valabil pentru cre=teri de material 1 de p`n[ la 1.5 tone =i reduceri de pan` la 6 tone.

Domeniul de valori ]n care pre\ul umbr[ este aplicabil se nume=te domeniu de fezabilitate. Deci pentru materialul 1 domeniul de fezabilitate este ]ntre 20-6ˆ14 =i 20‡1.5ˆ21.5 tone. Pentru modific[ri ]n afara domeniului de fezabilitate problema trebuie rezolvat[ din nou pentru a g[si noul pre\ umbr[.

Pentru restric\ia materialului 2 cre=terea permis[ este 1E‡30, deci 1030, un num[r foarte mare. Putem interpreta aceast[ valoare ca o eviden\[ a faptului c[ nu exist[ limit[ superioar[ pentru domeniul de fezabilitate a materialului 2. Cu alte cuvinte, oric`t material 2 ar fi disponibil, valoarea func\iei obiectiv nu s-ar modifica. Descre=terea permis[ (1) arat[ c[ limita minim[ a domeniului de fezabilitate pentru materialul 2 este 5-1ˆ4 tone. Deci dac[ pentru produc\ie ar fi disponibile 4.5 tone de material 2, valoarea func\iei obiectiv nu s-ar modifica. Dac[ sunt disponibile mai pu\in de 4 tone va trebui s[ rezolv[m problema din nou pentru a afla noua solu\ie =i pre\urile umbr[.

Pentru materialul 3, domeniul de fezabilitate este ]ntre 21-2.25ˆ18.75 tone =i 21‡9ˆ30 tone. Deci pre\ul umbr[ de 44.44 este aplicabil dac[ termenul din partea dreapt[ a restric\iei (cantitatea de material disponibil) ia valori ]ntre 18.75 tone =i 30 tone.

Informa\iile din raportul de analiz[ de senzitivitate se bazeaz[ pe presupunerea c[ doar

un coeficient se modific[, to\i ceilal\i r[m`n`nd neschimba\i.