Таким образом, приближенный детерминированный аналог многоэтапной стохастической задачи (3.92) -(3.96) при сделанных допущениях оказывается задачей выпуклого программирования, решение которой может быть осуществлено известными методами [46, 56]. [c.84]
Таким образом, для многоэтапной стохастической задачи (3.92) — (3.96) оптимального календарного планирования основного производства НПП удается построить выпуклые детерминированные аналоги, которые в зависимости от принятых допущений позволяют получать точные или приближенные плановые решения. [c.85]
Разбивка годовой производственной программы на календарные отрезки времени осуществляется на основе вероятностной модели многоэтапной стохастической задачи оптимизации календарною планирования основного производства НПП. [c.177]
Обоснованы вероятностные постановки задач текущего и календарного планирования производственной программы НПП в условиях неполноты технико-экономической информации, обеспечивающие надежность плановых решений. Многоэтапная стохастическая задача оптимизации отражает адаптивный характер процедур принятия плановых решений и повышает реализуемость производственной программы предприятия. [c.215]
Если продолжить в дальнейшем такие корректировки на основе учета характеристик случайного спроса, то двухэтапная задача перерастет в многоэтапную стохастическую задачу управления (см. Динамическое программирование, Многошаговые процессы). [c.349]
Многоэтапная стохастическая задача управления 351 [c.474]
Таким образом, запись (1.4) — (1.6) включает в себя и задачи с вероятностными ограничениями. Некоторые усложнения позволяют в аналогичной форме записывать и многоэтапные стохастические задачи с условными и безусловными ограничениями. 10 [c.10]
Построение платежной функции игры в том или ином виде отражает информацию, которой располагает принимающий решение. Игровой подход к многоэтапным стохастическим задачам приводит к динамической игре, в которой шаг за шагом накапливается информация об условиях взаимосвязанных задач, подлежащих решению. Выбор решения на каждом ходе должен оптимизировать платежную функцию многоходовой игры, гарантируя, естественно, возможность завершения игры— удовлетворения условиям игры при допустимых случайных ситуациях, которые могут возникнуть в процессе игры. [c.15]
Модели стохастического управления, в которых закон управления или механизм управления учитывает последовательный характер накопления информации и может уточняться в процессе управления, описываются многоэтапными стохастическими задачами. Целевой функционал динамической задачи зависит от состояния системы на конечном (.S-M) этапе или от всей траектории системы. Область определения задачи отдельного этапа описывается жесткими или условными статистическими или условными вероятностными ограничениями. Оптимальные решающие правила или решающие распределения этих задач определяют законы управления или механизмы стохастического управления. [c.46]
Настоящая глава посвящена не технологии математического обеспечения (в указанном смысле), а математическим вопросам, связанным с постановкой задач и построением решающих правил. В 1 вводятся некоторые вспомогательные понятия, необходимые для формальной постановки и обсуждения многоэтапных задач стохастического программирования. Параграф 2 посвящен многоэтапным стохастическим задачам с условными ограничениями. В 3 обсуждается задача -отдельного этапа многоэтапной задачи -с условными статистическими ограничениями. В 4 рассматриваются многоэтапные задачи стохастического программирования с безусловными ограничениями. В 5 изучаются многоэтапные стохастические задачи в жесткой постановке. В заключительном параграфе главы (см. 6) сравниваются различные информационные структуры и изучается роль информации при анализе многоэтапных стохастических задач. [c.193]
Многоэтапные стохастические задачи с условными ограничениями [c.194]
Рассмотрим следующую многоэтапную стохастическую задачу М < >0 (си , л ") —> sup, (2. > [c.194]
Подчеркнем особенности решения многоэтапных стохастических задач с условными статистическими ограничениями. Проведем рассуждения в терминах априорных решающих правил. Обсуждение особенностей решения задач с апостериорными решающими правилами проводится по такой же схеме. [c.195]
Определение оптимального решающего правила на г -м этапе многоэтапной стохастической задачи сводится, таким образом, к решению задачи математического программирования [c.197]
Теория многоэтапного стохастического программирования еще слабо развита. Конструктивных методов решения задач достаточно общего вида в настоящее время нет. Имеются лишь методы решения частных классов многоэтапных стохастических задач с условными или безусловными вероятностными ограничениями. Чтобы расширить круг приложений разрабатываемых конструктивных вычислительных методов, естественно попытаться установить связь между задачами с условными и безусловными статистическими ограничениями, отвечающими одним и тем же функциям фо(ы", хп) и г з/((сой, xh), k = ],. .., п. [c.198]
Теорема 4.1. Пусть А — множество допустимых решающих правил (апостериорных пли априорных) многоэтапной стохастической задачи с безусловными статистическими ограничениями [c.198]
Рассмотрим частный класс многоэтапных стохастических задач с безусловными вероятностными ограничениями. Пусть г )о(а>", хп) = [c.199]
В литературе исследуются и (при некоторых предположениях относительно распределения случайных параметров условий задачи) решаются задачи с безусловными вероятностными ограничениями, в которых решающие правила заранее предполагаются линейными. Решение многоэтапных стохастических задач с безусловными ограничениями при достаточно общих предположениях относительно допустимых решающих правил требует преодоления серьезных теоретических и вычислительных трудностей. В ряде случаев исследование упрощается при сведении задачи с безусловными статистическими ограничениями к эквивалентной стохастической задаче с условными статистическими ограничениями. [c.201]
Четкая формализация моделей подобного рода дана Беллманом в терминах динамического программирования [10—12]. Качественные и вычислительные аспекты многоэтапных стохастических задач в жесткой постановке изучены в работах Н. 3. Шора и др. [332, 334, 336]. [c.202]
Численные методы анализа многоэтапных стохастических задач в жесткой постановке весьма громоздки, и с увеличением размерности управлений и числа этапов трудоемкость решения задач быстро растет. Методы динамического программирования перестают быть эффективными уже при размерности состояний системы, равной трем. Методы, основанные на схемах блочного программирования, применимы лишь при конечном (относительно небольшом) числе реализаций наборов параметров условий задачи. Метод стохастического градиента неконструктивен при числе этапов, большем двух. Теоретически корректный метод случайного поиска, предложенный в [ПО], связан с большими вычислительными трудностями. [c.202]
Между тем можно существенно упростить решение ряда классов многоэтапных стохастических задач в жесткой постановке, если допустить нарушение условий на множестве состояний природы сколь угодно малой меры. Проиллюстрируем предлагаемый подход вначале на двухэтапной задаче линейного стохастического программирования [361]. [c.202]
В настоящем параграфе на примере специальной многоэтапной стохастической задачи достаточно общего вида будет проиллюстрирована роль информации о ходе процесса выбора решений и памяти- о принятых решениях. [c.204]
В главе приводится качественное исследование многоэтапных задач -стохастического программирования с апостериорными решающими правилами ( 1). В 2 формируется общий рекуррентный алгоритм построения апостериорных решающих правил. В 3 алгоритм конкретизируется применительно к многоэтапной стохастической задаче с условными вероятностными ограничениями, а в 5 — применительно к многоэтапной квадратичной задаче с условными статистическими. ограничениями. Параграф 4 посвящен Л-задаче, двойственной к многоэтапной задаче стохастического программирования. [c.207]
Подчеркнем, что в соответствии с утверждением, доказанным в 5 гл. 5, в многоэтапных стохастических задачах с выпуклым функционалом фо(соп, хп) и вогнутыми составляющими вектор-функций (оД fe) и произвольной мерой рп, гак же как и в задачах с непрерывной мерой рп и произвольными функционалами о >о и tyh, оптимальные значения целевых функционалов на чистых и смешанных апостериорных стратегиях совпадают. Это значит, что для решения таких задач можно ограничиться построением оптимальных апостериорных решающих правил. Необходимость в построении оптимальных апостериорных решающих распределений в этом случае отпадает. [c.212]
Специальный интерес представляет вырожденный случай многоэтапной стохастической задачи с вероятностными ограничениями, ког- [c.238]
Если, кроме того, составляющие векторов i детерминированы, то многоэтапная стохастическая задача с вероятностными ограничениями сведется к задаче линейного программирования с блочно-треугольной матрицей условий [c.239]
Как мы видели, вычисление априорных решающих правил линейной многоэтапной стохастической задачи с условными вероятностными ограничениями сводится к решению задачи вида (1.6) — (1.8). Условная функция распределения компонент вектора bi при фиксированном наборе со1 -1 предполагается известной. Однако вычисление [c.239]
При построении многоэтапных стохастических задач можно расширить понятие Р-модели и рассматривать множество Р-целей, когда требуется оптимизировать совместную вероятность [c.241]
Во всех рассмотренных в настоящем параграфе моделях не было необходимости в индуцированных ограничениях, обеспечивающих разрешимость задач последующих этапов. Отсюда. простота анализа моделей. В тех случаях, когда структура условий многоэтапной стохастической задачи не исключает необходимости в индуцированных ограничениях, вычисление априорных решающих правил существенно усложняется. [c.247]
В гл. 10 намечен общий подход к построению апостериорных решающих правил задачи (6.1) — (6.3). Конструирование априорных решающих правил связано с существенно большими теоретическими и вычислительными трудностями. В 4—5 указаны пути построения априорных решающих правил для частных классов многоэтапных стохастических задач. [c.252]
Приведем в соответствие многоэтапной стохастической задаче следующую двухэтапную задачу [c.254]
Сужение рассматриваемого класса многоэтапных.стохастических задач дает возможность подробнее охарактеризовать соотношения между решающими правилами n-этапной и поставленной ей в соответствие двухэтапной задачи. 256 [c.256]
Рассмотрим следующую многоэтапную стохастическую задачу с априорными решающими правилами [c.259]
Рассмотрим вначале многоэтапную стохастическую задачу вида [c.271]
Легко видеть, что если многоэтапная стохастическая задача (4.13) имеет решение, то и задача лексикографической оптимизации (4.14) имеет решение, оптимальное в смысле задачи (4.13). Однако из того,, что задача (4.14) разрешима, не следует, вообще говоря, разрешимость задачи (4.13). Существование решения задачи (4.13) вытекает из разрешимости задачи (4.14) только в том случае, когда на лексикографическом максимуме все компоненты <р(хп), за исключением последней,, равны единице. В противном случае решение задачи (4.14) определяет подходящие функции, которые могут быть приняты в качестве решающих правил неразрешимой многоэтапной стохастической задачи. [c.272]
Другая, существенно более простая для анализа, лексикографическая интерпретация многоэтапной стохастической задачи может быть получена, если требовать выполнения условий k-ro этапа не для всех,, а почти для всех реализаций со -1. [c.272]
Щ е п а к и и М. Б. Многоэтапная стохастическая задача о смеси. — В кн. Мат. методы исслед. и оптимизации систем. Вып. 4, Киев, 1970, с. 3—15. [c.393]
Первой попыткой перехода от статических моделей стохастического программирования к динамическим была, по-видимому, двухэтапная задача Данцига — Маданского. Двухэтапная задача может быть обобщена в различных направлениях. Естественно, например, перейти к многоэтапной задаче с жесткими ограничениями (с ограничениями, которые должны выполняться при всех возможных реализациях случая, подобно тому, как это предполагается в классической двухэтапной задаче). Такого рода подходы рассматривались Беллманом [10], Дж. Данцигом [88], Н. 3. Шором и др. [332, 334—336]. Здесь мы, однако, рассмотрим более широкие обобщения двухэтапной задачи — различные постановки многоэтапных стохастических задач с безусловными и условными статистическими, вероятностными и жесткими ограничениями. Частные модели подобного типа обсуждались в [70, 308—310] и других работах. Многоэтапные модели стохастического программирования имеют многочисленные приложения к задачам планирования в экономике и технике. Ряд практических проблем, возникающих при перспективном планировании, при многостадийном проектировании, при управлении боевыми операциями, при планировании экспериментов и оперативном управлении космическими объектами, при регулировании технологических процессов, подверженных случайным возмущениям, может быть рассмотрен как многоэтапные стохастические задачи со статистическими вероятностными и жесткими ограничениями. [c.192]
В предыдущих параграфах главы мы рассматривали многоэтапные стохастические задачи с условными и безусловными, статистическими и вероятностными ограничениями. Более непосредственным и естественным обобщением классической двухэтапной модели стохастического программирования являются многоэтапные задачи, в которых исключаются невязки условий при всех реализациях случая. На каждом этапе после получения информации о реализованных случайных параметрах условий задачи и о принятом на предыдущем этапе решении вводится коррекция, гарантирующая удовлетворение ограничений при всевозможных состояниях природы oeQ. По аналогии с соответствующими одноэтапными моделями такие задачи естественно называть многоэтапными задачами стохастического программирования в жесткой постановке. В этих задачах ограничены не средние значения некоторых функционалов (как в моделях предыдущих параграфов), а значения случайных функционалов при всех реализациях oeQ. [c.202]
Теорема 4.4. Пусть функция TjJo(w , д "), определяющая целевой функционал многоэтапной стохастической задачи, выпукла по хп Хп, у шп, а компоненты вектор-функции 1 ) (оД xk), k=l,...,n, определяющей ограничения многоэтапной задачи, вогнуты по xk Xh, уоЛ Тогда [c.216]
Построим Л-задачу (4.15) для многоэтапной стохастической задачи (5.1) — (5.2). Используя формулы (4.9), (4.11), запишем выражение для Фд1 (со71, хп 1, Хп) [c.231]
В соответствии с формулами (5.4), (5.6), (5.8), (5J10) оптимальные апостериорные решающие правила многоэтапной стохастической задачи (5.1) — (5.2) определяются соотношениями [c.233]
Настоящая глава посвящена многоэтапным стохастическим задачам с условными ограничениями и априорными решающими правилами. Качественный анализ таких задач связан с существенно большими трудностями, чем исследование стохастических задач с апостериорными решающими правилами. В общем случае для задач с априорными решающими правилами несправедливы теоремы двойственности, подобные тем, которые доказаны в предыдущей главе для задач с апостериорными решениями. Во многих случаях детерминированные эквиваленты задач с априорными решающими правилами оказываются многоэкстремальными моделями. Трудности, с которыми сопряжено исследование таких моделей, вынуждают сузить диапазон рассматриваемых задач по сравнению с кругом задач, обсуждаемых в предыдущей главе. Мы ограничимся здесь1 главным образом линейными задачами с условными вероятностными ограничениями. [c.233]
Пусть теперь все элементы матриц Аи, if=l,.,.,n, линейной многоэтапной стохастической задачи (1.3) — (1.5) неположительны (или, что [c.236]
Рассмотрим теперь многоэтапные стохастические задачи вида (1.3) — (1.5), в которых случайные параметры разных этапов — независимые между собой случайные величины. В этом случае определение юптимальных решающих правил существенно упрощается. [c.237]
Рассмотрим произвольный набор фгеФг и приведем в соответствие многоэтапной стохастической задаче (6.1) — (6.3) следующую двухзтап-ную задачу [c.255]
При других определениях нормы at( ufe-1)] соответствующим образом меняется лексикографическая интерпретация многоэтапной стохастической задачи. [c.272]