Algoritmul Simplex

• Algoritmul simplex se bazează pe metoda eliminării complete de rezolvare a unui sistem de ecuaţii liniare adaptată scopului urmărit, adică găsirea numai a soluţiilor cu componente nenegative, respectiv a soluţiei pentru care funcţia liniară f are valoarea optimă.

• Presupunem mai departe că opt = max, deoarece dacă se cere minim din relaţia max (-f) = - min (f) rezultă că este suficient să se determine max (-f), iar apoi cu semn schimbat vom avea min f.

• Întrebările la care trebuie să răspundă algoritmul simplex sunt următoarele: cum pornim, cum trecem de la o soluţie la alta mai bună şi cum ne oprim.

• Fie problema de programare liniară:

• Folosind metoda eliminării complete se determină o soluţie de bază şi presupunem că s-au redus primele m coloane:

• În ipoteza că i 0, i = soluţia de bază este:

x B0 = ( 1, 2, …, m, 0, …, 0 ) t şi f (x B0 ) = c1 1 + c2 2 + … + cm m.

• Trecem de la soluţia de bază x B0 la o altă soluţie de bază x B1 care să fie mai bună şi în care necunoscuta principală să fie x m+1 în locul lui x 1. Aceasta se face reducând coloana lui x m+1 şi presupunând că pivot este 1, m+1.

• Avem:

• Dacă elementele de pe ultima coloană sunt 0 atunci soluţia nou obţinută este soluţie de bază:

x B1 =

Avem şi , i = rezultă 1m+1 0 şi (raport minim) adică trecerea de la o soluţie de bază la altă soluţie de bază se face reducând o coloană cu respectarea condiţiilor în alegerea pivotului:

- elementul pivot trebuie să fie pozitiv;

- dacă în coloana care se reduce sunt mai multe elemente pozitive atunci pivotul va fi acela care furnizează cel mai mic raport când termenii liberi se împart la elementele pozitive corespunzătoare, din această coloană.

• Soluţia obţinută x B1 va fi mai bună decât x B0 dacă f (x B1 ) – f (x B0 ) 0.

• Avem f (x B1 ) – f (x B0 ) = c m+1 - c 1 1 – c 2 - … - c m =

= c m+1 – (c 1 1m+1 + c 2 2m+1 + …+ c m mm+1 ) =

= (c m+1 –f m+1) dacă f m+1 = c 1 1m+1 + c 2 2m+1 +…+ c m mm+1 = c B•P m+1

• Cum 0 se obţine condiţia c m+1 – f m+1 0, care ne asigură că prin trecerea de la x B0 la soluţia x B1 s-a obţinut o soluţie mai bună.

• Atunci când toate diferenţele c j – f j 0 soluţia nu se mai poate îmbunătăţii şi acea soluţie de bază este soluţia optimă a problemei.

Etapele algoritmului simplex sunt:

• se determină o soluţie de bază a problemei;

• se calculează valorile f j = c B • P j, j = ;

• dacă există diferenţe c j – f j 0 se trece la o altă soluţie de bază (prin reducerea coloanei cu diferenţa c j – f j cea mai mare) iar dacă nu există c j – f j 0 se trece la etapa 5;

• se repetă etapele 2 şi 3 până nu mai există diferenţe c j – f j 0 ;

• se scrie soluţia optimă: variabilele bazice au valorile corespunzătoare în coloana termenilor liberi, iar cele secundare sunt toate zero, iar valoarea pentru f max = cB • B –1• b.

• Calculele presupuse de etapele algoritmului simplex se pot organiza într-un tabel informaţional, denumit tabelul simplex, în care sunt uşor de găsit numeroase informaţii ale soluţionării prin intermediul rezultatelor numerice.