Idei de optimizare computer
1 Idei de optimizare IT Kurt Mehlhorn decembrie 2018
2 probleme de optimizare sunt omniprezente: găsiți cea mai rapidă rută de la A la B. Planificați călătoriile unei companii. Alocați un set de sarcini unui set de lucrători în așa fel încât timpul total de procesare să fie minimizat (alternativ, finalizarea cât mai devreme posibil). Controlați ferăstrăul într-o ferăstrău astfel încât să fie produse cele mai valoroase produse. Controlați o rachetă de croazieră în așa fel încât distanța totală de zbor să nu fie depășită și probabilitatea de a fi doborâtă să fie minimizată. Puneți obiecte într-un container. Optimizarea KM 2/21
3 Alte probleme de optimizare Optimizați orarul căii ferate federale, autobuzele Saarbrücken. Găsiți un orar bun pentru UdS. Găsiți planul de evacuare pentru un stadion sportiv. Calculați cel mai ieftin plan nutrițional (dieta). Pentru o companie de telefonie, calculați unde să amplasați catargele telefonului mobil. Scopul este de a realiza cea mai mare acoperire posibilă la costuri mici. Optimizarea KM 3/21
4 Procedură Formulați problema și creați un model matematic. Rezolvarea problemei modelului. Traducerea soluției înapoi în lumea reală și punerea la îndoială a soluției. Este soluția utilă în lumea reală sau indică o slăbiciune de modelare? În al doilea caz, îmbunătățirea modelului. Atenție: un model surprinde doar o parte din realitate. Chiar și atunci când creați cu atenție un model, se poate întâmpla ca aspectele esențiale ale realității să fie lăsate în afara. Așadar, al treilea pas este esențial. Soluția la o problemă de optimizare indică adesea puncte slabe ale modelului. Optimizarea KM 4/21
5 Un exemplu de avertisment (mai multe vor veni mai târziu) Ipoteză model pentru orarul Bundesbahn: timpul de transfer de cel puțin cinci minute. Un orar optim va planifica timpul minim de transfer pentru multe conexiuni. Când utilizați/inspectați soluția, observați că chiar și cele mai mici întârzieri pot distruge complet soluția. În consecință, se vor crește unii timpi de transfer sau se va lua în considerare modul în care se poate modela robustețea unui calendar împotriva întreruperilor (optimizare stocastică). Optimizarea KM 5/21
6 Planuri optime de nutriție În 1945, George Stigler a formulat următoarea sarcină de optimizare: Cât costă o dietă care satisface toate nevoile de bază? George J. Stigler: Costul subzistenței. Journal of Farm Economics, 27 (2): „A vrut să spună sarcina pe jumătate distractivă, pe jumătate serioasă. Pe jumătate distractiv pentru că pe atunci existau deja multe cărți și articole despre nutriție echilibrată și necostisitoare, pe jumătate serioase pentru că statul american avea de hrănit sute de mii de soldați. George Joseph Stigler () a fost un economist american. În 1982 a primit Premiul Nobel în Economie. A fost onorat pentru munca sa privind organizarea industrială, funcționarea piețelor și cauzele și consecințele reglementării pieței. Optimizarea KM 6/21
7 Modelare: Ce este nutriția adecvată? Primul răspuns: O dietă care îndeplinește recomandările Consiliului Național de Cercetare pentru 9 substanțe nutritive esențiale. Calorii nutrienți Proteine Calciu Fier Vitamina A Tiamina (Vitamina B1) Riboflavina (Vitamina B2) Niacina Acid ascorbic (Vitamina C) Aport zilnic recomandat 3.000 Calorii 70 grame 8 grame 12 miligrame 5.000 UI 1,8 miligrame 2,7 miligrame 18 miligrame 75 miligrame El subliniază că este recomandabil ca aceste recomandări să fie incomplete și inexacte. Astăzi: de asemenea, limita superioară pentru grăsimi în meniu, număr mai mic de calorii, optimizarea KM 7/21
8 Foods Stigler analizează cele 77 de alimente care sunt evaluate în mod regulat de Biroul de Statistică al Muncii. Pentru fiecare aliment, el preia conținutul diferiților nutrienți din literatură. El subliniază în mod expres că aceste cifre ar trebui tratate cu prudență, deoarece anumite tipuri de preparare sau depozitare îndelungată distrug anumite substanțe nutritive și întrucât tabelul conține doar valori medii. De exemplu, un măr Ontario conține de 10 ori mai multă vitamină C decât un măr McIntosh. Formalizarea sarcinii: Cât ar trebui să cumpere cineva din fiecare produs alimentar, astfel încât să fie îndeplinite cerințele pentru meniu și costurile minime? Optimizarea KM 8/21
9 Modelul matematic xi = cantitatea (în kg) din al i-lea aliment (NM) din meniul optim, i = condiții (una pentru fiecare ingredient): planul trebuie să furnizeze ingrediente în cantități suficiente, de ex. Pentru calorii: calorii/kg de NM 1 x calorii/kg NM 77 x costurile planului nutrițional sunt apoi costuri = preț/kg NM 1 x preț/kg NM 77 x 77. Sarcină: găsiți valori non-negative pentru necunoscute x 1 până la x 77, toate Respectați constrângerile și reduceți costurile. Optimizarea KM 9/21
10 Soluția sarcinii: Pasul 1, simplificare Stigler nu cunoștea niciun algoritm pentru rezolvarea sistemelor de inegalități. El a stabilit o soluție aproximativă într-un mod foarte inteligent. Dominanță: dacă A este mai ieftin decât B, dar conține cel puțin la fel de mult din fiecare ingredient ca B, atunci B poate fi șters fără a pierde o soluție optimă. Reducere la 15 NM. Făina domină pâinea, ficatul de vită domină toate celelalte tipuri de carne, toate cerealele și băuturile brevetate sunt dominate. Mâncare artificială, aproximativ 5 kilograme de făină plus 2 kilograme de ierburi: Dacă un NM artificial domină un NM real, cel real poate fi șters. Reducere la 9 NM. Optimizarea KM 10/21
11 Pasul 2: Soluție Acum 9 inegalități care trebuie îndeplinite în 9 variabile (obda, x 1 până la x 9). Vrei o soluție de cost minim. Soluția optimă trebuie să satisfacă unele dintre inegalități cu egalitatea, deoarece. Există = 511 subseturi ne-goale ale inegalităților. Stiglitz ia în considerare doar câteva subseturi (intuiție). Pentru un subset fix S rezolvă sistemul de ecuații rezultat și acum descrierea sa devine vagă. Apoi vine cu o soluție cu un cost anual de dolari (aproximativ 510 USD cu banii de astăzi). Optimizarea KM 11/21
12 Rezultat Apoi vine cu o soluție cu costuri anuale de dolari (aproximativ 510 dolari cu banii de astăzi). Alimente Cantități anuale Cost anual (în dolari) Făină de grâu 370 lb Lapte evaporat 57 cutii 3,84 Varză 111 lb Spanac 23 lb Fasole marine uscate 285 lb Costul anual total Este optim? Stigler susține (nu este complet curat) o limită inferioară: făina este cea mai ieftină sursă de calorii: făina pentru 24,50 dolari are 3000 de calorii. Dar abia calciu. Cea mai ieftină sursă de calciu este brânza. Apoi adăugați încă 14,90 USD. Dantzig inventează algoritmul soluției (algoritmul simplex) în 47. O echipă de 9 calculatoare umane calculează soluția optimă în 120 de zile-om: Cel mai ieftin meniu costă dolari. Soluția lui Stigler a fost cu doar 24 de cenți mai mare. Optimizarea KM 12/21
13 Ce știm acum? algoritmic: găsirea soluției optime la un sistem de inegalități nu este ușoară. Dantzig inventează algoritmul soluției în Vezi mai jos. Modelare: încercarea de a obține problema matematică este interesantă, dar modelarea este inadecvată: nimeni nu vrea să mănânce așa. Poți să modelezi varietate? Vom reveni la acest lucru la sfârșitul prelegerii. Optimizarea KM 13/21
14 Algoritmi pentru optimizarea liniară Optimizarea liniară = maximizarea (minimizarea) unei funcții liniare în n variabile reale sub constrângeri (constrângerile sunt ecuații și inegalități). Exemplu: crearea planului de masă și multe, multe alte probleme. Fourier-Motzkin: simplu, dar ineficient. Joseph Fourier (), Theodore Motzkin (), lucrează în 1936 algoritmul Simplex (Georg Dantzig, 1947): încă algoritmul cel mai utilizat; adesea foarte repede, dar în cel mai rău caz exponențial. Leonid Khachiyan, Ellipsoid Method și N. Karmakar, Inner Point Method, au dezvoltat algoritmi cu timp de rulare polinomial. Este adesea folosită metoda punctului interior. Sisteme: CPLEX, Gurobi, SoPlex. Optimizarea KM 14/21
15 Algoritmul simplex maximizează y unde 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) inegalități definesc un poligon P (zona gri). Căutăm colțul cu coordonata y maximă. Intersecția liniilor drepte 2x + 7y = 28 și 4x 2y = 20 are coordonatele (49 8, 9 4). De aici rezultă valoarea optimă y = 9 4. Ideea algoritmului: găsiți un colț p de P și luați în considerare marginile incidente ale lui P. Dacă niciuna nu conduce la o valoare mai mare a funcției obiective, colțul este optim. Dacă o margine duce la o valoare mai bună, mergeți la celălalt capăt al marginii și repetați. 3 diminuări la următoarea optimizare a diapozitivului KM 15/21
16 Simplex în 3D (imagine din Wikipedia) Maximizarea coordonatei z Optimizare KM 16/21
17 Fourier Motzkin decide dacă este rezolvabil Fourier Motzkin decide dacă un sistem de inegalități este rezolvabil. Rezolvați toate inegalitățile pentru una dintre variabile, să zicem pentru variabila x. Există trei tipuri de inegalități: (1) x. (2) x. și (3) nu menționează x. Construiți un sistem nou eliminând x: accept (3) neschimbat. Din fiecare pereche x A și x B din (1) și (2) construim B A. Iterează până când toate variabilele sunt eliminate. Atunci ai o mulțime de inegalități între numere. Banal pentru a decide. Ilustrați cu exemplul: vedeți diapozitivul următor Extensie la optimizare: optimizarea căutării binare KM 17/21
18 Exemplul Fourier Motzkin maximizează y unde 2x + 7y 28 4x 2y 20 x + y 6 y 0 are soluția 9 4. Folosim Fourier-Motzkin pentru a decide dacă există o soluție cu valoarea 3. Optimizarea KM 18/21
19 Pericolele unei modelări și/sau date proaste Rezultatul unei optimizări nu poate fi niciodată mai bun decât modelul și datele. (George B. Dantzig, The diet problem. Interfaces, 20 (4): 43 47, 1990.) Dantzig ar trebui să piardă în greutate: 1500 de calorii pe zi. Îi era frică să nu-i fie foame și, prin urmare, a vrut să maximizeze senzația de sațietate. A ales funcția țintă cantitate fără apă = (1 conținut de apă de 1 kg NM1) x de ce această funcție țintă? Și-a dat seama că, în timp ce apa umple stomacul, nu te face să te simți plin. De aceea a vrut să mănânce cât mai mult posibil, care să nu fie apă. Optimizarea KM 19/21
20 Pericolele unei modelări și/sau date proaste Rezultatul unei optimizări nu poate fi niciodată mai bun decât modelul și datele. (George B. Dantzig, The diet problem. Interfaces, 20 (4): 43 47, 1990.) Dantzig ar trebui să piardă în greutate: 1500 de calorii pe zi. Îi era frică să nu-i fie foame și, prin urmare, a vrut să maximizeze senzația de sațietate. El a ales funcția obiectivă cantitate fără apă = (1 conținut de apă de 1 kg NM1) x soluție 1: 500 galoane de oțet pe zi. De ce? Datele indicau că oțetul avea un conținut scăzut de calorii și nu conținea apă. Dantzig întinde oțet. Soluția 2: 200 cuburi stoc. A încercat o ciorbă cu 4 cuburi de brânză; total sărat. Limita superioară a trei cuburi de stoc. Soluția 3: 2 kilograme de tărâțe pe zi. Soția lui i-a interzis să mănânce atâtea tărâțe. Limita superioară pentru tărâțe. Soluția 4: 2 kilograme de melasă Soluția 5: În cele din urmă a devenit prea colorată pentru soția sa și ea a preluat regimul. Dantzig a slăbit 22 de lire sterline. Optimizarea KM 19/21
21 Plan de meniu, varietate de modelare Luăm feluri de mâncare ca componente ale meniului. x i = numărul de zile în care servim vasul i. Constrângeri suplimentare: x x n = 365, x i 26, i feluri de mâncare pentru paste x i 52, i feluri de mâncare pentru pește 52. Toate celelalte ca înainte. Problemă: ce înseamnă spaghetele de 3,37 ori? Meniu pentru un an cel mult o dată la două săptămâni Soluție alternativă 1: x i întreg ca o constrângere suplimentară: Dar optimizarea întregului este mult mai dificilă. Soluția 2: găsiți soluția reală optimă. Rotunjește numerele sus/jos la următorul număr întreg. Optimizarea KM 20/21
22 Plan de meniu, modelarea varietății Luăm feluri de mâncare ca componente ale meniului. x i = numărul de zile în care servim vasul i. Constrângeri suplimentare: x x n = 365, x i 26, i feluri de mâncare pentru paste x i 52, i feluri de mâncare pentru pește 52. Toate celelalte ca înainte. Problemă: ce înseamnă de 3,37 ori spaghetele? Meniu pentru un an cel mult o dată la două săptămâni Soluție alternativă 1: x i întreg ca o constrângere suplimentară: Dar optimizarea întregului este mult mai dificilă. Soluția 2: găsiți soluția reală optimă. Rotunjește numerele în sus/în jos la următorul număr întreg. Optimizarea KM 20/21
23 Rezumat Optimizarea liniară (= maximizarea (minimizarea) unei funcții liniare în n variabile sub constrângeri (constrângerile sunt ecuații și inegalități)) este foarte expresivă și poate fi rezolvată eficient. Optimizarea liniară întregi (sunteți interesat doar de soluțiile întregi) este mult mai expresivă, dar mai dificil de rezolvat. Rezultatul nu este niciodată mai bun decât modelul și datele. Acest lucru este valabil și pentru simulare. Simulare climatică de testare a stresului la optimizarea băncilor KM 21/21
24 Rezumat Optimizarea liniară (= maximizarea (minimizarea) unei funcții liniare în n variabile sub constrângeri (constrângerile sunt ecuații și inegalități)) poate fi rezolvată foarte expresiv și eficient. Optimizarea liniară întregi (sunteți interesat doar de soluțiile întregi) este mult mai expresivă, dar mai dificil de rezolvat. Rezultatul nu este niciodată mai bun decât modelul și datele. Acest lucru este valabil și pentru simulare. Simulare climatică test de stres la optimizarea băncilor KM 21/21