Рассмотрим стохастический аналог общей задачи квадратичного программирования со строго выпуклой целевой функцией и линейными ограничениями [351] [c.114]
Задача (4.1) сглаживания и упреждения по минимуму второго момента ошибок и более общая задача стохастического программирования вида (3.12) могут быть модифицированы и сформулированы в терминах фильтрации и прогнозирования случайных полей. Конструктивные методы построения оптимальных пространственно-временных фильтров разработаны, однако, до сих пор только для-задач вида (4.1). Вычисление характеристик оптимальных фильтров для сглаживания и прогнозирования случайных полей основано на соотношениях, естественным образом обобщающих формулы (4.2) и (4.8). [c.316]
Таким образом, в общем случае решение задачи стохастического программирования представляет собой решающее правило или решающее распределение, зависящее, вообще говоря, от двух групп факторов. Факторы первой группы не связаны с наблюдением текущих значений параметров условий задачи. Они определяются априорной информацией— некоторыми характеристиками распределения или выборкой возможных значений случайных параметров условий. Факторы первой группы могут быть заблаговременно использованы для построения (или для последовательного совершенствования) решающего правила или решающего распределения. Факторы второй группы определяются апостериорной информацией, появляющейся в результате наблюдения за конкретной реализацией параметров условий задачи. [c.5]
Решение задач стохастического программирования требует, таким образом, в общем случае вычисления не систем чисел, а систем функций или вероятностных распределений —решающих правил или решающих распределений задачи. В отдельных случаях из содержательных соображений или для упрощения расчетов функциональный вид решающих правил (или распределений) задается заранее и стохастическая задача сводится к детерминированной задаче математического программирования, в которой требуется вычислить значения параметров решающего правила (или решающего распределения). [c.6]
В периодической литературе последних лет обсуждается большое число моделей планирования, управления и проектирования в условиях неполной информации., К сожалению, гораздо меньше появляется работ по конструктивным методам анализа таких моделей. Именно поэтому в монографию наряду с общими, как правило, трудоемкими методами анализа задач стохастического программирования включено значительное количество частных методов, каждый из которых эффективен для ограниченного круга приложений. Представляется, однако, что некоторое разнообразие частных методов, нарушающее иногда единый подход к исследованию моделей стохастического программирования, не нанесет ущерба целеустремленному изложении)1 материала и оправдает себя расширением диапазона возможных приложений и интересом к ним со стороны специалистов по сложным системам различного профиля. [c.7]
Мы рассматривали стохастические аналоги задач линейного программирования. Как легко видеть, детерминированные эквиваленты задач линейного программирования со случайными параметрами условий, соответствующие, например, моделям с вероятностными ограничениями, представляют собой, вообще говоря, задачи нелинейного, а иногда и невыпуклого программирования. Поэтому в стохастическом программировании обычно несущественно, порождена ли стохастическая задача линейной или нелинейной экстремальной задачей. Если не ограничиваться стохастическими аналогами линейных моделей, можно привести более общую запись задачи стохастического программирования, объединяющую различные постановки стохастических задач. [c.10]
Методы адаптации представляют собой достаточно общий итеративный процесс решения задач стохастического программирования — процесс совершенствования решающих правил или статистических характеристик решающих распределений — по последовательным реализациям наборов случайных параметров условий задач. Формальная основа методов адаптации — различные обобщения схемы стохастической аппроксимации. [c.15]
Достаточно общая модель стохастического управления представляет собой модель стохастического программирования, в которой требуется минимизировать средний риск или максимизировать среднюю полезность— математическое ожидание некоторой случайной функции от параметров состояния и, возможно, от параметров управления — при трех группах условий. Первая группа условий связывает параметры состояния в различные моменты времени с параметрами управления. Эта группа условий определяет механизм функционирования системы. Такие ограничения задаются обычно в жесткой форме. Учитывая, однако, случайные возмущения, возникающие на входе системы, и погрешности наблюдения состояний системы, может оказаться целесообразным заменить жесткие ограничения, описывающие механизм функционирования устройства, вероятностными. Вторая и третья группы условий фиксируют допустимые области определения переменных состояния и соответственно параметров управления в различные моменты времени. В зависимости от содержательных особенностей задачи эти ограничения могут быть статистическими, вероятностными или жесткими. [c.45]
В 1—2 рассматриваются стохастические задачи с вероятностными ограничениями, порожденные моделями линейного программирования. В 1 оператор вероятности применяется к каждой строке ограничений в отдельности, а в 2 — одновременно к совокупности всех ограничений. В обоих параграфах рассматриваются такие распределения случайных параметров условий, при которых эквивалентные детерминированные задачи оказываются задачами выпуклого программирования. Параграф 3 посвящен построению эквивалентных детерминированных моделей для общей одноэтапной стохастической задачи с вероятностными ограничениями, порожденной, вообще говоря, нелинейной моделью математического программирования. В 4 рассматриваются две простые, но представляющие интерес для приложений частные модели стохастических задач, в которых решения определяются в детерминированных векторах. Параграфы 5—6 посвящены стохастическим моделям оценки невязок с детерминированными оптимальными планами. В 5 рассматривается классификация таких моделей. В 6 исследуются условия, при которых соответствующие детерминированные эквивалентные задачи являются задачами выпуклого программирования. Ясно, что только в таких случаях можно говорить о конструктивных методах решения задачи. [c.62]
В предыдущих параграфах рассмотрены частные стохастические задачи с вероятностными ограничениями, порожденные моделями линейного программирования. Специфика стохастического характера условий позволила в каждом из рассмотренных случаев построить эквивалентную детерминированную задачу. Ниже приводится достаточно общий прием построения детерминированного эквивалента для широкого класса задач стохастического программирования, решение которых определяется среди детерминированных векторов. [c.74]
Различные модели стохастического программирования связаны с различными подходами к определению плана стохастической задач и к выбору правила предпочтения одних планов другим. Известны попытки единого подхода к разным классам задач стохастического программирования. Однако, как правило, такие подходы не позволяют получать общие качественные закономерности и тем более численные методы анализа разных моделей, формально включенных в единый класс. Несмотря на это, изучение общих подходов содействует установлению взаимосвязей между различными моделями — существенных для рациональной формализации практических задач управления в условиях неполной информации. [c.78]
Рассмотрим достаточно общий подход к одноэтапным моделям линейного стохастического программирования с априорными решающим правилами. Этот же подход может быть использован для классификации задач с априорными решающими распределениями. Различные по- [c.78]
Необходимые условия экстремума представляют собой достаточно общий аппарат для установления функционального вида решающих правил задач стохастического программирования. [c.133]
Как мы видели, наиболее трудная часть решения двухэтапной задачи стохастического программирования—определение предварительного плана — сводится к решению эквивалентной детерминированной задачи. Доказано, что эквивалентная задача является задачей выпуклого программирования. Однако в общем случае для ее решения стандартные методы выпуклого программирования неприменимы. Дело в том, что как целевая функция, так и область определения планов общей двухэтапной задачи заданы неявно. Показатель качества решения эквивалентной задачи далеко не всегда представляет собой дифференцируемую функцию. Вычисление параметров задачи, используемых в стандартных методах решения выпуклых задач, сопряжено со значительными трудностями. Существующие методы решения двухэтапных задач стохастического программирования используют специфические особенности эквивалентной детерминированной задачи. В настоящем параграфе рассмотрены общие и специальные методы вычисления предварительного плана и некоторые неравенства, позволяющие получить и оценить приближенные решения эквивалентной задачи. Ясно, что во всех частных случаях, в которых удается получить явную запись эквивалентной задачи в виде простой линейной, кусочно-линейной или выпуклой задачи, нет необходимости прибегать к предлагаемым здесь, вообще говоря, трудоемким методам. [c.180]
Введенные понятия и обозначения позволяют сформулировать общую схему многоэтапной задачи стохастического программирования с условными статистическими ограничениями. [c.193]
Теория многоэтапного стохастического программирования еще слабо развита. Конструктивных методов решения задач достаточно общего вида в настоящее время нет. Имеются лишь методы решения частных классов многоэтапных стохастических задач с условными или безусловными вероятностными ограничениями. Чтобы расширить круг приложений разрабатываемых конструктивных вычислительных методов, естественно попытаться установить связь между задачами с условными и безусловными статистическими ограничениями, отвечающими одним и тем же функциям фо(ы", хп) и г з/((сой, xh), k = ],. .., п. [c.198]
В общем случае неясно, как записать выражения для области К в более конструктивной форме. В этом трудность исследования задач стохастического программирования с безусловными вероятностными ограничениями. Однако при некоторых частных предположениях относительно вида решающих правил [или относительно функций распределения Fbv(-)] удается получить явное выражение для области (4.7) и решить задачу (4.8). [c.200]
В главе приводится качественное исследование многоэтапных задач -стохастического программирования с апостериорными решающими правилами ( 1). В 2 формируется общий рекуррентный алгоритм построения апостериорных решающих правил. В 3 алгоритм конкретизируется применительно к многоэтапной стохастической задаче с условными вероятностными ограничениями, а в 5 — применительно к многоэтапной квадратичной задаче с условными статистическими. ограничениями. Параграф 4 посвящен Л-задаче, двойственной к многоэтапной задаче стохастического программирования. [c.207]
Приведем общую схему построения апостериорных решающих правил для многоэтапной задачи стохастического программирования с условными вероятностными ограничениями. Эта задача представляет собой частный случай модели (1.1) — (1.2), в которой на каждом этапе ФА(ШЙ, х11) представляет собой характеристическую функцию случайного множества Gk(u>h, ft 1), зависящего от решений, выбранных на предшествующих этапах, [c.212]
При достаточно общих предположениях относительно структуры. модели можно указать конструктивные пути построения и анализа Л-задачи для вычисления апостериорных решающих правил многоэтапных задач стохастического программирования [362, 364]. [c.214]
Рассмотрим общую многоэтапную задачу стохастического программирования с условными статистическими ограничениями [c.252]
Отметим, что многоэтапные задачи стохастического программирования не являются тривиальными обобщениями двухэтапных задач. Многие результаты, справедливые для двухэтапных задач общего вида, неверны для многоэтапных. Например, оптимальные решающие правила линейных двухэтапных задач с вероятностными ограничениями — кусочно-линейные функции от некоторых случайных параметров условий задачи. Для многоэтапных задач это утверждение, вообще говоря, неверно [70]. [c.256]
Общие постановки стохастических задач, изложенные в гл. 9, также могут служить основанием для классификации моделей стохастического программирования (см. 5 гл. 9). Можно ожидать, что синтез различных подходов к классификации стохастических моделей приведет к более общей постановке задачи стохастического программирования и расширит круг задач, рассматриваемых с единой точки зрения. [c.262]
Как мы видели, точные методы вычисления функции распределения Q(L ) оптимального значения линейной формы задачи линейного стохастического программирования в общем случае неконструктивны. Функция Q(L ) необходима для решения многих практических задач. Поэтому значительный интерес представляют приближенные методы оценки и вычисления (Ь ). В ряде случаев вполне приемлемые оценки можно получить, исходя из соотношений (3.5) и известного неравенства Чебышева. 19 291 [c.291]
В настоящей главе излагаются различные постановки задач сглаживания и экстраполяции случайных процессов и указываются общие схемы стохастического программирования, в которые они могут быть уложены. Общие подходы стохастического программирования позволяют модифицировать модели фильтрации и прогноза, унифицируют методы анализа и расширяют область их приложения. [c.301]
Как видим, задача сглаживания и прогнозирования по минимуму второго момента ошибок прогноза является в общем случае задачей стохастического программирования с выпуклым целевым функционалом и статистическими, вероятностными или жесткими ограничениями. [c.310]
Таким образом, вычисление оптимальной функции веса, отвечающей сглаживанию или упреждению по минимуму второго момента ошибок, сводится в общем случае ас задаче бесконечно-мерного стохастического программирования с квадратичным целевым функционалом. [c.311]
В общем случае задача фильтрации и прогноза представляет сабой следующую задачу стохастического программирования [c.323]
Стохастическая аппроксимация в широком смысле слова представляет собой общий метод решения условных экстремальных задач при неполной информации об исходных данных. Мы будем рассматривать стохастическую аппроксимацию как общий итеративный метод решения задач стохастического программирования по последовательным реализациям случайных наборов параметров условий задачи. Такой подход к стохастической аппроксимации влияет известным образом и на ее проблематику и направления развития. [c.341]
Общая многоэтапная задача стохастического программирования с условными статистическими ограничениями 252, 257 [c.396]
Каждый из четырех подходов к динамическому инвестированию имеет в себе нечто привлекательное. Решающие правила гораздо проще для реализации, а соответствующие оптимизационные задачи не заставляют нас прибегать к крупномасштабным процедурам линейного и нелинейного программирования. Они могут быть без труда протестированы на выбранных сценариях (путем имитации) и обеспечивают приемлемые доверительные интервалы для рекомендаций. Они интуитивно ясны для большинства профессиональных инвесторов. Однако они способны привести к невыпуклым моделям оптимизации, которые требуют интенсивных расчетов для нахождения глобально-оптимального решения. Кроме того, правила, естественно, могут привести к субоптимальному поведению. Стохастическое программирование дает основу для построения моделей общего назначения, которые могут принимать во внимание особенности реального мира, такие как ограничения на оборотные средства опера- [c.20]
Стохастическое управление - это еще одна общая схема для решения задач общего характера. Он применим к тем задачам, где можно реально оперировать в пространстве состояний, т.е. к задачам с тремя или четырьмя (самое большое) переменными. Как и при стохастическом программировании, трудно сгенерировать доверительные пределы. Ошибки моделирования могут также возникать из-за аппроксимации в пространстве состояний. Трудность в точном определении общих ограничений на процесс сужает область приложений метода стохастического контроля. Однако метод имеет концептуальное превосходство над стохастическим программированием (в тех случаях, когда метод может быть реализован на практике), [c.21]
По аналогии с приведенными моделями могут быть исследованы постановки стохастических транспортных задач, в которых случайными являются объемы производства аг = аг((о), и более общие модели, в которых не могут быть заранее предсказаны как объемы производства, так и спрос в пунктах потребления. Известны только статистические характеристики соответствующих случайных величин. Анализ всех этих. моделей сводится к решению задач выпуклого или линейного программирования в зависимости от того, имеем ли мы дело с непрерывно или дискретно распределенными случайными параметрами условий задачи. [c.38]
Метод основан на общих свойствах детерминированной задачи, эквивалентной двухэтапной стохастической задаче, и на идее выпуклого программирования, принадлежащей Келли. [c.184]
Обзор работ по специальной задаче стохастического программирования — задаче фильтрации и прогноза — и по итеративным методам стохастического программирования, связанным со стохастической аппроксимацией, приведены соответственно в гл. 14 и 15 настоящей монографии. Попытки получения общего подхода к различным схемам стохастического программирования предпринимались в работах И. Лемари [183], Д. Б. Юдина (352, 353], Ю. М. Ермольева [105, 107]. [c.18]
В настоящей главе обсуждаются методы построения решающих правил для одноэтапных задач стохастического программирования, а для отдельных моделей приводятся и явные выражения для решающих правил. В 1 рассматриваются частные модели первого класса, в которых предполагается, что решающие правила — линейные функции случайных составляющих условий задачи. Вычисление параметров решающих правил сводится к задачам выпуклого программирования. Параграф 2 посвящен изучению. М-модели с вероятностным ограничением общего вида. Относительно решающего правила л (со) не делается никаких предположений, кроме того, что л (со)—измеримая вектор-функция на множестве X произвольной структуры, на котором она определена. В 3 метод построения решающих правил из предыдущего параграфа обобщается на М-модель с конечнозначным ограничением — с условием, ограничивающим математическое ожидание случайной функции от х, принимающей конечное число значений. Таким условием может быть аппроксимировано любое статистическое ограничение. В 4 построены решающие правила (точнее, решающие таблицы) дляч Р-мо-дели с вероятностными ограничениями общего вида. В 5 рассматривается стохастическая задача со смешанными ограничениями. Эта модель отличается от задачи 4 дополнительными условиями, которые могут существенно изменить структуру решения. В 6—8 построены решающие правила для одноэтапных задач стохастического программирования со статистическими ограничениями достаточно общего вида. Модель, изученная в 6, представляет собой стохастический аналог общей задачи линейного программирования с двухсторонними ограничениями. Модель из 7 — стохастический аналог общей задачи квадратичного программирования. Модель, исследованная в 8, является стохастическим аналогом частной задачи выпуклого программирования с квадратичной целевой функцией и квадратичными ограничениями. Заключительный параграф главы ( 9) посвящен итеративным методам построения решающих правил одноэтапных задач стохастического программирования. [c.84]
Ермольев Ю. М. Об одной общей задаче стохастического программирования. — Кибернетика , 1971, № 8, с. 47—50. [c.385]
Итеративный метод решения двухэтапных задач, не требующий априорных характеристик случайных параметров условий, разработан Ю. М. Ермольевым и Н. 3. Шорам [110]. Ерю.шеву принадлежит, кроме того, ряд общих подходов к анализу задач стохастического программирования [104—109]. [c.17]
Как мы видели выше, общие методы решения двухэтапной задачи стохастического программирования достаточно трудоемки. Трудности численного анализа двухэтапной задачи возрастают, если нет явного выражения для множества К предварительных планов задачи. Один из подходов к приближенному анализу решения двухэтапной задачи заключается в оценке оптимального значения ее целевой функции. Двухэтапной задаче приводятся в соответствие детерминированные задачи, оптимальные значения показателей качества которых оценивают сверху и снизу целевую функцию стохастической задачи на оптимальном предварительном плане х. Обычно решения соответствующих детерминированных задач являются неплохими начальными приближениями для итерационных методов решения двухэтатшых задач. Далее предполагается, что В и q детерминированы. [c.190]
Итак, рассмотрены две возможные постановки задачи стохастического программирования. Надо сказать, что имеется и общая постановка такой задачи, но здесь не стбит ее [c.121]