В настоящей главе приведены постановка и качественный анализ двухэтапной стохастической задачи. [c.152]
Таким образом, решение двухэтапной стохастической задачи состоит из двух векторов детерминированного л-мерного вектора х, определяющего предварительный план, и случайного / -мерного вектора у=у(ю), определяющего план компенсации невязок. [c.153]
В [14 — 47] общая схема двухэтапной стохастической задачи расширена таким образом, что в нее могут быть уложены двухэтапные задачи стохастического оптимального управления. Приведенные в этих работах постановки задач обобщают ряд моделей управления поведением динамических систем в условиях неполной информации. [c.164]
Приведем формальную постановку специального класса двухэтапных стохастических задач — двухэтапных задач оптимального управления в условиях неполной информации. [c.164]
Пусть по-прежнему случайными параметрами условий двухэтапной стохастической задачи являются только компоненты вектора ограничений Ъ. Рассмотрим случай конечного числа реализаций вектора Ъ. [c.172]
Поэтому эквивалентная выпуклая задача для двухэтапной стохастической задачи в простейшей постановке имеет вид [c.174]
Двухэтапная стохастическая задача в простейшей постановке сведена, таким образом, к следующей задаче выпуклого сепарабельного программирования [c.175]
Эквивалентная детерминированная задача для двухэтапной стохастической задачи в простейшей постановке в форме (3.21) — (3.25) линейна относительно переменных Xj, v,t, v-i и выпукла и сепарабельна [c.177]
Метод стохастических градиентов может быть использован также для решения нелинейной двухэтапной стохастической задачи. [c.181]
Приведем метод решения двухэтапной стохастической задачи, предполагающий возможность вычисления MQ(x, A,, b)=M z (A, b, х) (b — —Ах) по заданной величине х и известным статистическим характеристикам случайных параметров условий задачи. [c.184]
Метод основан на общих свойствах детерминированной задачи, эквивалентной двухэтапной стохастической задаче, и на идее выпуклого программирования, принадлежащей Келли. [c.184]
Обозначим решение этой задачи через Ад. Очередное приближение предварительного плана х двухэтапной стохастической задачи определяется по формуле [c.189]
Формализуем задачу двухэтапного стохастического программирования в виде [43] [c.60]
Если продолжить в дальнейшем такие корректировки на основе учета характеристик случайного спроса, то двухэтапная задача перерастет в многоэтапную стохастическую задачу управления (см. Динамическое программирование, Многошаговые процессы). [c.349]
Один из приемов, облегчающих построение решающих правил или решающих распределений многоэтапной задачи, основан на соответствий, которое может быть установлено между стохастическими задачами-с различной информационной структурой. Сведение многоэтапной задачи к одно- или двухэтапной задаче позволяет в ряде случаев по решению задачи более простой структуры восстановить решение исходной задачи. [c.14]
Задача ставится как двухэтапная стохастическая. На первом этапе, до того как станут известны заявки на специальные рейсы, самолеты каждого типа распределяются между маршрутами и определяется число полетов самолетов каждого типа по каждой линии. На втором этапе после установления реализации случайных параметров условий задачи производится переназначение самолетов с маршрута на маршрут. [c.53]
В практических приложениях стохастического программирования чаще других встречаются так называемые двухэтапные задачи, или стохастические задачи с компенсацией невязок. Этой задаче посвящено гораздо больше публикаций, чем любой другой модели стохастического программирования. [c.152]
Будем называть общей двухэтапной стохастической экстремальной задачей следующую задачу [c.164]
В перечисленных работах изучаются условия существования оптимальных планов общей двухэтапной стохастической экстремальной задачи. Установленные условия конкретизируются далее применительно к двухэтапной задаче стохастического оптимального управления. [c.164]
Вычисление величин Q4, Qa и Qa связано с существенно менее трудоемкими расчетами, чем решение задачи двухэтапного стохастического программирования. Разности Qa — Qi и Qs — Qz характеризуют погрешности, которые могут быть получены, если заменить решение стохастической задачи вычислением оптимальных планов более простых детерминированных задач. [c.192]
Между тем можно существенно упростить решение ряда классов многоэтапных стохастических задач в жесткой постановке, если допустить нарушение условий на множестве состояний природы сколь угодно малой меры. Проиллюстрируем предлагаемый подход вначале на двухэтапной задаче линейного стохастического программирования [361]. [c.202]
Приведем в соответствие многоэтапной стохастической задаче следующую двухэтапную задачу [c.254]
Подчеркнем еще раз, что рассуждения, аналогичные приведенным, позволяют привести в соответствие каждой многоэтапной задаче с априорными решающими правилами (так же как и задаче с апостериорными решающими правилами) одноэтапную стохастическую задачу, оптимальные апостериорные решающие правила которых позволяют получить оптимальные априорные решающие правила исходной задачи.. Вопрос о том, в каких случаях целесообразнее сводить многоэтапную задачу с априорными решающими правилами к одноэтапной или двухэтапной задаче, решается в каждом отдельном случае при сопоставлении трудоемкости решения эквивалентной задачи и восстановления по ее оптимальному плану оптимальных решающих правил исходной задачи вида (6.1) — (6.3). [c.256]
Сужение рассматриваемого класса многоэтапных.стохастических задач дает возможность подробнее охарактеризовать соотношения между решающими правилами n-этапной и поставленной ей в соответствие двухэтапной задачи. 256 [c.256]
Подходы к постановке и анализу стохастических задач существенно различаются в зависимости от последовательности получения информации - в один прием или по частям. При построении стохастической модели важно также знать, необходимо ли принять единственное решение, не подлежащее корректировке, или можно по мере накопления информации один или несколько раз корректировать решение. В соответствии с этим в стохастическом программировании исследуются одноэтапные, двухэтапные и многоэтапные задачи. [c.21]
Подобной содержательной постановке задачи планирования в наибольшей степени удовлетворяет информационная и алгоритмическая структура двухэтапных задач стохастического программирования. [c.60]
Первая группа параметров определяет предварительное решение об объеме продуктов, производимых по тому или иному технологическому способу. Информация об этих параметрах позволяет руководству предприятия подготовить оснастку производства, заключить договоры с соисполнителями, провести всю необходимую организационную и технологическую подготовку и начать выпуск продукции. После установления спроса (после наблюдения реализации случайных параметров условий задачи) вычисляется вторая группа параметров решения — коррекции плана. Коррекция вызывается необходимостью компенсации невязок — несоответствия между спросом и объемом продукции, определяемым предварительным планом. Компенсация невязок производится посредством заранее установленного набора технологических способов. Каждой реализации спроса соответствует свой план компенсации невязок. Естественно полагать, что компенсация невязки связана с большими затратами, чем производство того же объема продукции в соответствии с предварительным планом. Поэтому разработка предварительного плана должна учитывать всю априорную информацию о статистических характеристиках спроса, чтобы свести к минимуму суммарные затраты на производство требуемой продукции. Выбор оптимального плана в задачах подобного рода определяется тем, как будут оценены невязки в условиях задачи и каким образом оценка невязки сопоставляется с затратами на реализацию предварительного плана. Разработка предварительного плана и компенсация невязок — два этапа решения одной задачи. В соответствии с этим задачи рассматриваемого типа называют двухэтапными задачами стохастического программирования. Трудности, с которыми связан анализ двухэтапных задач, в значительной степени определяются необходимостью такого выбора предварительного плана разрешимой задачи, который гарантировал бы существование компенсации невязок при всех реализациях случая. Двухэтапные задачи, структура условий которых обладает тем свойством, что при любом плане первого этапа компенсация невязок всегда оказывается возможной, существенно проще в исследовании. Двухэтапным задачам посвящена богатая литература и для целого ряда частных постановок имеются вполне приемлемые методы построения решения. [c.13]
Решение этого вопроса приводит к двухэтапной задаче стохастического программирования. [c.34]
Ограничения второй группы, обычные для двухэтапных задач стохастического программирования, представляют собой балансовые соотношения для каждого маршрута. [c.53]
Представление планирования полетов в виде двухэтапной модели— определенная идеализация задачи. Более естественное описание ситуации можно представить многоэтапной задачей стохастического программирования, в которой последовательно учитывались бы ежедневные изменения заявок на перевозки. Однако решение многоэтапной задачи планирования полетов связано со значительными вычислительными трудностями. Предлагается следующий путь упрощения задачи. [c.55]
Разобьем горизонт планирования на п периодов и представим ситуацию в виде последовательности двухэтапных моделей стохастического программирования. Решение, полученное для последовательности двухэтапных задач, можно рассматривать как приближенное решение многоэтапной задачи планирования полетов. [c.55]
Можно полагать, что намеченная последовательность двухэтапных задач позволяет получить достаточно хорошее приближение к оптимальному планированию полетов при существенно меньших вычислительных трудностях, чем многоэтапная задача стохастического программирования. [c.55]
В [112] задача перспективного планирования рассматривается как двухэтапная модель стохастического программирования. Вектор X—(KI,. .., XN) представляет собой предварительный план — решение первого этапа. [c.60]
Допущения, принятые в предыдущем пункте и позволившие свести задачу перспективного планирования к двухэтапной задаче стохастического программирования, достаточно жестки. В практике планирования не всегда имеются основания предполагать, что после выбора предварительного решения х= (xit. . . , XN) можно одновременно получить информацию о значениях случайных параметров условий, отвечающих всем периодам, и вычислить все коррекции z/ и у , =2,...,Л/- -1. [c.61]
ДВУХЭТАПНАЯ ЗАДАЧА СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ. (ПОСТАНОВКА И КАЧЕСТВЕННЫЙ [c.152]
Теорема 4.1. Последовательность Q(Xh) сходится к оптимальному значению целевой функции детерминированной задачи, эквивалентной двухэтапной стохастической задаче линейного программирования. Последовательность лг/J содержит сходящуюся подпоследовательность. Каждая сходящаяся подпоследовательность из Xh сходится к оптимальному предварительному плану х двухэташюй стохастической задачи. [c.190]
Дж. Вессельс [58], М. Демпстер [94] и другие предложили различные обобщения двухэтапных постановок и изучали стохастические задачи оценки невязок. [c.17]
Приведем вначале, следуя [14], формальную постановку общей двухэтапяой стохастической задачи, а затем конкретизируем ее применительно к двухэтапной задаче стохастического оптимального управления. [c.164]
Используя псевдообратные матрицы, можно записать детерминированную задачу, эквивалентную задаче двухэтапного стохастического программирования, в форме, позволяющей выделить ряд случаев, для которых могут быть построены эффективные методы анализа [94, 140, 313, 320]. [c.185]
Как мы видели выше, общие методы решения двухэтапной задачи стохастического программирования достаточно трудоемки. Трудности численного анализа двухэтапной задачи возрастают, если нет явного выражения для множества К предварительных планов задачи. Один из подходов к приближенному анализу решения двухэтапной задачи заключается в оценке оптимального значения ее целевой функции. Двухэтапной задаче приводятся в соответствие детерминированные задачи, оптимальные значения показателей качества которых оценивают сверху и снизу целевую функцию стохастической задачи на оптимальном предварительном плане х. Обычно решения соответствующих детерминированных задач являются неплохими начальными приближениями для итерационных методов решения двухэтатшых задач. Далее предполагается, что В и q детерминированы. [c.190]
Первой попыткой перехода от статических моделей стохастического программирования к динамическим была, по-видимому, двухэтапная задача Данцига — Маданского. Двухэтапная задача может быть обобщена в различных направлениях. Естественно, например, перейти к многоэтапной задаче с жесткими ограничениями (с ограничениями, которые должны выполняться при всех возможных реализациях случая, подобно тому, как это предполагается в классической двухэтапной задаче). Такого рода подходы рассматривались Беллманом [10], Дж. Данцигом [88], Н. 3. Шором и др. [332, 334—336]. Здесь мы, однако, рассмотрим более широкие обобщения двухэтапной задачи — различные постановки многоэтапных стохастических задач с безусловными и условными статистическими, вероятностными и жесткими ограничениями. Частные модели подобного типа обсуждались в [70, 308—310] и других работах. Многоэтапные модели стохастического программирования имеют многочисленные приложения к задачам планирования в экономике и технике. Ряд практических проблем, возникающих при перспективном планировании, при многостадийном проектировании, при управлении боевыми операциями, при планировании экспериментов и оперативном управлении космическими объектами, при регулировании технологических процессов, подверженных случайным возмущениям, может быть рассмотрен как многоэтапные стохастические задачи со статистическими вероятностными и жесткими ограничениями. [c.192]
В предыдущих параграфах главы мы рассматривали многоэтапные стохастические задачи с условными и безусловными, статистическими и вероятностными ограничениями. Более непосредственным и естественным обобщением классической двухэтапной модели стохастического программирования являются многоэтапные задачи, в которых исключаются невязки условий при всех реализациях случая. На каждом этапе после получения информации о реализованных случайных параметрах условий задачи и о принятом на предыдущем этапе решении вводится коррекция, гарантирующая удовлетворение ограничений при всевозможных состояниях природы oeQ. По аналогии с соответствующими одноэтапными моделями такие задачи естественно называть многоэтапными задачами стохастического программирования в жесткой постановке. В этих задачах ограничены не средние значения некоторых функционалов (как в моделях предыдущих параграфов), а значения случайных функционалов при всех реализациях oeQ. [c.202]
В (308] и 169] утверждалось, что оптимальные решающие правила Xs ( oft-1) многоэтапных линейных стохастических задач с условными вероятностными ограничениями представляют собой кусочно-линейные функции от F 1 (I—afe( oft-1)) и решающих правил предшествующих этапов. В [70] указано, что сформулированное утверж--дение, тривиальное для двухэтапной задачи, вообще говоря, несправедливо при числе этапов, большем двух. Там же построен соответствующий пример. В последующей работе Э10] авторы привели некоторые условия, при которых, по их мнению, оптимальные решающие правила многоэтапных задач кусочно-линейны. Можно, однако, построить задачи, удовлетворяющие требованиям из [310], оптимальные решающие правила которых тем не менее не кусочно-линейны. [c.249]
Беркович Е. М. О существовании оптимальных решений для одного класса двухэтапных Стохастических экстремальных задач. В кн. Приближенные методы решения задач оптимального управления и некоторых некорректных обратных задач. Труды ВЦ МГУ. Изд. МГУ, М., 1972. [c.381]
Естественным обобщением двухэтапных задач являются многоэтапные задачи стохастического программирования. Часто в процессе управления представляется возможность последовательно наблюдать ряд реализаций параметров условий и соответствующим образом корректировать план. Естественяо, что >при составлении предварительного плана и при последовательной коррекции должны учитываться априор- [c.13]
Первые работы по стохастическому программированию появились в 1955 г. В них содержатся постановки линейных двухэтапных задач и подходы к вычислению распределения оптимального значения целевой функции задачи линейного программирования со случайными параметрами условий (так называемый пассивный подход к задачам стохастического программирования). Модели двухэтапных задач предложены одновременно и, по-видимому, независимо друг от друга Е. Билом i[30], и Дж. Данцигом [89]. Анализ двухэтапных постановок был затем развит А. Маданским [191—193], Р. Ветсом [60—62], П. Каллем [140, 142] и др. В настоящее время двухэтапным задачам посвящена достаточно обширная литература (см., например, [14—16, 71, 58, 94, 160, 176, 199, 253, 176, 284, 320, 49, 361]). [c.17]
Итеративный метод решения двухэтапных задач, не требующий априорных характеристик случайных параметров условий, разработан Ю. М. Ермольевым и Н. 3. Шорам [110]. Ерю.шеву принадлежит, кроме того, ряд общих подходов к анализу задач стохастического программирования [104—109]. [c.17]
Задача планирования полетов сводится, таким образом, к двухэтапной модели стохастического программирования, в которой требуется вычислить неотрицательные параметры хц, xijh, yf, у , минимизирующие целевой функционал (7.10) при условиях (7.7) — (7.9). На пере-54 [c.54]