МОДЕЛИ СО СЛУЧАЙНЫМИ ПАРАМЕТРАМИ
Неопределенности, встречающиеся в тех или иных моделях операций, весьма разнообразны. Отсутствие сведений о целевой функции и связанные с этим последствия, обсуждавшиеся в гл. 10, не исчерпывают всей проблемы неполноты моделей. Практика показывает, что предположения, заменяющие собой точную информацию об изучаемом объекте, могут относиться (и формально, и посуществу) к любым элементам исследуемых задач — функциям цели как таковым, их отдельным свойствам, ограничениям, погрешностям вычислений т т.п.
Своеобразные ситуации возникают в тех случаях, когда какие-то параметры изучаемой модели имеют вероятностную природу. Классическим примером здесь является задача линейного программирования со случайными коэф-
п
фициентами Cj выражения z — 2 c/xj- Ее можнорешать
/= і
обычными способами (см. гл. 2), заменяя с} математическим ожиданием rn(Cj) (метод средних оценок), однако этот путь при своей внешней привлекательности приводит к результатам, полезность которых должна проявиться в многократно повторяемых решениях. Аналогичная картина наблюдается и при анализе оптимизационных задач других классов со случайностями, поэтому все разрабатываемые для них методыобъединены общим названием «стохастическое программирование» (от греческого stochastikos — умеющий верно угадывать).
Основные трудности стохастического программирования связаны с тем, что не всегда удается ограничиться понятиями, используемыми в детерминированных моделях, хотя именно такая попытка делается в упоминавшемся методе средних оценок. Приходится разрабатывать специальные приемы поискарешений, предполагающие сознательное введение элемента случайности в действия исследователя с целью компенсировать исходную неопределенность. С этой точки зрения практический интерес представляют методы стохастической аппроксимации и методы случайного поиска, рассматриваемые ниже.
§ 11.1. Ошибки эксперимента.
Информационный аспект проблемы
Обратимся к изучению схем поиска X*, г*, содержащих элементслучайности. Для простоты сначала рассмотрим задачи, в которых целевая функция имеет скалярный аргумент (см. § 10.1).
Предположим, что эксперименты, проводимые для оценки значений целевой функции z=f(x), содержат ошибки 6Z. Эти ошибки являются случайными и носят аддитивный характер, так что измеренная величина z есть сумма истинного, но неизвестного исследователю значения ги и указанной 8г, т. е. z=zH+6z.
Чтобыучесть присутствие ошибки 6г, необходимо располагать теми или иными сведениями о ней, причем полнота этих сведений может меняться в широких пределах, начи-
ная от законов совместного распределения ошибок в разных экспериментах и кончая моментами (математическим ожиданием и дисперсией) величины 6г при конкретном X.
Пусть на интервале [0, 1] выбрана точка х, и требуется получить оценку ги=/(х) вусловиях, когда известно ЛИШЬ математическое ожидание т(Ьг). Подобная задача возникает при попытке реализовать какую-либо из детерминированных процедур поиска ** путем многократного повторения экспериментов в jt и использования получаемых г для вычисления среднего z. Зная т(б2), легко находим г„ — — z—т(6г). Чем выше требования к точности оценки г„, тем больше затраты средств и времени на получениенужного результата.
Вопрос о том, можно ли избежать указанных затрат (или как-то уменьшить их) решается на основе следующих рассуждений. Если в данной точке х проведены N экспериментов и определены гш, г12' г(Л0, образующие стати-
N
стику, то допустимо считать zN = -дг V, гш. Если бы число
(= і
экспериментов составило N—1, то оценка г имела бы вид
л'-1
г,у_ і = v 1 t У, г'1"'. Сравнивая этиформулы, приходим ' г= і
_ /у і _ j
к соотношению гЛг =—— 2,v_^ -f -дг г(Л'\ которое показывает, что величина 2 гяк+бгЛ). Очевидно, характер преобразования (алгоритмического отображения) Wh должен влиять на сходимость последовательности значений хь (А = 1, 2, . . .) к некоторому пределу х или х*. Если, например, Wk таково, что xh+i = Wih(xk, s) + Wihfizk), то,...
Неопределенности, встречающиеся в тех или иных моделях операций, весьма разнообразны. Отсутствие сведений о целевой функции и связанные с этим последствия, обсуждавшиеся в гл. 10, не исчерпывают всей проблемы неполноты моделей. Практика показывает, что предположения, заменяющие собой точную информацию об изучаемом объекте, могут относиться (и формально, и посуществу) к любым элементам исследуемых задач — функциям цели как таковым, их отдельным свойствам, ограничениям, погрешностям вычислений т т.п.
Своеобразные ситуации возникают в тех случаях, когда какие-то параметры изучаемой модели имеют вероятностную природу. Классическим примером здесь является задача линейного программирования со случайными коэф-
п
фициентами Cj выражения z — 2 c/xj- Ее можнорешать
/= і
обычными способами (см. гл. 2), заменяя с} математическим ожиданием rn(Cj) (метод средних оценок), однако этот путь при своей внешней привлекательности приводит к результатам, полезность которых должна проявиться в многократно повторяемых решениях. Аналогичная картина наблюдается и при анализе оптимизационных задач других классов со случайностями, поэтому все разрабатываемые для них методыобъединены общим названием «стохастическое программирование» (от греческого stochastikos — умеющий верно угадывать).
Основные трудности стохастического программирования связаны с тем, что не всегда удается ограничиться понятиями, используемыми в детерминированных моделях, хотя именно такая попытка делается в упоминавшемся методе средних оценок. Приходится разрабатывать специальные приемы поискарешений, предполагающие сознательное введение элемента случайности в действия исследователя с целью компенсировать исходную неопределенность. С этой точки зрения практический интерес представляют методы стохастической аппроксимации и методы случайного поиска, рассматриваемые ниже.
§ 11.1. Ошибки эксперимента.
Информационный аспект проблемы
Обратимся к изучению схем поиска X*, г*, содержащих элементслучайности. Для простоты сначала рассмотрим задачи, в которых целевая функция имеет скалярный аргумент (см. § 10.1).
Предположим, что эксперименты, проводимые для оценки значений целевой функции z=f(x), содержат ошибки 6Z. Эти ошибки являются случайными и носят аддитивный характер, так что измеренная величина z есть сумма истинного, но неизвестного исследователю значения ги и указанной 8г, т. е. z=zH+6z.
Чтобыучесть присутствие ошибки 6г, необходимо располагать теми или иными сведениями о ней, причем полнота этих сведений может меняться в широких пределах, начи-
ная от законов совместного распределения ошибок в разных экспериментах и кончая моментами (математическим ожиданием и дисперсией) величины 6г при конкретном X.
Пусть на интервале [0, 1] выбрана точка х, и требуется получить оценку ги=/(х) вусловиях, когда известно ЛИШЬ математическое ожидание т(Ьг). Подобная задача возникает при попытке реализовать какую-либо из детерминированных процедур поиска ** путем многократного повторения экспериментов в jt и использования получаемых г для вычисления среднего z. Зная т(б2), легко находим г„ — — z—т(6г). Чем выше требования к точности оценки г„, тем больше затраты средств и времени на получениенужного результата.
Вопрос о том, можно ли избежать указанных затрат (или как-то уменьшить их) решается на основе следующих рассуждений. Если в данной точке х проведены N экспериментов и определены гш, г12' г(Л0, образующие стати-
N
стику, то допустимо считать zN = -дг V, гш. Если бы число
(= і
экспериментов составило N—1, то оценка г имела бы вид
л'-1
г,у_ і = v 1 t У, г'1"'. Сравнивая этиформулы, приходим ' г= і
_ /у і _ j
к соотношению гЛг =—— 2,v_^ -f -дг г(Л'\ которое показывает, что величина 2 гяк+бгЛ). Очевидно, характер преобразования (алгоритмического отображения) Wh должен влиять на сходимость последовательности значений хь (А = 1, 2, . . .) к некоторому пределу х или х*. Если, например, Wk таково, что xh+i = Wih(xk, s) + Wihfizk), то,...
Поделиться рефератом
Расскажи своим однокурсникам об этом материале и вообще о СкачатьРеферат