Notiuni generale privind problema programarii liniare

Notiuni generale privind problema programarii liniare

Exemplele prezentate conduc la rezolvarea unor probleme matemetice asemanatoare. Forma standard a unei probleme de programare liniara de minim (sau program liniar de minimizare) se prezinta astfel:

iar a unui program liniar de maximizare:

Conditiile restrictive se mai numesc si restrictiile programului liniar.

Daca notam:

atunci se transcrie matriceal astfel:

iar :

Evident ca sistemul de restrictii poate fi:

incompatibil

compatibil unic determinat (numai in cazul )

compatibil nedeterminat.

Ultimul caz intereseaza cel mai mult pentru ca aici se pune problema de a alege dintre mai multe solutii pe cea mai buna.

Pentru modelele de PL care nu au forma standard exista modalitati de construire a unor forme standard echivalente. Acestea sunt prezentate in II.5.

Sa presupunem ca rangul lui A este m.Daca notam coloanele matricei A cu atunci restrictiile problemei se transcriu:

Definitia II.3.1. Un vector , ale carui componente satisfac restrictiile unei probleme de programare liniara, se numeste program admisibil (sau solutie admisibila, sau solutie posibila)

Definitia II.3.2 Un program admisibil care minimizeaza (sau maximizeaza, in functie de problema) functia liniara asociata acelei probleme se numeste program optim (sau solutie optima).

Definitia II.3.3.Un program se numeste program de baza daca vectorii coloana , corespunzatori componentelor nenule , sunt liniar independenti.

Deoarece rang un program de baza are cel mult m componente nenule;

Definitia II.3.4. Daca un program de baza are exact m componente nenule (m= rang A), atunci programul de baza se numeste nedegenerat. In caz contrar, degenerat.

Definitia II.3.5. Matricea B de tipul m x m formata din coloanele lui A corespunzatoare componentelor nenule ale unui program de baza nedegenerat X se numeste baza a programului X.

Exemplul II.3.1. Problema de programare liniara:

se transcrie matriceal astfel:

min ( 2 -3 -3 1 ) . ( x₁ x₂ x₃ x₄ )^T

Sistemul liniar de restrictii se transcrie si sub forma:

Programe ale problemei sunt de pilda:

primele doua fiind si programe de baza nedegenerate cu bazele respectiv (sau cu notatiile anterioare

Valorile functiei obiectiv, corespunzatoare celor trei programe sunt: Programul nu este de baza deoarece vectorii coloana corespunzatori componentelor nenule, respectiv: sunt liniar dependenti.

Vectorul , desi verifica sistemul de restrictii nu este program admisibil deoarece nu are toate componentele nenegative.

Notam cu P multimea solutiilor posibile ale unei probleme PL - min. Deci si notam cu multimea programelor optime ale acestei probleme:

.

Teorema II.3.1. Multimile P sisunt convexe.

Demonstratie: Sa demonstram ca P este convexa, adica

Faptul ca este evident.

Deoarece . Deci: .

Deci:

Pentru a demonstra ca este convexa, fie Avem:

Deci este optim.

Teorema II.3.2. Daca o problema de programare liniara admite programe atunci admite si programe de baza.

Teorema II.3.3. Daca un program liniar are optim, atunci are si un program optim de baza.

Pentru demonstratia acestor doua teoreme avem nevoie de urmatoarea lema:

Lema II.3.1. Oricare ar fi sistemele de numere reale: se poate determina un numar astfel incat pentru orice si pentru cel putin un indice j, , sa avem

Demonstratia lemei. Grupam indicii dupa semnul numerelor astfel incat . Cum nu toti sunt nuli, , avem . Daca comparam rapoartele cu si apoi pe cele cu . Gasim si astfel incat:

Vom lua iar j astfel:

- daca

- daca

Observand ca vom avea in ambele cazuri .

Daca luam iar daca luam.

Demonstratia lemei este incheiata.

Demonstratia teoremei II.3.2. Vom demonstra ca un program de baza este un program admisibil cu un numar minim de componente nenule.

Fie X programul admisibil cu numarul minim de componente nenule. Fie r numarul componentelor sale nenule. (Orice alt program admisibil va avea cel putin r componente nenule).

Daca r = 0 atunci X = 0 este program de baza. Daca r > 0, fie componentele strict pozitive ale lui X. (restul sunt nule). Daca sunt liniar independenti atunci X este program de baza. Sa presupunem prin reducere la absurd ca sunt liniar dependenti , adica exista nu toti nuli astfel incat:

(5)

Considerand pentru

atunci folosind (5) putem scrie . Atunci:

(6)

Acum aplicam lema II.3.1. pentru sistemele Deci exista astfel incat, pentru un

sa avem

pentru macar un . Atunci devine un program admisibil dar cu cel mult componente nenule, contrar ipotezei. Deci relatia (5) nu este posibila, rezulta ca X este program de baza.

Demonstratia teoremei II.3.3. Fie un program optim pentru PL - min care are un numar minim r de componente nenule. Daca r = 0 atunci este program optim de baza. Daca r > 0, fie coloanele lui A corespunzatoare celor r componente nenule din . Daca aceste coloane sunt liniar independente atunci este program optim de baza. Presupunem prin absurd ca aceste coloane ar fi liniar dependente. Cu aceleasi notatii ca in demonstratia precedenta gasim un satisfacand

Daca am putea alege un astfel incat

atunci contrar faptului ca este program optim; deci .

Atunci alegand un astfel ca sa aiba cel mult r-1 componente nenule gasim ca ceea ce contrazice faptul ca r este numarul minim de componente nenule pentru un program optim. Deci este program optim de baza.

In concluzie, un program optim de baza este un program optim cu un numar minim de componente nenule.

Teoremele II.3.2. si II.3.3. reduc cautarea solutiei optime a unei probleme de programare liniara printre programele de baza, al caror numar este finit. Cu algoritmul simplex se porneste de la un program de baza care nu este optim si se construieste un alt program de baza in care functia obiectiv sa aiba o valoare mai mica sau mai mare, dupa cum este un PL - min sau PL - max.