2.elem. programare liniară

8/12/2019 2.Elem. Programare Liniară

http://slidepdf.com/reader/full/2elem-programare-liniara 1/23

ELEMENTE DE PROGRAMARE LINIARĂpentru optimizarea deciziei economice

Obiective şi competenţe Optimizarea deciziilor economice prin aplicarea modelelor matematice de programare

liniară. Metoda SIMPLEX de rezolvare a problemei de programare liniară.

Studentul va recunoaşte problemele de natură economică care necesită optimizarea funcţiei

de eficienţă economică prin programare liniar ă,va şti să transpună textul economic în modelulmatematic al Problemei de Programare Liniară (PPL) , va aplica algoritmul Simplex pentru

rezolvarea PPL , va interpreta rezultatele din punct de vedere economic şi va stabili decizia optimăîn contextul economic.

Timp alocat de studiu: 8 h

Teme de studiu : Modele de programare liniară întâlnite în practica economica (pr oblema

de planificare a producţiei, de nutriţie, de amestec, de transport – descrierea generală şi

construirea modelului matematic). Aducerea la forma standard a PPL şi determinarea unui program de bază. Teoremele algoritmului Simplex (criteriul de optim, criteriul de intrare în bază,

criteriul de optim infinit, criteriul de ieşire din bază). Algoritmul Simplex primal (enunţ şiinterpretare economică). Metoda bazei artificiale – coeficienţi de penalitate.

Conținut:

• Sinteză și exemple

• Probleme rezolvate

• Aplicaţii propuse• Test grilă de autoevaluare

*Manual: Radu Despa, Marilena Aura Din, Cristina Coculescu, Cătălina Vișan, Ovidiu Solomon,Carmen Țirdă, Maria Gogâltan, Adam Altăr Samulel, Matematici aplicate în economie, Ed.Universitară 2012, București, 281 pagini, ISBN: 978-606-591-539-8.

Teme de studiu:

2.1. Exemple de modele de programare liniară întâlnite în practica economică

Problema de programare liniară este modelul matematic al unei probleme de luare a decizieioptime.



Matematici aplicate în economie – Conf. univ. dr. Din Marilena-Aura

Modelul matematic este numit program liniar din cauză că funcţiile obiectiv şi restricţiilesunt liniare. Rezolvarea unui program liniar revine la optimizarea funcţiei obiectiv (maximizareasau minimizarea) supusă la limitări şi cerinţe care reprezintă restricţiile.

Modelarea unei probleme cu conţinut economic care implică optimizare liniară necesită parcurse următoarele etape:

1. Identificarea variabilelor modelului, a funcţiei obiectiv (funcţia eficienţă) ce se cereoptimizată, a restricţiilor cărora le sunt supuse variabilele modelului şi eventual întocmireaunui tabel de date;

2. Determinarea modelului matematic asociat problemei de programare liniară (P.P.L.)rezultate;

3. Aducerea P.P.L. la forma standard, cea pentru care este elaborat algoritmul de optimizare asoluţiei primal admisibile de bază;

4. Determinarea unei baze admisibile;5. Aplicarea algoritmului Simplex pentru determinarea programului optim de bază şi a

optimului funcţiei obiectiv şi verificarea rezultatelor; 6. Interpretarea rezultatelor din punct de vedere economic şi luarea deciziei optime în plan

economic.Prezentăm câteva dintre cele mai întâlnite probleme cu caracter economic modelate cu

ajutorul programării liniare, urmărind etapele 1. şi 2., adică punerea problemei în modelulmatematic al unei P.P.L.

Următoarele probleme sunt enunţate ca modele economice pretabile la a fi modelate prinmodelul matematic al problemei de programare liniar ă. Pentru fiecare enunţ economic se noteazăvariabilele modelului şi se organizează datele într -un tabel de date, pentr u a fi mai uşor de desprins

părţile componente ale modelului matematic: optimul funcţiei obiectiv, restriscţiile problemei şicondiţiile de nenegativitate.

a) problemă de planificare a producţiei.

O întreprindere produce n sortimente n,1 j ,S j = şi dispune de m resurse m,1i ,R i = . Se cere

să se organizeze producţia dacă se cunosc cantitatea de resurse disponibile, consumurile specifice şi beneficiile unitare.

Identificăm organizarea producţiei în crearea modelului PPL cu planul de producţie. Fie:

di- cantitatea de resurse R i disponibilă aij - cantitatea de resurse R i necesare consumării pentru sortimentul S j c j - beneficiul adus de sortimentul S j.

Notăm x j – numărul de sortimente de tip S j. Atunci planul de producţie este re prezentat de

vectorul coloană ( )Tn21 x,,x,x =Χ .Organizăm datele într -un tabel ca cel de mai jos:

sortimenteS1 S2 Sn disponibil

resurse

R1 a11 a12 a1n d1 R2 a21 a22 a2n d2

Rm am1 am2 amn dm

beneficiu c1 c2 cn



Elemente de programare liniară

Deci PPL se poate enunţa astfel:Să se determine coordonatele 0x j ≥ ale lui Χ în condiţiile de nedepăşirea resurselor şi

obţinerea unui beneficiu maxim.

Modelul matematic devine:

( )

( ) n1, j 0x

m1,i ,

max

j

1

2211

=∀≥

=≤

+++

∑=

i

n

j

jij

nn

d xa

xc xc xc

Observaţie:

Dacă întreprinderea este obligată să producă cel puţin p sortimente de tip Sk , atunci apar şirestricţii de forma pxk ≥ , sau dacă întreprinderea nu are asigurată desfacerea decât pentru qsortimente de tip Sk atunci apar restricţii de forma qxk ≤

b) problemă de nutriţie

O dietă trebuie să conţină substanţe nutritivei

S în cantităţile mid i ,1, = ,ce se gasesc în

alimentele j A . Fie aij - cantitatile de substanta

iS conţinută in alimentul A j, .,1 n j = şi cij- costul

unitar al alimentului A j.Să se determine cantităţile x j de alimente necesare asigurarii nivelului cerut de substante

iS astfel încât costul total al dietei sa fie minim.

Reprezentăm datele într -un tabel:

Alimente

Substanţe A1…A2…A3 ………An

Cantităţ de substantă

S1 a11 a12 a13 ……. ..a1n d1

S2 a21 a22 a23 …….. a2n d2

.

.Sm

.

.am1 am2 am3 … amn

.

.dm

Cost c1………………………cn

Modelul matematic al problemei devine:

∑=

n

j

j j xc

1

min

mid xai

n

j

jij,1,

1

==∑=

( ) n j x j ,10 =∀≥

c) Problemă de transport

Acelaşi produs trebuie distribuit de la m –centre de producţie iF , mi ,1= ( furnizori) cătren-centre de desfacere (beneficiari ), ştiind că:




- cantitatea disponibilă la furnizoruluii

F estei

a ,

- cantitatatea necesar ă fiecărui beneficiar j B este

jb ,

- iar costul unitar de transport de la furnizoruliF către beneficiarul B j este

ijc .

A organiza optim transportul produsului de la cei m furnizori către cei n beneficiari revinela a determina cantităţile de produs ce trebuiesc transportate de la fiecare furnizor către fiecare

beneficiar, astfel incât costul total al transportului sa fie mimim. Altfel spus, revine la a determina planul optim de transport, echivalent cu determinarea matricii cantităţilor transportate

n jmiij

x X 1,1

===

pentru care costul total de transport este minim.

Notăm deci cuij x – cantitatea ce se transportă de la furnizorul

iF la beneficiarul

j B .

Considerând că totalul disponibil la toţi furnizorii este egal cu totalul necesar tuturor beneficiarilor , problema devine echilibrată, adică:

∑∑==

=n

j

j

m

i

j ba

11

Modelul matematic al problemei de transport este:

min ∑∑==

n

j

ijij

m

i

xc11

mia xi

m

j

ij,1,

1

==∑=

(totalul cantităţilor transportate de la furnizoruliF către toţi

beneficiarii să fie egal cu disponibilul său din depozit)

n jb x j

n

i

ij,1,

1

==∑=

(totalul cantităţilor transportate la beneficiarul j

B , trcând pe

la toţi furnizorii să fie egal cu necesarul său pentru desfacere)

( ) n j xij ,10 =∀≥ , mi ,1=

d) Problemă de amestec

Un produs se obţine din amestecul a n- materii prime M j , unitatea de materii prime M j

conţine aij unităţi de substanţăi

S , mi ,1= . Produsul trebuie sa conţină cel puţin dh , ph ,1= unităţi

de substanţă hS si cel mult dk , m pk ,1+= unităţi de substanţă k S ,costul unitar al materiilor prime

M j este c j . Să se determine x j cantităţile de materii prime M j ce trebuie să intre în componenţa produsului astfel încât costul lui sa fie minim.

Modelul matematic al problemei formulat ca o PPL este:

∑=

n

j

j j xc1

min

h

n

j

jhj d xa ≥∑=1

, ph ,1=

k

n

j

jkj d xa <∑=1

, m pk ,1+=

( ) n j x j ,10 =∀≥




e) Problemă privind alocarea eficientă a resurselor

Presupunem că avem la dispoziţie mai multe resurse limitate mi Ri ,1, = (forţă de muncă,

resurse financiare, materii prime, maşini unelte etc.) care permit desfăşurarea activităţilor

n j A j,1, = şi că se cunosc următoarele date:

- =ib disponibil din resursa ( )mii ,1= ;

- =ij

a coeficienţii tehnologici (cantitatea din resursa i necesară pentru producerea unei unităţi

din activitatea j; se presupune căija nu depinde decât de tipul resursei şi al activităţii);

- j

c = preţul de vânzare al unei unităţi din activitatea j;

- jd = preţul de cost unitar pentru produsul j.

Să se determine nivelele j x la care trebuie desfăşurate activităţile

j A astfel încât venitul total

realizat să fie maxim.

Modelul matematicdevine:[ ] ( ) ( )

( ) nT

n j

n

j

i jij

n

j

j j j

x xundeX n j x

mib xa

xd c x f

∈==≥

=≤

−=

∑

∑

=

=

,......,,1,0

,1,

max

1

1

1

f) Problemă privind repartizarea optimă a sarcinilor de producţie

Într-o întreprindere, diferite secţii pot produce cu eficienţe diferite aceleaşi produse. În afaracondiţiilor subiective care determină aceste eficienţe, mai acţionează şi factori obiectivi de care celînsărcinat cu organizarea ştiinţifică a producţiei trebuie să ţină seama în scopul realizării optimuluieconomic. Notăm:

- =i A produsele fabricate, mi ,1= ; j B =secţiile producătoare, n j ,1= ;

- =ij

a coeficienţii tehnologici; =ij

c preţul de cost al unei unităţi i A realizat în secţia

j B ;

=ib cantitatea planificată din produsuli

A ; = jt timpul de lucru disponibil în secţia j B ,sau

numărul de muncitori, sau totalul utilajelor disponibile în secţia j B etc.;

- =ij

x cantitatea din produsuli

A ce se realizează în secţia j B astfel încât cheltuielile totale să

fie minime.


[ ] ( )

n jmi x

n jt xa

mib x

xc x f

ij

m

j

jijij

n

j

iij

m

i

n

j

ijij

,1;,1,0

,1,

,1,

min

1

1

1 1

==≥

=≤

==

=

∑

∑

∑∑

=

=

= =




g) Problemă privind folosirea raţională a investiţiilor

Presupunem că, pentru o anumită ramură de producţie, cunoaştem:

- S = suma totală care poate fi investită în diferite activităţile n ja j,1, = ;

- = jc beneficiul asigurat de investiţii în activitatea n ja j ,1, =

- =*S suma minimă ce va fi consumată de activităţile nmmk ak <= ,,3, ;

Investiţia în activitatea a j=1,2, nu trebuie să depăşească suma investiţiilor în restulactivităţilor. Investiţia în activitatea j=1, din motive tehnice nu poate depăşi p% din activitateatotală.

Se cere să se determine suma j

x ce trebuie investită în activitate, astfel încât în cadrul sumei

alocate să se asigure obţinerea unui beneficiu total maxim.


[ ] ( ) ∑==

n

j

j j xc x f

1

max

≤+

≤

<≥

=

∑

∑

∑

=

=

=

n

j j

m

k

k

n

j

j

x x x

pS x

S S S x

S x

321

1

**

3

1

100

,

n jo x j ,1; =≥ , unde ( ) nT

n R x x X ∈= ,1

h) Problemă privind stabilirea structurii planului de producţie la unităţile deproiectare

Fie o întreprindere în care diferitele subunităţi efectuează aceeaşi lucrare cu costuri diferiteşi cu un consum de timp diferit, ca urmare a unor diferenţieri în ceea ce priveşte experienţaacumulată, dotarea tehnico-materială, pregătirea proiectanţilor etc. Notăm:

- i A = lucrările de proiectare din planul instituţiei, mi ,1= - = j B subunitatea de proiectare, m j ,1=

- =ija coeficienţii tehnologici, reprezentând numărul de ore de proiectare necesare pentru

efectuarea unei lucrării

A , de către subunitatea de proiectare j B ;

- =ijc preţul de cost al lucrăriii

A efectuată de j B

- =ij

x partea din lucrarea i A ce urmează a se efectua de către

j B astfel încât cheltuielile de

producţie să fie minime ( ij x sunt necunoscute)





[ ] ( )

∑

∑∑

=

==

==

=

n

j

ij

n

j

ij

m

i

mib x

c x f

1

11

,1,

min

n jt xam

j

jijij ,1,1

=≤∑=

n jmi xij,1,,1,0 ==≥

i) Problemă privind desfacerea mărfurilor

Presupunem că o unitate comercială vrea să-şi stabilească planul de desfacere pentru oanumită perioadă de timp. Condiţiile în care are loc desfacerea sunt caracterizate mai jos.

- =iP marfa de tipul nii ,1, = ;

- =i

a limita inferioară a planului de desfacere din marfa i în perioada considerată

( )ni ,1= ;

- =ib limita superioară a planului de desfacere din marfaiP în perioada considerată ( )ni ,1= ;

- =ic beneficiul realizat pe o unitate din marfaiP ex primat în unităţi monetare;

- =id necesarul de spaţiu de înmagazinare (magazii, rafturi etc.) pentru o unitate din marfa

iP ;

- =it timpul pentru desfacerea unei unităţi din marfa

iP ;

- =d capacitatea totală a spaţiului de înmagazinare; - t = timpul total de desfacere a mărfurilor. Notând

i x = cantitatea de marfă

iP desfăcută pentru care beneficiul total brut f este maxim,

obţinem modelul matematic:

[ ] ( )

=≤≤

≤

≤

=

∑

∑

∑

=

=

=

nib xa

t xt

d xd

xc x f

iii

n

i

ii

n

i

ii

n

i

ii

,1;

max

1

1

1

( ) nT

n R x xundeX ni x ∈==≥ ....,,,1,0 11

j) Problemă privind depozitarea mărfurilor

Fie o întreprindere comercială cu ridicata care se ocupă de procurarea şi repartizareamărfurilor organizaţiilor comerciale subordonate. Să presupunem că această întreprindere are un

număr m de depozitare pe care o notăm )m j D j,1= şi că are în subordine p organizaţii comerciale

notate cu ( ) pk C k

,1== .

Fie, de asemenea:

- iP = sortimentele de marfă ni ,1= ;




- =ija coeficienţii tehnologici (suprafaţa ocupată de o unitate de marfăi

P din capacitatea

totală a depozitului j

D );

- =ik b cantitatea de marfăiP necesară organizaţiei comerciale ( ) pk niC

k ,1;,1 == ;

- =ijk

C costul transportului unei unităţi de marfă ( )niPi ,1= depozitată în centrul )m j D j ,1=

la organizaţia comercială ( ) pk niC k ,1;,1 == ;- =ijk x cantitatea de marfă

iP depozitată în centrul

j D şi transportată la organizaţiak C .

Vrem să determinăm cantităţileijk

x astfel încât cheltuielile de trans port să fie minime.


[ ] ( )

=≤

=

∑ ∑

∑ ∑ ∑

= =

= = =

n

i

p

k

ijk ij

n

i

m

j

p

k

ijk ijk

m j xa

xC x f

1 1

1 1 1

,1,1

min

( ) pk m jniijk

ijk

m

j

ijk

xundeX

pk mk ni x

pk ni x

,1,,1,,1

1

,,1,,1,,1,0

,1,,1,0

===

=

=

===≥

==≥∑

Exemplu numeric:

O întreprindere urmăreşte maximizarea beneficiului în întocmirea planului de producţie la 3

produse 1P , 2P şi 3P din două materii prime 1 M şi 2 M , cu un disponibil de 60, respectiv 50 unităţi.

Coeficienţii tehnologici pentru aceste materii prime sunt daţi în tabelul de mai jos:

1P 2P 3P 1 M 4 1 2

2 M 1 2 1

Planul de producţie la 2P şi 3P nu trebuie să fie mai mare de 40 u. Beneficiile unitare aduse

de 1P , 2P şi 3P sunt de 18, 20 şi respectiv 15 u.

Modelul matematic devine:[ ] ( )

( ) 3

3213,2,1

32

321

321

321

,,;0

40

502

6024

152018max

R x x xundeX x

x x

x x x

x x x

x x x x f

T ∈=≥

≤+

≤++

≤++

++=

2.2. Formularea problemei de programare liniară

O problemă de programare matematică reprezintă determinarea optimului (maximului sauminimului) unei funcţii de variabilă vectorială care îndeplineşte anumite condiţii (restricţii, legături)de tip inecuaţii sau ecuaţii, precum şi condiţii de nenegativitate ale variabilelor funcţiei. Dacă toate




funcţiile care intervin în formularea problemei de programare matematică sunt liniare, atunci problema se numeşte problemă de programare liniară (PPL); În caz contrar, problema se numeşte problemă de programare neliniară.

Modele matematice pentru PPL:

1) Forma standard – este cea care conţine restricţii de tip ecuaţii:

- optim z= ( )nn

xc xc xc xc +++ ....332211

- restricţii de tip egalitate:

=+++

=+++

=+++

mnmnmm

nn

nn

d xa xa xa

d xa xa xa

d xa xa xa

....

............................................

....

....

2211

22222121

11212111

- condiţii de nenegativitate: 0,,0,0 21 ≥≥≥ n

x x x

Matriceal, forma standard poate fi exprimată astfel:

≥

=

0

X

D AX

X C optim T

undemxnija A = ,

( )

( )

( )T m

T

n

T

n

d d d D

cccC

x x x X

...,

,...,,

,...,,

21

21

21

=

=

=

Observaţii:

Dacă restricţiile sunt de tip inegalitate, acestea pot fi aduse la forma unor restricţii de tipegalitate (adică cele cerute de forma standard) prin adunarea (sau scăderea) unui termen numit

variabilă ecart sau variabilă de compensare. - ( ) X C xc x z T

n

j

j j == ∑

=1

- se numeşte funcţie obiectiv ( funcţie economică, funcţie eficienţă);

- spaţiul R n al vectorului X ,respectiv C - se numeşte spaţiul activităţilor economice; - vectorul m

R D∈ se numeşte vectorul resurselor; - spaţiul R m se numeşte spaţiul resurselor .

2) Formele canonice

a) Pentru problema de minim:

≥

≥

0

min

X

D AX

X C T

b) Pentru problema de maxim:

≥

≤

0

max

X

D AX

X C T

Definiţii:

- ( )t

n x x x X ,,, 21 = care verifică sistemul de restricţii se numeşte soluţia problemei (soluţie posibilă);

- o soluţie X a restricţiilor care verifică condiţiile de nenegativitate se numeşte program sau




soluţie admisibilă;

- programul X pentru care se realizează extremul solicitat al funcţiei se numeşte program

optim.

Fie problema de programare liniară în forma standard. Presu p u nem rang A =m şi m<n. Rezultă că sistemul d e restricţii este compatibil

nedeterminat; s-a presupus eliminarea ecuaţiilor secundare.

NotămiV -vectorii coloană ni ,1= ai matricei A , m

i RV ∈ ; atunci sistemul de restricţii se

poate scrie: DV xV xV x nn

=+++ ...2211

Fie B o bază în spaţiul m R . Notăm Bi ∈ pentru

iV unul din vectorii bazei B.

Fie B

X notaţia pentru soluţia de bază corespunzătoare bazei B.

Definiţie: O bază B care conduce la un program se numeşte baza admisibilă, iar dacă B

X nueste program, spunem că B este doar posibilă.

Deci, a rezolva o problemă de programare liniară revine la a determina un program de bază ( soluţie admisibilă de bază) pentru care funcţia obiectiv atinge optimul dorit, minim sau maxim. Înacest sens, soluţia căutată se numeşte program optim de bază.

2.3. Metoda Simplex - Determinarea soluţiilor primal admisibile, de bază,ale P.P.L. (program de bază iniţial)

Fie problema PPL standard:

0

z[min]

≥=

=

X D AX

X C T

.

Considerăm sistemul compatibil

AX=D, )mxnija A = ,n>m,

rang A=m, A=(V1, V2 ,… Vn),m

i RV ∈ ;

( )T n x x x X ,...,, 21= este solutia sistemului ,dacă:

DV xV xV x nn =+++ ...2211

Definiţii:

Vectorul X este o soluţie de bază a sistemului, dacă vectoriii

V corespunzători coordonatelor

nenule ale sale sunt liniari independenţi. Soluţia de bază se numeşte nedegenerată dacă are chiar m coordonate nenule, în caz contrar

numindu-se degenerată.Cum rang A=m, putem detaşa din A o matrice nesingulară B. Dacă B este bază a matricei A,

deci a spaţiului R m, vom nota matricea rămasă cu S , adică matricea formată din vectorii coloană ailui A care nu fac parte din bază. Partajăm şi vectorul X în B

X respectiv S X , unde B X conţine

necunoscutele principale (variabile bazice), iar S X pe cele secundare (variabile nebazice).

Sistemul se poate scrie:

D X S X B D X

X S B D X A S B

S

B

=⋅+⋅⇔=

⋅⇔=⋅ )(




şi înmulţind la stânga cu B-1 se obţine soluţia sistemului S B X S B D B X ⋅⋅−⋅= −− 11

Pentru XS=0⇒ Bnot

B D D B X =⋅= −1

Deci coordonatele în baza B, ale vectorului D al termenilor liberi din sistemul de restricţii,reprezintă soluţia de bază corespunzătoare lui B.

Soluţia sistemului, scrisă pe coordonate este: B

i x =

∉

∈

Bidaca

Bidacad Bi

0

Aceasta este deci nedegenerată pentru toate coordonatele lui DB nenule şi degenerată în cazcontrar.

Observaţii:

i) Fiecărei baze din A îi corespunde o soluţie de bază . Reciproc nu este adevărat. O soluţiede bază poate corespunde mai multor baze.

ii) Numărul maxim de soluţii de bază ale unui sistem este m

nC .

Observăm că, exprimând vectorii coloană iV ai matricei A descompuşi în baza B, se obţine onouă matrice AB, numită matricea redusă a matricei A, corespunzătoare bazei B.

Astfel , coloanele lui AB sunt coordonatele vectorilori

V in baza B, daţi de relaţia:

B-1i

V = A B AV B B

i

1−=⇔

De asemenea se poate observa pe exemplul anterior că forma redusă conţine o matriceunitate U m formată din coloanele vectorilor unitari (baza canonică a spaţiului resurselor R

m ).

Pentru determinarea formei reduse se foloseşte metoda eliminării complete, prin eliminareasuccesivă a câte unui singur vector din bază. În tabelul de mai sus reliefăm calculele coordonatelor

lui D în bazele succesive, obţinute prin înlocuirea în bază a câte unui vector din A.În final se obţine soluţia de bază a sistemului restricţiilor PPL:

X=B-1D=DB.

2.4. Teoremele algoritmului Simplex (criteriul de ieşire din bază, criteriulde optim, criteriul de intrare în bază, criteriul de optim infinit)

Algoritmul SIMPLEX nu rezolvă o PPL, ci doar optimizează un program de bază al PPL.Algoritmul aplică un criteriu de optim pentru a interoga dacă programul de bază este sau nu optim.

În cazul în care răspunsul este afirmativ, atunci algoritmul se opreşte, oferind programul optim de bază pentru care funcţia obiectiv ia valoarea optimă. Dacă răspunsul este negativ, atunci seconsideră ca vinovată de acest lucru baza corespunzătoare programului de bază interogat. În acest

B D V1 V2… Vk …Vn e1 e2 ...ek ...en e1

e2

.

.

.eh

.

.

.

em

d1

d2

.

.

.dh

.

.

.

dm

a11 a12… a1k ….a1n a21 a22… a2k … a2n

. .

.ah1 ah2…ahk ….ahn

.

.

.

am1 am2…amk …amn

1 0 0 ...0 01 0 0 ....0 0

...0 0 1... 0 0...0 0 0....0 1




caz se trece la îmbunătăţirea soluţiei prin schimbarea bazei, lucru care se face eliminând un vectordin bază şi înlocuindu-l cu un alt vector al matricii. Atât eliminarea vectorului din bază, cât şiintroducerea unui alt vector care sa-l înlocuiască se fac după anumite criterii, numite criteriul deieşire din bază, respectiv criteriul de intrare în bază.

Urmărim să impunem condiţia de nenegativitate asupra soluţiei de bază, astfel încât sădeterminăm un program de bază, pe care mai apoi sa-l testăm dacă este optim (să verifice optimulcerut pentru funcţia obiectiv), adică sa obţinem un criteriu de optim.

Aşadar, dacă vectorul Vk intră în bază şi vectorul eh iese, se obţine o nouă bază B1 şi, cutransf ormările de coordonate la schimbarea bazei datorate aplicării regulei pivotului ahk ≠0 se obţinrelaţiile:

≠−

=

=

hia

ad ad

a

d

d

Bhk

Bik

Bh

Bhk

Bi

Bhk

Bh

Bi

,

hi,

1

Se pune problema determinării pentru sistemul compatibil AX=D, mxnija A = ,n>m rang

A=m, a acelor soluţii de bază pentru care 0≥ B

X .

Cum B

i x =

∉

∈

Bidaca

Bidacad Bi

..0

. atunci 0≥

B

X 0≥⇔ B D , condiţie care conduce la formularea

criteriului de ieşire din bază.

Criteriul de ieşire din bază: Dacă în bază intră vectorul V k , atunci din bază se elimină vectorul V h care îndeplineşte

condiţia:

Bi,inf 0

∈∀

=> B

ik

Bi

a Bhk

Bh

a

d

a

d

Bik

Avem descompunerea:A=(B,S), unde

miii V V V B ,,,

21= ,

mn j j j V V V S

−= ,,,

21

şi corespunzător, descompunerea vectorului

=

S

B

X

X X în variabile bazice şi nebazice ;

=

S

B

C

C C ;

Sistemul de restricţii devine:

⇔= D AX ( ) D X X S B

S

B

=

, ⇔ DSX BX S B =+ .

Dacă notăm B

jV S B =−1 atunci soluţia sistemului de restricţii devine:

∑∈

−=S j

j

B

j

B B X V D X

sau, scrisă pe componente,

∑∈

∈−=S j

j

B

ij

B

i

B

i xad x Bi, .

Înlocuind în funcţia obiectiv, se obţine:

∑ ∑∑∑∑ ∈ ∈∈∈∈

−+=+==

S j

j Bij

Bi

i j

Bi

Bii

S j

j j

Bi

iit xaccd c xc xc X C z .

Dacă notăm:




∑∈

= Bi

Bii

Bd c z valoarea funcţiei obiectiv corespunzătoare programului de bază

B

x ,

Bij

Bi

i B j ac z ∑

∈

= ,

obţinem:

( ) j

S j

B j j

B x zc z z ∑∈

−+= . (*)

Se pot enunţa deci următoarele criterii folosite de algoritmul de optimizare:

Criteriul de optim pentru PPL:

Programul de bază B

x este optim pentru problema de minim dacă:

S j,0 ∈∀≥− B

j j zc

Observaţie: pentru o problemă de maxim, inegalitatea se schimbă.

Criteriul de intrare în bază:

Pentru problema de minim: d acă S ,0 ∈<−∃ j zc B

j j , atunci programul

B

x nu este optim

şi programul se îmbunătăţeşte dacă vectorul V k intră în bază, unde:

V k este vectorul coloană al matricii A pentru care

S ,0inf ∈<−=− j zc zc B

j j

B

k k

Observaţie: Dacă indicele k pentru care se verifică relaţia criteriului de intrare în bază, nu este unic

determinat, atunci regula adoptată pentru o valoare a funcţiei obiectiv cât mai apropiată de valoareaminimă:

„Dacă ,0 <−∃ B

k k zc intră în bază vectorul V k pentru care inf B j j

Bk k zc zc −=− ”

la o problemă de maxim, devine:

„Dacă ,0 >−∃ Bk k zc intră în bază vectorul V k pentru care sup B

j j Bk k zc zc −=− ”

Criteriul de optim infinit:

Dacă 0 <−∃ B

j j zc şi { } inf B

j j

B

k k zc zc −=− , Bia B

ik ∈∀≤ 0 , atunci spunem ca PPL

admite un optim infinit şi algoritmul de optimizare se opreşte.

2.5. Enunţarea algoritmului SIMPLEX

Algoritmul SIMPLEX oferă soluţia optimă a PPL (program optim de bază), plecând de la osoluţie primal admisibilă de bază (program de bază). Îl enunţăm pentru problema de minim.

a) Se determină o bază admisibilă B şi se calculează:

- programul de bază corespunzător: B

x B

D D B == −1

n jV BS BV j B j ,1,11 === −−

- valoarea funcţiei obiectiv:




∑∈

− === Bi

Bii

T B

BT B

Bd c D BC xC z 1

Bij

Bi

i B j ac z ∑

∈

=

- diferenţele: B j j zc − = n jV C c B

jT B j ,1, =− ; B j zc B

j j ∈=− ,0

Datele se introduc într-un tabel SIMPLEX:baza coef sol

1c 2c ….........

nc Baza unitară

B CB DB V1 V2…......... Vn eV 1 eV 2 ..

e

mV

eV 1

1ic

1i x 1,1ia

2,1ia ................. nia ,1

eV 2

2ic 2i x 1,2i

a 2,2i

a ................. nia ,2

.

.

.

.

.

.

.

.

.

.

.

.

. .

. .

. .emV

mic mi x 1,mi

a 2,mi

a ............... nima ,

B z

B z1 B

z2 ............. Bn z

B

j j j zc −=∆ B

zc 11 − B zc 22 − ... B

nn zc −

b) Se aplică testul de optim

Dacă n j zc B j j ,1,0 =≥− , atunci programul

B x este optim şi STOP.

Dacă nu, adică S j ,0 ∈<−∃ B

j j zc atunci programul B

x nu este optim şi se trece la

îmbunătăţirea bazei prin aplicarea criteriului de intrare în bază: intră în bază vectorul V k pentru care inf B

j j Bk k zc zc −=−

c) Se aplică testul de optim infinit

Dacă nia B

ik ,1 0 =∀≤ , atunci problema admite optim infinit şi STOP.

d) Dacă 0 >∃ Bik a atunci se aplică criteriul de ieşire din bază, adică iese din bază vectorul V h

pentru care:

Bi,inf 0

∈∀

=> B

ik

Bi

a Bhk

Bh

a

d

a

d

Bik

.

Se obţine o nouă bază B1 şi se reia algoritmul de la punctul b), iar ieşirea din el are loc fie la punctul b) (testul de optim), fie la punctul c) (testul de optim infinit).

Deci: algoritmul SIMPLEX testează condiţia de optim pentru programul de bază găsit şi,

în caz că aceasta nu este satisfăcută, va determina un alt program de bază care va apropia

funcţia obiectiv de valoarea optimă, iar în final va determina valoarea sa optimă.

Observaţii:

a) Pentru o problemă de maxim se schimbă semnul inegalităţii în criteriul de optim şi infimumdevine supremum la criteriul de intrar e în bază.

b) Diferenţa din criteriul de optim poate fi B

j j j zc −=∆ sau j

B

j j c z −=∆ şi atunci evident că

se schimbă şi semnul din criteriul de optim. c) Dacă criteriile decid că B

hk a este pivot (în tabel coincide cu celula aflată la intersecţia

vectorului coloană care intră în bază cu linia vectorului vare părăseşte baza), atunci în tabelul




SIMPLEX toţi vectorii coloană îşi vor schimba coordonatele în noua bază, după transformărileelementare din procedeul Gauss Jor dan, adică după regulile:

i) linia pivotului se împarte element cu element la pivot şi rezultatele se completează pe liniacorespunzătoare din iteraţia în curs.

ii) coloana pivotului se completează cu 0 până se obţine vectorul unitar al bazei canonice. iii) orice alt element din tabel se transformă după regula dreptunghiului (a pivotului): p…....a

b…... x ; unde x devine x’=(px-ab)/p , p

ab x x −='

2.6. Metoda bazei artificiale (a celor două faze şi a penalizării) Fie forma standard a unei P.P.L.

0

[min]z

≥

=

=

X

D AX

X C T

Dacă matricea sistemului de restricţii nu conţine vectorii unitari care alcătuiesc bazacanonică necesară determinării unei soluţii iniţiale de bază , recurgem la metoda bazei artificiale

prin introducerea variabilelor artificiale 0≥a

k x şi se rezolvă problema de programare liniară: ( )

( ) 0;0 ≥≥

=+a

a

X X

D IX AX

Avem următorul rezultat teoretic :Orice soluţie posibilă a problemei iniţiale este o soluţie posibilă a programului extins pentrucare valorile tuturor variabilelor artificiale sunt nule şi reciproc orice soluţie a programuluiextins în care toate variabilele artificiale sunt nule, este o soluţie a programului iniţial după

inlăturarea acestora. Deci problema iniţială are soluţii dacă şi numai dacă sistemul extins al restricţiilor are soluţii de

forma( )

( ) 0,0 =≥

a

a X cu

X

X

O astfel de problemă se rezolvă prin metoda celor două faze:

Faza I . În această fază se rezolvă problema:[ ] ( )

( )

( ) 0;0

min 1

≥≥

=+

=

a

a

a

X X

D IX AX

X z

La sfârşit putem avea următoarele situaţii :1) [ ] 0min 1 = z deci toate variabilele artificiale sunt nule şi nici o variabilă artificială nu este bazicăfaţă de soluţia optimă. În acest caz dispunem de o soluţie de bază a programului extins din care prinînlaturarea variabilelor artificiale se obţine o soluţie de bază a programului iniţial şi se trece la fazaa II-a2) [ ] 0min 1 = z şi cel puţin o variabilă artificială este bazică, ea trebuind eliminată astfel:

- dacă pe linia variabilei artificiale există elemente nenule (rang A=m) alegem unul dintreacestea drept pivot şi facem încă o iteraţie pentru a o elimina din bază .

- dacă pe linia variabilei artificiale nu avem elemente nenule (rang A<m), o vom neglija suprimând-o din tabel . Se trece la faza a II-a.

3) [ ] 0min 1 > z problema iniţială nu are soluţie de bază (vezi exemplul de mai jos) Faza a II-a . În această fază se elimină din ultimul tabel simplex coloanele variabilelor

artificiale şi se continuă algoritmul introducând coeficienţii funcţiei obiectiv z=C T X . Dacă în bază




au mai rămas variabile artificiale nenule, aceasta este dovada că problema iniţială nu admite soluţii(exemplul de mai jos).

Construcţia unei baze iniţiale unitare pentru pornirea algoritmului simplex, în situaţia că nuexistă în matricea sistemului, sau nu este completă, revine deci la a construi o bază artificială.

În varianta metodei penalizărilor , problema iniţială se înlocuieşte cu o problemă modificată, pe care o putem numi problema extinsă:

( ) ( )

( )

( ) 0;0

min

≥≥

=+

+=

a

a

aT T

X X

D IX AX

X M X C z

cu i R M M i ∀∈= ,* , suficient de mare, numit coeficient de penalizare (pentru max z se scade( )aT

X M ).Deci, varianta penalizării modifică funcţia obiectiv, introducând vectorii artificiali cu acesti

coeficienţi. Cum pentru aceştia nu există corespondent în interpretarea economică a rezultatelor,rezultă evident că, ei vor fi folosiţi doar în scopul construcţiei bazei artificiale necesare unei bazeunitare, primal admisibile , algoritmul trebuind în final să-i excludă din programul optim de bază.

Aşa se explică de ce coeficienţii de penalizare au valori pozitive foarte mari, cu semnul plus la problemele de minim, respectiv minus la cele de maxim.

În iteraţiile succesive, algoritmul simplex înlătură bazele pentru care funcţia obiectiv nu eoptimă, deci va excludere din bază vectorii artificiali. Dacă nu, atunci spunem că P.P.L. iniţială nuare soluţie posibilă de bază şi deci nu are soluţie optimă. Observaţie :

Dacă un vector artificial a fost înlăturat din bază, putem să nu mai calculăm în iteraţiile următoarecoordonatele lui din matricea redusă a noii baze. Dacă însă ne interesează inversa bazei optime,

pentru verificarea soluţiei optime sau alte calcule care o implică, completăm în tabloul simplex şicoloanele vectorilor artificiali ieşiţi din bază. Avem următorul rezultat teoretic :

Dacă problema iniţială are program optim de bază, acesta este şi pentru problema extinsă program optim de bază şi reciproc.

Este suficient deci să rezolvăm problema extinsă, plecând de la o soluţie primal admisibilă de bază:

( ) ( ) ( ) ( )( )t a

m

aaa B B

x x x X Bcu D X ,,,, 21 === .

Probleme Rezolvate:

Algoritmul SIMPLEX

1. Să se rezolve problema de programare liniară:

[ ] ( ) 321 152018max x x x x z ++=

≤+

≤++

≤++

40

502

6024

32

321

321

x x

x x x

x x x

03,2,1 ≥ x

Soluţie: Se aduce la forma standard de lucru transformând inegalităţile în egalităţi cu ajutorul

variabilelor de compensare03,2,1 ≥ y

.




[ ] ( ) ( )321321 0152018max y y y x x x x z ++⋅+++=

=++

=+++

=+++

40

502

6024

332

3321

1321

y x x

y x x x

y x x x

0,0 3,2,13,2,1 ≥≥ y x

Matricea noului sistem de restricţii conţine vectorii unitari, deci baza primal admisibilă este:

},,{ 321 y y y B =

CB B B X

18 20 15 0 0 0 C j

1a 2a 3a 4a 5a 6a θ

000

a4

a5

a6

605040

410

121

211

100

010

001

60/150/240/1

0 0 0 0 0 0 0 z j

j∆ 18 20 15 0 0 00200

a4

a2

a6

352515

[ 7/2]1/2-1/2

010

3/21/21/2

100

-1/21/2-1/2

001

1050-

500 10 20 10 0 10 0 z j

j∆

8 0 5 0 -10 0

1820

0

a1

a2

a6

1020

20

10

0

01

0

[3/7]2/7

5/7

2/7-1/7

1/7

-1/74/7

-4/7

00

1

70/370

28580 18 20 94/7 16/7 62/7 0 z j

j∆

0 0 11/7 -16/7 -62/7 0

15200

a3

a2

a6

70/340/310/3

7/3-2/3-5/3

010

100

2/3-1/3-1/3

-1/32/3-1/3

001

1850/3 65/3 20 15 10/3 25/3 0 z j

j∆

-11/3 0 0 -10/3 -25/3 0

B

j j zc j −=∆

Soluţia optimă este:

=

=

=

3

70

3

40

0

3

2

1

x

x

x

3

10

0

3

21

=

==

y

y y

[ ] ( )

3

850.1max = x z

Verificare:

=

−−−

−

== −

310

340

370

4050

60

13

13

103231

03

13

2

1

D B X

B




Probleme Rezolvate:

Metoda bazei artificiale (a celor două faze şi a penalizării)

1. Să se rezolve următoarea P.P.L.

[ ] ( )

0

1832

4

43min

2,1

21

21

21

≥

≥+

≤+

+−=

x

x x

x x

x x x z

a) prin metoda penalizării. b) prin metoda celor două faze.

Soluţie: a) Aducem P.P.L la forma standard. Introducând y1, y2 variabile de compensare se observăca matricea sistemului de restricţii conţine doar un vector unitar, y1.

[ ] ( ) ( )

,0,0

1832

4

043min

2,12,1

221

121

2121

≥≥

=−+

=++

+++−=

y x

y x x

y x x

y y x x x z

În completarea bazei unitare, se adună vectorul unitar care lipseşte la ecuaţia a doua a

sistemului, adică variabila artificială a. { }

==⇒ 10

01,1 a y B . Fie M>0 coeficientul de penalizare

cu care intră variabila artificială in funcţia obiectiv. Obţinem problema extinsă:

[ ] ( )

( ) 5

21212,12,1

221

121

21

,,,,0,0,0

1832

4

43min

Ra y y x x X undea y x

a y x x

y x x

a M x x x z

T ∈=≥≥≥

=+−+

=++

⋅++−=

pentru care aplicăm algoritmul simplex:

BC B B X

-3 1 0 0 M jc

1 x 2 x 1 y 2 y a θ

0M

y1

a418

12

11

10

0-1

01

46

z j 18M 2M 3M 0 -M M j∆ 2M+3 3M-4 0 -M 0

4M

x2

a46

1-1

10

1-3

0-1

01

z j 6M+16 4-M 4 4-3M -M M j∆ 7-M 0 4-3M -M 0




Întrucât toate diferenţele 5,1,0 =≤−=∆ jc z j

B

j j, condiţia de optim este îndeplinită, algoritmul se

opreşte, dar, se observă că în baza optimă a rămas variabila artificială (de penalizare) a, cu a>0, deciP.P.L nu are soluţie.

b) Metoda celor 2 faze

Faza I. Rezolvăm P.P.L.:

[ ]

0,0,0

1832

4min

2,12,1

221

121

1

≥≥≥

=+−+

=++=

a y x

a y x x

y x x

a z

BC

B B

X 0 0 0 0 1 j

c

1 x 2 x 1 y 2 y a θ

01

y1

a4

1812

11

10

0-1

01

46

j z1 18 2 3 0 -1 1 j∆ 2 3 0 -1 0

01

x2

a46

1-1

10

1-3

0-1

01

j z1

6 -1 0 -3 -1 1 j∆ -1 0 -3 -1 0

Întrucât toate diferenţele 06[min]5,1,0 11 >===≤−=∆ a zdar jc z j j B

j , P.P.L nu are soluţie.

2. Să se rezolve programul liniar :

[ ] 4321 32max x x x x f ++−=

=++

=+−=++−

42

11

321

421

321

x x x

x x x x x x

41,0 ≤≤≥ i xi

Soluţie :

−

−

=

0211

1011

0111

A

În A avem un vector coloană unitar 4

a

( )

t 0,1,0=

deci adăugăm sistemului de restricţiinumai două variabile artificiale

a x5 la prima ecuaţie şi

a x6 la ultima ; rezolvăm problema prin celedouă faze :

Faza I . Rezolvăm programul liniar . [ ] aa x x f 651min +=

=+++

=+−

=+++−

42

1

1

6321

421

5321

a

a

x x x x

x x x

x x x x

0,0,41,0

65

≥≥≤≤≥ aa

i x xi x

Avem tabelul simplex :




0 0 0 0 1 1

Bc B B x 1a 2a 3a 4a 5a 6a

1 5a 1 -1 1 1 0 1 0

04a 1 1 -1 0 1 0 0

1 6a 4 1 1 2 0 0 1

j f 5 0 2 3 0 1 1

j j f c − 0 -2 -3 0 0 0

03a 1 -1 1 1 0 1 0

04a 1 1 -1 0 1 0 0

1 6a 2 3 -1 0 0 -2 1

j f 2 3 -1 0 0 -2 1

j j f c − -3 1 0 0 2 00

3a 5/3 0 2/3 1 0 1/3 1/3

04a 1/3 0 -2/3 0 1 2/3 -1/3

01a 2/3 1 -1/3 0 0 -2/3 1/3

j f 0 0 0 0 0 0 0

Faza a II a :2 -1 3 1

CB B XB a1 a2 a3 a4

3 a3 5/3 0 2/3 1 01 a4 1/3 0 -2/3 0 12 a1 2/3 1 -1/3 0 0

f j 20/3 2 2/3 3 1c j-f j 0 -5/3 0 0

Rezultă[ ]

3

20max = f

şi pentru ( )t x 3/1,3/5,0,3/2= soluţie nedegenerată.

3. Să se rezolve problema de programare liniară :

=≥

≥++≥++

++=

3,1,0

8725432

384)min(

321

321

321

i x

x x x x x x

x x x z

i Soluţie: Se aduce modelul la forma standard, aici introducând două variabile de compensare u,v:

( )

≥=≥

=−++

=−++

+⋅+++=

0,,3,1,0

8725

432

0384)min(

321

321

321

vui x

v x x x

u x x x

vu x x x z

i

Acest model nu are o bază formată din vectori unitate, deci se impune introducerea a douăvariabile artificiale p,q în completarea bazei canonice. Să utilizăm metoda bazei artificiale cu

coeficienţi de penalizare. Aceste variabile modifică funcţia obiectiv, intrând cu coeficienţi nenuli,




aşa numiţii coeficienţi de penalizare (de regulă foarte mari şi pozitivi pentru ca, în fina l, algoritmulcare păstrează valorile minime ale funcţiei obiectiv, sa-i elimine din soluţia de bază). Putem alege ovaloare numerică pentru aceşti coeficienţi, de exemplu 100=λ , evitând astfel evaluarea semnului

expresiilor algebrice in λ pentru diferenţele B

j j j zc −=∆

( ) ( )

≥≥=≥

=+−++

=+−++

+⋅++⋅+++=

0,,0,,3,1,0

8725

432

1000384)min(

321

321

321

q pvui x

qv x x x

pu x x x

q pvu x x x z

i Pentru acest model, iteraţiile simplex sunt prezentate în continuare:

4 8 3 0 0 100 100

B BC

B D 1 x 2 x 3 x

u v p q

pq

100100

48

25

12

37

-10

0-1

10

01

B

z 1200 700 300 1000 -100 -100 100 100?0≥∆

j NU j∆ -696 -292 -997 100 100 0 0

p 100 4/7 -1/7 1/7 0 -1 3/7 1 -3/7

3 x 3 8/7 5/7 2/7 1 0 -1/7 0 1/7 B

z 424/7 -85/7 106/7 3 -100 297/7 100 *

?0≥∆ j NU j∆ 109/7 -58/7 0 100 -297/7 0 *

v 0 4/3 -1/3 1/3 0 -7/3 1 * *

3 x

3 4/3 2/3 1/3 1 -1/3 0 * * B

z

4 2 1 3 -1 0

?0≥∆ j DA j∆ 2 7 0 1 0 * *

Soluţia problemei este deci:

(min)z=4; 1 x = 2 x =0; 3 x =4/3;u=0;v=4/3.

Aplicaţii Propuse 1.

54321 9324)([min] x x x x x x f +++−=

=+−

=−+

=+++

13

552

223

421

432

542

x x x

x x x

x x x

5,1,0 =≥ i xi

2.

213)([min] x x x f +−=

=++−

=++

142

421

321

x x x x x x




4,1,0 =≥ i xi

3.

21 3)([min] x x x f −−=

≤+−

≤−

3

42

21

21

x x

x x

2,1,0 =≥ i xi

4.

321 423)([min] x x x x f −+−=

≤++−

≤−+

≤++

14

2

92

321

321

321

x x x

x x x

x x x

3,1,0 =≥ i xi

Test grilă de autoevaluare

1. Utilizaţi algoritmul Simplex pentru:

0,,

14425

19537

46(min)

≥

=++

=++

++=

z y x

z y x

z y x

z y x f

a. R: x=2,y=1,z=1; optim 17.

b. R: x=0,y=3,z=2; optim 11.c. R: x=-1,y=9,z=2; optim 11.2. In cadrul unei livezi sunt destinate 8 ha de teren pentru a se cultiva doua feluri de

plante A şi B. Investiţiile necesare pe hectar sunt respectiv de 2000 u.m. şi 5000 u.m. iar câştigulnet pe ha este de 30000 u.m., respectiv 60000 u.m. Se investesc 25000 u.m. în cultura celor douafeluri de plante. Pe câte ha trebuie cultivate fiecare din aceste plante, pentru ca să se obţină un

beneficiu cât mai mare?

a. R: 3;3 21 == x x ; optim 330000.

b. R: 5;321

== x x ; optim 390000.

c. R: 3;5 21 == x x ; optim 330000.

Bibliografie

Manual: Radu Despa, Marilena Aura Din, Cristina Coculescu, Cătălina Vișan, Ovidiu Solomon,Carmen Țirdă, Maria Gogâltan, Adam Altăr Samulel, Matematici aplicate în economie, Ed.Universitară 2012, București, 281 pagini, ISBN: 978-606-591-539-8.

1. Bădin V.şi colab. – Culegere de probleme de matematici aplicate în economie, UniversitateaRomâno – Americană Bucureşti 1998;

2. Cenuşă Ghe.şi colab. – Matematici pentru economişti, Editura Cison, Academia de StudiiEconomice Bucureşti 2000;




3. Despa R. Şi colab. - Matematici aplicate în economie, Editura Universitară UniversitateaRomâno-Americană, 2006;

4. Din Marilena A.– Matematici pentr u economişti – Editura Europolis, Constanţa 2003; 5. Popescu O. şi colab. – Matematici aplicate în economie, Vol. I şi II, Editura Didactică şi

Pedagogică, Bucureşti 1993;

2.elem. programare liniară

Documents