Стохастическое программирование выполнили Шпарик Анна Кутас Юлия

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

В задаче линейного программирования: (1.1)

Стохастическая постановка целевой функции может быть двух видов: М- постановка и Р-постановка. При М-постановке случайная величина заменяется ее математическим ожиданием и задача сводится к оптимизации детерминированной целевой функции:

(1.2) где сj математическое ожидание случайной величины сj.

При Р-постановке целевая функция будет иметь вид: при максимизации целевой функции: (1.3) при минимизации целевой функции: (1.4)

Наиболее распространены СТП-постановки в вероятностных ограничениях вида: (1.5)

Так, ограничение (а) означает, что вероятность соблюдения неравенства 1.6 должна быть не меньше, чем ai. Аналогичный смысл и других ограничений.

Для случая, когда вероятностные ограничения представлены в виде типа (а), задачу СТП можно записать при М- постановке: (1.7)

При Р-постановке: в случае максимизации целевой функции 1.8 в случае минимизации целевой функции 1.9

Детерминированная постановка задач стохастического программирования Процесс решения задачи СП разделяется на два этапа: Предварительный этап (более трудоемкий). Формируются решающие правила, связывающие решение с заданными статистическими характеристиками случайных параметров условий задачи. Этап не требует знания конкретных значений параметров целевой функции и ограничений. Построение решающих правил требует информации о структуре задачи и о статистических характеристиках случайных исходных данных. На основном этапе решающие правила используются для оперативного решения задачи. Второй этап называют оперативным этапом анализа стохастической модели.

Для решения задачи стохастического программирования в Р-постановке и с вероятностными ограничениями переходят к детерминированному эквиваленту. Для целевой функции детерминированный эквивалент имеет вид: при минимизации целевой функции 2.1

при максимизации целевой функции 2.2 где σ2j дисперсия случайной величины сj Решение таких задач затруднительно, поэтому далее рассматриваем целевая функция только в М- постановке.

Детерминированный эквивалент вероятностного ограничения типа (а) 2.3 может быть сведен к виду: 2.4

где ai j, bi математические ожидания;, σ i j 2, ө i 2 дисперсии случайных величин aij, bi ; ta = Ф*-1(ai) обратная функция нормального распределения при функции распределения: 2.5 где ai заданный уровень вероятности

Детерминированный эквивалент задачи СТП в М-по- становке имеет вид 2.6

Каждое 1-е ограничение в детерминированном эквиваленте (2.6) отличается от аналогичного ограничения задачи линейного программирования следующим: 2.7 от детерминированных значений aij, bi выполнен переход к математическим ожиданиям случайных величин aij, bi; появился дополнительный член ( ζ ) который учитывает все вероятностные факторы: закон распределения с помощью ta; заданный уровень вероятности ai ; дисперсии случайных величин aij равные σ ij 2; дисперсии случайных величин bi равные ө i 2.

Решение задач СТП Детерминированный эквивалент задачи стохастического программирования в М- постановке включает ограничения, которые являются нееепарабельными функциями. Обозначим 3.1

тогда задачу стохастического программирования можно записать в сепарабельной форме: 3.2 где

Эта задача является сепарабельной задачей нелинейного программирования и может быть решена с помощью стандартных программных средств. Функция F(x1, х2, хп) называется сепарабельной, если она может быть представлена в виде суммы функций, каждая из которых является функцией одной переменной, т. е. если

Заключение Таким образом можно сказать что стохастические модели, при выборе решений в сложных ситуациях, более адекватны реальным явлениям и процессам, чем детерминированные. В практических задачах приходится выбирать решения в условиях недостатка информации об исходных данных.