Нижняя грань целевого функционала (7.18) на г(д) определяет для каждого ft и, следовательно, для каждого x =x(t, и, ш) и со составляющую i ) ( j, ш) показателя качества (7.18) решения двухэтапной задачи оптимального управления [c.166]
Ниже будут приведены некоторые соображения о сведении многоэтапной задачи с априорными решающими правилами к. двухэтапной задаче и о восстановлении по оптимальному плану двухэтапной задачи оптимальных решающих правил исходной задачи вида (6.1) — (6.3). Аналогичные рассуждения могут быть проведены и для случая сведения задачи к одноэтапной или любой другой, для которой имеются конструктивные приемы построения оптимальных решающих правил. 252 [c.252]
Двухэтапные задачи оптимального управления в условиях неполной информации 164 [c.394]
Первая группа параметров определяет предварительное решение об объеме продуктов, производимых по тому или иному технологическому способу. Информация об этих параметрах позволяет руководству предприятия подготовить оснастку производства, заключить договоры с соисполнителями, провести всю необходимую организационную и технологическую подготовку и начать выпуск продукции. После установления спроса (после наблюдения реализации случайных параметров условий задачи) вычисляется вторая группа параметров решения — коррекции плана. Коррекция вызывается необходимостью компенсации невязок — несоответствия между спросом и объемом продукции, определяемым предварительным планом. Компенсация невязок производится посредством заранее установленного набора технологических способов. Каждой реализации спроса соответствует свой план компенсации невязок. Естественно полагать, что компенсация невязки связана с большими затратами, чем производство того же объема продукции в соответствии с предварительным планом. Поэтому разработка предварительного плана должна учитывать всю априорную информацию о статистических характеристиках спроса, чтобы свести к минимуму суммарные затраты на производство требуемой продукции. Выбор оптимального плана в задачах подобного рода определяется тем, как будут оценены невязки в условиях задачи и каким образом оценка невязки сопоставляется с затратами на реализацию предварительного плана. Разработка предварительного плана и компенсация невязок — два этапа решения одной задачи. В соответствии с этим задачи рассматриваемого типа называют двухэтапными задачами стохастического программирования. Трудности, с которыми связан анализ двухэтапных задач, в значительной степени определяются необходимостью такого выбора предварительного плана разрешимой задачи, который гарантировал бы существование компенсации невязок при всех реализациях случая. Двухэтапные задачи, структура условий которых обладает тем свойством, что при любом плане первого этапа компенсация невязок всегда оказывается возможной, существенно проще в исследовании. Двухэтапным задачам посвящена богатая литература и для целого ряда частных постановок имеются вполне приемлемые методы построения решения. [c.13]
Можно полагать, что намеченная последовательность двухэтапных задач позволяет получить достаточно хорошее приближение к оптимальному планированию полетов при существенно меньших вычислительных трудностях, чем многоэтапная задача стохастического программирования. [c.55]
Легко доказать, что при условиях (9.12) — (9.13) оптимальный план задачи (9.9) — (9.11) единствен и удовлетворяет равенству (9.7). Это значит, что нелинейные соотношения (9.7) могут быть отброшены и двухэтапная задача перспективного планирования может быть записана в виде [c.60]
Во введении ( 1) рассмотрены постановка и содержательная интерпретация задачи. В 2 изучается область определения планов первого этапа. Параграф 3 посвящен условиям разрешимости задачи второго этапа. В 4 построена и исследуется детерминированная задача, решением которой является план первого этапа двухэтапной задачи. В 5 формулируются некоторые условия оптимальности плана первого этапа. В 6 и 7 излагаются обобщения двухэтапной задачи. В 6 построен и охарактеризован нелинейный аналог, а в 7 — бесконечно мерный аналог двухэтапной задачи стохастического программирования. [c.152]
Сформулируем необходимые условия оптимальности предварительного плана х двухэтапной задачи. (В дальнейшем мы будем называть х планом двухэтапной задачи.) [c.161]
Теорема 5.1. (Необходимое условие оптимальности плана двухэтапной задачи.) Если х — решение двухэтапной задачи, то для любого х К [c.161]
Доказательство. Поскольку х — оптимальный план, ах — план двухэтапной задачи, то Q(x ) . Q(x), или, что то же самое, [c.161]
Отсюда экономический смысл условия (5.1). Если вектор х определяет оптимальный предварительный план двухэтапной задачи, то суммарная средняя прибыль при интенсивностях х использования технологических способов производства, подсчитанная в оптимальных (отвечающих х ) оценках, не меньше суммарной средней прибыли, подсчитанной в оптимальных оценках для любого другого допустимого плана х. [c.162]
Теорема 5.2. (Необходимое и достаточное условие оптимальности плана двухэтапной задачи.) Пусть х — внутренняя точка множества К, а целевая функция Q(x) детерминированной задачи, эквивалентной двухэтапной задаче, дифференцируема в окрестности х. Тогда задача (3.8), (3.9), двойственная к задаче второго этапа, имеет решение z (А, Ь, х ), такое, что [c.162]
В [14 — 47] общая схема двухэтапной стохастической задачи расширена таким образом, что в нее могут быть уложены двухэтапные задачи стохастического оптимального управления. Приведенные в этих работах постановки задач обобщают ряд моделей управления поведением динамических систем в условиях неполной информации. [c.164]
Для оптимального выбора коррекции при каждой реализации случайных параметров условий требуется решить новую задачу оптимального управления — задачу второго этапа. Математическое ожидание нижней грани целевого функционала задачи второго этапа, как и в классической двухэтапной задаче стохастического программирования, определяет штраф за коррекцию и входит составной частью в целевой функционал бесконечно-мерной двухэтапной задачи. [c.164]
В перечисленных работах изучаются условия существования оптимальных планов общей двухэтапной стохастической экстремальной задачи. Установленные условия конкретизируются далее применительно к двухэтапной задаче стохастического оптимального управления. [c.164]
В приведенной модели предполагается, что функции g, go, компоненты вектор-функции , начальное состояние системы х0 и составляющие вектора d фиксированы и известны принимающему решение. В прикладных задачах такое допущение далеко не всегда приемлемо. Не все характеристики и параметры условий задачи заранее известны. Некоторые из них могут быть случайными. Между тем может возникнуть необходимость выбрать управление до получения полной информации об условиях задачи и до наблюдения реализаций случайных характеристик и параметров динамической системы. Выбранное управление и реализованные значения не определенных до этого параметров условий могут нарушить некоторые из ограничений задачи. Естественно, как и в классической двухэтапной задаче стохастического программирования, ввести корректирующее управление, компенсирующее возникающие невязки. Мы приходим, таким образом, к двухэтапной задаче стохастического оптимального управления. [c.165]
Для общей двухэтапной задачи стохастического оптимального управления получены лишь качественные результаты, относящиеся к условиям существования и устойчивости решения (16]. Вычислительная схема построена для частного случая двухэтапной задачи, связанной ""с линейными моделями оптимального управления, в которых [c.167]
В [90] доказаны следующие необходимые и достаточные условия оптимальности плана двухэтапной задачи с конечным числом реализаций случайного вектора ограничений. [c.172]
Теорема 2.1. Для оптимальности плана х двухэтапной задачи необходимо и достаточно, чтобы при х=х существовало решение z (b, x ) задачи (3.8) —(3.9) гл. 6, двойственной к задаче второго этапа, удовлетворяющее соотношениям [c.172]
Структура задачи (2.6) — (2.8) позволяет, используя методы блочного программирования, определить оптимальный план двухэтапной задачи. [c.173]
Ясно, что /и-мерный вектор Л 1 оценок условий (2.9) относительно оптимального базиса г-задачи совпадает с оптимальным планом х двухэтапной задачи стохастического программирования. , ...., [c.173]
Предоставим читателю доказать, что критерий оптимальности решения задачи (2.6) — -(2.8) методом разложения совпадает с достаточным условием оптимальности плана двухэтапной задачи, сформулированным в теореме 2.1. [c.173]
Многогранное множество (3.13) — (3.14) не зависит от случайных параметров Ли Ь условий двухэтапной задачи. Пусть и 1, . .., <-v> — векторы, отвечающие вершинам этого множества. По крайней мере одна из этих вершин определяет оптимальный план задачи. Таким образом, максимальное значение линейной формы (3.12) при условиях (3.13) — (3.14), а стало быть, и минимальное значение формы (3.10) при условии (3.11) равно [c.186]
Приведем две модификации модели (6.4) — (6.6), представляющие два различных варианта двухэтапных задач, по оптимальным решающим правилам которых могут быть восстановлены оптимальные решающие правила исходной многоэтапной задачи [360]. [c.253]
Доказательство. Допустимость решающих правил (6.10) по отношению к исходной многоэтапной задаче очевидна. Множество допустимых решений задачи (6.1) — (6.3) является подмножеством множества допустимых решений двухэтапной задачи. Учитывая, кроме того, последнее неравенство системы (6.9), приходим к выводу, что формулы (6.10) определяют не только допустимые, но и оптимальные решающие правила многоэтапной задачи (6.1) — (6.3). [c.254]
Задача (6.11) — (6.13) отличается от двухэтапной задачи (6.4) — (6.6) только последними условиями — равенствами системы (6.13) ограничений второго этапа. Эти условия-равенства отсекают информационно-недопустимые для многоэтапной задачи (6.1) — (6.3) решения и обеспечивают совпадение множества допустимых (а следовательно, и множества оптимальных) решений задач (6.1) — (6.3) и (6.11) — (6.13). [c.255]
Рассмотренные в предыдущем пункте две схемы сведения многоэтапной задачи стохастического программирования с априорными решающими правилами к эквивалентной в некотором смысле двухэтапной могут быть модифицированы и обобщены. Каждая из рассмотренных схем является типичным представителем класса схем, приводящих в соответствие многоэтапным задачам двухэтапные и позволяющих по-решениям двухэтапной задачи получить оптимальные решающие правила исходной задачи. [c.255]
Отметим, что многоэтапные задачи стохастического программирования не являются тривиальными обобщениями двухэтапных задач. Многие результаты, справедливые для двухэтапных задач общего вида, неверны для многоэтапных. Например, оптимальные решающие правила линейных двухэтапных задач с вероятностными ограничениями — кусочно-линейные функции от некоторых случайных параметров условий задачи. Для многоэтапных задач это утверждение, вообще говоря, неверно [70]. [c.256]
Подчеркнем еще раз, что рассуждения, аналогичные приведенным, позволяют привести в соответствие каждой многоэтапной задаче с априорными решающими правилами (так же как и задаче с апостериорными решающими правилами) одноэтапную стохастическую задачу, оптимальные апостериорные решающие правила которых позволяют получить оптимальные априорные решающие правила исходной задачи.. Вопрос о том, в каких случаях целесообразнее сводить многоэтапную задачу с априорными решающими правилами к одноэтапной или двухэтапной задаче, решается в каждом отдельном случае при сопоставлении трудоемкости решения эквивалентной задачи и восстановления по ее оптимальному плану оптимальных решающих правил исходной задачи вида (6.1) — (6.3). [c.256]
Пусть известно оптимальное значение целевого функционала -этап-. ной задачи. Обозначим его через я з о. Используя эту информацию, можно записать необходимое и достаточное условие е-оптимальности решающих правил многоэтапной задачи, вычисленных по решающим правилам двухэтапной задачи с помощью преобразования вида (6.23). [c.258]
Обозначим оптимальное значение целевого функционала двухэтапной задачи через г 50. Очевидно, что для произвольных -, удовлетворяющих условиям (6.25), справедливо неравенство [c.258]
Множество Qi оптимально в следующем смысле Qi Ki(x) и для любого x Qi вероятность того, что будет возможность выбрать корректирующий план z/j O, максимальна. Этот случай обычно опускается при изучении двухэтапной задачи. [c.268]
Б ер ко аи ч Е. М. О двухэтапной задаче стохастического оптимального управления.— Вестник МГУ. Сер. мат. мех. , 1970, выл. 4, с. 9—17. [c.381]
Непосредственно определение ремонтного плана ведется в энергообъединении и частично в энергосистемах. В объединении определяются ремонтная площадка и варианты ее заполнения с учетом заданных ограничений. В оценке топливной составляющей целевой функции, соответствующей каждому варианту плана, расход топлива подсчитывается при двухэтапном решении задачи оптимального распределения типовых графиков нагрузок объединения между энер- [c.183]
Применение двухэтапного алгоритма оптимального управления для прогноза динамики конфликта локальных систем воздушного нападения и противовоздушной обороны. Рассмотрим задачу противодей-б [c.83]
Первые работы по стохастическому программированию появились в 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]
Приведем вначале, следуя [14], формальную постановку общей двухэтапяой стохастической задачи, а затем конкретизируем ее применительно к двухэтапной задаче стохастического оптимального управления. [c.164]
Пусть каждое Принятое решение ыесУ удовлетворяет условиям (7.10) при всех возможных реализациях яь(со)е.Хо и rf(w)eZ), а условия (7.Г1) могут нарушаться. Невязки, возникающие в условиях (7.11), компенсируются коррекцией. Минимально возможный штраф за коррекцию (оптимальное значение показателя качества решения задачи второго этапа) г з 1[л (/ь и, со), (и] включается в целевой функционал (7.12) двухэтапной задачи. [c.166]
Двухэтапная задача стохастического оптимального управления состоит, таким образом, в минимизации Q(u)=MQ(u, со) на множестве uef7. [c.167]
Как мы видели выше, общие методы решения двухэтапной задачи стохастического программирования достаточно трудоемки. Трудности численного анализа двухэтапной задачи возрастают, если нет явного выражения для множества К предварительных планов задачи. Один из подходов к приближенному анализу решения двухэтапной задачи заключается в оценке оптимального значения ее целевой функции. Двухэтапной задаче приводятся в соответствие детерминированные задачи, оптимальные значения показателей качества которых оценивают сверху и снизу целевую функцию стохастической задачи на оптимальном предварительном плане х. Обычно решения соответствующих детерминированных задач являются неплохими начальными приближениями для итерационных методов решения двухэтатшых задач. Далее предполагается, что В и q детерминированы. [c.190]
В (308] и 169] утверждалось, что оптимальные решающие правила Xs ( oft-1) многоэтапных линейных стохастических задач с условными вероятностными ограничениями представляют собой кусочно-линейные функции от F 1 (I—afe( oft-1)) и решающих правил предшествующих этапов. В [70] указано, что сформулированное утверж--дение, тривиальное для двухэтапной задачи, вообще говоря, несправедливо при числе этапов, большем двух. Там же построен соответствующий пример. В последующей работе Э10] авторы привели некоторые условия, при которых, по их мнению, оптимальные решающие правила многоэтапных задач кусочно-линейны. Можно, однако, построить задачи, удовлетворяющие требованиям из [310], оптимальные решающие правила которых тем не менее не кусочно-линейны. [c.249]
Теорема 6.2. Пусть A i = onst, л , =л г (сои), i = 2,...,n, — оптимальные решающие правила двухэтапной задачи (6.14) — (6.16). Тогда [c.255]
Доказательство. Допустимость решающих правил (6.17) для задачи (6.1) — (6.3) следует из вида ограничений (6.15) — (6.16) для pje Dj. Множество допустимых решений задачи (6.1) — (6.3) является подмножеством допустимых решений двухэтапной задачи (6.14) — (6.16). Последнее из условий системы (6.16) позволяет тогда заключить, что решающие правила (6.17) являются оптимальными для многоэтапной задачи (6.1) — (6.3). [c.255]
Приведем еще один класс двухэтапных задач в соответствие многоэтапной задаче (6.1) — (6.3). Легко видеть, что оптимальные решающие правила i. = onst, л = я/ (м") следующей двухэтапной задачи сов- [c.255]
Беркович Е. М. О существовании оптимальных решений для одного класса двухэтапных Стохастических экстремальных задач. В кн. Приближенные методы решения задач оптимального управления и некоторых некорректных обратных задач. Труды ВЦ МГУ. Изд. МГУ, М., 1972. [c.381]
До сих пор нами расматривались двухэтапные экономико-математические модели задачи выбора проектных вариантов новых изделий. При этом считались известными предприятия, на которых должны создаваться новые изделия. Однако нередко при проектировании новой техники вне завода полностью либо частично не всегда бывает известно, на каких предприятиях отрасли и в каких объемах будут производиться эти изделия. Следовательно, решая задачу выбора оптимальных проектных вариантов новых изделий, необходимо одновременно решать и задачу о выборе пунктов производства новых изделий и определении объемов их производства в этих пунктах, имея в виду известными общую потребность в проектируемых изделиях и сеть потребителей. Будем рассматривать только случай действующих заводов, на которых должно осуществляться производство проектируемых изделий. [c.157]