II. Metode Simplex Pentru Modele Liniare

II. METODE SIMPLEX PENTRU MODELE LINIARE

1. Algoritmul simplex primal. Descriere.

Pentru rezolvarea modelelor liniare, au apărut, începând cu 1948, mai multe metode, dintre care amintim: metoda simplex cu variantele sale, metoda Kantorovici, metoda relaxării. Dintre toate metodele apărute în literatura de specialitate, cea mai răspândită este cea elaborată de G. B. Dantzig.

Algoritmul propus de Dantzig permite determinarea unei soluţii admisibile de bază optime, dacă există, prin examinarea parţială dirijată a mulţimii soluţiilor admisibile de bază; mai precis, vor fi testate o parte din soluţiile admisibile de bază. În mod empiric, pe baza unor experienţe de calcul efectuate timp de 10 ani, s-a stabilit că soluţia optimă, dacă există, se obţine după cel mult 3m iteraţii (m = rangA). Fiecare dintre aceste noi iteraţii constă în găsirea unei noi soluţii admisibile de bază căreia îi corespunde o valoare mai bună a funcţiei obiectiv decât în situaţia precedentă.

1.a) Teoreme fundamentale ale algoritmului simplex primal

Se consideră o problemă de programare liniară sub formă standard:

bAX = , unde ( )RnmMA ×∈ , nmA <=rang ; 0≥b şi Ii∈∃ a.î.

(P) 0≥X CXxf =)([max]

0≥ib

Analiza economico-matematică a unor modele liniare

Fie 1X o SAB corespunzătoare bazei ( ) 11

BJssaB ∈= , în raport cu care

se va explicita sistemul de restricţii ( ) ( ) RB RXBbBX ⋅−⋅=−− 11111

, unde

( ) ( ) 0111 ≥=⋅

− BnotXbB . Elementele vectorului ( ) ( )Tm

B xxxX ...., , , 21

1

= sunt

valorile variabilelor bazice, deci, componentele nenegative ale vectorului 1X .

Teorema 1: Criteriul de îmbunătăţire a unei soluţii admisibile de bază

Fie problema de programare liniară (P), 1B o bază în mR şi 1X soluţia admisibilă de bază corespunzătoare ei. Dacă pentru un indice

BJJj −∈ , 0<− jj cf şi există cel puţin un indice 1BJs∈ astfel încât

0>sjy , atunci 1X poate fi înlocuită printr-o soluţie admisibilă de bază 2X

cel puţin la fel de bună, în sensul )()( 21 XfXf ≤ . Soluţia admisibilă 2X corespunde bazei 2B dedusă din 1B prin înlocuirea lui ka ,

1BJk∈ , cu

la , 1BJJl −∈ . Indicii l şi k sunt daţi de relaţiile:

II.1.1 { } 0 |min11 <−−

−∈=− jjjjB

cfcfJJj

cf

şi

II.1.2 ⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧

>∈

= 0min sjsj

s

Bkl

k yyx

Jsyx

.

Teorema 2: Testul de optimalitate O soluţie admisibilă de bază, X , a problemei (P) este optimă dacă şi numai dacă II.1.3 0≥− jj cf , Jj∈∀ .

Metode simplex pentru modele liniare

Observaţia 1 : Dacă există SABX astfel încât să fie identificate relaţiile

II.1.3 - numite criteriu de optimalitate - atunci +∞<<)([max] xf .

Observaţia 2: Relaţia II.1.4 0≤− jj cf , Jj∈∀

este criteriu de optimalitate dacă se cere minimizarea funcţiei liniare f.

Observaţia 3: 0=− ss cf , BJs∈∀ , unde BJ reprezintă mulţimea indicilor

variabilelor bazice.

Corolar: Soluţia optimă *X este unic determinată dacă

II.1.5 0>− jj cf , BJJj −∈∀ (adică, oricare j pentru care ja este

nebazic). Teorema 3: Testul de optim infinit

Dacă pentru o soluţie admisibilă de bază a problemei considerate

există un indice BJJl −∈ astfel încât 0≤− ll cf şi 0≤sly , BJs∈∀ ,

atunci (P) are optim infinit. Observaţia 4: Pentru problemele cu funcţia obiectiv f[min] , criteriul de

recunoaştere a optimului nemărginit (teorema 3) este:

BJJl −∈∃ astfel încât 0>− ll cf şi 0≤sly , BJs∈∀ .

Din enunţul teoremei rezultă că o problemă de programare liniară

are optim infinit dacă există un vector nebazic cu toate componentele nenegative ( ( )ssll ya = , 0≤sly , s∀ ), pentru care ll cf − nu satisface

criteriul de optimalitate al tipului său de optim.


Concluziile celor trei teoreme sunt sistematizate în tabelul următor:

Soluţie optimă finită ([opt]f<<∞ ) unic

determinată multiplă Optim infinit

[max]

0>− jj cf , BJJj −∈∀

0=− jj cf , BJj∈∀

0≥− jj cf , },..,1{ nj∈∀

şi BJJk −∈∃ a.î.

0=− kk cf

BJJl −∈∃ a.î.

0<− ll cf şi

0≤sly , BJs∈∀

[min]

0=− jj cf , BJj∈∀

0<− jj cf , BJJj −∈∀

0≤− jj cf , },..,1{ nj∈∀

şi BJJk −∈∃ a.î.

0=− kk cf

BJJl −∈∃ a.î.

0>− ll cf şi

0≤sly , BJs∈∀

1.b) Schema de rezolvare prin algoritmul simplex – primal:

Modelul matematic. Forma standard

bAX = , 0≥X , ( ) cXXf =[max]

nmA nm <=×rang , 0≥b , 0>∃ kb , mk ,1∈

Se generează o SAB →)1(X )...( 1 maaB = şi )...( 1 nm aaR += ⇒

⎟⎟⎠

⎞⎜⎜⎝

⎛

===

=−

0

1)1(

R

BB

xxbBx

X , },...,1{ mJ B =


DA

Calculează:

•⎪⎩

⎪⎨

⎧

≤≥

∀−⋅⋅=− −

nebazic vector pentru , 0sau nebazic, vector pentru , 0

bazic vector pentru , 0 este care 1

j

j

j

jjB

jj

aaa

caBccf

• bBcf B ⋅⋅= −10

STOP. Problema admite soluţie optimă finită

ff [max]0 = ; ⎟⎟⎠

⎞⎜⎜⎝

⎛=

−

0

1* bB

X

)(∃ vector nebazic cu componentele negative şi diferenţa

strict negativă?

( BJJl \∈∃ a.î. 0<− ll cf

şi 0≤sly , Is∈∀

STOP. Problema admite optim nemărginit

(1)

NU

nj

cf jj

,1

0

=∀

≥− DA


Se aplică: • criteriul de intrare în bază (C.I.B): { } rrjjcf

cfcfjj

−=−<− 0

min ;

• criteriul de eliminare din bază (C.E.B): kr

k

sr

s

Isoy y

xyx

sr

=⎭⎬⎫

⎩⎨⎧

∈>

min raport unic.

Observaţii: - ka va fi eliminat de ra ;

- 0>kry este pivotul iteraţiei; - dacă raportul nu este unic determinat, se lucrează cu problema perturbată sau se aplică

metoda lexicografică pentru a stabili ce vector va fi eliminat.

Se trece la )2(SABX , unde ( ) ( ))2()1( XfXf ≤

( )mkkk aaaaa ... ... 111 +− ( )mkrk aaaaa ... ... 111 +−→

( ) }{}{\: rkJJ BB U=⇒

Se calculează componentele vectorilor în noua bază:

1) Elementele din linia pivotului, linia k: kr

kn

kr

k

kr

k

yy

yy

yx

,....,, 1 ;

2) Vectorii care se menţin în bază îşi menţin componentele; dacă ra a luat locul lui ka ,

atunci, în noua bază, ra va avea componentele lui ka ; 3) Pentru orice altă componentă care nu a fost calculată la 1) sau 2), se aplică una dintre

formulele:

kr

irkkrii y

yxyxx

⋅−⋅=: , pentru }{\ rJi B∈

kr

irkjkrijij y

yyyyy

⋅−⋅=: , pentru Jj∈

(1)

NU


Observaţia 5:

• numărul soluţiilor admisibile de bază este cel mult mnC ;

• trecerea de la o iteraţie la alta presupune trecerea de la o SAB la o altă soluţie admisibilă de bază, cel puţin la fel de bună în sensul dat de optimul funcţiei; rezultă că după un număr finit de paşi acest procedeu iterativ se opreşte dacă nu apare fenomenul de ciclare. Observaţia 6: Prin algoritmul simplex sunt examinate numai soluţiile admisibile de bază. Procedura de iterare a algoritmului simplex se opreşte atunci când nu va mai exista nici un vector care, introdus în bază, să ducă la creşterea valorii funcţiei scop, dacă problema admite optim finit. Din punct

de vedere geometric se ajunge la punctul de extrem al mulţimii χ care

optimizează funcţia scop. Observaţia 7: Prin trecerea de la o SAB la o alta cel puţin la fel de bună în sensul dat de tipul de optim al funcţiei )(Xf , se realizează o creştere a

acesteia cu ( )rrkr

k cfyx

− .

Observaţia 8: Când scopul este de a minimiza funcţia obiectiv, algoritmul se modifică, în sensul maximizării funcţiei ( )f− .

1.c) Aplicaţii ale algoritmului simplex În continuare vom exemplifica aplicarea algoritmului în trei modele

distincte. Model liniar cu optim finit, unic determinat Specific acestui prim exemplu, care va fi studiat, este că prin

aducerea la forma standard apar m vectori care formează o bază în spaţiul bunurilor.


Etapa 0: Se consideră un model simplificat al unui proces de fabricare a trei

produse, prin utilizarea limitată a trei resurse:

3,1,0

9002280042

6802171620[max]

321

321

21

321

=∀≥

⎪⎩

⎪⎨

⎧

≤++≤++

≤+

++=

jx

xxxxxx

xxxxxf

j

,

cu forma standard:

II.1.6

6,1,0

9002280042

6802000171620[max]

6321

5321

421

654321

=∀≥

⎪⎩

⎪⎨

⎧

=+++=+++

=++

+++++=

jx

xxxxxxxx

xxxxxxxxxf

j

.

Etapa 1: Generarea unei soluţii admisibile de start.

Pasul 1 • Se scrie matricea A şi se verifică apoi condiţia 63rang 63 <=×A :

654321 100122010412001021

aaaaaa

A⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡=

şi rangA = 3 < 6.


• Se scrie baza de start şi se deduce soluţia admisibilă de bază (SAB) de start: ( ) 36541 IaaaB == este baza de start formată din vectorii

unitate 4a , 5a şi 6a . Aşadar, ⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛=

6

5

41

xxx

X B , ⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛=

3

2

11

xxx

X R , de unde rezultă

explicitarea sistemului în raport cu baza 1B :

II.1.7 ⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛⋅⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡−⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛=

⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛⋅⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡

3

2

1

6

5

4

122412021

900800680

100010001

xxx

xxx

Se stabileşte SAB de start:

Bnot

X=⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛

900800680

şi ⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛=

000

RX , sau

( )TSABX 900800680000= .

Observaţia 9: Nu are importanţă ce coloane ale matricii A sunt vectori

liniar independenţi în mR ; important pentru rapiditatea găsirii soluţiei optime este ca A să conţină o matrice unitate.


Pasul 2

( ) ( ) 0900800680

000)( 6541

0 =⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛⋅=⋅=⋅== BBB XcccXcXff ;

( ) 0221

000 311

31 =⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛⋅⋅=⋅⋅= − IaIcf B ,

( ) 0212

000 321

32 =⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛⋅⋅=⋅⋅= − IaIcf B ;

( ) 0140

000 331

33 =⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛⋅⋅=⋅⋅= − IaIcf B ,

( ) 0001

000 341

34 =⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛⋅⋅=⋅⋅= − IaIcf B ;

( ) 0010

000 351

35 =⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛⋅⋅=⋅⋅= − IaIcf B ,

( ) 0100

000 361

36 =⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛⋅⋅=⋅⋅= − IaIcf B .

De obicei, calculele implicate de aplicarea algoritmului simplex sunt

organizate în tabelele simplex, care au cel mult 4+m linii şi 4+n coloane, şi corespund unei baze. În continuare va fi dat tabelul corespunzător bazei de start.


T. II.1.1

→jc 20 16 17 0 0 0 Bc B BX 1a 2a 3a 4a 5a 6a ρ

0 4a 680 1 2 0 1 0 0 680/1 0 5a 800 2 1 4 0 1 0 800/2 (minim) 0 6a 900 2 2 1 0 0 1 900/2 jf 0 0 0 0 0 0 0 jj cf − -20 -16 -17 Ø Ø Ø

Pasul 3 Este verificat testul de optimalitate (vezi teorema 2)?

Pentru problema de faţă, 0<− jj cf , 3,2,1=j şi 0=− jj cf ,

6,5,4=j ⇒ se trece la Pasul 4.

Pasul 4 Se verifică dacă problema admite optim infinit (teorema 3):

Din T.II.1.1 se observă că nu există vector nebazic ( )321 aaa cu toate

componentele negative şi pentru care 0<− ll cf .

BJJl −∈∃ astfel încât 0<− ll cf şi 0≤sly , BJs∈∀ ?

DA STOP. 1X este soluţia optimă a problemei şi 0f valoarea maximă a funcţiei obiectiv.

NU Pasul 4

DA STOP.

+∞=f[max]

NU Pasul 5

0≥− jj cf , nj ,1=∀ ?


Pasul 5 Dacă algoritmul nu se opreşte la Pasul 3 sau Pasul 4,

rezultă că soluţia testată, 1X , nu este optimală, deci, trebuie să se treacă la o

nouă SAB, 2X , cel puţin la fel de bună ca 1X , în sensul că ( ) ( )21 XfXf ≤ .

Pentru aceasta se vor executa două operaţii.

Operaţia 1: Se aplică criteriul de intrare în bază:

{ } llljjjjJJj

f acfcfcfB

⇒−=<−−⎯⎯ →⎯−∈

0min C.I.B [max] va intra în

bază.

Operaţia 2: Se aplică criteriul de eliminare din bază:

[ ]

[ ]

kl

ksl

sl

s

Jssl

sl

s

Js

f

f ab

ab

yyx

BB=

⎭⎬⎫

⎩⎨⎧

>=⎭⎬⎫

⎩⎨⎧

>=→∈∈

0a min0 min C.E.Bmax

minρ , pentru 1X ,

sau, în general, kl

k

yx

=ρ , de unde rezultă că ka va fi eliminat, iar kly devine

pivotul iteraţiei. Se va presupune că pivotul este unic, ceea ce este echivalent cu a spune că noua SAB are m componente strict pozitive.

Rapoartele calculate se trec în ultima coloană din tabelul II.1.1. În cazul nostru, avem:

Operaţia 1: { } { } 113,2,12017- 16,- ,20min0min cfcfcf jjjjj

−=−=−=<−−=

,

de unde rezultă că 1a va intra în noua bază (l=1).

Operaţia 2: 21

2

33

3

21

2

11

1

2800

2900,

2800,

1680min,,min

ab

ab

ab

ab

==⎭⎬⎫

⎩⎨⎧=

⎭⎬⎫

⎩⎨⎧

⇒

2a va fi eliminat şi 221 =a este pivotul iteraţiei, pe care îl vom colora în tabel.


Cele trei rapoarte se trec în ultima coloană a tabelului T.II.1.1; dacă

un raport nu se poate calcula – în sensul dat de C.E.B – în ultima coloană, pe acel loc, se va trece “/ “ sau “-“ .

Pasul 6 Conform teoremei 1, se trece de la soluţia admisibilă de bază 1X la soluţia admisibilă de bază 2X ce corespunde bazei 2B dedusă din 1B prin înlocuirea vectorului ka cu vectorul la :

( )nklk aaaaaB ...... 1112 +−= şi }{}){( 12 lkJJ BB U−= .

Se trece la un nou tabel simplex. Se vor scrie vectorii nebazici şi

BX în noua bază. Aceste calcule ce vor fi trecute în tabelul T.II.1.3 – iteraţia 2 a algoritmului simplex – sunt efectuate în conformitate cu calculele implicate de metoda eliminării complete: • Dacă un vector se menţine în bază, atunci el îşi menţine componentele ( )mkk aaaa ...... 11 + ; dacă vectorul ka este eliminat din bază de către la , atunci acesta îi ia componentele (vezi tabelul T.II.1.2). În particular, vectorii 4a , 6a îşi menţin componentele, iar vectorul 1a va avea componentele lui 5a din iteraţia 1. • Elementele din linia vectorului la se obţin împărţind elementele din linia vectorului ka , iteraraţia precedentă, la pivotul iteraţiei, kly . Astfel,

elementele din linia 2, iteraţia 2, iau valorile 20,

21,

20,

24,

21,

22,

2800 .

Formulele de trecere de la o iteraţie la alta pot fi sistematizate direct în tabelul simplex:

T.II.1.2 →jc 1c .

1−kc kc 1+kc . mc 1+mc .

jc . lc .

nc

Bc B B

X 1a . 1−ka ka 1+ka . ma 1+ma . ja . la . na ρ

1c 1a kl

lkkl

a

abab11

⋅−⋅

. . 0

kla

la1−

0 . 0 0

.

.

. . .

. . . . . . . .

1−kc 1−ka

kl

lkkklk

a

abab11 −+

⋅−⋅

. . 1

kla

lka

1−−

0 . 0

kla

ilakjaklaija ⋅−⋅

2BJJj −∈∀

0

lc la kl

k

a

b

. . .

kla

1

0 . .

kla

kma

1+

. . . 1 .

klakn

a

1+kc 1+ka kl

lkkklk

a

abab11 ++

⋅−⋅

. . 0

kla

lka

1+−

1 . 0 0

.

.

. . .

. . . . . . . .

mc ma kl

mlkklm

a

abab ⋅−⋅

. . 0 . 0 . 1

0

jf 0f 1f . . kf . .

mf lf

nf

j

j

c

f −

1

1

c

f −. 0

kckf − 0 .

mc

mf −

1

1

+

−+

mc

mf

. . .

lc

lf −

.

nc

nf −


După efectuarea calculelor, se revine la pasul 2. Pentru exemplul numeric de mai înainte, obţinem:

2802

18002680=

⋅−⋅

1002

28002900=

⋅−⋅

BX

2a

• prima componentă • a treia componentă

1 2 1

2

1 2 2

2

21122:12⋅−⋅

=y

21222:32⋅−⋅

=y


Rezultatele calculelor pentru exemplul numeric propus, până la oprirea algoritmului, sunt date în tabelul II.1.3:

T.II.1.3 →jc

20 16 17 0 0 0

Bc

B BX 1a

2a 3a

4a

5a 6a ρ

0 4a 280 0 3/2 -2 1 -1/2 0 280/3/

2

20 1a 400 1 1/2 2 0 1/2 0 400/2

0 6a 100 0 1 -3 0 -1 1 100/2

jf 8000 20 10 40 0 10 0

jj cf −

Ø -6 23 Ø 10 Ø 0≥ ? NU

0 4a 130 0 0 5/2 1 1 -3/2

20 1a 350 1 0 7/2 0 1 -1/2

16 2a 100 0 1 -3 0 -1 1

jf 8600 20 16 22 0 4 6

jj cf −

Ø Ø 5 Ø 4 6 0≥ ? DA⇒ STOP

În linia test jj cf − este verificat criteriul de optimalitate, motiv

pentru care algoritmul se opreşte, modelul liniar admiţând soluţie optimă finită.

Iteraţia 2

Iteraţia 3


Citirea soluţiei:

Baza optimă Variabile bazice Valori optimale 4a 4x 130

1a 1x 350

2a 2x 100

Variabile nebazice Valori optimale

3x 0

5x 0

6x 0

Soluţia optimă ( )TX 001300100350* = este:

• unic determinată, deoarece 0>− jj cf , pentru ja∀ nebazic;

• nedegenerată, pentru că numărul componentelor strict pozitive este egal cu rangA=3. • 08600[max] ff == în ultimul tabel, numit şi tabel optimal.

Modelul liniar cu optim nemărginit

Considerăm următorul program liniar

4,1 , 0

1

121

22[max]

432

431

4321

=≥

⎪⎩

⎪⎨⎧

=−+

=+−

+++=

jx

xxx

xxx

xxxxf

j


Vom studia natura sa aplicând algoritmul propus de Dantzig.

Deoarece 011

>⎟⎟⎠

⎞⎜⎜⎝

⎛=b ,

4321 11102/1101

aaaa

A ⎥⎦

⎤⎢⎣

⎡−

−=

, rang A=2<4 şi

( )211001

aaB =⎥⎦

⎤⎢⎣

⎡= , rezultă că scrierea canonică a sistemului de restricţii

⎟⎟⎠

⎞⎜⎜⎝

⎛=⎟⎟

⎠

⎞⎜⎜⎝

⎛⋅⎥

⎦

⎤⎢⎣

⎡−

−+⎟⎟

⎠

⎞⎜⎜⎝

⎛⋅⎥

⎦

⎤⎢⎣

⎡11

112/11

1001

4

3

2

1

xx

xx

,

evidenţiază o SAB de start, şi anume, ( )TSABX 0011= .

Calculele implicate de aplicarea algoritmului sunt sistematizate în

următorul tabel simplex:

→jc

1 2 2 1

Bc

B BX 1a 2a

3a 4a ρ

1 1a 1 1 0 -1 1/2 1/(1/2)

2 2a 1 0 1 1 -1 -

jf 3 1 2 1 -3/2

jj cf −

Ø Ø -1 -5/2 0≥ ? NU; Th.3? NU ⇒Th.1

1 4a 2 2 0 -2 1 -

2 2a 3 2 1 -1 0 -

jf 8 6 2 -4 1

jj cf −

5 Ø -6 Ø 0≥ ? NU; Th.3? DA


În ultima linie există un vector nebazic, şi anume 3a , pentru care

033 <− cf şi ⎩⎨⎧

<−=<−=

0102

23

13

yy

3.Th

⇒ STOP: +∞=f[max]

Vom investiga natura programului dual.

121: 124 −= uud

2: 22 =ud

2: 123 += uud

1: 11 =ud

O 1u

2u

121

21 ≥−⋅ uu

4321 1221[max] xxxxf ⋅+++⋅=

( )⎪⎩

⎪⎨⎧

=⋅−+⋅+⋅+⋅

=⋅+⋅−+⋅+⋅

1 )1( 1 1 0

1 21 1 0 1

4321

4321

xxxx

xxxx

01 ≥x 02 ≥x 03 ≥x 04 ≥x

21[min] uug +=

R∈2u

( ) 21 21 ≥+⋅− uu

R∈1u

21 2 ≥⋅u10 21 ≥⋅+ uu


Din rezolvarea grafică a problemei duale, se observă că χ Φ= . Nu

există ( )21 uu , R∈iu , 2,1=i , care să verifice simultan cele 4 restricţii.

Să reţinem că, dacă o problemă de programare liniară are optim infinit, atunci duala sa nu are soluţie. Este aceasta o afirmaţie general valabilă? Răspunsul îl vom afla în următorul capitol.

2. Generarea SAB prin metode particulare

În continuare, vom analiza cazul în care matricea A, după aducerea

la forma standard, nu conţine o bază unitate din spaţiul mR . În general, în matricea A din modelele matematice corespunzătoare unor procese reale nu apare complet mI . Pentru a genera o soluţie admisibilă de bază a problemei

date, dacă acest lucru este posibil, se poate alege una din variantele:

• Scrierea explicită a sistemului de restricţii în raport cu o bază din mR . • Metoda celor două faze. • Metoda bazei artificiale. a) Metoda bazei artificiale (1953 A. Chaines, W. Cooper, D. Fan)

Se consideră un model matematic sub forma sa standard:

II.2.1 ( )⎪

⎩

⎪⎨

⎧

=≥=

cXXfX

bAX

[max]0 şi nmA nm <=×rang , 0≥b , Ik ∈∃ a.î. 0≥kb .

Presupunem că matricea A nu conţine o bază unitate de ordinul m.

Prin această metodă se urmăreşte generarea unei SAB pentru (II.2.1), dacă acest lucru este posibil, folosind numai algoritmul simplex primal.


Metoda bazei artificiale presupune parcurgerea următoarelor etape: Etapa 1 Se extinde problema prin introducerea a m variabile artificiale care vor fi penalizate în funcţia obiectiv:

II.2.2 ⎪⎩

⎪⎨

⎧

−=≥≥

=+

a

a

am

XCXfXX

bXIAX

α[max]0 ,0 ,

unde 0>>α , mI este matricea unitate de ordin m, ( )Tamn

ana xxX ++= ...1 este

vectorul coloană cu componentele ainx + , mi ,1∈ , variabile artificiale. Din

scrierea AXbX a −= , rezultă soluţia de start:

SABX ⎩⎨⎧

==

bXX

a

0 .

Pentru a exemplifica parcurgerea acestei etape, considerăm modelul

liniar:

3,1 , 0

42634

423[max]

321

321

321

∈≥⎩⎨⎧

=++=++

++=

jx

xxxxxx

xxxf

j

, unde ⎥⎦

⎤⎢⎣

⎡=

112341

A , ⎟⎟⎠

⎞⎜⎜⎝

⎛=

46

b , rangA=2<3.

321 aaa


Se constată că baza ⎥⎦

⎤⎢⎣

⎡=

1001

B nu poate fi formată cu ajutorul unor vectori

din A, motiv pentru care se trece la forma extinsă:

5,1 , 0

42634

)(423[max]

5321

4321

54321

∈≥⎩⎨⎧

=+++=+++

+−++=

jx

xxxxxxxx

xxxxxf

j

a

a

aaα

, 0>>α În noua matrice

⎥⎦

⎤⎢⎣

⎡=

1011201341

A , apare baza ( )54 aaB = , care permite scrierea

soluţiei de start 54321 aaaaa pentru problema extinsă: 0321 === xxx ,

64 =ax , 45 =ax şi f va fi 0)46( <−− αα .

Observaţia 1: Valoarea funcţiei obiectiv este o valoare foarte mică ( 0≥ib ,

mi ,1=∀ şi 0>>α ). Deoarece se cere maximizarea lui f, ideal ar fi ca în

soluţia optimă toate variabilele artificiale să aibă valoarea 0. Variabilele artificiale au fost “penalizate” în funcţia obiectiv cu coeficienţi foarte mici, pentru ca algoritmul simplex să le elimine din bază. Dacă se cere f[min] ,

atunci ele vor fi penalizate cu coeficienţi foarte mari: ( )amn

an xx ++ ++ ...1α , cu

0>>α , ceea ce s-ar traduce printr-o comportare nerentabilă în raport cu tipul de optim. Etapa 2: Se aplică algoritmul simplex problemei extinse. Presupunem că

după k iteraţii, *Nk∈ , ∞<k , avem 0≥− jj cf , mnj += ,1 , deci,

problema extinsă admite soluţie optimă finită.


La baza discuţiei ce va urma, relativ la existenţa sau nonexistenţa soluţiei optime a problemei iniţiale, stau următoarele teoreme:

După oprirea algoritmului, se discută natura problemei iniţiale după cum urmează: Cazul 1: Soluţia optimă a problemei extinse nu conţine nici o variabilă artificială cu valoare strict pozitivă ⇒ soluţia optimă a problemei II.2.1 se obţine considerând numai valorile optimale ale variabilelor nxx ,...,1 .

Cazul 2: În soluţia optimă există cel puţin o variabilă artificială cu valoare strict pozitivă; în acest caz, problema iniţială nu are soluţie. Observaţia 2: Deoarece funcţia obiectiv este de forma ( )aXCX α− ,

diferenţele jj cf − vor fi funcţii liniare de α . Să presupunem că la o

anumită iteraţie există ( ) 0)( <− αjj cf pentru cel puţin doi indici. Va intra

în noua bază vectorul la dacă ( ) )(αll cf − va avea cel mai mic coeficient

negativ (respectiv, pentru f[min] , cel mai mare coeficient pozitiv).

Observaţia 3: Să presupunem că algoritmul s-a oprit la iteraţia *Nk ∈ ,

+∞<k , şi că la iteraţia *Nr∈ , kr < , s-a obţinut o bază formată numai cu vectori din A (fără vectori artificiali). SAB corespunzătoare acestei baze

Teorema 1 Dacă II.2.1 are soluţie optimă finită, atunci ea va fi optimă şi pentru II.2.2. Orice soluţie optimă a problemei extinse care nu conţine nici o variabilă artificială strict pozitivă este soluţie optimă şi pentru problema iniţială, după înlăturarea variabilelor artificiale.

Teorema 2 Dacă II.2.1 are funcţia obiectiv nemăr-ginită, atunci şi II.2.2 are funcţia obiectiv nemărginită. Reciproca este adevărată.


este o SAB pentru problema iniţială. Practic, la această etapă, se aplică algoritmul simplex primal pentru problema originară. Observaţia 4: În general, dacă a fost eliminat un vector artificial din bază, componentele sale nu vor mai fi calculate la următoarele iteraţii. Nu se recomandă acest lucru atunci când se cere soluţia optimă a dualei sau se pune problema postoptimizării modelului.

Se continuă problema prin aplicarea algoritmului simplex primal

→jc 3 2 4 α− α−

Bc B B

X 1a 2a 3a 4a 5a ρ

α− 4a 6 1 4 3 1 0 6/4

α− 5a 4 2 1 1 0 1 4/1

jf α10− α3− α5− α4− α− α−

jj cf − 33 −− α 25 −− α 44 −− α Ø Ø 0≥ ?j∀ NU

2 2a 3/2 1/4 1 3/4 1/4 0 6

α− 5a 5/2 5/4 0 1/4 -1/4 1 2

jf 32/5 +− α 4/52/1 α− 2 4/2/3 α− 4/2/1 α+ α−

jj cf − 4/52/5 α−− Ø 4/52/5 α−− 2/52/1 α+ Ø

0≥ ?j∀ NU

2 2a 1 0 1 7/10 3/10 -1/5 10/7

3 1a 2 1 0 1/5 -1/5 4/5 10

jf 8 3 2 2 0 2

jj cf − Ø Ø -2 α α+2 0≥ ?j∀ NU

4 3a 10/7 0 10/7 1 3/7 -2/7

3 1a 12/7 1 -2/7 0 -2/7 6/7

jf 76/7 3 24/7 24 6/7 10/7

jj cf − Ø 20/7 Ø α+7/6 α+7/10 0≥ ⇒ DA STOP


• Exemplificarea observaţiei 2: Iteraţia 1 C.I.B: { }=−−−− 4-4- ,25 ,33min ααα 2225 cf −=−− α sau

min{-3, -5, -4}=-5 ⇒ 2a eliminat.

Iteraţia 2 C.I.B: min{-5/4, -1/4}=-5/4 ⇒ 1a va intra în bază.

La iteraţia a 3-a, variabilele artificiale au fost eliminate şi dispunem acum de o bază a problemei iniţiale: ( )12 , aa , cu 21 =x , 12 =x , 03 =x .

• Exemplificarea observaţiei 1: în soluţia optimă a problemei extinse,

712*

1 =x , 0*2 =x ,

710*

3 =x , 0*4 =x , 0*

5 =x , toate variabilele artificiale au

valori nule. Conform unei teoreme enunţată anterior în acest capitol,

problema iniţială admite soluţia optimă finită T

X ⎟⎠⎞

⎜⎝⎛=

7100

712* şi

776[max] =f .

Considerăm acum un alt exemplu pentru a aplica metoda şi în cazul

în care se impune minimizarea funcţiei scop. Rezolvarea problemei, fără comentarii, este redată în cele ce urmează:

3,1 ,0

1822043

6225[min]

32

32

321

321

=≥

⎪⎩

⎪⎨

⎧

≥+=+≥++

++=

jx

xxxx

xxxxxxf

j

⇒ forma standard

5,1 ,0

1822043

6225[min]

532

32

4321

321

=≥

⎪⎩

⎪⎨

⎧

=−+=+

=−++

++=

jx

xxxxx

xxxxxxxf

j

.


54321 10210

0043001121

aaaaa

A⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡

−

−=

, rang A=3< 5, 018206

>⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛=b ,

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡=

100010001

3B nu

poate fi formată numai cu coloane din A, dar 31 Ba ∈ .

Etapa 1: Forma extinsă:

aa xxxxxf 74321 25[min] αα ++++= ; .0>>α

7,1 ,0

1822043

62

7532

632

4321

=≥

⎪⎩

⎪⎨

⎧

=+−+=++=−++

jx

xxxxxxx

xxxx

j

a

a

,

7654321 101021001004300001121

aaaaaaa

A⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡

−

−=

⇒

⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛=

7

6

1

xxx

X B

⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛=

18206

( )761 aaaB = ⇒ SABX

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

=

⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜

⎝

⎛

=

0000

5

4

3

2

xxxx

X R


Tabelul simplex:

→jc 5 1 2 0 0 α α

Bc B B

X 1a 2a 3a 4a 5a 6a 7a ρ

5 1a 6 1 2 1 -1 0 0 0 6/1

α 4a 20 0 3 4 0 0 1 0 20/4 (min)

α 7a 18 0 1 2 0 -1 0 1 18/2

jf α3830 + 5 104 +α 56 +α -5 α− α α f[min]

jj cf − Ø 94 +α 36 +α -3 α− Ø Ø ? 0 j∀≤ NU

5 1a 1 1 5/4 0 -1 0 -1/4 0

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

α 7a 8 0 -1/2 0 0 -1 -1/2 1

jf α815 + 5 2/4/31 α− 2 -5 α− 2/4/3 α−− α f[min]

jj cf − Ø

2/4/27 α− Ø -5 α− 2/34/3 α−−

Ø ? 0 j∀≤ DA

⇒ STOP

Problema extinsă admite soluţia optimă finită 1*

1 =x , 0*2 =x ,

5*3 =x , 0*

4 =x , 0*5 =x , 0*

6 =x , 8*7 =x , care are o variabilă artificială

bazică cu valoare strict pozitivă. Conform teoremei 2, problema propusă spre rezolvare este fără soluţie. b) Metoda celor două faze (1954, G.B. Dantzig, A. Orden, P. Wolfe)

Se menţin ipotezele de lucru de la metoda bazei artificiale. Ca şi la metoda precedentă, se urmăreşte generarea unei SAB pentru II.2.1 ori de câte ori calculul direct al unei astfel de soluţii este dificil datorită dimensiunilor problemei (m şi/sau n foarte mari). Aceste două metode pun la dispoziţia utilizatorului procedee generale de generare a soluţiilor admisibile de bază, sau informaţia că problema nu are soluţii ceea ce ar putea indica o modelare greşită a procesului economic.


Metoda celor două faze constă în parcurgerea următoarelor etape: Faza 1: Scopul acestei etape este de a obţine, dacă este posibil, o SAB de start pentru II.2.1, aplicând algoritmul simplex-primal problemei auxiliare:

II.2.3 ( ) ( )mT

mninn bbxxxBXA ......... 11 =⋅+⋅ +++ ,

unde inx + este variabila artificială adăugată numai părţii stângi a restricţiei i

, mi ,1= , iar B este matricea unitate de ordinul m=rangA.

II.2.4 0≥X , 0≥aX ,

II.2.5 ∑=

+=m

iinxW

1[min] .

La această fază obiectivul va fi minimizarea sumei variabilelor articiale din restricţii, indiferent de tipul de optim al problemei considerate. Din II.2.3 rezultă că variabilele artificiale bazice sunt în SAB de start:

⎩⎨⎧

==

=bX

XX

aSAB

0. Se aplică algoritmul simplex primal problemei auxiliare.

Admitem că aceasta are soluţie optimă finită, deci există o SAB care

verifică criteriul de optimalitate: 0≤− jj cw , mnj +=∀ ,1 .

Atunci,

Faza 2: Se revine la

⎪⎩

⎪⎨

⎧

=

≥

=

CXXf

X

bAX

)([max]

0

NU

STOP II.2.1 nu are soluţii

0min =W DA

Se trece la rezolvarea ei prin metoda simplex primal cu SAB de start dată de soluţia optimă a problemei auxiliare, după ce au fost eliminate variabilele artificiale.


La baza metodei stau următoarele afirmaţii: Tema 1: Orice soluţie admisibilă de bază a problemei II.2.1 este SAB a problemei auxiliare cu 0=aX . Existenţa unei astfel de soluţii atrage în mod

necesar [min]W=0. Tema 2: Orice soluţie admisibilă de bază a problemei extinse pentru care W=0 este o SAB a problemei iniţiale.

Să exemplificăm numeric aplicarea acestei metode. Considerăm modelul liniar:

3,1 ,0

943832

302550[min]

321

321

321

=≥⎩⎨⎧

≥++≥++

++=

jx

xxxxxx

xxxf

j

, cu forma standard

5,1 ,0

943832

302550[min]

5321

4321

321

=≥⎩⎨⎧

=−++=−++

++=

jx

xxxxxxxx

xxxf

j

.

54321 10143

01321

aaaaa

A ⎥⎦

⎤⎢⎣

⎡−

−=

, ⎟⎟⎠

⎞⎜⎜⎝

⎛=

98

b , rangA=2<5. Întrucât matricea A nu

conţine 2 vectori unitari care să formeze baza unitate în 2R , vom aplica metoda celor două faze.


Faza 1: Se construieşte problema auxiliară

7,1 ,0

943832

[min]

75321

64321

76

=≥⎩⎨⎧

=+−++=+−++

+=

jx

xxxxxxxxxx

xxW

j

,

7654321 10101430101321

aaaaaaa

A ⎥⎦

⎤⎢⎣

⎡−

−=

. Deoarece

( ) ⎟⎟⎠

⎞⎜⎜⎝

⎛==

1001

76 aaB , rezultă ( )TaSAB XXX 98 ,0 : == . Se aplică

algoritmul simplex-primal:

→jc 0 0 0 0 0 1 1

Bc B B

X 1a 2a 3a 4a 5a 6a 7a ρ

1 6a 8 1 2 3 -1 0 1 0 8/2

1 7a 9 3 4 1 0 -1 0 1 8/4

jf 17 4 6 4 -1 -1 1 1

jj cf −

4 6 4 -1 -1 Ø Ø

1 6a 7/2 -1/2 0 5/2 -1 1/2 1 7/5

0 2a 9/4 3/4 1 1/4 0 -1/4 0 9

jf 7/2 -1/2 0 5/2 -1 1/2 1

jj cf −

-1/2 Ø 5/2 -1 1/2 Ø

0 3a 7/5 -1/5 0 1 -2/5 1/5

0 2a 19/10 4/5 1 0 1/10 -3/10

jf 0 0 0 0 0 0

jj cf −

0 Ø Ø 0 0

Problema extinsă are soluţie optimă finită: 0*1 =x , 10/19*

2 =x , 5/7*

3 =x , 0*7

*6

*5

*4 ==== xxxx ; [min]W=0 ⇒ se trece la faza 2.

0≤ 7,1=∀j ? NU.

0≤ 7,1=∀j ? NU.

0≤ 7,1=∀j ? DA⇒ STOP.


Observaţie: Coloana lui 7a nu ne mai interesează, deoarece variabila 7x , odată eliminată din bază, nu va mai fi reintrodusă ulterior. Idem pentru 6a .

Faza 2: Se revine la funcţia obiectiv din modelul originar. Problema de rezolvat va fi:

5,1 ,0

943832

302550[min]

5321

4321

321

=≥⎩⎨⎧

=−++=−++

++=

jx

xxxxxxxx

xxxf

j

, cu

⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜

⎝

⎛

=

⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜

⎝

⎛

=

00

5/710/19

0

5

4

3

2

1

xxxxx

X SAB obţinută prin

eliminarea variabilelor auxiliare din soluţia optimă găsită la faza 1. Se testează optimalitatea sa:

→jc

50 25 30 0 0

Bc

B BX 1a 2a 3a 4a 5a

1 3a 7/5 -1/5 0 1 -2/5 1/5

1 2a 19/10 4/5 1 0 1/10 -3/10

jf 89,5 14 25 30 -9,5 -1,5

jj cf −

-36 Ø Ø -9,5 -1,5

Problema admite soluţia optimă finită T

SABX ⎟⎠⎞

⎜⎝⎛= 00

57

10190 ,

cu [min]f=89,5. Vom continua studiul modelului matematic prin scrierea dualei:

3,1 ,0

943832

302550[min]

2321

1321

321

=≥⎩⎨⎧

→≥++→≥++

++=

jx

uxxxuxxx

xxxf

j

, pentru care duala este

2,1,03032542

50398[max]

21

21

21

21

=≥

⎪⎩

⎪⎨

⎧

≤+≤+≤+

+=

iuuuuu

uuuug

i

.

0≤ 5,1=∀j ? DA ⇒ STOP


Stabilim soluţia optimă a dualei (dacă există). Forma standard a

dualei va evidenţia o bază unitate în 3R . Într-adevăr,

5,1,0

3032542

50398[max]

521

421

321

21

=≥

⎪⎩

⎪⎨

⎧

=++=++=++

+=

iu

uuuuuu

uuuuug

i

,

54321 100130104200131

aaaaa

A⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡=

, rang A=3<5, 0302550

>⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛=b ,

( )543

100010001

aaaB =⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡= , ( )TSABX 30255000= .

Se aplică algoritmul simplex-primal:

→jc 8 9 0 0 0

Bc B B

X 1a 2a 3a 4a 5a ρ

0 3a 50 1 3 1 0 0 50/3

0 4a 25 2 4 0 1 0 25/4

0 5a 30 3 1 0 0 1 30/1

jf 0 0 0 0 0 0

jj cf − -8 -9 Ø Ø Ø

0 3a 125/4 -1/2 0 1 3/4 0

9 2a 25/4 1/2 1 0 1/4 0 25/2

0 5a 95/4 5/2 0 0 -1/4 1 19/2

jf 175/4 9/2 9 0 9/4 0

jj cf − -7/2 Ø Ø 9/4 Ø

0 3a 26 0 0 1 -4/5 1/5

9 2a 3/2 0 1 0 3/10 -1/5

8 1a 19/2 1 0 0 -1/10 2/5

jf 89,5 8 9 0 19/10 7/5

jj cf − Ø Ø Ø 19/10 7/5 0≥ 5,1=∀j ? DA ⇒ STOP

0≥ 5,1=∀j ?


Duala admite soluţia optimă finită: 2/3*1 =u , 2/19*

2 =u , 36*3 =u ,

0*5

*4 == uu şi fg [min]5,89[max] == .

3. Degenerare şi ciclare în probleme de programare liniară

Definiţie: X se numeşte SAB degenerată pentru II.2.1 dacă numărul valorilor variabilelor bazice strict pozitive este cel mult (m-1) unde m=rangA.

Soluţiile admisibile de bază degenerate se pot obţine în două moduri:

1) În sistemul de restricţii scris sub forma explicită bBRXBX RB 11 −− =+ ,

bB 1− are cel puţin o componentă egală cu zero şi toate celelalte strict

pozitive ⇒ valorile variabilelor bazice bBX B 1−= , strict pozitive, sunt în număr de cel mult (m-1).

2) Există cazul în care, în spaţiul bunurilor mR , vectorul b nu formează un sistem de vectori liniar independenţi cu orice combinaţie de (m-1) vectori din A. Din punct de vedere geometric, acest lucru înseamnă că b trece printr-un vârf al poliedrului conex al restricţiilor bAX = . Să

presupunem că ( )maaa ...21 este o bază în mR , dar

( )baaa m 121 ... − nu este un sistem de m vectori liniar

independenţi. Vectorul b poate fi scris în mod unic în baza ( )maaa ...21 :

II.3.1 baxaxaxa mmm =⋅++++ −− 0... 112211 .

Din II.3.1 rezultă că SABX are componentele ( )Tmxx 0....0.... 11 − , deci

este SAB degenerată.


Rezolvarea următorului model matematic, în 2R , ne va furniza o interpretare geometrică a conceptului de degenerare:

2,1 ,0

14111463255212

4[max]

21

21

21

21

21

=∀≥

⎪⎪⎩

⎪⎪⎨

⎧

≤+−≤+≥+−≤+−

+=

jx

xxxxxxxx

xxf

j

, cu forma standard

6,1 ,0

14111463255212

4[max]

621

521

421

321

21

=∀≥

⎪⎪⎩

⎪⎪⎨

⎧

=++−=++=−+−=++−

+=

jx

xxxxxxxxxxxxxxf

j

.

Valoarea maximă este atinsă în ⎟⎠⎞

⎜⎝⎛

47,

83B , prin care trec trei drepte

care definesc mulţimea convexă (simplexul) a soluţiilor admisibile. Dacă înlocuim soluţia optimă în forma standard, se obţine un program optim

degenerat: 83*

1 =x , 47*

2 =x , 0*3 =x , 3*

4 =x , 0*5 =x , 0*

6 =x .

Observaţie: Şi prin A trec trei drepte, 1d , 2d şi 01 =x , deci, prin înlocuirea

coordonatelor sale în forma standard, se obţine o SAB degenerată.

Să presupunem că unei probleme de programare liniară degenerată i se caută soluţia optimă aplicând metoda simplex, şi, la o anumită iteraţie,

2x

1x O 3

2

1

-5/2 -1/2

B C

3d

2d

1d

A


raportul minρ nu este unic determinat. Metoda perturbaţiilor (A. Chanes) şi

metoda lexicografică (B.B. Dantzig şi P. Wolfe) sunt două metode ce nu înlătură degenerarea, ci creează posibilitatea continuării algoritmului prin înlăturarea arbitrariului în determinarea vectorului ce va fi eliminat din bază, vector situat pe una din liniile rapoartelor minime de valori egale.

a) Metoda lexicografică

Presupunem că la iteraţia *N∈p , vectorul la , Jl∈ , trebuie să intre

în bază, toate componentele sale sly , Is∈ , sunt strict pozitive şi

rl

r

kl

k

sl

s

ysrk yx

yx

yx

sl

==⎭⎬⎫

⎩⎨⎧

==>0|

minρρ .

Se pune întrebarea: care din cei doi vectori va fi eliminat, ka sau ra ?

T.II.3.1

jc 1c

lc

nc

Bc B BX

1a

… la …

na

ρ

1c 1a 1x ly1

111 / yx … … … …

kc ka kx kly

klk yx / … … … …

rc ra rx rly

rlr yx / … … … …

mc ma mx mly

mlm yx /

jf

jj cf −

Decizia va fi luată după parcurgerea următorilor paşi:

min


Pasul 1 Se împart elementele liniei k, începând cu kx , la eventualul element

pivot kly . Se împart elementele liniei r la eventualul element pivot rly , şi se

aşează sub celelalte rapoarte în ordinea dată de coloanele tabelului simplex:

kl

kn

kl

kl

kl

kl

kl

k

kl

k

kl

k

yy

yy

yy

yy

yy

yx ,....,,,...,,, 121 − ;

rl

rn

rl

rl

rl

rl

rl

r

rl

r

rl

r

yy

yy

yy

yy

yy

yx ,....,,,...,,, 121 − .

Pasul 2 Operaţia 1 Operaţia 2: ⇒+= 1: kk Operaţia 1.

După cel mult n operaţii se poate stabili vectorul care trebuie eliminat. Observaţie: În cazul programării pe calculator, se va elimina din bază vectorul cu cel mai mic indice. În foarte puţine cazuri, această metodă prezintă dezavantajul că, după un anumit număr de iteraţii, poate să se

revină la baza iteraţiei p, *N∈p .

DA Se trece la Operaţia 2.

NU

Se compară rapoartele din a doua coloană:

rl

r

kl

k

yy

yy 11 = ?

STOP. Pivotul iteraţiei va fi numitorul raportului minim. Va fi eliminat

din bază vectorul situat în linia pivotului.


Fie problema:

54321 32423)([min] xxxxxXf ++++=

II.3.2 ⎩⎨⎧

=+++=+++

1532102

5321

4321

xxxxxxxx

.

0≥jx , 5,1=j

După scrierea matricii ⎥⎦

⎤⎢⎣

⎡=

1013201121

A , rangA=2<5, ne este sugerată

soluţia de

54321 aaaaa

start pentru algoritmul simplex-primal, ( )TSABX 1510000= .

Completând primul tabel, se va observa în formula criteriului de eliminare din bază că minimul nu este unic. Într-adevăr, jc 3 2 4 2 3

Bc B BX 1a 2a 3a 4a 5a ρ

2 4a 10 1 2 1 1 0 10/2

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

jf 65 8 13 5 2 3 [ ] fmin

jj cf − 5 11 1 Ø Ø 0≤ ?5,1=∀j NU

Se observă că: ( ) ⇒−==−

>− 22011max cfcf jjcf jj

2a va intra în noua

bază. Dar, 3

152

10= . Aşadar, care vector va fi eliminat?

Pasul 1 20,

21,

21,

22,

21,

210

31,

30,

31,

33,

32,

315

Pasul 2 O1: 315

210

=

O2: 32

21< ⇒ se elimină vectorul 4a .

Pivotul iteraţiei este 2.


jc 3 2 4 2 3

Bc B BX 1a 2a 3a 4a 5a

2 4a 5 1/2 1 1/2 1/2 0

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

jf 10 2 2 -1 -5 2

jj cf −

-1 Ø -5 -7 Ø

Soluţia optimă este degenerată. Variabila bazică 5x are valoarea

zero.

b) Metoda perturbaţiilor

Vom exemplifica această metodă pe modelul precedent. Pasul 1 Fie )1,0(∈ε arbitrar de mic. Se va trece de la II.3.2, la o problemă

perturbată, de forma:

∑=

=n

jjj xcf

1[max]

II.3.3 ∑∑∑===

+=+n

jj

jn

jj

jn

jjj abaxa

111εε

njx j ,1 ,0 =≥

Dacă soluţia admisibilă de bază corespunde bazei formată din primii m vectori, atunci restricţiile din II.3.3 se mai pot scrie:

II.3.4 ( ) )(11

εεε baaxn

mjj

jm

ss

ss =++ ∑∑

+==

,

unde ∑=

+=n

jj

jabb1

)( εε .

⇒=∀≤ 5,1 0 j STOP


În particular, pentru II.3.2 avem scrierea

⎟⎟⎠

⎞⎜⎜⎝

⎛

++++++++

=⎟⎟⎠

⎞⎜⎜⎝

⎛+⎟⎟

⎠

⎞⎜⎜⎝

⎛+⎟⎟

⎠

⎞⎜⎜⎝

⎛+⎟⎟

⎠

⎞⎜⎜⎝

⎛+⎟⎟

⎠

⎞⎜⎜⎝

⎛+⎟⎟

⎠

⎞⎜⎜⎝

⎛= 532

43254321

3215210

10

01

11

32

21

1510

)(εεεεεεεε

εεεεεεb

Pasul 2 Prin modificarea de la pasul 1 s-a obţinut o problemă nedegenerată. Presupunem că la este vectorul ce va face parte din noua bază (se acceptă

ipotezele expuse la metoda lexicografică). Vom aplica acum criteriul de eliminare din bază:

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛++

=∑

+=

>sk

n

mjsk

jss

ys y

yx

sk

1

0|min

εερ .

În particular:

=⎟⎟⎠

⎞⎜⎜⎝

⎛ ++++++++=

33215,

2210min

325324 εεεεεεεερ

⎟⎟⎠

⎞⎜⎜⎝

⎛++++++++=

33325,

2225min

532

432 εεεεεεεε

Pentru ε suficient de mic, 333

25222

553

243

2 εεεεεεεε++++<++++ ⇒

4a va fi eliminat.

Observaţia 1: Metodele au fost date în cazul în care raportul minim este realizat pentru doi indici Is∈ , dar se pot aplica şi în situaţia în care se pot elimina mai mult de doi vectori din bază.

b 1a 2a 3a 4a 5a


Observaţia 2: Se poate trece de la o SAB degenerată la o SAB cu valorile variabilelor bazice strict pozitive (nedegenerată), aşa cum se va vedea şi din exemplul următor:

Se doreşte realizarea unui amestec din trei tipuri de benzină. Acest amestec este de multe ori condiţionat de cantităţile de care dispunem din fiecare produs. Se înţelege că avem analizele de laborator ale tuturor produselor şi cunoaştem caracteristicile chimice ale produselor pe care le amestecăm, de aceea, dacă amestecăm benzina de 92 cu benzina de 88 şi cu nafta o facem pentru a obţine benzină de 92. Cantitatea de benzină de 92 trebuie să reprezinte cel puţin 50% din întregul amestec, iar nafta trebuie să fie cuprinsă între 25% şi 30% din întregul amestec.

Preţurile unitare ale sortimentelor sunt de 30$ barilul de nafta, 40$ barilul de benzină de 88 şi 50$ barilul de benzină de 92. Să determinăm ce cantităţi se amestecă astfel încât valoarea amestecului rezultat să fie maximă.

Notăm cu 1x cantitatea de nafta, cu 2x cantitatea de benzină de 92 şi

cu 3x cantitatea de benzină de 88. Restricţiile privind disponibilul sunt:

0033703

90100

321

321

321

2

1

≤+−≤−−≤++−

≤≤

xxxxxxxxx

xx

.

Forma standard este:

8,1 ,0

0033703

90100

354[max]

8321

7321

6321

52

41

321

=∀≥

⎪⎪⎪

⎩

⎪⎪⎪

⎨

⎧

=++−=+−−=+++−

=+=+

++=

jx

xxxxxxxxxxxx

xxxx

xxxf

j

.


Calculele implicate de aplicarea algoritmului simplex primal sunt prezentate în tabelul următor:

jc 4 5 3 0 0 0 0 0 Bc B BX 1a 2a 3a 4a 5a 6a 7a 8a ρ

0 4a 100 1 0 0 1 0 0 0 0 -

0 5a 90 0 1 0 0 1 0 0 0 90

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

0 7a 0 7 -3 -3 0 0 0 1 0 -

0 8a 0 1 -1 1 0 0 0 0 -1 -

jf 0 0 0 0 0 0 0 0 0

jj cf −

-4 -5 -3 Ø Ø Ø Ø Ø

0 4a 100 1 0 0 1 0 0 0 0 100

0 5a 90 3 0 -1 0 1 -1 0 0 30

5 2a 0 -3 1 1 0 0 1 0 0 -

0 7a 0 -2 0 0 0 0 3 1 0 -

0 8a 0 -2 0 2 0 0 1 0 1 -

jf 0 -15 5 5 0 0 5 0 0

j cf −

-19 Ø 2 Ø Ø 5 Ø Ø

0 4a 70 0 0 1/3 1 -1/3 1/3 0 0 210

4 1a 30 1 0 -1/3 0 1/3 -1/3 0 0 -

5 2a 90 0 1 0 0 1 0 0 0 -

0 7a 60 0 0 -2/3 0 2/3 7/3 1 0 -

0 8a 60 0 0 4/3 0 2/3 1/3 0 1 45

jf 570 40 50 -4/3 0 19/3 -4/3 0 0

jj cf −

Ø Ø -13/3 Ø 19/3 -4/3 Ø Ø

0 4a 55 0 0 0 1 -1/2 1/4 0 -1/4 220

4 1a 45 1 0 0 0 1/2 -1/4 0 1/4 -


5 2a 90 0 1 0 0 1 0 0 0 -

0 7a 90 0 0 0 0 1 5/2 1 1/2 36

3 3a 45 0 0 1 0 1/2 1/4 0 3/4 180

jf 765 4 5 3 0 17/2 -1/4 0 13/4

jj cf −

Ø Ø Ø Ø 17/2 -1/4 Ø 13/4

jc

4 5 3 0 0 0 0 0 Bc B BX 1a 2a 3a 4a 5a 6a 7a 8a

0 4a 46 0 0 0 1 -3/5 0 -1/10 -3/10

4 1a 54 1 0 0 0 3/5 0 1/10 3/10

5 2a 90 0 1 0 0 1 0 0 0

0 6a 36 0 0 0 0 2/5 1 2/5 1/5

3 3a 36 0 0 1 0 2/5 0 -1/10 7/10

jf 774 4 5 3 0 43/5 0 1/10 33/10

jj cf −

Ø Ø Ø Ø 43/5 Ø 1/10 33/10

După câteva iteraţii, obţinem soluţia care recomandă amestecarea a

541 =x barili nafta, 902 =x barili de benzină de 92 şi 363 =x barili de

benzină de 88. Astfel, se vor obţine 180 de barili cu valoarea totală de 10774 ⋅ dolari. Preţul unui baril de amestec va fi de 42$. Benzina nafta va

reprezenta %3010018054

=⋅ din amestec, benzina auto de 92 va reprezenta

50% din amestec, iar benzina auto de 88 reprezintă 30% din amestec. Se observă astfel că, deşi la iteraţia 2 soluţia admisibilă de bază este

degenerată, la următoarea iteraţie soluţia admisibilă devine nedegenerată.

c) Ciclare Dacă valoarea funcţiei scop nu se modifică pe parcursul câtorva

iteraţii succesive, este posibil să apară fenomenul de ciclare, adică să se revină la una dintre soluţiile admisibile de bază prin care s-a trecut deja.


Degenerarea este o condiţie necesară, dar nu şi suficientă, de ciclare. Deşi foarte multe procese economice sunt modelate prin programe liniare cu soluţii admisibile de bază degenerate, la nici una până acum nu a apărut fenomenul de ciclare. E. Beale [] a găsit şi a publicat un astfel de model.

6,1 , 0

1

032112

21

09841

62120

43[min]

63

76542

76541

7654

=≥

⎪⎪

⎩

⎪⎪

⎨

⎧

=+

=+−−+

=+−−+

+−+−=

jx

xx

xxxxx

xxxxx

xxxxf

j

.

Prezentăm în continuare rezultatele – sub formă de tabel – a şapte iteraţii. Se va observa că primul tabel coincide cu ultimul.

jc 0 0 0 -3/4 20 -1/2 6 Bc B BX 1a 2a 3a 4a 5a 6a 7a ρ

0 1a 0 1 0 0 1/4 -8 -1 9 0

0 2a 0 0 1 0 1/2 -12 -1/2 3 0

0 3a 1 0 0 1 0 0 1 0 -

jf 0 0 0 0 0 0 0 0

jj cf − Ø Ø Ø 3/4 -20 1/2 -6


jc 0 0 0 -3/4 20 -1/2 6

Bc B BX 1a 2a 3a 4a 5a 6a 7a ρ

-3/4 4a 0 4 0 0 1 -32 -4 36 -

0 2a 0 -2 1 0 0 4 3/2 -15 0

0 3a 1 0 0 1 0 0 1 0 -

jf 0 -3 0 0 -3/4 24 3 -27

jj cf −

-3 Ø Ø Ø 4 7/2 -33

jc 0 0 0 -3/4 20 -1/2 6


-3/4 4a 0 -12 8 0 1 0 8 -84 0

20 5a 0 -1/2 1/4 0 0 1 3/8 -15/4 0

0 3a 1 0 0 1 0 0 1 0 1

jf 0 -1 -1 0 -3/4 20 3/2 -12

jj cf −

-1 -1 Ø Ø Ø 2 -18

jc 0 0 0 -3/4 20 -1/2 6


-1/2 6a 0 -3/2 1 0 1/8 0 1 -21/2 -

20 5a 0 1/16 -1/8 0 -3/64 1 0 3/16 0

0 3a 1 3/2 -1 1 -1/8 0 0 21/2 2/21

jf 0 2 -3 0 -1 20 -1/2 9

jj cf − 2 -3 Ø -1/4 Ø Ø 3


jc 0 0 0 -3/4 20 -1/2 6


-1/2 6a 0 2 -6 0 -5/2 56 1 0 0

6 7a 0 1/3 -2/3 0 -1/4 16/3 0 1 0

0 3a 1 -2 6 1 5/2 -56 0 0 -

jf 0 1 -1 0 -1/4 4 -1/2 6

jj cf − 1 -1 Ø 1/2 -16 Ø Ø

jc 0 0 0 -3/4 20 -1/2 6


0 1a 0 1 -3 0 -5/4 28 1/2 0 -

6 7a 0 0 1/3 0 1/6 -4 -1/6 1 0

0 3a 1 0 0 1 0 0 1 0 1

jf 0 0 2 0 1 -24 -1 6

jj cf − Ø 2 Ø 7/4 -44 -1/2 Ø

jc 0 0 0 -3/4 20 -1/2 6


0 1a 0 1 0 0 1/4 -8 -1 9 4

0 2a 0 0 1 0 1/2 -12 -1/2 3 0

0 3a 1 0 0 1 0 0 1 0 -

jf 0 0 0 0 0 0 0 0

jj cf − Ø Ø Ø 3/4 -20 1/2 -6

În tabelele precedente, deşi criteriul de intrare în bază ne-a dat posibilitatea de a alege între două variabile, am ales întotdeauna prima variabilă din partea de sus a tabelelor. Dacă însă vom alege la un moment dat alte variabile care ies din bază decât cele alese anterior putem ajunge la


soluţia optimă, evitând în acest fel ciclarea, aşa cum se vede din următoarele două iteraţii:

jc 0 0 0 -3/4 20 -1/2 6


0 1a 0 1 -1/2 0 0 -2 -3/4 15/2 -

-3/4 4a 0 0 2 0 1 -24 -1 6 -

0 3a 1 0 0 1 0 0 1 0 1

jf 0 0 -3/2 0 -3/4 18 3/4 -9/2

jj cf −

Ø -3/2 Ø Ø -2 5/4 -21/2

jc 0 0 0 -3/4 20 -1/2 6 Bc B BX 1a 2a 3a 4a 5a 6a 7a

0 1a 3/4 1 -1/2 3/4 0 -2 0 15/2

-3/4 4a 1 0 2 1 1 -24 0 6

-1/2 6a 1 0 0 1 0 0 1 0

jf -5/4 0 -3/2 -5/4 -3/4 18 -1/2 -9/2

jj cf −

Ø -3/2 -5/4 Ø -2 Ø -21/2

Astfel, soluţia optimă este dată de ( )TX 0101004/3= ,

valoarea minimă a funcţiei obiectiv fiind ( ) 4/5−=Xf .

Deşi în problemele practice nu s-a observat fenomenul de ciclare, teoretic există posibilitatea de a apărea şi, ca urmare, este bine să cunoaştem o cale de a-l evita.

4. Algoritmul simplex revizuit

Acest algoritm este o formă “revizuită” a algoritmului simplex primal, care se recomandă a fi folosită atunci când rezolvarea modelului matematic se face cu ajutorul calculatorului. Ideea de bază este de a reţine datele iniţiale, apoi, folosind matricea sistemului de restricţii se va construi


o matrice inversă, se vor calcula 1−Bc B , bBX B 1−= şi jj cf − , în funcţie

de care se ia decizia de a opri algoritmul sau de a-l continua trecând la o soluţie admisibilă de bază mai bună.

Considerăm problema de programare liniară la forma standard

II.4.1 {0

)(min

≥=

=

XbAX

cXxf,

unde )(, RnmMA∈ , nmrangA ≤= mb R∈ , nXc R∈, .

Pentru aplicarea algoritmului simplex revizuit, se construieşte

“completata” problemei II.4.1:

II.4.2

R∈≥⎩⎨⎧

==−

=

0

0

01

,0

0)(min

xXbAX

cXxxxf

.

Aici, matricea sistemului de restricţii va fi: ⎟⎟⎠

⎞⎜⎜⎝

⎛ −−=

RBcc

A RB

01

1 ,

unde ( )RBA = . Se observă că 11 += mrangA . Vectorul termenilor liberi

pentru problema completată este ⎟⎟⎠

⎞⎜⎜⎝

⎛=

bb

01 . Notăm ⎟⎟

⎠

⎞⎜⎜⎝

⎛−=

k

kk a

ca1 , unde ka

este coloana k din matricea A.


Dacă B este bază primal admisibilă pentru II.4.1, atunci

⎟⎟⎠

⎞⎜⎜⎝

⎛ −=

Bc

BB

01

1 este bază primal admisibilă pentru II.4.2. Este uşor de

verificat că ⎟⎟⎠

⎞⎜⎜⎝

⎛=

−−

11

1 01

Bu

BB

, unde 1−= Bcu BB .

Tabelul simplex revizuit va avea următoarea formă:

Variabilele de bază 11−B 1

11 bB − 11

1 kaB − * 0x 1 1−= Bcu BB Bf k

Bk cf −

BX 0 1−B BX kBk aBy 1−=

* Ultima coloană va apărea în momentul când se trece la îmbunătăţirea soluţiei curente.

Etapele algoritmului simplex revizuit sunt prezentate în schema logică S.II.4.1:

Schema logică S.II.4.1

Datele iniţiale: bAX = , 0≥X , ( ) cXxf =[max]

nmrangA nm ≤=× , mb R∈ , nc R∈

Se determină o bază primal admisibilă pentru problema II.4.1 şi se calculează apoi 1B , 1

11 bB − , Bu , 11

1 jaB −

nj

cf jBj

,1

0

=∀

≤−

STOP. Problema admite soluţie optimă finită

ff [min]0 = ; ⎟⎟⎠

⎞⎜⎜⎝

⎛=

−

0

1bBX B .

DA

NU

Alegem k astfel încât 0)(max0

>−=−>−

kB

kjBj

cfcfcf

jBj

.

Se completează ultima coloană din tabel cu vectorul ⎟⎟⎠

⎞⎜⎜⎝

⎛

=−

=−

−

kBk

kB

kk aBy

cfaB 1

111 .

?0≤Bky DA STOP

Problema are optim ( ∞− ).

NU

Se alege r după regula: Brk

Br

Bik

Bi

yi yx

yx

Bik

=|

min .

Se înlocuieşte coloana ra cu coloana ka , şi se formează noua bază primal admisibilă, 1

~B . Se calculează 11

1~ bB − , Bu

~, 11

1~

jaB − .

1


Pas 0 Se determină B bază primal admisibilă şi se calculează: 1−B , BX , Bf , 1−= Bcu BB .

Pas 1 Se calculează jjB

jBj caucf −=− , Rj∈∀ .

Dacă 0≤− jBj cf , { } RBnj =−∈∀ ,..,1 ⇒ soluţie optimă.

Dacă nu, se trece la Pasul 2.

Pas 2 Alegem k astfel încât 0)(max0

>−=−>−

kB

kjBj

cfcfcf

jBj

.

Se calculează kBk aBy 1−= . Dacă 0≤B

ky , problema are optim

nemărginit ( ∞− ). Dacă nu, se trece la Pasul 3.

Pas 3 Alegem r după regula: Brk

Br

Bik

Bi

yi yx

yx

Bik

=|

min . Se înlocuieşte coloana ra cu

coloana ka , şi se formează noua bază primal admisibilă, 1~B . Se revine la

Pasul 1. Să rezolvăm cu algoritmul simplex revizuit următoarea problemă de

programare liniară:

2,1 , 0

62183

42[min]

21

21

21

21

=∀≥

⎪⎩

⎪⎨

⎧

≤+−≤−≤−

−−=

ix

xxxx

xxxxf

i

.


În primul rând, aducem, problema la forma standard:

5,1 , 0

62183

42[min]

521

421

321

21

=∀≥

⎪⎩

⎪⎨

⎧

=++−=+−=+−

−−=

ix

xxxxxx

xxxxxf

i

. Matricea restricţiilor este ⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛

−−−

=100210101300111

A ,

( )5433 aaaIB == . Scriem “completata” problemei de mai sus:

5,1 , 0

62183

40)2(

[min]

521

421

321

210

0

=∀≥

⎪⎪⎩

⎪⎪⎨

⎧

=++−=+−=+−

=−−−

=

ix

xxxxxx

xxxxxx

xg

i

.

Aşadar, ⎟⎟⎠

⎞⎜⎜⎝

⎛ −−=

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

−−−

=BRcc

ABR

01

100210010130001110000121

1 , ⎟⎟⎠

⎞⎜⎜⎝

⎛=

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

=b

b0

16840

1 .

Observaţie: După reordonare putem obţine chiar ⎟⎟⎠

⎞⎜⎜⎝

⎛ −−=

RBcc

ARB

01

1 .

Completăm tabelul simplex revizuit, evident fără ultima coloană:

( ) ( )000000 31 =⋅== − IBcu BB .

Variabilele de bază 11−B 1

11 bB −

0x 1 0 0 0 0

3x 0 1 0 0 4

4x 0 0 1 0 18

5x 0 0 0 1 6


Pentru Rj∈∀ , calculăm ( ) ⎟⎟⎠

⎞⎜⎜⎝

⎛−=−

j

jBj

Bj a

cucf 1 . În cazul nostru,

}2,1{=R . Aşadar, pentru 1=j avem:

( ) ( ) 02

1312

000111

111 >=

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

−

=⎟⎟⎠

⎞⎜⎜⎝

⎛−=−

ac

ucf BB , ⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛

−=−

131

11aB ,

iar pentru 2=j ,

( ) ( ) 01

211

1

000112

222 >=

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

−−

=⎟⎟⎠

⎞⎜⎜⎝

⎛−=−

ac

ucf BB , ⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛−−

=−

211

21aB .

Soluţia curentă nu este optimă şi nici cazul optim nemărginit nu este

îndeplinit. Trecem la schimbarea bazei. Deoarece, 2211 12 cfcf BB −=>=− ,

variabila 1x va intra în noua bază.

Completăm tabelul de mai sus cu ultima coloană:

Variabilele de bază 1

1−B 1

11 bB − 11

11 aB −

0x 1 0 0 0 0 2

3x 0 1 0 0 4 1

4x 0 0 1 0 18 3

5x 0 0 0 1 6 -1

Deoarece 14

318,

14min =

⎭⎬⎫

⎩⎨⎧ , variabila 3x va ieşi din bază. Pivotul

este, desigur, valoarea aflată în căsuţa colorată, adică 1. Tabelul simplex revizuit următor se obţine din cel precedent, după aceleaşi reguli care se aplică tabelului simplex obişnuit.


Astfel, cu noua bază avem:


~ −B 11

1~ bB − 12

11

~ aB − *

0x 1 -2 0 0 -8 3

1x 0 1 0 0 4 -1

4x 0 -3 1 0 6 2

5x 0 1 0 1 10 1

* Ultima coloană se va completa ulterior.

( ) ( ) 03

211

1

002112

2~

2

~

2 >=

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

−−

−=⎟⎟⎠

⎞⎜⎜⎝

⎛−=−

ac

ucf BB (soluţia curentă

nu este optimă).

⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛−=

⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛−−

⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛−=−

121

211

101013001

~2

1aB (rezultă de aici că nu avem optim

infinit),

( ) ( ) 02

0010

002113

3~

3

~

3 <−=

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

−=⎟⎟⎠

⎞⎜⎜⎝

⎛−=−

ac

ucf BB .

Singura variabilă care poate intra în bază este 2x . Completăm ultima

coloană. Cum 26

110,

26min =

⎭⎬⎫

⎩⎨⎧ , rezultă că variabila 4x iese din bază.

Pivotul este 2.


Următorul tabel simplex revizuit, unde baza este acum notată 1

~~B :


1

~~ −B 11

1

~~ bB − 131

1

~~ aB − ** 0x 1 5/2 -3/2 0 -17 5/2

1x 0 -1/2 1/2 0 7 -1/2

2x 0 -3/2 1/2 0 3 -3/2

5x 0 5/2 -1/2 1 7 5/2

** Ultima coloană se va completa ulterior.

( ) 02/5

0010

02/32/513

~~

3 >=

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

−=− cf B (soluţia curentă nu este

optimă).

⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛−−

=⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛

⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛

−−−

=−

2/52/32/1

001

12/12/502/12/302/12/1~~

31aB (rezultă de aici că nu avem

optim infinit),

( ) 02/3

0100

02/32/514

~~

4 <−=

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

−=− cf B .

Variabilă care intră în bază este 3x . Completăm ultima coloană.

Se observă imediat că singura variabilă care poate ieşi din bază este

5x . Pivotul este 5/2. La această iteraţie baza curentă este notată prin 1B̂ .



ˆ −B 11

1ˆ bB −

0x 1 0 -1 -1 -24

1x 0 0 2/5 1/5 42/5

2x 0 0 1/5 3/5 36/5

3x 0 1 -1/5 2/5 14/5

Cum ( ) 01

0100

11014ˆ

4 <−=

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

−−=− cf B şi

( ) 01

1000

11015ˆ

5 <−=

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

−−=− cf B , rezultă că soluţia curentă,

( )Tx 005/145/365/42= este optimă, unică şi nedegenerată.

Din exemplificarea aplicării algoritmului simplex revizuit, rezultă

următoarele: • Memoria calculatorului este eficient folosită, prin reducerea volumului de infomaţii stocate. • Datele reţinute la o iteraţie sunt suficiente pentru a obţine toate informaţiile dorite, relativ la problema primală şi la duala sa.

5. Algoritmul simplex dual Când s-a aplicat algoritmul simplex primal s-a apelat – pe tot

parcursul algoritmului – la soluţii admisibile de bază (SAB) şi regulile sale au fost stabilite impunându-se condiţia de nenegativitate a variabilelor din model.


Cu ajutorul teoriei dualităţii se poate formula un nou algoritm de rezolvare a problemelor de programare liniară, pornind de la o soluţie de bază care nu respectă - total sau parţial - condiţia de nenegativitate, şi anume, algoritmul simplex dual. Conceptul de bază cu care se operează este cel de soluţie dual realizabilă (SDR). Definiţie: Se numeşte soluţie dual realizabilă a unei probleme de programare liniară o soluţie de bază care are cel puţin o componentă strict negativă şi care verifică criteriul de optimalitate al modelului liniar.

Algoritmul simplex-dual este o procedură de explorare orientată a soluţiilor dual-admisibile până la obţinerea soluţiei optime sau până la evidenţierea faptului că problema nu admite soluţii. Aplicarea sa presupune cunoaşterea unei soluţii dual-realizabile (sau dual-admisibile) dar nu şi admisibile, deoarece, dacă toate variabilele ar avea valori pozitive, cum este verificat criteriul de optimalitate, ar rezulta că soluţia este optimă. În general, stabilirea unei soluţii dual-admisibile este greu de realizat, motiv pentru care acest algoritm se aplică atunci când o soluţie dual realizabilă se poate stabili cu un volum mic de calcule, când restricţiile sunt cu precădere de forma “≥ ”, sau când aceasta se obţine prin modificarea unor caracteristici numerice din model. Acest algoritm poate fi privit ca dualul algoritmului simplex-primal, deoarece reflectă aplicarea acestuia la problema duală.

Pentru algoritmul simplex dual, valorile funcţiei scop descresc când aceasta se cere maximizată şi cresc când se cere minimizată, până când este atinsă valoarea optimă, dacă programul liniar admite soluţie optimă finită.


Schema de desfăşurare a algoritmului simplex-dual, când se cere [ ] fmax este următoarea:

NU

DA

● Modelul matematic se aduce la forma standard ● Se stabileşte o SDR:

( )RnMB∈∃ a.î. ( )TmB xxbBX ....1

1 == − 0≥

01 ≥−=− −jj

Bjj caBccf , nj ,1=∀

0<∃ kx a.î

0≥kjy , nj ,1=∀ STOP

Problema este fără soluţii.

● Alege { }sxsl xxs 0|

min<

= (C.E.B);

● Elimină din bază vectorul la ;

● Alege ⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧ −

=−

< min

0|lj

jj

yjlk

kk

ycf

ycf

lj

(C.I.B);

● Înlocuieşte vectorul la cu ka ;

● Se formează 1B

Se calculează elementele noului tabel; după regulile aplicate în cazul algoritmului simplex primal, având ca pivot elementul 0<lky . Dacă nu apare fenomenul de ciclare, după efectuarea calculelor se ajunge la una din situaţiile: 1. 01 ≥BX şi 0≥− jj cf , nj ,1=∀ ⇒ STOP. Problema admite soluţie optimă finită. 2. 01 ≥BX şi 0<−∃ kk cf , { }nk ,..,1∈ ⇒ s-a generat o SAB, se va continua cu algoritmul simplex-primal. 3. Există cel puţin o variabilă bazică cu valoare strict negativă şi 0≥− jj cf ,

nj ,1=∀ ⇒


Observaţie: Cele două criterii de eliminare şi respectiv de intrare în bază, sub această formă, sunt invariante la tipul de optim.

Pentru o mai bună înţelegere a modalităţilor de operare a celor doi algoritmi duali, se vor sumariza principalele lor elemente după cum urmează: Algoritmul simplex primal Algoritmul simplex dual

Soluţie de start,

B bază curentă

SABX : 01 ≥⋅= − bBX B ;

0=RX ;

Obs: 0=− ss cf , sx∀ variabilă bazică

SDRX : bBX B ⋅= −1 ; 0=RX a.î.

0<∃ sx , BJs∈ şi

0≥− jj cf j∀ (pt. [max]) sau

0≤− jj cf j∀ (pt. [min])

STOP

a) Dacă 0≥− jj cf j∀ (pt. [max]),

respectiv 0≤− jj cf j∀ (pt.

[min]) ⇒ programul are soluţieoptimă finită.

b) Dacă ka∃ nebazic pentru care

0<− kk cf şi 0≤sky , s∀ (pt.

[max]), respectiv 0>− kk cf şi

0≤sky , s∀ (pt. [min]) ⇒program cu funcţia obiectivnemărginită.

a) Dacă 0≥− jj cf j∀ (pt. [max]),

respectiv 0≤− jj cf j∀ (pt.

[min]) şi 0≥BX ⇒ programul liniar are soluţie optimă finită.

b) Dacă 0<∃ sx , BJs∈ şi 0≥sjy ,

j∀ ⇒ programul liniar nu are soluţie.

Algoritmul se continuă

dacă

Pt. [max]: 0<−∃ kk cf şi 0>skypentru cel puţin o valoare BJs∈ . Se continuă cu simplex primal. Pt. [min]: 0>−∃ kk cf şi 0>skypentru cel puţin o valoare BJs∈ . Se continuă cu simplex primal.

Dacă pt. [max] 0≥− jj cf , respectiv

pt. [min] 0≤− jj cf , j∀ , şi

0<∃ sx , BJs∈ , atunci se continuă cu simplex dual, deoarece s-a generat o SDR. Dacă pt. [max] 0<− kk cf , respectiv

pt. [min] 0>− kk cf , cu ka nebazic,

şi 0≥∃ sx , BJs∈∀ , atunci se continuă cu simplex primal, deoarece s-a generat o SAB.

Pivot 0>lky 0<lky

Criterii pentru

schimbarea bazei

a) C.I.B. b) C.E.B.

a) C.E.B b) C.I.B.


Pentru a înţelege mai bine modul de aplicare a algoritmului simplex-dual, precum şi diferenţele faţă de aplicarea algoritmului simplex-primal, vom da câteva exemple numerice. Exemplul 1 Să se găsească soluţia optimă a modelului liniar:

3,1 ,0

326224

656[min]

321

321

321

321

=≥

⎪⎩

⎪⎨

⎧

≤−+−≥+−≥++−

++=

jx

xxxxxxxxx

xxxf

j

.

Soluţie: ● Se schimbă sensul primelor două restricţii:

3,1 ,0

3262

24656[min]

321

321

321

321

=≥

⎪⎩

⎪⎨

⎧

≤−+−−≤−+−−≤−−

++=

jx

xxxxxx

xxxxxxf

j

● Se aduce problema la forma standard

6,1 ,0

3262

24656[min]

6321

5321

4321

321

∈∀≥

⎪⎩

⎪⎨

⎧

=+−+−−=+−+−−=+−−

++=

ix

xxxxxxxx

xxxxxxxf

i

.

După scrierea matricii ⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛

−−−−−−

=100211010112001114

A , rangA=3<6,

se constată că bazei ( )654 aaa îi corespunde o soluţie bazică

( )TX 362000 −−= , care nu respectă condiţia de nenegativitate.


Pentru a stabili dacă satisface criteriul de optimalitate, trebuie construit primul tabel de tip simplex:

→jc

6 5 6 0 0 0

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

0 4a -2 4 -1 -1 1 0 0

0 5a -6 -2 1 -1 0 1 0

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

jf 0 0 0 0 0 0 0

jj cf −

-6 5 -6 Ø Ø Ø

Soluţia bazică construită este dual realizabilă, deoarece verifică

criteriul de optimalitate. Conform schemei de rezolvare vor fi efectuate următoarele operaţii:

● Se verifică dacă în liniile valorilor strict negative ale variabilelor bazice există şi componente strict negative. Răspunsul fiind afirmativ, se vor aplica cele două criterii: - Criteriul de eliminare din bază (C.E.B): { } 66,2min −=−− ⇒ 5a părăseşte

baza. - Criteriul de intrare în bază (C.I.B):

26

16 ,

26min ,min

23

33

21

11

−−

=⎭⎬⎫

⎩⎨⎧

−−

−−

=⎭⎬⎫

⎩⎨⎧ −−

ycf

ycf

⇒ 1a va fi al doilea

vector al noii baze şi (-2) pivotul. ● Se efectuează calculele implicate de scrierea vectorilor b şi ja ,

6,1=j în noua

bază ( )614 aaa şi a diferenţelor jj cf − , 6,1=j .

0≤ 6,1=∀j ? DA


Calculele sunt prezentate în tabelul de mai jos: →jc 6 5 6 0 0 0

Bc

B BX 1a 2a 3a 4a 5a 6a

0 4a -14 0 1 -3 1 2 0

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

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

jf 18 6 -3 3 0 -3 0

jj cf −

Ø -8 -3 Ø -3 Ø

Noua soluţie de bază se menţine dual realizabilă, ca urmare se vor aplica criteriile algoritmului simplex-dual:

C.E.B: -14 unică ⇒ 4a eliminat;

C.I.B: 3a va înlocui vectorul 4a , -3 fiind singura componentă strict

negativă din linia vectorului eliminat.

Se va efectua o nouă pivotare.

→jc

6 5 6 0 0 0

Bc B BX 1a 2a 3a 4a 5a

6a

6 3a 14/3 0 -1/3 1 -1/3 -2/3 0

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

0 6a 13 0 0 0 -1/2 -3/2 1

jf 32 6 -4 6 -1 -5 0

jj cf −

Ø -9 Ø -1 -5 Ø

0≤ 6,1=∀j ? DA

0≤ 6,1=∀j ? DA


Din acest ultim tabel rezultă: 0≥BX ; 0≤− jj cf , 6,1=j , deci

algoritmul se opreşte. Problema admite soluţia optimă finită T

X ⎟⎠⎞

⎜⎝⎛= 1300

3140

32* cu 32[min] =f .

Observaţie: Spre deosebire de algoritmul simplex primal, unde valoarea funcţiei obiectiv scade – în cazul problemelor de minim – de la o iteraţie la alta, până la valoarea minimă, în algoritmul simplex dual valoarea funcţiei obiectiv creşte până la valoarea minimă admisibilă (în cazul studiat, de la 0 la 18, şi apoi la 32).

Exemplul 2 Se consideră programul liniar:

3,1 ,0

175247052

10543623[max]

321

321

321

321

∈∀≥

⎪⎩

⎪⎨

⎧

≤++≤++≤++

++=

jx

xxxxxxxxx

xxxf

j

.

Aflati soluţia optimă. Să se scrie duala programului liniar dat. Să se afle soluţia sa optimă X aplicând algoritmul simplex dual. Soluţie: ● Mai întâi aducem problema la forma standard:

6,1 ,0

175247052

10543623[max]

6321

5321

4321

321

∈∀≥

⎪⎩

⎪⎨

⎧

=+++=+++=+++

++=

jx

xxxxxxxxxxxx

xxxf

j

.


Rezolvarea acestei probleme este complet prezentată prin cele 3 tabele simplex de mai jos, corespunzătoare iteraţiilor parcurse până la aflarea soluţiei optime:

→jc 3 2 6 0 0 0 Bc B BX 1x 2x 3x 4x 5x 6x

0 4x 105 1 3 4 1 0 0

0 5x 70 2 5 1 0 1 0

0 6x 175 4 1 2 0 0 1

jf 0 0 0 0 0 0 0

jj cf − -3 -2 -6 Ø Ø Ø

6 3x 105/4 1/4 3/4 1 1/4 0 0

0 5x 175/4 7/4 17/4 0 -1/4 1 0

0 6x 490/4 7/2 -1/2 0 -1/2 0 1

jf 315/2 3/2 9/2 6 3/2 0 0

jj cf − -3/2 5/2 Ø 3/2 Ø Ø

Se observă că 0≥− jj cf , 6,1=∀j , deci programul liniar admite

soluţia optimă finită ( )TX 350020025* = . Baza optimă este dată

de ( )613 aaaB = , a cărei inversă

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡

−−

−=−

12007/47/107/17/2

1B

6 3x 20 0 1/7 1 2/7 -1/7 0

3 1x 25 1 17/7 0 -1/7 4/7 0

0 6x 35 0 -9 0 0 -2 1

jf 195 3 58/7 6 9/7 6/7 0

jj cf − Ø 43/7 Ø 9/7 6/7 Ø

0≥ 6,1=∀j ? NU

0≥ 6,1=∀j ? NU

0≥ 6,1=∀j ? DA


poate fi citită în dreptul vectorilor care au format baza iniţială.

● Se construieşte duala:

6,1 ,0

17524705210543

623[max]

3321

2321

1321

321

∈∀≥

⎪⎩

⎪⎨

⎧

→≤++→≤++→≤++

++=

jx

uxxxuxxxuxxx

xxxf

j

⇔

3,1 ,0

624253342

17570105[min]

321

321

321

321

∈∀≥

⎪⎩

⎪⎨

⎧

≥++≥++≥++

++=

iu

uuuuuuuuu

uuug

i

Din forma standard:

6,1 ,0

624253342

17570105[min]

6321

5321

4321

321

∈∀≥

⎪⎩

⎪⎨

⎧

=−++=−++=−++

++=

iu

uuuuuuuuuuuu

uuug

i

rezultă că matricea A conţine matricea unitate, din 3R , cu semn schimbat, ca urmare toate restrictiile dualei vor fi înmulţite cu ( )1− :

6,1 ,0

624253342

17570105[min]

6321

5321

4321

321

∈∀≥

⎪⎩

⎪⎨

⎧

−=+−−−−=+−−−−=+−−−

++=

iu

uuuuuuuuuuuu

uuug

i

.


Rezolvarea problemei, prin algoritmul simplex dual, este prezentată mai jos:

→jc 105 70 175 0 0 0 Bc B BX 1u 2u 3u 4u 5u 6u

0 4u -3 -1 -2 -4 1 0 0

0 5u -2 -3 -5 -1 0 1 0

0 6u -6 -4 -1 -2 0 0 1

jf 0 0 0 0 0 0 0

jj cf − -105 -70 -175 Ø Ø Ø

0 4u -3/2 0 -7/4 -7/2 1 0 -1/4

0 5u 5/2 0 -17/4 -1/2 0 1 -3/4

105 1u 3/2 1 1/4 1/2 0 0 -1/4

jf 315/2 105 105/4 105/2 0 0 -105/4

jj cf − Ø -175/4 -243/4 Ø Ø -105/4

70 2u 6/7 0 1 2 -4/7 0 1/7

0 5u 43/7 0 0 -8 -17/7 1 -1/7

105 1u 9/7 1 0 0 1/7 0 -2/7

jf 195 105 70 140 -25 0 -20

jj cf − Ø Ø -210 -25 Ø -20

Se observă imediat că 195[min][max] == gf . Soluţia optimă a

dualei este

⎟⎠⎞

⎜⎝⎛= 0

7430

76

79*U .

Se verifică uşor că

( )⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛

−=⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛

−

−=

⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛

−−−

−

*3

*2

*1

20025

7/207/17/117/17

7/107/415070

xxx

.

0≤ 6,1=∀j

0≤ 6,1=∀j

0≤ 6,1=∀j


6. Probleme pentru fixarea cunoştinţelor

Problema 1 Se consideră modelul liniar:

3,1,0

202122

453[min]

321

21

321

=∀≥⎩⎨⎧

≥++≥+

++=

jx

xxxxx

xxxf

j

.

a) Să se genereze, dacă este posibil, SAB sau/şi SDR prin explicitarea sistemului de restricţii în raport cu bazele ),( 21 aa şi ),( 32 aa .

b) Să se scrie duala sa. Admite soluţie optimă finită? Justificaţi răspunsul. c) Ce legătură există între SAB generată la punctul a) şi problema duală? d) Să se rezolve problema dată cu ajutorul algoritmului simplex-dual. Soluţie:

a) • Forma standard:

5,1,0

202122

453[min]

5321

421

321

=∀≥⎩⎨⎧

=−++=−+

++=

jx

xxxxxxx

xxxf

j

.

• Matricea sistemului de restricţii: ⎟⎟⎠

⎞⎜⎜⎝

⎛−

−=

1012101012

A .

• Vectorul termenilor liberi: ⎟⎟⎠

⎞⎜⎜⎝

⎛=

2012

b .


Pentru baza determinată de coloanele 1 şi 2 din matricea A ,

)( 21 aaB = , rezultă )( 543 aaaR = , ⎟⎟⎠

⎞⎜⎜⎝

⎛=

2

1

xx

X B , ⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛=

5

4

3

xxx

X R . Sistemul de

restricţii scris sub forma canonică relativ la B este

II.6.1 ⎟⎟⎠

⎞⎜⎜⎝

⎛=

⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛⋅⎟⎟⎠

⎞⎜⎜⎝

⎛−

−+⎟⎟

⎠

⎞⎜⎜⎝

⎛⋅⎟⎟⎠

⎞⎜⎜⎝

⎛2012

101010

2112

5

4

3

2

1

xxx

xx

.

Prin înmulţirea relaţiei II.6.1 cu ⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜

⎝

⎛

−

−=−

32

31

31

32

1B , obţinem:

⎟⎟⎠

⎞⎜⎜⎝

⎛⋅⎟⎟⎠

⎞⎜⎜⎝

⎛−

−=

⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛⋅⎟⎟⎠

⎞⎜⎜⎝

⎛−

−⋅⎟⎟⎠

⎞⎜⎜⎝

⎛−

−+⎟⎟

⎠

⎞⎜⎜⎝

⎛⋅⎟⎟⎠

⎞⎜⎜⎝

⎛2012

3/23/13/13/2

101010

3/23/13/13/2

1001

5

4

3

2

1

xxx

xx

, sau

⎟⎟⎠

⎞⎜⎜⎝

⎛=

⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛⋅⎟⎟⎠

⎞⎜⎜⎝

⎛−

−+⎟⎟

⎠

⎞⎜⎜⎝

⎛3/283/4

3/23/13/23/13/23/1

5

4

3

2

1

xxx

xx

.

Deoarece 03/283/41 >⎟⎟⎠

⎞⎜⎜⎝

⎛=− bB se poate construi o soluţie admisibilă

de bază, şi anume 34

1 =x , 328

2 =x , 0543 === xxx , pentru care valoarea

funcţiei obiectiv va fi 3

152 .


Baza generată de coloanele 2 şi 3 din matricea sistemului de

restricţii, ⎟⎟⎠

⎞⎜⎜⎝

⎛=

1201

B , cu inversa ⎟⎟⎠

⎞⎜⎜⎝

⎛−

=−

12011B , conduce la următoarea

explicitare a sistemului de restricţii ale problemei:

⎟⎟⎠

⎞⎜⎜⎝

⎛=

⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛⋅⎟⎟⎠

⎞⎜⎜⎝

⎛−

−+⎟⎟

⎠

⎞⎜⎜⎝

⎛⋅⎟⎟⎠

⎞⎜⎜⎝

⎛2012

101012

1201

5

4

1

3

2

xxx

xx

,

de unde rezultă, prin înmulţirea cu 1−B :

⎟⎟⎠

⎞⎜⎜⎝

⎛⋅⎟⎟⎠

⎞⎜⎜⎝

⎛−

=⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛⋅⎟⎟⎠

⎞⎜⎜⎝

⎛−

−⋅⎟⎟⎠

⎞⎜⎜⎝

⎛−

+⎟⎟⎠

⎞⎜⎜⎝

⎛2012

1201

101012

1201

5

4

1

3

2

xxx

xx

.

După efectuarea calculelor apare scrierea explicită a sistemului de

restricţii în raport cu baza ( )32 aa din spaţiul bunurilor:

⎟⎟⎠

⎞⎜⎜⎝

⎛−

=⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛⋅⎟⎟⎠

⎞⎜⎜⎝

⎛−−

−+⎟⎟

⎠

⎞⎜⎜⎝

⎛4

12123

012

5

4

1

3

2

xxx

xx

sau ⎩⎨⎧

−=−++−=−+

423122

5431

421

xxxxxxx

.

Se observă că ⎟⎟⎠

⎞⎜⎜⎝

⎛−

=−

4121bB nu are toate componentele pozitive.

Dacă se vor anula variabilele nebazice 0541 === xxx şi cele bazice vor

lua valorile 122 =x , 43 −=x , se va obţine o soluţie a problemei care are

două componente nenule (rangA=2) şi vectorii ataşaţi variabilelor bazice sunt liniar independenţi ( 2a şi 3a formează baza). În aceste condiţii,

vectorul ( )TX 0041201 −= nu poate fi SAB, dar ar fi dual


realizabilă dacă ar verifica criteriul de optimalitate. Se va verifica acest lucru:

→jc 3 5 4 0 0

Bc B BX 1a 2a 3a 4a 5a 5

2a 12 2 1 0 -1 0

3 3a -4 -3 0 1 2 -1

jf 48 1 5 3 1 -3

jj cf − -2 0 0 1 -3

Deoarece 044 >− cf , vectorul ( )TX 004120 −= nu este

soluţie dual realizabilă, este doar soluţie pentru modelul scris sub forma standard.

Observaţie: În tabel, vectorul ⎟⎟⎠

⎞⎜⎜⎝

⎛− 32

trecut în coloana lui 1a reprezintă

scrierea acestuia în baza )( 32 aa . Într-adevăr,

⎟⎟⎠

⎞⎜⎜⎝

⎛−

=⎟⎟⎠

⎞⎜⎜⎝

⎛⋅−⎟⎟

⎠

⎞⎜⎜⎝

⎛⋅=−=⎟⎟

⎠

⎞⎜⎜⎝

⎛=

342

10

321

23212

321 aaa .

b) Construim acum duala problemei din enunţ.

3,1,0

202 122453[min]

2321

121

321

=∀≥⎩⎨⎧

→≥++→≥+

++=

jx

uxxxuxx

xxxf

j

, de unde rezultă duala

0,40

5232

2012[max]

21

21

21

21

21

≥

⎪⎩

⎪⎨

⎧

≤+⋅≤+≤+

+=

uuuu

uuuu

uug

.

Se observă că orice cuplu ),( 21 uu care verifică primele două

restricţii ale problemei duale, o verifică şi pe a treia. Mulţimea soluţiilor admisibile ale acestei probleme este dată de intersecţia dintre semiplanele


determinate de inecuaţiile: 32 21 ≤+ uu , 52 21 ≤+ uu şi 42 ≤u , în

condiţiile 0, 21 ≥uu , şi este o mulţime mărginită şi convexă. Atunci (vezi

teorema programării liniare), problema admite soluţie optimă finită. c) Fie baza dată de coloanele 1 şi 2 din matricea sistemului de restricţii ale

problemei primale: )( 21 aaB = . Atunci

301

)53(11

1 =⎟⎟⎠

⎞⎜⎜⎝

⎛== − aBcf B ,

510

)53(21

2 =⎟⎟⎠

⎞⎜⎜⎝

⎛== − aBcf B .

În problema duală, acestei baze îi corespunde un sistem de restricţii saturate, şi anume, restricţiile cu termenii liberi 3 şi 5:

⎪⎩

⎪⎨

⎧

=

=⇒

⎩⎨⎧

=+=+

3731

5232

2

1

21

21

u

u

uuuu

.

d) Soluţia de start pentru algoritmul simplex-dual este o soluţie dual realizabilă (SDR).

Se observă că matricea A conţine matricea unitate de ordinul 2 cu semnul schimbat: ))(1( 54 aaB −= . Restricţiile scrise sub forma standard se vor înmulţi cu (-1):

⎩⎨⎧

−=+−−−−=+−−

202122

5321

421

xxxxxxx

apoi se va scrie sistemul sub forma matriceală:

⎟⎟⎠

⎞⎜⎜⎝

⎛−−

=⎟⎟⎠

⎞⎜⎜⎝

⎛⎟⎟⎠

⎞⎜⎜⎝

⎛+

⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛

⎟⎟⎠

⎞⎜⎜⎝

⎛−−−

−−2012

1001

121012

5

4

3

2

1

xx

xxx

.

Vectorul 1X de componente 0321 === xxx , 124 −=x şi 205 −=x verifică sistemul de restricţii din forma standard, are două

componente nenule (rangA=2), cel puţin una strict negativă, şi corespunde


bazei )( 54 aaB = . 1X va fi SDR dacă ar satisface criteriul de optimalitate. Să verificăm acest lucru:

jc 3 5 4 0 0


4a -12 -2 -1 0 1 0

0 5a -20 -1 -2 -1 0 1

jf 0 0 0 0 0 0

jj cf − -3 -5 -4 0 0

5 4a -2 -3/2 0 1/2 1 -1/2

3 2a 10 1/2 1 1/2 0 -1/2

jf 50 5/2 5 5/2 0 -5/2

jj cf − -1/2 0 -3/2 0 -5/2

5 1a 4/3 1 0 -1/3 -2/3 1/3

3 2a 28/3 0 1 2/3 1/3 -2/3

jf 152/3 3 5 7/3 -1/3 -7/3

jj cf − 0 0 -5/3 -1/3 -17/3

Iteraţia 1: Deoarece 0≤− jj cf , 5,1∈∀j ⇒ 1X este SDR . Se aplică

algoritmul simplex dual: • CEB: min(-12, -20)=-20 ⇒ eliminăm vectorul 5a ; în linia vectorului

eliminat toate componentele sunt pozitive? NU ⇒ aplicăm CIB. • CIB: min(|-3/-1|, |-5/-2|, |-4/-1|)=|-5/-2| ⇒ 2a ia locul lui 5a , 222 −=y

este pivot.

Iteraţia 2: Deoarece 0≤− jj cf , 5,1∈∀j ⇒ 2X este SDR.

• CEB: 4a eliminat

• CIB:2/32/1

2/12/5,

2/32/1min

−−

=⎟⎟⎠

⎞⎜⎜⎝

⎛−−

−− .


Observaţia 1: Matricea 1−B se citeşte din ultimul tabel, în dreptul vectorilor ce au format prima bază, dar, atenţie, elementele vor fi luate cu

semn schimbat: ⎟⎟⎠

⎞⎜⎜⎝

⎛−

−=−

3/23/13/13/21B .

Observaţia 2: Valorile optime ale variabilelor dualei se citesc în linia jf

din ultimul tabel, în dreptul vectorilor ce au format prima bază (ca în tabelul

simplexului-primal), cu semnul impus în modelul dualei: 2,1,0 =∀≥ iui

37,

31 *

2*1 −=−=⇒ uu .

Problema 2 Să se rezolve grafic şi printr-o metodă simplex următorul program liniar:

2,1 ,0

5332

435[min]

21

21

21

21

∈∀≥

⎪⎩

⎪⎨

⎧

≥+≥+−

≥+

+=

jx

xxxx

xxxxf

j

.

Soluţia grafică: În primul rând vom reprezenta grafic mulţimea

soluţiilor admisibile ale problemei. Aşa cum ştim, mulţimea soluţiilor admisibile este generată de restricţiile programului liniar de mai sus, şi se află la intersecţia semiplanelor definite de aceste restricţii. Pentru a găsi semiplanele şi apoi interesecţia acestora, vom reprezenta mai întâi dreptele

4: 211 =+ xxd , 32: 212 =+− xxd şi 53: 213 =+ xxd .

Semiplanul determinat de prima restricţie a problemei este cel mărginit de dreapta 1d şi care nu conţine originea. Semiplanul determinat

de a doua restricţie este determinat de 2d şi nu conţine originea. În fine,

semiplanul determinat de cea de-a treia restricţie este mărginit de 3d şi nu


include originea. Dacă notăm { }Add =21 I , { }Bdd =31 I şi

{ }Cdd =32 I , prin rezolvarea sistemelor de ecuaţii ⎩⎨⎧

=+−=+

324

21

21

xxxx

,

⎩⎨⎧

=+=+

534

21

21

xxxx

şi ⎩⎨⎧

=+=+−5332

21

21

xxxx

, găsim coordonatele punctelor A, B şi C, şi

anume: ⎟⎠⎞

⎜⎝⎛

311,

31A , ⎟

⎠⎞

⎜⎝⎛

27,

21B şi ⎟

⎠⎞

⎜⎝⎛

519,

52C . Astfel, porţiunea haşurată din

grafic reprezintă mulţimea soluţiilor admisibile. Se ştie faptul că soluţia optimă se găseşte într-unul din vârfurile mulţimii soluţiilor admisibile.

Astfel, este foarte uşor de realizat faptul că ⎟⎠⎞

⎜⎝⎛

519,

52C reprezintă punctul de

minim. Valoarea funcţiei obiectiv în acest punct, valoarea minimă a funcţiei,

este 5

675

193525 =⋅+⋅ .

1d

3d

2d

A

B

C

1x

2x

O


Observaţie: Acelaşi lucru ar fi fost observat cu uşurinţă şi dacă am fi construit dreapta de nivel corespunzătoare funcţiei obiectiv,

035: 21 =+ xxd . Ducând paralele la această dreaptă, se vede că prima

paralelă care intersectează mulţimea soluţiilor admisibile ale problemei este

cea care trece prin ⎟⎠⎞

⎜⎝⎛

519,

52C şi se află la cea mai mică distanţă de origine.

Soluţie analitică: Vom utiliza algoritmul simplex dual (punctul a)), apoi algoritmul simplex primal (punctul b)).

Aducem mai întâi problema la forma standard:

5,1 ,0

5332

435[min]

521

421

321

21

∈∀≥

⎪⎩

⎪⎨

⎧

=−+=−+−

=−+

+=

jx

xxxxxx

xxxxxf

j

.

a) Pentru a aplica algoritmul simplex dual, vom înmulţi mai întâi fiecare

restricţie cu ( )1− :

5,1 ,0

53324

35[min]

521

421

321

21

∈∀≥

⎪⎩

⎪⎨

⎧

−=+−−−=+−−=+−−

+=

jx

xxxxxxxxx

xxf

j

, cu ⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛

−−−−−

=100130101200111

A .

Baza de start pentru algoritmul simplex dual trebuie să fie dual

admisibilă. O astfel de bază este formată din vectorii 3a , 4a , 5a .

Cunoscând toate aceste date, putem trece la aplicarea algoritmului menţionat anterior:


jc 5 3 0 0 0


3a -4 -1 -1 1 0 0

0 4a -3 2 -1 0 1 0

0 5a -5 -3 -1 0 0 1

jf 0 0 0 0 0 0

jj cf − -5 -3 Ø Ø Ø

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

0 4a -19/3 0 -5/3 0 1 2/3

5 1a 5/3 1 1/3 0 0 -1/3

jf 25/3 5 5/3 0 6 -1/3

jj cf − Ø -4/3 Ø Ø -1/3

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

3 2a 19/5 0 1 0 -3/5 -2/5

5 1a 2/5 1 0 0 -1/5 -1/5

jf 67/5 5 3 0 -4/5 -1/5

jj cf − Ø Ø Ø -4/5 -11/5

Prima bază admisibilă ( )123 aaa este şi bază optimă pentru

modelul studiat. Din tabelul optimal obţinem cel puţin două informaţii:

• funcţia de eficienţă are valoarea minimă 5

67 ;

• soluţia optimă are componentele: 52*

1 =x , 5

19*2 =x ,

51*

3 =x , 0*4 =x ,

0*5 =x .

b) Să reluăm modelul de la forma standard, deoarece această formă ne sugerează folosirea metodei bazei artificiale (sau metoda celor două faze), în cazul în care se impune rezolvarea prin algoritmul simplex primal.

0≤ j∀ ? DA⇒ SDR

0≤ j∀ ? DA⇒ SDR

0≤ j∀ ? DA⇒ soluţie optimă


Forma extinsă este:

8,1 ,0

5332

435[min]

8521

7421

6321

87621

∈∀≥

⎪⎩

⎪⎨

⎧

=+−+=+−+−

=+−+

++++=

jx

xxxxxxxx

xxxxxxxxxf

j

ααα

.

jc 5 3 0 0 0 α α α

Bc B BX 1a 2a 3a 4a 5a 6a 7a 8a α

6a 4 1 1 -1 0 0 1 0 0

α 7a 3 -2 1 0 -1 0 0 1 0

α 8a 5 3 1 0 0 -1 0 0 1

jf 14α 2α 3α -α -α -α α α α

jj cf − 2α -5 3α -3 -α -α -α Ø Ø Ø

α 6a 1 3 0 -1 1 0 -1 0

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

α 8a 2 5 0 0 1 -1 0 1

jf 3α +9 8α 3 -α -α -α α α

jj cf − 8α -5 Ø -α -α -α Ø Ø

5 1a 1/3 1 0 -1/3 1/3 0 0

3 2a 11/3 0 1 -2/3 -1/3 0 0

α 8a 1/3 0 0 5/3 -2/3 -1 1

jf (58+α )/3 5 3 (5α -11)/3 (2-2α )/3 -α α

jj cf − Ø Ø (5α -11)/3 (2-2α )/3 -α Ø

5 1a 2/5 1 0 0 1/5 -1/5

3 2a 19/5 0 1 0 -3/5 -2/5

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

jf 67/5 5 3 0 -4/5 -11/5

jj cf − Ø Ø Ø -4/5 -11/5


Prin rezolvarea acestui model liniar prin cei doi algoritmi am vrut să evidenţiem, încă o dată, comportarea duală a acestora în ceea ce priveşte atingerea minimului funcţiei f :

Algoritmul simplex primal

Algoritmul simplex dual

α1401 =f

( ) 3/5803 α+=f

9302 += αf

5/67[min] =f

3/2502 =f

001 =f

II. Metode Simplex Pentru Modele Liniare

Documents

Transcript of II. Metode Simplex Pentru Modele Liniare