2999072765

Rys. 2.1. Interpretacja graficzna zadania programowania liniowego.

Na rys. 2.1 przedstawiona jest interpretacja geometryczna rozpatrywanego przykładu liczbowego oraz jego rozwiązanie. Wielokąt ABCD stanowi zbiór rozwiązań dopuszczalnych Q, w naszym przykładzie jest wielokątem wypukłym na płaszczyźnie punktów (x/, x₂), jest również dwuwymiarowym przypadkiem szczególnym n-wymiarowego obszaru wielościennego, opisanego przez warunki ograniczające [2.2] w ^-wymiarowej przestrzeni. Oczywiście metoda graficznego rozwiązania zagadnienia programowania liniowego może być stosowana jedynie w przypadku n = 2. Wyznaczenie obszaru wielościennego O. w n-wymiarowej przestrzeni (gdy n > 2) i poszukiwane tam określonego wierzchołka, który jest najbardziej oddalony od hiperpłaszczyzny utworzonej przez wielomian funkcji kryterium (c_lx_l + c₂x₂ +... + c_nx„ = 0) jest praktycznie niemożliwe.

Warto w tym miejscu zwrócić uwagę na pewną właściwość rozwiązania optymalnego. Poszukiwany punkt optymalny C, w którym funkcja celu PL osiąga wartość optymalną, nie leży, jak widać na wykresie (rys. 2.1), wewnątrz zbioru O. rozwiązań dopuszczalnych, lecz na jednym z jego wierzchołków. Podobnie będzie również w przestrzeniach «-wymiarowych, gdzie optymalne rozwiązanie będzie leżało gdzieś na wierzchołkach hipersfery utworzonej przez wielościan wypukły.

2.4. Metoda simpleks

Metoda simpleks jest podstawową metodą znajdywania optymalnych rozwiązań zadań programowania liniowego. Jest to metoda ogólna, pozwalająca rozwiązać każde zadanie PL, która polega na sekwencyjnym, ściśle określonym przeglądzie rozwiązań bazowych.