problem programowania liniowego można zdefiniować jako problem maksymalizacji lub minimalizacji funkcji liniowej podlegającej systemowi ograniczeń liniowych. Ograniczenia mogą być równościami lub nierównościami. Funkcję liniową nazywa się funkcją celu, o postaci f (x, y) = A x + b y + C. Zbiór rozwiązań układu nierówności jest zbiorem możliwych lub wykonalnych rozwiązań, które mają postać (x, y).,
Jeśli problem programowania liniowego można zoptymalizować, wartość optymalna pojawi się na jednym z wierzchołków regionu reprezentującego zbiór możliwych rozwiązań.
gdy wykres układu nierówności tworzy obszar zamknięty, mówi się, że region jest ograniczony. Czasami system nierówności tworzy region, który jest otwarty. W tym przypadku region nazywa się unbounded.
aby rozwiązać problem programowania liniowego, wykonaj następujące kroki.
• Wykreśl region odpowiadający rozwiązaniu systemu ograniczeń.,
• Znajdź współrzędne wierzchołków utworzonego regionu.
• ocenia funkcję celu na każdym wierzchołku, aby określić, które wartości x i y, jeśli istnieją, maksymalizują lub minimalizują funkcję.