Стохастично програмиране

Стохастично програмиране (англ. stochastic programming) — дял на математическото програмиране, разработващ модели и методи за решаване на оптимизационни задачи в условия на неопределеност, когато някои параметри на модела не са известни точно, а са представени като случайни величини с известни или оценени вероятностни разпределения.

За разлика от детерминираните задачи, при които всички данни се считат за зададени константи, стохастичното програмиране си поставя за цел да намери решение (или политика за вземане на решения), което е оптимално в някакъв статистически смисъл. Най-често това означава минимизиране или максимизиране на математическото очакване на целевата функция. Ключовата идея се състои в намирането на такава политика за вземане на решения, която ще бъде най-добра „средно" по всички възможни реализации на случайните параметри, което е особено актуално за задачи, при които решения се вземат многократно в сходни условия (например в управлението на запасите или енергийните системи).

Математическа постановка на задачата

В общ вид задачата на стохастичното програмиране може да бъде формулирана като: $\underset{x\in X}{min}𝔼[f(x,\xi )]$ където:

• $x$ — вектор от управляващи променливи (решения), които трябва да бъдат определени.
• $X$ — множеството от допустими решения за $x$, определено от детерминирани ограничения.
• $\xi$ — случаен вектор, представящ неопределените параметри на задачата (например търсене, цени, метеорологични условия).
• $f(x,\xi )$ — целева функция, чиято стойност зависи както от приетото решение $x$, така и от реализацията на случайния вектор $\xi$.
• $𝔼[\cdot ]$ — оператор на математическото очакване, изчисляван по вероятностното разпределение на вектора $\xi$.

Най-важният принцип, лежащ в основата на многоетапните стохастични модели, е принципът на непредвосхищане (англ. non-anticipativity principle). Той гласи, че решенията, вземани на всеки етап, могат да зависят само от информацията, налична към този момент, и не могат да „гледат в бъдещето\".

Двуетапна задача с право на компенсация

Най-разпространеният модел е двуетапната задача с право на компенсация (англ. two-stage stochastic program with recourse). Процесът на вземане на решения е разделен на два етапа:

1. Първи етап: Взема се решение „тук и сега\" (here-and-now) — определя се векторът $x$. Това решение трябва да бъде взето, преди да стане известна конкретната реализация на случайния вектор $\xi$.
2. Втори етап: След като случайното събитие е настъпило, се взема коригиращо или компенсационно решение (recourse decision) — векторът $y(\xi )$, насочено към минимизиране на отрицателните последствия или използване на благоприятните възможности, възникнали в резултат на съчетанието на решението от първия етап $x$ и изхода $\xi$.

Математически двуетапната задача на стохастичното линейно програмиране се формулира по следния начин: $\underset{x\in {ℝ}^{n_1}}{min}\{c^{T}x+{𝔼}_{\xi }[Q(x,\xi )]\}$ при ограничения от първия етап: $Ax=b,x\ge 0$. Тук $Q(x,\xi )$ е функцията на компенсация (recourse function), представляваща оптималната стойност на задачата от втория етап: $Q(x,\xi )=\underset{y\in {ℝ}^{n_2}}{min}\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ където $\xi$ — случаен вектор, включващ параметрите $q(\xi ),T(\xi )$ и $h(\xi )$; а $c,A,b$ и $W$ — детерминирани параметри.

Ключови свойства и теореми

• Изпъкналост: Един от фундаменталните резултати на теорията е, че за двуетапната задача на стохастичното линейно програмиране очакваната функция на компенсация $Q(x)={𝔼}_{\xi }[Q(x,\xi )]$ е изпъкнала функция. Това свойство е от огромно значение, тъй като гарантира, че общата задача от първия етап е задача на изпъкнало програмиране, за която съществуват ефективни методи за решаване и глобалният оптимум съвпада с локалния.
• Детерминиран еквивалент: Ако случайният вектор $\xi$ има краен брой възможни реализации (сценарии) ${\xi }_1,\dots ,{\xi }_K$ с вероятности $p_1,\dots ,p_K$, то задачата на стохастичното програмиране може да бъде преформулирана като една голяма детерминирана оптимизационна задача. В този случай математическото очакване се замества от претеглена сума по всички сценарии. Въпреки това размерът на тази задача нараства линейно с броя на сценариите, което води до „проклятието на размерността\" и прави такъв подход изчислително неразрешим при голям брой сценарии.

Сравнение с робастна оптимизация

Стохастичното програмиране е един от няколкото подхода за оптимизация в условия на неопределеност. Ключовото му отличие от робастната оптимизация се състои в начина на моделиране на неопределеността и критерия за оптималност.

Сравнение на подходите за оптимизация в условия на неопределеност

Критерий	Стохастична оптимизация	Робастна оптимизация
Представяне на неопределеността	Параметрите са случайни величини с известно вероятностно разпределение	Параметрите принадлежат на зададено множество на неопределеност, разпределение не се изисква
Критерий за оптималност	Оптимизация на математическото очакване на целевата функция	Оптимизация в най-лошия сценарий (минимакс)
Характер на решението	Политика, оптимална „средно\", може да бъде недопустима за редки сценарии	Решение, гарантирано допустимо за всички реализации; може да бъде консервативно

Примери

• Задачата на вестникопродавача (англ. newsvendor problem): Класическа задача за управление на запасите, при която продавачът трябва да реши какво количество стока да закупи, без да знае точното бъдещо търсене. Решението балансира между риска от загуби поради излишъци и риска от пропусната печалба поради дефицит.
• Задачата на фермера: Фермерът решава колко акра земя да отдели за различни култури на обща площ, без да знае бъдещото време, което влияе върху добива. След като времето стане известно, фермерът може да предприеме коригиращи действия (например да продаде излишъците или да закупи допълнително необходимата реколта на пазара).

Вижте също

• Математическо програмиране
• Изследване на операциите
• Робастна оптимизация
• Динамично програмиране
• Теория на управлението