bazele cercetarilor operationale curs 6

7/24/2019 Bazele cercetarilor operationale CURS 6

1/31

1

TEMA III

OPTIMIZAREA PROCESELOR ECONOMICE

UTILIZND PROGRAMAREA LINIAR

CURS 6-7. Introduceren programarea liniar. Proprieti ale programelorliniare, forme speciale ale PPL

1 Programarea matematic- Programarea liniar2 Exemple de probleme de modelare economico matematic/ SEMINAR

3 Forma general a unui program liniar4 Studiul unui program liniar n dou variabile/ SEMINAR5 Concluzii generale rezultate din rezolvarea grafic a programelor liniare

n dou variabile/ SEMINAR

6 Forme speciale de prezentare a programelor liniare

Probleme propuse


2/31

2

1 Programarea matematic- Programarea liniar

Am afirmat despre CO c are ca obiect de studiu problemele de optimizare, rezultate dinmodelarea matematic a unor fenomene i procese din domeniul economic, tiinific, tehnic saumilitar.Vom prezenta un exemplu simplu, de problem de optimizare, care va constitui suportul aplicativ aldezvoltrilor teoretice ulterioare.

Exemplul de problem de optimizare.O companie IT import componente electronice i asambleaz dou tipuri de computere PC1

i PC2. Vnzarea unui PC1 (respectiv PC2 ) aduce un profit de $50(respectiv $40). Un PC1are nevoie

de 3 ore pentru asamblare iar un PC2 necesit 5 ore. Pentru urmtoarea sptmn sunt disponibile 150 ore pentru asamblare. Compania are n stoc numai 20 monitoare PC2; altfel spus, n urmtoareasptmn ea nu poate produce mai mult de 20 uniti PC2. Pentru depozitare un PC1 are nevoie de8u.a. (uniti de arie) iar un PC2 de 5u.a. Spaiul disponibil pentru depozitarea produciei dinurmtoarea sptmn nsumeaz 300 u.a. Cererea este suficient de mare pentru ca ntreaga producies fie vndut. Conducerea companiei este interesat n elaborarea unui program de producie pentru urmtoarea sptmn care s-i aduc un profit maxim.

Ti pul de problem : elaborarea unui program de producie , pe o anumit perioad, n condiiileexistenei unui disponibil limitat de resurse .Soluiile problemei : sunt diversele programe de producie realizabile din resursele limitate

specificate: timpul disponibil pentru asamblare, monitoarele PC2i spaiulde depozitare.Un program de producie este definit prin dou valori numerice: numrul de uniti PC1, respectivnumrul de uniti PC2ce vor fi produse n urmtoarea sptmn.Programele admisibile sunt comparate ntre ele prin intermediul profitului pe care l-ar aduce n cazde realizare.Pentru determinarea soluiilor optime ale problemelor enunate avem nevoie de un instrument special,numit model matematic.

Formalizarea problemei.

Notm:

22

11

unitatidenumarul

unitatidenumarul

PCx

PCx

care vor fi realizate n urmtoarea sptmn,

? Orice cuplu de numere ),( 21 xx reprezint un program posibil de producie ? Evident cnu.

Oprim cerin natural esteca :0,0 21 xx (2.1)


3/31

3

unde 0sau0 21 xx semnific opiunea firmei de a nu produce PC1sau PC2.n continuare, asumm proprietile de liniaritate (omogenitate i aditivitate), pentru a construimodelul matematic al problemei .

Pentru asamblarea a x1 uniti PC1 sunt necesare 3x1 ore; cele x2uniti PC2au nevoie de 5x2

ore. Realizarea programului ),( 21 xx ar necesita, pentru asamblare, un total de 3x1 + 5x2 ore.Deoarece fondul disponibil de timp de asamblare este limitat la 150 ore, urmeaz c o condiiede realizare a programului ),( 21 xx este:

15053 21 xx (2.2)

Stocul limitat de monitoare PC2impune condiia:202 x (2.3)

Pentru depozitarea produselor finite este necesar o suprafa msurnd

21 58 xx u.a. Limitarea

spaiului de depozitare inplic cerina:

30058 21 xx (2.4)

Soluiile admisibile ale problemei firmei de calculatoare se identific cu acele cupluri ),( 21 xx care

satisfac condiiile (2.1)(2.4). Profitul rezultat din vnzarea unitilor produse prin programul ),( 21 xx este exprimat prin funcia

obiectiv:

21 4050 xxf (2.5)

Diferitele programe posibile vor fi apreciate prin valoarea pe care o dau acestei funcii. Reformulm problema dat :

n mulimea cuplurilor de valori numerice care satisfac condiiile (2.1) (2.4) s se determine cuplul),( 21

xx care d funciei obiectiv (2.5) cea mai mare valoare posibil.

Sintetizm, prin exprimarea matematic:

0,0

30058

20

15053

4050max

21

21

2

21

21

xx

xx

x

xx

xxf

(2.6)

i vom spune c (2.6) este modelul matematic al problemei firmei IT .

***


4/31

4

Studiul problemelor de optimizare practice nseamn, pe lng formularea unor modele matematice adecvate, i elaborarea unor metode de rezolvare a acestora adic elaborarea deproceduri/algoritmi de determinare a soluiilor optime.

***DEFINIIA 1. Ansamblul de relaii matematice, care const n maximizarea sauminimizarea unei funcii, ale crei variabile trebuie s satisfac un set de restricii i condiiiexplicite,poart numele de problem de programare matematic.

Dac funcia obiectiv i restriciile sunt liniare n variabilele de decizie vom avea de a face cu oproblem de programare liniar (PPL) sau program liniar (PL). Neliniaritatea funciei obiectiv saua unora dintre restricii plaseaz problema de programare n clasa celor neliniare.-----------pag 13.

2 Exemple de probleme de modelare economico matematic/ SEMINAR

n aceast seciune se dau cteva exemple de elaborare a modelelor matematice pentru o

serie de situaii din practica economic. Din motive evidente, situaiile analizate au fost multsimplificate rmnnd totui plauzibile, acestea punnd n eviden:

- identificarea corect a mrimilor variabile, a criteriului de performan i a condiiilorlimitative din situaia modelat;

- formalizarea corect a acestor elemente n relaii matematice.

Problema 1. Pentru asigurarea activitii curente de producie, o firm are nevoie de anumite cantitidin trei repere. n principiu, firma are posibilitatea de a fabrica aceste repere cu mijloace proprii darconducerea este de prere c resursele disponibile nu sunt suficiente pentru producerea cantitilor

necesare astfel c se pune problema achiziionrii unora de pe pia, cel puin n parte. n procesul defabricaie al reperelor la firm sunt implicate dou utilaje, fiecare cu un numr limitat de oredisponibile de funcionare. Datele concrete ale situaiei sunt indicate n tabelul 1.1:

Repere

Consumuri unitare de timp deprelucrare (u.t./reper)

Cost intern deproducie(u.m./reper)

Cost deachiziie de pe

pia(u.m./reper)

Cantitateanecesar de repere

(buci)M1 M2

R1 2 5 25 31 200

R2 3 4 44 47 100

R3 6 1 19 23 150

Timp disponibil(u.t.) 1200 1000

Tabelul 1.1

Conducerea firmei este interesat n a stabili ct s produc i ct s cumpere de pe pia astfel ncttotalul cheltuielilor sfie minim. Scriei un program liniar care s rspund acestui obiectiv.


5/31

5

Modelul matematic

I) Identificarea mrimilor variabile. Vom nota:

xicantitarea (n buci) din reperul Riprodus n cadrul firmei, i= 1,2,3

II) Identificarea condiiilor limitative i formalizarea lor n restricii.- ncadrarea necesarului de timp de prelucrare n fondurile de timp disponibil ale utilajelor M1i M2:

1200632321

xxx (1)

100045321

xxx (2)

- cantitile produse nu trebuie s depeasc comenzile:

2001 x (3)100

2 x (4)

1503x (5)

Observaie : un calcul simplu arat c fondurile de timp disponibil ale celor dou utilaje nu suntsuficiente pentru producerea reperelor cerute:

12001600150610032002 10001550150110042005

astfel c unele repere vor fi cumprate de pe pia la un pre mai mare.

III) Identificarea criteriului de performan i formalizarea lui n funcia obiectiv

Costul total =Costul producerii unor reperen cadrul firmei +

Costul achiziionrii restului derepere de pe pia =

)150(23)100(47)200(31194425 321321 xxxxxx

min43614350321

xxx

ns, minimizarea expresiei 321 43614350 xxx este echivalent cu maximizarea scztorului

321 436 xxx pentru c desczutul este o constant. n consecin vom lua ca funcie obiectiv:

max436321

xxxf (6)

IV) Condiii explicite impuse variabilelor:


6/31

6

0,0,0 321 xxx (7)

Observaie : normal ar fi s impunem i condiia 321 ,, xxx ntregi (cum de altfel ar fi trebuit i n

cazul problemei firmei de calculatoare din exemplul 1.2!) dar nu o facem deoarece s-ar complicarezolvarea. Este posibil ca n soluia optim

321 ,, xxx s aibe valori ntregi i dac nu se ntmpl acest

lucru putem recurge la rotunjiri. Soluia rezultat din rotunjire poate s nu mai fie optim dar abatereade la optim este economic neglijabilReunind (1)(7) obinem programul liniar:

0,,

150

100

200

100045

1200632

436(max)

)(

321

3

2

1

321

321

321

xxx

x

x

x

xxx

xxx

xxxf

P

Rezolvarea acestuia a condus la soluia optim:

1598(max)143,0,171 321 fxxx

Interpretarea soluiei:

-Din reperul R1, 171 buci se produc n cadrul firmei, restul de 29 buci se cumpr. Cost: 25171 + 3129 = 4275 + 899 = 5174u.m.

- Reperul R2se cumpr n totalitate de pe pia.Cost: 47100 = 4700u.m.

- Din reperul R3, 143 buci se produc n firm i celelalte 7 buci se cumpr:Cost: 19143 + 237 = 2717 + 161 = 2878u.m.

Costul total 5174 + 4700 + 2878 = 12752 = 14350- 1598

Problema 2.O banc asigur clienilor si patru tipuri de credit cu urmtoarele dobnzi anuale:

Tip credit Dobnda anual

1 12%

2 20%3 20%

4 10%

Tabel 1.2


7/31

7

Banca dispune de 250 milioane euro i n stabilirea cotelor pe care le va repartiza fiecrui tip de creditea va trebui s in seama de urmtoarele condiii:

a) Tipul 1 trebuie s reprezinte cel puin 55% din totalul creditelor de tipurile 1 i 2 i cel puin25% din totalul creditelor acordate (n milioane euro);

b) Tipul 2 nu trebuie s depeasc 25% din totalul creditelor acordate;c) Dobnda medie a tuturor creditelor acordate nu trebuie s depeasc 15%.

Cum va trebui s procedeze banca pentru a-i maximiza venitul din dobnzile la creditele acordate?

Modelul matematic

I) Identificarea mrimilor variabile. Vom nota

i

x volumul creditelor de tipul iacordate, i=1,2,3,4 (n milioane euro)

II) Formalizarea criteriului de performan n funcia obiectiv. Venitul bncii, din dobnzile lacreditele acordate are expresia

max10,020,020,014,0 4321 xxxxf (1)

III) Formalizarea condiiilor limitative n restricii

- totalul creditelor este plafonat la 250 milioane euro:

2504321

xxxx (2)

-

formalizarea condiiei a):

055,045,0)(55,0 21211 xxxxx (3)

025,025,025,075,0)(25,0 432143211 xxxxxxxxx (4)

- formalizarea condiiei b):

025,025,075,025,0)(25,0 432143212 xxxxxxxxx (5)- formalizarea condiiei c):

005,005,005,001,015,010,020,020,014,04321

4321

4321

xxxx

xxxx

xxxx

(6)

IV) Condiii explicite impuse variabilelor:

4,..,10 ixi (eventual ntregi dac nu se admit fraciuni de milion!) (7)


8/31

8

BunuriResurse

G1 G2 G3

R1 2 4 5R2 1 3 2R3 2 1 1

Tabelul 1.4

Reunind (1)(7) i opernd simplificri evidente se obine modelul liniar:

0,,

0555

03

0119

250

510107(max)

321

4321

4321

21

4321

4321

xxx

xxxx

xxxx

xx

xxxx

xxxxf

Pentru rezolvare s-a folosit un utilitar care a produs urmtoarea soluie ntreag:

Tip credit Volum (milioaneeuro)

1 65

2 513 484 86

Total 250

Tabelul 1.3

Tipul 1 reprezint 56% din totalul creditelor de tipurile 1 i 2 i 26% din totalul tuturor creditelor. Tipul2 reprezint numai 20,4% din total credite. n fine, dobnda medie la creditele acordate este de 15%.Venitul din dobnzi al bncii se ridic la 37,5 milioane euro.

Problema 3. O mic firm produce bunurile alimentare G1, G2, G3 folosind trei materii prime agricolede baz R1, R2, R3. Necesarul de resurse, n kg, pentru realizarea unui kilogram din fiecare din bunurileG1, G2, G3sunt indicate n tabelul 1.4.

Pentru ziua urmtoare exist n stoc 45 kg din R1, 30 kg din R2 i 20kg din R3.Profiturile sunt de 7, 9, 12 uniti monetare pe kilogramuldin G1, G2, respectiv G3. Firma livreaz bunul G1 n cutii de kg,bunul G2 n cutii de 1 kg i bunul G3 n cutii de 2 kg iar desfacereaeste asigurat pentru tot ceeace se produce.

1) Scriei un program liniar pentru determinarea programului de activitate al firmei n ziua

urmtoare avnd ca obiectiv maximizarea profitului.2) Cum se modific programul iniial dac din bunul G1 nu trebuie s se fac mai mult de zece

cutii?3) Cum se modific programul iniial dac din bunul G1 se pot face cel mult zece cutii iar din

G2cel puin trei?4) Deoarece resursele R1, R2, R3 sunt foarte perisabile firma este interesat n a le valorifica ct

mai bine. Cum se poate modela acest deziderat?


9/31

9

1) Modelul matematic

I) Identificarea mrimilor variabile . Fr ndoial, mrimile variabile ale acestei situaii sunt ce seva produce n ziua urmtoare din G1,G2,G3 cu resursele existente n stoc. Consumurile de resurse sunt

calculate la kg de produs finit ns forma final de prezentare a bunurilor este n cutii, astfel c nevaluarea produciei ce urmez a fi realizate bunurile vor fi msurate n cutii. n consecin, variabilelemodelului vor fi:

i

x numrul de cutii coninnd bunul Gice urmeaz a fi produse din resursele existente.

II) Identificarea condiiilor limitative i formalizarea lor n restricii. Avnd n vedere notaiile

introduse, bunurile G1,G2,G3 vor fi produse atunci n cantitile (n kg) kg.2respectiv,2

1321 xxx

ncadrarea consumurilor de resurse n stocurile disponibile conduce la restriciile:

452542

1

2 321 xxx

(1)

302232

11 321 xxx (2)

202112

12 321 xxx (3)

III) Identificarea criteriului de performan i formalizarea lui n funcia obiectiv . Se urmrete

maximizarea profitului a crui expresie este321

21292

17 xxx u.m.

IV) Condiii explicite impuse variabilelor modelului. Condiiile de nenegativitate sunt evidente:

0,0,0 321 xxx

la care se adaug condiia

321 ,, xxx ntregi

deoarece produsele finale sunt msurate n uniti indivizibile (nu se poate produce o fracie dintr-ocutie) n final se obine programul liniar:

(intregi)0,,

202

30435,0

451042495,3(max)

)(

321

321

321

321

321

1

xxx

xxx

xxx

xxxxxxf

P


10/31

10

2) La modelul (P1) se adaug restricia 101 x obinndu-se programul (P2)

3) La modelul (P1) se adaug restriciile 3,10 21 xx obinndu-se programul (P3)

4) n notaiile modelului (P1) cantitile de resurse neconsumate au expresiile:

resursa R1: 0)104(45 321 xxx resursa R2: 0)435,0(30 321 xxx

resursa R3: 0)2(20 321 xxx

Valorificarea celor trei resurse este cu att mai bun cu ct diferenele de mai sus sunt mai mici. Vomrealiza acest lucru minimiznd cea mai mare dintre diferene:

(P)modeluluirelatiiletoatesatisfac,,si

)}2(20),435,0(30),104(45max{

unde

(min)

321

321321321

xxx

xxxxxxxxxy

y

Pentru a transforma noul model ntr-un program liniar uzual nlocuim relaia de definiie a variabilei ycu inegalitile:

yxxx )104(45 321

yxxx )435,0(30 321

yxxx )2(20 321

Tot din relaia de definiie a lui y rezult c dac 321 ,, xxx sunt ntregi atunci y este sau un numr ntregsau un numr cu partea fracionar 0,5; n consecin, numrul z = 2y va fi cu siguran ntreg.

nlocuind mai sus2

zy obinem programul liniar:

(intregi)0,,,

205,02

305,0435,0

455,0104

202

30435,0

45104

5,0(min)

)(

321

321

321

321

321

321

321

4

zxxx

zxxx

zxxx

zxxx

xxx

xxx

xxx

z

P


11/31

11

Analiza comparativ a soluiilor optime. n tabelul 1.5 sunt prezentate soluiile optime ntregiale modeleor P1P4.

Cel mai mare profit care s-ar obine din resursele date este de 121 u.m.; aceast valoare poate filuat ca punct de referin. Soluia corespunztoare are unele inconveniente: nu produce bunul G2 i

aproape o treime din resursa R2 nu se consum. ncercarea de diversificare a produciei vezi soluiilemodelelor (P2) i (P3) - reduce profitul cu cteva procente i duce la creterea cantitilor de resurseneutilizate. Ultima propunere de plan de activitate asigur o utilizare aproape total a resurselordisponibile iar profitul aferent este foarte aproape de nivelul maxim posibil. Totui ea nu prevedeproducerea bunului G3 i acest lucru s-ar putea s conteze n decizia final, decizie care va trebui sin seama i de cererea pentru acest bun.

Model

Programul optim de activitateCantitatea de produsn cutii i kg

din:

Resurse consumate(n kg i % din stocurile disponibile) Profit

G1 G2 G3 R1 R2 R3

Cutii kg Cutii kg Cutii kg kg % kg % kg % u.m. %P1 14 7 - - 3 6 44 97,8 19 63,3 20 100 121 100

P2 10 5 1 1 3 6 44 97,8 20 66,7 17 85 116 95,9

P3 9 4,5 4 4 2 4 45 100 24,5 81,7 17 80 115,5 85

P4 12 6 8 8 - - 44 97,8 30 100 20 100 114 94,2

Tabelul 1.5

Problema 4. Din bare cu lungimea 100 dm trebuie tiate bare mai mici cu lungimile 47,31 i 19 dm ncantitile 15, 21 respectiv 40 buci. Scriei un program liniar pentru realizarea comenzilor specificatecu un consum minim de bare cu lungimea 100 dm.

Modelul matematic

I) Identificarea mrimilor variabile. Dac n problemele precedente mrimile variabile erau efectivprezente n enun ,ateptnd doar s fie recunoscute i notate, n cazul de fa lucrurile sunt maicomplicate: din enun lipsesc informaiile privind modalitile de tiere a barelor lungi n bare maiscurte. Aceste modaliti de tiere se numesc reete de croire i multiplicitile de folosire a lor vor fivariabilele modelului!O reet de croire se va zice maximal dac din restul ei nu se mai poate croi nici una din barele (maimici) cerute. Lista reetelor maximale este dat n tabelul 1.11

Reeta R1 R2 R3 R4 R5 R6 R747 dm 2 1 1 - - - -31 dm - 1 - 3 2 1 -19 dm - 1 2 - 2 3 5

Rest (dm) 6 3 15 7 0 12 5

Tabelul 1.11


12/31

12

Notm

jx numrul barelor lungi de 100 dm tiate dup reeta Rj, j= 1,...,7

II) Formalizarea condiiilor limitative n restricii Barele cu lungimea de 47 dm se obin numai dinaplicarea reetelor R1 , R2 , R3. Din tierea a x1bare de 100 dm dup reeta R1se obin 2x1bare de 47dm. Aplicnd i reetele R2 i R3 de x2 respectiv x3ori se mai obin- separat - cantitilex2ix3de barede 47 dm. n consecin, din procesul de tiere rezult un total de

3212 xxx bare de 47 dm care

trebuie s acopere cele 15 buci cerute:

152 321 xxx (1)

Realizarea cantitilor de bare de 31 dm i de 19 dm conduce la inegalitile:2123 6542 xxxx (2)

405322 76532 xxxxx (3)

III) Formalizarea criteriului de performan n funcia obiectiv. Se urmrete minimizareanumrului de bare de 100 dm tiate:

7654321(min) xxxxxxxf (4)IV) Condiii explicite impuse variabilelor:

7,,10 jxj i ntregi (5)

Reunind (1)(5) se obine un program liniar cu trei restricii i apte variabile.Observaie : O soluie acceptabil pentru problema dat se obine astfel. Calculm lungimea total a barelor cerute: 1547 + 2131 + 4019 = 2116 dm. Rezult imediat c pentru

satisfacerea comenzilor trebuie tiate cel puin 221002116

bare de 100 dm. Am putea folosi reeta R2

de 15 ori apoi reeta R6 de 6 ori i la urm reeta R7de dou ori obinnd cantitile cerute i un surplusde 3 bare de 19 dm.Se folosesc 15 + 6 + 2 = 23 bare lungi. Resturile procesului de tiere nsumeaz23100 2116 = 184 dm reprezentnd 8% din lungimea barelor tiate. Dei poate fi apreciat ca foartebun, aceast soluie nu este optim; se poate arta c sunt suficiente 22 de bare de 100 dm pentru acroi toate barele mai mici, resturile reprezentnd numai 3,82% din ce s-a tiat.. Invitm cititorul sgseasc soluia optim.


13/31

13

3 Forma general a unui program liniar

Reamintim c oproblem de programare matematic const n maximizarea sau minimizarea uneifuncii ale crei variabile trebuie s satisfac un set de egaliti i/sau inegaliti nestricte. naplicaiile practice,vari abil ele nu pot lua dect anumite valor i reale, ca de exemplu numai valor i

nenegative.Funcia de optimizat se numete funcie obiectiv iar relaiile necesar a fi ndeplinite de ctre variabilese numesc restricii.DEFINIIA 2. O problem de programare liniar (PPL), sau un program liniar (PL) este oproblem de programare matematic n care funcia obiectiv i restriciile sunt liniare nvariabilele problemei.

Exemplul 1Exemple de programe liniare:

0,0

30058

20

15053

4050(max)

)(

21

21

2

21

21

1

xx

xx

x

xx

xxf

P (dat anterior)

0;0;frs

45

33

223

1005030(min)

)(

321

31

21

321

321

2

xxx

xx

xx

xxx

xxxf

P

frs fr restricie de semn( orice valoare real)

Putem presupune c toate variabilele unui program liniar satisfac condiia de nenegativitate :

0jx

nlocuind la nevoie:

- o variabil nepozitiv 0jx cu opusa ei 0 jj xx

- o variabil fr restricie de semn,cu diferena a dou variabile nenegative:

0,0cu jjjjj xxxxx

Exemplul 2 Transformm programul (P2) din exemplul 1 ntr-un program echivalent n care toatevariabilele satisfac condiia de nenegativitate. Pentru aceasta facem substituiile :

0,0cu 11111 xxxxx i 0cu 222 xxx


14/31

14

Obinem programul:

0,0,0,0

455

333

223

100503030(min)

3211

311

211

3211

3211

xxxx

xxx

xxx

xxxx

xxxxf

DEFINIIA 3: n forma sa general, un program liniar (P) const din:

n variabile reunite n vectorul ),,,( 21 nxxxx ;

mrestricii liniare n variabilele nxxx ,,, 21 care pot fi egaliti sau inegaliti nestricte:

mibxaxaxaininii

,,12211

(1)

(n (1) ieste indicele restriciei; pentru fiecare mi ,,1 este precizat unul din semnele , = sau )

funcie obiectiv, liniar n variabilele nxxx ,,, 21 :

nnxcxcxcxf 2211)( (2)

condiii de nenegativitate impuse tuturor variabilelor:

0,,0,0 21 nxxx (3)

DEFINIIA 4. Un ansamblu de valori numerice ),,,( 21 nxxxx care satisfac restriciile (1) senumete soluie a programului (P). Dac n plus sunt verificate i condiiile de nenegativitate (3) adic

01 x , 0

2 x , ...., 0nx ,vom spune c x este o soluie admisibil a lui (P)

Vom nota cu A (sau cu A P dac este necesar) mulimea soluiilor admisibile ale programului (P).Aeste o submulime a spaiului numeric nR .

DEFINIIA 5. O soluie admisibil ),,,( 21

n

xxxx cu proprietatea:

A xxfxf ,)(max)( sau, dup caz A xxfxf ,)(min)(

se numete soluie optim a programului (P).n baza relaiei:

-A xxf ,)(min A xxf ,)(max

n consideraiile teoretice dezvoltate n continuare vom presupune c funcia obiectiv din (P) semaximizeaz.


15/31

15

Exemplul 3Pentru programul liniar

ansamblul de valori numerice (vectorul) 5,5,15)5,5,15( 321 xxxx este o

soluie neadmisibil; vectorul )2,16,14(~ x este o soluie admisibil care d funciei obiectiv valoarea 30)~( xf ;

vectorul 0,9,13)0,9,13( 321

xxxx este unica soluie optim a programului

(P), oferind funciei obiectiv valoarea maxim 50)( xf .

4 Studiul unui program liniar n dou variabile / SEMINAR

Considerm un program liniar n dou variabile 21 , xx : lum ca exemplu modelul matematic alproblemei firmei de calculatoare:

0,0

3005820

15053

4050(max)

)(

21

21

2

21

21

1

xx

xxx

xx

xxf

P

Pentru un asemenea program avem posibilitatea vizualizrii mulimii soluiilor sale admisibile identificnd x1 i x2 cu abscisa respectiv ordonata unui punct dintr-un plan raportat la un sistem deaxe.Sunt necesare cteva rudimente de geometrie analitic.

0,0,0

203

352

3023

768(max)

)(

321

31

21

321

321

xxx

xx

xx

xxx

xxxf

P


16/31

16

Avnd n vedere semnificaia variabilelor21

, xx punctele ),( 21 xx n care x1


17/31

17

Se ridic firescntrebrile:

I) Care sunt punctele corespunztoare inteniilor de plan realizabile? Cum aratmulimea lor?

II) Unde se gsete punctul corespunztor programului realizabil cu cel mai mare profit(programul optim) i cum se gsete el?III) Ce concluzii s-ar putea trage pentru cazul general (mai mult de dou variabile)?

I) Rspuns

Determinm punctele ),( 21 xx cu 0,0 21 xx care satisfac prima restricie din (P1): 15053 21 xx .

Pentru aceasta reprezentm n plan dreapta de ecuaie 1505321

xx - vezi figura 2.2. Punctele

acestei drepte n care 0,021

xx corespund inteniilor de plan care utilizeaz integral timpuldisponibil pentru asamblare. Din acest motiv, dreapta de ecuaie 15053

21 xx se va numi n

continuare dreapta asamblare.

Punctele ),( 21 xx care satisfac inegalitatea 15053 21 xx constituie unul din cele dou semiplane

determinate de dreapta asamblare. Pentru identificarea lui va fi suficient s lum un punct nesituat pedreapt de exemplu origina (0,0) i s testm satisfacerea restriciei de ctre coordonatele punctuluiales.n caz afirmativ, reinem semiplanul care conine punctul, altminteri reinem cellalt semiplan.Programele poteniale care satisfac prima restricie sunt vizualizate n figura 2.3.

.

Procedm analog i cu celelalte dou restricii vezi figurile 2.4 i 2.5

x2

x1

Trasarea dreptei asamblare de ecuaie15053 21 xx

Origina (0,0)

x1=0 x2=30

x2=0 x1=50

Tieturi

Figura 2.2

x2

x1

Figura 2.3

30

50(0,0) x20

Dreapta ASAMBLARE15053

21 xx

Punctele corespunztoare inteniilor poteniale de

plan (x10, x20) al cror necesar de timp pt.asamblare se ncadreaz n disponibil:

1505321

xx


18/31

18

Recapitulnd, n figurile 2.1, 2.3, 2.4 i 2.5 apar mulimile de puncte ),( 21 xx ale cror coordonate

satisfac separat! condiiile de nenegativitate i restriciile programului (P 1). Partea lor comun,adic intersecia, este format din punctele care satisfac simultan toate aceste condiii.

n figura 2.6 este vizualizat aceast intersecie; ea este mulimea hasurat OABCD. Punctele eisunt exact soluiile admisibile ale programului (P1) i corespund propunerilor de plan, realizabiledin resursele date.

II) Rspunsla a doua ntrebare .

Dnd funciei obiectiv f o valoare oarecare, de exemplu 1300, ne putem ntreba ce semnificaie aupunctele ),( 21 xx - firete cu 0,0 21 xx - situate pe dreapta:

130040501300 21 xxf

Aceste puncte corespund inteniilor de plan care ar aduce firmei un profit de $1300 firete n cazuln care aceast intenie ar fi i realizabil.

Pentru a vedea dac firma poate realiza un profit de $1300 din resursele date, cercetm dac dreaptaf = 1300 intersecteaz mulimea A a programelor de producie realizabile. Din figura 2.7 rezult cexist chiar o infinitate de programe realizabile care ar conduce la acest profit. Se poate obine un profitdublu? Din aceeai figur rezult c dreapta

21 40502600 xxf nu mai intersecteaz A i n

consecin $2600 nu pot fi ctigai din resursele date!Pentru a vedea ct de mare este profitul ce poate fi realizat, translatm dreapta f = 1300 ctre dreaptaf = 2600 oprindu-ne n momentul n care se pierde intersecia cu mulimea soluiilor admisibile A.

dreapta MONITOARE PC2x2= 20

x2

x1

Figura 2.4

20

Punctele corespunztoare inteniilorpoteniale de plan (x10,x20) al crornecesar de monitoare PC2se ncadreazn disponibil:x220

x1 0

x2

x20x1

Figura 2.5

x1 0

x2

x20

60

37,5

Punctele corespunztoare inteniilorpoteniale de plan (x10,x20) al cror

necesar de spaiu pt. depozitare sencadreaz n spaiul disponibil:

8x1+5x2300

Dreapta DEPOZITARE8x1+5x2= 300


19/31

19

x2

x1

x20

x10

(25,20)

(15,10)

(10,20)

O A

B

D C

A

Figura 2.6

mulimea soluiilor admisibile aleprogramului liniar:

0,0

30058

20

15053

4050(max)

)(

21

21

2

21

21

1

xx

xx

x

xx

xxf

P

x2

x1O A

B

D C

A

Figura 2.7

Profit =$1300

Profit =$2600

Profit maxim Soluia optim

12,30 21

xx


20/31

20

Din figura 2.7 rezult c dreapta profit maxim trece prin punctual B, punct ce reprezint soluiaoptim a problemei.Programul realizabil reprezentat de punctual B, program care ar aduce firmei cel mai mare profitposibil, se afl la intersecia dreptelor asamblare i spaiu de depozitare; prin urmare acest plan

necesit consumarea integral a resurselor sus amintite.Componentele programului optim coordonatele punctului B se obin rezolvnd sistemul de ecuaiiliniare:

fx

x

xx

xxmaximprofitul

PCunitati12

PCunitati30

30058

15053

22

11

21

21 $1980

5 Concluzii generale rezultate din rezolvarea grafic a programelorliniare n dou variabile/ SEMINAR

Considerm acum un alt program liniar n dou variabile:

0,0

52

1045

323

3(max)

)(

21

21

21

21

21

2

xx

xx

xx

xx

xxf

P

n figura 2.8 este vizualizat mulimea soluiilor admisibile A : este mulimea haurat ABCD. Ecuaiade definiie a funciei obiectiv:

fxx 21

3

poate fi interpretat ca ecuaia unei mulimi de drepte paralele, ( denumirea consacrat: fascicul dedrepte paralele) numite drepte de nivelale funciei f. Dac o dreapt particular

fxx 213 (n figur 1f )

intersecteaz A aceasta va nsemna c programul (P2) are soluii admisibile care ofer funciei obiectivvaloarea prestabilit f. Pentru valori numerice superioare lui f dreptele de nivel corespunztoare sunt

translaii ale dreptei originale n sensul indicat de sgeat. Rezult uor c maximul funciei f se atingen vrful (colul) A al frontierei mulimii A. A este intersecia dreptelor de ecuaii 323 21 xx

i 52 21 xx . Rezolvnd sistemul acestor ecuaii se gsete soluia optim

7

9,

7

13x cu


21/31

21

7

30)(max xff , care satisface cu egalitate prima i a treia restricie i cu inegalitate strict pe cea

de a doua.

Dac n (P2) schimbm funcia obiectiv 213 xxf cu funcia 21 xxg obinem un nou program

liniar, (P3) a crui soluie optim se gsete n alt vrf al mulimii A i anume n B de coordonatele

22

15,

11

1621 xx - vezi figura 2.9.

x2

A

f= 1

x20

x1

x10

A

B

C

D

max f

7

30max f

2x1+x2 53x1-2x2 3

5x1+4x2 10

Soluia optim x*:

7

9,

7

1321

xx

Figura 2.8


22/31

22

n fiecare din cele trei rezolvri grafice de programe liniare n dou variabile de pn acum, optimulfunciilor obiectiv a fost realizat de ctre o singur soluie admisibil. Nu ntotdeauna este aa; sconsiderm programul liniar (P4) derivat din (P2) prin nlocuirea funciei obiectiv f cu funcia

21 510 xxh .Din figura 2.10 rezult c nu numai vrfurile

7

9,

7

13A i 5,0D sunt soluii

optime dar i toate celelalte puncte ale segmentului AD au aceast calitate. Prin urmare programul (P4)are o infinitate de soluii optime.Vom analiza acum programul liniar:

0,01045

323

3(max)

)(

21

21

21

21

5

xxxx

xx

xxf

P

derivat din (P2) prin eliminarea celei de a treia restricii. Mulimea soluiilor admisibile ale nouluiprogram este nemrginit vezi figura 2.11 i orice dreapt de nivel a funciei obiectiv

fxx 21

3

A

x1

A

B

C

D

max g

22

17max g

Figura 2.9

Soluia optim:

2215

21116

1 , xx

x2


23/31

23

x2

B

Max h

Max h= 25

Orice punct al segmentuluiAD reprezint o soluie optim

D

A

A

Figura 2.10

C

x1

max f

B

C

x2

x1

Figura 2.11

Mulimea soluiilor admisibileale programului (P5) estenemrginit. Nu exist o ceamai bun soluie! Zicem cprogramul (P5)are optim infinit


24/31

24

o va intersecta, orict de mare ar fi constanta f.Conchidem c dei (P5) are soluiiadmisibile, nu existuna care s ofere funciei obiectiv cea mai mare valoare. Vom spune c funcia obiectiv a programului(P5) este nemrginit superiorpe mulimea soluiilor sale admisibile sau c (P5) are optim infinit.

S lum n considerare i programul liniar:

0,0

52

1045

323

3(max)

)(

21

21

21

21

21

6

xx

xx

xx

xx

xxf

P

dedus din (P2) schimbnd sensurile tuturor restriciilor. n figura 2.12 sunt puse n eviden cele cinci

semiplane n care sunt verificate restriciile i condiiile de nenegativitate. Mulimea haurat esteformat din punctele ale cror coordonate verific toate restriciile programului; aceste punctereprezint soluiile programului. Nici una dintre aceste soluii nu verific simultan ambele condiii denenegativita te, altfel spus nu este admisibil. Programul (P6) nu are soluii admisibile ; zicem c (P6)

Figura 2.12

5x1+4x2 10

2x1+x2 5

3x1-2x2 3

1 0

2 0

Programul (P6) are soluii dar nu aresoluii admisibile!Un program liniar fr soluii admisibilese zice incompatibil

1

2


25/31

25

este un program incompatibil.Exemplele studiate mai sus ilustreaz urmtoarea clasificare a programelor liniare dup existenasoluiilor admisibile.

Observaie : Existena unei soluii optime n cazul n care funcia obiectiv este mrginitpe mulimeasoluiilor admisibile A este consecina faptului c A este o mulime nchis n topologia uzual aspaiului numeric nR ( i conine frontiera). Faptul c A este nchis rezult din cerina ca toaterestriciile inegaliti s fie nestricte .De exemplu, funcia xxf 3)( este mrginit superior pe mulimea A = }10{ xx - care nu este

nchis - ns xxf ,)(max{ A }nu exist: singurul candidat ar fi 1dar1x A!

Urmtoarele concluzii sunt valabile pentru orice program liniar compatibil n dou sau trei variabile mulimea soluiilor admisibile Aputnd fi vizualizat n planul R2 sau spaiul fizic R3:

Mulimea este convex, adic cu dou puncte conine i segmentul care unete punctele.

O consecin intuitiv a acestei proprieti este c soluia optim, dac exist, se gseteundeva pe frontiera lui .

Frontiera mulimii are un numr finit de vrfuri i dac programul are soluii optimecel puin una dintre ele se gsete ntr-un vrf.

Programeliniare

Compatibile(cu soluii admisibile)

Incompatibile(fr soluii admisibile)

Cu optim finit(funcia obiectiveste mrginit pemulimea soluiilor admisibile)

Cu optim infinit(funcia obiectiv este nemrginitpe mulimea soluiilor admisibile)

Cu soluieoptim unic

Cu o infinitate de soluii optime

Figura 2.13


26/31

26

Aceste afirmaii constituie sursa ntregii teorii a programrii liniare deoarece sunt valabile pentru

orice program liniar, bineneles cu condiia generalizriicorespunztoare a termenilor geometriciutilizai n formulare.

6 Forme speciale de prezentare a unui program liniar

ntr-un program liniar se pot ntlni restricii de toate tipurile, egaliti i inegaliti, acestea din urmputnd fi de sensuri contrare. Studiul teoretic a impus forme speciale de prezentare, mai simple, n caretoate restriciile au aceeai form:

- forma canonic, n care toate restriciile sunt inegaliti cu acelai sens;- forma standard, n care toate restriciile sunt egaliti.

Orice program liniar poate fi adus la una din aceste forme fr alterarea mulimii soluiilor admisibilei nici a soluiilor sale optime!

1) Forma canonica unei probleme de programare liniar

DEFINIIA 6. O restricie a unui program liniar (P) se zice concordant dac este oinegalitate de tipul "" cnd funcia obiectiv se maximizeaz i de tipul "" cnd funcia obiectiv seminimizeaz.

DEFINIIA 7. O restricie inegalitate care nu este concordant se va numi neconcordant.Restriciile egaliti nu fac obiectul acestei clasificri.

DEFINIIA 8. Spunem c o problem de programare liniar este n form canonic dactoate restriciile ei sunt inegaliti concordante.

n consecin, o problem n form canonicde maximizare aratastfel:

a x b i m

x j n

f c x

ij jj

n

i

j

j jj

n

1

1

1

0 1

,...,

,...,

(max)

sau matricial

Ax b

x

f cx

0

(max)

unde:

A

a a a

a a a

a a a

b

b

b

b

x

x

x

x

n

n

m m mn m n

11 12 1

21 22 2

1 2

1

2

1

2

c c c cn 1 2


27/31

27

O problem n form canonicde minimizare se va scrie:

a x b

x

f c x

ij jj

n

i

j

j jj

n

1

1

0

(min)

Ax b

x

f cx

0

(min)

Orice problem de programare liniar se poate pune sub o form canonic de maximizare sauminimizare, frmodificarea mulimii soluiilor admisibile, observnd c:

o egalitate se poate nlocui cu dou inegaliti de sens contrar; o restricie neconcordant devine concordant prin nmulire cu -1; putem schimba sensul optimizrii funciei obiectiv, graie formulei generale:

x

f xx

f x

A Amin ( ) max ( ) (1)

n consecin, putem face anumite raionamente teoretice pe o form canonic, ca de exemplu n teoriadualitii liniare, frca prin aceasta srestrngem generalitatea.

Exemplul 2.1 de aducere a unui program liniar la o form canonic:

(max)

, ,

f x x x

x x x

x x

x x

x x x

2 3 4

3 5 3

3 5

2 10

0 0 0

1 2 3

1 2 3

1 2

1 3

1 2 3

(min)( )

, ,

f x x x

x x x

x x x

x x

x x

x x x

2 3 4

3 5 3

3 5 3

3 5

2 10

0 0 0

1 2 3

1 2 3

1 2 3

1 2

1 3

1 2 3

Programul (P) Forma canonic de minimizare a programului (P)

2) Forma standard a unei probleme de programare liniar

DEFINIIA 9. Spunem c o problem de programare liniar este n form standard dactoate restriciile ei sunt egaliti.

Importana acestei forme particulare rezult din faptul c metoda de rezolvare a problemelorde programare l ini arcare va fi expusmai departe cere ca probl ema sfie n aceastprezentare.


28/31

28

n consecin, o problem (P) care are i restricii inegaliti va fi nlocuit - n vederearezolvrii ei - cu o alta n care toate restriciile sunt egaliti.

Noua problem, numit forma standard a problemei (P) i notat (FSP), se construiete astfel: O restricie inegalitate din problema original (P) de tipul "" (respectiv de tipul "")

se transform n egalitate prin adugarea (respectiv prin scderea) unei variabilenenegative din membrul su stng.

Restriciile egaliti nu se modific.

Noile variabile introduse nu apar n funcia obiectiv a problemei originale (alternativ,spunem cele apar cu coeficieni nuli)

Variabilele introduse n restricile inegaliti n scopul transformrii acestora n egaliti poart numelede variabile de abatere .

Exemplul 2.2 de aducere a unu i program l ini ar l a forma standard.

( )

(max)

, ,

P

f x x x

x x x

x x x

x x x

x x x

7 9 8

5 2 4

3 5

2 3 9

0 0 0

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

( )

(max)

, , ...,

FSP

f x x x

x x x x

x x x

x x x x

x jj

7 9 8

5 2 4

3 5

2 3 9

0 1 5

1 2 3

1 2 3 4

1 2 3

1 2 3 5

Problema care apare n acest context este aceea de a explica modul n care se obine soluia optim aproblemei (P) dacse cunoate soluia optim a formei sale standard (FSP).

Se poate arta uor c ntre mulimile de soluii admisibile AP ,ale problemei (P) iAFSP, ale problemei(FSP), exist o coresponden bijectiv care conserv soluiile optime.Vom arta cum funcioneazaceastcoresponden pe exemplul precedent.

Notnd-o cu ,aceasta va asocia unei soluii admisibile x = ( x x x1 2 3, , ) a problemei (P)vectorul:

( ) ( , , , , )x x x x x x x x x x 1 2 3 1 2 3 1 2 35 2 4 9 2 3

care prin construcie se dovedete a fi o soluie admisibil a problemei (FSP). Reciproc, unei soluiiadmisibile ~ (~ ,~ ,~ ,~ ,~ )x x x x x x 1 2 3 4 5 a problemei (FSP) corespondena invers

-1 i asociaz vectorul

( ~ ,~ ,~ )x x x1 2 3 care satisface restriciile problemei originale (P) deoarece 0~,0~ 54 xx .Dac x estesoluia optim a problemei (P) atunci (x ) este soluia optim a problemei (FSP) i reciproc, daccunoatem soluia optim ~x a problemei (FSP) , 1(~)x reprezint soluia optim a problemei (P).

n problemele concrete, variabilele de abatere au interpretri economice precise ca deexemplu cantiti de resurse neutilizate sau depiri ale unor indicatori economici aa c n


29/31

29

analiza soluiei optime valorile lor vor fi luate n considerare laolalt cu valorile variabilelororiginale.

Exemplul 2.3 Relum modelul problemei firmei de calculatoare (rezolvat grafic n seciunea

anterioar) mpreun cu forma sa standard:

54321

521

42

321

21

21

21

2

21

0004050(max)

5,,10

30058

20

15053

)(

4050(max)

0,0

30058

20

15053

)(

xxxxxf

jx

xxx

xx

xxx

FSP

xxf

xx

xx

x

xx

P

j

Coninutul economic al variabilelor de abatere 543 ,, xxx deriv nemijlocit din semnificaiilerestriciilor n care sunt introduse. Astfel:

Analog:

24

20 xx monitoare PC2 rmase n stoc

)58(300 215 xxx spaiul de depozitare nefolosit

tiind c:

1980(max)0801230 54321 fxxxxx

este soluia optim a formei standard, cuplul 1230 21

xx reprezint soluia optim a programuluioriginal (P) iar 1980 este valoarea maxim a funciei obiectiv. n termeni economici , programul optimde activitate al firmei pentru urmtoarea sptmn ar consta n asamblarea a 30 uniti PC 1 i a 12

uniti PC2 cu un profit maxim de $1980. n plus 03

x i 05

x arat c acest program ar utiliza

integral fondul de timp pentru asamblare i spaiul de depozitare n timp ce 84

x arat c n stoc armai rmne 8 monitoare PC2ce ar putea fi folosite n alt perioad de planificare.

Fondul de timpdisponibil pentru asamblare

150x3 =

Necesarul de timp pentruasamblarea cantitilor x1,x2de produse finite

( 3x1+ 5x2 )Fondul de timp pentruasamblare neutilizat-


30/31

30

Probleme propuse

1. S se reprezinte grafic mulimea soluiilor admisibile ale programului liniar:

0,0

2126

0

5

2(max)

)(

21

21

21

21

21

1

xx

xx

xx

xx

xxf

P

a)

s se determine grafic soluia optim a programului (P1);b) care va fi soluia optim dac funcia obiectiv se schimb n 21 2(max) xxg


0,0

22

22

62

25(min)

)(

21

21

21

21

21

2

xx

xx

xx

xx

xxf

P

a) s se determine grafic soluia optim a programului (P2);b) care va fi soluia optim dac funcia obiectiv se schimb n 21 63(min) xxg


0,062

22

1243

(max)

)(

21

21

21

21

21

3

xxxx

xx

xx

xxf

P

a) s se determine grafic soluia optim a programului (P3);b) care va fi soluia optim dac funcia obiectiv se schimb n 21(max) xxg


31/31

4. Determinai pe cale grafic soluiile optime ale programelor liniare rezultate din modelareaproblemelor 1 i 2 din seciunea Probleme propuse a unitii de nvare 1. Interpretai economicsoluiile gsite.

5.

Rezolvai pe cale grafic programul liniar:

0,0,0,0

22

22

42

1

3

23(max)

4321

43

43

21

21

21

4321

xxxx

xx

xx

xx

xx

xx

xxxxf

bazele cercetarilor operationale curs 6

Documents