Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


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




Рассматривается задача ЛП, в которой требуется найти максимум линейной формы 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)

       
 
   
 






Поделиться с друзьями:


Дата добавления: 2015-09-20; Мы поможем в написании ваших работ!; просмотров: 464 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Самообман может довести до саморазрушения. © Неизвестно
==> читать все изречения...

2571 - | 2410 -


© 2015-2025 lektsii.org - Контакты - Последнее добавление

Ген: 0.012 с.