Здавалка
Главная | Обратная связь

Недетерминированные задачи. Принцип гарантированного результата



Недетерминированная задача- задача, в которой присутствуют неконтролируемые факторы у.

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

Т.е целевая функция включает в качестве аргументов случайные величины, т.е W(х,у)=W(х, ).

В этом случае можно оценить эффективность как математическое ожидание от целевой функции х, ).В данном случае уже имеет место детерминированная задача поиска на экстремум.

Далее необходимо ответить на вопрос: как решать задачи, если в них известен диапазон значений У неконтролируемых факторов? Ответ на этот вопрос дает принцип гарантируемости результата. Если использовать данный принцип, то необходимо рассматривать пользу значения критерия эффективности при всех возможных . Рассмотрим работу принципа гарантируемости результата на примере задачи о курьере, предположив, что место расположения выхода на конечной станции не явл. случайной величиной, обозначив через f(x) функцию, которая опр. расстояние от места высадки из поезда до выхода из конечной станции, если этот выход расположен в начале платформы, а через (х) обозначим функцию работ, если выход расположен в конце платформы. Очевидно что (х)=x,а (х)=L- .

Наихудшим результатом для курьера явл. max из вышеперечисленных функций: , поэтому данная задача сводится к задаче минимизации : min max{х,1-х}. Довольно часто принцип гарантированного результата используется при решении задачи теории игр







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.