14 Algoritmul SimplexAlgoritmul simplex este o metoda analitica de determinare a solutiei unei probleme de programare liniara.Daca n este numarul variabilelor iar m este numarul restrictiilor problemei de programare, se poate arata ca

exista o solutie a problemei de programare liniara pentru care cel putin nm din variabilele x1, . . . , xn sunt egalecu zero (o astfel de solutie se numeste solutie de baza). Desi aceasta simplifica mult problema (solutia problemeipoate fi cautata numai ntre solutiile avnd n m valori egale cu zero), problema este n continuare dificila (nspecial pentru valori mari ale lui n si m), si este nevoie de o metoda sistematica de cautare a solutiei problemei.Metoda / algoritmul Simplex este o metoda iterativa n care se pleaca de la o solutie admisibila de baza si

se construiesc alte solutii de baza astfel nct valoarea functiei obiectiv creste catre valoarea optima.Vom prezenta aceasta metoda mai nti pe un exemplu concret.

Exemplul 14.1 Sa se rezolve problema de programare liniara

max (60x1 + 30x2 + 20x3) (73)

n conditiile

8x1 + 6x2 + x3 484x1 + 2x2 + 1.5x3 202x1 + 1.5x2 + 0.5x3 8

x2 5(74)

x1, x2, x3 0.

Solutia 14.2 Sa observam ca problema este n forma standard (problema este de maxim, toate inegalitatile sunt).Introducem variabilele de compensare y1, y2, y3 0 pentru a transforma toate inegalitatile n egalitati:

y1 = 48 8x1 + 6x2 + x3y2 = 20 4x1 + 2x2 + 1.5x3y3 = 8 2x1 + 1.5x2 + 0.5x3y4 = 5 x2

(75)

x1, x2, x3, y1, y2, y3, y4 0.

Sa observam ca o solutie admisibila a problemei se poate obtine considernd x1 = x2 = x3 = 0 si rezolvndsistemul anterior, adica y1 = 48, y2 = 20, y3 = 8 si y4 = 5. Spunem ca y1, y2, y3, y4 sunt variabile de baza iarx1, x2, x3 sunt variabile auxiliare.O prima problema este urmatoarea: este solutia gasita o solutie optima? Raspunsul este NU, deoarece ob-

servam ca marind putin valoarea x1 = 0, valoarea functiei obiectiv f = 60x1 + 30x2 + 20x3 va creste (si decivaloarea nu este maxima). Acelasi lucru se observa si pentru x2 si x3. n general, solutia gasita NU ESTE OPTIMAdaca coeficientii variabilelor auxiliare n functia obiectiv sunt numere pozitive (n cazul de fata, acesti coeficientisunt 60, 30 si respectiv 20).Alegem asadar variabila x1 ca si variabila care va intra n baza (deoarece coeficientul ei este 60, si deci va produce

o crestere mai rapida a functiei obiectiv).O a doua problema este urmatoarea: cu ct putem mari valoarea valoarea variabilei ce va intra n baza? Sa

observam ca deoarece y1, y2, y3 0 si x2 = x3 = 0, conditiile de mai sus ne arata ca trebuie sa avem:

y1 = 48 8x1 0y2 = 20 4x1 0y3 = 8 2x1 0y4 = 5 0

, (76)

de unde obtinem

x1 6x1 5x1 4

, (77)

si deci valoarea maxima care o poate lua x1 este x1 = 4 (data de cea de-a treia inegalitate). A treia inegalitate serefera la y3, ceea ce ne arata ca y3 va deveni o variabila auxiliara (cu valoarea y3 = 0, deoarece x1 = 4), iar x1 vadeveni o variabila de baza cu valoarea x1 = 4.

61

A treia etapa pentru continuarea procedeului este sa rescriem membrul drept al functiei obiectiv si al egalitatilorn functie de variabilele auxiliare, adica n functie de x2, x3 si y1. Pentru aceasta, rezolvam a treia ecuatie n (75)n functie de x1, iar apoi eliminam variabila x1 din restul ecuatiilor si din functia obiectiv folosind aceasta ecuatie.Dupa calcule, obtinem:

max (240 15x2 + 5x3 30y3) (78)

y1 = 16 +x3 +4y3y2 = 4 +x2 0.5x3 +2y3x1 = 4 0.75x2 0.25x3 0.5y3y4 = 5 x2

(79)

x1, x2, x3, y1, y2, y3 0. (80)

Repetnd acum pasii 1 3 de mai sus, observam ca variabila x3 devine variabila de baza, cu valoarea x3 = 8data de a doua ecuatie, iar y2 devine variabila auxiliara, cu valoarea 0. Obtinem noua problema:

max (280 5x2 10y2 10y3) (81)

y1 = 24 +2x2 2y2 +8y3x3 = 8 +2x2 2y2 +4y3x1 = 2 1.25x2 +0.5y2 1.5y3y4 = 5 x2

(82)

x1, x2, x3, y1, y2, y3 0. (83)

cu solutia x2 = y2 = y3 = 0 si x1 = 2, x3 = 8, y1 = 24 si y4 = 5.Cum coeficientii variabilelor auxiliare (x2, y2, y3) n functia obiectiv sunt negativi, solutia gasita este optima.Valoarea maxima a functiei obiectiv este deci f = 280, si se obtine pentru x1 = 2, x2 = 8 si x3 = 0.

Putem simplifica calculul de mai sus procednd n felul urmator. Aranjam coeficientii functiei obiectiv siai restrictiilor date ntr-un tabel, n care pe prima linie apar coeficientii din functia obiectiv (73), iar pe liniileurmatoare apar ecuatiile (75), pe care le rescriem trecnd n membrul stng necunoscutele problemei. n primacoloana apar coeficientii lui x1, n adoua coloana coeficientii lui x2, samd. Obtinem astfel urmatorul tabel:

x1 x2 x3 y1 y2 y3 y4 Valori Baza60 30 20 0 0 0 0 08 6 1 1 0 0 0 48 y1 = 484 2 1.5 0 1 0 0 20 y2 = 202 1.5 0.5 0 0 1 0 8 y3 = 8 =0 1 0 0 0 0 1 5 y4 = 5

La pasul urmator, pentru a determina care variabila va intra n baza, alegem din linia 1 (functia obiectiv aproblemei) variabila auxiliara avnd cel mai mare coeficient pozitiv, adica x1. Pentru determina care variabila vaiesi din baza, formam rapoartele ntre termenii coloanei Valori si cei ai coloanei lui x1 (variabila ce va intra nbaza), pentru care coeficientul respectiv este strict pozitiv, si l alegem pe cel mai mic. Obtinem

48

8= 6,

20

4= 5,

8

2= 4,

si deci valoarea minima este x1 = 4, fiind data de penultima linie - aceasta arata ca variabila respectiva (y3 nacest caz) este variabila ce va iesi din baza. Numarul 2, situat n coloana variabilei ce intra n baza si n liniacorespunzatoare variabilei ce iese din baza se numeste pivot.Se poate verifica usor ca procedeul indicat pentru etapa a treia de mai sus revine la:

linia pivotului se mparte la pivot

toate numerele din coloana pivotului, cu exceptia pivotului, devin 0

restul numerelor din tablou se modifica dupa regula dreptunghiului, dupa cum urmeaza: pentru a determinanoua valoare a unui numar, se considera cele patru numere aflate n colturile dreptunghiului avnd diagonalaformata de pivot si de numarul ales. Noua valoare a numarului se determina astfel: se scade din vecheavaloarea a numarului produsul numerelor de pe cealalta diagonala a dreptunghiului (cea care nu contine

62

pivotul) mpartit la pivot. Spre exemplu, n cazul de fata pivotul are valoarea 2, fiind situat n prima coloanasi a patra linie a tabelului de mai sus. Noua valoare a numarului aflat n a doua linie si a doua coloana atabelului, este

6 8 1.52

= 6 6 = 0.

Numarul aflat n prima linie si a doua coloana a tabelului devine

30 60 1.52

= 30 45 = 15.

Procednd astfel, obtinem al doilea tabel (a doua etapa din algoritmul simplex):

x1 x2x3 y1 y2 y3 y4 Valori Baza

0 15 5 0 15 30 0 2400 0 1 1 0 4 0 16 y1 = 160 1 0.5 0 1 2 0 4 y2 = 4 =1 0.75 0.25 0 0 0.5 0 4 x1 = 40 1 0 0 0 0 1 5 y4 = 5

Variabilele auxiliare au valoarea 0, iar valorile variabilelor de baza sunt date de coloana Valori a tabelului(acestea se trec n coloana Baza a tabelului).n continuare, pentru a determina daca solutia este optima, se determina daca coeficientii din functia obiectiv

(prima linie a tabelului) ai vreuneia din variabilele auxiliare este pozitiv. Daca da, atunci solutia gasita nu esteoptima, n caz contrar solutia fiind optima.n cazul de fata solutia nu este optima, variabila x3 urmnd a intra n baza (are coeficient +5). Procednd ca

mai sus, se determina pivotul 0.5 (linia 3, coloana 2 a tabelului), si deci variabila y2 va iesi din baza.Dupa o noua iteratie a algoritmului simplex, rezulta tabelul

x1 x2 x3 y1 y2 y3 y4 Valori Baza0 5 0 0 10 10 0 2800 2 0 1 2 8 0 24 y1 = 240 2 1 0 2 4 0 8 x3 = 81 1.25 0 0 0.5 1.5 0 2 x1 = 20 1 0 0 0 0 1 5 y4 = 5

Variabilele auxiliare sunt x2, y2, y3, toate avnd coeficienti negativi in functia obiectiv (prima linie a tabelului), sideci solutia gasita este optima. Valoarea optima este f = 280 (coloana Valori, prima linie, dar cu semn schimbat),fiind obtinuta pentru x1 = 2, x2 = 0 si x3 = 8.Aloritmul simplex consta deci n urmatorii pasi:

1. Se determina o solutie admisibila (prin introducerea variabilelor suplimentare y1, y2, . . . SAU prin rezolvareaunei probleme suplimentare)

2. Se determina daca solutia gasita este optima (daca toti coeficientii variabilelor auxiliare din functia obiectivsunt negativi). Daca DA, atunci ne oprim: valoarea maxima este data de elementul din prima linie a coloaneiValori, dar cu semn schimbat, valorile variabilelor de baza fiind date de ultima coloana a tabelului, restulfiind egale cu zero.

Daca solutia nu este optima, determinam variabila care intra n baza (variabila cu cel mai mare coeficientpozitiv din functia obiectiv) si variabila care iese din baza (formam rapoartele ntre termenii coloanei Valorisi cei ai coloanei variabilei ce va intra n baza, care sunt pozitivi, si alegem cea mai mica valoare. Liniacorespunzatoare este linia variabilei ce iese din baza). Pivotul este elementul situat n coloana variabilei ceintra n baza si n linia variabilei ce iese din baza.

3. Se determina noul tabel simplex (linia pivotului se mparte la valoarea pivotului, elementele din coloanapivotului devin 0, cu exceptia pivotului, iar restul numerelor se modifica cu regula dreptunghiului, de maisus). Se revine apoi la pasul 2.

Exercitii

63

n fiecare din problemele de mai jos, sa se scrie problema n forma standard si sa se rezolve prin metoda simplex,presupunnd ca toate variabilele x1, x2, . . . sunt ne-negative.

Exercitiul 14.1 Sa se maximizeze f (x1, x2) = 30x1 + 20x2 n conditiile x1 + x2 5, 2x1 + x2 10.

Exercitiul 14.2 O firma doreste sa maximizeze productia totala zilnica, producnd x1 unitati de produs ntr-unproces P1 si x2 unitati de produs ntr-un proces P2. Procesul P1 necesita 2 ore de munca fizica si 5 ore de lucru aunei masini, iar procesul P2 necesita 4 ore de munca fizica si 2 ore de lucru a unei masini. Firma are la dispozitiezilnic 800 de ore de munca fizica si 600 de ore de lucru a masinilor. Sa se determine alegerea optima pentru x1 six2.

Exercitiul 14.3 f (x1, x2) = 40x1 + 88x2, n conditiile 2x1 + 8x2 60, 5x1 + 2x2 60.

Exercitiul 14.4 Sa se maximizeze productia zilnica n cazul producerii a x1 scaune ntr-un proces P1 si x2 scaunentr-un proces P2 n conditiile 3x1+4x2 550 (numarul de ore-masina pe zi), 5x1+4x2 650 (numarul de ore demunca manuala pe zi).

Exercitiul 14.5 Sa se maximizeze f (x1, x2, x3) = 2x1 + x2 + 3x3 n conditiile 4x1 + 3x2 + 6x3 12.

Exercitiul 14.6 Sa se maximizeze profitul zilnic n producerea a x1 rame R1 (profit 90 lei) si x2 rame R2 (profit50 lei) n conditiile x1 + 3x2 18 (restrictii de materiale), x1 + x2 10 (restrictii ore-masina) si 3x1 + x2 24(restrictii ore munca manuala).

Exercitiul 14.7 Sa se minimizeze f (x1, x2) = 5x1 20x2 n conditiile 2x1 + 10x2 5, 2x1 + 5x2 10.

Exercitiul 14.8 Sa se minimizeze f (x1, x2, x3) = 4x110x220x3 n conditiile 3x1+4x2+5x3 60, 2x1+x2 20,2x1 + 3x3 30.

Exercitiul 14.9 Sa se maximizeze profitul unei firme ce produce x1 baterii B1 ntr-un proces P1 si x2 baterii ntr-un proces P2, si x3 baterii B2 ntr-un proces P3 si x4 ntr-un proces P4, n conditiile 12x1 +8x2 + 6x3 +4x4 120(numarul ore-masina) si 3x1 + 6x2 + 12x3 + 24x4 180 (numarul de ore de munca manuala).

64