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 în 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 în 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, în 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. În 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 ) . ( x1 x2 x3 x4 )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 încât pentru orice si pentru cel putin un indice j, , sa avem
Demonstratia lemei. Grupam indicii dupa semnul numerelor astfel încât . Cum nu toti sunt nuli, , avem . Daca comparam rapoartele cu si apoi pe cele cu . Gasim si astfel încât:
Vom lua iar j astfel:
- daca
- daca
Observând ca vom avea în ambele cazuri .
Daca luam iar daca luam.
Demonstratia lemei este încheiata.
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 încât:
(5)
Considerând pentru
atunci folosind (5) putem scrie . Atunci:
(6) ...
