PROGRAMOWANIE LINIOWE

Pełne sformułowanie zadania programowania liniowego zawiera układ równań lub nierówności
liniowych, które opisują warunki (ograniczenia) zadania oraz funkcję liniową wyrażającą cel
rozpatrywanego zadania, zwaną funkcją celu. Oprócz warunków ograniczających w zadaniu
występować mogą także tzw. warunki brzegowe (warunki znaku zmiennych, np. warunek ich
nieujemności lub typu zmiennych, np. warunek ich ciągłości, całkowitoliczbowości lub binarności).

Rozwiązanie optymalne uzyskuje się poprzez minimalizację lub maksymalizację funkcji celu,
z uwzględnieniem warunków ograniczających, w zależności od tego, co opisuje funkcja celu. Jeżeli
funkcja celu opisuje np. zysk przedsiębiorstwa, to należy poszukiwać jej maksimum, jeżeli
natomiast opisuje ona np. koszty przedsiębiorstwa, to należy poszukiwać jej minimum.

Zadaniem PL o postaci standardowej nazywamy zadanie, w którym wszystkie ograniczenia są
nierównościami typu <= dla zadań na maksimum, bądź nierównościami typu >= dla zadań na
minimum oraz wszystkie zmienne muszą być nieujemne.

Zadaniem PL o postaci kanonicznej nazywamy zadanie, w którym wszystkie warunki ograniczające
są równaniami oraz na wszystkie zmienne są nałożone warunki nieujemności.

Podstawowym zabiegiem stosowanym przy rozwiązywaniu zadań decyzyjnych jest sprowadzanie
ich do równoważnej, lecz wygodniejszej ze względów numerycznych postaci. Dla zadania PL
rozwiązywanego metodą SIMPLEKS (będącą podstawową metodą rozwiązywania modeli
programowania liniowego) będzie to postać kanoniczna. Aby uzyskać równoważną dla danego
zadania postać kanoniczną, nierówności sprowadzamy do równości, wprowadzając tzw. zmienne
bilansujące równoważące lewą stronę nierówności z prawą. Zmienne te wchodzą do funkcji celu
z zerowymi wagami.

Równania ograniczeń w zadaniach programowania liniowego wyznaczają zbiór rozwiązań
dopuszczalnych, który jest zbiorem wypukłym. Zbiór wypukły to taki zbiór punktów, że jeżeli A
i B są dowolnymi dwoma punktami zbioru, to odcinek łączący je jest również zawarty w tym
zbiorze.

Rozwiązaniem dopuszczalnym są współrzędne każdego punktu zawartego w zbiorze wypukłym
utworzonym przez warunki ograniczające danego zadania.

Rozwiązanie optymalne to rozwiązanie dopuszczalne spełniające funkcję celu.

Zadanie PL może mieć rozwiązania dopuszczalne lub być zadaniem sprzecznym, nieposiadającym
rozwiązania dopuszczalnego. Jeżeli zadanie PL ma rozwiązania dopuszczalne, to zachodzi jedna
z trzech możliwości: występuje jedno rozwiązanie optymalne, występuje nieskończenie wiele
rozwiązań optymalnych, nie ma rozwiązania optymalnego (zbiór rozwiązań dopuszczalnych jest
nieograniczony z jednej strony w związku z czym funkcja celu jest nieograniczona na zbiorze
rozwiązań dopuszczalnych).

Jeżeli zadanie PL nie jest sprzeczne oraz funkcja celu jest ograniczona na zbiorze rozwiązań
dopuszczalnych, to rozwiązanie optymalne zadania znajduje się w co najmniej jednym punkcie
wierzchołkowym wypukłego zbioru rozwiązań dopuszczalnych.

Jeżeli zadanie PL ma więcej niż jedno rozwiązanie optymalne, to każda wypukła kombinacja
liniowa tych rozwiązań jest rozwiązaniem optymalnym (gdyby dwa wierzchołki stanowiły
rozwiązanie optymalne, to odcinek je łączący też stanowi rozwiązanie optymalne).

Z podanych informacji wynika, że poszukiwanie rozwiązania optymalnego można ograniczyć do
wierzchołków zbioru wypukłego. Spostrzeżenie to ma istotne znaczenie w metodzie SIMPLEKS.