Параметрическое и стохатическое программирование

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

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

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

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

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

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

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

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

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

Таблица 2.1

 

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

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

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

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

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

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

 

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

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

3.1 

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

3.2 

где

 

 

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

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

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

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

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

 

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

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

 

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

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

 

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

Таблица 3.3

 

Таблица 3.4

 

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

 

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

 

Таблица 3.5

 

Таблица 3.6

 

Рассмотрим теперь, как повлияют на результат решения  задачи величины, определяющие ее вероятностный  характер. К таким величинам относят  заданный уровень вероятности ai, и дисперсий σij2 и θi2. Начнем с анализа влияния ai (табл. 3.6).

Из анализа  решения этой задачи можно сделать  следующие выводы: для обеспечения  гарантированного (с вероятностью a = 0,6) выполнения плана необходимо иметь дополнительно около 5% каждого вида ресурса. При отсутствии дополнительного ресурса целевой функции может уменьшиться на величину (β = 4% вследствие возможного сокращения выпуска продукции х2 от 5,3 до 5,04.

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

При этом можно  сделать выводы:

в целях повышения заданного уровня вероятности выполнения плана ai требуется увеличить дополнительные ресурсы γi. Так, для выполнения плана с вероятностью, близкой к 1 (а = 0,987), необходим дополнительный ресурс в размере γi = 26, ..., 33% от величины используемого без учета вероятностных характеристик;

отсутствие такого увеличения может привести к ухудшению  целевой функции на величину β = 33,6%;

возрастание a отражается на номенклатуре продукции. При этом в интервале a = 0,5, ..., 0,77 значение х1 сохраняется неизменным, а х2 — уменьшается. При дальнейшем увеличении а = 0,89, ..., 0,987 значение х2 = const, в то время как х1 сначала скачком растет, а затем постепенно уменьшается. Несмотря на то что при а = 0,89 значения x1,2 резко изменяются, целевая функция во всем интервале изменения а уменьшается плавно. Таково влияние заданного уровня вероятности соблюдения ограничений а на результат решения задачи. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Литература:

1. Интернет сайт: http://ru.wikipedia.org/wiki/
2. «Математическое программирование» / Костевич Л.