Оптимизационни проблеми: концепция, методи за решаване и класификация

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

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

История на развитието

Линейното програмиране (LP) се занимава с клас оптимизационни проблеми, при които всички ограничения са линейни.

Представя кратка история на развитието на LP:

• През 1762 г. Лагранж решава прости оптимизационни задачи с ограничения за равенство.
• През 1820 г. Гаус решава линейна система уравнения с помощта на изключване.
• През 1866 г. Уилям Джордан усъвършенства метода за намиране на грешки по метода на най-малките квадрати като критерий за съпоставяне. Сега се нарича по метода на Гаус-Jordan.
• През 1945 г. се появява цифровият компютър.
• През 1947 г. Данциг изобретява симплексните методи.
• През 1968 г. Фиако и Маккормик въвеждат метода на вътрешната точка.
• През 1984 г. Кармакар прилага метода на вътрешните точки за решаване на линейни програми, като добавя своя иновативен анализ.

LP се оказа изключително мощен инструмент, както за моделиране на реални проблеми, така и като широко прилагана математическа теория. Много интересни проблеми за оптимизация обаче са нелинейни.

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

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

Класификация на проблемите за оптимизация

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

1. Задачи за дискретна и непрекъсната оптимизация. Някои модели имат смисъл само ако променливите приемат стойности от дискретно подмножество от цели числа. Други съдържат данни, които могат да придобият реална стойност. Като цяло те са по-лесни за решаване. Усъвършенстването на алгоритмите, съчетано с напредъка на компютърните науки, значително увеличи размера и сложността на проблема за оптимизация линейно програмиране.

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

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

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

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

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

Основни компоненти

Целевата функция е тази, която трябва да бъде минимизирана или максимизирана. Повечето видове оптимизационни проблеми имат една целева функция. Ако не, те често могат да бъдат преформулирани по такъв начин, че да бъдат изпълнени.

Две изключения от това правило:

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

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

Видове компоненти:

• Контролираните входни данни са набор от променливи за вземане на решения, които влияят върху стойността на целевата функция. В производствен проблем променливите могат да включват разпределението на различните налични ресурси или необходимия труд за всяко действие.
• Ограниченията са връзките между променливите и параметрите на решението. За проблема с осъществимостта няма смисъл да се отделя голямо количество време за дадена дейност, затова ограничете всички "временни" променливи.
• Възможни и оптимални решения. Стойност на решението за променливите, където всички ограничения са изпълнени, то се нарича изпълнимо решение. Повечето алгоритми първо го намират, а след това се опитват да го подобрят. Накрая те променят променливите, за да преминат от едно изпълнимо решение към друго. Този процес се повтаря, докато целевата функция достигне своя максимум или минимум. Този резултат се нарича оптимално решение.

Широко се използват алгоритми за оптимизация, разработени за следните математически програми:

• Изпъкнал.
• Делимо .
• Квадратни.
• Геометричен.

Линейни решения на Google

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

Google предлага три начина за решаване на линейни оптимизационни задачи:

• Библиотека с отворен код Glop.
• Добавка за линейна оптимизация за Google Sheets.
• Услуга за линейна оптимизация в Google Apps Script.

Glop е вграденият линеен решевател на Google. Той е достъпен като отворен код. Достъпът до Glop се осъществява чрез пакета за линейни решения на OR-Tools, който представлява обвивка за Glop.

Модулът за линейна оптимизация за Google Sheets ви позволява да решавате задачи за линейна оптимизация чрез въвеждане на данни в електронна таблица.

Квадратно програмиране

Платформата Premium Solver използва разширена LP/квадратична версия на метода Simplex с ограничения за обработка на LP и QP проблеми до 2000 променливи решения.

SQP Solver за широкомащабни задачи използва съвременна реализация на метода на активното множество за решаване на задачи на квадратичното програмиране (QP). XPRESS Solver използва естествено продължение на метода "Вътрешна точка" или Newton-Barrier за решения на проблеми QP.

MOSEK Solver прилага методи за вграждане "Вътрешна точка" и самостоятелни. Това е особено ефективно за слабо свързани QP проблеми. Той може също така да решава задачи за мащабно квадратично ограничение (QCP) и конусно програмиране от втори ред (SOCP).

Многооперационни изчисления

Те се използват доста успешно с функциите на Microsoft Office, напр. решаване на оптимизационни задачи в Excel.

В горната таблица са използвани тези обозначения:

• K1 - K6 - клиенти, които трябва да предоставят продукта.
• S1 - S6 - потенциални производствени обекти, които могат да бъдат изградени за тази цел. Могат да бъдат създадени 1,2,3,4,5 или всички 6 локации.

За всяка позиция има фиксирани разходи, посочени в колона I (Фиксирани).

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

Идентифициране на потенциални местоположения за постигане на най-ниски разходи.

При дадени условия дадено местоположение или е зададено, или не е. Двете държави са: "TRUE - FALSE" или "1 - 0". Има шест състояния за шест места, например 000001 е зададено само за шесто място, 111111 е зададено за всички.

В двоичен запис има точно 63 различни варианта от 000001 (1) до 111111 (63).

L2-L64 сега трябва да бъде {= МНОГОКРАТНА ОПЕРАЦИЯ (K1)}, това са резултатите от всички алтернативи. Тогава минималната стойност е = Min (L), а съответната алтернатива е INDEX (K).

Целочислено програмиране CPLEX

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

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

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

Той също така използва LP и други методи за решаване на оптимизационни задачи за изчисляване на ограниченията.

Стандартно решение на Microsoft Excel

Използва се основна реализация на основния Simplex метод за решаване на задачи за LP. Тя е ограничена до 200 променливи. "Premium Solver" използва подобрен метод на първичния симплекс с двустранни граници за променливите. Премиум решаването използва разширена версия на решаването на LP/квадратичен симплекс за решаване на оптимизационен проблем с до 2000 променливи за решение.

Платформата Large-scale LP for Premium Solver прилага най-съвременната имплементация на прост и двоен симплекс метод, който използва рядкостта в LP модела, за да спести време и памет, усъвършенствани стратегии за актуализиране и рефакторизиране на матрици, многократно и частично ценообразуване и ротации, както и за преодоляване на дегенерацията. Този механизъм се предлага в три версии (с възможност за работа с до 8000, 32000 или неограничен брой променливи и ограничения).

MOSEK Solver включва първичен и двоен симплекс метод, който също така се възползва от рядкостта и използва усъвършенствани стратегии за актуализиране на матрици и "рефакторизиране". Той решава проблеми с неограничен размер и е тестван върху проблеми на линейното програмиране с милиони променливи за вземане на решения.

Пример стъпка по стъпка в EXCEL

За да дефинирате модел на оптимизационен проблем в Excel, изпълнете следните стъпки

• Организирайте данните за задачата в електронна таблица в в логическа форма.
• Изберете клетка да съхранявате на всяка променлива.
• Създаване на формула в клетка за изчисляване на целевия математически модел на оптимизационния проблем.
• Създаване на формули за изчисляване на лявата страна на всяко ограничение.
• Използване на диалози в Excel за информиране "Решаващ орган" за променливите на решението, целите, ограниченията и желаните граници тези параметри.
• Изпълнявайте "Решаващ орган", да намерите най-доброто решение.
• Създаване на лист в Excel.
• Подреждане на данните за задачата в Excel, където се изчисляват формулата за целевата функция и ограниченията.

В горната таблица сме запазили клетки B4, C4, D4 и E4 за представяне на променливите решение X 1, X 2, X 3 и X 4. Примери за решения:

• Моделът на продуктовата гама (печалбите за всеки продукт са 450, 1150, 800 и 400 USD) се въвежда съответно в клетки B5, C5, D5 и E5. Така се изчислява целта в F5 = B5 * B4 + C5 * C4 + D5 * D4 + E5 * E4 или F5: = SUMPRODUCT (B5: E5, B4: E4).
• В поле B8 въведете размера на ресурсите, необходими за всеки тип продукт.
• Формула за F8: = SUMPRODUCT (B8: E8, $ B$4: $ E$4).
• Копирайте тази формула в F9. Знаците на долара в B$4: E$4 показват, че този диапазон от клетки остава постоянен.
• В G8 въведете наличното количество от всеки вид ресурс, съответстващо на стойностите на ограниченията вдясно. Това позволява те да бъдат изразени по следния начин: F11<= G8: G11.
• Това е еквивалентно на четирите ограничения на F8<= G8, F9 <= G9, F10 <= G10 и F11 <= G11. Можете да въведете този набор директно в диалоговите прозорци на Solver заедно с условията за неотрицателност B4: E4> = 0

Области на приложение на метода

Линейната оптимизация има много практически приложения като пример за оптимизационен проблем:

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

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

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

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

Нито един успешен бизнес процес в света не е възможен без оптимизация. Съществуват много алгоритми за оптимизация. Някои методи са подходящи само за определени видове проблеми. Важно е да умеете да разпознавате техните характеристики и да избирате подходящ метод за решаване.