Rezolvarea problemelor de programare liniara

REZOLVAREA PROBLEMELOR DE PROGRAMARE LINIARA

FUNDAMENTELE ALGORITMULUI SIMPLEX

Consideram problema de programare liniara sub forma standard:

min (max) (z = c'x)

Ax = b (1)

x

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:

(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

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 Testul de optimalitate si criteriul de intrare in baza

Daca pentru toti , atunci baza este

optima, deci programul corespunzator bazei ,

este programul optim, iar este valoarea optima a

functiei obiectiv. STOP.

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.

Daca exista astfel incat si,

, atunci problema are optim infinit. STOP.

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

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

Daca pentru toti , atunci baza este

optima, deci programul corespunzator bazei ,

este programul optim, iar este valoarea optima a

functiei obiectiv. STOP.

Daca exista astfel incat atunci baza

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

Luam astfel incat .

METODA CELOR DOUA FAZE

Pentru aplicarea algorimului simplex este necesara existenta unei baze initiale, de dorit matrice unitate, deci a unui program de baza initial. Mentionam doua metode pentru determinarea unui program de baza initial: metoda celor doua faze si metoda penalitatii. Vom prezenta in continuare prima dintre metodele mentionate.

Prima faza ne permite sa determinam o baza initiala     (in cazul in care aceasta exista).

Ne propunem sa rezolvam problema:

(11)

Etapa 1. Se rezolva problema de programare liniara:

(12)

Am presupus , , fiind vectorul variabilelor artificiale.

Observatii. (i). Nu este necesar sa se introduca m variabile artificiale. Este insa necesar sa se introduca atatea variabile artificiale cati vectori unitari lipsesc pentru a forma o baza unitara.

(ii). Problema (12) se poate scrie in detaliu astfel:

(12

(iii). Problema (12) poseda un program de baza initial (in limbaj geometric, multimea P_a a programelor problemei (12) poseda un varf) de forma:

.

(iv). Valoarea minima a functiei obiectiv a problemei (12) este .

(v). Daca atunci multimea P a programelor problemei (11) este vida.

(vi). Daca atunci, indiferent de faptul ca nici-o variabila artificiala nu este variabila de baza, sau ca exista cel putin o variabila artificiala de baza (evident cu valoare nula), un varf al multimii P_a programelor problemei (12) este un varf al multimii P a programelor problemei (11), caz in care se trece la etapa

Etapa Se rezolva problema initiala, pornind cu baza obtinuta in finalul etapei 1. Daca atunci etapa a doua este consistenta, in caz contrar etapa a doua este inconsistenta, problema initiala neadmitand programe de baza.

Observatii. (i). Daca nici-o variabila artificiala nu face parte din baza, se aplica algoritmul simplex pentru multimea P si functia obiectiv z pana se obtine optimul.

(ii). Daca exista cel putin o variabila artificiala in baza, aplicam algoritmul simplex pentru multimea P_a, cu mentiunea ca ne restrangem numai la muchiile lui P_a, care mentin valoarea nula a lui w, caz in care programul optim (varful optim) va apartine si lui P.

Observatie. Din relatiile (5), (7) si (8) rezulta ca in cadrul unei iteratii simplex, pentru calculul elementelor tabelului simplex este suficienta cunoasterea inversei bazei curente, adica B^-1.

Deoarece nu toate elementele tabelului simplex sunt necesare in cadrul unei iteratii, iar calculul tuturor elementelelor scade eficienta algoritmului, prezentam in continuare algoritmul simplex-revizuit care constituie o varianta "mai economica" a algoritmului simplex. Aceasta varianta este recomandata indeosebi atunci cand n >> m

Tabelul algoritmului simplex-revizuit are urmatoarea forma:

Prima linie a tabelului corespunde primei faze (daca aceasta este necesara), iar cea de a doua linie a tabelului corespunde celei de a doua faze.

In cadrul algoritmului simplex-revizuit un rol deosebit il joaca matricea incadrata din tabelul asociat acestuia si matricea extinsa, adica matricea:

.

Observatii: (i). ;

(ii).

(iii). ;

(iv). ;

(v).