1

PROGRAMARE LINIARĂ

#1. Scurt istoric.

Progamarea liniară, ca disciplină matematică, a apărut la mijlocul

secolului nostru, primele lucrări fiind publicate de L. Kantorovici (1939) şi F.

Hitchcock (1941).

Primele probleme rezolvate se refereau la organizarea optimă a

transporturilor maritime, necesităţile de aprovizionare a frontului, planificarea

misiunilor aviaţiei de bombardament.

În 1947 G. Dantzig şi J. Von Newmann creează metoda simplex care stă

la baza rezolvării problemelor de programare liniară. Ulterior programarea

liniară a cunoscut un mare avânt prin lucrările unor matematicieni şi economişti

ca T. Koopmans, L. Ford, D. Fulkerson, W. Cooper, H. Kuhn, găsindu-şi un

câmp foarte larg de aplicaţii în economie.

Necesităţile reale ale vieţii economice au condus la apariţia şi

dezvoltarea altor tipuri de programări, cum ar fi:

programarea pătratică,

programarea convexă,

programarea în numere întregi,

programarea stohastică,

programarea dinamică,

toate acestea fiind înglobate în termenul generic de programare matematică.

#2. Exemple de probleme de programare liniară

a) Problema planului optim de producţie.

Fie maşinile M M Mn1 2, ,..., care fabrică sau consumă produsele

P P Pm1 2, ,..., , în cantităţi date pe unitatea de timp, anume aij din Pi pentru

maşina M i m j nj , ,1 1 . (Dacă M j produce în unitatea de timp

cantitatea aij din Pi atunci aij 0 , dacă consumă atunci aij 0 , iar dacă

aij 0 , M j nu produce şi nu consumă Pi ). Producţia (respectiv consumul)

produsului Pi nu trebuie să fie sub limita (respectiv să depăşească)

b bi i, 0 (respectiv bi dacă bi 0 ) pentru 1 i m .

2

Fie x j timpul de funcţionare al maşinii M j , iar c j beneficiul obţinut

prin funcţionarea lui M j în unitatea de timp, 1 j n . Un sistem de numere

reale x x xn1 2, ,..., constituie un plan optim de producţie, dacă maximizeză

beneficiul total adică funcţia:

f c xj j

j

n

1

în condiţiile restrictive:

a x b i mij j i

j

n

, 1 01

şi x j .

Dacă c j reprezintă costul funcţionării maşinii M j în unitatea de timp,

atunci se va cere minimizarea funcţiei de cost f c xj j

j

n

1

.

b) Problema dietei (a amestecului).

Să se determine cantităţile x j din alimentele Aj , 1 j n , alcătuind o

dietă x xn1,..., astfel încât costul acesteia f c xj j

j

n

1

să fie minim, unde

c j reprezintă costul unitar al alimentului Aj , dacă se mai cunoaşte componenţa

în substanţe nutritive S S Sm1 2, ,..., (cum ar fi: glucide, lipide, vitamine) a

alimentelor Aj , 1 j n , dată prin matricea: aij i mj n

11

unde aij este

cantitatea de substanţă Si conţinută în unitatea din alimentul Aj şi se cere ca

fiecare dietă să conţină cel puţin cantităţile bi din substanţa Si , 1 i m .

Deci, matematic problema se transcrie:

n1,2,...,j0x

mi1,bxa

erestrictiv conditiilein xcmin

j

n

1j

ijij

n

1j

jj

3

c) Problema folosirii optime a resurselor.

O unitate economică trebuie să producă produsele P P Pn1 2, ,..., având

la dispoziţie cel mult cantităţile b b bm1 2, ,..., din resursele R R Rm1 2, ,..., .

Ştiind că producerea unei unităţi din produsul Pj necesită cantitatea aij din

resursa Ri şi că prin livrarea unei unităţi din acelaşi produs se obţine beneficiul

C j , 1 i n se cere să se determine cantităţile x x xn1 2, ,..., din produsele

P P Pn1 2, ,..., astfel ca beneficiul să fie maxim. Deci:

njx

mibxa

xc

j

n

j

ijij

n

j

jj

,...,2,10

1,

conditiilein max

1

1

d) Problema de transport.

Se dau depozitele D D Dn1 2, ,..., , având disponibilă o marfă în

cantităţile b b bn1 2, ,..., ; consumatorii C C Cm1 2, ,..., solicitând marfa în

cantităţile b'1, b'2, ..., b'm; şi costul unitar cij de transport al mărfii de la

depozitul Di la consumatorul C j .

Se cere să se găsească un sistem de numere nenegative

x i n j mij , , ,..., ; , ,..., 1 2 1 2 unde xij este cantitatea de marfă

transportată de la Di la C j , care să facă minim costul de transport, adică

funcţia f c xij ij

j

m

i

n

11

şi să nu depăşească disponibilul din nici un depozit,

adică: x b i nij

j

m

i

1

1, ,..., şi să satisfacă măcar cererea fiecărui

consumator, adică: x b j mij

i

m

j

1

1' , ,...,

Sistemul x i n j mij , , ,..., ; , ,..., 1 2 1 2 care îndeplineşte aceste

condiţii se numeşte program de transport. Evident, existenţa unui program de

4

transport impune condiţia ca disponibilul total să depăşească sau să fie măcar

egal cu cererea totală, adică:

11 1

b bi

i

n

j

j

m

'

Dacă restricţiile problemei sunt date ca egalităţi atunci şi relaţia (1)

devine egalitate, şi în acest caz problema de transport se numeşte echilibrată.

În caz contrar spunem că avem o problemă de transport neechilibrată.

Datele problemei de transport pot fi înscrise într-un tablou de forma:

Tabelul (T) Consumatori

Depozite

C C Cm1 2 ... Disponibil

D

D

Dn

1

2

c c c

c c c

c c c

m

m

n n nm

11 12 1

21 22 2

1 2

...

...

...

b

b

bn

1

2

Cerere b b b m' ' ... '1 2

#3. Noţiuni generale privind problema programării liniare

Exemplele prezentate conduc la rezolvarea unor probleme matemetice

asemănătoare. Forma standard a unei probleme de programare liniară de minim

(sau program liniar de minimizare) se prezintă astfel:

nix

bmibxa

xcf

PL

j

ii

n

j

jij

n

j

jj

1,0

0,1,

erestrictivconditiileinmin

min2

1

1

iar a unui program liniar de maximizare:

5

njx

bmibxa

xcf

PL

j

ii

n

j

jij

n

j

jj

1,0

0,1,

conditiileinmax

max3

1

1

Condiţiile restrictive se mai numesc şi restricţiile programului liniar.

Dacă notăm:

x x x X a An

T

ij i mj n

1 2 11

, ,..., ;

b b b L c c c Cm

T

n1 2 1 2, ,..., ; , ,...,

atunci PL min se transcrie matriceal astfel:

2

0

'

min f x C X

A X L

X

T

iar PLmax :

3

0

'

max f x C X

A X L

X

T

Evident că sistemul de restricţii A X L poate fi:

incompatibil

compatibil unic determinat (numai în cazul m n )

compatibil nedeterminat.

Ultimul caz interesează cel mai mult pentru că aici se pune problema de

a alege dintre mai multe soluţii pe cea mai bună.

Pentru modelele de PL care nu au forma standard există modalităţi de

construire a unor forme standard echivalente. Acestea sunt prezentate în II.5.

Să presupunem că rangul lui A este m.Dacă notăm coloanele matricei A

cu a j nj , 1 atunci restricţiile problemei se transcriu:

4 1

1

2

2a x a x a x Ln

n ...

Definiţia II.3.1. Un vector X Rn , ale cărui componente satisfac

restricţiile unei probleme de programare liniară, se numeşte program admisibil

(sau soluţie admisibilă, sau soluţie posibilă)

6

Definiţia II.3.2 Un program admisibil X care minimizează (sau

maximizează, în funcţie de problemă) funcţia liniară asociată acelei probleme se

numeşte program optim (sau soluţie optimă).

Definiţia II.3.3.Un program X x x xn

T 1 2, ,..., se numeşte program

de bază dacă vectorii coloană a j, corespunzători componentelor x j nenule

x j 0 , sunt liniar independenţi.

Deoarece rang A m un program de bază are cel mult m componente

nenule;

Definiţia II.3.4. Dacă un program de bază are exact m componente

nenule (m= rang A), atunci programul de bază se numeşte nedegenerat. În caz

contrar, degenerat.

Definiţia II.3.5. Matricea B de tipul m x m formată din coloanele lui A

corespunzătoare componentelor nenule ale unui program de bază nedegenerat X

se numeşte bază a programului X.

Exemplul II.3.1. Problema de programare liniară:

min

, .

2 3 3

2

3 4

0 1 4

1 2 3 4

1 2 3 4

1 2 3 4

x x x x

x x x x

x x x x

x jj

se transcrie matriceal astfel:

min ( 2 -3 -3 1 ) . ( x1 x2 x3 x4 )T

1 1 1 1

1 1

2

4

0

1

2

3

4

1 -3

rang A = 2

x

x

x

x

X ,

Sistemul liniar de restricţii se transcrie şi sub forma:

7

1

1

1

1

1

3

1

1

2

4

1 2 3 4

1 2 3 4

a a a a L

x x x x

Programe ale problemei sunt de pildă:

X X X1 2 3

3

0

0

1

3

1

0

0

5

1

1

1

; ;

primele două fiind şi programe de bază nedegenerate cu bazele B11 1

1 1

;

respectiv B21 1

1 1

(sau cu notaţiile anterioare B a a B a a1 1 4 2 1 2 , ; , .

Valorile funcţiei obiectiv, corespunzătoare celor trei programe sunt:

f X f X f X1 2 37 3 5 , , . Programul X 3 nu este de bază deoarece

vectorii coloană corespunzători componentelor nenule, respectiv:

a a a a1 2 3 4, , , sunt liniar dependenţi.

Vectorul X 4

1

0

1

0

, deşi verifică sistemul de restricţii nu este program

admisibil deoarece nu are toate componentele nenegative.

Notăm cu P mulţimea soluţiilor posibile ale unei probleme PL - min.

Deci P x R AX L Xn , 0 şi notăm cu Pmulţimea programelor

optime ale acestei probleme:

P X P C X C X X PT T ; .

Teorema II.3.1. Mulţimile P şi Psunt convexe.

Demonstraţie: Să demonstrăm că P este convexă, adică

X Y P Y P Y, ,si avem X+ 1- si X+ 1- 01 0

Faptul că X+ 1- Y 0este evident.

Deoarece X P A X L siY P implicã AY = L. Deci:

A X Y A X AY L L L 1 1 1 .

Deci: X Y P 1

8

Pentru a demonstra că P este convexă, fie

X Y P deci C X C Y C XT T

X P

T , min

º i 0 1. Avem:

C X Y C X C Y C X

C X C X

T T T

X P

T

X P

T

X P

T

1 1

1

min

min min

Deci X Y 1 este optim.

Teorema II.3.2. Dacă o problemă de programare liniară admite

programe atunci admite şi programe de bază.

Teorema II.3.3. Dacă un program liniar are optim, atunci are şi un

program optim de bază.

Pentru demonstraţia acestor două teoreme avem nevoie de următoarea

lemă:

Lema II.3.1. Oricare ar fi sistemele de numere reale:

x x i n y i n yi i i i si nu toate nule 0 1 1, , se poate determina un

număr 0 astfel încât x yi i 0 pentru orice , , 1 i n şi

pentru cel puţin un indice j, 1 j n , să avem

x y x yj j j j 0 0sau

Demonstraţia lemei. Grupăm indicii 1 2, ,...,n după semnul

numerelor yi astfel încât I i y I i yi i1 20 0 si . Cum nu toţi yi

sunt nuli, 1 i n , avem I I1 2 . Dacă I1 si I2 comparăm

rapoartele x yi i/ cu i I 1 şi apoi pe cele cu i I 2 . Găsim r I 1 şi s I 2

astfel încât:

0

0

1

2

x

y

x

y

x

y

x

y

r

r i I

i

i

r

r i I

i

i

min

max

Vom lua min , iar j astfel:

- dacă

luam si vom avea cãci = =

x

y

r

r

j r x yr r 0

9

- dacă

luam si vom avea cãci = =

-x

y

s

s

j s x ys s 0

Observând că

min

i I

i

i

x

y2

vom avea în ambele cazuri

x y i ni i 0 1 si , .

Dacă I1 si I2 luăm iar dacă I1 si I2

luăm .

Demonstraţia lemei este încheiată.

Demonstraţia teoremei II.3.2. Vom demonstra că un program de bază

este un program admisibil cu un număr minim de componente nenule.

Fie X programul admisibil cu numărul minim de componente nenule. Fie

r numărul componentelor sale nenule. (Orice alt program admisibil va avea cel

puţin r componente nenule).

Dacă r = 0 atunci X = 0 este program de bază. Dacă r > 0, fie

x x xi i ir1 2, ,..., componentele strict pozitive ale lui X. (restul sunt nule).

Dacă a a ai i ir1 2, ,..., sunt liniar independenţi atunci X este program de bază. Să

presupunem prin reducere la absurd că a a ai i ir1 2, ,..., sunt liniar dependenţi ,

adică există y y y Ri i ir1 2, ,..., nu toţi nuli astfel încât:

(5) y a y a y ai

i

i

i

i

i

r

r

1

1

2

2 0 ...

Considerând Y Rn cu yi 0pentru

i n i i i y i i i k rr i rk 12 121 2 1 2, ,... , , ,... , , ,... , ; , ,... , . si y pentru ii

atunci folosind (5) putem scrie A Y 0 . Atunci:

(6) A X Y AX AY AX L R

Acum aplicăm lema II.3.1. pentru sistemele

x x y yi i i ir r1 1,..., ,..., .si Deci există 0 astfel încât, pentru un

, să avem x y k r x yi i i ik k j j 0 1 0, , si

pentru măcar un j r 12, ,..., . Atunci X Y devine un program

admisibil dar cu cel mult r 1componente nenule, contrar ipotezei. Deci

relaţia (5) nu este posibilă, rezultă că X este program de bază.

Demonstraţia teoremei II.3.3. Fie X P un program optim pentru

PL - min care are un număr minim r de componente nenule. Dacă r = 0 atunci

X 0 este program optim de bază. Dacă r > 0, fie a a ai i ir1 2, ,..., coloanele

10

lui A corespunzătoare celor r componente nenule din X . Dacă aceste coloane

sunt liniar independente atunci X este program optim de bază. Presupunem

prin absurd că aceste coloane ar fi liniar dependente. Cu aceleaşi notaţii ca în

demonstraţia precedentă găsim un Y Rn satisfăcând AY 0.

Dacă C YT 0 am putea alege un 0 , astfel încât

X Y P C YT si 0;atunci

C CT TX Y X C Y C XT T

contrar faptului că X este

program optim; deci C YT 0 .

Atunci alegând un , astfel ca X Y P să aibă cel

mult r-1 componente nenule găsim că X Y P 0ceea ce contrazice faptul

că r este numărul minim de componente nenule pentru un program optim. Deci

X este program optim de bază.

În concluzie, un program optim de bază este un program optim cu un

număr minim de componente nenule.

Teoremele II.3.2. şi II.3.3. reduc căutarea soluţiei optime a unei

probleme de programare liniară printre programele de bază, al căror număr este

finit. Cu algoritmul simplex se porneşte de la un program de bază care nu este

optim şi se construieşte un alt program de bază în care funcţia obiectiv să aibă o

valoare mai mică sau mai mare, după cum este un PL - min sau PL - max.

# 4. Algoritmul simplex

Se consideră problema de programare (2) şi un program de bază

nedegenerat X . După unele renumerotări şi rearanjări putem considera

X x x xm

T 1 2 0 0 0, ,..., , , ,..., ; deci variabilele x x xm1 2, ,..., sunt

principale iar x xm n1,..., secundare, iar vectorii coloană a a am1 2, ,...,

formează baza B a programului de bază X . Fie N a a am m n 1 2, ,..., .

Mai notând:

X

x

x

X

x

x

C

c

c

C

c

c

p

m

s

m

n

p

m

s

m

n

1 1 1 1

; ; ; problema (2) poate fi

scrisă:

11

7

0

min f X C X C X

B X N X L

X

p

T

p s

T

s

p s

Înmulţind BX NX Lp s la stânga cu B1obţinem:

8 1 1E X B N X B Lp s

care reprezintă transcrierea sistemului de restricţii în baza B, căci dacă scriem

a z a j nj

ij

i

i

m

1

1, (exprimarea vectorilor coloană în funcţie de

vectorii bazei B) vom avea:

zij ij pentru 1 i, j m si z pentru m+1 j n.ij 0 Corespunzător

programului X problema (2) devine:

9

1

1

f X c x

x z x x

i i

i

m

i ij j i

j m

n

Deci xi

sunt componentele vectorului L în baza B.

L B X B L X z B Nij i mm j n

11

1

1iar

Deci relaţia (8) devine:

10 1X B NX Xp s de unde

11 1X X B NXp s şi atunci

: f X C X C X C X B NX C X C X C C B N XpT

p sT

s pT

s sT

s pT

sT

pT

s 1 1

sau explicit:

121 11

f X c x c c z xi i

i

m

j j ij

i

m

j m

n

j

Notând: c x Z c z Z m j ni i

i

m

i ij

i

m

j

1 1

1si , atunci:

131

f X Z c Z xj j j

j m

n

Observăm că Z f X C B Lp

T

si Z 1 .

Acum putem asocia problemei PL- min următorul tabel:

12

C Bp

c1 c

2 c

n X

a1 a

2 a

n

vectorii

bazei z z z

z z z

n

m m mm

11 12 1

1 2

...

...

componentele

nenule ale lui

X

C Zj j ..................................

....... f X

Teorema II.4.1. Dacă X este un program de bază nedegenerat pentru

PL - min şi în tabelul asociat (S) avem c Z m j nj j 0 1 atunci

X este program optim.

Demonstraţie: Din (13) avem:

f X f X c Z x f Xj j

j m

n

j

0

10

pentru orice program admisibil X.

Deci X este optim.

Teorema II.4.2. Dacă X este un program de bază nedegenerat şi în

tabelul simplex asociat (S) există un t, m t n 1 , astfel încât

c Z i mt t 0 0 1si zit , atunci PL - min nu are optim finit.

Demonstraţie: Fie: X x x xn

T

1 2, ,..., unde:

x R

x x z i m

x m j n j t

t

i i it

j

,

;

; ,

1

0 1

Astfel avem x j nj 0 1 .

Pentru 1 i m avem:

a x a x a x a x z a a x a z aij j

j

n

ij j

j

m

ij j

j m

n

ij j jt

j

m

it ij j

j

m

ij jt it

j

m

1 1 1 1 1 1

(folosind (9))

a x z x a z aij j jh h

h m

n

j

m

ij jt

j

m

it

11 1

(S)

13

a x a z x a a a x a z x

a x a z x a x x a z a x

x a a x x

ij j

j

m

ij

j

m

jh h

h m

n

it it ij j

j

m

ij jh h

h m

n

j

m

ij j

j

m

ij jh h

j

m

h m

n

ij j

j

m

h ij jh

j

m

h m

n

ij j

j

m

h ih

h m

n

ij j

j

m

1 1 1 1 11

1 11 1 11 1

1 1

(renotãm pe h cu j) j ij

j m

n

ij j

j

n

ia a x b

1 1

Deci X este soluţie admisibilă. Avem:

f X c x c Z x c x c Zj j

j

m

j j

j m

n

j j j

j

m

t t

1 1 1

din definirea lui X .

Deoarece 0 0si ct Zt atunci f X

, adică

funcţia obiectiv nu are optim finit.

Teorema II.4.3. Dacă X este un program de bază nedegenerat pentru

PL - min, iar în tabelul simplex asociat (S) există un t,

m t n c Zt t 1 0cu şi cel puţin un indice i, 1 i m, astfel încât

zit 0 , atunci alegând s s m, 1 , după criteriul:

14 1 0x

z

x

zi m zs

st

i

it

it

min / ,

se poate substitui în baza B vectorul a scu vectorul a t

, obţinând o bază B' ,

corespunzătoare unui program de bază X ' care ameliorează valoarea funcţiei

obiectiv.

Demonstraţie. Deoarece zst 0, folosind lema substituţiei rezultă că

înlocuind a s în B cu a t

sistemul de vectori nou obţinut B', este o bază. Soluţia

de bază corespunzătoare lui B'este dată tot de lema substituţiei:

15

1

0

0

0 1

x xx

zz i m i s

x

xx

z

x m j n j t

i is

stit

s

ts

st

j

'

'

'

'

, ,

, ,

cu toate componentele nenegative (pentru 1 i m i s, dacă zit 0 atunci

14

x xx

zzi i

s

stit

'

, deci o sumă de numere nenegative; iar dacă zit 0

avem x zx

z

x

zi it

i

it

s

st

'

şi ţinând seama de (14) înseamnă că xi

' este produs

de două numere nenegative).

Deci X x x xn

T

' , ,...,' ' ' 1 2 este o soluţie de bază. Valoarea funcţiei obiectiv

pentru X ' este:

f X f X c Z x f X c Z x f Xj j

j m

n

j t t t' .' '

1

Acum putem prezenta algoritmul simplex pentru o problemă PL - min în

formă standard.

-Pasul 10: Se găseşte un program de bază nedegenerat X

cu baza B; se

construieşte tabelul simplex (S).

-Pasul 2 : Se verifică dacă diferenţele c Zj j 0pentru orice j j n,1 .

Dacă DA se trece la pasul 5; dacă NU, dintre toate diferenţele c Zj j ,

negative, se alege cea mai mică. Indicele j corespunzător să-l notăm cu t. (Dacă

există mai mulţi t se alege primul de la stânga la dreapta). Vectorul a tva intra

în bază. Se cercetează dacă zit 0 pentru 1 i m. Dacă DA, se trece la

pasul 4, dacă NU, se trece la pasul 3.

-Pasul 3 : Se alege s, astfel încât x

z

x

zi m zs

st

i

it

it

min / ,1 0 .

Vectorul a sva ieşi din bază. Elementul zst devine pivot. Se construieşte un nou

tabel simplex folosind regula dreptunghiului:

a) se împarte linia pivotului la pivot.

b) în coloana pivotului, elementele z cu j tsj se înlocuiesc cu 0

c) elementele z i s j tij , ,cu se înlocuiesc cu z zz z

zij ij

it sj

st

'

.

Se obţine un alt program de bază X ' cu baza B' şi o nouă valoare a funcţiei

obiectiv.

Se revine la pasul 2 cu B B 'şi X X '

-Pasul 40 .Concluzie: “PL - min nu are optim finit” şI algoritmul se opreşte.

15

-Pasul 5 .Concluzie: “PL - min are optim X iar valoarea minimă f X ".

STOP.

Exemplul II.4.1. Fie problema:

min

, , ... ,

f x x x x x

x x x x x

x x x x xx jj

5 7 9 2

3 2 5 3 7

2 3 40 1 2 5

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

Alegem XT 1 2 0 0 0, , , , . Avem:

a a a a a B a a1 2 3 4 5 1 23

2

2

1

1

1

5

3

3

1

; ; ; ; ,

Coordonatele vectorilor a a1 2si în baza B sunt 1

0

, respectiv

0

1

.

Pentru a afla coordonatele lui a 3 se procedează astfel: punem

a a a R31

12

21 2 , , , deci:

1 2

1 2

1 2

3

2

2

1

1

1

3 2 1

2 1

ceea ce ne dă 1 21 1 , .

Deci în baza B, aB3

1

1

. Analog se găsesc: a aB B

4 51

1

1

3

,

Aşadar tabelul simplex corespunzător bazei B are forma:

5 7 9 2 1

a a a a a1 2 3 4 5

5

7

a

a

1

2

1 0 1 1 -1

0 1 -1 1

1

2

c Zj j 0 0 11 -10 -15 19

Deci a 5intră în bază, a2

iese din bază, z25 - pivot. Se execută pivotajul

şi obţinem:

5

1

a

a

1

5

1 1/3 2/3 0

0 1/3 -1/3 1/3 1

5 3

2 3

/

/

c Zj j 0 5 6 -5 0 9

Intră în baza a4şi iese a1

.

3

4/3

X f X'

/

/

'

5 3

0

0

0

2 3

9

16

2

1

a

a

4

5

3 4 1 4 1 2 1 0

1 4 1 4 1 2 0 1

/ / /

/ / /

5 4

1 4

/

/

c Zj j 15/4 25/4 17/2 0 0 11 4/

Şi am obţinut c Z jj j 0 1 5.Deci programul optim este

0,0,0,5 4 1 4/ , / minT

fcu =11

4.

Algoritmul se aplică şi problemelor PL - max în forma

standard cu observaţia că max minf f . De asemenea algoritmul se

aplică şi în cazul în care funcţia obiectiv are forma f c x Rj j

j

n

1

, ,

deoarece punctele de extrem ale acesteia sunt aceleaşi cu punctele de extrem ale

funcţiei: g c xj j

j

n

1

.

# 5. Tratarea problemelor de programare liniară care nu au forma

standard. Metoda bazei artificiale.

Dacă sistemul de restricţii conţine inecuaţii de forma

: a x b a x b i mij j

j

n

i ij j

j

n

i

1 1

1sau , atunci acestea se transformă în

egalităţi dacă se adaugă (respectiv se scade) în primul membru o necunoscută

auxiliară yi , yi 0, numită şi variabilă de egalizare sau de compensare.

Deci: a x y bij j

j

n

i i

1

(respectiv a x y bij j

j

n

i i

1

).

Dacă o componentă a termenului liber b i mi , ,2,... , 1 este negativă

atunci se înmulţeşte egalitatea sau inegalitatea respectivă cu -1.

Dacă nu toate componentele lui X Rn

sunt constrânse să fie

nenegative atunci facem substituirea acestora cu variabile ce satisfac condiţia de

nenegativitate astfel: dacă x j 0 atunci punem: x x xj j j ' '

;cu 0 dacă

x j este liberă, neconstrânsă atunci punem: x x x x xj j j j j ' '' ' ''

, .cu 0

Aceste substituţii se înlocuiesc atât în funcţia obiectiv cât şi în

17

restricţiile problemei.

Exemplul II.5.1. Problema:

max f x x

P

x x

x x

x x R

2

2 4

4

0,

1 2

1 2

1 2

2 1

se transformă în:

min

'

, , , ,

' ''

' ''

' ''

' ''

f x x x

P

x x x y

x x x y

x x x y y

2 2

2 2 4

4

0

1 1 2

1 1 2 1

1 1 2 2

1 1 2 1 2

care este o problemă standard PL - min. Se rezolvă problema (P') şi apoi se

reţine soluţia pentru problema (P).

În cazul în care nu dispunem de un program de bază se utilizează metoda

celor două faze pentru determinarea unui astfel de program.

Faza I: Programului liniar:

16 1

0, 1

1

1

PL

f c x

a x b i m

x j m

j j

j

n

j j

j

n

i

j

min

min

,

i se asociază programul liniar auxiliar, cu variabilele artificiale x x xa a

m

a

1 2, ,..., :

18

17 1

0, 0, 1 1

1

1

PL

g x

a x x b i m

x x j n i m

a

i

a

i

m

ij j i

a

j

n

i

j i

a

min

min

,

, .

Sistemul de restricţii este un sistem de m ecuaţii cu n + m necunoscute.

Se observă că 0,0, 1 2... ,0, , , ... ,b b bm

Teste o soluţie de bază pentru PL

amin

cu care se poate pleca în algoritmul simplex. Deoarece funcţia obiectiv g este

pozitivă, vom găsi cu certitudine un program optim de bază pentru care

min g 0. Dacă min g = 0 atunci componentele xi

aîn programul optim de bază

pentru (17) sunt nule şi eliminându-se aceste zerouri, corespunzătoare

variabilelor xi

adin acest program optim de bază al PL

amin, se obţine un

program de bază X pentru (16).

Faza a II-a: În continuare se aplică algoritmul simplex pentru (16) cu

programul de bază X0. Dacă min g > 0 atunci (16) nu are soluţii admisibile.

Exemplul II.5.2.

min

,2,3,4

f x x

x x x

x x x

x ii

1 2

1 2 3

1 2 4

6

2 3

3 4

0 1

Faza I:

PL

g x x

x x x x

x x x x

x i x x

a

a a

a

a

i

a a

min

min

,2,3,4, ,

1 2

1 2 3 1

1 2 4 2

1 2

2 3

3 4

0 1 0

Care are soluţia de bază 0,0,0,0,3,4T

. Aplicăm algoritmul simplex:

0 0 0 0 1 1

a1

a2 a

3 a

4 a

5 a

6

19

1 a5 2 1 -1 0 1 0 3

1 a6 1 0 -1 0 1 4

-3 -4 1 1 0 0 7

1 a5 0 -1 1/3 1 -1/3 5/3

0 a2 1/3 1 0 -1/3 0 1/3 4/3

-5/3 0 1 -1/3 0 4/3 5/3

0 a1 1 0 -3/5 1/5 3/5 -1/5 1

0 a2 0 1 1/5 -2/5 -1/5 2/5 1

0 0 0 0 1 1 0

Am obţinut programul optim de bază

11, ,0,0,0,0T

pentru PL ga min mincu 0. Faza întâi s-a încheiat.

Faza a II-a. Reţinem ca program de bază 11 0 0, , ,T

(componentele

corespunzătoare, respectiv, lui x x x x1 2 3 4, , , , din programul optim de bază

obţinut la faza I) pentru problema iniţială şi aplicăm algoritmul simplex.

#.6. Eliminarea degenerării

Este posibil ca după câteva iteraţii în aplicarea algoritmului simplex să

revenim la una din bazele prin care am trecut deja, şi atunci procesul continuă la

infinit fără a conduce la o soluţie. Această situaţie se numeşte ciclare. Această

situaţie poate apărea atunci când problema de programare liniară admite soluţii

de bază degenerate (vezi definiţia II.3.4.). Nu întotdeauna degenerarea implică

neapărat ciclare. În practică, ciclarea apare foarte rar.

Pentru înlăturarea degenerării se foloseşte aşa numita "tehnică a

perturbării cu ".

Fie o problemă PL - min şi X un program de bază degenerat. Deci

X are r componente nenule, r m . Fie X x x xr

T 1 2 0 0, ,... , , , ... , .

Aceasta înseamnă că în iteraţia algoritmului simplex care conduce la

obţinerea lui X s-a întâlnit situaţia: min ,

x

zi m zi

itit

1 0

se atinge în

mai multe puncte (pentru mai mulţi indici i). Fie s şi u indicii pentru care avem

x

z

x

z

s

st

u

ut

.

3

5/3

20

Se pune întrebarea cum alegem în acest caz pivotul (linia pivotului)?

Vom înlocui X cu:

(18) X X aj j

j

n

1

unde 0 este un număr

foarte mic, iar a j nj , 1 sunt vectorii coloană ai sistemului de restricţii.

Deci j j

j

n

a

1

este o combinaţie liniară de vectorii a jcu coeficienţii

, , ,..., .2 3 n

Componentele lui X vor fi:

(19) x x zk k

j

kj

j

n

1

0 0, ,

Observaţie: Aici prin jînţelegem puterea a j a a lui . Dacă alegem

diferit de rădăcinile ecuaţiei:

(20) x

z

x

z

s

st

u

ut

atunci pentru acest vom avea:

(21) x

z

x

z

s

st

u

ut

Împărţind (19) la z k s zst utdacă şi la dacă k= u obţinem:

(22) x

z

x

z

z

z

s

st

s

st

j

n

nsj

st

1

(23) x

z

x

z

z

z

u

ut

u

ut

j

n

nuj

ut

1

Din relaţiile (22) şi (23), comparând coeficienţii lui j

, obţinem compararea

celor două linii, care este o comparare lexicografică: dacă j este primul indice

pentru care z

z

z

z

sj

st

uj

ut

atunci şi x

z

x

z

s

st

u

ut

adică

21

min ,

x

zi m z

i

itit

1 0

se atinge pentru i s . Deci pivotul va fi zst ,iar

linia s este linia pivotului.

Făcând 0 se revine la problema iniţială.

În practică, dacă am ajuns la un pas în care avem: x

z

x

z

s

st

u

ut

se

procedează astfel:

1 Se împart elementele de pe linia s la zst şi cele de pe linia u la zut . Se

formează două linii de rapoarte.

2 Se compară rapoartele corespunzătoare de pe cele două linii. Linia pe care

apare primul raport mai mic se alege ca linie pivot.

Exemplul II.6.1. Fie situaţia:

2 1 1 1

a a a a1 2 3 4

2

1

1

a

a

a

1

2

3

1 0 0 4/5

0 1 0 2/5

0 0 1 2

12 5

6 5

8

/

/

c zj j 0 0 0 -3 14

Împărţim prima linie la 4/5 şi cea de-a doua la 2/5. Obţinem:

5 4 0 0 1

0 5 2 0 1

/

/

Primul raport mai mic apare pe linia a doua, deci z24 este pivotul.

#.7. Algoritmul simplex dual

Problemei de programare liniară:

12 5

4 53

6 5

2 53

/

/

/

/

22

(24)

min f X C X

A X L

X

T

0

i se asociază problema:

(25)

max g Y L Y

A Y C

Y

T

T

0

unde Y

y

y

ym

1

2

Problema (24) se va numi primală iar problema (25) duala problemei

(24) şi reciproc.

Exemplul II.7.1

min

, , , ,

f x x x

x x x x

x x x x

x x x x

x ii

1 2 3

1 2 3 4

1 2 3 4

1 2 3 4

2 2

2 1

2 2

1

0 1 2 3 4

Folosind tabelul:

Y

X x x x x1 2 3 4 L

y

y

y

1

2

3

1 2 1 1

2 1 1 1

1 1 1 1

1

2

1

1 2 2 0 C

găsim duala:

max

, , ,

g Y y y y

y y y

y y y

y y y

y y y

y ii

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

2

2 1

2 2

2

0

0 1 2 3

23

Teorema II.7.1. Fie X o soluţie posibilă pentru problema (24) şi Y o

soluţie posibilă pentru problema (25). Atunci f X g Y

Demonstraţie: Din AX L , înmulţind la stânga cu YT 0 obţinem:

Y A X Y L L Y g YT T T

Pe de altă parte: A Y C X A Y X C C X f XT T T T T

Dar cum Y A X A X Y X A YT T T T ajungem la concluzia

g Y f X .

Teorema II.7.2. Dacă (24) are optim finit atunci (25) are optim finit şi

avem XfYg minmax YLX T TCsau unde X este o

soluţie optimă pentru (24) iar Y o soluţie optimă pentru (25).

Demonstaţie: Din teorema II.7.1. pentru orice pereche de programe

duale X,Y, avem XfYg . Deci are loc şi XfYg max . Cum f

este o funcţie liniară, deci continuă, atunci Xfmin există şi are loc

max ming Y f X .

Pe de altă parte folosind (13) şi teorema II.4.1. avem

LBCZXfXf Tp 1min

. Se demonstrează că 01

pCBY

este un program optim pentru duala (25). Atunci:

.maxmin 11 YgYgYLLYLCBLBCXf TTT

pTp

Teorema II.7.3. (teorema ecarturilor complementare)

Fie X,Y soluţii ale problemelor (24), respectiv (25). Atunci X,Y sunt

soluţii optime dacă şi numai dacă au loc relaţiile:

Y L AX X A Y CT T T 0 0;

Demonstraţie. Avem:

L Y Y L Y AX X A Y X C C XT T T T T T T

Folosind teoremele II.7.2. şi II.7.1. obţinem că X,Y sunt programe

optime dacă şi numai dacă L Y C XT T ceea ce conduce la:

Y L Y A X X A Y X CT T T T T

sau: Y L AX X A Y CT T T 0 0; .

Dualitatea se foloseşte cel mai frecvent în cazul în care problema

primală necesită calcule multe:

24

Exemplul II.7.2.

min

, ,

.

f x x

x x

x x

x x

x x

x ii

3

2 1

1

3 2 3

2 3 1

0 1 2

1 2

1 2

1 2

1 2

1 2

Pentru a rezolva această problemă cu algoritmul simplex trebuie

introduse patru variabile de egalizare, dar scriind problema duală:

max

,

g y y y y

y y y y

y y y y

yi

1 2 3 4

1 2 3 4

1 2 3 4

3

2 3 2 3

2 3 1

0 1 4

i

aceasta necesită numai două variabile de egalizare. Obţinem:

001311

654321 aaaaaa

0

0 6

5

a

a

2 1 3 2 1 0

1 1 3 0 1 1

3

-1 -1 -3 -1 0 0 0

0

3 3

5

a

a

1/2 -1/2 0 -5/2 1 -3/2

1/2 1/2 1 3/2 0 1/2 2/1

2/3

1/2 1/2 0 7/2 0 3/2 -3/2

deci max / min .g f 3 2

Pentru a putea formula duala unei probleme de minim am văzut că

restricţiile trebuie să aibă forma (24). În acest caz, restricţiile " " sunt numite

concordante, iar cele " " neconcordante. Pentru problema primală de maxim,

restricţiile " " sunt cele concordante iar " " cele neconcordante.

În caz că nu au această formă pot fi aduse la forma (24) după

următoarele reguli:

modelul dat modelul dual

număr de variabile număr de restricţii

2

25

număr de restricţii număr de variabile

minim maxim

maxim minim

termeni liberi ai restricţiilor coeficienţii funcţiei obiectiv

coeficienţii funcţiei obiectiv termenii liberi ai restricţiilor

coloanele matricii restricţiilor liniile matricii restricţiilor

restricţie concordantă variabilă nenegativă

restricţie neconcordantă variabilă nepozitivă

restricţie egalitate variabilă liberă

variabilă nenegativă restricţie concordantă

variabilă nepozitivă restricţie neconcordantă

variabilă liberă restricţie egalitate

Exemplul II.7.3.

min

, ,/

f x x x x

x x x x

x x x x

x x x x

x x x R

3 2

2 5

2 2 10

2 10

0 0

1 2 3 4

1 2 3 4

1 2 3 4

1 2 3 4

1 2 3 4

Duala va fi:

max

, ,

g y y y

y y y

y y y

y y y

y y y

y y y R

5 10 10

2 3

2 2

2 1

2 1

0 0

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

26

#.8 Problema transportului

O problemă de transport, echilibrată, corespunzătoare tabelului (T) (vezi

II.2), are forma:

PT

f X c x

x b i n

x b j m

b b

x i j

ij ij

j

m

i

n

ij

j

m

i

ij

j

n

j

j

j

m

i

i

n

ij

:

min

,

,

,

'

'

11

1

1

1 1

26

1 27

1 28

29

0

numită şi forma standard.

În cazul în care avem b bj

i

m

i

i

n'

1 1

, atunci în tabelul (T)

introducem coloana (m+1)-a cu b b b c i nm i

i

n

j

j

m

i m

1

1 1

1 0 1' ', ;º i

iar in cazul cã b bj

j

m

i

i

n

'

1 1

introducem linia (n+1)-a cu

.10 si ,1

11

''1 mjcbbb jn

n

i

i

m

j

jn

Din (27) şi (28) avem m n relaţii cu m n necunoscute. Din (29)

rezultă că între ecuaţiile (27) şi (28) mai există cel puţin o relaţie şi atunci

rangul matricii sistemului (27) + (28) este ce mult m n 1

Definiţia II.8.1. Dacă rangul matricii sistemului (27)+(28) este m+n-1,

iar un program de bază are exact m+n-1 componente pozitive (restul nule)

atunci programul se numeşte nedegenerat.

27

O problemă de transport se poate rezolva prin metoda simplex dar există

şi metode specifice.

Pentru început vom prezenta două metode specifice pentru obţinerea

unui program de bază; în cazul unui exemplu concret:

1* - Metoda colţului N-V (nord-vest)

2* - Metoda elementului minim din linie sau coloană.

Problemă: Din trei depozite D D D1 2 3, , trebuie transportată acelaşi tip

de marfă la trei magazine C C C1 2 3, , . Costurile unitare de transport,

disponibilul (D) şi necesarul (N) sunt date în tabelul:

C1 C2 C3 D

D1 2 5 3 100

D2 4 2 1 120

D3 7 8 3 70

N 80 110 100

Observăm că problema este echilibrată.

Metoda 1 .În colţul din N-V se trece min , min , .D N1 1 100 80 80

Deoarece necesarul N1 s-a epuizat se trece 0 (sau se lasă libere, sau se

haşurează) celelalte căsuţe de pe prima coloană. Iar D1 devine100 80 20 .

Obţinem tabelul:

C1 C2 C3 D

D1 80 20

D2 /////////// 120

D3 /////////// 70

N 110 100

Cu coloanele C2 , C3 rămase procedăm la fel. În colţul N-V (căsuţa (1,2) din

tabel) înscriem min , min , .D N1 2 20110 20 Deoarece disponibilul D1 s-a

epuizat se trece 0 în restul căsuţelor de pe prima linie; iar necesarul N2 a

devenit 110 20 90 . Obţinem tabelul:

28

c C2 C3 D

D1 80 20 ///////////

D2 /////////// 120

D3 /////////// 70

N 90 100

Cu căsuţele rămase libere se procedează ca mai sus şi se obţine, în final,

programul de bază:

80 20 0

0 90 30

0 0 70

care este nedegenerat (are m n 1componente; în cazul de faţă m=3, n=3).

Metoda 2 Metoda minimului pe linie:

Căutăm costul minim din prima linie; îl găsim pe poziţia c11 2 . În căsuţa

respectivă , trecem min , min ,N D1 1 80100 80 . Deoarece N1 s-a epuizat

haşurăm celelalte căsuţe ale coloanei C1 ; iar D1 a devenit 100-20=80.

Tabelul s-a transformat în:

C1 C2 C3 D

D1 80 20

D2 /////////// 120

D3 /////////// 70

(N) 110 100

În tabelul rămas, compus din coloanele C2 şi C3 căutăm din nou cel mai

mic cost de pe prima linie: găsim c13 3 . În căsuţa corespunzătoare trecem

min , min , .D N1 3 20100 20 Deoarece D1 s-a epuizat, haşurăm căsuţele

libere din prima linie, iar N3 a devenit 100-20=80. Obţinem tabelul:

C1 C2 C3 D

D1 80 /////////// 20

D2 /////////// 120

29

D3 /////////// 70

(N) 110 80

În continuare procedăm la fel şi obţinem programul de bază:

80 0 20

0 110 10

0 0 70

care este diferit de cel obţinut prin metoda colţului N-V. Lucrurile se petrec la

fel dacă căutăm costul minim de transport de pe o coloană.

De regulă în rezolvarea unei probleme de transport, după ce i s-a

determinat un program de bază, se foloseşte duala sa:

PT

g b u b v

u v c

u v R i n j m

d

i i

i

n

j j

j

m

i j

j

m

i

n

ij

i j

:

max

, , ,

'

1 1

11

1 1

Conform teoremelor dualităţii avem:

g Y f X pentru orice pereche de soluţii duale X,Y.

max ming Y f X în cazul în care avem optim.

Înlocuind în g Y valorile b i n j mi , ,1 1 şi b j

'cu

expresiile date de modelul primal ((27), respectiv (28)), găsim:

3011 11 11

x u x v u v xij i

j

m

i

n

ij j

i

n

j

m

i j ij

j

m

i

n

Inegalitatea g Y f X devine:

31 011 11

u v x c x xi j ij

j

m

i

n

ij ij

j

m

i

n

ij

unde

sau:

32 0 011

u v c x xi j ij ij

j

m

i

n

ij

, .

Dacă X este optim finit pentru problema primală avem

max ming Y f X şi inegalitatea (32) se transformă în egalitate. Cum

x i jij 0 , ajungem la concluzia:

30

33 0 0u v c xi j ij ij dacã .

Tot de aici reiese că dacă pentru un xij 0avem u v ci j ij 0 atunci

X nu este optim.

Cum xij 0sunt în număr de m+n-1 atunci (33) reprezintă m+n-1 relaţii

cu m+n necunoscute ( ui sunt în număr de n, iar v j în număr de m). Ţinând

seama şi de forma sistemului (33) este suficient să facem u1 0 pentru a

obţine restul necunoscutelor.

Condiţia ca X să fie optim revine la faptul că u v ci j ij 0 pentru

xij nebazici.

Notând u v C Ci j 0 0 0şi cij condiţia ca X să fie optim

devine 0 0 pentru xij nebazici. Dacă nu toţi 0 0 pentru xij nebazici,

se trece la îmbunătăţirea programului:

Se alege

c Crsi j

0 0 0 0min,

.

Variabila xrs corespunzătoare, nebazică se introduce în bază. Pe linia r,

dintr-un xrk bazic trebuie scăzut un xrs , pentru a nu modifica disponibilul

Dr şi atunci pe coloana k, la un xpk bazic trebuie adăugat xrs pentru a nu

modifica necesarul Nk şi în consecinţă pe linia p la un xps trebuie scăzut

xrs pentru a nu modifica disponibilul Ds .

Notând xrs , se formează astfel un ciclu:

x x

x

ps pk

rk

Alegând min ,x xps rk se obţine o nouă soluţie de bază. Se calculează

din nou C0 0, , ş.a.m.d., până în momentul în care nu mai avem 0 0 .

Toate aceste rezultate se pun într-un tabel specific pe care îl prezentăm

în contextul problemei exemplu anterioare.

31

X0 C0

v1 v2 v3 vj

ui

2 5 4 0 Ciclul

u1 80 20 0 /// /// 4 -1 20-

u2 90 30 -3 -1 /// /// 5 90+ 30-

u3 70 -1 1 4 /// 6 4

În caseta X avem programul de bază determinat cu metoda colţului N-V.

Corespunzător acestuia sistemul u v ci j ij 0 devine:

u v

u v

u v

u v

u v

1 1

1 2

2 2

2 3

3 3

2

5

2

1

3

Punând u1=0 obţinem v v u v u1 2 2 3 32 5 3 4 1 , , , , valori pe

care le-am trecut în prima coloană, respectiv prima linie din caseta C . Apoi

căsuţele din această casetă, corespunzătoare programului de bază se haşurează,

iar celelalte se completează cu valorile C corespunzătoare. Se calculează

valorile 0 0 c Cij care au fost trecute în căsuţele corespunzătoare.

Observăm că 13 1 0 , deci X nu este soluţie optimă şi trebuie

îmbunătăţită.

Formăm ciclul cu şi găsim min .20,30 20 Scriem un nou tabel

cu noua soluţie găsită pe care am notat-o X1 .

X1 C0

v1 v2 v3 vj

ui

2 4 3 0

u1 80 20 0 //// 4 //// //// 1 ////

u2 110 10 -2 0 //// //// 4 ////

u3 70 0 2 4 //// 5 4 ////

32

Am obţinut 0 0 i j, nebazici, deci soluţia X1 este optimă.

Observăm că ea coincide cu soluţia de bază determinată cu ajutorul metodei

costului minim pe linie.

Propunem spre rezolvare următoarele probleme de transport:

1.

C1 C2 C3 C4 (D)

D1 5 6 2 5 15

D2 1 3 4 2 25

D3 7 1 3 4 20

(N) 10 30 5 15

Observaţie: Soluţia de bază obţinută cu metoda colţului N-V este:

X N V

10 5 0 0

0 25 0 0

0 0 5 15

care are 5 componente nenule.

Cum m+n-1=3+4-1=6 rezultă că XN V este degenerată. Se caută altă soluţie de

bază cu metoda costului minim pe linie, obţinându-se:

0 0 5 10

10 10 0 5

0 20 0 0

2.

D1 D2 D3 D4 N

C1 1 3 2 5 50

C2 6 2 3 2 20

C3 4 5 1 1 60

D 30 10 10 80

Observaţie: Mai întâi trebuie transpus acest tabel. Se va găsi soluţia de bază:

30 0 0

0 10 0

0 0 10

20 10 50

.

33

3.

C1 C2 C3 D

D1 2 3 1 50

D2 4 5 2 30

N 30 10 40

4.

C1 C2 C3 D

D1 5 2 1 20

D2 3 4 2 40

D3 5 4 3 40

(N) 40 10 30

Observaţie: Deoarece (D) > (N) problema este neechilibrată. Introducem un

consumator fictiv:

C1 C2 C3 C4 D

D1 5 2 1 0 20

D2 3 4 2 0 40

D3 5 4 3 0 40

N 40 10 30 20

Probleme de programare liniară propuse spre rezolvare:

I. Să se rezolve următoarele probleme puse sub forma standard:

1.)

max

,4.

f x x x

x x x

x x x

x ii

3

2 3 4

5 2 12

0 1

1 2

1 2 3

1 2 4

Sol. 19

136max0;0;

19

4;

19

44

fX

T

optim

34

2.)

min

,6

f x x x x

x x x x

x x x x

x x x x

x ii

1 2 3

1 2 3 4

1 2 3 5

1 2 3 6

2 2

2 1

2 2 2

3 4

0 1

Sol: Xoptim 5 11 19 27,0, ,0, ,0 minT

f

3.)

min f x x x x

x x x x

x x x x

x x x x

xi

4 5 6

1 4 5 6

2 4 5 6

3 4 5 6

2 3

2 3

3 4

3 2 1

0

Sol: X foptim

T 0,0,0,2 11 47,7, min

4.)

max

,7

f x x x x x

x x x x x

x x x x x

x x x x x

x ii

3 2 4 2

2 2 2

3 1

4 2

0 1

1 2 3 4

1 2 3 4 5

1 2 3 4 6

1 2 3 4 7

Sol: Xoptim 0,0,0,1 2.,4,0,3 ; maxT

f

5.)

min f x x x x x

x x x x x

x x x x x

x x x x x

xi

3 2 4

2 3 1

2

2 2 3

0

1 2 3 7

1 2 3 4 7

1 2 3 5 7

1 2 3 6 7

Sol: nu are optim finit

35

II. Să se aducă la forma standard şi apoi să se rezolve problemele:

6.)

max f x x x x

x x x

x x x

xi

3 2 4

2 5

4 1

0

1 2 3

1 2 3

1 2 3

Sol: nu are optim finit

7.)

max

,

f x x x

x x

x x

x x

7 4

1

2 4

2 0

1 2

1 2

1 2

1 1 2

Sol: Xoptim

Tf 2 1 18, ,2,0,0 max

8.)

min

,4

f x x x x

x x x x

x x x x

x x x x

x ii

2 3

2 3 1

2

2 2 3

0 1

1 2 4

1 2 3 4

1 2 3 4

1 2 3 4

Sol: Xoptim

T 8,11 5,0,

9.)

max

, ,

f x y z

x y

y z

x z

x y z

2 3

2 3

2 3

0

Sol: Xoptim

T 111, ,

10.)

max

, ,

f x y z

x y

y z

x z

x y z

1

1

1

0

Sol: Xoptim

T

1

2

1

2

1

2; ;

36

11.)

min

,3

f x x x x

x x x

x x

x ii

2

1

2 4

0 1

1 2 3

1 2 3

2 3

Sol: nu există minim

12.)

max

,

f x x x

x x

x x

x R y

2

2 4

4

0

1 2

1 2

1 2

Sol:Xoptim

T 4 0,

13.)

min

,3

f x x x

x x x

x x x

x x x

x ii

2 3 2

1

2 3 4

2 2 3

0 1

1 2 3

1 2 3

1 2 3

1 2 3

14.)

min

,

f x x x x

x x x

x x x

x x x R

1 2 3

1 2 3

1 2 3

1 2 3

2

2 1

4

0

Sol: Xoptim 0 0 1 2, , / T

15.)

max

, ,

f x x x x

x x x

x x x

x x x

1 2 3

1 2 3

1 2 3

1 2 3

2 3

6

2 3 6

2 3 0

Indicaţie: Se face mai întâi schimbarea de variabile:

x x x x1 1 2 22 3' ', Sol: Xoptim

T 2 31, , .

37

III. Folosind metoda celor două faze să se rezolve programele liniare:

16.)

min

,

f x x x x x x

x x x x x

x x x x x

x ii

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

3 2 2

2 2 1

3 2 2 3

0 1 5

Sol: Xoptim 0 0 5 3 7 3 0, , / , / ,

17.)

min f x x x x x

x x x x x

x x x x x

x x x x

xi

3

1

2 2 2

2 4

0

1 2 3 4

1 2 3 4 5

1 2 3 4 5

1 2 3 4

Sol: X foptim

T 111 0 1, , , min

18.)

min

/

f x x x

x x

x x

x x

x

2 3

1

2

2 1

0

1 2

1 2

1 2

1 2

1 2

Sol: Xoptim 1 0,

19.)

max

,3

f x x x x

x x x

x x x

x ii

1 2 3

1 2 3

1 2 3

3 5 2

3 2 2 2

0 1

Sol: Xoptim

2

7

4

70; ;

38

20.)

min f x x x x

x x x

x x x

xi

2

2

2 3

0

1 2 3

1 2 3

1 2 3

IV. Să se transcrie matematic şi apoi să se rezolve următoarele probleme:

21.) O maşină care lucrează 25 de ore pe săptămână produce trei articole.

Beneficiul obţinut în urma vânzării acestor articole este de 40 lei/buc pentru

primul articol, respectiv 120 lei/buc pentru al doilea articol şi 30 lei/buc pentru

ultimul articol. Într-o oră maşina poate realiza 50 buc din primul articol sau 25

buc din al doilea articol sau 75 buc din al treilea articol. Cererea săptămânală nu

depăşeşte 1000 buc din primul articol, 500 buc din al doilea articol, 1500 buc

din al treilea articol. Cum trebuie repartizată producţia celor trei articole pentru

ca întreprinderea să-şi asigure un beneficiu maxim:

Răspuns: Fie x x x1 2 3, , cantităţile din cele trei articole ce trebuiesc produse.

Atunci avem de rezolvat problema:

max

, ,

f x x x

x

x

x

x x x

x x x

40 120 30

1000

500

1500

1

50

1

25

1

7525

0

1 2 3

1

2

3

1 2 3

1 2 3

(1

501 x reprezintă numărul de ore pe săptămână în care maşina produce

cantitatea x1 din primul articol).

22.) O fabrică de zahăr trebuie să producă între 1 noiembrie - 28 februarie.

Livrările de zahăr se fac lunar, după contract: în noiembrie 20.000 t, în

decembrie 30.000 t, în ianuarie 50.000 t şi în februarie 40.000 t. Producţia

excedentară a unei luni poate fi livrată luna următoare, suportând cheltuielile de

depozitare de 2.000 lei/tonă pe lună. Capacitatea lunară de producţie a fabricii

este: 55.000 t în noiembrie, 40.000 t în decembrie, 25.000 t în ianuarie, 50.000 t

în februarie. Preţurile de cost sunt: 140.000 lei/tonă în noiembrie, 160.000

39

lei/tonă în decembrie, 150.000 lei/tonă în ianuarie, 170.000 lei/tonă în

februarie.

Să se stabilească nivelul de producţie lunar astfel încât contractele să fie

satisfăcute cu cheltuieli minime.

Răspuns. Vom presupune că producţia se termină fără stoc.

Fie x x x x1 2 3 4, , , cantităţile de zahăr ce trebuiesc produse respectiv în lunile:

noiembrie, decembrie, ianuarie, februarie. Avem:

x i

x

x

x

x

x

x x

x x x

x x x x

i

0 1

55000

40000

25000

50000

20000

20000 30000

50000 50000

100 000 40 000

1

2

3

4

1

2 1

3 1 2

4 1 2 3

,4

. .

( x1 20000 - reprezintă excedentul din noiembrie.)

Considerând cheltuielile de producţie şi cele de depozitare în mii lei

funcţia obiectiv devine:

f x x x x x x x x

x x x

140 160 150 170 2 20000 2 50000

2 100000

1 2 3 4 1 1 2

1 2 3

Deci avem de calculat minimul funcţiei:

f x x x x x 146 164 152 170 3400001 2 3 4 .

23.) Un atelier de construcţii metalice dispune de ţevi cu lungimea de 5m,

din care trebuie să taie cel puţin 35 ţevi în lungime de 2m, 25 ţevi de 2,5m şi 10

ţevi de 3m lungime. Cum trebuie procedat astfel ca să se realizeze consumuri

minime de material?

Răspuns: Există patru variante de a tăia o ţeavă de 5m lungime în bucăţi

cu lungimile specificate:

40

v

v

v

v

1

2

3

4

5 2 2 1

5 2 5 2 5

5 3 2

5 2 2 5 0,5

:

: , ,

:

: ,

Observăm că la prima variantă se pierde 1m de ţeavă, la cea de-a patra

0,5m iar la variantele a II-a şi a III-a nimic. Notând cu x x x x1 2 3 4, , , numărul

ţevilor de 5m care se taie respectiv după variantele v v v v1 2 3 4, , , vom avea:

min .

,4

f x x

x x x

x x

x

x ii

1 4

1 3 4

2 4

3

0,5

2 35

2 25

10

0 1

Vom obţine x x x x1 2 3 40 5 10 15 , , ,

24.) Fiecare animal dintr-o fermă are nevoie de o cantitate minimă de

principii nutririve pe zi care depinde de specie, vârstă, scop urmărit în

alimentaţie.

Principiile nutritive se află în diferite proporţii în produsele ce compun

raţia furajeră. Folosind datele din tabelul de mai jos să se determine cantitatea x

din alimentul A1 şi cantitatea y din alimentul A2 exprimate în kilograme, ce

trebuie să intre în compoziţia raţiei furajere a unui animal astfel încât costul ei

să fie minim.

Denumirea

principiilor nutritive

Conţinutul în principii

nutritive al alimentelor (kg)

Cantităţile minime

prescrise (kg)

A1 A2

P1

P2

P3

P4

0,1

0

0,1

0,2

0

0,1

0,2

0,1

0,4

0,6

2

1,7

Costul (lei/kg) 240 80

41

Indicaţie: problema se transcrie matematic astfel:

0,1 0,4

0,1 0,6

0,1 0,2 2

0,2 0,1 1

0

240 80

x

y

x y

x y

x y

f x y

,7

,

min

Se găseşte x y 4 9,