Вариация условий стохастической задачи МП и оценка влияния уровня стохастичности информации на результаты

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

1) Случаен только вектор С функции цели, остальная информация детерминирована.

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

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

а) Решение задачи Х рассматривается как детерминированный (фиксированный) вектор; допустимым решением (планом) считается такой вектор Х, который удовлетворяет ограничениям задачи при всех возможных сочетаниях значений А и В, имеющих положительную вероятность; это жесткая постановка задачи, не использующая дополнительных сведений относительно статистических характеристик условий в модели. A(q)*X<=B(q) для всех q@Q,X>=0

Здесь q‑случайные параметры, от которых зависят значения А и В (состояния природы), их набор обычно считается конечным;

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

в) Р(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) при условии жесткой постановки (одноэтапной);