В одноэтапных задачах решение представляет собой детерминированный вектор, определенный до наблюдения случайных параметров условий на основе априорной оценки ситуации, или решающее правило, позволяющее вычислить численное значение решения в зависимости от реализованных значений случайных исходных данных. В зависимости от содержания решение стохастической задачи определяется в чистых или смешанных стратегиях. В чистых стратегиях механизм решения является детерминированным и определяет решение в виде вектора или вектор-функции, зависящей от случайных исходных данных. Смешанная стратегия использует случайный механизм решения и определяет решающие распределения. [c.54]
В зависимости от последовательности чередования процедур решение" или наблюдение" решающие правила и решающие распределения определяются априорной или априорной и апостериорной информацией. [c.56]
Задача стохастического программирования (3.1) -(3.3) в зависимости от вида целевого функционала (3.1) преобразуется в одноэтапную М -модель с вероятностными ограничениями, одноэтапную /"-модель с вероятностными ограничениями, одноэтапную /"-модель со смешанными условиями (для решения этих моделей используются априорные или апостериорные решающие правила) либо в одноэтапную задачу с построчными вероятностными ограничениями и решающими правилами нулевого порядка. [c.57]
Априорные решающие правила многоэтапной задачи (3.14)— (3.16) соответствуют последовательности решение — наблюдение — решение — наблюдение-... -решение" и имеют вид xt=xt( i) (t—2, 3,..., Т). В задачах этого класса решение Х выбирается на основе априорной оценки начального состояния среды j0, а решение t-ro этапа принимается после реализации случайных параметров условий на предыдущем (t - 1) -м этапе. [c.59]
Априорную плотность вероятности можно оценить различными способами. В параметрических методах предполагается, что плотность вероятности (PDF) является функцией определенного вида с неизвестными параметрами. Например, можно попробовать приблизить PDF при помощи гауссовой функции. Для того чтобы произвести классификацию, нужно предварительно получить оценочные значения для вектора среднего и матрицы ковариаций по каждому из классов данных и затем использовать их в решающем правиле. В результате получится полиномиальное решающее правило, содержащее только квадраты и попарные произведения переменных. Вся описанная процедура называется квадратичным дискриминантным анализом (QDA). В предположении, что матрицы ковариаций у всех классов одинаковы, QDA сводится к линейному дискриминантному анализу (LDA). [c.47]
Таким образом, в общем случае решение задачи стохастического программирования представляет собой решающее правило или решающее распределение, зависящее, вообще говоря, от двух групп факторов. Факторы первой группы не связаны с наблюдением текущих значений параметров условий задачи. Они определяются априорной информацией— некоторыми характеристиками распределения или выборкой возможных значений случайных параметров условий. Факторы первой группы могут быть заблаговременно использованы для построения (или для последовательного совершенствования) решающего правила или решающего распределения. Факторы второй группы определяются апостериорной информацией, появляющейся в результате наблюдения за конкретной реализацией параметров условий задачи. [c.5]
В случаях, когда решение предшествует наблюдению, решающие правила и решающие распределения зависят только от детерминированных параметров и статистических характеристик случайных параметров условий задачи. В задачах, в которых решение следует за наблюдением, решающие правила (и статистические характеристики решающих распределений) представляют собой функции, таблицы или инструкции, устанавливающие зависимость решения как от априорной информации, так и от реализованных значений случайных параметров условий задачи. [c.5]
Аналогичные ситуации возникают при разработке алгоритмов управления случайными процессами или процессами, сопровождающимися случайными возмущениями. Оптимальный алгоритм целесообразно рассматривать как решение задачи стохастического программирования. Показатель качества и ограничения задачи определяются конкретным назначением алгоритма и априорными статистическими характеристиками случайных возмущений. Решение задачи естественно представлять в виде решающего правила, связывающего искомые параметры управления со случайными параметрами условий. Каждой реализации случайных параметров условий задачи отвечает реализация параметров управления и соответственно конкретная реализация алгоритма. [c.11]
В задачах стохастического программирования, отвечающих ситуациям,, в которых решение следует принимать до наблюдения реализации случайных условий и нельзя корректировать решение при получении информации о реализованных значениях случайных параметров, естественно определять оптимальный план в виде детерминированного вектора. Так определяется класс стохастических задач, для которых естественные решающие правила — правила нулевого порядка. Решение задач стохастического программирования Б виде случайного вектора позволяет установить связь между компонентами оптимального плана, реализациями параметров условий задачи и их априорными статистическими характеристиками. Каждой реализации условий задачи соответствует, таким образом, реализация решения. Следовательно, решение задачи стохастического программирования в виде случайного вектора целесообразно определять в ситуациях, в которых решение может быть принято после наблюдения реализации условий задачи. [c.12]
Можно (рассматривать две постановки задачи сглаживания и прогноза одноэтапную и многоэтапную. В одноэтапной постановке по известным статистическим характеристикам процессов v (t) и t,(t) определяются априорные или апостериорные решающие правила, необходимые для управления наборы = , i=l, , п, сглаженных или упрежденных точек — оценок r (ti + taj. Для вычисления необходимо задать (а) класс операторов, из которых выбираются структуры механизма связи t,i со значениями, К/) на (ti—Т, ti) (б) показатель качества прогноза R(L) и (в) область Q определения —набор ограничений, высекающих множество допустимых сглаженных или упрежденных точек. [c.39]
Последовательный процесс накопления информации е отражен в одноэтапной задаче сглаживания и прогноза. Все решения о прогнозах, отвечающих моментам ti,. . ., tn, принимаются одновременно. Одно-этапная задача фильтрации и прогноза описывается одноэтапной моделью стохастического прогнозирования. Априорные решающие правила задачи определяют структуру зависимости от значений ( t) на (J(ti— [c.39]
Анализ взаимосвязи задачи прогноза и задачи управления или планирования, ради которой производится прогнозирование, подсказывает подходящие информационные структуры решения. Можно указать ситуации, в которых решение следует определять в априорных или апостериорных решающих правилах. В гл. 14 указаны случаи, когда не существует решающих правил, удовлетворяющих условиям задачи прогноза при сложных критериях качества, но решение может быть получено в решающих распределениях. [c.43]
В результате решения задачи вычисляются детерминированная матрица А — характеристика объекта управления и закон управления u(t), который связывает очередной набор команд с наблюдаемыми векторами состояния х(0), х( ),. . ., x(t), определяющими пройденную системой ветвь траектории. В зависимости от постановки задачи закон управления определяется в виде априорных решающих правил или априорных решающих распределений. [c.51]
Подготовка решающих правил или решающих распределений, как и в любой многоэтапной задаче, связана с решением задачи с конца, начиная с s — 1-го этапа. Это довольно трудоемкая работа. Тем не менее, как показано в гл. 11, для ряда классов многоэтапных задач априорные решающие правила построены. В гл. 9 и 1 1 указаны приемы, позволяющие конструировать решающие правила и решающие распределения и для многоэтапных задач более сложной структуры. [c.51]
В настоящей главе под планом и оптимальным планом задачи подразумевается решающее распределение — безусловное или условное (в зависимости от постановки задачи) распределение компонент вектора х. Как и ранее, при рассмотрении решающих правил, целесообразно исследовать два крайних случая — априорные и апостериорные решающие распределения, отвечающие априорным и апостериорным решающим правилам при решении задачи в чистых стратегиях. Компоненты решения в априорных решающих распределениях, как и составляющие априорных решающих правил, не зависят от реализаций случайных значений параметров условий задачи. Составляющие апостериорных решающих распределений являются условными распределениями при фиксированных реализациях случайных исходных данных. Как и в предыдущей главе, естественно рассматривать случаи, когда функциональный вид решающего распределения задан и определению подлежат лишь параметры распределения, а также общий случай, когда вид распределения заранее не фиксирован. [c.134]
В [355 и 357] соответственно для априорных и апостериорных решающих правил рассматриваются достаточные условия, при которых оптимальное значение целевой функции на смешанных стратегиях — решающих распределениях — достигается также с помощью чистых стратегий — решающих правил. [c.134]
Оптимальная чистая стратегия х первого игрока представляет собой априорное решающее правило задачи стохастического программирования в игровой постановке. [c.137]
При анализе модели (3.7) — (3.9) с фиксированным функциональным видом апостериорного решающего распределения целесообразно рассматривать два варианта постановки задачи. В первом варианте вектор а статистических параметров фиксированного условного распределения Fx a предполагается не зависящим от реализации случая, т. е. FX °> = F(X а м)- Во втором варианте а=а(со) и Fx.—F(x, а(со), со). Анализ первого варианта сводится к вычислению априорного решающего правила (детерминированного вектора), представляющего собой оптимальный план стохастической задачи вида (4.8) — (4.9), в которой [c.144]
В задачах второго подкласса решение на t-м этапе принимается после реализации случайных параметров условий на предыдущем (г—1)-м этапе. Решающие правила задач второго подкласса имеют вид Xi = Xi((ui 1), i=l,. .., п. Будем называть задачи второго подкласса многоэтапными задачами стохастического программирования с условными статистическими ограничениями и с априорными решающими-правилами. [c.194]
При решении стохастических задач с апостериорными или априорными решающими правилами могут еще задаваться дополнительные требования на характер решающего правила вплоть до вида функциональной зависимости решающего правила от случайных параметров условий задачи. В последнем случае задача бесконечно-мерного программирования сводится к конечно-мерной задаче (или к последовательности конечно-мерных задач), в которой требуется вычислить оптимальные численные значения параметров решающего правила. Дополнительные требования к классу измеримых функций, из которых следует выбирать решение задачи (2.1) — (2.3.), могут определяться содержательными соображениями или необходимостью упростить построение и реализацию решающего правила. [c.194]
С одной стороны, решение выгодно принимать возможно позже. При этом может быть учтено больше полезной информации и облегчается прогноз последствий решения. Другие факторы требуют ускорить выбор решения. Запаздывание с решением приводит обычно к дополнительной затрате ресурсов. Конкретное содержание задачи определяет рациональный компромисс между противоречивыми требованиями к моменту выбора решения. Во многих случаях, конечно, содержательная постановка задачи однозначно определяет характер и даже общий вид решающих правил. До сих пор мы рассматривали решение многоэтапных задач в чистых стратегиях. Естественно, что все здесь сказанное об априорных и апостериорных решающих правилах можно применительно к случаю, когда многоэтапные задачи решаются в смешанных стратегиях, повторить и для априорных и апостериорных решающих распределений. Как видно, однако, из материалов гл. 5, практические "приемы построения решающих распределений связаны с существенно более трудоемкой работой, чем вычисление соответствующих решающих правил. Во всех случаях, когда решение многоэтапных задач сводится к анализу соответствующих одноэтапных стохастических задач, вычисление оптимальных смешанных стратегий проводится согласно рекомендациям гл. 5. [c.195]
Подчеркнем особенности решения многоэтапных стохастических задач с условными статистическими ограничениями. Проведем рассуждения в терминах априорных решающих правил. Обсуждение особенностей решения задач с апостериорными решающими правилами проводится по такой же схеме. [c.195]
Для априорных решающих правил [c.196]
Теорема 4.1. Пусть А — множество допустимых решающих правил (апостериорных пли априорных) многоэтапной стохастической задачи с безусловными статистическими ограничениями [c.198]
Параграф 1 посвящен качественному исследованию целевого функционала и области определения априорных решающих правил многоэтапной линейной М-модели с условными вероятностными ограничениями. В 2 рассмотрены частные модели, относительно матриц усло- [c.233]
Как мы видели, вычисление априорных решающих правил линейной многоэтапной стохастической задачи с условными вероятностными ограничениями сводится к решению задачи вида (1.6) — (1.8). Условная функция распределения компонент вектора bi при фиксированном наборе со1 -1 предполагается известной. Однако вычисление [c.239]
Таким образом, при принятых допущениях априорные решающие правила задачи (3.6) — (3.9) могут быть вычислены с помощью методов выпуклого программирования. [c.243]
Априорные решающие правила для частных классов линейных задач многоэтапного стохастического программирования [c.243]
При конструирований априорных решающих правил для всех моделей, рассматриваемых в настоящем параграфе, целесообразно учитывать следующее замечание. [c.243]
Теорема 4.1. При допущениях Г — 4° оптимальные априорные решающие правила задачи (1.3) -(1.5) имеют вид [c.243]
Во всех рассмотренных в настоящем параграфе моделях не было необходимости в индуцированных ограничениях, обеспечивающих разрешимость задач последующих этапов. Отсюда. простота анализа моделей. В тех случаях, когда структура условий многоэтапной стохастической задачи не исключает необходимости в индуцированных ограничениях, вычисление априорных решающих правил существенно усложняется. [c.247]
Априорные решающие правила для частного класса нелинейных задач стохастического программирования [c.250]
При допущениях, аналогичных допущениям п. 4.1, можно построить оптимальные априорные решающие правила для частного класса нелинейных многоэтапных задач стохастического программирования с условными вероятностными ограничениями. [c.250]
Теорема 5.1. При допущениях 1°—4° оптимальные априорные решающие правила задачи (5Л)—<(5.3) имеют вид [c.251]
В гл. 10 намечен общий подход к построению апостериорных решающих правил задачи (6.1) — (6.3). Конструирование априорных решающих правил связано с существенно большими теоретическими и вычислительными трудностями. В 4—5 указаны пути построения априорных решающих правил для частных классов многоэтапных стохастических задач. [c.252]
Ниже будут приведены некоторые соображения о сведении многоэтапной задачи с априорными решающими правилами к. двухэтапной задаче и о восстановлении по оптимальному плану двухэтапной задачи оптимальных решающих правил исходной задачи вида (6.1) — (6.3). Аналогичные рассуждения могут быть проведены и для случая сведения задачи к одноэтапной или любой другой, для которой имеются конструктивные приемы построения оптимальных решающих правил. 252 [c.252]
В частных случаях, рассмотренных в гл. 8, для вычисления Xi — решения задачи первого этапа — имеются конструктивные приемы. В общем случае, когда задача первого этапа оказывается выпуклой и область K=Ki П Kz ее определения задана явно, можно вычислить xi по методу стохастического градиента [107]. Знание je i=J i позволяет сократить число этапов в исходной задаче на единицу. Параметры условий полученной таким образом задачи зависят от реализации MI. В некоторых задачах специальной структуры параметрические методы исключают необходимость в решении множества задач, определяемых возможными реализациями он. В общем случае требуются весьма громоздкие вычисления. Для некоторого набора реализаций он, выбор которого обусловлен структурой задачи, следует, используя, например, метод стохастических градиентов, вычислить узлы сетки (таблицы). значений x z( i), по которой можно восстановить с требуемой точностью значения составляющих x z(u)i) для произвольной реализации он. Этот процесс может быть продолжен. Однако с увеличением числа этапов трудоемкость вычислений и требования к памяти чрезвычайно быстро растут. При немалых п представляется более перспективным сведение многоэтапной задачи к вычислению апостериорных решающих правил одноэтапных задач. Если восстановление априорных решающих правил исходной задачи по апостериорным решающим правилам одноэтапной задачи связано со значительными вычислительными трудностями, целесообразно после вычисления x i рассматривать второй этап задачи (6.7) — (6.9) (при каждой реализации oi) как одноэтапную-задачу с апостериорными решающими правилами. [c.254]
Рассмотренные в предыдущем пункте две схемы сведения многоэтапной задачи стохастического программирования с априорными решающими правилами к эквивалентной в некотором смысле двухэтапной могут быть модифицированы и обобщены. Каждая из рассмотренных схем является типичным представителем класса схем, приводящих в соответствие многоэтапным задачам двухэтапные и позволяющих по-решениям двухэтапной задачи получить оптимальные решающие правила исходной задачи. [c.255]
Подчеркнем еще раз, что рассуждения, аналогичные приведенным, позволяют привести в соответствие каждой многоэтапной задаче с априорными решающими правилами (так же как и задаче с апостериорными решающими правилами) одноэтапную стохастическую задачу, оптимальные апостериорные решающие правила которых позволяют получить оптимальные априорные решающие правила исходной задачи.. Вопрос о том, в каких случаях целесообразнее сводить многоэтапную задачу с априорными решающими правилами к одноэтапной или двухэтапной задаче, решается в каждом отдельном случае при сопоставлении трудоемкости решения эквивалентной задачи и восстановления по ее оптимальному плану оптимальных решающих правил исходной задачи вида (6.1) — (6.3). [c.256]
Приведем примеры вычисления априорных решающих правил многоэтапных задач стохастического программирования по решающим правилам эквивалентных двухэтапных и одноэтапных задач. [c.259]
Оптимальное решающее правило х задачи первого этапа вычисляется, например, по методу стохастических градиентов. Переход к априорным оптимальным решающим правилам х ( шь-1) исходной многоэтапной задачи (7.1) — (7.3) производится по формулам (6.10). В рассматриваемом примере они имеют вид [c.260]
Рассмотрим еще один пример многоэтапной задачи, оптимальные априорные решающие правила которой могут быть получены из решающих правил эквивалентной одноэтапной стохастической задачи [c.261]
Задача стохастического управления рассматривается как одноэтап-ная задача стохастического программирования, если описываемая моделью ситуация требует выбора закона управления для всей траектории системы (/ = 0, 1,. .., s—1) в один прием и коррекции по ходу управления в процессе накопления информации не допускаются. Априорные решающие правила определяют закон управления, зависящий только от детерминированных параметров и статистических характеристик случайных параметров условий задачи. Закон управления, определяемый апостериорными решающими правилами, зависит, кроме того, от реализации случайных исходных данных. Закон управления, соответствующий решающим распределениям, представляет собой случайный механизм формирования решения со статистическими характеристиками, зависящими (при апостериорных решающих распределениях) или не зависящими (при априорных решающих распределениях) от реализации случайных параметров условий задачи. Механизм управления, отвечающий решающим распределениям, может при одних и тех же реализациях исходных данных приводить к различным траекториям управления и, [c.45]
Построим априорные решающие правила еще для одного частного класса многоэтапной задачи линейного стохастического программирования с условными ве-.роятностными ограничениями вида (1.3 — (Р1.5). Как мы видели, такие задачи могут также быть переписаны в форме (1.6) — (1.8). [c.245]
Априорные решающие правила исходной задачи. (6.1) — (6.3) имеют вид x i = onst, x i = x i(