Оптимизацията ви помага да намерите най-добрия резултат, който носи печалба, намалява разходите или задава параметър, който причинява неуспехи в бизнес процесите.
Този процес се нарича още математическо програмиране. Той решава задачата за определяне на разпределението на ограничените ресурси, необходими за постигане на целта, поставена от ръководителя на задачата за оптимизация. От всички възможни опции е желателно да се намери този, който максимизира (или намалява) контролния параметър, например печалба или цена. Моделите за оптимизация се наричат още предписващи или нормативни, защото се стремят да намерят осъществима стратегия за бизнеса.
История на развитие
Линейното програмиране (LP) работи с клас оптимизационни проблеми, където всички ограничения са линейни.
Представяме кратка история на развитието на LP:
- През 1762 г. Лагранж решава прости оптимизационни проблеми с ограничения за равенство.
- През 1820 г. Гаус решавалинейна система от уравнения, използваща елиминиране.
- През 1866 г. Вилхелм Джордан усъвършенства метода за намиране на грешките на най-малките квадрати като критерий за прилягане. Сега това се нарича метод на Гаус-Йордан.
- Цифровият компютър се появява през 1945 г.
- Данциг изобретява симплекс методи през 1947 г.
- През 1968 г. Фиако и Маккормик въвеждат метода Inside Point.
- През 1984 г. Кармаркар прилага вътрешния метод за решаване на линейни програми, добавяйки своя новаторски анализ.
LP се оказа изключително мощен инструмент както за моделиране на проблеми от реалния свят, така и като широко прилагана математическа теория. Въпреки това, много интересни оптимизационни проблеми са нелинейни.
Какво да направите в този случай? Изучаването на такива проблеми включва разнообразна смес от линейна алгебра, многовариантно смятане, числен анализ и изчислителни методи. Учените разработват изчислителни алгоритми, включително вътрешни точкови методи за линейно програмиране, геометрия, анализ на изпъкнали множества и функции и изучаване на специално структурирани проблеми като квадратично програмиране.
Нелинейната оптимизация предоставя фундаментално разбиране на математическия анализ и се използва широко в различни области като инженерство, регресионен анализ, управление на ресурсите, геофизично проучване и икономика.
Класификация на оптимизационни проблеми
Важна стъпкаПроцесът на оптимизация е класификацията на моделите, тъй като техните алгоритми за решение са адаптирани към определен тип.
1. Проблеми с дискретна и непрекъсната оптимизация. Някои модели имат смисъл само ако променливите вземат стойности от дискретно подмножество цели числа. Други съдържат данни, които могат да придобият всякаква реална стойност. Те обикновено са по-лесни за решаване. Подобренията в алгоритмите, комбинирани с напредъка в компютърните технологии, драстично увеличиха размера и сложността на оптимизационния проблем за линейно програмиране.
2. Неограничена и ограничена оптимизация. Друга важна разлика са задачите, при които няма ограничение за променливи. Тя може да варира в широки граници от прости оценки до системи от равенства и неравенства, които моделират сложни връзки между данните. Такива оптимизационни проблеми могат да бъдат допълнително класифицирани според естеството на функциите (линейни и нелинейни, изпъкнали и гладки, диференцируеми и недиференцируеми).
3. Задачи за осъществимост. Тяхната цел е да намерят променливи стойности, които отговарят на ограниченията на модела без конкретна цел за оптимизиране.
4. Задачи за допълване. Те намират широко приложение в технологиите и икономиката. Целта е да се намери решение, което отговаря на условията за допълване. На практика задачите с няколко цели често се преформулират в такива с една цел.
5. Детерминистична срещу стохастична оптимизация. Детерминистичната оптимизация предполага, че данните зазаданията са напълно точни. Въпреки това, по много актуални въпроси те не могат да бъдат известни по редица причини.
Първата е свързана с проста грешка при измерване. Втората причина е по-фундаментална. Той се крие във факта, че някои данни представляват информация за бъдещето, например търсенето на продукт или цената за бъдещ период от време. При оптимизиране при условия на стохастична оптимизация, несигурността е включена в модела.
Основни компоненти
Целевата функция е тази, която трябва да бъде минимизирана или максимизирана. Повечето видове оптимизационни проблеми имат една целева функция. Ако не, те често могат да бъдат преформулирани, за да работят.
Две изключения от това правило:
1. Целева задача за търсене. В повечето бизнес приложения мениджърът иска да постигне конкретна цел, като същевременно удовлетворява ограниченията на модела. Потребителят не иска особено да оптимизира нещо, така че няма смисъл да се дефинира целева функция. Този тип обикновено се нарича проблем със задоволимостта.
2. Много обективни характеристики. Често потребителят би искал да оптимизира няколко различни цели наведнъж. Обикновено са несъвместими. Променливите, които оптимизират за една цел, може да не са най-добрите за други.
Видове компоненти:
- Контролираният вход е набор от променливи за решение, които влияят върху стойността на целева функция. В производствена задача променливите могат да включват разпределението на различните налични ресурси или необходимия трудвсяко действие.
- Ограниченията са връзки между променливи и параметри на решението. За производствен проблем няма смисъл да отделяте много време за каквато и да е дейност, така че ограничете всички "временни" променливи.
- Възможни и оптимални решения. Стойността на решението за променливи, при които са изпълнени всички ограничения, се нарича удовлетворяема. Повечето алгоритми първо го намират, след което се опитват да го подобрят. И накрая, те променят променливите, за да преминат от едно осъществимо решение към друго. Този процес се повтаря, докато целевата функция достигне своя максимум или минимум. Този резултат се нарича оптимално решение.
Алгоритмите за оптимизационни задачи, разработени за следните математически програми, са широко използвани:
- Изпъкнал.
- Разделя се.
- Quadratic.
- Геометричен.
Google Linear Solvers
Линейна оптимизация или програмиране е името, дадено на изчислителния процес за оптимално решаване на проблем. Той е моделиран като набор от линейни връзки, които възникват в много научни и инженерни дисциплини.
Google предлага три начина за решаване на проблеми с линейната оптимизация:
- Glop библиотека с отворен код.
- Добавка за линейна оптимизация за Google Таблици.
- Услуга за линейна оптимизация в Google Apps Script.
Glop е вграден в Googleлинеен решаващ. Предлага се в отворен код. Можете да получите достъп до Glop чрез OR-Tools linear Solver wrapper, който е обвивка за Glop.
Модул за линейна оптимизация за Google Sheets ви позволява да изпълните линейна формулировка на проблема за оптимизация чрез въвеждане на данни в електронна таблица.
Квадратично програмиране
Платформата Premium Solver използва разширена LP/Quadratic версия на метода Simplex с LP и QP ограничения за обработка на проблеми до 2000 променливи за решение.
SQP Solver за широкомащабни проблеми използва модерна реализация на метода на активния набор с рядкост за решаване на проблеми с квадратично програмиране (QP). Двигателят XPRESS Solver използва естествено разширение на метода "Interior Point" или Newton Barrier за решаване на QP проблеми.
MOSEK Solver прилага вградени „Вътрешна точка“и автоматични двойни методи. Това е особено ефективно при слабо свързани QP проблеми. Може също така да реши проблемите с мащабното квадратично ограничение (QCP) и програмирането на конус от втори ред (SOCP).
Изчисления с няколко операции
Те се използват доста успешно с използването на функции на Microsoft Office, например за решаване на оптимизационни проблеми в Excel.
В горната таблица символите са:
- K1 - K6 - клиенти, които трябва да предоставят стоки.
- S1 - S6 са потенциални производствени обекти, които могат да бъдат изградени за това. Може да се създаде1, 2, 3, 4, 5 или всичките 6 местоположения.
Има фиксирани разходи за всяко съоръжение, изброено в колона I (поправка).
Ако местоположението не промени нищо, то няма да се брои. Тогава няма да има фиксирани разходи.
Определете потенциални местоположения, за да получите най-ниската цена.
При тези условия местоположението или е установено, или не. Тези две състояния са: "ВЯРНО - НЕВЕРНО" или "1 - 0". Има шест състояния за шест местоположения, например 000001 е настроен само на шестото, 111111 е настроен на всички.
В двоичната бройна система има точно 63 различни опции от 000001 (1) до 111111 (63).
L2-L64 вече трябва да се чете {=МНОГООПЕРАЦИЯ (K1)}, това са резултатите от всички алтернативни решения. Тогава минималната стойност е=Min (L) и съответната алтернатива е INDEX (K).
CPLEX целочислено програмиране
Понякога линейната връзка не е достатъчна, за да стигнем до същността на бизнес проблем. Това е особено вярно, когато решенията включват дискретен избор, като например дали да се отвори или не склад на определено място. В тези ситуации трябва да се използва целочислено програмиране.
Ако проблемът включва както дискретни, така и непрекъснати избори, това е програма със смесено цяло число. Може да има линейни, изпъкнали квадратични проблеми и същите ограничения от втори ред.
Целочисленните програми са много по-сложни от линейните, но имат важни бизнес приложения. софтуерСофтуерът CPLEX използва сложни математически методи за решаване на задачи с цели числа. Неговите методи включват систематично търсене на възможни комбинации от дискретни променливи с помощта на линейни или квадратични софтуерни релаксации за изчисляване на границите на стойността на оптималното решение.
Те също използват LP и други методи за решаване на проблеми за оптимизация за изчисляване на ограничения.
Стандартен Microsoft Excel Solver
Тази технология използва основното изпълнение на основния симплекс метод за решаване на проблеми с LP. Той е ограничен до 200 променливи. "Premium Solver" използва подобрен първичен симплекс метод с двустранни граници за променливи. Платформата Premium Solver използва разширена версия на LP/Quadratic Simplex Solver за решаване на оптимизационен проблем с до 2000 променливи за решение.
Мащабният LP за платформата Premium Solver прилага най-съвременна реализация на простия и двоен симплекс метод, който използва рядкост в LP модела, за да спести време и памет, усъвършенствани стратегии за актуализиране и матрици за рефакторинг, множествено и частично ценообразуване и ротации и за преодоляване на дегенерацията. Този двигател се предлага в три версии (способен да обработва до 8 000, 32 000 или неограничени променливи и лимити).
MOSEK Solver включва първичен и двоен симплекс, метод, който също използва рядкост и използва усъвършенствани стратегии за актуализиране на матрицата и "рефакторизация". Решава проблеми с неограничен размер, бешетестван върху проблеми с линейно програмиране с милиони променливи за решение.
Пример стъпка по стъпка в EXCEL
За да дефинирате модела на проблема за оптимизация в Excel, изпълнете следните стъпки:
- Организирайте данните за проблема в електронна таблица в логическа форма.
- Изберете клетка за съхраняване на всяка променлива.
- Създайте в клетката формула за изчисляване на целевия математически модел на задачата за оптимизация.
- Създайте формули за изчисляване на лявата страна на всяко ограничение.
- Използвайте диалози в Excel, за да кажете на Solver за променливи за решение, цели, ограничения и желани граници на тези параметри.
- Изпълнете "Solver", за да намерите оптималното решение.
- Създайте лист в Excel.
- Организирайте данните за проблема в Excel, където се изчислява формулата за целевата функция и ограничението.
В горната таблица клетки B4, C4, D4 и E4 са запазени за представяне на променливи за решение X 1, X 2, X 3 и X 4. Примери за решение:
- Моделът на продуктовия микс ($450, $1150, $800 и $400 печалба на продукт) беше въведен съответно в клетки B5, C5, D5 и E5. Това позволява целта да бъде изчислена във F5=B5B4 + C5C4 + D5D4 + E5E4 или F5:=СУМПРОИЗВОД (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=0
Поле на практическо приложение на метода
Линейната оптимизация има много практически приложения като пример за оптимизационен проблем:
Една компания може да произвежда няколко продукта с известен марж на приноса. Производството на единица от всеки артикул изисква известно количество ограничени ресурси. Задачата е да се създаде производствена програма, която да определи колко от всеки продукт трябва да бъде произведен, така че печалбата на компанията да бъде максимизирана, без да се нарушават ограниченията на ресурсите.
Проблемите със смесването са решението на проблемите с оптимизация, свързани с комбинирането на съставките в крайния продукт. Пример за това е проблемът с диетата, изследван от Джордж Данциг през 1947 г. Дават се редица суровини, като овес, свинско и слънчогледово олио, заедно с тяхното хранително съдържание, като протеини, мазнини, витамин А, и тяхната цена за килограм. Предизвикателството е да се смесват един или повече крайни продукти от суровини на възможно най-ниска цена, като се спазват минималните и максималните граници за тяхната хранителна стойност.
Класическо приложение на проблем за линейна оптимизация е да се определи маршрутизирането за нуждитетрафик в телекомуникационни или транспортни мрежи. В същото време потоците трябва да се маршрутизират през мрежата по такъв начин, че всички изисквания за трафик да бъдат изпълнени, без да се нарушават условията за честотна лента.
В математическата теория линейната оптимизация може да се използва за изчисляване на оптимални стратегии в игри с нулева сума за двама души. В този случай се изчислява разпределението на вероятностите за всеки участник, което е коефициентът на произволно смесване на неговите стратегии.
Нито един успешен бизнес процес в света не е възможен без оптимизация. Има много налични алгоритми за оптимизация. Някои методи са подходящи само за определени видове проблеми. Важно е да можете да разпознаете техните характеристики и да изберете подходящия метод за решение.
