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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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