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

Математическото поле се нарича комбинаторна оптимизация и името идва от целта за по-ефективно намиране на оптимални решения, отколкото изчерпателно търсене чрез всяка възможност. Тази публикация ще представи най-централния проблем във всички комбинаторни оптимизации, известен като линейна програма. Още по-добре, ние знаем как ефективно да решаваме линейни програми, така че в бъдещи публикации ще напишем програма, която изчислява най-достъпната диета, като същевременно отговаря на препоръчания здравен стандарт.

Генерализиране на конкретна линейна програма

Повечето проблеми с оптимизацията се състоят от две части: целева функция, нещото, което искаме да увеличим или сведем до минимум, и ограничения, правила, които трябва да спазваме, за да гарантираме, че получаваме валидно решение. Като прост пример може да искате да минимизирате времето, което отделяте за извършване на данъците си (целева функция), но със сигурност не можете да отделите отрицателно време за тях (ограничение).

Следващият по-сложен пример е в центъра на тази публикация. Повечето хора искат да минимизират количеството пари, похарчени за храна. В същото време човек трябва да поддържа определено ниво на хранене. За мъже на възраст 19-30 години Националният здравен институт на САЩ препоръчва 3,7 литра вода на ден, 1000 милиграма калций на ден, 90 милиграма витамин С на ден и т.н.

Можем да зададем този хранителен проблем математически, като използваме само няколко променливи играчки. Да речем, че имахме възможността да си купим някаква комбинация от портокали, мляко и броколи. Някои груби оценки [1] дават следното съдържание/разходи на тези храни. За 0,272 USD можете да получите 100 грама портокал, съдържащ общо 53,2 mg калций, 40 mg витамин С и 87 g вода. За 0.100 USD можете да получите 100 грама пълномаслено мляко, съдържащо 276 mg калций, 0 mg витамин С и 87 g вода. И накрая, за 0,381 USD можете да получите 100 грама броколи, съдържащи 47 mg калций, 89,2 mg витамин С и 91 g вода. Ето таблица, обобщаваща тази информация:

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

Така че нека продължим да правим това. Ако обозначим с броя на 100g единици броколи, които решим да купим, и количеството мляко и количеството портокали, тогава можем да запишем дневните разходи за храна като

В интерес на това да бъдем компактни (и отново, изграждайки към общата формулировка за линейно програмиране) можем да извлечем информацията за цената в един векторен разход и по същия начин да запишем нашите променливи като вектор. По подразбиране фиксираме подреждане на променливите, което се поддържа през целия проблем, но изборът на подреждане няма значение. Сега функцията на разходите е само вътрешният продукт (точков продукт) на вектора на разходите и на променливия вектор. По някаква причина много хора обичат да пишат това като, където означава транспонирането на матрица и ние си представяме, че това са матрици с размер. Ще се придържам към използването на нотацията на вътрешната скоба на продукта.

Сега за всеки вид храна получаваме точно определено количество от всяко хранително вещество и сумата от тези хранителни вещества трябва да бъде по-голяма от минималната препоръка. Например искаме поне 1000 mg калций на ден, така че се нуждаем от това. По същия начин можем да изпишем таблица с ограниченията, като разгледаме колоните на нашата таблица по-горе.

По същия начин, по който извлекохме данните за разходите във вектор, за да ги отделим от променливите, можем да извлечем всички данни за хранителните вещества в матрица и препоръчителните минимуми във вектор. Традиционно буквата се използва за вектора на минимумите, но засега използваме за броколи.

И сега ограничението е това, където означава „по-голямо или равно на всяка координата“. Така че сега можем да запишем по-общата форма на задачата за нашите специфични матрици и вектори. Тоест, нашият проблем е да сведем до минимум обекта, който се ограничава. Това често се пише в офсетна форма, за да се контрастира с вариации, които ще видим след малко:

Като цяло няма причина да не можете да имате „отрицателно“ количество от една променлива. В този проблем не можете да купувате отрицателни броколи, затова ще добавим ограниченията, за да гарантираме, че променливите са неотрицателни. Така че нашата окончателна форма е

Като цяло, ако имате матрица, вектор „минимуми“ и вектор на разходите, проблемът с намирането на вектора, който минимизира функцията на разходите, докато отговаря на ограниченията, се нарича проблем с линейно програмиране или просто линейна програма.

За да задоволим изгарящото любопитство на читателя, решението на проблема с нашия калций/витамин С е приблизително. Тоест, трябва да имате около 100 г броколи и 4,2 кг мляко (като 4 литра) и да пропуснете портокалите изцяло. Дневните разходи са около 4,53 USD. Ако това изглежда неловко голямо, това е така, защото има по-евтини начини за получаване на вода от млякото.

програмиране

100 г броколи (източник на изображение: 100-grams.blogspot.com)

Двойственост

Сега, когато видяхме общата форма на линейна програма и сладък пример, можем да зададем истинския месест въпрос: има ли ефективен алгоритъм, който решава произволни линейни програми? Въпреки колко широко приложими изглеждат тези проблеми, отговорът е да!

Но преди да можем да опишем алгоритъма, трябва да знаем повече за линейните програми. Например, да кажем, че имате някакъв вектор, който отговаря на вашите ограничения. Как можете да разберете дали е оптимално? Без такъв тест нямаше как да знаем кога да прекратим нашия алгоритъм. Друг проблем е, че сме го формулирали от гледна точка на минимизиране, но какво да кажем за проблемите, при които искаме да максимизираме нещата? Можем ли да използваме същия алгоритъм, който намира минимуми, за да намерим и максимумите?

И двата проблема са добре отговорени от теорията за двойствеността. Като цяло в математиката най-добрият начин да разберем какво означават хората под „двойственост“ е, че един математически обект уникално определя две различни перспективи, всяка полезна по свой начин. И обикновено теоремата за двойствеността предоставя на един ефективен начин за трансформиране на една перспектива в друга и свързване на информацията, която получавате от двете перспективи. Теорията за двойствеността се счита за красива, защото ви дава наистина дълбока представа за математическия обект, който ви интересува.

При линейното програмиране двойствеността е между максимизиране и минимизиране. По-специално, всеки максимизационен проблем има уникален проблем с „двойно“ минимизиране и обратно. Наистина интересното е, че променливите, които се опитвате да оптимизирате в една форма, съответстват на контрантите в другата форма! Ето как човек може да открие толкова красива кореспонденция. Ще използваме измислен пример с малки числа, за да улесним нещата.

Така че имате този проблем с оптимизацията

Само за кикотене, нека напишем какво и какво сме.

Кажете, че искате да излезете с долна граница на оптималното решение на вашия проблем. Тоест, искате да знаете, че не можете да направите по-малко от някакво число. Ограниченията могат да ни помогнат да извлечем такива по-ниски граници. По-специално, всяка променлива трябва да бъде неотрицателна, така че ние знаем това и така 6 е долна граница на нашия оптимум. По същия начин,

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

За да го направим валидна долна граница, трябва да гарантираме, че коефициентите на всеки от са по-малки от коефициентите в целевата функция (т.е. коефициентът на завършва по-малко от 4). И за да го направим възможно най-добрата долна граница, искаме да увеличим максимално размера на десния размер на неравенството:. Ако запишете тези уравнения и ограниченията, ще получите нашия проблем с „долната граница“, записан като

И не бихте ли знаели, матрицата, осигуряваща ограниченията е, и векторите и превключените места.

Това не е случайно. Всички линейни програми могат да бъдат трансформирани по този начин и би било полезно упражнението за читателя да превърне горния проблем с максимизацията отново в проблем за минимизиране чрез същата техника (изчисляване на линейни комбинации от ограниченията, за да се направят горни граници). Ще бъдете изненадани да откриете, че се връщате към първоначалния проблем за минимизиране! Това е част от това, което го прави „двойственост“, защото дуалното на дуалното отново е оригиналното. Често, когато поправяме „оригиналния“ проблем, ние го наричаме първична форма, за да го разграничим от дуалната форма. Обикновено основният проблем е този, който е лесен за тълкуване.

(Забележка: тъй като засега сме приключили с броколите, ще използваме, за да обозначим предишния вектор на ограничението.)

Сега кажете, че сте получили данните от линейна програма за минимизиране, т.е. векторите и матрицата за проблема, „минимизиране подлежи на“. Можем да направим обща дефиниция: двойната линейна програма е максимизационният проблем, „максимизиране в зависимост от това“. Ето новия набор от променливи и горният индекс T означава транспонирането на матрицата. Ограничението за дуалното често се пише, като отново се идентифицират вектори с матрици с една колона, но намирам, че блатото от транспониране е безсмислено и досадно (защо нещата трябва да бъдат колони?).

Сега можем действително да докажем, че целевата функция за дуалното осигурява обвързаност с целевата функция за първоначалния проблем. Очевидно е от работата, която сме свършили, поради което се нарича теорема за слабата двойственост.

Теорема за слабата двойственост: Позволете да бъдат данните на линейна програма в първичната форма (задачата за минимизиране), чиято целева функция е. Припомнете си, че целевата функция на дуалния (максимизиращ) проблем е. Ако са възможни решения (отговарят на ограниченията на съответните им проблеми), тогава

С други думи, максимумът на дуалното е долна граница на минимума на първоначалния проблем и обратно. Освен това, всяко осъществимо решение за едното осигурява обвързване с другото.

Доказателство. Доказателството е приятно просто. Просто инспектирайте количеството. Ограниченията от дефинициите на първичното и дуалното ни дават това

Неравенствата произтичат от факта на линейната алгебра, че ако in е неотрицателен, тогава можете да увеличите размера на продукта само чрез увеличаване на компонентите на. Ето защо се нуждаем от ограниченията за неотрицателност.

Всъщност светът е много по-приятен. Има теорема, която казва, че двата оптимума са равни!

Теорема за силна двойственост: Ако има някакви решения на първоначалния (минимизиращ) проблем и съответно на дуалния (максимизиращ) проблем, тогава двата проблема също имат оптимални решения, а две кандидат-решения са оптимални, ако и само ако произвеждат еднакви обективни стойности .

Доказателството за тази теорема е малко по-объркано от теоремата за слабата двойственост и ключовата техника е лема на Фаркас и нейните вариации. Вижте втората половина на тези бележки за пълно доказателство. Хубавото е, че тази теорема ни дава начин да разберем дали е направен алгоритъм за решаване на линейни програми: поддържаме двойка възможни решения на първичните и двойните задачи, подобряваме ги с някакво правило и спираме, когато двете решения дават равни обективни ценности. Тогава трудната част е намирането на принципен и гарантиран начин за подобряване на дадена двойка решения.

От друга страна, можете също да докажете силната теорема за двойствеността, като измислите алгоритъм, който доказуемо прекратява. Ще видим такъв алгоритъм, известен като симплекс алгоритъм в следващата публикация. Подъл поглед: много прилича на елиминирането на Гаус. След това ще използваме алгоритъма (или еквивалентна версия за индустрията), за да решим много по-голям проблем с храненето.

Всъщност можете да направите малко по-добре от теоремата за силната двойственост, по отношение на изготвянето на условие за спиране за алгоритъм за линейно програмиране. Можете да забележите, че оптималното решение предполага допълнителни ограничения върху връзката между първичните и двойствените проблеми. По-специално, това се нарича допълнителни условия на отпуснатост и те по същество казват, че ако оптималното решение на първичното има положителна променлива, тогава съответното ограничение в двойствения проблем трябва да бъде строго (е равенство), за да се получи оптимално решение на двоен. Противоположното казва, че ако някакво ограничение е хлабаво или строго неравенство, тогава или съответната променлива е нула, или решението не е оптимално. По-формално,

Теорема (допълнителни условия на отпуснатост): Позволявам да бъдат данните на първичната форма на линейна програма, „минимизиране на предмет.“ Тогава са оптимални решения на първичните и двойните проблеми, ако има такива, само ако са налице всички от следните условия.

  • са изпълними и за съответните им проблеми.
  • Винаги, когато 0 "title =" x ^ * _ i> 0 "/> съответното ограничение е равенство.
  • Винаги, когато 0 "title =" y ^ * _ j> 0 "/> съответното ограничение е равенство.

Тук ние обозначаваме с -тия ред на матрицата и за означаване на -тия запис на вектор. Друг начин да напишете условието, като използвате вектори вместо английски, е

Доказателството следва от теоремите за двойствеността и просто включва прокарване на някаква векторна алгебра. Вижте раздел 6.2 от тези бележки.

Човек може да интерпретира допълнителната отпуснатост в линейните програми по много различни начини. За нас това просто ще бъде условие за прекратяване на алгоритъм: човек може ефективно да провери всички тези условия за ненулевите променливи и да спре, ако всички са удовлетворени или ако намерим променлива, която нарушава условието за отпускане. В действителност, при по-зрели анализи за оптимизация, състоянието на отпуснатост, което е по-грубо нарушено, може да предостави доказателства за това къде дадено решение за кандидатстване може да бъде най-добре подобрено. За по-сложна и подробна история за това как да се тълкуват допълнителните условия на отпуснатост, вижте раздел 4 от тези бележки от Джоел Собел.

И накрая, преди да приключим, трябва да отбележим, че има геометрични начини да се мисли за линейно програмиране. Имам предпочитана визуализация в главата си, но все още не съм намерил подходяща анимация в мрежата, която да я възпроизвежда. Ето един пример в две измерения. Наборът от ограничения дефинира изпъкнала геометрична област в равнината

Ограниченията определят изпъкнала област на „изпълними решения“. Източник на изображението: Уикипедия.

Сега функцията за оптимизация също е линейна функция и ако фиксирате някаква изходна стойност, това определя линия в равнината. При промяна линията се движи по своя нормален вектор (т.е. всички тези фиксирани линии са успоредни). Сега, за да оптимизираме геометрично целевата функция, можем да си представим, че започваме с линията и я плъзгаме по нейния нормален вектор в посоката, която я задържа в възможната област. Можем да продължаваме да го плъзгаме в тази посока и максимумът на функцията е само последният момент, в който тази линия пресича възможния регион. Ако нито едно от ограниченията не е успоредно на семейството линии, дефинирани от, тогава това е гарантирано, че ще се случи във връх на възможния регион. В противен случай ще има семейство оптими, разположени навсякъде в отсечката на последното пресичане.

При по-високите измерения единствената промяна е, че линиите стават афинирани подпространства на измерението. Това означава, че в три измерения сте плъзгащи се равнини, в четири измерения сте плъзгащи триизмерни хиперплоскости и т.н. Фактите за последното пресичане е връх или „отсечка от права“ все още са валидни. Така че, както ще видим следващия път, успешните алгоритми за линейно програмиране на практика се възползват от това наблюдение, като ефективно обхождат върховете на тази изпъкнала област. Ще видим това много по-подробно в следващата публикация.