6. Algoritmul simplex

Cele două teoreme realizează efectiv trecerea către o problemă rezolvabilă pe calculator. Într-adevăr, deoarece o bază este un minor de ordinul m al matricii A şi unei baze îi corespunde o unică soluţie de bază rezultă că sunt cel mult soluţii de bază, adică un număr finit. În acest moment s-ar părea că nu avem decât să lăsăm calculatorul să calculeze toate soluţiile de bază şi valorile funcţiei obiectiv în cele admisibile găsind-o prin comparare pe cea care dă minimul sau maximul funcţiei printre acestea. Totuşi, această variantă se dovedeşte nepractică la o analiză mai atentă, ţinând cont de următoarele observaţii:

1. faptul că numărul soluţiilor de bază este finit ne asigură doar că problema se va termina cândva, ceea ce, din punct de vedere economic, este evident nemulţumitor. Noi dorim ca problema să fie rezolvată în timp util, adică repede. Rezolvând problema ca mai sus vom avea, pentru o problemă cu 50 variabile şi 20 restricţii, de calculat, listat şi comparat soluţii de bază, adică în jur de 1020. Presupunând că suntem dotaţi cu un supercalculator care ar termina un miliard de baze pe secundă, rezolvarea ar dura 3000 ani. De altfel, o problemă ca cea de sus este foarte mică în comparaţie cu problemele "serioase" ce au peste 1000 de variabile şi 100 de restricţii. În plus, un calculator ca cel de sus nu există încă, deci în nici un caz nu e disponibil întreprinderilor obişnuite.

2. Cu algoritmul de mai sus vom găsi cea mai bună soluţie dintre soluţiile admisibile de bază, fără însă să ştim dacă problema admite, de fapt, optim (ar putea să aibă optim infinit).

3. Nu vom şti dacă un minor de mm este bază decât după ce-i vom calcula determinantul şi nu vom şti dacă soluţia de bază corespunzătoare este admisibilă decât după ce o vom calcula.

4. Soluţia optimă, odată găsită, nu va fi recunoscută ca atare decât după ce vom calcula toate celelalte soluţii de bază, chiar dacă ea a apărut chiar la începutul calculelor.

În concluzie, pentru a fi eficient, un algoritm ar trebui să aibă următoarele proprietăţi:

a) să dispună de un criteriu de recunoaştere a faptului că problema nu are soluţii admisibile;

b) să dispună de un criteriu de recunoaştere a faptului că problema are optim infinit;

c) să dispună de un criteriu de recunoaştere dacă o soluţie este optimă sau nu;d) să treacă de la o soluţie de bază admisibilă la una cel puţin la fel de bună (o

soluţie x este mai bună decât o soluţie y dacă f(x) > f(y) într-o problemă de maxim şi f(x) < f(y) într-o problemă de minim;

e) să treacă de la o soluţie la cea mai bună dintre soluţiile cel puţin la fel de bune posibile ca succesoare;

f) să nu revină la o soluţie deja analizată;

g) să efectueze un număr de iteraţii comparabil polinomial cu dimensiunea problemei.

h) să nu introducă erori de rotunjire (sau nu prea mari);i) să fie cât mai simplu de implementat;

Condiţiile de mai sus reprezintă de fapt un algoritm ideal. La începuturile cercetării operaţionale era suficient, de fapt, şi un algoritm care să îndeplinească măcar condiţiile b), c), d), e) şi h). Acest algoritm a fost dat de G.B. Dantzig, în 1947, care la numit algoritmul simplex. El rămâne şi în zilele noastre cel mai eficient algoritm în ceea ce priveşte viteza de lucru, simplitatea şi implementarea pe calculator, pentru problemele care apar efectiv în practica economică.

Totuşi, el nu îndeplinea condiţiile a), f) şi g). Condiţia a) este relativ uşor de îndeplinit şi ea este acoperită prin introducerea

unei faze iniţiale suplimentare la algoritmul simplex, rezultând algoritmul simplex în două faze.

Condiţia f) a fost pusă în momentul în care s-a observat că, în condiţiile existenţei soluţiilor degenerate, se poate ajunge în situaţia când, de la o soluţie dată, nu se poate ajunge decât la una la fel de bună şi tot aşa, astfel încât, dacă nu se iau măsuri de evitare, se poate ajunge la o soluţie care a mai fost, fenomen numit ciclare. Astfel de exemple a fost efectiv găsite, unul fiind exemplul lui Beale prezentat mai jos:

Se observă imediat baza admisibilă B0 = (a1,a2,a3), de la care, aplicând algoritmul sub forma clasică, se vor obţine succesiv bazele admisibile B1 = (a4,a2,a3), B2 = (a4,a5,a3), B3 = (a6,a5,a3), B4 = (a6,a7,a3), B5 = (a6,a2,a3), B6 = (a4,a2,a3) ... . Cititorul poate verifica uşor că toate aceste baze au ca soluţie de bază soluţia (0,0,1,0,0,0,0) şi valoarea funcţiei 0, dar nu îndeplinesc condiţia de optim. Pe de altă parte se vede că B6 = B1 şi deci algoritmul va

repeta la infinit această succesiune de baze, neatingând niciodată valoarea maximă ,

corespunzătoare soluţiei ( ,0,0,1,0,1,0).

Această situaţie este îngrijorătoare nu atât din considerente practice imediate (încă nu a fost găsită o problemă din practică la care să apară acest fenomen, toate exemplele existente fiind artificial construite, ca şi cel de mai sus) cât din faptul că un algoritm implementat pe calculator s-ar putea să fie pus în faţa unei astfel de probleme, situaţie în care n-am putea rezolva problema nici pe calculator, nici manual, ea fiind prea mare. Situaţia a fost depăşită prin diferite tehnici suplimentare adăugate celei de trecere la o

soluţie cel puţin la fel de bună (insuficientă, cum s-a văzut), cea mai cunoscută fiind cea care foloseşte ordonarea lexicografică a soluţiilor, care va fi prezentată şi în această carte.

În fine, referitor la condiţia g), a durat mult timp până s-a demonstrat că algoritmul, sub această formă, nu este în timp polinomial, un exemplu fiind clasa de probleme de mai jos, găsită de Klee şi Minty în 1972, în care algoritmul trebuie să analizeze 2n baze (n = numărul de necunoscute) până la găsirea celei optime.

Pentru o astfel de problemă, la 100 de variabile, algoritmul va avea 2100 1030

iteraţii, şi chiar la o viteză de un miliard iteraţii pe secundă (mult peste puterea unui calculator actual) va termina în 1013 ani.

Nu se ştie încă dacă există sau nu o altă modalitate de trecere de la o bază la alta, folosind tabelele simplex, prin care algoritmul să devină în timp polinomial. Au fost însă găsiţi algoritmi care nu folosesc tabelele simplex, primul fiind algoritmul de punct interior al lui Karmakar, despre care s-a demonstrat că lucrează în timp polinomial.

În ceea ce priveşte erorile de rotunjire, inevitabile când se fac calculele pe un calculator, algoritmul se comportă într-adevăr foarte rău, orice eroare propagându-se imediat la tot tabelul cu efecte foarte mari. Acest lucru poate fi însă depăşit aplicând o variantă a algoritmului, numită varianta revizuită a algoritmului simplex.

Toate punctele slabe ale algoritmului, amintite mai sus, nu au înmormântat însă algoritmul simplex, deoarece folosirea acestuia aduce informaţii mult mai ample decât găsirea soluţiei propriu-zise, este mult mai maleabil în cazul modificărilor ulterioare ale datelor problemei (vezi analiza senzitivităţii soluţiei la datele problemei), se pretează mult mai bine la interpretări economice, este uşor de scris un program de calculator asociat, este implementat pe foarte multe calculatoare şi în plus, aşa cum aminteam mai sus, încă nu a apărut o problemă practică în faţa căruia să clacheze. Noii algoritmi rămân doar ca alternative teoretice sau pentru cazurile în care algoritmul simplex este lent, dar ei nu-l pot înlocui complet.

Se consideră problema de programare

şi un program de bază 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:

Xx

xX

x

xC

c

cC

c

cp

m

s

m

n

p

m

s

m

n

1 1 1 1

; ; ; problema poate fi scrisă:

Înmulţind BX NX Lp s la stânga cu B 1 obţinem:

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

a z a j njij

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 devine:

Deci xi sunt componentele vectorului L în baza B.

Atunci de unde ş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:

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

m

i iji

m

j

1 11si , avem

Observăm că Z f X C B LpT

si Z 1 .

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

c1 c2 cn

C Bp

X

a1 a2 an

vectorii bazei

z z z

z z z

n

m m mm

11 12 1

1 2

...

...

componentele bazice ale lui X

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

f X

Teorema 1. Dacă X este un program de bază pentru PL - min şi în tabelul simplex avem c Z m j nj j 0 1 atunci X este program optim.

Demonstraţie:Avem:

f X f X c Z x f Xj jj m

n

j

0

1 0 pentru orice program admisibil X. Deci X este

optim.

Teorema2. Dacă X este un program de bază şi în tabelul simplex asociat există un t, m t n 1 , astfel încât c Z i mt t 0 0 1si z it , atunci PL - min nu are optim finit.

Demonstraţie: Fie: X x x xnT

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 jj

n

ij jj

m

ij jj m

n

ij j jtj

m

it ij jj

m

ij jt itj

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 jtj

m

it11 1

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 jj

m

ijj

m

jh hh m

n

it it ij jj

m

ij jh hh m

n

j

m

ij jj

m

ij jh hj

m

h m

n

ij jj

m

h ij jhj

m

h m

n

ij jj

m

h ihh m

n

ij jj

m

1 1 1 1 11

1 11 1 11 1

1 1

(renotãm pe h cu j) j ijj m

n

ij jj

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 jj

m

j jj m

n

j j jj

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 3. Dacă X este un program de bază pentru PL - min, iar în tabelul simplex asociat 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:

se poate substitui în baza B vectorul a s cu 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:

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

x xxz

zi is

stit

'

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

x z xz

xzi 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 jj 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 0 pentru 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 t va 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 xz

xz

i m zs

st

i

itit

min / ,1 0 .

Vectorul a s va 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 ijit 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.-Pasul 5 .Concluzie: “PL - min are optim X iar valoarea minimă f X ". STOP.

Exemplul . Fie problema:

min

, , ... ,

f x x x x x

x x x x xx x x x x

x jj

5 7 9 2

3 2 5 3 72 3 4

0 1 2 5

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

Alegem X T 1 2 0 0 0, , , , . Avem:

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

21

11

53

31

; ; ; ; ,

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

, respectiv

01

. 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

32

21

11

3 2 12 1

ceea ce ne dă 1 21 1 , . Deci în baza

B, a B3 1

1

. Analog se găsesc: a aB B

4 511

13

,

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

5 7 9 2 1a a a a a1 2 3 4 5

57

aa

1

2

1 0 1 1 -1

0 1 -1 1

12

c Zj j 0 0 11 -10 -15

19

Deci a 5 intră în bază, a2 iese din bază, z25 - pivot. Se execută pivotajul şi obţinem:

51

aa

1

5

1 1/3 2/3 0

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

5 32 3

//

c Zj j 0 5 6 -5 0 9

Intră în baza a4 şi iese a1 .

3

4/3

X f X'

/

/

'

5 3000

2 3

9

21

aa

4

5

3 4 1 4 1 2 1 01 4 1 4 1 2 0 1/ / // / /

5 41 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 jj

n

1

, , deoarece punctele de extrem ale acesteia

sunt aceleaşi cu punctele de extrem ale funcţiei: g c xj jj

n

1

.