17.4.2
Grafické řešení úloh lineárního programování
Doc. Ing. Alois Fiala, CSc.
NahoruGrafické řešení
Graficky lze řešit úlohu LP, která obsahuje pouze dvě rozhodovací
proměnné. Takové úlohy se v praxi vyskytují jen výjimečně. Význam grafického
řešení však nespočívá v jeho praktické použitelnosti, ale v tom, že pomocí něj
můžeme geometricky ilustrovat vlastnosti úlohy LP a jejího řešení.
Postup grafického řešení sestává z těchto dvou kroků:
-
Zkonstruujeme množinu přípustných řešení jako průnik přímek
(odpovídají omezením ve tvaru rovnic) a polorovin (odpovídají omezením ve tvaru
nerovnic). Každá polorovina je určena hraniční přímkou, jejíž rovnici dostaneme
nahrazením znaku nerovnosti rovnítkem. Je-li průnik prázdný, úloha nemá žádné
přípustné řešení.
-
Hledáme optimální řešení následujícím způsobem. Nejprve do grafu
zakreslíme přímku určenou rovnicí účelové funkce pro nějakou hodnotu kritéria z zvolenou tak, aby procházela množinou přípustných řešení (volbou
různých hodnot z bychom takto dostali systém rovnoběžek). Pak k této
přímce zkonstruujeme nejvzdálenější rovnoběžku ve směru růstu (při
maximalizaci) nebo poklesu (při minimalizaci) hodnot z tak, aby měla
ještě alespoň jeden společný bod s množinou přípustných řešení. Souřadnice
takto nalezeného bodu představují optimální řešení. Takových bodů může být více
(pak tvoří úsečku nebo polopřímku) nebo nemusí existovat žádný (jestliže ve
směru optimalizace není množina přípustných řešení ohraničená).
Příklad 1
Řešme graficky následující úlohu:
Nejprve zkonstruujeme množinu přípustných řešení. Postup této
konstrukce ilustruje prvý z následujících obrázků. Množina přípustných řešení
je průnikem šesti polorovin, odpovídajících vlastním omezením a podmínkám
nezápornosti. Pro každou polorovinu nakreslíme její hraniční přímku (její
rovnici získáme nahrazením znaku nerovnosti rovnítkem) a dosazením souřadnic
nějakého bodu neležícího na této přímce (u vlastních omezení zde můžeme
dosazovat souřadnice počátku) do příslušné nerovnice zjistíme, na kterou stranu
je polorovina orientována (to je v obrázku naznačeno šipkou u příslušné
přímky).
Vidíme, že množina přípustných řešení je neprázdná a můžeme tedy
přikročit k nalezení optimálního řešení (postup je ukázán na následujícím
obrázku). Do grafu zakreslíme dvě přímky, jejichž rovnice získáme z účelové
funkce dosazením hodnot z = 120 a z = 240. Vidíme, že tyto přímky jsou
rovnoběžné a že hodnota z se zvyšuje směrem od počátku. Zkonstruujeme tedy
takovou rovnoběžku s těmito přímkami, která je co nejdále od počátku a přitom
má ještě alespoň jeden bod společný s množinou přípustných řešení. Tato přímka
se množiny přípustných řešení dotýká pouze v jednom bodě, který je tedy
optimálním řešením.
Optimální hodnoty rozhodovacích proměnných jsou určeny
souřadnicemi optimálního bodu a můžeme je odečíst na osách, což však nemusí být
přesné. Pokud tyto hodnoty…
