Curs5 Modelare Economica 2008 - Nadia Ciocoiu

CURS 6 MODELARE ECONOMICA, LECTOR DR. Nadia Ciocoiu MODELAREA STRUCTURII SORTIMENTALE. STUDIU DE SENZITIVITATE 1. Optimizarea modelelor de tip liniar

2. Formularea cazului general de postoptimizare 3. Aspecte practice în cazul modelării structurii de fabricaţie cu variabilele continue (carte Modelare economica!!) 4. Modelarea structurii de producţie şi a posibilităţilor de ale unei organizaţii (cazul în care variabilele sunt numere întregi)

1. OPTIMIZAREA MODELELOR DE TIP LINIAR  Fiind date n activităţi competitive şi m resurse limitate, se notează cu:

x1, x2,...,xn, nivelurile pe care le pot atinge fiecare din cele n activităţi = variabilele de decizie ale problemei.  Alegerea unei variante decizionale se realizează pe baza unor criterii economice (profit, cost, încărcarea utilajelor etc.) exprimate prin funcţii liniare de forma: n

f(X) =

c

j

xj

j 1

Aceste funcţii vor fi maximizate sau minimizate în funcţie de obiectivul pe care îl reprezintă. Ele se numesc funcţii obiectiv sau de eficienţă.  Nivelul pe care îl poate atinge valoarea funcţiei obiectiv depinde de nivelul resurselor disponibile şi de obligaţiile pe care organizaţia le are de îndeplinit. Aceste constrângeri la care sunt supuse variantele decizionale pot fi exprimate matematic prin restricţii liniare.  Metodele de rezolvare ale modelelor de programare liniară au la bază algoritmul simplex construit de G. Dantzig

1. OPTIMIZAREA MODELELOR DE TIP LINIAR Forma generală a modelului de programare liniară este: n max (sau min) f(X) =  c jx j j1 supusă la restricţiile: AX  b (sau AX ≥ b) X0 unde: 

 X = vector coloană cu n componente x1, x2,...,xn, care reprezintă necunoscutele    

modelului (variabilele decizionale); A, b, c sunt constantele modelului, considerate certe în perioada analizată; A = matrice cu m linii şi n coloane. Este numită matricea coeficienţilor tehnologici aij, i = 1,...,m, j = 1,...,n; b = vector coloană cu m componente b1, b2, ..., bm, care sunt termenii liberi din partea dreaptă a restricţiilor. Ei reprezintă disponibilul maxim dintr-o anumită resursă sau nivelul minim care trebuie atins de anumite activităţi; c = vector linie cu n componente care reprezintă coeficienţii funcţiei obiectiv. Ei pot fi costuri unitare, preţuri unitare, profituri unitare sau alţi indicatori de performanţă care caracterizează variabilele de decizie.

1. OPTIMIZAREA MODELELOR DE TIP LINIAR Orice problemă de programare liniară are două forme: • forma primală  • forma duală.  Prin rezolvarea uneia dintre ele se obţin soluţiile pentru

ambele forme.  Rezolvarea în sistem conversaţional se poate efectua cu produse informatice cum sunt: QM/Linear Programming, WINQSB/Lp – ilp, LINDO, XA, XPRESS – MP, SOLVER care este un instrument add-ins al sistemului Excel.

1. OPTIMIZAREA MODELELOR DE TIP LINIAR Prin rezolvarea modelului de programare liniară (forma primală) se obţin:  Soluţia optimă, adică varianta decizională care duce la cea mai bună valoare a  criteriului de performanţă specificat prin funcţia obiectiv;  Preţurile umbră asociate restricţiilor liniare: • Preţurile umbră reprezintă valorile optime ale variabilelor duale; • Preţurile umbră sunt folosite la analiza senzitivităţii soluţiei optime la variaţia vectorului b al resurselor (termenii liberi ai restricţiilor liniare); • Preţul umbră arată cu cât s-ar modifica valoarea funcţiei obiectiv dacă s-ar putea mări cu o unitate disponibilul din resursa respectivă; • Preţul umbră asociat unei resurse este valabil pentru un anumit interval de variaţie al cantităţii disponibile de resursă; • Preţul umbră este diferit de zero numai dacă restricţia asociată este verificată cu egalitate, adică numai dacă resursa respectivă este folosită integral de către soluţia optimă.  Costurile reduse asociate restricţiilor de neneg. asupra variabilelor deciz.: • Costurile reduse sunt folosite pentru verificarea optimalităţii soluţiilor problemei de programare liniară; • Costul redus este diferit de zero numai dacă variabila asociată are valoarea zero în soluţia optimă; • Costul redus arată cu cât s-ar înrăutăţi valoarea funcţiei obiectiv dacă valoarea variabilei asociate ar creşte de la 0 la 1.

Studiul de caz (carte Modelare economică)

O societate comercială specializată în realizarea de ţesături urmează să producă în luna următoare, pe baza studiilor de piaţă întreprinse, trei tipuri de stofe: Stofa1, Stofa2 şi Stofa3. Se doreşte stabilirea unui program optim de producţie în următoarele condiţii: 1. Maximizarea venitului dacă preţurile de vânzare sunt: 57 u.m./metru pentru Stofa1, 70 u.m./metru pentru Stofa2 şi 50 u.m./metru pentru Stofa3; 2. Obţinerea unei producţii fizice de cel puţin 8000 metri (pentru care există contracte ferme) şi cel mult 10000 metri; 3. Consumul din materia primă de import MI să nu depăşească 2400 kg, cunoscându-se consumurile specifice: 0,2 kg/metru Stofa1, 0,3 kg/metru Stofa2, 0,1 kg/metru Stofa3.

Studiul de caz (carte Modelare economică) 1. Modelul economico – matematic:  Variabilele: x1 = cantitatea din Stofa1, x2 = cantitatea din Stofa2, x3 = cantitatea din Stofa3  Funcţia obiectiv: max (57x1 + 70x2 + 50x3)  Restricţiile liniare: x1 + x2 + x3  8000 x1 + x2 + x3  10000 0,2x1 + 0,3x2 + 0,1x3  2400  Restricţiile referitoare la semnul variabilelor: x1  0, x2  0, x3  0

Studiul de caz (carte Modelare economică) 2. Rezolvarea cu WINQSB/LP-ILP: Decisi on Varia ble

Solution Value

Unit Cost or Profit c(j)

Total Contribu tion

Reduce Cost

Basis Status

at bound

1

X1

0

57.00

0

-3.00

2

X2

7000.00

70.00

490000.00

0

3

X3

3000.00

50.00

150000.00

0

Objective Function (Max)= Constrain Left Hand t Side

Allowa ble Min. c(j)

Allowa ble Max. c(j)

-M

60.00

basic

64.00

150.00

basic

44.00

70.00

640000.00

Directio n

Right Hand Side

Slack or Surplus

Shadow Price

Allowabl Min. RHS

Allowable Max. RHS

1

C1

10000.00

>=

8000.00

2000.0 0

0

-M

10000.00

2

C2

10000.00

<=

10000.00

0

40.00

8000.00

24000.00

4

C3

2400.00

<=

2400.00

0

100.00

1000.00

3000.00

2. FORMULAREA CAZULUI GENERAL DE POSTOPTIMIZARE     

După obţinerea soluţiei optime, înainte de implementarea practică a acesteia, decidentul poate efectua: Modificarea simultană a cantităţilor disponibile din diferite resurse duce la reoptimizarea în raport cu vectorul b sau la parametrizarea vectorului b al termenilor liberi; Modificarea simultană a mai multor costuri unitare (sau preţuri) duce la reoptimizarea în raport cu vectorul c sau la parametrizarea vectorului c al coeficienţilor funcţiei obiectiv; Modificarea consumurilor tehnologice determină modificarea unor elemente ale matricei coeficienţilor tehnologici şi duce la reoptimizarea în raport cu matricea A; Asimilarea de produse noi determină introducerea unor variabile noi şi duce la reoptimizarea în raport cu matricea A şi vectorul c; Apariţia unor noi resurse limitate determină adăugarea de noi restricţii şi duce la reoptimizarea în raport cu matricea A şi vectorul b. Aceste modificari se pot realiza prin: Analize de senzitivitate, Reoptimizări, Parametrizări

2. FORMULAREA CAZULUI GENERAL DE POSTOPTIMIZARE I. Analiza senzitivităţii soluţiei optime la variaţia coeficienţilor funcţiei

obiectiv

 Furnizează intervalul în care poate varia fiecare coeficient al funcţiei obiectiv,

astfel încât soluţia optimă primală (coloana Solution Value din WINQSB) să rămână neschimbată.  Intervalul asociat unui coeficient al funcţiei obiectiv pentru care soluţia problemei rămâne optimă se numeşte interval de optimalitate (Coloanele Allowable Min c(j) şi Allowable Max c(j) din WINQSB)  Cunoscând soluţia optimă şi intervalul de variaţie al unui coeficient al funcţiei obiectiv, în ipoteza că ceilalţi coeficienţi ai modelului nu se modifică, se poate determina variaţia corespunzătoare a funcţiei obiectiv.  Ex.: dacă preţul de vânzare pentru Stofa1 este mai mic de 60 u.m./metru atunci  x1 = cantitatea realizată din Stofa1 va rămâne zero. Creşterea de la 57u.m./metru la 58 u.m./metru a preţului de vânzare nu va genera venit suplimentar deoarece (58 – 57)*0 = 0. Dacă ceilalţi coeficienţi nu se modifică, dar se modifică de la 70 u.m./metru la 72 u.m./metru preţul asociat lui x2, deoarece 72 aparţine intervalului [64; 150], iar x2 = cantitatea optimă realizată din Stofa2 = 7000 metri, atunci venitul total va creşte cu (72-70)*7000 = 14000 u.m., adică de la 640 000 u.m. la 654000 u.m.

2. FORMULAREA CAZULUI GENERAL DE POSTOPTIMIZARE II. Analiza senzitivităţii soluţiei optime (primale si duale) la variaţia

termenilor liberi ai restricţiilor liniare  Furnizează intervalul în care poate varia fiecare termen liber, astfel încât soluţia optimă duală (vectorul preţurilor umbră) să nu se modifice.  Intervalul asociat unui termen liber pentru care preţul umbră asociat rămâne neschimbat se numeşte interval de admisibilitate pentru soluţia primalei. (Coloanele Allowable Min RHS şi Allowable Max RHS din WINQSB).  Cunoscând preţul umbră optim şi intervalul de variaţie al unui termen liber, în ipoteza că ceilalţi coeficienţi ai modelului nu se modifică, se poate determina variaţia corespunzătoare a funcţiei ob. 

Ex.: preţul umbră de 100 u.m. asociat restricţiei C3 este valabil pentru variaţia disponibilului b3 de materie primă de import MI între 1000 kg şi 3000 kg. Dacă disponibilul de resursă creşte de la cantitatea curentă 2400 kg la 2500 kg, atunci se va obţine un spor de venit = (2500 – 2400)*100 = 10000 u.m., adică venitul total va fi de (640000 + 10000) = 650000 u.m. De asemenea, dacă disponibilul de resursă scade de la cantitatea curentă 2400 kg la 2300 kg, atunci se va obţine o reducere de venit = (2300 – 2400)*100 = -10000 u.m.,  adică venitul total va fi de (640000 – 10000) = 630000 u.m.

2. FORMULAREA CAZULUI GENERAL DE POSTOPTIMIZARE Reoptimizarea în cazul modificării coeficienţilor cj din funcţia obiectiv, în afara intervalelor lor de optimalitate şi/sau modificarea termenilor liberi bi din partea dreaptă  a restricţiilor în afara intervalelor de admisibilitate şi/sau modificarea unor coeficienţi din matricea A.

Reoptimizarea pp. parcurgerea a două etape:  Verificarea optimalităţii soluţiei curente în noile condiţii;  Determinarea noii soluţii în cazul în care soluţia curentă nu îndeplineşte condiţiile de optimalitate.

2. FORMULAREA CAZULUI GENERAL DE POSTOPTIMIZARE Parametrizarea pentru analize de tipul „ce-ar fi dacă?” în cazul în care coeficienţii cj ai funcţiei obiectiv sau termenii liberi bi din partea dreaptă restricţiilor sunt funcţii liniare de un parametru (-, +).

Parametrizarea pp parcurgerea a două etape:  Rezolvarea problemei pentru o valoare fixată a parametrului;  Studiul senzitivităţii soluţiei la variaţia parametrului.

Studiul de caz

Ex: Parametrizarea coeficientului c1 asociat variabilei x1 în funcţia obiectiv (pret unitar al prod Stofa 1). Parametric Analysis for LP Sample Problem -- Objective Function Range

From Coeff. of X1

To Coeff. of X1

From OBJ Value

To OBJ Value

Slope

Leaving Variable

Entering Variable

1

57.00 60.00 640000

640000

0

X3

X1

2

60.00 70.00 640000

700000 6000

X2

Slack_ C3

3

70.00

M

700000

4

57.00

-M

640000

1000 0 640000 0 M

Studiul de caz

Valoarea functiei obiectiv

M 900000

800000

700000

700000 640000

640000

640000

600000 -M 30

40

50

57 60

70

Coeficientul lui x1 din functia obiectiv

80

M 90

Studiul de caz Ex: Parametrizarea termenului liber b3 asociat restricţiei C3 referitoare la materia primă de import. Parametric Analysis for LP Sample Problem - Right-Hand-Side From RHS of C3

To RHS of C3

From OBJ Value

To OBJ

Leaving Variable

Slope

Entering Variable

Value 1

2400

2

3000

3

2400

4

1000

3000.00

X3

Slack_C3

X2

Slack_C2

640000

700000

100

700000

700000

0

1000

640000

500000

100

800

500000

400000

500 Surplus_C

M

1 5

800 -Infinity Infeasible

Studiul de caz

4. MODELAREA STRUCTURII DE PRODUCŢIE ŞI A POSIBILITĂŢILOR DE DEZVOLTARE ALE UNEI ORGANIZAŢII (cazul în care variabilele sunt numere întregi)

 În cazul produselor indivizibile, pentru

determinarea structurii optime de fabricaţie se pot utiliza modele de programare liniară în numere întregi.  Domeniul de admisibilitate al modelelor liniare cu variabile în numere întregi este format dintr-un număr finit de puncte. Rezultă că numărul de variante sau alternative decizionale este finit.

4. MODELAREA STRUCTURII DE PRODUCŢIE ŞI A

POSIBILITĂŢILOR DE DEZVOLTARE ALE UNEI ORGANIZAŢII (cazul în care variabilele sunt numere întregi)  Rezolvarea modelelor liniare cu variabile întregi se   



efectuează cu metode de enumerare. Există două tipuri de metode de enumerare: explicită şi implicită. Din categoria metodelor de enumerare implicită face parte metoda „branch and bound” adică „ramifică şi mărgineşte”. Procesul iterativ de rezolvare a unei probleme printr-o metoda de tip „branch and bound” poate fi reprezentat printr-un arbore binar, în care fiecare nod are un singur ascendent şi doi descendenţi direcţi. Fiecare nod al arborelui binar reprezintă o problemă de programare liniară fără restricţiile ca variabilele să fie întregi. Problemele asociate nodurilor arborelui binar se rezolvă cu algoritmul simplex.

4. MODELAREA STRUCTURII DE PRODUCŢIE ŞI A POSIBILITĂŢILOR DE DEZVOLTARE ALE UNEI ORGANIZAŢII (cazul în care variabilele sunt numere întregi)  Un nod se ramifică dacă soluţia problemei este neîntreagă şi nu

există alt nod cu soluţie întreagă şi cu valoare mai bună a funcţiei obiectiv.  Pentru ramificarea unui nod, din soluţia problemei asociată acelui nod, se alege o componentă xj cu valoare neîntreagă, xj = . Pornind de la această variabilă se construiesc două probleme care generează două noduri descendente:  Problema pentru nodul stâng: prin adăugarea restricţiei xj  [], unde [] este parte întreagă a numărului   Problema pentru nodul drept: prin adăugarea restricţiei xj  [] +1.  Un nod nu se mai ramifică, adică devine margine dacă:  Are soluţie întreagă;  Nu are soluţie admisibilă;  Are soluţie neîntreagă, dar există alt nod cu soluţie întreagă şi o valoare mai bună a funcţiei obiectiv

Studiul de caz 5 (carte Modelare economică) - Programare Liniară în Numere Întregi Modelul economico matematic  Variabilele modelului

x1 = numărul de produse F43 x2 = numărul de produse F126 x3 = număr suplimentar de utilaje LM43 x4 = număr suplimentar de muncitori pentru grupa de montaj  Funcţia obiectiv Max (450x1 + 700x2 – 90x3 – 25x4)  Restricţii 5x1 + 2x2  24 1,5x1 + 5x2  24 + 8x3  1,5x1 + 5x2 - 8x3 24 5x1 + 6x2  36 + 8x4  5x1 + 6x2 - 8x4 36 x3  2 x4  4 x1  0 şi întreg, x2  0 şi întreg, x3  0 şi întreg, x4  0 şi întreg

Studiul de caz 5 (carte Modelare economică) - Programare Liniară în Numere Întregi Rezolvare cu WINQSB (7 iteratii), ex: Lower Bound

Upper Bound

Soluti on Value

Varia Le Type

Statu s

1 X1

2.00

M

2.00

Integer

Yes

No

2 X2

0

M

7.00

Integer

Yes

Integer

Yes

3 X3

0

M

1.75

Integer

No

Integer

No

4 X4

0

M

2.00

Integer

Yes

Decis on Varia le

Lower Bound

Upper Bound

Solutio n Value

Variabl e Type

Sta Us

1

X1

0

M

1.82

Integer

No

2

X2

0

M

7.45

Integer

3

X3

0

M

2.00

4

X4

0

M

2.23

Current OBJ(Maximize) = 5800.68 >= Non-integer

Decision Variab le

Lower Bound

Decis on Varia le

Current OBJ(Maximize) = 5592.50 >= Non-integer

ZL = -M

Upper Bound

Solution Value

Variable Type

Status

1

X1

2.00

M

2.00

Integer

Yes

2

X2

0

M

7.00

Integer

Yes

3

X3

2.00

M

2.00

Integer

Yes

4

X4

0

M

2.00

Integer

Yes

Current OBJ(Maximize)= 5570.00 >=

ZL = -M

ZL = -M New incumbent

Studiul de caz 5 (carte Modelare economică) - Programare Liniară în Numere Întregi Iteraţia 1 Z=5800,68 x1 = 1,82 x2 = 7,45 x3 = 2 x4 = 2,23

x1  1

x1  2 Iteraţia 2

Iteraţia 5

Z=5592,50 x1 = 2 x2 = 7 x3 = 1,75 x4 = 2

Z= 5612,50 x1 = 1 x2 = 7,7 x3 = 2 x4 = 1,9

x2  7 Iteraţia 7 Z=5175 x1 = 1 x2 = 7 x3 = 1,56 x4 = 1,38

x3  1

x2  8

Iteraţia 6 Z=5382,50 x1 = 0 x2 = 8 x3 = 2 x4 = 1,5 Soluţie neadmisibilă

Iteraţia 4 Z=4967,95 x1 = 2,55 x2 = 5,64 x3 = 1 x4 = 1,32

x3  2 Iteraţia 3 Z=5570 x1 = 2 x2 = 7 x3 = 2 x4 = 2

Soluţia optimă