Solutiile problemei de programare liniara

Solutiile problemei de programare liniara

In continuare vom considera problema standard (S) de programare liniara. Pentru compatibilitatea sistemului (2.7.) consideram ca si ceea ce implica

Definitia 3.1. Numim solutia posibila (sau realizabila) a problemei (S) un vector din spatiul solutiilor care satisface (2.7.) si (2.8.).

Multimea solutiilor posibile este o submultime a spatiului vectorial n-dimensional al solutiilor, ea poate fi vida, redusa la un punct, infinita dar marginita, infinita si nemarginita asa cum rezulta din exemplele pe care le vom analiza.

Se demonstreaza ca multimea solutiilor posibile este o multime convexa.

Definitia 3.2. O solutie posibila (sau realizabila) se numeste solutie de baza (sau program de baza) daca are cel mult m componente strict pozitive ( ) si daca vectorii coloana corespunzator coordonatelor nenule (), ale vectorului sunt liniar independenti.

Daca solutia de baza are exact m componente nenule ea este nedegenerata, in caz contrar (daca contine mai putin de m componente nenule) ea este degenerata.

Definitia 3.3 Se numeste solutie optima a problemei (S) o solutie posibila care satisface cerinta de optim (2.9)