Задачи с построчными вероятностными ограничениями

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

(10.16)

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

Вариант А. А =||a_ij|| - детерминированная матрица,

- случайная матрица-столбец, - случайные величины.

Считается, что задана совместная плотность распределения составляющих b_i случайного вектора В:

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

.

Зная распределение одной случайной величины , можно определить значение порога из уравнения

, (10.17)

где является нижним пределом интегрирования.

Она определяется как заданная вероятность a_i превышения случайной величиной b_i порога , что иллюстрируется на рис. 10.2.

Следовательно, построчные вероятностные ограничения

(10.18)

можно записать в виде неравенства

(10.19)

Таким образом, задача для варианта А запишется в матричном виде

(10.20)

где – вычисленные значения порогов для всех построчных ограничений.

Таким образом, задача при детерминированной матрице А и случайном столбце В будет решаться как детерминированная задача ЛП.

Вариант В. Принимаются элементы матрицы А=||а_ij|| - нормально распределенные независимые случайные величины со средним значением и дисперсией . Составляющие случайного вектора B=||b_j||^T - нормально распределенные независимые случайные величины со средним значением и дисперсией . Принимаем, что вероятность соблюдения построчных ограничений а_i³0,5.

При принятых допущениях невязка i-го вероятностного ограничения из (10.16) будет случайной величиной с нормальным распределением, как линейная комбинация нормально распределенных a_ij и b_i . Таким образом, невязка имеет вид

. (10.21)

Эта невязка имеет среднее значение и дисперсию

Построчные вероятностные ограничения можно выразить через невязку в виде неравенства следовательно, . Или для нормального распределения вероятность можно определить по известной формуле нормального распределения

(10.22)

где e - параметр интегрирования.

Вводя интеграл вероятности Ф, соотношение (10.22) можно записать в виде

или , (10.23)

где - функция, обратная интегралу вероятности. Иначе: Подставляя сюда значения , получаем

. (10.24)

Ф^-1( )³0. Область, ограничиваемая этим соотношением, выпукла, а сами ограничения квадратичны, т.к. .

Таким образом, при нормально распределенных случайных элементах матрицы А и составляющих вектора В решение задачи с построчными вероятностными ограничениями и решение в виде детерминированного вектора сводятся к решению задачи выпуклого программирования с линейной целевой функцией из (10.16) и квадратичными ограничениями из (10.24).

Вариант С. Рассматривается P-модель, у которой требуется минимизация порога k при заданной вероятности a₀ непревышения целевой функцией этого порога.

. (10.25)

Заданы случайные коэффициенты целевой функции с_j, которые распределены нормально со средним значением и коррелированы между собой.

Корреляция определяется корреляционной матрицей . Целевая функция для нормально распределенной величины с_j будет также нормально распределенной со средним значением и дисперсией .

Среднее значение невязки из соотношения (10.25) . Вводя интеграл вероятности Ф, аналогично (10.23) в принятых обозначениях получим .

Откуда . (10.26)

Поэтому целевая функция для минимизации порога k запишется из выражения (10.26) в виде

. (10.27)

Таким образом, при минимизации порога для заданной вероятности непревышения его целевой функцией задача СП с построчными вероятностными ограничениями сводится к детерминированной задаче выпуклого программирования с квадратичной целевой функцией и квадратичными ограничениями.

Например, рассмотрим задачу стохастического программирования, у которой заданы целевая функция в виде Р – модели и построчные вероятностные ограничения в виде

где заданы вероятности a₀=0.37; a₁=a₂=0.9.

Матрица системы детерминирована, c₁ ,c₂ ,b₁ ,b₂ – нормально распределенные независимые между собой пары случайных величин со средними значениями , и корреляционными матрицами , .

Можно рассмотреть плотность распределения одной из случайных величин, например b₁ , т. е. , приведенную на рис. 10.3.

По заданному среднему значению строится , смещенная относительно начала координат. Известная величина a₁=0.9 задает площадь под функцией плотности распределения, которая определяет границу =2.72 порога в ограничении, как следует из уравнения (10.17). Из табличных значений обратного интеграла вероятности находится Ф ^–1 (0.37) =0.33.

Таким образом, детерминированный эквивалент рассматриваемой задачи будет иметь целевую функцию

и систему ограничений

Решение стохастической задачи полностью сводится к решению детерминированной задачи.