Nápady na počítačovú optimalizáciu
1 Nápady optimalizácie IT Kurt Mehlhorn december 2018
2 problémy s optimalizáciou sú všadeprítomné: Nájdite najrýchlejšiu cestu z bodu A do bodu B. Naplánujte si výlety spoločnosti. Priraďte množinu úloh množine pracovníkov tak, aby sa minimalizoval celkový čas spracovania (alternatívne dokončenie čo najskôr). Ovládajte píly na píle tak, aby sa vyrábali najcennejšie možné produkty. Ovládajte riadenú strelu tak, aby nebola prekročená jej celková letová vzdialenosť a aby bola minimalizovaná pravdepodobnosť zostrelenia. Vložte predmety do nádoby. Optimalizácia KM 2/21
3 Ďalšie problémy s optimalizáciou Optimalizujte cestovný poriadok federálnej železnice, autobusov Saarbrücken. Nájdite dobrý harmonogram UdS. Nájdite evakuačný plán pre športový štadión. Vypočítajte najlacnejší výživový plán (diéta). Pre telefónnu spoločnosť vypočítajte, kam umiestniť stožiare mobilných telefónov. Cieľom je dosiahnuť čo najväčšie pokrytie pri nízkych nákladoch. Optimalizácia KM 3/21
4 Postup Sformulujte problém a vytvorte matematický model. Riešenie modelového problému. Preložiť riešenie späť do reálneho sveta a spochybniť riešenie. Je riešenie užitočné v reálnom svete alebo naznačuje slabinu modelovania? V druhom prípade vylepšenie modelu. Upozornenie: Model vždy zachytáva iba časť reality. Aj pri starostlivom vytváraní modelu sa môže stať, že budú vynechané základné aspekty reality. Tretí krok je teda nevyhnutný. Riešenie optimalizačného problému často naznačuje slabé stránky modelu. Optimalizácia KM 4/21
5 Varovný príklad (ďalšie prídu neskôr) Predpoklad modelu pre cestovný poriadok Bundesbahn: čas prestupu minimálne päť minút. Optimálny cestovný poriadok naplánuje iba minimálny čas prestupu pre mnoho spojov. Pri používaní/kontrole riešenia zistíte, že aj najmenšie oneskorenia môžu úplne pokaziť riešenie. V dôsledku toho sa zvýšia niektoré prestupové časy alebo sa zváži, ako možno modelovať robustnosť cestovného poriadku proti prerušeniam (stochastická optimalizácia). Optimalizácia KM 5/21
6 Plány optimálnej výživy George Stigler sformuloval v roku 1945 túto optimalizačnú úlohu: Koľko stojí strava, ktorá spĺňa všetky základné potreby? George J. Stigler: Náklady na živobytie. Journal of Farm Economics, 27 (2): „Myslel to na úlohu napoly zábavnú, napoly vážnu. Polovičná zábava, pretože v tom čase už bolo veľa kníh a článkov o vyváženej a lacnej strave, polozávažná preto, lebo americký štát musel kŕmiť státisíce vojakov. George Joseph Stigler () bol americký ekonóm. V roku 1982 získal Nobelovu cenu za ekonómiu. Bol ocenený za prácu v oblasti priemyselnej organizácie, fungovania trhov a príčin a dôsledkov regulácie trhu. Optimalizácia KM 6/21
7 Modelovanie: Čo je to adekvátna výživa? Prvá odpoveď: Strava, ktorá spĺňa odporúčania Národnej rady pre výskum týkajúce sa 9 základných živín. Výživové kalórie Bielkoviny Vápnik Železo Vitamín A Tiamín (vitamín B1) Riboflavín (vitamín B2) Niacín Kyselina askorbová (vitamín C) Denný odporúčaný príjem 3 000 kalórií 70 gramov. 8 gramov 12 miligramov 5 000 IU 1,8 miligramov 2,7 miligramov 18 miligramov 75 miligramov. Poukazuje na to že tieto odporúčania budú pravdepodobne neúplné a nepresné. Dnes: tiež horná hranica tukov v menu, nižší počet kalórií, optimalizácia KM 7/21
8 Foods Stigler sa zameriava na 77 potravín, ktoré Úrad pre štatistiku práce pravidelne oceňuje. Pre každú potravinu berie obsah rôznych výživných látok z literatúry. Výslovne poukazuje na to, že s týmito údajmi je potrebné zaobchádzať opatrne, pretože určité druhy prípravkov alebo dlhodobé skladovanie ničia určité živiny a keďže tabuľka obsahuje iba priemerné hodnoty. Napríklad jablko Ontario obsahuje desaťkrát viac vitamínu C ako jablko McIntosh. Formalizácia úlohy: Koľko by si mal človek kúpiť za každú potravinu, aby boli splnené požiadavky na jedálniček a náklady boli minimálne? Optimalizácia KM 8/21
9 Matematický model xi = množstvo (v kg) i-tej potraviny (NM) v optimálnom menu, i = podmienky (jedna pre každú zložku): plán musí obsahovať prísady v dostatočnom množstve, napr. Pre kalórie: kalórie/kg NM 1 x kalórie/kg NM 77 x náklady na výživový plán sú potom náklady = cena/kg NM 1 x cena/kg NM 77 x 77. Úloha: nájdite nezáporné hodnoty pre neznáme x 1 až x 77, všetky Splňte obmedzenia a minimalizujte náklady. Optimalizácia KM 9/21
10 Riešenie úlohy: Krok 1, zjednodušenie Stigler nepoznal žiadny algoritmus na riešenie systémov nerovností. Veľmi šikovným spôsobom určil približné riešenie. Dominancia: Ak je A lacnejšie ako B, ale obsahuje minimálne toľko každej zložky ako B, potom je možné B vypustiť bez straty optimálneho riešenia. Zníženie na 15 NM. Múka dominuje chlebu, hovädzia pečeň dominuje všetkým ostatným druhom mäsa, dominujú všetky patentované obilniny a nápoje. Umelé jedlo, asi 5 kíl múky a 2 kilá byliny: Ak umelé NM dominuje nad skutočným NM, je možné ho vymazať. Zníženie na 9 NM. Optimalizácia KM 10/21
11 Krok 2: Riešenie Teraz treba splniť 9 nerovností v 9 premenných (obda, x 1 až x 9). Chcete riešenie s minimálnymi nákladmi. Optimálne riešenie musí uspokojiť niektoré nerovnosti rovnosťou. Existuje = 511 neprázdnych podmnožín nerovností. Stiglitz berie do úvahy iba niekoľko podskupín (intuícia). Pre pevnú podmnožinu S rieši výsledný systém rovníc a jeho popis je teraz nejasný. Potom prichádza s riešením s ročnými nákladmi na doláre (asi 510 dolárov s dnešnými peniazmi). Optimalizácia KM 11/21
12 Výsledok Potom príde s riešením s ročnými nákladmi na doláre (asi 510 dolárov s dnešnými peniazmi). Jedlo Ročné množstvá Ročné náklady (v dolároch) Pšeničná múka 370 lb Odparené mlieko 57 plechoviek 3,84 Kapusta 111 lb Špenát 23 lb Sušené námornícke fazule 285 lb Celkové ročné náklady Je to optimálne? Stigler tvrdí (nie je to úplne jasné) dolná hranica: Múka je najlacnejším zdrojom kalórií: múka za 24,50 dolárov má 3 000 kalórií. Ale sotva nejaký vápnik. Najlacnejším zdrojom vápnika je syr. Potom pridajte ďalších 14,90 dolárov. Dantzig vynašiel algoritmus riešenia (simplexný algoritmus) v 47. Tím 9 ľudských počítačov vypočíta optimálne riešenie za 120 človekodní: Najlacnejšie menu stojí doláre. Stiglerovo riešenie bolo iba o 24 centov vyššie. Optimalizácia KM 12/21
13 Čo teraz vieme? algoritmické: nájsť optimálne riešenie systému nerovností nie je ľahké. Dantzig vynašiel algoritmus riešenia v časti Pozri nižšie. Modelovanie: pokus o získanie matematického problému je zaujímavý, ale modelovanie je nedostatočné: nikto nechce jesť tak. Môžete modelovať rozmanitosť? K tomu sa ešte vrátime na konci prednášky. Optimalizácia KM 13/21
14 Algoritmy pre lineárnu optimalizáciu Lineárna optimalizácia = maximalizácia (minimalizácia) lineárnej funkcie v n reálnych premenných pod obmedzeniami (obmedzeniami sú rovnice a nerovnosti). Príklad: tvorba stravovacieho plánu a mnoho ďalších problémov. Fourier-Motzkin: jednoduchý, ale neefektívny. Joseph Fourier (), Theodore Motzkin (), práce z roku 1936 Algoritmus Simplex (Georg Dantzig, 1947): stále najpoužívanejší algoritmus; často veľmi rýchlo, ale v horšom prípade exponenciálne. Leonid Khachiyan, elipsoidná metóda a N. Karmakar, metóda vnútorného bodu, vyvinuli algoritmy s polynomickým časom behu. Často sa používa metóda vnútorného bodu. Systémy: CPLEX, Gurobi, SoPlex. Optimalizácia KM 14/21
15 simplexný algoritmus maximalizuje y, kde 2x + 7y 28 4x 2y 20 x + y 6 y 0 x + y = 6 (6,0) 4x 2y = 20 2x + 7y = 28 y = 0 (14,0) nerovnosti definujú polygón P (šedá oblasť). Hľadáme roh s maximálnou súradnicou y. Priesečník priamok 2x + 7y = 28 a 4x 2y = 20 má súradnice (49 8, 9 4). Optimálna hodnota y = 9. 4. Idea algoritmu: nájdite roh p bodu P a zvážte hrany dopadu P. Ak žiadny z nich nevedie k vyššej hodnote objektívnej funkcie, je roh optimálny. Ak jeden okraj vedie k lepšej hodnote, choďte na druhý koniec okraja a opakujte. 3 stlmenia na ďalšej optimalizácii snímky KM 15/21
16 Simplex v 3D (obrázok z Wikipédie) Maximalizácia súradnice z Optimalizácia KM 16/21
17 Fourier Motzkin rozhodne, či je to riešiteľné Fourier Motzkin rozhodne, či je systém nerovností riešiteľný. Vyriešte všetky nerovnosti pre jednu z premenných, povedzme pre premennú x. Existujú tri typy nerovností: (1) x. (2) x. a (3) neuvádzajte x. Vytvorte nový systém odstránením x: take (3) bez zmeny. Z každého páru x A a x B z (1) a (2) zostrojte B A. Iterujte, kým nebudú vylúčené všetky premenné. Potom máte veľa nerovností medzi číslami. Triviálne rozhodnúť. Ilustrujte na príklade: pozri ďalšiu snímku Rozšírenie k optimalizácii: optimalizácia binárneho vyhľadávania KM 17/21
18 Fourierov Motzkinov príklad maximalizovať y, kde 2x + 7y 28 4x 2y 20 x + y 6 y 0 má riešenie 9 4. Na určenie, či existuje riešenie s hodnotou 3, použijeme Fourier-Motzkin. Optimalizácia KM 18/21
19 Nebezpečenstvo zlého modelovania a/alebo údajov Výsledok optimalizácie nikdy nemôže byť lepší ako model a údaje. (George B. Dantzig, Problém s diétou. Interfaces, 20 (4): 43 47, 1990.) Dantzig by mal schudnúť: 1 500 kalórií denne. Bál sa pocitu hladu, a preto chcel maximalizovať pocit sýtosti. Zvolil cieľovú funkciu nevodné množstvo = (1 obsah vody v 1 kg NM1) x prečo táto cieľová funkcia? Prišiel na to, že zatiaľ čo voda napĺňa žalúdok, neznamená to, že sa cítite plní. Preto chcel jesť čo najviac, čo nebola voda. Optimalizácia KM 19/21
20 Nebezpečenstvo zlého modelovania a/alebo údajov Výsledok optimalizácie nikdy nemôže byť lepší ako model a údaje. (George B. Dantzig, Problém s diétou. Interfaces, 20 (4): 43 47, 1990.) Dantzig by mal schudnúť: 1 500 kalórií denne. Bál sa pocitu hladu, a preto chcel maximalizovať pocit sýtosti. Zvolil objektívnu funkciu nevodné množstvo = (1 obsah vody v 1 kg NM1) x roztok 1: 500 galónov octu denne. Prečo? Údaje uvádzali, že ocot bol nízkokalorický a neobsahoval vodu. Dantzigský natieraný ocot. Riešenie 2: 200 zásobných kociek. Vyskúšal polievku so 4 zásobnými kockami; úplne slaný. Horná hranica troch základných kociek. Riešenie 3: 2 libry otrúb denne. Jeho žena mu zakázala jesť toľko otrúb. Horná hranica pre otruby. Riešenie 4: 2 libry melasy Riešenie 5: Nakoniec to pre jeho manželku začalo byť príliš farebné a ona prevzala režim. Dantzig schudol na 22 kíl. Optimalizácia KM 19/21
21 Plán jedálnička, modelovanie rozmanitosti Jedlá prijímame ako súčasť menu. x i = počet dní, počas ktorých podávame jedlo i. Dodatočné obmedzenia: x x n = 365, x i 26, i cestovinové jedlá x i 52, i rybie jedlá 52. Všetko ostatné ako predtým. Problém: čo znamená 3,37-krát špagety? Stravovací plán na rok, maximálne raz za dva týždne Alternatívne riešenie 1: celé číslo x i ako ďalšia sekundárna podmienka: Optimalizácia celého čísla je však oveľa ťažšia. Riešenie 2: Nájdite optimálne skutočné riešenie. Zaokrúhľujte čísla hore/dole na ďalšie celé číslo. Optimalizácia KM 20/21
22 Plán jedálnička, modelovanie rozmanitosti Jedlá prijímame ako súčasť menu. x i = počet dní, počas ktorých podávame jedlo i. Dodatočné obmedzenia: x x n = 365, x i 26, i cestovinové jedlá x i 52, i rybie jedlá 52. Všetko ostatné ako predtým. Problém: čo znamená 3,37-krát špagety? Stravovací plán na rok, maximálne raz za dva týždne Alternatívne riešenie 1: celé číslo x i ako ďalšia sekundárna podmienka: Optimalizácia celého čísla je však oveľa ťažšia. Riešenie 2: Nájdite optimálne skutočné riešenie. Zaokrúhľujte čísla hore/dole na ďalšie celé číslo. Optimalizácia KM 20/21
23 Zhrnutie Lineárna optimalizácia (= maximalizácia (minimalizácia) lineárnej funkcie v n premenných pod obmedzeniami (obmedzeniami sú rovnice a nerovnosti)) je veľmi expresívna a dá sa efektívne vyriešiť. Celočíselná lineárna optimalizácia (zaujímajú vás iba celočíselné riešenia) je oveľa expresívnejšia, ale náročnejšia na riešenie. Výsledok nikdy nie je lepší ako model a údaje. To platí aj pre simuláciu. Stresový test klimatickej simulácie pri optimalizácii bánk KM 21/21
24 Zhrnutie Lineárna optimalizácia (= maximalizácia (minimalizácia) lineárnej funkcie v n premenných pod obmedzeniami (obmedzeniami sú rovnice a nerovnosti)) je veľmi expresívna a dá sa efektívne vyriešiť. Celočíselná lineárna optimalizácia (zaujímajú vás iba celočíselné riešenia) je oveľa expresívnejšia, ale náročnejšia na riešenie. Výsledok nikdy nie je lepší ako model a údaje. To platí aj pre simuláciu. Stresový test klimatickej simulácie pri optimalizácii bánk KM 21/21