SIMPLEX - programare liniara

O problema de programare liniara poate fi definita ca o problema de maximizare sau minimizare a unei functii liniare supusa unor constrangeri liniare.

Problema standard de maxim:
Trebuie determinat un vector
X = (X1, X2, ..., Xn)
pentru a maximiza
C*X = C1*X1+C2*X2+...+Cn*Xn
si care sa respecte anumite constrangeri:
A11*X1+A12*X2+...+A1n*Xn <= B1
A21*X1+A22*X2+...+A2n*Xn <= B2
.
.
.
Am1*X1+Am2*X2+...+Amn*Xn <= Bm
unde X1, X2, ...,Xn >= 0 		Problema standard de minim:
Trebuie determinat un vector
Y = (Y1, Y2, ..., Ym)
pentru a minimiza
B*Y = B1*Y1+B2*Y2+...+Bm*Ym
si care sa respecte anumite constrangeri:
A11*Y1+A21*Y2+...+Am1*Ym >= C1
A12*Y1+A22*Y2+...+Am2*Ym >= C2
.
.
.
A1n*Y1+A2n*Y2+...+Amn*Ym >= Cn
unde Y1, Y2, ...,Yn >= 0

Terminologie

  • Funtia de maximizat / minimizat se numeste functie obiectiv
  • Vectorul X pentru problema standard de maxim sau vectorul Y pentru problema standard de minim se spune realizabil daca indeplineste constrangerile impuse
  • Setul de vectori realizabili este numit set de constrangeri
  • O problema de programare liniara este numita realizabila daca setul de constrangeri este nenul. In caz contrar se numeste nerealizabila
  • O problema realizabila de maxim / minim se numeste nelimitata daca functia obiectiv poate asuma valori arbitrare mari pozitive / negative pentru vectori realizabili. In caz contrar problema se numeste limitata
  • Valoarea unei probleme realizabile, limitate de maxim / minim este maximul / minimul valorii functiei obiectiv cand variabilele parcurg setul de constrangeri
  • Un vector realizabil pentru care functia obiectiv isi atinge valoarea se numeste optim


Toate problemele de programare liniara pot fi convertite la forma standard


Tipuri de probleme de programare liniara

  • LP -- rezultatele apartin multimii numerelor reale - solutia se numeste relaxation
  • ILP -- rezultatele apartin multimii numerelor intregi
  • MILP -- rezultatele pot apartine multimii numerelor intregi sau multimii numerelor reale
  • BLP -- rezultatele apartin multimii {0,1}