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

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

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

Історія розвитку

Лінійне програмування (ЛП) працює з класом задач оптимізації, де всі обмеження є лінійними.

Представляє коротку історію розвитку ЛП:

• У 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, де розраховується формула для цільової функції і обмеження.

У наведеній вище таблиці зарезервовано комірки B4, C4, 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 році. Наведено ряд сировинних матеріалів, наприклад, вівса, свинини і соняшникової олії, а також вміст в них поживних речовин, наприклад, білка, жиру, вітаміну А і їх ціна за кілограм. Завдання полягає в тому, щоб змішати один або кілька кінцевих продуктів із сировини з мінімальними витратами за умови дотримання мінімальних і максимальних меж для їх харчової цінності.

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

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

Без оптимізації неможливий жоден успішний бізнес-процес у світі. Існує багато доступних алгоритмів оптимізації. Деякі методи підходять лише для певних типів проблем. Важливо вміти розпізнавати їх характеристики і підбирати відповідний метод рішення.