3 Úloha lineární optimalizace Od této přednášky se začneme zabývat jistou obsáhlou a dobře prozkoumanou třídou optima- lizačních úloh zvanou úlohy lineární optimalizace, neboli lineární programování LP. Typickým znakem takových úloh je spojitost a "konvexita" jejich řešení. Úloha LP se skládá z lineárního (vektorového) univerza, omezujících podmínek vyjádřených jako lineární rovnosti a nerovnosti a z lineární účelové funkce. Stručný přehled lekce ˇ Ukázat matematické formulace úloh lineární optimalizace. ˇ Formální zápis těchto úloh pomocí matic a vektorů. ˇ Převádět formulace těchto úloh do standardizovaných tvarů. Petr Hliněný, FI MU 1 IA102 "OU": Lineární optimalizace 3.1 Příklad formulace úlohy Příklad 3.1. Firma hodlá prodávat lupínky za 120Kč/kg a hranolky za 76Kč/kg. Na výrobu 1kg lupínků se spotřebují 2kg brambor a 0.4kg oleje. Na výrobu 1kg hranolek je zapotřebí 1.5kg brambor a 0.2kg oleje. Firma má nakoupeno 100kg brambor a 16kg oleje. Brambory stály 12Kč/kg a olej 40Kč/kg. Nalezněte takový plán výroby, při kterém firma nejvíce vydělá. Řešení: Nechť vyrobíme kg lupínků a h kg hranolků. Dané podmínky jsou ­ máme k dispozici 100kg brambor ­ a 16kg oleje, ­ navíc lze (pochopitelně) vyrobit jen nezáporné množství od každého výrobku. Tedy v matematickém zápise dle výše uvedených bodů 2 + 1.5h 100 0.4 + 0.2h 16 , h 0 . Tyto nerovnice nám určují množinu všech přípustných řešení úlohy ve vektorovém pro- storu se dvěma souřadnicemi , h. Petr Hliněný, FI MU 2 IA102 "OU": Lineární optimalizace Našim cílem je maximalizace zisku, na to však mohou být dva různé (i když podobné) pohledy: ˇ Můžeme být v situaci, kdy nakoupené suroviny již nelze jinak využít a jejich zbytky se vyhodí. V tom případě nás zajímá jen hrubý zisk z tržeb, tedy optimalizujeme funkci max 120 + 76h . (Náklady surovin jsou fixní a lze je nakonec od tržeb odečíst, nezávisle na řešení úlohy.) ˇ Můžeme také uvažovat situaci, kdy se zbytky z výroby dále využijí (na další výrobu či se vrátí dodavateli). Potom však musíme náklady surovin započítat již do účelové funkce, neboli počítat čistý zisk po odečtení nákladů, takže vyjde max (120 - 24 - 16) + (76 - 18 - 8)h = 80 + 50h . Optimálním řešením je v tomto příkladě, při obou formulacích účelové funkce, vyrobit 20kg lupínků a 40kg hranolků. Tržba firmy v první formulaci je 5440Kč, zisk z výroby v druhé formulaci je 3600Kč. Jak ale k těmto výsledkům dospějeme? . . . . . . 2 Petr Hliněný, FI MU 3 IA102 "OU": Lineární optimalizace 80 66 40 40 50 80 h 0.4 + 0.2h 16 2 + 1.5h 100 80 + 50h max Obrázek 3.1: Grafický význam předchozí úlohy LP (Příklad 3.1): Množina přípustných řešení je šrafovaná, optimum je vyznačeno kroužkem. Petr Hliněný, FI MU 4 IA102 "OU": Lineární optimalizace 3.2 Složitější formulace Příklad 3.2. Spotřebitelé požadují 7, 8, 10 a 11 tun cementu. Sklady cementu jsou tři, s kapacitami po řadě 10, 15 a 11 tun. Dopravní náklady mezi sklady (řádky) a spotřebiteli (sloupce) jsou dané tabulkou sp 1 sp 2 sp 3 sp 4 sklad 1 4 5 5 3 sklad 2 6 6 7 8 sklad 3 5 7 7 5 na tunu nákladu. Minimalizujte dopravní náklady mezi spotřebiteli a sklady. Řešení: Podmínky jsou: ˇ Dodání cementu pro i-tého spotřebitele z j-tého skladu x11 + x12 + x13 = 7, x21 + x22 + x23 = 8, x31 + x32 + x33 = 10, x41 + x42 + x43 = 11. ˇ Dodržení kapacit skladů x11 + x21 + x31 + x41 10, Petr Hliněný, FI MU 5 IA102 "OU": Lineární optimalizace x12 + x22 + x32 + x42 15, x13 + x23 + x33 + x43 11. ˇ Podmínky nezápornosti xij 0 pro i = 1, 2, 3, 4 j = 1, 2, 3. Poznámka: Podmínky nezápornosti nyní nejsou zcela nutné. Převoz záporného množství ce- mentu ze skladu spotřebiteli má reálný význam ­ spotřebitel dostal z jiných skladů více ce- mentu, než potřebuje, tak zbylé množství vrací do skladu. Hodnocení účelové funkce nám však zaručí, že takové zbytečné převozy tam a zpět se neuskutecční v optimálním řešení. Cílem je minimalizace přepravních nákladů, účelová funkce tedy vypadá takto: min 4x11 +5x21 +5x31 +3x41 +6x12 +6x22 +7x32 +8x42 +5x13 +7x23 +7x33 +5x43. Petr Hliněný, FI MU 6 IA102 "OU": Lineární optimalizace Optimální hodnota účelové funkce je (x) = 188.0 a hodnoty jednotlivých nenulových proměnných: x31 = 3.0 x41 = 7.0 x22 = 8.0 x32 = 7.0 x13 = 7.0 x43 = 4.0 Optimálním řešením tedy je přepravit z prvního skladu 3t třetímu spotřebiteli a 7t čtvrtému spotřebiteli, z druhého skladu přepravit 8t materiálu druhému spotřebiteli a 7t třetímu spotřebiteli a ze třetího skladu přepravit 7t prvnímu spotřebiteli a 4t čtvrtému spotřebiteli. Náklady na přepravu činí 188 jednotek. Obrázkem: 2 Sklad1 (10t) Sklad2 (15t) Sklad3 (11t) Spo1 (7t) Spo2 (8t) Spo3 (10t) Spo4 (11t) 7 7 3 8 7 4 Petr Hliněný, FI MU 7 IA102 "OU": Lineární optimalizace Přirozenou otázkou je, jak jsme k uvedenému číselnému řešení předchozího příkladu dospěli. Takové úlohy s více proměnnými již nelze řešit "pohledem na obrázek" jako Příklad 3.1. Pro řešení úloh LP však existuje poměrně jednoduchá simplexová metoda, která má mnoho i volně dostupných implementací. Malé a vhodně formulované úlohy lineární optimalizace snadno vyřešíme různými aplety a prográmky volně dostupnými na internetu, například [?] http://algos.inesc.pt/lp/. Další možností (zcela nenáročnou na stranu klienta, funguje i na PDA) je využít klientský přístup [?] k aplikaci WLPS řešící LP a IP úlohy. Poznámka: Čtenáře může napadnout, v jakém vztahu jsou celková kapacita skladů a celkové požadavky spotřebitelů. Pokud by celková kapacita skladů byla nižší, řešení by nemohlo exis- tovat. V našem případě je kapacita právě dostatečná, takže každý sklad bude plně využit. To přináší jisté nebezpečí zaokrouhlovacích chyb, které mohou znemožnit nalezení řešení. (Před- stavte si, že vinou zaokrouhlovací chyby se během výpočtů třeba jen velmi málo sníží kapacita jednoho skladu a řešení úlohy tak nebude možné.) Při matematické formulaci praktických úloh je dobré na toto nebezpečí myslet a vyhýbat se "hraničním" formulacím rovností v LP. Petr Hliněný, FI MU 8 IA102 "OU": Lineární optimalizace Příklad 3.3. Armáda pro potřeby cvičení musí ze dvou skladů o kapacitách 6 a 5 tun střeliva přepravit 3, 2 a 2 tuny střeliva na tři její střelnice. Úkolem je, v rámci rozložení rizik, minimalizovat maximální množství střeliva přepravované po jednotlivých cestách od skladů ke střelnicím. Řešení: Podmínky nyní jsou následovné. ˇ Kapacity skladů x11 + x12 + x13 6, x21 + x22 + x23 5. ˇ Požadavky střelnic -- z i-tého skladu dodat j-té množství střeliva x11 + x21 = 3, x12 + x22 = 2, x13 + x23 = 2. ˇ Podmínky nezápornosti xij 0, i = 1, 2, j = 1, 2, 3. Cílem je nyní minimalizovat převážené množství střeliva na každé jedné silnici (aby nedocházelo k příliš vysoké koncentraci střeliva na jednom místě). Pokud podmínku přepíšeme do hodnocení účelové funkce, získáme zápis min ((x) = max{x11, x12, x13, x21, x22, x23}) . Petr Hliněný, FI MU 9 IA102 "OU": Lineární optimalizace Tuto formuli lze následně přidáním dodatečných podmínek upravit na min (x) = z : kde z xij pro i = 1, 2, j = 1, 2, 3 . Optimální hodnota účelové funkce je (x) = 1.5 a hodnoty jednotlivých složek / proměnných jsou: z = 1.5 x11 = 1.5 x12 = 0.5 x13 = 0.5 x21 = 1.5 x22 = 1.5 x23 = 1.5 Optimálním řešením je třeba přepravit z prvního skladu 1.5t k 1. střelnici, 0.5t k 2. střel- nici a 0.5t k 3. střelnici. Z druhé skladiště se přepraví 1.5t k 1. střelnici, 1.5t k 2. střelnici a 1.5t k 3. střelnici. Obrázkem: Sklad2 (5t) Sklad1 (6t) Stř1 (3t) Stř2 (2t) Stř3 (2t) 1.5 1.5 0.5 1.5 0.5 1.5 2Petr Hliněný, FI MU 10 IA102 "OU": Lineární optimalizace 3.3 Obecná úloha LP Nyní přejdeme ke zobecnění matematické formalizace LP. Definice 3.4. Úlohou lineárního programování (zkratkou LP) rozumíme úlohu nalezení vektoru x, který maximalizuje, resp. minimalizuje, skalární součin c x za podmínek A x b, x 0, kde A je daná matice úlohy, b je vektor pravých stran a c je účelový vektor. Náš zkrácený maticový zápis podmínek úlohy A x b, x 0 ve skutečnosti znamená pro A = ai,j m,n i,j=1 soustavu lineárních nerovností a1,1x1 + a1,2x2 + . . . + a1,nxn b1, ... ... am,1x1 + am,2x2 + . . . + am,nxn bm, x1, x2, . . . , xn 0 . Značení: Úlohu LP z Definice ?? zkráceně zapisujeme max c x pro A x b a x 0 . Petr Hliněný, FI MU 11 IA102 "OU": Lineární optimalizace Pro lepší rozlišení také mluvíme o úloze LP v základním tvaru. Všimněme si, že v základním tvaru je každá složka vektoru x nezáporná. Definice: Zobecněnou úlohou LP rozumíme max c (x, y) či min c (x, y) pro A (x, y) b, A (x, y) b, A (x, y) = b, x 0. O složkách vektoru x pak mluvíme jako o omezených proměnných a o složkách vektoru y jako o neomezených proměnných. Definice: Přípustné řešení úlohy LP je vektor (x, y) splňující všechny podmínky (rov- nosti a nerovnosti) úlohy. Petr Hliněný, FI MU 12 IA102 "OU": Lineární optimalizace Převody forem úloh LP Pro co nejširší aplikovatelnost úlohy LP je samozřejmě vhodnější volit její zobecněný tvar, avšak z dobrých matematických důvodů je zase lepší zapisovat úlohy LP v zá- kladním tvaru. Že to neznamená žádné podstatné omezení, ukazuje následující tvrzení. Věta 3.5. Ke každé zobecněné úloze LP existuje ekvivalentní úloha v základním tvaru. Důkaz: Mějme zobecněnou úlohu danou maticemi a vektory A, A , A , b, b, b, c, x, y jako ve výše uvedené definici. Provedeme následující substituce: ˇ Náhrada proměnných y novými nezápornými proměnnými yi - (x i - x i ), x i, x i 0. ˇ Obrácení nerovností z A (x, y) b a j(x, y) b j - - a j(x, y) -b j. ˇ Náhrada rovností dvojicema nerovností a j (x, y) = b j - a j (x, y) b j , -a j (x, y) -b j . Nyní je úloha v základním tvaru. 2 Petr Hliněný, FI MU 13 IA102 "OU": Lineární optimalizace