Идеи за компютърна оптимизация
1 Идеи за ИТ оптимизация Kurt Mehlhorn декември 2018 г.
2 проблема с оптимизацията са вездесъщи: Намерете най-бързия маршрут от А до Б. Планирайте пътувания на компанията. Задайте набор от задачи на набор от работници по такъв начин, че общото време за обработка да бъде сведено до минимум (алтернативно, завършване възможно най-рано). Управлявайте трионите в дъскорезницата по такъв начин, че да се произвеждат възможно най-ценните продукти.Контролирайте крилата ракета, така че нейното общо полетно разстояние да не бъде превишено и вероятността да бъде свален е сведена до минимум. Поставете предмети в контейнер. Оптимизиране на KM 2/21
3 По-нататъшни проблеми с оптимизацията Оптимизирайте разписанието на федералната железница, автобусите в Саарбрюкен. Намерете добър график за UdS. Намерете плана за евакуация на спортен стадион. Изчислете най-евтиния хранителен план (диета). За телефонна компания изчислете къде да поставите мачти за мобилен телефон. Целта е да се постигне възможно най-голямо покритие при ниски разходи. Оптимизиране на KM 3/21
4 Процедура Формулирайте задачата и създайте математически модел. Решаване на проблема с модела. Превеждане на решението обратно в реалния свят и поставяне под въпрос на решението. Полезно ли е решението в реалния свят или показва слабост в моделирането? Във втория случай подобряване на модела. Предупреждение: Моделът улавя само част от реалността. Дори когато внимателно създавате модел, може да се случи, че съществените аспекти на реалността са пропуснати. Така че третата стъпка е от съществено значение. Решението на проблема с оптимизацията често показва слабости в модела. Оптимизиране на KM 4/21
5 Предупредителен пример (повече ще дойдат по-късно) Предположение за модел за разписанието на Bundesbahn: време за прехвърляне най-малко пет минути. Оптималният график само ще планира минималното време за трансфер за много връзки. Когато използвате/проверявате решението, установявате, че дори и най-малките забавяния могат напълно да объркат решението. В резултат на това човек ще увеличи времето за трансфер или ще помисли как може да моделира устойчивостта на разписанието срещу прекъсвания (стохастична оптимизация). Оптимизиране на KM 5/21
6 Планове за оптимално хранене Джордж Стиглер формулира следната оптимизационна задача през 1945 г .: Колко струва диета, която отговаря на всички основни нужди? Джордж Дж. Стиглер: Разходите за издръжка. Journal of Farm Economics, 27 (2): „Той имаше предвид задачата полу-забавна, полу-сериозна. Полузабавно, защото тогава вече имаше много книги и статии за балансирано и евтино хранене, полусериозно, защото американската държава имаше стотици хиляди войници, които да се хранят. Джордж Джоузеф Стиглер () беше американски икономист. През 1982 г. получава Нобелова награда за икономика. Той беше отличен за работата си по индустриална организация, функционирането на пазарите и причините и последствията от регулирането на пазара. Оптимизиране на KM 6/21
7 Моделиране: Какво е адекватно хранене? Първи отговор: Диета, която отговаря на препоръките на Националния съвет за изследвания за 9 основни хранителни вещества. Хранителни калории Протеин Калций Желязо Витамин А Тиамин (Витамин В1) Рибофлавин (Витамин В2) Ниацин Аскорбинова киселина (Витамин С) Препоръчителен дневен прием 3000 калории 70 грама 8 грама 12 милиграма 5000 IU 1,8 милиграма 2,7 милиграма 18 милиграма 75 милиграма Той посочва че тези препоръки вероятно ще бъдат непълни и неточни. Днес: също горната граница за мазнини в менюто, по-нисък брой калории, оптимизация на KM 7/21
8 Foods Stigler разглежда 77-те храни, които Бюрото по трудова статистика редовно цени. За всяка храна той взема съдържанието на различните хранителни вещества от литературата. Той изрично посочва, че тези цифри трябва да се третират с повишено внимание, тъй като някои видове приготвяне или продължително съхранение унищожават определени хранителни вещества и тъй като таблицата съдържа само средни стойности. Например, ябълка в Онтарио съдържа 10 пъти повече витамин С, отколкото ябълка McIntosh. Формализиране на задачата: Колко трябва да се купува от всяка хранителна стока, така че да бъдат изпълнени изискванията за менюто и разходите да са минимални? Оптимизиране на KM 8/21
9 Математически модел xi = количество (в kg) на i-та храна (NM) в оптималното меню, i = условия (по едно за всяка съставка): планът трябва да съдържа съставки в достатъчни количества, например за калории: калории/kg от NM 1 x калории/kg NM 77 x разходите по хранителния план са тогава разходи = цена/kg NM 1 x цена/kg NM 77 x 77. Задача: намерете неотрицателни стойности за неизвестните x 1 до x 77, всички те Постигнете ограничения и минимизирайте разходите. Оптимизиране на KM 9/21
10 Решение на задачата: Стъпка 1, опростяване Стиглер не познава алгоритъм за решаване на системи от неравенства. Той определи приблизително решение по много умен начин. Доминиране: Ако A е по-евтин от B, но съдържа поне толкова от всяка съставка, колкото B, тогава B може да бъде изтрит, без да губи оптимално решение. Намаляване до 15 NM. Брашното доминира в хляба, говеждият черен дроб доминира във всички останали видове месо, всички патентовани зърнени култури и напитки. Изкуствена храна, около 5 килограма брашно плюс 2 килограма билка: Ако изкуствена НМ доминира в истинска НМ, истинската може да бъде изтрита. Намаляване до 9 NM. Оптимизиране на KM 10/21
11 Стъпка 2: Решение Сега 9 неравенства трябва да бъдат изпълнени в 9 променливи (obda, x 1 до x 9). Искате решение с минимални разходи. Оптималното решение трябва да задоволи някои от неравенствата с равенство, тъй като. Има = 511 непразни подмножества на неравенствата. Стиглиц разглежда само няколко подмножества (интуиция). За фиксирано подмножество S той решава получената система от уравнения и сега неговото описание става неясно. След това той предлага решение с годишни разходи в долари (около 510 долара с днешните пари). Оптимизация на KM 11/21
12 резултат След това той предлага решение с годишни разходи в долари (около 510 долара с днешните пари). Храна Годишни количества Годишни разходи (в долари) Пшенично брашно 370 lb Изпарено мляко 57 кутии 3.84 Зеле 111 lb Спанак 23 lb Сушен флот 285 lb Общи годишни разходи Това оптимално ли е? Stigler твърди (не е напълно ясно) долна граница: Брашното е най-евтиният източник на калории: брашното от 24,50 долара има 3000 калории. Но едва ли има калций. Най-евтиният източник на калций е сиренето. След това добавете още $ 14.90. Данциг изобретява алгоритъм за решение (симплекс алгоритъм) в 47. Екип от 9 човешки компютъра изчислява оптималното решение за 120 човекодни дни: Най-евтиното меню струва долари. Решението на Stigler беше само с 24 цента по-високо. Оптимизация на KM 12/21
13 Какво знаем сега? алгоритмично: намирането на оптимално решение на система от неравенства не е лесно. Dantzig изобретява алгоритъм за решение в Вижте по-долу. Моделиране: опитът да се получи математическият проблем е интересен, но моделирането е неадекватно: никой не иска да се храни така. Можете ли да моделирате разнообразие? Ще се върнем към това в края на лекцията. Оптимизиране на KM 13/21
14 Алгоритми за линейна оптимизация Линейна оптимизация = максимизиране (минимизиране) на линейна функция в n реални променливи при ограничения (ограниченията са уравнения и неравенства). Пример: създаване на план за хранене и много, много други проблеми. Фурие-Моцкин: просто, но неефективно. Джоузеф Фурие (), Теодор Моцкин (), работят през 1936 г. Симплекс алгоритъм (Георг Данциг, 1947): все още най-широко използваният алгоритъм; често много бързо, но в най-лошия случай експоненциално. Леонид Хачиян, Елипсоиден метод и Н. Кармакар, метод на вътрешната точка, разработиха алгоритми с полиномно време на работа. Често се използва методът на вътрешната точка. Системи: CPLEX, Gurobi, SoPlex. Оптимизиране на KM 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 затъмнения на следващата оптимизация на слайд KM 15/21
16 Симплекс в 3D (снимка от Уикипедия) Максимизиране на координатата z z Оптимизация KM 16/21
17 Фурие Моцкин да реши дали е разрешим Фурие Моцкин решава дали система от неравенства е разрешима. Решете всички неравенства за една от променливите, да речем за променлива x. Има три вида неравенства: (1) x. (2) х. и (3) не споменават x. Изградете нова система, като премахнете x: take (3) непроменен. От всяка двойка x A и x B от (1) и (2) конструирайте B A. Итерация, докато всички променливи бъдат елиминирани. Тогава имате много неравенства между числата. Тривиално за решаване. Илюстрирайте с примера: вижте следващия слайд Разширение за оптимизация: оптимизация за двоично търсене KM 17/21
18 Пример на Фурие Моцкин максимизирайте y, където 2x + 7y 28 4x 2y 20 x + y 6 y 0 има решение 9 4. Използваме Fourier-Motzkin, за да решим дали има решение със стойност 3. Оптимизиране на KM 18/21
19 Опасностите от лошо моделиране и/или данни Резултатът от оптимизацията никога не може да бъде по-добър от модела и данните. (George B. Dantzig, Проблемът с диетата. Интерфейси, 20 (4): 43 47, 1990.) Dantzig трябва да отслабне: 1500 калории на ден. Страхуваше се от глад и затова искаше да увеличи чувството за ситост. Той избра целевата функция неводно количество = (1 водно съдържание 1 кг NM1) x защо тази целева функция? Той реши, че докато водата изпълва стомаха, това не ви кара да се чувствате сити. Ето защо той искаше да яде колкото се може повече, което не беше вода. Оптимизиране на KM 19/21
20 Опасностите от лошо моделиране и/или данни Резултатът от оптимизацията никога не може да бъде по-добър от модела и данните. (George B. Dantzig, Проблемът с диетата. Интерфейси, 20 (4): 43 47, 1990.) Dantzig трябва да отслабне: 1500 калории на ден. Страхуваше се от глад и затова искаше да увеличи чувството за ситост. Той избра целевата функция неводно количество = (1 водно съдържание 1 кг NM1) х разтвор 1: 500 галона оцет на ден. Защо? Данните посочват, че оцетът е с ниско съдържание на калории и не съдържа вода. Данциг намазва оцет. Решение 2: 200 кубчета запас. Опита супа с 4 кубчета акция; напълно солено. Горна граница от три кубчета. Решение 3: 2 килограма трици на ден. Съпругата му му забранила да яде толкова трици. Горна граница за трици. Решение 4: 2 килограма меласа Решение 5: Накрая стана твърде цветно за жена му и тя пое режима. Данциг отслабна с 22 килограма. Оптимизиране на KM 19/21
21 План на менюто, разнообразие от модели Приемаме ястията като компоненти на менюто. x i = брой дни, в които сервираме ястие i. Допълнителни ограничения: x x n = 365, x i 26, i тестени ястия x i 52, i рибни ястия 52. Всичко останало, както преди. Проблем: какво означават 3,37 пъти спагети? Меню за една година най-много веднъж на две седмици Решение за редуване 1: x i integer като допълнително вторично условие: Но оптимизацията на integer е много по-трудна. Решение 2: намерете оптималното реално решение. Закръглете числата нагоре/надолу към следващото цяло число. Оптимизация на KM 20/21
22 План на менюто, моделиране на разнообразието Ние приемаме ястията като компоненти на менюто. x i = брой дни, в които сервираме ястие i. Допълнителни ограничения: x x n = 365, x i 26, i тестени ястия x i 52, i рибни ястия 52. Всичко останало, както преди. Проблем: какво означават 3,37 пъти спагети? Меню за една година най-много веднъж на две седмици Решение за редуване 1: x i integer като допълнително ограничение: Но оптимизацията на integer е много по-трудна. Решение 2: намерете оптималното реално решение. Закръглете числата нагоре/надолу към следващото цяло число. Оптимизация на KM 20/21
23 Резюме Линейната оптимизация (= максимизиране (минимизиране) на линейна функция в n променливи при ограничения (ограниченията са уравнения и неравенства)) е много изразителна и може да бъде решена ефективно. Целочислената линейна оптимизация (интересуват ви се само от целочислени решения) е много по-изразителна, но по-трудна за решаване. Резултатът никога не е по-добър от модела и данните. Това важи и за симулацията. Стрес тест за климатична симулация при оптимизация на банки KM 21/21
24 Обобщение Линейната оптимизация (= максимизиране (минимизиране) на линейна функция в n променливи при ограничения (ограниченията са уравнения и неравенства)) е много изразителна и може да бъде решена ефективно. Целочислената линейна оптимизация (интересуват ви се само от целочислени решения) е много по-изразителна, но по-трудна за решаване. Резултатът никога не е по-добър от модела и данните. Това важи и за симулацията. Стрес тест за климатична симулация при оптимизация на банки KM 21/21