curs5 modelare economica 2008 - nadia ciocoiu

CURS 6

MODELARE ECONOMICA,

LECTOR DR. Nadia Ciocoiu

MODELAREA STRUCTURII SORTIMENTALE. MODELAREA STRUCTURII SORTIMENTALE.

STUDIU DE SENZITIVITATESTUDIU DE SENZITIVITATE

1. 1. Optimizarea modelelor de tip liniarOptimizarea modelelor de tip liniar

2. 2. Formularea cazului general de Formularea cazului general de postoptimizarepostoptimizare

3. 3. Aspecte practice Aspecte practice îîn cazul modelării structurii den cazul modelării structurii de

fabricafabricaţţieie cucu variabilele continuevariabilele continue (carte (carte ModelareModelare economicaeconomica!!)!!)

4. 4. Modelarea structurii de producModelarea structurii de producţţie ie şşi a posibilităi a posibilităţţilor de ilor de

ale unei organizaale unei organizaţţii (cazul ii (cazul îîn care variabilele sunt numeren care variabilele sunt numere

îîntregi)ntregi)

1. 1. OPTIMIZAREA MODELELOR DE TIP LINIAROPTIMIZAREA 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:

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

jxc

1

1. 1. OPTIMIZAREA MODELELOR DE OPTIMIZAREA MODELELOR DE

TIP LINIARTIP LINIAR

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.

jx

n

1j

jc



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.



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.


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


2. Rezolvarea cu WINQSB/LP-ILP:

3000.001000.00100.0002400.00<=2400.00C34

24000.008000.0040.00010000.00<=10000.00C22

10000.00-M 02000.0

0

8000.00>=10000.00C11

Allowable

Max. RHS

Allowabl

Min. RHS

Shadow

Price

Slack

or

Surplus

Right Hand

Side

Directio

n

Left Hand

Side

Constrain

t

640000.00

Objective Function

(Max)=

70.0044.00basic0150000.0050.003000.00X33

150.0064.00basic0490000.0070.007000.00X22

60.00-M at bound-3.00057.000X11

Allowa

ble

Max.

c(j)

Allowa

ble

Min.

c(j)

Basis

Status

Reduce

Cost

Total

Contribu

tion

Unit

Cost

or

Profit

c(j)

Solution

Value

Decisi

on

Varia

ble

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


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.


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.


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

0640000640000-M57.004

1000

0

M700000M70.003

Slack_

C3

X2600070000064000070.0060.002

X1X3064000064000060.0057.001

Entering

Variable

Leaving

Variable

SlopeTo

OBJ Value

From

OBJ Value

To

Coeff.

of X1

From

Coeff.

of X1

Range

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

640000

640000

700000

640000

600000

700000

800000

900000

30 40 50 60 70 80 90

Coeficientul lui x1 din functia obiectiv

Valoarea functiei obiectiv

M

-M

57 M

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

Infeasible-Infinity8005

Surplus_C

1

50040000050000080010004

Slack_C2X2100500000640000100024003

0700000700000M30002

Slack_C3X31007000006400003000.0024001

Entering

Variable

Leaving

VariableSlope

To

OBJ

Value

From

OBJ Value

To RHS

of C3

From

RHS of C3

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.




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.




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



Rezolvare cu WINQSB (7 iteratii), ex:

Current OBJ(Maximize) = 5800.68 >= ZL = -M

Non-integer

NoInteger2.23M0X44

YesInteger2.00M0X33

NoInteger7.45M0X22

NoInteger1.82M0X11

Sta

Us

Variabl

e

Type

Solutio

n

Value

Upper

Bound

Lower

Bound

Decis

on

Varia

le

Current OBJ(Maximize) = 5592.50 >= ZL = -M

Non-integer

YesInteger2.00M0X44

NoInteger1.75M0X33

YesInteger7.00M0X22

YesInteger2.00M2.00X11

Statu

s

Varia

Le Type

Soluti

on

Value

Upper

Bound

Lower

Bound

Decis

on

Varia

le

Current OBJ(Maximize)= 5570.00 >= ZL = -M New incumbent

YesInteger2.00M0X44


YesInteger7.00M0X22


StatusVariable

Type

Solution

Value

Upper

Bound

Lower

Bound

Decision

Variab

le



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 3Iteraţia 4

Iteraţia 5

Iteraţia 7 Iteraţia 6

Soluţia optimă

curs5 modelare economica 2008 - nadia ciocoiu

Documents