Математика ∩ Програмування

Оптимізація - безумовно один із найбагатших способів застосування інформатики та математики в реальному світі. Усі прагнуть щось оптимізувати: компанії хочуть максимізувати прибуток, заводи хочуть максимізувати ефективність, інвестори хочуть мінімізувати ризик, список просто можна продовжувати і продовжувати. Математичні інструменти для оптимізації також є одними з найбагатших математичних методів. Вони складають наріжний камінь цілої галузі, яка називається операційним дослідженням, і досягнення в цій галузі буквально змінюють світ.

Математичне поле називається комбінаторною оптимізацією, і ця назва походить від мети пошуку оптимальних рішень ефективніше, ніж вичерпний пошук за всіма можливостями. Ця публікація представить найголовнішу проблему у всій комбінаторній оптимізації, відому як лінійна програма. Ще краще, ми знаємо, як ефективно вирішувати лінійні програми, тому в наступних публікаціях ми напишемо програму, яка обчислює найбільш доступну дієту, відповідаючи рекомендованим стандартам охорони здоров’я.

Узагальнення конкретної лінійної програми

Більшість проблем оптимізації мають дві частини: цільову функцію, те, що ми хочемо максимізувати чи мінімізувати, та обмеження, правила, яких ми повинні дотримуватися, щоб отримати дійсне рішення. Як простий приклад ви можете мінімізувати кількість часу, витраченого на сплату податків (цільова функція), але ви, звичайно, не можете витратити на них негативну кількість часу (обмеження).

Наступний більш складний приклад є центральним елементом цього допису. Більшість людей хочуть мінімізувати кількість грошей, витрачених на їжу. У той же час потрібно підтримувати певний рівень харчування. Для чоловіків віком від 19 до 30 років Національний інститут охорони здоров’я США рекомендує 3,7 літра води на день, 1000 міліграмів кальцію на день, 90 міліграмів вітаміну С на день тощо.

Ми можемо поставити цю проблему харчування математично, просто використовуючи кілька змінних іграшок. Скажімо, у нас була можливість придбати якусь комбінацію апельсинів, молока та брокколі. Деякі приблизні оцінки [1] дають такий вміст/витрати на ці продукти. За 0,272 дол. США ви можете отримати 100 грам апельсина, що містить 53,2 мг кальцію, 40 мг вітаміну С і 87 г води. За 0,100 доларів США ви можете отримати 100 грамів незбираного молока, що містить 276 мг кальцію, 0 мг вітаміну С та 87 г води. Нарешті, за 0,381 дол. США ви можете отримати 100 грам брокколі, що містить 47 мг кальцію, 89,2 мг вітаміну С та 91 г води. Ось таблиця, що узагальнює цю інформацію:

Деякі спостереження: брокколі дорожча, але отримує найбільше з усіх трьох поживних речовин, цільне молоко не містить жодного вітаміну С, але отримує тонну кальцію по-справжньому дешево, а апельсини - десь посередині. Тож ви могли б, мабуть, поважитися з кількістю і зрозуміти, яка найдешевша корисна дієта. Проблема полягає в тому, що відбувається, коли ми включаємо сотні чи тисячі продуктів харчування та десятки рекомендацій щодо поживних речовин. Цей простий приклад лише для того, щоб допомогти нам створити приємну офіційність.

Тож давайте продовжувати це робити. Якщо ми позначаємо кількістю 100 г одиниць брокколі, яку ми вирішили придбати, а також кількістю молока та кількістю апельсинів, то ми можемо записати щоденну вартість їжі як

В інтересі бути компактним (і знову ж таки, будуючи загальне формулювання лінійного програмування), ми можемо витягти інформацію про ціну в єдиний вектор витрат, а також записати наші змінні як вектор. Ми неявно фіксуємо впорядкування змінних, яке підтримується протягом усієї проблеми, але вибір упорядкування не має значення. Тепер функція витрат - це лише внутрішній продукт (крапковий продукт) вектора витрат та вектора змінної. З якоїсь причини багато людей люблять писати це як, де позначає транспонування матриці, і ми уявляємо, що це і є матрицями розміру. Я дотримуватимусь внутрішнього позначення продуктової дужки.

Зараз для кожного типу їжі ми отримуємо певну кількість кожного поживного речовини, і сума цих поживних речовин повинна бути більшою за мінімальну рекомендацію. Наприклад, ми хочемо щонайменше 1000 мг кальцію на день, тому нам цього потрібно. Так само ми можемо записати таблицю обмежень, переглянувши стовпці нашої таблиці вище.

Так само, як ми виділили дані про витрати у вектор, щоб відокремити їх від змінних, ми можемо вилучити всі дані про поживні речовини в матрицю, а рекомендовані мінімуми - у вектор. Традиційно буква використовується для вектора мінімумів, але наразі ми використовуємо для брокколі.

І тепер обмеження полягає в тому, де означає "більше або дорівнює в кожній координаті". Тож тепер ми можемо записати більш загальну форму задачі для наших конкретних матриць та векторів. Тобто, наша проблема полягає в тому, щоб звести до мінімуму обмеження, яке обмежує. Це часто пишуть у зміщеній формі, щоб протиставити його варіаціям, які ми трохи побачимо:

Загалом немає жодної причини, що у вас не може бути “від’ємної” суми однієї змінної. У цій проблемі ви не можете придбати негативну брокколі, тому ми додамо обмеження, щоб переменні не були негативними. Отже, наша остаточна форма така

Загалом, якщо у вас є матриця, вектор “мінімумів” та вектор витрат, проблема пошуку вектора, який мінімізує функцію витрат при задоволенні обмежень, називається проблемою лінійного програмування або просто лінійною програмою.

Щоб задовольнити пекучу цікавість читача, рішення проблеми з кальцієм/вітаміном С є приблизно. Тобто у вас повинно бути близько 100 г брокколі та 4,2 кг молока (наприклад, 4 літри), і повністю пропустити апельсини. Щоденна вартість близько 4,53 USD. Якщо це здається незручно великим, це тому, що є дешевші способи отримати воду, ніж молоко.

100 г брокколі (джерело зображення: 100-grams.blogspot.com)

Подвійність

Тепер, коли ми побачили загальну форму лінійної програми та милий приклад, ми можемо поставити справжнє м’ясо запитання: чи існує ефективний алгоритм, який вирішує довільні лінійні програми? Незважаючи на те, наскільки широко застосовуються ці проблеми, відповідь так!

Але перед тим, як ми можемо описати алгоритм, нам потрібно знати більше про лінійні програми. Наприклад, скажімо, у вас є вектор, який задовольняє вашим обмеженням. Як ви можете визначити, чи це оптимально? Без такого тесту ми не змогли б знати, коли припинити наш алгоритм. Інша проблема полягає в тому, що ми сформулювали проблему з точки зору мінімізації, але як щодо проблем, де ми хочемо максимізувати речі? Чи можемо ми використовувати той самий алгоритм, який знаходить мінімуми, щоб також знайти максимуми?

На обидві ці проблеми чітко відповідає теорія подвійності. У математиці загалом найкращий спосіб зрозуміти, що люди розуміють під «подвійністю», - це те, що один математичний об’єкт однозначно визначає дві різні точки зору, кожна корисна по-своєму. І, як правило, теорема про двоїстість забезпечує один ефективний спосіб перетворення однієї точки зору в іншу та співвідношення отриманої інформації з обох перспектив. Теорія подвійності вважається прекрасною, тому що вона дає вам справді глибоке розуміння математичного об'єкта, який вам важливий.

У лінійному програмуванні подвійність знаходиться між максимізацією та мінімізацією. Зокрема, кожна задача максимізації має унікальну “подвійну” проблему мінімізації, і навпаки. Дійсно цікаво, що змінні, які ви намагаєтеся оптимізувати в одній формі, відповідають контрантантам в іншій формі! Ось як можна виявити таку прекрасну листування. Для спрощення ситуації ми використаємо вигаданий приклад із невеликими цифрами.

Отже, у вас є ця проблема оптимізації

Просто для хихикання давайте випишемо, що і є.

Скажімо, ви хочете придумати нижчу межу оптимального рішення вашої проблеми. Тобто ви хочете знати, що ви не можете зробити менше, ніж деяке число. Обмеження можуть допомогти нам отримати такі нижчі межі. Зокрема, кожна змінна повинна бути невід’ємною, тому ми це знаємо, і тому 6 є нижньою межею нашого оптимуму. Так само,

і це ще нижча межа, ніж 6. Ми могли б спробувати записати цей підхід загалом: знайти кілька чисел, які ми будемо використовувати для кожного обмеження для формування

Щоб зробити його допустимою нижньою межею, нам потрібно забезпечити, щоб коефіцієнти кожного з них були меншими, ніж коефіцієнти цільової функції (тобто, щоб коефіцієнт закінчувався менше 4). І щоб зробити його найкращою нижньою межею, ми хочемо максимізувати розмір правої нерівності:. Якщо ви запишете ці рівняння та обмеження, ви отримаєте нашу задачу "нижньої межі", записану як

І чи не знаєте ви, матриця, яка забезпечує обмеження, - це вектори та місця, що перемикаються.

Це не випадково. Усі лінійні програми можуть бути трансформовані таким чином, і для читача було б корисно вправити перетворити вищезазначену проблему максимізації назад у задачу мінімізації за допомогою тієї ж техніки (обчислення лінійних комбінацій обмежень для вироблення верхніх меж). Ви здивуєтесь, коли повернетесь до початкової проблеми мінімізації! Це частина того, що робить його «подвійністю», тому що подвійне подвійне - це знову ж оригінальна річ. Часто, коли ми фіксуємо “оригінальну” проблему, ми називаємо її первинною формою, щоб відрізнити її від подвійної форми. Зазвичай первинна проблема - це проблема, яку легко інтерпретувати.

(Примітка: оскільки на сьогодні ми закінчили з брокколі, ми будемо використовувати його для позначення вектора обмеження, який був раніше.)

Тепер скажімо, що вам надано дані лінійної програми для мінімізації, тобто векторів та матриці для задачі, "звести до мінімуму". Ми можемо скласти загальне визначення: подвійна лінійна програма є проблемою максимізації, “максимізувати за умови”. Ось новий набір змінних, а верхній індекс Т позначає транспонування матриці. Обмеження для дуалу часто пишуть, знову ж ідентифікуючи вектори з матрицями в один стовпець, але я вважаю болото транспонувань безглуздим і надокучливим (чому речі повинні бути стовпцями?).

Тепер ми можемо фактично довести, що цільова функція для подвійного забезпечує зв’язок з цільовою функцією для вихідної задачі. Це очевидно з роботи, яку ми зробили, саме тому вона називається теоремою слабкої дуальності.

Теорема слабкої двоїстості: Нехай - дані лінійної програми в первинній формі (задача мінімізації), цільовою функцією якої є. Нагадаємо, що цільовою функцією подвійної (максимізаційної) задачі є. Якщо є можливими рішеннями (задовольняють обмеження відповідних проблем), то

Іншими словами, максимум подвійного є нижньою межею мінімуму первинної задачі і навпаки. Більше того, будь-яке можливе рішення для одного забезпечує зв'язок з іншим.

Доказ. Доказ приємно простий. Просто огляньте кількість. Обмеження з визначень первинного та подвійного дають нам це

Нерівності випливають з факту лінійної алгебри: якщо in невід'ємне, то можна збільшити розмір добутку, лише збільшивши компоненти. Ось чому нам потрібні обмеження невід’ємності.

Насправді світ набагато приємніший. Існує теорема, яка говорить, що два оптимуми рівні!

Теорема сильної подвійності: Якщо є будь-які рішення первинної (мінімізаційної) задачі та подвійної (максимізаційної) відповідно, то ці дві проблеми також мають оптимальні рішення, і два рішення-кандидати є оптимальними тоді і лише тоді, коли вони дають однакові цільові значення .

Доказ цієї теореми є дещо складнішим, ніж теорема про слабку двоїстість, і ключовим прийомом є лема Фаркаса та її варіацій. Див. Другу половину цих приміток для повного підтвердження. Приємно те, що ця теорема дає нам спосіб визначити, чи виконаний алгоритм розв’язування лінійних програм: підтримувати пару можливих рішень первинних та подвійних задач, вдосконалювати їх за якимось правилом і зупинятись, коли два рішення дають рівні об'єктивні цінності. Тож важкою частиною є пошук принципового та гарантованого способу вдосконалення даної пари рішень.

З іншого боку, ви також можете довести сильну теорему подвійності, вигадавши алгоритм, який доказово припиняється. Ми побачимо такий алгоритм, відомий як симплексний алгоритм, у наступному дописі. Крадькома: це дуже схоже на елімінацію Гауса. Тоді ми використовуватимемо алгоритм (або еквівалентну галузеву версію) для вирішення набагато більшої проблеми харчування.

Насправді ви можете зробити трохи краще, ніж теорема про сильну подвійність, з точки зору висунення умови зупинки для алгоритму лінійного програмування. Ви можете помітити, що оптимальне рішення передбачає додаткові обмеження щодо взаємозв'язку між первинною та подвійною проблемами. Зокрема, це називається додатковими умовами в'ялості, і вони по суті кажуть, що якщо оптимальне рішення первинного елемента має додатну змінну, тоді відповідне обмеження в подвійній задачі повинно бути жорстким (це рівність), щоб отримати оптимальне рішення подвійний. Протилежне говорить, що якщо якесь обмеження є слабким або сувора нерівність, то або відповідна змінна дорівнює нулю, або рішення не є оптимальним. Більш формально,

Теорема (додаткові умови млявості): Нехай будуть дані первинної форми лінійної програми, "звести до мінімуму". Тоді є оптимальними рішеннями первинних та подвійних задач, якщо такі є, лише якщо виконуються всі наступні умови.

обидва можливі для відповідних проблем.
Щоразу, коли 0 "title =" x ^ * _ i> 0 "/> відповідне обмеження є рівністю.
Щоразу, коли 0 "title =" y ^ * _ j> 0 "/> відповідне обмеження є рівністю.

Тут ми позначаємо -th рядком матриці і позначаємо -th запис вектора. Іншим способом написання умови за допомогою векторів замість англійської є

Доведення випливає з теорем двоїстості і передбачає просторування навколо деякої векторної алгебри. Див. Розділ 6.2 цих приміток.

Можна інтерпретувати додаткову млявість у лінійних програмах різними способами. Для нас це буде просто умовою припинення для алгоритму: можна ефективно перевірити всі ці умови для ненульових змінних і зупинитися, якщо всі вони задоволені або якщо ми знайдемо змінну, яка порушує умову млявості. Дійсно, при більш зрілому оптимізаційному аналізі стан в’ялості, який більш грубо порушується, може надати докази того, де найкраще можна покращити рішення кандидата. Для більш хитромудрого та детального оповідання про те, як інтерпретувати додаткові умови млявості, див. Розділ 4 цих приміток Джоеля Собеля.

Нарешті, перед тим, як закрити, слід зазначити, що є геометричні способи думати про лінійне програмування. У моїй голові вподобана візуалізація, але я ще не знайшов відповідної анімації в Інтернеті, яка б її повторювала. Ось один приклад у двох вимірах. Набір обмежень визначає опуклу геометричну область на площині

Обмеження визначають опуклу область «можливих рішень». Джерело зображення: Вікіпедія.

Тепер функція оптимізації також є лінійною функцією, і якщо ви зафіксуєте якесь вихідне значення, це визначає лінію в площині. Змінюючись, лінія рухається по своєму нормальному вектору (тобто всі ці нерухомі лінії паралельні). Тепер, щоб геометрично оптимізувати цільову функцію, ми можемо уявити, що починаємо з лінії та ковзаємо її вздовж її нормального вектора у напрямку, який утримує її у здійсненній області. Ми можемо продовжувати ковзати в цьому напрямку, і максимум функції - це лише останній момент, коли ця лінія перетинає можливу область. Якщо жодне з обмежень не паралельне сімейству прямих, визначених, то це гарантовано відбуватиметься у вершині можливої області. В іншому випадку буде сімейство оптимумів, що лежать де завгодно на відрізку останнього перетину.

У вищих вимірах єдина зміна полягає в тому, що лінії стають афінними підпросторами розмірності. Це означає, що в трьох вимірах ви ковзаєте площинами, в чотирьох вимірах ви ковзаєте тривимірними гіперплощинами і т. Д. Факти про останнє перетину, яке є вершиною або “відрізком лінії”, все ще зберігаються. Отож, як ми побачимо наступного разу, успішні алгоритми лінійного програмування на практиці використовують переваги цього спостереження, ефективно обходячи вершини цієї опуклої області. Ми побачимо це набагато детальніше в наступному дописі.