Programowanie liniowe

Programowanie liniowe – klasa problemów programowania matematycznego, w której wszystkie warunki ograniczające oraz funkcja celu mają postać liniową^[1]. Warunki ograniczające mają postać:

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}\geqslant \alpha ,}$

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}\leqslant \alpha ,}$

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}=\alpha .}$

Mamy zmaksymalizować lub zminimalizować funkcję celu, również liniową:

${\displaystyle f=\alpha +c_{1}x_{1}+c_{2}x_{2}+\ldots +c_{n}x_{n}.}$

Zmienne ${\displaystyle x_{i}}$ są liczbami rzeczywistymi.

Nie zawsze taki problem ma jakiekolwiek rozwiązanie, np.:

${\displaystyle x_{1}\geqslant 2,}$

${\displaystyle x_{1}\leqslant 1.}$

Być może też żadne rozwiązanie nie jest optymalne, ponieważ potrafimy uzyskać dowolnie dużą wartość funkcji celu, np.:

Zmaksymalizuj ${\displaystyle f=x_{1}}$ przy warunku

${\displaystyle x_{1}\geqslant 10.}$

Programowanie liniowe znalazło szerokie zastosowanie w teorii decyzji, np. do optymalizacji planu produkcyjnego. Wiele problemów optymalizacyjnych znajduje rozwiązanie poprzez sprowadzenie ich do postaci problemu programowania liniowego.