10. Geometryczne przedstawienie modeli i rozwiązań zadań programowania liniowego
Przy pomocy metody geometrycznej można poszukiwać rozwiązań modeli zadań PL zawierających w zasadzie tylko dwie zmienne. Z tego powodu jest to metoda nieprzydatna do rozwiązywania modeli o dużych rozmiarach. Metoda ta ma jednak pewne zalety poznawcze, które umożliwiają zrozumienie ważnych pojęć dotyczących rozwiązań modeli. W wyniku jej zastosowania można zobaczyć gdzie się znajduje i jak wygląda zbiór rozwiązań dopuszczalnych dla modelu, a także w jaki sposób poszukuje się rozwiązania optymalnego. Można również zobaczyć kiedy model ma tylko jedno rozwiązanie optymalne a kiedy ma ich wiele. I wreszcie można również przy jej pomocy pokazać przypadek gdy model nie posiada rozwiązania optymalnego. Ze względu na te i inne możliwość dostarczenia wielu cennych informacji o rozwiązaniu modelu należy ją poznać.
Geometryczna metoda rozwiązywania modeli jest bardzo prosta w realizacji. Spróbujmy ją poznać rozwiązując przy je pomocy kilka charakterystycznych przypadków dla modeli z dwiema zmiennymi.
Mając dany model liniowy składający się z funkcji celu i warunków ograniczających znaleźć metodą geometryczną rozwiązanie optymalne.
FC = —x, + x, —> max 4 1 2
(«)
(b)
(c)
(d)
(e)
- x, + 2x, <9 (c
7x, -2x2 <21 7x, + 6x2 > 42 x, >0 x2 > 0
Przystępując do rozwiązywania takiego układu należy narysować i oznaczyć układ współrzędnych o osiach Xi i %2 (rys. 10.1). Następnie na osiach nanosimy jednostki. Po czym rysujemy proste, dzięki którym będziemy mogli przedstawić warunki ograniczające. Aby narysować prostą wystarczy znaleźć współrzędne dwóch punktów przez które ona przechodzi. I tak aby wykreślić pierwszy warunek ograniczający oznaczony przez (a) należy narysować prostą -X\+2x2=9. Ponieważ warunek ograniczający (a) podany jest w postaci nierówności znajdujemy i zaznaczamy półpłaszczyznę, której punkty spełniają tę nierówność. Jest to półpłaszczyzna zawierająca punkt (0,0). Podobnie postępujemy