curs9&10 modelare economica 2013_nadia ciocoiu

44
CURS 9&10 MODELARE ECONOMICA, CONF. DR. Nadia Ciocoiu MODELE DE ALOCARE OPTIMALA A UNOR RESURSE LIMITATE 1. Optimizarea modelelor de programare de tip liniar (cu variabile numere reale/continue) 2. Formularea cazului general de postoptimizare 3. Alte aplicații practice ale programării liniare 4. Optimizarea modelelor de programare de tip liniar (cu variabile numere intregi) 5. Programarea multidimensionala/multiobiectiv 6. Proceduri de fuzzyficare a problemelor de programare liniară

Upload: miruna-mosoia

Post on 01-Dec-2015

17 views

Category:

Documents


1 download

DESCRIPTION

Modelare economica- Facultatea de Management economic, 2013

TRANSCRIPT

Page 1: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

CURS 9&10

MODELARE ECONOMICA,

CONF. DR. Nadia Ciocoiu MODELE DE ALOCARE OPTIMALA A UNOR

RESURSE LIMITATE

1. Optimizarea modelelor de programare de tip liniar (cu variabile numere reale/continue)

2. Formularea cazului general de postoptimizare

3. Alte aplicații practice ale programării liniare

4. Optimizarea modelelor de programare de tip liniar (cu variabile numere intregi)

5. Programarea multidimensionala/multiobiectiv

6. Proceduri de fuzzyficare a problemelor de programare liniară

Page 2: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

1. OPTIMIZAREA MODELELOR DE PROGRAMARE

TIP LINIAR (cu variabile reale/continue)

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:

f(X) =

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

j

n

j

j xc1

Page 3: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

1. OPTIMIZAREA MODELELOR DE PROGRAMARE

DE TIP LINIAR (cu variabile reale/continue)

Forma generală a modelului de programare liniară este:

max (sau min) f(X) =

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.

jxn

1jjc

Page 4: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

1. OPTIMIZAREA MODELELOR DE PROGRAMARE

TIP LINIAR (cu variabile reale/continue)

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:

WINQSB/Lp – ilp,

LINDO,

SOLVER care este un instrument add-ins al Excel.

Page 5: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

1. OPTIMIZAREA MODELELOR DE PROGRAMARE

DE TIP LINIAR (cu variabile reale/continue)

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 decizionale:

• 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.

Page 6: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

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 4 ptr. Seminar ( din carte RSC, LF; HD, CN, Modelare economică, Ed.

ASE, 2009, p. 100): Determinarea sructurii optime de productie pentru variabile

numere reale

Page 7: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

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 4 ptr. Seminar (din carte RSC, LF; HD, CN, Modelare economică, Ed.

ASE, 2009, p. 100): Determinarea sructurii optime de productie pentru variabile

numere reale

Page 8: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Studiul de caz 4 (carte Modelare economică, Ed. ASE, 2009, p. 100): Determinarea

structurii optime de productie pentru variabile numere reale

2. Rezolvarea cu WINQSB/LP-ILP:

Decisi

on

Varia

ble

Solution

Value

Unit

Cost

or

Profit

c(j)

Total

Contribu

tion

Redu

ced

Cost

Basis

Status

Allowa

ble

Min.

c(j)

Allowa

ble

Max.

c(j)

1 X1 0 57 0 -3.00 At

bound -M 60

2 X2 7000 70 490000 0 basic 64 150

3 X3 3000 50 150000 0 basic 44 70

Objective Function

(Max)= 640000

Constrai

nt

Left Hand

Side

Directio

n

Right Hand

Side

Slack

or

Surplus

Shado

w

Price

Allowabl

Min. RHS

Allowable

Max. RHS

1 C1 10000 >= 8000 2000 0 -M 10000

2 C2 10000 <= 10000 0 40 8000 24000

4 C3 2400 <= 2400 0 100 1000 3000

Interval de

optimalitate

Inerval de

admisibilitate

Page 9: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

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

Page 10: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

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.

Page 11: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

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.

Page 12: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

2. FORMULAREA CAZULUI GENERAL DE

POSTOPTIMIZARE

III.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.

Page 13: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

2. FORMULAREA CAZULUI GENERAL DE

POSTOPTIMIZARE

IV. 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.

Page 14: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

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 M 1000

0

4 57.00 -M 640000 640000 0

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

Studiul de caz 4 ptr. Seminar (carte RSC, LF; HD, CN, Modelare economică, Ed. ASE,

2009, p. 100): Determinarea sructurii optime de productie pentru variabile numere reale

Page 15: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

640000640000

700000

640000

600000

700000

800000

900000

30 40 50 60 70 80 90

Coeficientul lui x1 din functia obiectiv

Valo

are

a f

unctiei obie

ctiv

M

-M 57 M

Studiul de caz 4 ptr. Seminar (carte RSC, LF; HD, CN, Modelare economică, Ed. ASE,

2009, p. 100): Determinarea sructurii optime de productie pentru variabile numere reale

Page 16: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

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

Value

Slope

Leaving

Variable

Entering

Variable

1 2400 3000.00 640000 700000 100 X3 Slack_C3

2 3000 M 700000 700000 0

3 2400 1000 640000 500000 100 X2 Slack_C2

4 1000 800 500000 400000 500

Surplus_C

1

5 800 -Infinity Infeasible

Studiul de caz 4 ptr. Seminar (carte RSC, LF; HD, CN, Modelare economică, Ed. ASE,

2009, p. 100): Determinarea sructurii optime de productie pentru variabile numere reale

Page 17: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Studiul de caz 4 ptr. Seminar (carte RSC, LF; HD, CN, Modelare economică, Ed. ASE,

2009, p. 100): Determinarea sructurii optime de productie pentru variabile numere reale

Page 18: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

3. ALTE APLICAȚII PRACTICE ALE PROGRAMARII LINIARE

MODELE PENTRU PROBLEME DE AMESTEC Un produs final P are în componenţă sa produsele care trebuie amestecate.

Produsul P are caracteristici calitative impuse şi exprimate prin m indicatori I1, I2, ... Im de mărime bi (i = 1, ..., m);

aij – mărimea indicatorilor pentru fiecare produs (i = 1, ..., m); (j = 1, ..., n);

Eh (h = 1, ..., r) – indicatori de eficienţă ai fiecărui produs cu mărimile Chj (h = 1, ..., r); (j = 1, ..., n), care, după caz, vor fi maximizaţi sau minimizaţi.

Modelul matematic general al problemei de amestec:

Exemplu: care să fie cantitatea din fiecare ingredient

ce formează intră în compoziția unui produs (variabilele),

astfel încât să se obțină un produs cu cost minim

(functia obiectiv), în condițiile respectării unor anumite

conținuturi în substanțe nutritive (restricțiile).

ij

n

1jij bxa

0x j

j

n

1jhjxCopt

n,...,1jPj

Page 19: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

3. ALTE APLICAȚII PRACTICE ALE PROGRAMARII

LINIARE

MODELE DE CROIRE

Modelul general al problemei de croire:

Notaţii: aij- număr de piese/bucăţi de tip i care se debitează/taie/

croiesc conform soluţiei (tiparului) j;

cj – costul sau cantitatea deşeurilor rămase conform soluţiei j;

Ni - numărul de piese/bucăţi necesare de tip i;

Xj - numărul de suprafeţe debitate/croite conform soluţiei j.

ijij Nxa

0x j

jj

jxcmin

Page 20: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Î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. OPTIMIZAREA MODELELOR DE PROGRAMARE

DE TIP LINIAR (cu variabile numere întregi)

Page 21: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

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. OPTIMIZAREA MODELELOR DE PROGRAMARE

DE TIP LINIAR (cu variabile numere întregi)

Page 22: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

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 NUse 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

4. OPTIMIZAREA MODELELOR DE PROGRAMARE

DE TIP LINIAR (cu variabile numere întregi)

Page 23: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Exemplu practic: Modelarea structurii de productie si a posibilitatilor de dezvoltare a

unei organizatii, cu variabile numere intre

Studiul de caz 5 (carte Modelare economică, Ed. ASE, 2009, p. 124)

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

Page 24: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Exemplu practic: Modelarea structurii de productie si a posibilitatilor de dezvoltare a unei

organizatii, cu variabile numere intregi

Rezolvare cu WINQSB (7 iteratii), ex:

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 No

3 X3 0 M 2.00 Integer Yes

4 X4 0 M 2.23 Integer No

Current OBJ(Maximize) = 5800.68

>= ZL = -M Non-integer

Decis

on

Varia

le

Lower

Bound

Upper

Bound

Soluti

on

Value

Varia

Le Type

Statu

s

1 X1 2.00 M 2.00 Integer Yes

2 X2 0 M 7.00 Integer Yes

3 X3 0 M 1.75 Integer No

4 X4 0 M 2.00 Integer Yes

Current OBJ(Maximize) = 5592.50 >=

ZL = -M Non-integer

Decisio

Variable

Lower

Bound

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 New incumbent

ITERATIA 1 ITERATIA 2

ITERATIA 3

Page 25: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Exemplu practic: Modelarea structurii de productie si a posibilitatilor de dezvoltare a unei

organizatii, cu variabile numere intregi

Z=5800,68

x1 = 1,82

x2 = 7,45

x3 = 2 x4 = 2,23

Z= 5612,50

x1 = 1

x2 = 7,7

x3 = 2

x4 = 1,9

Z=5592,50

x1 = 2

x2 = 7

x3 = 1,75

x4 = 2

x1 1 x1 2

x3 1 x3 2

Z=4967,95

x1 = 2,55

x2 = 5,64

x3 = 1

x4 = 1,32

Z=5570

x1 = 2

x2 = 7

x3 = 2

x4 = 2

x2 7 x2 8

Z=5175

x1 = 1

x2 = 7

x3 = 1,56

x4 = 1,38

Z=5382,50

x1 = 0

x2 = 8

x3 = 2

x4 = 1,5

Soluţie neadmisibilă

Iteraţia 1

Iteraţia 2

Iteraţia 3 Iteraţia 4

Iteraţia 5

Iteraţia 7 Iteraţia 6

Soluţia optimă

Page 26: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

5. PROGRAMAREA LINIARĂ

MULTIDIMENSIONALĂ/ MULTIOBIECTIV

Forma generală a problemei de programare liniară cu mai multe funcţii

obiectiv:

Optimum F(x) = Cx

cu restricţiile:

Ax b

x 0,

unde: F(x) = vector coloană cu r componente f1(x), f2(x),...,fr(x), care reprezintă funcţiile obiectiv prin care sunt exprimate criteriile de evaluare a variantelor decizionale.

Metode:

Metoda maximizării unei funcţii sinteză de utilitate

Metoda programarii scop

Page 27: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

METODA MAXIMIZĂRII UNEI FUNCŢII SINTEZĂ DE UTILITATE

Pentru determinarea unei soluţii care realizează cel mai bun compromis pentru toate funcţiile se va construi o funcţie sinteză a tuturor funcţiilor obiectiv numită funcţie sinteză de utilitate.

Funcţia sinteză de utilitate se obţine prin transformarea funcţiilor obiectiv f1(x), f2(x), ..., fr(x), cu semnificaţii economice concrete, în funcţii de utilitate care pot fi însumate.

Prin maximizarea funcţiei sinteză de utilitate în raport cu restricţiile problemei se obţine soluţia de compromis cu utilitate maximă.

Algoritmul de calcul:

Pasul 1. Se obţin valorile optimiste şi valorile pesimiste ale tuturor funcţiilor obiectiv.

Pasul 2. Pe baza axiomelor von Neumann – Morgenstern, se determină utilităţile valorilor optimiste O1, O2, ..., Or şi pesimiste P1, P2, ..., Pr ale functiilor obiectiv.

Pasul 3. Se construiesc funcţiile de utilitate de forma (αhfh(x) + βh)

Pasul 4. Se rezolvă problema de programare liniară care maximizeaza funcţia sinteză de utilitate.

Pentru înțelegerea modelului vezi exemplul practic din cartea Rațiu-Suciu C, Luban

F, Hincu D, Ciocoiu N, Modelare Economică, Ed ASE, 2009, St caz 10, p. 165-167

5. PROGRAMAREA LINIARĂ

MULTIDIMENSIONALĂ/ MULTIOBIECTIV

Page 28: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

METODA PROGRAMARII SCOP

PS - o metodă de rezolvare a problemei de programare liniară cu mai multe funcţii obiectiv.

Metoda PS a fost propusă şi dezvoltată sub denumirea de "Goal Programming" de A. Charnes şi W. Cooper.

Obiectivul programării scop: găsirea unei soluţii care verifică restricţiile Ax b, x0 şi care conduce la abateri cât mai mici faţă de scopurile propuse prin funcţiile obiectiv.

Ideea de bază a metodei constă în transformarea tuturor funcţiilor obiectiv în „restricţii scop” prin:

– specificarea pentru fiecare funcţie obiectiv a unui nivel de aspiraţie sau scop;

– definirea pentru fiecare scop a unei perechi de variabile de abatere sau deviaţie:

• deviaţia în plus faţă de scopul propus;

• deviaţia în minus faţă de scopul propus.

Nivelurile de aspiraţie sau scopurile pot fi:

– stabilite de decident;

– obţinute prin optimizarea problemei de programare liniară în raport cu fiecare funcţie obiectiv.

5. PROGRAMAREA LINIARĂ

MULTIDIMENSIONALĂ/ MULTIOBIECTIV

Page 29: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

METODA PROGRAMARII SCOP

Funcţia care minimizează deviaţiile faţă de nivelurile de aspiraţie sau scopurile propuse se numeşte „funcţie scop”.

Forma generală a unui model PS:

minimizează una sau mai multe funcţii scop de forma:

supusă la restricţiile:

Ax b

x 0

şi restricţiile „scop”: fi(x) = Vi + d+i - d

-i => fi(x) - d+

i+ d-i = Vi, i = 1,...,N

d+i 0, d-

i 0, i = 1,...,N

unde: •d+

i si d-i deviaţia în plus/în minus faţă de val. prestabilită pentru funcţia obiectiv i;

•πi şi ρi sunt coeficienţi ai deviaţiilor care fac posibilă însumarea lor; •fi(x) - funcţia obiectiv i; •Vi - valoarea prestabilită (nivelul de aspiraţie) pentru funcţia obiectiv i; •x - vector coloană cu n componente x1, x2,...,xn care reprezintă variabilele decizionale ale problemei. •Ax b: restricţiile care definesc domeniul de admisibilitate al problemei pentru variabilele decizionale x1, x2,...,xn.

)(1

ii

N

i

ii dd

5. PROGRAMAREA LINIARĂ

MULTIDIMENSIONALĂ/ MULTIOBIECTIV

Page 30: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

METODA PROGRAMARII SCOP

Elementul cheie - specificarea funcţiei obiectiv, adică definirea coeficienţilor πi şi ρi pentru deviaţiile di+ şi di-.

Dacă deviaţiile se măsoară cu unităţi de măsură diferite, atunci este necesară definirea unor costuri de penalizare a deviaţiilor astfel încât să se poată minimiza suma totală a costurilor de penalizare generate de diferite deviaţii.

Funcţiilor scop li se pot asocia diferite priorităţi. În acest caz se poate proceda astfel:

– Se ordonează descrescător scopurile şi se stabileşte prioritatea de satisfacere a fiecărui scop:

P1 P2 … Pn... unde înseamnă "mult mai mare".

– Numărul priorităţilor este mai mic sau cel mult egal cu numărul funcţiilor obiectiv, iar numărul funcţiilor scop este egal cu numărul priorităţilor acordate.

– Ordonarea prin priorităţi este absolută, astfel că scopul cu prioritatea P2 nu va fi niciodată atins înainte ca scopul cu prioritatea P1 să fie realizat cu abaterea cea mai mică faţă de nivelul de aspiraţie propus.

În acest caz, prin metoda programării scop se rezolvă succesiv un număr de probleme egal cu numărul priorităţilor.

Rezolvarea modelelor de PS: WINQSB/ Gp – igp.

5. PROGRAMAREA LINIARĂ

MULTIDIMENSIONALĂ/ MULTIOBIECTIV

Page 31: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Studiul de caz 10 ptr. seminar (carte RSC, LF, HD, CN, Modelare Economica, Ed

ASE, 2009, p.165 ): Rezolvarea cu metoda programarii scop

Pasul I: scrierea modelului econ. – matematic cu mai multe functii obiectiv:

Variabilele:

x1 = cantitatea din Pcs1 x2 = cantitatea din Pcs2 x3 = cantitatea din Pcs3

Funcţiile obiectiv:

Maximizarea venitului total

(max) f1(x) = 60x1 + 120x2 + 90x3

Minimizarea timpului necesar de lucru

(min) f2(x) = 15x1 + 10x2 + 19x3

Minimizarea consumului total din materia primă de import

(min) f3(x) = 0,2x1 + 0,6x2 + 0,4x3

Restricţii:

referitoare la materialul Mat1:

C1: 0,6x1 + 0,6x2 + 0,2x3 10

referitoare la cantităţile contractate:

C2: 1x1 + 1x2 12

C3: 1x3 5

Restricţiile de nenegativitate:

x1 0, x2 0, x3 0,

Cele 3 fct obiectiv

se transforma in

Restrictii Scop

Page 32: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Pasul 2: transformarea in modelul economico – matematic de PS Funcţiile scop:

Scopul cu prioritate 1: minimizarea deviaţiei în plus Mimpsupl faţă de consumul minim de

materie primă de import

Min G1: 1Mimpsupl

Scopul cu prioritate 2: minimizarea deviaţiei în minus Venitm faţă de venitul maxim

Min G2: 1Venitm

Scopul cu prioritate 3: minimizarea deviaţiei în plus Timpsupl faţă de timpul de lucru necesar minim

Min G3: 1Timpsupl

Restricţiile pentru consumuri materiale şi pentru cerere:

C1: 0,6x1 + 0,6x2 + 0,2x3 10

C2: 1x1 + 1x2 12

C3: 1x3 5

Restricţiile scop:

C4: 60x1 + 120x2 + 90x3 – Venitsupl + Venitm = 2700

C5: 15x1 + 10x2 + 19x3 – Timpsupl + Timpm = 215

C6: 0,2x1 + 0,6x2 + 0,4x3 – Mimpsupl + Mimpm = 4,4

Restricţiile de nenegativitate:

x1 0, x2 0, x3 0,

Venitsupl 0, Venitm 0,

Timpsupl 0, Timpm 0,

Mimpsupl 0. Mimpm 0

Niveluri de

aspiratie

Variabile de

abatere/deviatie

Studiul de caz 10 ptr. seminar (carte RSC, LF, HD, CN, Modelare Economica, Ed

ASE, 2009, p.165 ): Rezolvarea cu metoda programarii scop

Page 33: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Pasul 3: Rezolvarea modelului cu WINQSB/Gp-igp

Decision

Variable

Solution

Value

Basis

Status

Reduced

Cost

Goal 1

Reduced

Cost

Goal 2

Reduced

Cost

Goal 3

1 X1 12 basic 0 0 0

2 X2 0 at bound 0 60 -35

3 X3 5 basic 0 0 0

4 Venitsupl 0 at bound 0 1 0

5 Venitm 1480 basic 0 0 0

6 Timpsupl 60 basic 0 0 0

7 Timpm 0 at bound 0 0 1

8 Mimpsupl 0 at bound 1 -300 75

9 Mimpm 0 at bound 0 300 -75

Goal 1: Minimize G1 = 0

Goal 2: Minimize G2 = 1480

Goal 3: Minimize G3 = 60

Studiul de caz 10 ptr. seminar (carte RSC, LF, HD, CN, Modelare Economica, Ed

ASE, 2009, p.165 ): Rezolvarea cu metoda programarii scop

Page 34: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Sensitivity Analysis of the Right-Hand-Sides for Studiul de caz 10

Constraint

Right

Hand

Side

Allowabl

e

Min.RHS

Allowable

Max.RHS Shadow

Price

Goal 1

Shadow

Price

Goal 2

Shadow

Price

Goal 3

1 Material1 <= 10 8.2 M 0 0 0

2 Cerere Pcs1+Pcs2 >= 12 -M 12 0 0 0

3 Cerere PCs3 >= 5 3.2 5 0 20 -11

4 Venit

prioritate 2

= 2700 1220 M 0 1 0

5 Timp

prioritate 3

= 215 -M 275 0 0 -1

6 Mimport

prioritate 1

= 4.4 4.4 5 0 -300 75

2 conflicte: 1. intre scopul de prioritate 1 si cel de prioritate 2 (cu valoarea -300)

2. Intre scopul de prioritate 1 si cel de prioritate 3 (cu valoarea 75)

Studiul de caz 10 ptr. seminar (carte RSC, LF, HD, CN, Modelare Economica, Ed

ASE, 2009, p.165 ): Rezolvarea cu metoda programarii scop

Page 35: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Pasul 4: Analiza rezultatelor:

1. Citirea solutiei (solution value)

2. Interpretarea costului redus

3. Interpretarea pretului umbra

4. Identificarea si analiza conflictelor dintre

scopuri

Studiul de caz 10 ptr. seminar (carte RSC, LF, HD, CN, Modelare Economica, Ed

ASE, 2009, p.165 ): Rezolvarea cu metoda programarii scop

Page 36: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

6. PROCEDURI DE FUZZYFICARE A

PROBLEMELOR DE PROGRAMARE LINIARĂ

Se porneşte de la forma generală a problemei de programare liniară cu mai

multe funcţii obiectiv descrisă la punctul 5, unde, pentru simplificarea

prezentării, restricţiile s-au împărţit în două grupe: de tip ≤, indexate superior

cu 1 şi de tip ≥, indexate superior cu 2.

Optim F(x) = Cx

Cu restricţiile:

A1x ≤ b1

A2x ≥ b2

x ≥ 0

Pentru acest model, mulţimea soluţiilor admisibile D este definită prin restricţiile

A1x ≤ b1, A2x ≥ b2, x ≥ 0.

Ideea de bază a fuzzyficării constă în asocierea unei mulţimi vagi sau fuzzy

valorilor fiecărei funcţii obiectiv şi valorilor fiecărei restricţii.

O mulţime vagă sau fuzzy este astfel definită încât un element poate nu numai să

îi aparţină sau să nu îi aparţină, ci să se caracterizeze şi printr-o apartenenţă

intermediară.

Page 37: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

6. PROCEDURI DE FUZZYFICARE A

PROBLEMELOR DE PROGRAMARE LINIARĂ

Fie E = mulţimea tuturor vectorilor realizabili de producţie,

Si = mulţime vagă inclusă în E (de exemplu mulţimea vectorilor de producţie

care satisfac „aproximativ” restricţia i) şi x = (x1, x2, ..., xn) un vector de

producţie din E, x E.

În general, o mulţime vagă Si E este caracterizată atât prin mulţimea

elementelor sale x, cât şi prin funcţiile lor de apartenenţă µSi(x). Aceste funcţii

pun în corespondenţă fiecare element x E cu un număr real din intervalul

[0, 1]. Acest număr indică gradul de apartenenţă al elementului x la mulţimea

vagă Si. Prin urmare, o mulţime vagă Si E este definită cu ajutorul

perechilor (x, µSi(x)), pentru x E şi µSi(x): E [0, 1].

În cazul fuzzyficării modelelor de programare liniară, este important de

reţinut faptul că deşi, exprimarea vagă se poate referi numai la restricţii,

funcţiile obiectiv devin de asemenea fuzzy din cauza restricţiilor fuzzy.

Modelul fuzzy va avea ca funcţie obiectiv maximizarea gradului de satisfacere

simultană de către soluţia x a restricţiilor şi a funcţiilor obiectiv.

Pentru înțelegere se prezintă exemplul practic următor.

Page 38: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

În tabelul urmator sunt preluate rezultatele obţinute prin rezolvarea diferitelor

modele în vederea stabilirii programului de producţie pentru produsele Pcs1, Pcs2 şi

Pcs3. A fost exclusă soluţia obţinută prin rezolvarea modelului min f3(x), pentru x

D deoarece este dominată de celelalte soluţii.

Exemplu practic: Studiul de caz 10 (carte RSC, LF, HD, CN, Modelare Economica,

Ed ASE, 2009, p.165 ), Rezolvarea cu model fuzzy

Criteriile Tip

criteriu

max f1(x)

x D

min f2(x)

x D

Maximizarea

funcţiei sinteză

de utilitate

Programarea scop

f1(x) = venitul

total (u.m.) max 2700* 1890 2250 1220

f2(x) = timpul

necesar de lucru

(ore)

min 386 215* 245 275

f3(x) =consumul

de materie primă

de import (tone)

min 12,8 9,2 11 4,4*

Page 39: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Decidentul dispune de patru programe de producţie pentru perioada următoare, dar nici

unul dintre ele nu realizează toate obiectivele propuse.

De aceea, decidentul doreşte să determine programul de producţie care să maximizeze

gradul de satisfacere simultană a celor trei obiective propuse: maximizarea venitului total,

minimizarea timpului necesar de lucru, minimizarea consumului total de materie primă de import.

Pentru rezolvarea problemei este necesară fuzzyficarea funcţiilor obiectiv ale modelului de

programare liniară multicriterială.

Pasul 1. Construirea modelului de programare liniară multicriterială.

Vectorul programului de producţie x pentru luna următoare este format din componentele:

x1 = cantitatea din Pcs1, x2 = cantitatea din Pcs2, x3 = cantitatea din Pcs3

Funcţiile obiectiv:

Maximizarea venitului total

(max) f1(x) = 60x1 + 120x2 + 90x3

Minimizarea timpului necesar de lucru

(min) f2(x) = 15x1 + 10x2 + 19x3

Minimizarea consumului total din materia primă de import

(min) f3(x) = 0,2x1 + 0,6x2 + 0,4x3

Exemplu practic: Studiul de caz 10 (carte RSC, LF, HD, CN, Modelare Economica,

Ed ASE, 2009, p.165 ), Rezolvarea cu model fuzzy

Page 40: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Restricţia referitoare la materialul Mat1:

0,6x1 + 0,6x2 + 0,2x3 10

Restricţiile referitoare la cantităţile contractate:

1x1 + 1x2 12

1x3 5

Restricţiile de nenegativitate:

x1 0, x2 0, x3 0,

Pasul 2. Specificarea nivelurilor de aspiraţie pentru valorile funcţiilor obiectiv şi a

toleranţelor pozitive a admise faţă de aceste niveluri de aspiraţie.

Funcţia obiectiv Nivelul de aspiraţie Toleranţa

max f1(x) = 60x1 + 120x2 + 90x3 v1 = 2700 u.m. q1 = 2700-1220 = 1480 u.m.

min f2(x) = 15x1 + 10x2 + 19x3 v2 = 215 ore q2 = 386 – 215 = 171 ore

min f3(x) = 0,2x1 + 0,6x2 + 0,4x3 v3 = 4,4 tone q3 = 12,8 – 4,4 = 8,4 tone

Exemplu practic: Studiul de caz 10 (carte RSC, LF, HD, CN, Modelare Economica,

Ed ASE, 2009, p.165 ), Rezolvarea cu model fuzzy

Page 41: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Pasul 3. Fuzzyficarea funcţiilor obiectiv şi construirea funcţiilor de

apartenenţă asociate.

Funcţia obiectiv

fuzzy

Restricţia asociată pentru

definirea

lui Sh

Funcţia de apartenenţă

μSh(x)

f1(x) f1(x) v1 - q1

μS1(x) =

pentru 1220 f1(x) 2700

f2(x) f2(x) v2 + q2

μS2(x) =

pentru 215 f2(x) 386

f3(x) f3(x) v3 +q3

μS3(x)=

pentru 4,4 f3(x) 12,8

xa~m 1480

12203x902x1201x60

ni~

m 171

)3x192x101x15(386

ni~

m 4,8

)3x4,02x6,01x2,0(8,12

Exemplu practic: Studiul de caz 10 (carte RSC, LF, HD, CN, Modelare Economica,

Ed ASE, 2009, p.165 ), Rezolvarea cu model fuzzy

Page 42: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Pasul 4. Se introduce variabila cu valori în [0, 1] şi se construiesc

restricţiile μSh(x) , pentru h = 1, 2, 3.

μS1(x)

sau

60x1 + 120x2 + 90x3 – 1480 1220

μS2(x)

sau

15x1 + 10x2 + 19x3 + 171 386

μS3(x)

sau

0,2x1 + 0,6x2 + 0,4x3 + 8,4 12,8

Exemplu practic: Studiul de caz 10 (carte RSC, LF, HD, CN, Modelare Economica,

Ed ASE, 2009, p.165 ), Rezolvarea cu model fuzzy

Page 43: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Pasul 5. Se construieşte şi se rezolvă modelul pentru determinarea programului de

producţie care să maximizeze gradul de satisfacere simultană a celor trei obiective propuse.

Max 1

Cu următoarele restricţii:

Restricţiile obţinute prin fuzzyficare

60x1 + 120x2 + 90x3 – 1480 1220

15x1 + 10x2 + 19x3 + 171 386

0,2x1 + 0,6x2 + 0,4x3 + 8,4 12,8

Restricţiile iniţiale nevagi

0,6x1 + 0,6x2 + 0,2x3 10

1x1 + 1x2 12

1x3 5

1 1

Restricţiile de nenegativitate:

x1 0, x2 0, x3 0, 0

S-a obţinut un model de programare liniară cu o singură funcţie obiectiv, patru variabile, şapte

restricţii.

Exemplu practic: Studiul de caz 10 (carte RSC, LF, HD, CN, Modelare Economica,

Ed ASE, 2009, p.165 ), Rezolvarea cu model fuzzy

Page 44: Curs9&10 Modelare Economica 2013_Nadia Ciocoiu

Conform acestei soluţii, dacă în perioada următoare se vor realiza

6,517 tone produs Pcs1, 7,945 tone produs Pcs2 şi 6,613 tone produs

Pcs3, gradul de satisfacere a nivelului de aspiraţie pentru fiecare

obiectiv propus va fi de 0,486.

WINQSB/Lp-ilp/ Solution Summary for Studiul de caz fuzzy

Decision

Variable

Solution

Value

Unit Cost or

Profit C(j)

Total

Contribution

Reduced

Cost

Basis

Status

1 X1 6.517 0 0 0 basic

2 X2 7.945 0 0 0 basic

3 X3 6.613 0 0 0 basic

4 alfa 0.486 1.000 0.486 0 basic

Objective Function (Max.)= 0.486

Exemplu practic: Studiul de caz 10 (carte RSC, LF, HD, CN, Modelare Economica,

Ed ASE, 2009, p.165 ), Rezolvarea cu model fuzzy