Идеи за компјутерска оптимизација
1 идеи за ИТ оптимизација Курт Мелхорн декември 2018 година
2 проблеми со оптимизација се сеприсутни: Пронајдете ја најбрзата рута од А до Б. Планирајте патувања на компанијата. Доделете збир на задачи на збир на работници на таков начин што целокупното време на обработка е минимизирано (алтернативно, завршување што е можно порано). Контролирајте ги пилите во пилана на таков начин што се произведуваат највредните можни производи Контролирајте крстосувачка ракета за да не се надмине вкупното растојание на летот и да се минимизира веројатноста за соборување. Ставете предмети во контејнер. Оптимизација на КМ 2/21
3 Понатамошни проблеми со оптимизација Оптимизирајте го возниот ред на федералната железница, автобусите на Сарбрикен. Пронајдете добар возен ред за UdS. Пронајдете го планот за евакуација на спортски стадион. Пресметајте го најевтиниот план за исхрана (диета). За телефонска компанија, пресметајте каде да ги поставите јарболите за мобилни телефони. Целта е да се постигне најголема можна покриеност при ниски трошоци. Оптимизација на КМ 3/21
4 Постапка Формулирајте го проблемот и креирајте математички модел. Решавање на проблемот со моделот. Преведувајќи го решението назад во реалниот свет и ставајќи го во прашање решението. Дали решението е корисно во реалниот свет или укажува на слабост во моделирањето? Во вториот случај, подобрување на моделот. Предупредување: Модел само некогаш фаќа дел од реалноста. Дури и при внимателно креирање на модел, може да се случи суштинските аспекти на реалноста да бидат изоставени. Значи, третиот чекор е од суштинско значење. Решението за проблем со оптимизација често укажува на слабости во моделот. Оптимизација на КМ 4/21
5 Пример за претпазливост (повеќе ќе дојде подоцна) Претпоставка на моделот за распоредот на Бундесбан: време на трансфер најмалку пет минути. Оптимален возен ред ќе го испланира само минималното време на пренос за многу врски. Кога го користите/проверувате решението, откривате дека дури и најмалите одложувања можат целосно да го избркаат решението. Како последица, ќе се зголемат некои времиња на трансфер или ќе се разгледа како може да се моделира робусноста на распоредот против нарушувања (стохастичка оптимизација). Оптимизација на КМ 5/21
6 планови за оптимална исхрана Georgeорџ Стиглер ја формулира следнава задача за оптимизација во 1945 година: Колку чини диета што ги задоволува сите основни потреби? J.орџ S. Стиглер: Цената на егзистенцијата. Journalурнал за фарма економија, 27 (2): 'Тој ја смисли задачата полу-забавна, полу-сериозна. Полу-забавна бидејќи тогаш веќе имаше многу книги и написи за избалансирана и ефтина исхрана, полусериозна затоа што американската држава имаше стотици илјади војници да се хранат. Georgeорџ Josephозеф Стиглер () беше американски економист. Во 1982 година ја доби Нобеловата награда за економија. Тој беше почестен за неговата работа во областа на индустриската организација, функционирањето на пазарите и причините и последиците од регулацијата на пазарот. Оптимизација на КМ 6/21
7 моделирање: Што е адекватна исхрана? Прв одговор: Исхрана што ги исполнува препораките на Националниот совет за истражување за 9 основни хранливи материи. Хранливи материи калории Протеин калциум железо витамин А тиамин (витамин Б1) рибофлавин (витамин Б2) ниацин аскорбинска киселина (витамин Ц) дневно препорачано внесување 3.000 калории 70 грама. 8 грама 12 милиграми 5.000 IU 1,8 милиграми 2,7 милиграми 18 милиграми 75 милиграми Тој посочува дека овие препораки најверојатно ќе бидат нецелосни и неточни. Денес: исто така горна граница на маснотии во менито, помал број на калории, оптимизација на КМ 7/21
8 Храни Стиглер ги разгледува 77-те намирници кои редовно ги цени Бирото за статистика на трудот. За секоја храна ја зема содржината на различните хранливи материи од литературата. Тој експресно посочува дека овие бројки треба да се третираат со претпазливост, бидејќи одредени видови на подготовка или долго складирање уништуваат одредени хранливи материи и бидејќи табелата содржи само средни вредности. На пример, јаболкото во Онтарио содржи 10 пати повеќе витамин Ц од јаболкото Мекинтош. Формализација на задачата: Колку треба да се купи секој од прехранбените производи, така што барањата за менито се исполнети, а трошоците минимални? Оптимизација на КМ 8/21
9 Математички модел xi = количина (во кг) од i-тата храна (НМ) во оптималното мени, i = услови (по една за секоја состојка): планот мора да обезбеди состојки во доволни количини, на пр. За калории: калории/кг NM 1 x калории/kg NM 77 x трошоците на планот за исхрана се трошоци = цена/kg NM 1 x цена/kg NM 77 x 77. Задача: пронајдете не-негативни вредности за непознатите x 1 до x 77, сите Исполнете ги ограничувањата и минимизирајте ги трошоците. Оптимизација на КМ 9/21
10 Решение за задачата: Чекор 1, поедноставување Стиглер не знаеше никаков алгоритам за решавање на системи на нееднаквости. Тој определи приближно решение на многу паметен начин. Доминација: Ако А е поевтино од Б, но содржи барем колку од секоја состојка како Б, тогаш Б може да се избрише без да се изгуби оптимално решение. Намалување до 15 НМ. Брашното доминира во лебот, говедскиот црн дроб доминира во сите други видови месо, доминираат сите патентирани житни култури и пијалоци. Вештачка храна, околу 5 килограми брашно плус 2 килограми билка: Ако вештачки НМ доминира во вистински НМ, вистинскиот може да се избрише. Намалување до 9 НМ. Оптимизација на КМ 10/21
11 Чекор 2: Решение Сега 9 нееднаквости што треба да се исполнат во 9 варијабли (obda, x 1 до x 9). Сакате решение за минимални трошоци. Оптималното решение мора да задоволи некои нееднаквости со еднаквост, бидејќи. Постојат = 511 непразни подмножества на нееднаквостите. Стиглиц разгледува само неколку подмножества (интуиција). За фиксна подгрупа S тој го решава добиениот систем на равенки и сега неговиот опис станува нејасен. Потоа тој дошол до решение со годишна цена на долари (околу 510 УСД со денешните пари). Оптимизација на КМ 11/21
12 Резултат Потоа тој дошол до решение со годишна цена на долари (околу 510 УСД со денешните пари). Храна Годишни количини Годишен трошок (во долари) Брашно од пченица 370 кг испарено млеко 57 лименки 3,84 зелка 111 кг спанаќ 23 кг сушен грав од морнарица 285 кг вкупна годишна цена Дали е оптимално? Стиглер тврди (не е јасно) долна граница: Брашното е најевтиниот извор на калории: брашното од 24,50 долари има 3000 калории. Но, тешко калциум. Најевтиниот извор на калциум е сирењето. Потоа додадете уште 14,90 УСД. Данциг измислува алгоритам за решение (алгоритам на симплекс) во 47. Тим од 9 човечки компјутери го пресметува оптималното решение за 120 човечки дена: Најевтиното мени чини долари. Решението на Стиглер беше повисоко за само 24 центи. Оптимизација на КМ 12/21
13 Што знаеме сега? алгоритамски: да се најде оптимално решение за систем на нееднаквости не е лесно. Данциг измислува алгоритам на решенија во Погледнете подолу. Моделирање: обидот да се добие математички проблем е интересно, но моделирањето е несоодветно: никој не сака да јаде така. Можете ли да моделирате разновидност? Thisе се вратиме на ова на крајот од предавањето. Оптимизација на КМ 13/21
14 Алгоритми за линеарно оптимизирање Линеарно оптимизирање = максимизирање (минимизирање) на линеарна функција во n реални променливи под ограничувања (ограничувањата се равенки и нееднаквости). Пример: креирање на план за јадење и многу, многу други проблеми. Фурие-Моцкин: едноставен, но неефикасен. Josephозеф Фуриер (), Теодор Моцкин (), работа во 1936 година Симплекс алгоритам (Георг Данциг, 1947 година): сè уште најчесто користен алгоритам; често многу брзо, но во најлош случај експоненцијално. Леонид Качијан, Метод на елипсоид и Н.Кармакар, метод на внатрешна точка, развија алгоритми со полиномско време на трчање. Често се користи методот на внатрешна точка. Системи: CPLEX, Gurobi, SoPlex. Оптимизација на КМ 14/21
15 Симплекс алгоритмот максимизира y каде 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) нееднаквости дефинираат многуаголник P (сива површина). Го бараме аголот со максимална y-координата. Пресекот на прави 2x + 7y = 28 и 4x 2y = 20 ги има координатите (49 8, 9 4). Така, оптималната вредност y = 9 4. Идеја на алгоритмот: пронајдете агол p од P и разгледајте ги инцидентните рабови на P. Ако ниту еден не доведе до поголема вредност на објективната функција, аголот е оптимален. Ако едниот раб доведе до подобра вредност, одете до другиот крај на работ и повторете го. 3 затемнувања на следната оптимизација на слајдот КМ 15/21
16 Симплекс во 3Д (слика од Википедија) Максимизирање на z координатата Оптимизација KM 16/21
17 Фурие Моцкин да одлучи дали е решлив Фуриер Моцкин одлучува дали е може да се реши систем на нееднаквости. Решете ги сите нееднаквости за една од променливите, да речеме за променливата x. Постојат три типа на нееднаквости: (1) x. (2) x и (3) не споменувај x. Конструирајте нов систем со елиминирање на x: земете (3) непроменет. Од секој пар x A и x B од (1) и (2) конструкција Б A. Итера, сè додека не се елиминираат сите променливи. Тогаш имате многу нееднаквости помеѓу броевите. Тривијално да се одлучи. Илустрирајте со примерот: видете го следниот слајд Продолжување до оптимизација: бинарно оптимизирање на пребарувањето КМ 17/21
18 Пример за Фурие Моцкин максимизирај y каде 2x + 7y 28 4x 2y 20 x + y 6 y 0 има решение 9 4. Ние го користиме Фурие-Моцкин за да одлучиме дали има решение со вредност 3. Оптимизација на КМ 18/21
19 Опасности од лошо моделирање и/или податоци Резултатот од оптимизацијата никогаш не може да биде подобар од моделот и податоците. (B.орџ Б. Данциг, Проблем со исхраната. Интерфејси, 20 (4): 43 47, 1990.) Данциг треба да изгуби тежина: 1500 калории на ден. Се плашеше од чувство на глад и затоа сакаше да го зголеми чувството на ситост. Тој ја избра целната функција не-количина на вода = (1 содржина на вода од 1 кг NM1) x зошто оваа цел-функција? Тој сфатил дека додека водата го исполнува стомакот, тоа не прави да се чувствувате сити. Затоа тој сакаше да јаде што е можно повеќе што не беше вода. Оптимизација на КМ 19/21
20 Опасности од лошо моделирање и/или податоци Резултатот од оптимизацијата никогаш не може да биде подобар од моделот и податоците. (B.орџ Б. Данциг, Проблем со исхраната. Интерфејси, 20 (4): 43 47, 1990.) Данциг треба да изгуби тежина: 1500 калории на ден. Се плашеше од чувство на глад и затоа сакаше да го зголеми чувството на ситост. Тој ја избра објективната функција количина на вода = (1 содржина на вода од 1 кг NM1) x раствор 1: 500 литри оцет на ден. Зошто? Податоците наведуваат дека оцетот има малку калории и не содржи вода. Данциг намачка оцет. Решение 2: 200 коцки залихи. Тој проба супа со 4 коцки залихи; тотално солено. Горна граница на три коцки залихи. Решение 3: 2 килограми трици на ден. Неговата сопруга му забрани да јаде толку трици. Горна граница за трици. Решение 4: 2 килограми меласа Решение 5: На крајот стана премногу шарена за неговата сопруга и таа го презеде режимот. Данциг изгуби 22 килограми. Оптимизација на КМ 19/21
21 План за мени, разновидност за моделирање Ние земаме јадења како компоненти на менито. x i = број на денови што ги послужуваме јадење i. Дополнителни ограничувања: x x n = 365, x i 26, јадења со тестенини x i 52, рибини јадења 52. Сè друго како порано. Проблем: што значи 3,37 пати шпагети? План за оброк најмногу една година еднаш на секои две недели Алтернативно решение 1: x i цел број како дополнителен секундарен услов: Но оптимизацијата на цел број е многу потешка. Решение 2: пронајдете оптимално реално решение. Заокружете ги броевите нагоре/надолу до следниот целосен број. Оптимизација на КМ 20/21
22 План за мени, моделирање на разновидност Ние земаме јадења како компоненти на менито. x i = број на денови што ги послужуваме јадење i. Дополнителни ограничувања: x x n = 365, x i 26, јадења со тестенини x i 52, рибини јадења 52. Сè друго како порано. Проблем: што значи 3,37 пати шпагети? План за оброк најмногу една година еднаш на секои две недели Алтернативно решение 1: x i цел број како дополнителен секундарен услов: Но оптимизацијата на цел број е многу потешка. Решение 2: пронајдете оптимално реално решение. Заокружете ги броевите нагоре/надолу до следниот целосен број. Оптимизација на КМ 20/21
23 Резиме Линеарна оптимизација (= максимизирање (минимизирање) на линеарна функција во n променливи под ограничувања (ограничувањата се равенки и нееднаквости)) е многу експресивна и може ефикасно да се реши. Линеарната оптимизација на цел број (заинтересирани сте само за решенија со цел број) е многу поизразена, но потешко е да се реши. Резултат никогаш подобар од моделот и податоците. Ова исто така важи и за симулацијата. Стрес-тест за симулација на клима при оптимизација на банките КМ 21/21
24 Резиме Линеарната оптимизација (= максимизирање (минимизирање) на линеарна функција во n променливи под ограничувања (ограничувањата се равенки и нееднаквости)) е многу експресивна и може ефикасно да се реши. Линеарната оптимизација на цел број (заинтересирани сте само за решенија со цел број) е многу поизразена, но потешко е да се реши. Резултат никогаш подобар од моделот и податоците. Ова исто така важи и за симулацијата. Стрес-тест за симулација на клима при оптимизација на банките КМ 21/21