Стохастические задачи

А. Стохастическая неопределенность

В этих условиях W дополнительно зависит от неизвестных факторов -неопределенности ξ, тогда w=w(а, х, ξ). Задача поиска оптимальных решений теряет прежний смысл и ищется х* € Х, который дает W= maxW. «Этот» х* в общем случае хуже, чем в детерминированном случае, так как его уменьшает неопределенность. Для решения этого типа задач разработан ряд методов, различающихся природой ξ.

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

Пример стохастической задачи: Организация службы обслуживания и ремонта технологической линии. В этом случае неопределенность ξ – характеризует отказы оборудования. Частоту и длительность возникновения отказов будем считать известными. Так как W – случайная неконтролируемая в данный момент величина, то искать ее максимум бессмысленно.

Напрашивается мысль заменить ξ одним или несколькими (в зависимости от задачи) средними значениями – математическими ожиданиями ее элементов, тогда задача становится детерминированной и все решается.

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

Пример.

При стыковке космических кораблей штанга одного должна войти в зону ее приема на другом корабле. Управление возможно как в автоматическом, так и в ручном режиме. При выполнении этой операции возможны сбои и необходимы повторные сближения, в конечном итоге – стыковка. Дисперсия ошибки сближения достаточно мала, а мат.ожидание равно нулю, но, тем не менее, принять вероятность сближения W за 1 нельзя, так как это будет означать, что стыковка всегда осуществляется с первого раза, что исключает необходимость резерва топлива на сближение, а это, в принципе, неверно.

Аналогичный пример.

В тире за попадание в десятку платят 10 рублей. Студенту надо заработать 100 рублей. Сколько раз он должен выстрелить?

Если примем вероятность попадания W в десятку за 1, то 10 раз. Но W случайная величина и поэтому может быть промах и можно лишь сказать, что необходимо не менее 10 выстрелов.

И, наконец, последний вариант ξ – существенно случайна, а, следовательно, также и существенно случайная величина W. Как быть в этом случае?

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

W=Wсредн=М [W], т.е. осредненное значение W по условиям (а) и выбирать такое значение, при котором

М [W(а, ξ, х)]=> max

Таким образом, принимается за показатель эффективности среднее значение W по а

W= М[W]

 

В литературе такой подход называется оптимизацией в среднем. Например, рассматривается не просто «расход», «доход», «время», а их средние значения. Такой подход применим если операция обладает свойством повторяемости с различным итогом, значения которого при повторах выравниваются (игра в казино, игра в зале игральных автоматов и др). Наряду с этим существует класс задач, которые не обладают такими свойствами, поэтому прием оптимизации в среднем необходимо дополнить стохастическими ограничениями – иначе может быть катастрофический итог.

 

Пример.

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

Если использовать оптимизацию в среднем, то получим в среднем минимальное время обслуживания. Ясно, что при этом может быть время Т превосходящее заданное T_max, т.е. t> Т_max, что недопустимо. В тоже время, так как t случайная величина, нельзя потребовать, чтобы t ≤ T_max, т.е. жестко не превосходило T_max. В таких условиях требование можно записать так

P (t ≤ T_max) ≥ β,

и непременно потребовать, чтобы вероятность события t ≤ T_max выполнялось с возможно более высокой вероятностью. Например, если принять β =0, 9999, то такое событие будет практически достоверным. Такое введение ограничения на время исключают решения, которые ему не удовлетворяют. Эти ограничения называются стохастическими. Они, как правило, значительно осложняют решение задач оптимизации.

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

Т..е. осредненное значение W по условиям а и выбирать такое решение х, при котором

М [W(а, ξ, х)]=> max,

Таким образом, за показатель эффективности принимается среднее значение W(а) и выбирается х, дающий max M[W]