Оптимізація допомагає знайти найкращий результат, який приносить прибуток, зменшує витрати або встановлює параметр, що викликає збої бізнес-процесів.
Цей процес також називають математичним програмуванням. Воно вирішує проблему визначення розподілу обмежених ресурсів, необхідних для досягнення поставленої мети керівником оптимізаційної задачі. З усіх допустимих варіантів бажано знайти той, який максимально посилює (або зменшує) контролюючий параметр, наприклад, прибуток або вартість. Моделі оптимізації також називаються розпорядчими або нормативними, оскільки прагнуть знайти можливу стратегію для бізнесу.
Історія розвитку
Лінійне програмування (ЛП) працює з класом задач оптимізації, де всі обмеження є лінійними.
Подає коротку історію розвитку ЛП:
- У 1762 році Лагранж вирішив прості оптимізаційні задачі з обмеженнями рівності.
- У 1820-му Гаусс вирішив лінійну систему рівнянь з допомогою винятку.
- В 1866 – м Вільгельм Джордан удосконалив метод пошуку помилок найменших квадратів, як критерій відповідності. Тепер це називається методом Гаусса-Джордана.
- У 1945-му з’явився цифровий комп’ютер.
- У 1947-му Данциг винайшов симплексні методи.
- У 1968-му Фіакко і Маккормік представили метод «Внутрішня точка».
- У 1984 році Кармаркар застосував метод інтер’єру для вирішення лінійних програм, додавши свій інноваційний аналіз.
ЛП виявилося надзвичайно потужним інструментом для моделювання реальних завдань, так і в якості широко застосовуваної математичної теорії. Однак багато цікаві оптимізаційні задачі є нелінійними.
Що робити в цьому випадку? Дослідження таких проблем включає в себе різноманітну суміш лінійної алгебри, багатовимірного обчислення, чисельного аналізу і обчислювальних методів. Вчені займаються розробкою обчислювальних алгоритмів, включаючи методи внутрішніх точок для лінійного програмування, геометрію, аналіз опуклих множин і функцій, а також вивчення спеціально структурованих завдань, таких як квадратичне програмування.
Нелінійна оптимізація забезпечує фундаментальне розуміння математичного аналізу і широко використовується в різних областях, таких як проектування, регресійний аналіз, управління запасами, геофізичних досліджень та економіці.
Класифікація оптимізаційних задач
Важливим кроком у процесі оптимізації є класифікація моделей, оскільки їх алгоритми рішення адаптовані до конкретного типу.
1. Завдання з дискретної і безперервної оптимізацією. Одні моделі мають сенс тільки в тому випадку, якщо змінні приймають значення з дискретного набору підмножину цілих чисел. Інші містять дані, які можуть приймати будь-яке реальне значення. Їх, як правило, легше вирішувати. Удосконалення алгоритмів у поєднанні з досягненнями в області обчислювальної техніки різко збільшили розмір і складність оптимізаційної задачі лінійного програмування.
2. Необмежена і обмежена оптимізація. Ще одна важлива відмінність – це задачі, в яких немає обмеження на змінні. Воно може широко варіюватися від простих оцінок до систем рівностей і нерівностей, які моделюють складні відносини між даними. Такі задачі оптимізації можуть бути додатково класифіковані за характером функцій (лінійні та нелінійні, опуклі і гладкі, диференційовані і недифференцируемые).
3. Завдання здійсненності. Їх мета полягає в тому, щоб знайти значення змінних, які задовольняють обмеженням моделі без якої-небудь конкретної мети оптимізації.
4. Завдання комплементарності. Вони широко поширені в техніці та економіці. Мета полягає в тому, щоб знайти рішення, яке задовольняє умовам додатковості. На практиці завдання з декількома цілями часто переформульовуються в єдині об’єктивні.
5. Детермінована проти стохастичної оптимізації. При детермінованої оптимізації передбачається, що дані для завдання абсолютно точні. Однак з багатьох актуальних питань вони не можуть бути відомі по ряду причин.
Перша пов’язана з простою помилкою вимірювання. Друга причина більш фундаментальна. Вона полягає в тому, що деякі дані представляють інформацію про майбутньому, наприклад, попит на продукт або ціну на майбутній період часу. При оптимізації в умовах стохастичної оптимізації невизначеність включається в модель.
Основні компоненти
Цільова функція – це та, яку потрібно мінімізувати або максимізувати. Більшість видів оптимізаційних задач мають одну цільову функцію. Якщо немає, то їх часто можна переформулювати так, щоб вони виконувалися.
Два винятки з цього правила:
1. Завдання пошуку мети. У більшості бізнес-додатків менеджер бажає досягти конкретної мети, одночасно задовольняючи обмеження моделі. Користувач не особливо хоче щось оптимізувати, тому немає сенсу визначати цільову функцію. Цей тип зазвичай називають проблемою здійсненності.
2. Безліч об’єктивних функцій. Найчастіше користувач хотів би оптимізувати відразу кілька різних цілей. Зазвичай вони несумісні. Змінні, які оптимізують одну мету, можуть бути далеко не найкращими для інших.
Типи компонентів:
- Керовані вхідні дані – це набір змінних рішення, які впливають на значення цільової функції. У виробничої задачі змінні можуть включати в себе розподіл різних доступних ресурсів або трудовитрати, необхідні для кожної дії.
- Обмеження – це відносини між змінними рішеннями і параметрами. Для виробничої проблеми не має сенсу витрачати велику кількість часу на будь-яку діяльність, тому обмежують всі «тимчасові» змінні.
- Можливі й оптимальні рішення. Значення рішення для змінних, при якому всі обмеження виконуються, називається виконуваною. Більшість алгоритмів спочатку його знаходять, потім намагаються поліпшити. Нарешті, вони змінюють змінні, щоб перейти від одного здійсненного рішення до іншого. Даний процес повторюється до тих пір, поки цільова функція не досягне свого максимуму чи мінімуму. Цей результат називається оптимальним рішенням.
Широко використовуються алгоритми оптимізаційних задач, розроблені для наступних математичних програм:
- Опуклі.
- Колективні.
- Квадратичні.
- Геометричні.
Лінійні розв’язувачі Google
Лінійна оптимізація або програмування – це ім’я, яке дається обчислювального процесу оптимального рішення задачі. Вона моделюється як набору лінійних відносин, які виникають у багатьох наукових і інженерних дисциплінах.
Google пропонує три способи рішення задач лінійної оптимізації:
- Бібліотека з відкритим вихідним кодом Glop.
- Надбудова Linear Optimization для Google Sheets.
- Служба лінійної оптимізації в Google Apps Script.
Glop – це вбудований в Google лінійний вирішувач. Він доступний з відкритим вихідним кодом. Можна отримати доступ до Glop через пакувальник лінійного вирішувача OR-Tools, який є оболонкою для Glop.
Модуль лінійної оптимізації для Google Sheets дозволяє виконувати лінійну постановку оптимізаційної задачі, вводячи дані в електронну таблицю.
Квадратичне програмування
Платформа Premium Solver використовує розширену LP/Quadratic версію методу Simplex з обмеженнями обробки завдань LP і QP до 2000 змінних рішень.
SQP Solver для великомасштабних завдань використовує сучасну реалізацію методу активного набору з розрідженістю для розв’язування задач квадратичного програмування (QP). Механізм XPRESS Solver використовує природне розширення методу “Внутрішньої точки” або Ньютона-Бар’єру для вирішення проблем QP.
MOSEK Solver застосовує методи впровадженої “Внутрішньої точки” і автодуальный. Це особливо ефективно для слабосвязанних завдань QP. Він також може вирішувати завдання масштабного квадратичного обмеження (QCP) і конусного програмування другого порядку (SOCP).
Многооперационные обчислення
Вони цілком успішно використовуються із застосуванням можливостей Microsoft Office, наприклад, рішення оптимізаційних задач в Excel.
У наведеній вище таблиці такі позначення:
- K1 – K6 – клієнти, яким необхідно надати товар.
- S1 – S6 – потенційні виробничі майданчики, які можуть бути побудовані для цього. Може бути створено 1,2,3,4,5 або всі 6 локацій.
Для кожного об’єкта є фіксовані витрати, зазначені у стовпчику I (Fix).
Якщо місцезнаходження нічого не змінює, воно не буде враховуватися. Тоді не буде фіксованих витрат.
Визначають потенційні місця розташування, щоб отримати саму низьку вартість.
У даних умовах розташування яких встановлено, або ні. Це два стани такі: «ІСТИНА – ХИБНІСТЬ» або «1 – 0». Існує шість станів для шести місцезнаходжень, наприклад, для 000001 встановлено лише шосте , для 111111 – все.
У двійковій системі числення існує рівно 63 різні варіанти від 000001 (1) до 111111 (63).
В L2-L64 тепер має стояти {= MULTIPLE OPERATION (K1)}, це результати всіх альтернативних рішень. Тоді мінімальне значення дорівнює = Min (L), а відповідна альтернатива дорівнює INDEX (K).
Цілочисельне програмування CPLEX
Іноді лінійних відносин недостатньо, щоб вловити суть бізнес-проблеми. Це особливо вірно, коли рішення включають дискретний вибір, наприклад, відкривати склад в певному місці чи ні. У цих ситуаціях необхідно використовувати цілочисельне програмування.
Якщо проблема включає в себе як дискретний, так і безперервний вибір, це змішана цілочисельна програма. Вона може мати лінійні, опуклі квадратичні завдання і такі ж обмеження другого порядку.
Цілочисельні програми набагато складніше, ніж лінійні, але вони мають важливі бізнес-додатки. Програмне забезпечення CPLEX використовує складні математичні методи для розв’язування цілочислових задач. Його методи включають в себе систематичний пошук можливих комбінацій дискретних змінних з використанням лінійних або квадратичних програмних релаксацій для обчислення меж значення оптимального рішення.
Вони також використовують LP і інші методи рішення оптимізаційних задач для обчислення обмежень.
Стандартний Microsoft Excel Solver
Ця технологія використовує базову реалізацію основного методу Simplex для вирішення завдань LP. Він обмежений 200 змінними. “Преміум Солвер” використовує покращений первинний симплекс-метод з двосторонніми межами для змінних. Платформа Premium Solver використовує розширену версію LP/Quadratic Simplex Solver для рішення оптимізаційної задачі з числом змінних рішень до 2000.
Великомасштабна LP для платформи Premium Solver застосовує сучасну реалізацію методу простого і подвійного симплексу, який використовує розрідженість у моделі LP для економії часу і пам’яті, передові стратегії для оновлення і рефакторизации матриць, багаторазового і часткового ціноутворення і поворотів, а також для подолання виродження. Цей механізм доступний в трьох версіях (з можливістю обробки до 8 000, 32 000 або необмеженого числа змінних і обмежень).
MOSEK Solver включає в себе первинний і двоїстий симплекс – метод, який також експлуатує розрідженість і використовує передові стратегії для відновлення матриці і «refactorization». Він вирішує завдання необмеженого розміру, був протестований на задачах лінійного програмування з мільйонами змінних рішень.
Покроковий приклад в EXCEL
Щоб визначити модель оптимізаційної задачі в Excel, виконують такі етапи:
- Організовують дані проблеми в електронній таблиці в логічній формі.
- Вибирають комірку для зберігання кожної змінної.
- Створюють у клітинці формулу обчислення цільової математичної моделі оптимізаційної задачі.
- Створюють формули для розрахунку лівій частині кожного обмеження.
- Використовують діалоги в Excel, щоб повідомити “Солверу” про змінних рішення, цілі, обмеження і бажаних межах цих параметрів.
- Запускають “Солвер”, щоб знайти оптимальне рішення.
- Створюють аркуш Excel.
- Упорядковують дані проблеми в Excel, де розраховується формула для цільової функції і обмеження.
У наведеній вище таблиці зарезервували комірки В4, С4, D4 і E4 для подання змінних прийняття рішення X 1, X 2, X 3, X 4. Приклади рішення:
- Модель асортименту продукції (прибуток для кожного виду виробів 450, 1150, 800 і 400 доларів) була введена в осередку 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 році. Наведено ряд сировинних матеріалів, наприклад, вівса, свинини і соняшникової олії, а також вміст в них поживних речовин, наприклад, білка, жиру, вітаміну А і їх ціна за кілограм. Завдання полягає в тому, щоб змішати один або кілька кінцевих продуктів із сировини з мінімальними витратами за умови дотримання мінімальних і максимальних меж для їх харчової цінності.
Класичним застосуванням лінійної оптимізаційної задачі є визначення маршрутизації для потреб трафіку в телекомунікаційних або транспортних мережах. При цьому потоки повинні маршрутизироваться через мережу таким чином, щоб усі вимоги до трафіку виконувалися без порушення умов пропускної здатності.
В рамках математичної теорії лінійна оптимізація може використовуватися для обчислення оптимальних стратегій в іграх з нульовою сумою для двох осіб. При цьому розраховується розподіл ймовірностей для кожного учасника, що є коефіцієнтом випадкового змішання його стратегій.
Без оптимізації неможливий жоден успішний бізнес-процес в світі. Існує багато доступних алгоритмів оптимізації. Деякі методи підходять тільки для певних типів проблем. Важливо вміти розпізнавати їх характеристики і підбирати відповідний метод вирішення.
