Схема преобразования стохастической задачи МП к эквивалентному детерминированному виду. Содержательное истолкование детерминированной задачи

Рассматривается задача ЛП, в которой требуется найти максимум линейной формы L=(C,X)àMAX при условиях AX≤B и X≥0, причем элементы вектора ограничений, элементы матрицы условий и коэффициенты функции цели могут быть случайными числами как с известными характеристиками (случай риска), так и неизвестными (случай неопред-ности).

Если задача полностью стохастическая, то необходимо уточнить исходную постановку задачи: определить, что понимается под допустимым решением (планом), а также смысловое содержание показателя качества решений. Исходной задаче может соответствовать различные определения (модели) стохастической задачи:

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

Решение задачи Х рассматривается как детерминированный (фиксированный) вектор; допустимым решением (планом) считается такой вектор Х, который удовлетворяет ограничениям задачи при всех возможных сочетаниях значений А и В, имеющих положительную вероятность; это жесткая постановка задачи, не использующая дополнительных сведений относительно статистических характеристик условий в модели.

A(q)*X<=B(q) для всех q@Q,X>=0 Здесь q‑случайные параметры, от которых зависят значения А и В (состояния природы), их набор обычно считается конечным;

Р(SUM Aij*Xj <= Bi) >= Pi; i=1,...,m; 0 =< Pi <= 1 при этом часто матрица А предполагается фиксированной и случаен только вектор ограничений В; если множество возможных состояний природы конечно и известны характеристики (оценки значений и их вероятностей) для каждого элемента Вi (т.е. Bki и Hki для k=1,...,s), то можно определить значения ~Bi, которые удовлетворяют условию P(Bi(q)>=~Bi)>=Pi; действительно, для этого необходимо упорядочить значения Bki в порядке убывания и выбрать наименьшую группу, удовлетворяющую условию: вероятность попадания значения Bi в данную группу больше или равна Pi (для этого суммарная вероятность группы должна быть больше или равна Pi). Тогда задача будет сведена к детерминированной: (^C,X)àMAX AX<=~B, где ~B=(~B1,~B2,...,~Bm) при условии жесткой постановки (одноэтапной);

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

- если X - допустимый план (перманентное решение) задачи, то он удовлетворяет соотношению A^X<=B^ для любой допустимой (возможной) пары [A^,B^].

Обычный подход сводится к рассмотрению решения детерминированной задачи, полученной заменой вероятностных условий их математическими ожиданиями; после этого проверяется перманентность плана (в случае ограниченности элементов матрицы А и В это несложно)

 

 

Формулировка двух типов задач поиска решений при использовании детерминированного эквивалента стохастической задачи МП на максимум математического ожидания функции цели и на максимум вероятности (надежности) достижения заданного уровня функции цели.

Рассматривается задача ЛП, в которой требуется найти максимум линейной формы L=(C,X)àMAX при условиях AX≤B и X≥0, причем элементы вектора ограничений, элементы матрицы условий и коэффициенты функции цели могут быть случайными числами как с известными характеристиками (случай риска), так и неизвестными (случай неопределенности).

1) все значения заменяются на мат. ожидании (среднее значение) – максимизация результата при заданной надежности P ≥ Р при Fà max

Случаен только вектор С функции цели, остальная информация детерминирована. Обычный в этой ситуации подход - выбор в качестве критерия математического ожидания функции цели - сводит задачу к детерминированной (критерий имеет вид (^C,X)àMAX, где ~С - математическое ожидание вектора С). Если статистические характеристики вектора С неизвестны, то применяются различные гипотезы и оценки, а также методы анализа зоны неопределенности.

2) максимизация надежности при заданном уровне эффекта F ≥ F при maxP(F). Если случайны не только вектор С, но и другая информация: вектор В и матрица условий А, то необходимо уточнить исходную постановку задачи: определить, что понимается под допустимым решением (планом), а также смысловое содержание показателя качества решений.

Р(SUM Aij*Xj <= Bi) >= Pi; i=1,...,m; 0 =< Pi <= 1 при этом часто матрица А предполагается фиксированной и случаен только вектор ограничений В; если множество возможных состояний природы конечно и известны характеристики (оценки значений и их вероятностей) для каждого элемента Вi (т.е. Bki и Hki для k=1,...,s), то можно определить значения ~Bi, которые удовлетворяют условию P(Bi(q)>=~Bi)>=Pi; действительно, для этого необходимо упорядочить значения Bki в порядке убывания и выбрать наименьшую группу, удовлетворяющую условию: вероятность попадания значения Bi в данную группу больше или равна Pi (для этого суммарная вероятность группы должна быть больше или равна Pi). Тогда задача будет сведена к детерминированной: (^C,X)àMAX AX<=~B, где ~B=(~B1,~B2,...,~Bm)