dnes je 14.12.2024

Input:

Grafické řešení úloh lineárního programování

11.1.2008, , Zdroj: Verlag Dashöfer

17.4.2
Grafické řešení úloh lineárního programování

Doc. Ing. Alois Fiala, CSc.

Grafické ř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ů:

  1. 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í.

  2. 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:

                   
z = 4 x1 + 6 x2 max
3 x1 + 3 x2 210
x1 + 2 x2 100
x1 60
x2 40
x1, x2 0

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

Nahrávám...
Nahrávám...