Zadanie programowania liniowego polega na znalezieniu punktu na wielościanie, który leży na płaszczyźnie o możliwie największej wartości funkcji celu.|300x300px
Funkcja celu ma postać liniową:
gdzie - zmienne, które są liczbami rzeczywistymi, oraz - stałe parametry określające funkcję.
Warunki ograniczające występują w postaci nierówności lub równości liniowych, tj.:
lub
lub
Celem optymalizacji jest znalezienie punktu dla którego lub
Warunki wykluczające istnienie rozwiązania optymalnego Nie zawsze problem ma jakiekolwiek rozwiązanie:
(1) gdy warunki ograniczające wzajemnie się wykluczają:
(2) gdy żadne rozwiązanie nie jest optymalne, ponieważ można uzyskać dowolnie dużą wartość funkcji celu, np. zadanie: Zmaksymalizuj przy warunku
Postać standardowa Postać standardowa to taka, w której funkcja celu ma być maksymalizowana. Występują tylko warunki postaci:
oraz na każdą zmienną nałożony jest warunek:
Można więc zapisać:
czyli ograniczenia w postaci standardowej można w sposób ogólny zapisać bardziej zwięźle:
Jeszcze zwięźlej ujmuje się to zagadnienie w postaci macierzowej:
Zmaksymalizować funkcję celu
przy ograniczeniach
gdzie: