Ідеї комп’ютерної оптимізації
1 Ідеї ІТ-оптимізації Курт Мелхорн, грудень 2018
2 проблеми оптимізації є всюдисущими: знайдіть найшвидший маршрут від А до Б. Сплануйте поїздки компанії. Розподіліть набір завдань для набору робітників таким чином, щоб загальний час обробки був зведений до мінімуму (в якості альтернативи, завершення якомога раніше). Керуйте пилами на лісопильному заводі таким чином, щоб вироблялися найцінніші продукти, а також керуйте крилатою ракетою, щоб не перевищувати її загальну відстань польоту і зводити до мінімуму ймовірність збиття. Покладіть предмети в контейнер. Оптимізація KM 2/21
3 Подальші проблеми оптимізації Оптимізуйте розклад руху федеральної залізниці, автобусів Саарбрюккена. Знайдіть хороший графік для UdS. Знайдіть план евакуації спортивного стадіону. Розрахуйте найдешевший план харчування (дієта). Для телефонної компанії підрахуйте, де розмістити щогли стільникового телефону. Метою є досягнення максимально можливого покриття при низьких витратах. Оптимізація KM 3/21
4 Процедура Сформулюйте задачу та створіть математичну модель. Вирішення проблеми моделі. Перекласти рішення назад у реальний світ та поставити під сумнів рішення. Чи корисне рішення в реальному світі, чи воно свідчить про слабкість моделювання? У другому випадку вдосконалення моделі. Попередження: модель лише колись фіксує частинку реальності. Навіть при ретельному створенні моделі може статися так, що основні аспекти реальності залишаються поза увагою. Отже, третій крок є суттєвим. Рішення проблеми оптимізації часто вказує на слабкі сторони моделі. Оптимізація KM 4/21
5 Приклад застереження (більше з’явиться пізніше) Припущення моделі для розкладу Бундесбана: час пересадки не менше п’яти хвилин Оптимальний розклад планує лише мінімальний час передачі для багатьох сполучень. Використовуючи/перевіряючи рішення, ви виявляєте, що навіть найменші затримки можуть повністю зіпсувати рішення. Як наслідок, можна збільшити час передачі або розглянути, як можна змоделювати стійкість розкладу проти зривів (стохастична оптимізація). Оптимізація KM 5/21
6 Оптимальні плани харчування Джордж Стіглер сформулював наступне завдання оптимізації в 1945 році: скільки коштує дієта, яка відповідає всім основним потребам? Джордж Дж. Стіглер: Вартість існування. Журнал економіки фермерських господарств, 27 (2): «Він мав на увазі завдання напівзабавно, напівсерйозно. Наполовину весело, тому що тоді вже було багато книг та статей про збалансовану та недорогу дієту, напівсерйозно, бо американський штат мав прогодувати сотні тисяч солдатів. Джордж Джозеф Стиглер () був американським економістом. У 1982 році отримав Нобелівську премію з економіки. Він був відзначений за свою роботу з організації промисловості, функціонування ринків та причин та наслідків регулювання ринку. Оптимізація KM 6/21
7 Моделювання: Що таке адекватне харчування? Перша відповідь: дієта, яка відповідає рекомендаціям Національної дослідницької ради щодо 9 основних поживних речовин. Поживні калорії Білок Кальцій Залізо Вітамін А Тіамін (Вітамін В1) Рибофлавін (Вітамін В2) Ніацин Аскорбінова кислота (Вітамін С) Щоденний рекомендований прийом 3000 калорій 70 грам. 8 грам. 12 міліграм. 5000 МО. 1,8 міліграма. 2,7 міліграма. що ці рекомендації можуть бути неповними та неточними. Сьогодні: також верхня межа жиру в меню, нижча кількість калорій, оптимізація KM 7/21
8 Foods Stigler розглядає 77 продуктів харчування, які Бюро статистики праці регулярно визначає. Для кожної їжі він бере вміст різних поживних речовин з літератури. Він прямо вказує, що до цих цифр слід ставитися з обережністю, оскільки певні типи препаратів або тривале зберігання руйнують певні поживні речовини і оскільки таблиця містить лише середні значення. Наприклад, яблуко в Онтаріо містить у 10 разів більше вітаміну С, ніж яблуко Макінтош. Формалізація завдання: Скільки потрібно купувати кожного продукту харчування, щоб вимоги до меню були задоволені, а витрати мінімальні? Оптимізація KM 8/21
9 Математична модель xi = кількість (у кг) i-ї їжі (NM) в оптимальному меню, i = умови (по одній на інгредієнт): план повинен передбачати інгредієнти в достатній кількості, наприклад для калорій: калорій/кг NM 1 х калорій/кг NM 77 x витрати на план харчування становлять тоді витрати = ціна/кг NM 1 х ціна/кг NM 77 x 77. Завдання: знайти невід'ємні значення для невідомих x 1 до x 77, усі вони Дотримуйтесь обмежень та мінімізуйте витрати. Оптимізація KM 9/21
10 Розв’язання завдання: Крок 1, спрощення Стіглер не знав жодного алгоритму розв’язання систем нерівностей. Він дуже розумно визначив приблизне рішення. Домінування: якщо A дешевший за B, але містить принаймні стільки кожного інгредієнта, скільки B, то B можна видалити, не втрачаючи оптимального рішення. Зменшення до 15 Нм. Борошно домінує в хлібі, яловича печінка - у всіх інших видах м’яса, запатентована крупа та напої. штучна їжа, близько 5 кілограмів борошна плюс 2 кілограми трави: якщо штучна НМ домінує над справжньою НМ, справжню можна видалити. Зменшення до 9 нм. Оптимізація KM 10/21
11 Крок 2: Розв’язання Тепер 9 нерівностей потрібно виконати за 9 змінними (obda, x 1 - x 9). Хочете рішення з мінімальними витратами. Оптимальне рішення повинно задовольнити деякі нерівності з рівністю, оскільки. Існує = 511 непорожній підмножина нерівностей. Стігліц розглядає лише кілька підмножин (інтуїція). Для фіксованої підмножини S він вирішує отриману систему рівнянь, і тепер його опис стає розмитим. Потім він пропонує рішення з річною вартістю доларів (близько 510 доларів на сьогоднішні гроші). Оптимізація KM 11/21
12 Результат Потім він пропонує рішення з річними витратами в доларах (близько 510 доларів на сьогоднішні гроші). Їжа Річна кількість Річна вартість (у доларах) Пшеничне борошно 370 фунтів Випарене молоко 57 банок 3,84 Капуста 111 фунтів Шпинат 23 фунтів Сушені боби темно-синього кольору 285 фунтів Загальна річна вартість Це оптимальне? Штіглер стверджує (не зовсім зрозуміло) нижню межу: борошно є найдешевшим джерелом калорій: борошно в $ 24,50 має 3000 калорій. Але навряд чи кальцій. Найдешевше джерело кальцію - сир. Потім додайте ще $ 14,90. Данциг винаходить алгоритм рішення (симплексний алгоритм) у 47. Команда з 9 людських комп’ютерів розраховує оптимальне рішення за 120 людських днів: Найдешевше меню коштує доларів. Розчин Штіглера був лише на 24 центи вище. Оптимізація KM 12/21
13 Що ми знаємо зараз? алгоритмічний: знайти оптимальне рішення системи нерівностей непросто. Данциг винаходить алгоритм рішення в Див. Нижче. Моделювання: спроба отримати математичну задачу цікава, але моделювання неадекватне: ніхто не хоче їсти так. Чи можете ви моделювати різноманітність? Ми повернемось до цього наприкінці лекції. Оптимізація 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 Оптимізація KM 16/21
17 Фур'є Моцкін вирішує, чи можна це розв'язувати Фур'є Моцкін вирішує, чи розв'язується система нерівностей. Розв’яжіть усі нерівності для однієї зі змінних, скажімо для змінної x. Існує три типи нерівностей: (1) x. (2) х. та (3) не згадують x. Побудуйте нову систему, виключивши x: accept (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. Ми використовуємо Фур'є-Моцкіна, щоб вирішити, чи існує рішення зі значенням 3. Оптимізація KM 18/21
19 Небезпеки поганого моделювання та/або даних Результат оптимізації ніколи не може бути кращим, ніж модель та дані. (Джордж Б. Данциг, проблема дієти. Інтерфейси, 20 (4): 43 47, 1990). Данциг повинен схуднути: 1500 калорій на день. Боявся почуття голоду і тому хотів посилити почуття ситості. Він обрав цільову функцію безводну кількість = (1 вміст води 1 кг NM1) x чому ця цільова функція? Він припустив, що, хоча вода наповнює шлунок, це не дає вам відчувати ситість. Тому він хотів їсти якомога більше, що не було водою. Оптимізація KM 19/21
20 Небезпеки поганого моделювання та/або даних Результат оптимізації ніколи не може бути кращим, ніж модель та дані. (Джордж Б. Данциг, проблема дієти. Інтерфейси, 20 (4): 43 47, 1990). Данциг повинен схуднути: 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 як додаткове обмеження: Але цілочисельна оптимізація набагато складніша. Рішення 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 як додаткове обмеження: Але цілочисельна оптимізація набагато складніша. Рішення 2: знайти оптимальне реальне рішення. Округліть цифри вгору/вниз до наступного цілого числа. Оптимізація KM 20/21
23 Резюме Лінійна оптимізація (= максимізація (мінімізація) лінійної функції з n змінних при обмеженнях (обмеження - це рівняння та нерівності)) є дуже виразною і може бути ефективно вирішена. Цілочисельна лінійна оптимізація (вас цікавлять лише цілочисельні рішення) набагато виразніше, але важче вирішити. Результат ніколи не кращий, ніж модель та дані. Це стосується і моделювання. Стрес-тест для моделювання клімату в оптимізації банків KM 21/21
24 Резюме Лінійна оптимізація (= максимізація (мінімізація) лінійної функції з n змінних при обмеженнях (обмеження - це рівняння та нерівності)) є дуже виразною і може бути ефективно вирішена. Цілочисельна лінійна оптимізація (вас цікавлять лише цілочисельні рішення) набагато виразніше, але важче вирішити. Результат ніколи не кращий за модель та дані. Це стосується і моделювання. Стрес-тест для моделювання клімату в оптимізації банків KM 21/21