Fundamentele algoritmului simplex

FUNDAMENTELE ALGORITMULUI SIMPLEX

Consideram problema de programare liniara sub forma standard:

min (max) (z = c'x)

Ax = b (1)

x 0

unde

A I M_m,n(R) ,  b I R^m , c I Rⁿ , x I Rⁿ

Presupunem in plus ca liniile matricei A sunt liniar independente (rang(A) = m n

Luam in discutie cazul m<n, deoarece in caz contrar problema de optimizare este triviala.

In detaliu, problema (1) devine:

min (max) (z =)

(2)

.

Definitia 1.       (i). Vectorul x I Rⁿ se numeste program al problemei (1) daca satisface sistemul de restrictii, deci daca Ax = b, x0.

(ii). Programul x se numeste program de baza al problemei (1) daca coloanele matricei A, corespunzatoare componentelor nenule ale lui x sunt liniar independente.

(iii). Programul de baza x se numeste nedegenerat daca are exact m componente nenule si degenerat in caz contrar.

(iv). Se numeste program optim al problemei (1) un program care confera functiei obiectiv valoarea optima.

Notam cu P si respectiv cu S multimea programelor, respectiv multimea programelor optime ale problemei (1):

Observatii. (i). Un program de baza are cel mult m componente nenule.

(ii). Oricarei baze B ce se obtine din matricea A, (BI M_m(R), rang B = m), care satisface proprietatea ca , i se asociaza programul de baza

unde, x^B=B^-1b, x^S = 0 si invers (oricare program de baza corespunde cel putin unei baze B).

(iii). Daca B este o baza si A = ( B S ), sistemul Ax = b este echivalent cu

x^B = B^-1b - B^-1Sx^S (3)

sau, mai detaliat :

,                          (4)

unde am notat :

si . (5)

Am folosit notatia simplificata urmatoare:

.

(iv). In baza relatiei (3) functia obiectiv poate fi exprimata numai cu ajutorul variabilelor secundare astfel:

(6)

unde:

(7)

(8)

Intr-adevar,

Fie acum x un program de baza corespunzator bazei B, adica () si

Presupunem in cele ce urmeaza ca si ca problema (1) este problema de minimizare.

Teorema 1. (Test de optimalitate).

Daca , atunci problema de programare liniara (1) are optim finit; B este baza optima, un program optim este , iar valoarea optimului este .

Demonstratie. Din (6) deoarece si rezulta ca , prin urmare B este baza optima, iar este valoarea functiei obiectiv.

Teorema 2.

Daca exista astfel incat atunci programul asociat bazei B nu este optim (cu exceptia eventual a cazului cand programul este degenerat) si el poate fi imbunatatit daca

Demonstratie. Din (6) tinand seama de faptul ca si rezulta

,

deci baza B nu mai ramane optima, existand o baza mai buna care se obtine din baza B prin introducerea in baza a coloanei (variabilei) a^k (x^k).

Teorema 3. (Criteriul de imbunatatire a programului).

Daca exista cu si cu , atunci poate creste pana la valoarea:

                                (9)

pentru care se obtine un nou program de baza asociat bazei:

Demonstratie. Intr-adevar, datorita conditiei , cresterea lui este limitata de minimul mentionat in enunt, deoarece pentru a nu iesi din tronsonul programelor, adica pentru ca , din (5) rezulta:

, adica,

.

In ipoteza ca minimul se atinge pentru indicele , atunci poate creste pana la valoarea (9).

Teorema 4. (Criteriul de recunoastere a infinititudinii optimului).

Daca existacu si daca pentru toti , atunci problema are optim infinit (-).

Demonstratie. Din (4) deoarece rezulta ca:

,

deci x^k poate creste nemarginit (), iar din (6) rezulta ca:

.

Observatie. Functia obiectiv tinde catre de-a-lungul razei:

In cazul problemei (1) de maximizare teoremele 1 - 4 devin:

Teorema 1'. Daca, atunci problema de programare liniara (1) are optim finit; B este baza optima, un program optim este , iar valoarea optimului este .

Teorema 2'. Daca exista astfel incat atunci programul asociat bazei B nu este optim (cu exceptia eventual a cazului cand programul este degenerat) si el poate fi imbunatatit daca

Teorema 3'. Daca exista cu si cu , atunci poate creste pana la valoarea:

pentru care se obtine un nou program de baza asociat bazei:

Teorema 4'. Daca exista cu si daca pentru toti , atunci problema are optim infinit (+).

Observatie. Oricarei baze B i se asociaza sistemul de valori; .

Aceste valori se trec intr-un tabel, numit tabel simplex, de forma urmatoare:

Am presupus ca primele m variabile (coloane) sunt variabile (coloane) de baza.

Algoritmul simplex este o metoda de explorare sistematica si economica a programelor de baza ale unei probleme de programare liniara, sau, cu alte cuvinte, o metode de trecere de la un program de baza la altul in sensul optimizarii (maximizarii, sau minimizarii) functiei obiectiv, pana la atingerea optimului, daca acesta exista.

Algoritmul simplex este asadar un algoritm iterativ, fiecare iteratie corespunde unei baze (unui program de baza, unui tabel simplex).

Prima linie si prima coloana a tabelului simplex sunt utile numai la prima iteratie a algoritmului simplex.

Teorema 5. Formulele de transformare ale tabelului simplex prin trecere de la baza la sunt:

; ,;

, ; , , ;(10)

;

, .

Demonstratie. Se folosesc relatiile (5) si (6). Din (5), pentru i = l rezulta:

,              

si mai departe

,

de unde, prin identificare, rezulta primele doua relatii din (10). Am notat: si  .

In aceeasi relatie (5) inlocuim pe obtinut mai sus si rezulta:

,

de unde, prin identificare, rezulta urmatoarele doua relatii din (10).

Ultimele doua relatii din (10) se obtin, tot prin identificare, din relatia (6) in care folosim aceeasi expresie a lui rezultata din (5):

Algoritmul simplex in cazul problemei (1) de minimizare consta in urmatoarele:

Pasul 1.Se determina o baza initiala (de preferat );

Se calculeaza , , , si se intocmeste tabelul simplex corespunzator bazei .

Pasul 2.Testul de optimalitate si criteriul de intrare in baza

2.1.          Daca pentru toti , atunci baza este

optima, deci programul corespunzator bazei ,

este programul optim, iar este valoarea optima a

functiei obiectiv. STOP.

2.2.          Daca exista astfel incat atunci baza

nu este optima si ea poate fi imbunatatita introducand in baza pe .

Luam astfel incat .

Pasul 3.Criteriul de iesire din baza.

3.1.          Daca exista astfel incat si,

, atunci problema are optim infinit. STOP.

3.2.       Daca exista astfel incat si exista astfel incat , atunci se determina astfel incat:

In acest caz iese din baza.

Pasul 4.Se trece de la baza la ,

,

se transforma tabelul simplex dupa formulele date de teorema 5 si se reia algoritmul de la pasul 2.

Observatie. In cazul in care problema este de maximizare Pasul 2 devine Pasul 2', iar Pasul 3 devine Pasul 3':

Pasul 2'.Testul de optimalitate si criteriul de intrare in baza

2'.1.     Daca pentru toti , atunci baza este

optima, deci programul corespunzator bazei ,

este programul optim, iar este valoarea optima a

functiei obiectiv. STOP.

2'.2.     Daca exista astfel incat atunci baza

nu este optima si ea poate fi imbunatatita introducand in baza  pe .

Luam astfel incat .