Стохастическое программирование (стр. 2 из 3)

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

1.7

При Р-постановке:

· в случае максимизации целевой функции

1.8

· в случае минимизации целевой функции

1.9

где cj , ai j , bi — случайные величины.

Для остальных случаев ограничений (б, в, г) постановка задач стохастического программирования аналогична.

Задачи (1.7), (1.8), (1.9) непосредственно решены быть не могут. Одним из возможных методов их решения может быть представление их в виде детерминированного эквивалента.

2. Детерминированная постановка задач стохастического

программирования

Стохастическое программирование позволяет по-новому подойти к решению задач, информационная структура которых (естественная или определяемая стохастическим расширением) известна заранее. Процесс решения задачи стохастического программирования может быть разделен на два этапа. Первый — предварительный этап — обычно весьма трудоемкий. На первом этапе строится закон управления — решающие правила или решающие распределения, связывающие решение или механизм формирования решения с реализованными значениями и заданными статистическими характеристиками случайных параметров условий задачи. Предварительный этап не требует знания конкретных реализаций значений параметров целевой функции и ограничений. Построение решающих правил или распределений требует лишь информации о структуре задачи и о некоторых статистических характеристиках случайных исходных данных. Поэтому процесс конструирования решающих механизмов не стеснен обычно недостатком времени и может начинаться с момента осознания важности задачи, как только построена стохастическая модель и проверено ее соответствие изучаемому явлению. Затраты времени и ресурсов на подготовку решающих правил или распределений обычно оправдываются. Полученные при этом законы управления позволяют решать не только отдельные конкретные задачи; они применимы для множества задач заданной информационной структуры. Решающие правила или распределения — это формулы, таблицы, инструкции или случайные механизмы с фиксированными или меняющимися в зависимости от реализации случайных параметров условий статистическими характеристиками. На втором этапе анализа стохастической модели решающие правила или распределения используются для оперативного решения задачи. Второй этап естественно называть оперативным этапом анализа стохастической модели. Заметим, что при отсутствии статистических характеристик случайных исходных данных можно заменить на предварительном этапе прямой путь построения решающих механизмов адаптивным — итеративным методом решения стохастической задачи по последовательным наборам реализаций случайных параметров условий задачи. Стохастическое программирование определяет новый подход к алгоритмизации управления в сложных системах. Математическое обеспечение сложных экстремальных управляющих систем целесообразно компоновать не из алгоритмов решения экстремальных задач, а из решающих правил соответствующих стохастических расширений. При этом формирование законов управления — решающих правил или решающих распределений — связывается не с оперативной работой, а с этапом проектирования управляющей системы. Стохастическое программирование и, в частности, стохастическое расширение открывают, таким образом, путь оперативного анализа сложных задач, альтернативой которому являются экспертные оценки и волевые решения.

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

Для целевой функции детерминированный эквивалент имеет вид:

· при минимизации целевой функции

2.1

· при максимизации целевой функции

2.2

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

2.3

может быть сведен к виду:

2.4

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

2.5

где ai— заданный уровень вероятности (табл. 2.1).

Обычно решают задачи при ai > 0,5, поэтому даны значенияtaтолько для положительныхta..

Таблица 2.1

ai	0,5	0,6	0,7	0,77	0,84	0,89	0,93	0,96	0,98	0,987	0,994
t a	0,0	0,25	0,5	0,75	1	1,25	1,5	1,75	2,0	2,25	2,5

Если же ai < 0,5; то t1-a= - ta.Так, для а = 0,4; t0,4 = t(1-0,6) = - t 0, 6 =0,25.

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

2.6

Из (2.6) следует, что для решения задачи стохастического программирования в М-постановке необходимы исходные данные, приведенные в предыдущей таблице.

Каждое 1-е ограничение в детерминированном эквиваленте (2.6) отличается от аналогичного ограничения задачи линейного программирования следующим:

2.7

·

от детерминированных значений aij, bi выполнен переход к математическим ожиданиям случайных величин aij, bi;

· появился дополнительный член ( ζ )

который учитывает все вероятностные факторы: закон распределения с помощью ta;заданный уровень вероятностиai ; дисперсии случайных величин aijравные σ ij 2; дисперсии случайных величин bi равные ө i 2.

3. Решение задач СТП

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

3.1

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

3.2

где

Эта задача является сепарабельной задачей нелинейного программирования и может быть решена с помощью стандартных программных средств.

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

Если целевая функция и функции в системе ограничений задачи нелинейного программирования сепарабелъные, то приближенное решение может быть найдено методом кусочно-линейной аппроксимации.

Пример 1. Рассмотрим задачу распределения двух видов ресурсов для выпуска двух наименований изделий.

Решение. Ее модель:

где aij , bi , cj— случайные.

При М-постановке модель запишется:

где a1, a2 — заданные уровни вероятности соблюдения каждого ограничения.

Для того чтобы решить задачу в М-постановке, необходимо перейти к ее детерминированному эквиваленту:

Исходные данные, необходимые для решения этой задачи, сведены в таблицах 3.3 и 3.4.

Таблица 3.3

Величина	С	d	D
X1	5	2	6
X2	8	3	9

Таблица 3.4

Ограничения	Случайные величины
	ai1		ai2		bi
1	10	2	15	3	100	9
2	20	6	14	4	150	12

Если задать уровни вероятности a1,2 = 0,6, для которыхta= 0,25, то получим после подстановки исходных данных детерминированный эквивалент:

Результаты решения этой задачи для детерминированного случая ζ i = 0 и при a i = 0,6 (табл. 3.5), где