8416073985

Programowanie liniowe

Programowanie liniowe jest to sformułowanie problemu decyzyjnego w postaci zadania optymalizacji matematycznej. Oznacza zbiór matematycznych modeli, opisujących rozpatrywaną sytuację decyzyjną oraz zestaw metod szukania minimów lub maksimów funkcji kryterialnych. Zagadnienie programowania liniowego to szczególny przypadek zagadnienia programowania matematycznego, w którym wszystkie związki zachodzące między zmiennymi mają charakter liniowy.

„Metoda geometryczna”

Zadanie programowania liniowego (PL) można zinterpretować i rozwiązać geometrycznie. W tym celu zagadnienie PL należy przedstawić w postaci kanonicznej gdzie przestrzeń rozwiązań X e R² jest przestrzenia działania:

cX = min cX

XeX„

X„=(X: XeR', AX-b <o}.

Interpretacja geometryczna zadania PL:

W przestrzeni działań, jeśli zbiór rozwiązań dopuszczalnych:

^u> b e R",ce R²

X_n = X : X e i?"

(przy czym b e R",c e R² jest ograniczony), to tworzy on wielościan wypukły S. Wyrażenie z=c*X określa w przestrzeni R² rodzinę równoległych hiperpłaszczyzn, przy czym wektor - c prostopadły do tych hiperpłaszczyzn wskazuje kierunek malenia funkcji z. Wychodząc z pewnej hiperpłaszczyzny należącej do tej rodziny i mającej wspólne punkty z wieloscianem S, przy przesuwaniu jej rónolegle w kierunku malenia z, można dojść do takiego jej położenia, że staje się ona hiperpłaszczyzną podpierającą. Jeśli ta hiperpłaszczyzna ma tylko jeden punkt wspólny ze zbiorem X₀ to punkt ten będzie punktem wierzchołkowym i zadanie PL ma jedyne rozwiązanie optymalne.

>3<