Стохастичне програмування: Оптимізація рішень з невизначеністю

Вступ: Невизначеність у лінійному програмуванні

У світі оптимізації часто виникає спокуса розглядати реальні проблеми як набір точних чисел: попит — це число, час у дорозі — це число, швидкість вітру — це число. Модель приймає ці дані, повертає оптимальне рішення і продовжує працювати. Однак реальність, яку ці числа мали б описувати, є часто нечіткою, мінливою та непередбачуваною. Саме тут на допомогу приходить стохастичне програмування — галузь, яка серйозно ставиться до цієї невизначеності, вбудовуючи її безпосередньо в модель.

Ціна за це — трохи більше нотації, але винагорода — це рішення, які залишаються дієвими, коли світ не співпрацює.

Проблема з випадковими змінними

Розглянемо приклад модної компанії, яка продає зимовий одяг у Німеччині. Виробництво відбувається в Бангладеш, що є дешево, але повільно, тому товари прибувають за кілька тижнів. Восени компанія повинна вирішити, скільки виробити на майбутній зимовий сезон. Тут є два ризики: виробити замало — втратити продажі; виробити забагато — залишитися з непроданими запасами. Відповідь на це питання залежить від того, що ще невідомо: зимового попиту.

Якби невизначеність ігнорувалася, а попит вважався фіксованим числом (h), можна було б написати просту лінійну програму (ЛП). Проте попит — це не число, а випадкова змінна (ξ). Чесна версія моделі, що включає випадкову змінну, стає погано визначеною. Розв'язувач не знає, яку проблему йому вирішувати, оскільки обмеження залежить від випадкової змінної. Стохастичне програмування пропонує набір принципових відповідей на це питання.

Чотири підходи до обробки невизначеності

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

1. Робастна оптимізація: підготовка до найгіршого

Це найобережніший підхід. Він не вимагає знання повного розподілу ймовірностей ξ, а лише його підтримки — множини всіх можливих значень, які може приймати ξ (множина невизначеності U). Запитання полягає в тому, яке найкраще рішення залишається здійсненним незалежно від того, яке ξ ∈ U фактично з'явиться. Наприклад, у випадку з модною компанією, якщо U = [0, 10], планування завжди буде відбуватися на попит 10, тобто на найгірший випадок. Сила і слабкість робастної оптимізації полягає в тому, що рішення є «куленепробивним», але воно також консервативне: часто залишаються зайві запаси, оскільки планування відбувалося так, ніби найгірший, малоймовірний випадок гарантований.

2. Обмеження за ймовірністю (Chance Constraints): послаблення найгіршого випадку

Якщо робастна оптимізація планує на будь-який можливий результат, то обмеження за ймовірністю послаблюють це до планування на більшість з них. Вибирається рівень ймовірності α, наприклад 95%, і вимагається, щоб обмеження виконувалося з ймовірністю не менше α.

Спільні обмеження за ймовірністю: всі елементи вектора обмежень мають виконуватися одночасно з ймовірністю ≥ α.
Індивідуальні обмеження за ймовірністю: кожне обмеження i має виконуватися з ймовірністю не менше αᵢ.

Спільна версія є більш консервативною. Обмеження за ймовірністю дають можливість регулювати рівень обережності за допомогою параметра α. Зазвичай у реальних застосуваннях α знаходиться в діапазоні 0.9–0.99. Однак, обмеження за ймовірністю є складними в загальному випадку, оскільки термін ймовірності всередині обмеження є нелінійною, часто неопуклою функцією, що ускладнює використання стандартних ЛП-розв'язувачів.

3. Двоетапні моделі з рекурсом: вирішити, спостерігати, виправити

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

У двоетапній версії часова шкала виглядає так:

Етап 1 (зараз): приймається рішення x, поки ξ ще невизначена.
Потім: ξ реалізується, тобто випадкова змінна стає відомим числом.
Етап 2 (пізніше): приймається рішення y, знаючи ξ.

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

4. Багатоетапні моделі з рекурсом: продовження процесу

Життя не завжди складається з двох етапів. Іноді процес «вирішити-спостерігати-виправити» повторюється знову і знову. Багатоетапні моделі з рекурсом є природним розширенням. У прикладі з модною компанією, припустимо, рішення приймаються тричі: восени (дешево, в Бангладеш), на початку зими (дорожче, в Румунії) та наприкінці зими (найдорожче, в Німеччині). Попит поступово розкривається протягом сезону, і на кожному етапі рішення приймаються на основі того, що було спостережено до цього моменту. Це можна візуалізувати як дерево сценаріїв, де кожен вузол є станом світу, кожна гілка — можливою реалізацією наступної випадкової змінної, а сценарій — повним шляхом від кореня до листа. Важливою властивістю є непередбачуваність (non-anticipativity): рішення можуть залежати лише від інформації, яка вже була спостережена на момент прийняття рішення.

Як розв'язувати рекурсні моделі?

Для розв'язання рекурсних моделей їх зазвичай перетворюють на детерміністичний еквівалент, який може обробляти стандартний ЛП-розв'язувач. Якщо випадкова змінна ξ має дискретний розподіл (приймає скінченну кількість значень — сценаріїв), то очікувана вартість другого етапу стає скінченною сумою, і всю двоетапну проблему можна записати як одну велику ЛП. Цю ЛП можна передати будь-якому стандартному розв'язувачу.

Якщо розподіл ξ не є дискретним, детерміністичний еквівалент має нескінченно багато сценаріїв. Стандартним рішенням є апроксимація середнього зразка (sample average approximation - SAA): береться зразок розміру S з істинного розподілу, розв'язується детерміністичний еквівалент для цього зразка, і S збільшується, доки рішення не стабілізується статистично.

Якщо детерміністичний еквівалент занадто великий для прямого розв'язання, використовуються методи декомпозиції. Декомпозиція Бендерса розділяє проблему на головну задачу (для змінних першого етапу) та підзадачу для кожного сценарію, обмінюючись інформацією між ними. Для багатоетапних моделей з багатьма етапами аналогічним методом є стохастичне подвійне динамічне програмування (SDDP), яке використовує вибірку та апроксимацію функцій вартості, щоб уникнути побудови повного дерева сценаріїв.

Чи варті ці зусилля?

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

Існують дві класичні метрики:

VSS (Value of the Stochastic Solution - Цінність стохастичного рішення): показує, наскільки гірше було б, якби просто розв'язали детерміністичну проблему із середніми значеннями та реалізували її рішення. Якщо VSS малий, стохастична програма не дає великої переваги.
EVPI (Expected Value of Perfect Information - Очікувана цінність досконалої інформації): показує, скільки можна було б виграти, якби було відомо реалізоване ξ заздалегідь. Якщо EVPI малий, кращі прогнози не дадуть значної вигоди; якщо великий, кращі дані мають реальну цінність.

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

Висновок

Якщо ви використовуєте лінійні програми в будь-якому контексті, де вхідні дані є дійсно невизначеними через прогнозований попит, погоду, ціни, час у дорозі або щось інше, ваша модель робить неявний вибір щодо того, як обробляти цю невизначеність. «Просто використовувати середнє значення» — це вибір. Так само як і «планувати на найгірший випадок». Стохастичне програмування дає вам термінологію для явного вибору та інструменти для оцінки того, чи був ваш вибір вдалим (наприклад, за допомогою VSS).

Підсумовуючи, чотири основні способи моделювання невизначеності в ЛП:

Робастна оптимізація: планування на найгірший випадок у заданій множині невизначеності.
Обмеження за ймовірністю: вимога здійсненності з ймовірністю не менше α.
Двоетапний рекурс: вирішити, спостерігати, виправити; оплата очікуваної вартості рекурсу.
Багатоетапний рекурс: та ж ідея, повторена в часі на дереві сценаріїв.

І дві метрики, які варто пам'ятати: VSS (чи допомагає стохастична модель?) та EVPI (чи допоможуть кращі прогнози?). Більшість реальних проблем не є детерміністичними, і ваш інструментарій моделювання також не повинен бути таким.

Що це означає для розробників

Стохастичне програмування надає розробникам інструменти для створення оптимізаційних моделей, які явно враховують невизначеність даних, таких як попит або час. Це дозволяє приймати більш обґрунтовані рішення, оцінюючи ризики та потенційні вигоди від складніших моделей за допомогою метрик VSS та EVPI.

Ключові факти

Стохастичне програмування вбудовує невизначеність безпосередньо в оптимізаційні моделі, на відміну від детерміністичних підходів.
Існує чотири основні підходи до обробки невизначеності: робастна оптимізація, обмеження за ймовірністю, двоетапні та багатоетапні моделі з рекурсом.
Двоетапні моделі з рекурсом є найпоширенішими на практиці, оскільки відображають хронологію рішень (вирішити, спостерігати, виправити).
Для розв'язання рекурсних моделей використовуються детерміністичні еквіваленти, апроксимація середнього зразка (SAA) та методи декомпозиції, такі як декомпозиція Бендерса та стохастичне подвійне динамічне програмування (SDDP).
Метрики VSS (цінність стохастичного рішення) та EVPI (очікувана цінність досконалої інформації) допомагають кількісно оцінити переваги стохастичного моделювання та цінність кращих прогнозів.