Számítógép-optimalizálási ötletek
1 Az informatikai optimalizálás ötletei Kurt Mehlhorn 2018. december
2 optimalizálási probléma mindenütt jelen van: Keresse meg a leggyorsabb utat A-ból B-be. Tervezze meg a vállalat útjait. Rendeljen egy sor feladatot a dolgozók egy csoportjához oly módon, hogy a teljes feldolgozási idő a lehető legkisebb legyen (alternatív megoldásként a lehető legkorábbi befejezés). Vezesse a fűrészeket egy fűrészüzemben úgy, hogy a lehető legértékesebb termékeket állítsa elő. Vezessen egy cirkáló rakétát úgy, hogy annak teljes repülési távolsága ne lépje túl és minimalizálja annak a valószínűségét, hogy lelőtték. Tegyen tárgyakat egy tartályba. A KM 2/21 optimalizálása
3 További optimalizálási problémák Optimalizálja a szövetségi vasút, a Saarbrücken buszok menetrendjét. Találjon megfelelő menetrendet az UDS számára. Keresse meg a sportstadion kiürítési tervét. Számolja ki a legolcsóbb táplálkozási tervet (étrend). Telefonszolgáltató esetében számolja ki, hol helyezze el a mobiltelefon árbocait. A cél a lehető legnagyobb lefedettség elérése alacsony költségek mellett. A KM 3/21 optimalizálása
4 Eljárás Fogalmazza meg a problémát, és hozzon létre egy matematikai modellt. A modellprobléma megoldása. A megoldás visszafordítása a való világba és a megoldás megkérdőjelezése. Hasznos a megoldás a való világban, vagy modellezési gyengeségre utal? A második esetben a modell fejlesztése. Figyelem: A modell mindig csak a valóság egy részét ragadja meg. Még egy modell alapos megalkotása során is megtörténhet, hogy a valóság lényegi szempontjai kimaradnak. Tehát a harmadik lépés elengedhetetlen. Az optimalizálási probléma megoldása gyakran jelzi a modell gyengeségeit. A KM 4/21 optimalizálása
5 Figyelmeztető példa (a későbbiekben még több lesz) A Bundesbahn-menetrend modellfeltevése: legalább öt perc átadási idő. Az optimális menetrend csak a legkisebb átadási időt tervezi meg sok kapcsolat esetén. A megoldás használata/ellenőrzése során azt tapasztalja, hogy a legkisebb késések is teljesen elrontják a megoldást. Ennek eredményeként megnő egy átadási idő, vagy fontolóra vehetjük, hogyan lehet modellezni az ütemterv robusztusságát a megszakításokkal szemben (sztochasztikus optimalizálás). A KM 5/21 optimalizálása
6 Optimális táplálkozási tervek George Stigler a következő optimalizálási feladatot fogalmazta meg 1945-ben: Mennyibe kerül az összes alapvető igényt kielégítő étrend? George J. Stigler: A megélhetés költségei. Journal of Farm Economics, 27. cikk (2): „Félig szórakoztatónak, félig komolynak gondolta a feladatot. Félig szórakoztató, mert akkor is sok könyv és cikk volt a kiegyensúlyozott és olcsó táplálkozásról, félig komoly, mert az amerikai államnak több százezer katonát kellett etetnie. George Joseph Stigler () amerikai közgazdász volt. 1982-ben közgazdasági Nobel-díjat kapott. Megtiszteltetés volt az ipari szervezéssel, a piacok működésével és a piaci szabályozás okaival és következményeivel kapcsolatos munkájáért. A KM 6/21 optimalizálása
7 Modellezés: Mi az a megfelelő táplálkozás? Első válasz: Olyan étrend, amely megfelel a Nemzeti Kutatási Tanács 9 nélkülözhetetlen tápanyagra vonatkozó ajánlásának. Tápanyag kalóriák Fehérje Kalcium Vas A-vitamin Tiamin (B1-vitamin) Riboflavin (B2-vitamin) Niacin-aszkorbinsav (C-vitamin) Napi ajánlott bevitel 3000 kalória 70 gramm. 8 gramm 12 milligramm 5000 NE 1,8 milligramm 2,7 milligramm 18 milligramm 75 milligramm hogy ezek az ajánlások valószínűleg hiányosak és pontatlanok. Ma: a zsír felső korlátja a menüben, alacsonyabb kalóriaszám, a KM 7/21 optimalizálása
8 Foods Stigler megvizsgálja a 77 ételt, amelyeket a Munkaügyi Statisztikai Hivatal rendszeresen áraz. Minden ételhez az irodalomból veszi a különféle tápanyagok tartalmát. Kifejezetten rámutat, hogy ezeket az adatokat óvatosan kell kezelni, mivel bizonyos típusú készítmények vagy hosszú tárolás tönkretesz bizonyos tápanyagokat, és mivel a táblázat csak az átlagértékeket tartalmazza. Például egy Ontario-alma tízszer annyi C-vitamint tartalmaz, mint egy McIntosh-alma. A feladat formalizálása: Mennyit kell vásárolni az egyes élelmiszerekből, hogy a menü követelményei teljesüljenek és a költségek minimálisak legyenek? A KM 8/21 optimalizálása
9 matematikai modell xi = az i-edik étel (NM) mennyisége (kg-ban) az optimális menüben, i = feltételek (egy összetevőnként egy): a tervnek elegendő mennyiségben kell tartalmaznia az összetevőket, például kalóriák esetében: kalória/kg NM 1 x kalória/kg NM 77 x a táplálkozási terv költségei ekkor költségek = NM/ár/kg 1 x ár/kg NM 77 x 77. Feladat: keressen nem negatív értékeket az ismeretlenekre x 1 - x 77, mindegyikre A korlátok teljesítése és a költségek minimalizálása. A KM 9/21 optimalizálása
10 A feladat megoldása: 1. lépés, egyszerűsítés Stigler nem tudott algoritmust az egyenlőtlenségi rendszerek megoldására. Nagyon okosan meghatározta a hozzávetőleges megoldást. Dominancia: Ha A olcsóbb, mint B, de legalább annyi minden összetevõt tartalmaz, mint B, akkor a B törölhetõ az optimális megoldás elvesztése nélkül. Redukció 15 NM-ra. A liszt uralja a kenyeret, a marhamáj az összes többi húst, az összes szabadalmaztatott gabona és ital dominál. Mesterséges táplálék, körülbelül 5 kg liszt és 2 kg gyógynövény: Ha egy mesterséges NM uralja a valódi NM-t, akkor a valódi törölhető. Csökkentés 9 NM-re. A KM 10/21 optimalizálása
11 2. lépés: Megoldás Most 9 egyenlőtlenséget kell teljesíteni 9 változóban (obda, x 1 és x 9 között). Minimális költségmegoldást szeretne. Az optimális megoldásnak ki kell elégítenie az egyenlőtlenségek egy részét az egyenlőséggel, mivel. = 511 nem üres részhalmaza van az egyenlőtlenségeknek. Stiglitz csak néhány részhalmazt vesz figyelembe (intuíció). Egy rögzített S részhalmaz esetében megoldja az eredményül kapott egyenletrendszert, és most leírása homályossá válik. Ezután előáll egy megoldással, amelynek éves költsége dollár (kb. 510 USD a mai pénzből). A KM 11/21 optimalizálása
12 Eredmény Ezután előáll egy megoldással, amelynek éves költsége dollár (kb. 510 dollár a mai pénzzel). Élelmiszer Éves mennyiségek Éves költség (dollárban) Búzaliszt 370 lb Párolt tej 57 doboz 3,84 Káposzta 111 lb Spenót 23 lb Szárított tengeri bab 285 lb Az éves összköltség optimális? Stigler szerint (nem teljesen világos) egy alsó határ: A liszt a legolcsóbb kalóriaforrás: a 24,50 dolláros liszt 3000 kalóriát tartalmaz. De alig van kalcium. A legolcsóbb kalciumforrás a sajt. Ezután adjon hozzá további 14,90 dollárt. Dantzig a 47-ben feltalálja a megoldási algoritmust (szimplex algoritmus). Egy 9 emberből álló számítógépes csapat 120 embernap alatt kiszámítja az optimális megoldást: A legolcsóbb menü dollárba kerül. Stigler megoldása csak 24 centtel volt magasabb. A KM 12/21 optimalizálása
13 Mit tudunk most? algoritmikus: az egyenlőtlenségek rendszerének optimális megoldását megtalálni nem könnyű. Dantzig megoldási algoritmust talál ki az alábbiakban. Modellezés: a probléma matematikai elérése érdekes, de a modellezés nem megfelelő: senki sem akar így enni. Modellezheti a változatosságot? Erre az előadás végén visszatérünk. A KM 13/21 optimalizálása
14 A lineáris optimalizálás algoritmusai Lineáris optimalizálás = egy lineáris függvény maximalizálása (minimalizálása) n valós változóban korlátozások alatt (a kényszerek egyenletek és egyenlőtlenségek). Példa: étkezési terv készítése és még sok-sok más probléma. Fourier-Motzkin: egyszerű, de nem hatékony. Joseph Fourier (), Theodore Motzkin (), 1936-ban végzett munka Simplex algoritmus (Georg Dantzig, 1947): még mindig a legszélesebb körben használt algoritmus; gyakran nagyon gyorsan, de a legrosszabb esetben exponenciálisan. Leonid Khachiyan, Ellipsoid Method és N. Karmakar, Inner Point Method algoritmusokat fejlesztettek ki polinomi futási idővel. Gyakran alkalmazzák a belső pont módszerét. Rendszerek: CPLEX, Gurobi, SoPlex. A KM 14/21 optimalizálása
15 A szimplex algoritmus maximalizálja y-t ahol 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) egyenlőtlenségek határoznak meg egy sokszöget P (szürke terület). A maximális y-koordinátájú sarkot keressük. A 2x + 7y = 28 és 4x 2y = 20 egyenesek metszéspontjának koordinátái vannak (49 8, 9 4). Így az optimális érték y = 9 4. Az algoritmus ötlete: keressen egy P p sarkot, és vegye figyelembe a P beeső széleit. Ha egyik sem vezet az objektív függvény magasabb értékéhez, akkor a sarok optimális. Ha az egyik él jobb értékhez vezet, sétáljon az él másik végébe, és ismételje meg. 3 sötét a következő dioptimáláson, KM 15/21
16 Simplex 3D-ben (kép a Wikipedia-ból) A z koordináta maximalizálása Optimalizálás KM 16/21
17 Fourier Motzkin annak eldöntésére, hogy megoldható-e Fourier Motzkin dönt arról, hogy az egyenlőtlenségek rendszere megoldható-e. Oldja meg az összes változó összes egyenlőtlenségét, például az x változó esetén. Az egyenlőtlenségeknek három típusa van: (1) x. (2) x. és (3) nem említi az x-et. Készítsen új rendszert az x: take (3) változatlan eltüntetésével. Az (1) és (2) x A és x B mindegyik párjából konstruáljuk a B A.-t. Addig iterálunk, amíg az összes változó ki nem eliminálódik. Akkor sok egyenlőtlenség van a számok között. Trivial dönteni. Illusztrálja a példával: lásd a következő diát Az optimalizálás kiterjesztése: bináris keresés optimalizálása KM 17/21
18 Fourier Motzkin-példa maximalizálja az y-t, ahol 2x + 7y 28 4x 2y 20 x + y 6 y 0-nak van 9-es megoldása. 4. A Fourier-Motzkin-t használjuk annak eldöntésére, hogy létezik-e 3-as értékű megoldás. A KM 18/21 optimalizálása
19 A rossz modellezés és/vagy adatok veszélyei Az optimalizálás eredménye soha nem lehet jobb, mint a modell és az adatok. (George B. Dantzig, A diétás probléma. Interfaces, 20 (4): 43 47, 1990.) Dantzignak fogynia kell: napi 1500 kalória. Félt az éhségtől, ezért maximalizálni akarta a jóllakottság érzését. Kiválasztotta a nem vízmennyiség = (1 víztartalom 1kg NM1) függvényt x miért pont ez a célfüggvény? Arra gondolt, hogy bár a víz megtölti a gyomrot, ettől nem érzi jól magát. Ezért akart annyit enni, ami csak nem víz volt. A KM optimalizálása 19/21
20 A rossz modellezés és/vagy adatok veszélyei Az optimalizálás eredménye soha nem lehet jobb, mint a modell és az adatok. (George B. Dantzig, A diétás probléma. Interfaces, 20 (4): 43 47, 1990.) Dantzignak fogynia kell: napi 1500 kalória. Félt az éhségtől, ezért maximalizálni akarta a jóllakottság érzését. A nem vízmennyiség = (1 víztartalom 1 kg NM1) x oldat 1: 500 liter ecet naponta célfüggvényt választotta. Miért? Az adatok szerint az ecet alacsony kalóriatartalmú és nem tartalmaz vizet. Dantzig ecetet terített. 2. megoldás: 200 alapkocka. Kipróbált egy levest 4 alapkockával; teljesen sós. Három alapkocka felső határa. 3. megoldás: napi 2 font korpa. A felesége megtiltotta neki, hogy ennyi korpát fogyasszon. A korpa felső határa. 4. megoldás: 2 font melasz 5. megoldás: Végül túl színes lett a felesége számára, és ő vette át a rendszert. Dantzig 22 kilót fogyott. A KM optimalizálása 19/21
21 Menüterv, változatosság modellezése Az ételeket a menü alkotóelemeként vesszük figyelembe. x i = azoknak a napoknak a száma, amikor az i-t tálaljuk. További korlátozások: x x n = 365, x i 26, i tésztaételek x i 52, i halételek 52. Minden más, mint korábban. Probléma: mit jelent a 3,37-szeres spagetti? Menü egy évre, legfeljebb kéthetente. 1. megoldás: x i egész szám további korlátozásként: Az egész szám optimalizálása azonban sokkal nehezebb. 2. megoldás: keresse meg az optimális valós megoldást. A számok fel/le kerekítése a következő egész számra. A KM 20/21 optimalizálása
22 Menüterv, változatosság modellezése Az ételeket a menü alkotóelemeként vesszük figyelembe. x i = azoknak a napoknak a száma, amikor az i ételt tálaljuk. További korlátozások: x x n = 365, x i 26, i tésztaételek x i 52, i halételek 52. Minden más, mint korábban. Probléma: mit jelent a 3,37-szeres spagetti? Menü egy évre, legfeljebb kéthetente. 1. megoldás: x i egész szám további korlátozásként: Az egész szám optimalizálása azonban sokkal nehezebb. 2. megoldás: keresse meg az optimális valós megoldást. A számok fel/le kerekítése a következő egész számra. A KM 20/21 optimalizálása
23 Összefoglalás A lineáris optimalizálás (= egy lineáris függvény maximalizálása (minimalizálása) n változóban korlátok alatt (a kényszerek egyenletek és egyenlőtlenségek)) nagyon kifejező és hatékonyan megoldható. Az egész lineáris optimalizálás (csak az egész megoldások érdekelnek) sokkal kifejezőbb, de nehezebben megoldható. Az eredmény soha nem jobb, mint a modell és az adatok. Ez vonatkozik a szimulációra is. Klímaszimulációs stresszteszt a bankok optimalizálásánál KM 21/21
24 Összefoglalás A lineáris optimalizálás (= egy lineáris függvény maximalizálása (minimalizálása) n változóban korlátok alatt (a kényszerek egyenletek és egyenlőtlenségek)) nagyon kifejező és hatékonyan megoldható. Az egész lineáris optimalizálás (csak az egész megoldások érdekelnek) sokkal kifejezőbb, de nehezebben megoldható. Az eredmény soha nem jobb, mint a modell és az adatok. Ez vonatkozik a szimulációra is. Klímaszimulációs stresszteszt a bankok optimalizálásánál KM 21/21