Рассмотрим многоэтапную задачу стохастического программирования с условными статистическими ограничениями и с априорными решающими правилами [43], отражающую динамический характер задач календарного планирования непрерывного производства [c.58]
Значительно большее разнообразие имеет место в информационной структуре динамических (многоэтапных) задач стохастического программирования. Будем рассматривать информационные структуры, порождаемые следующими двумя цепочками — процедурами последовательного анализа задачи [107] решение — наблюдение — решение. ... .. —решение си наблюдение — решение — наблюдение —. .. — решение . Решающие правила и решающие распределения, отвечающие пер- [c.5]
В многоэтапных задачах упомянутого типа предполагается, что на каждом последующем этапе требуется полностью компенсировать невязки, связанные с принятыми решениями и реализованными значениями параметров условий. Перспективным обобщением многоэтапных задач с жесткими условиями являются многоэтапные задачи стохастического программирования с безусловными и условными вероятностными или статистическими ограничениями. <В задачах этого класса требуется,, чтобы на каждом этапе вероятность удовлетворения ограничений превышала некоторую заранее заданную величину или чтобы математические ожидания некоторых функций от невязок условий были бы ограничены заданными числами или функциями от наблюденных на предыдущих этапах значений случайных параметров. Кроме того, на каждом этапе могут быть заданы и жесткие ограничения. [c.14]
Представление планирования полетов в виде двухэтапной модели— определенная идеализация задачи. Более естественное описание ситуации можно представить многоэтапной задачей стохастического программирования, в которой последовательно учитывались бы ежедневные изменения заявок на перевозки. Однако решение многоэтапной задачи планирования полетов связано со значительными вычислительными трудностями. Предлагается следующий путь упрощения задачи. [c.55]
Можно полагать, что намеченная последовательность двухэтапных задач позволяет получить достаточно хорошее приближение к оптимальному планированию полетов при существенно меньших вычислительных трудностях, чем многоэтапная задача стохастического программирования. [c.55]
В, [338] исследуется процесс получения полуфабрикатов и компаундирования из них товарных продуктов на нефтеперерабатывающем заводе. На переработку поступает обычно нефть различного качества из разных месторождений или смесь нефтей в неизвестных пропорциях. Поэтому количества полуфабрикатов заданного качества, вырабатываемые из единицы сырья, не могут быть заранее предсказаны. Спрос на различные товарные продукты также является случайной величиной, меняющейся, вообще говоря, со временем. В [338] построена стохастическая модель оптимизации процесса переработки нефтепродуктов. Модель представляет собой многоэтапную задачу стохастического программирования с жесткими ограничениями. В [338] приводится также алгоритм решения задачи, использующий случайный поиск, сходимость которого доказана в [110]. [c.57]
По-видимому, наиболее естественная постановка задачи перспективного планирования представляет собой многоэтапную задачу стохастического программирования с жесткими или условными вероятностными ограничениями и с априорными решающими правилами. [c.61]
Настоящая глава посвящена не технологии математического обеспечения (в указанном смысле), а математическим вопросам, связанным с постановкой задач и построением решающих правил. В 1 вводятся некоторые вспомогательные понятия, необходимые для формальной постановки и обсуждения многоэтапных задач стохастического программирования. Параграф 2 посвящен многоэтапным стохастическим задачам с условными ограничениями. В 3 обсуждается задача -отдельного этапа многоэтапной задачи -с условными статистическими ограничениями. В 4 рассматриваются многоэтапные задачи стохастического программирования с безусловными ограничениями. В 5 изучаются многоэтапные стохастические задачи в жесткой постановке. В заключительном параграфе главы (см. 6) сравниваются различные информационные структуры и изучается роль информации при анализе многоэтапных стохастических задач. [c.193]
Введем некоторые понятия, необходимые для формальной постановки многоэтапной задачи стохастического программирования. [c.193]
Введенные понятия и обозначения позволяют сформулировать общую схему многоэтапной задачи стохастического программирования с условными статистическими ограничениями. [c.193]
Выделим две принципиально различные интерпретации задачи (2.1) — (2.3) и в соответствии с этим разделим задачи вида (2.1) —(2.3) на два подкласса. В задачах первого подкласса решение Xi на г-м этапе принимается после наблюдения реализации состояния природы (случайных параметров условий задачи) на г -м этапе. Решающие правила задач первого подкласса имеют вид Xi — Xii ), t = l,. .., п. Будем называть задачи первого подкласса многоэтапными задачами стохастического программирования с условными статистическими ограничениями и с апостериорными решающими правилами. [c.194]
В задачах второго подкласса решение на t-м этапе принимается после реализации случайных параметров условий на предыдущем (г—1)-м этапе. Решающие правила задач второго подкласса имеют вид Xi = Xi((ui 1), i=l,. .., п. Будем называть задачи второго подкласса многоэтапными задачами стохастического программирования с условными статистическими ограничениями и с априорными решающими-правилами. [c.194]
Многоэтапная задача стохастического программирования с безусловными статистическими ограничениями записывается в виде [c.197]
Многоэтапные задачи стохастического программирования в жесткой постановке [c.202]
Многоэтапные задачи стохастического программирования [c.204]
В предыдущих параграфах мы рассматривали две в известном смысле крайние информационные структуры, соответствующие априорным и апостериорным решающим правилам. Многоэтапное стохастическое программирование и развивалось главным образом применительно к этим двум схемам информированности принимающего решение. К таким информационным структурам можно естественным образом, исходя из содержательных соображений, или формальным искусственным путем сводить много различных схем задания информации, которой располагает управляющий системой на том или ином этапе выбора решения. Тем не менее при анализе практических многоэтапных задач стохастического программирования часто возникают специфические проблемы, связанные с изучением роли информации и памяти на отдельных этапах выбора решений. [c.204]
Рассмотрим следующую многоэтапную задачу стохастического программирования. [c.204]
МНОГОЭТАПНЫЕ ЗАДАЧИ СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ С АПОСТЕРИОРНЫМИ РЕШАЮЩИМИ [c.207]
В главе приводится качественное исследование многоэтапных задач -стохастического программирования с апостериорными решающими правилами ( 1). В 2 формируется общий рекуррентный алгоритм построения апостериорных решающих правил. В 3 алгоритм конкретизируется применительно к многоэтапной стохастической задаче с условными вероятностными ограничениями, а в 5 — применительно к многоэтапной квадратичной задаче с условными статистическими. ограничениями. Параграф 4 посвящен Л-задаче, двойственной к многоэтапной задаче стохастического программирования. [c.207]
Рассмотрим многоэтапную задачу стохастического программирования с условными статистическими ограничениями [c.207]
Приведем общую схему построения апостериорных решающих правил для многоэтапной задачи стохастического программирования с условными вероятностными ограничениями. Эта задача представляет собой частный случай модели (1.1) — (1.2), в которой на каждом этапе ФА(ШЙ, х11) представляет собой характеристическую функцию случайного множества Gk(u>h, ft 1), зависящего от решений, выбранных на предшествующих этапах, [c.212]
При достаточно общих предположениях относительно структуры. модели можно указать конструктивные пути построения и анализа Л-задачи для вычисления апостериорных решающих правил многоэтапных задач стохастического программирования [362, 364]. [c.214]
Рассмотрим разрешимую многоэтапную задачу стохастического программирования вида [c.216]
Сформулируем условия, гарантирующие кусочную линейность оптимальных решающих правил линейных многоэтапных задач стохастического программирования с условными вероятностными ограничениями. [c.249]
При допущениях, аналогичных допущениям п. 4.1, можно построить оптимальные априорные решающие правила для частного класса нелинейных многоэтапных задач стохастического программирования с условными вероятностными ограничениями. [c.250]
Рассмотренные в предыдущем пункте две схемы сведения многоэтапной задачи стохастического программирования с априорными решающими правилами к эквивалентной в некотором смысле двухэтапной могут быть модифицированы и обобщены. Каждая из рассмотренных схем является типичным представителем класса схем, приводящих в соответствие многоэтапным задачам двухэтапные и позволяющих по-решениям двухэтапной задачи получить оптимальные решающие правила исходной задачи. [c.255]
Отметим, что многоэтапные задачи стохастического программирования не являются тривиальными обобщениями двухэтапных задач. Многие результаты, справедливые для двухэтапных задач общего вида, неверны для многоэтапных. Например, оптимальные решающие правила линейных двухэтапных задач с вероятностными ограничениями — кусочно-линейные функции от некоторых случайных параметров условий задачи. Для многоэтапных задач это утверждение, вообще говоря, неверно [70]. [c.256]
Приведем примеры вычисления априорных решающих правил многоэтапных задач стохастического программирования по решающим правилам эквивалентных двухэтапных и одноэтапных задач. [c.259]
Приведем две различные постановки многоэтапных задач стохастического программирования в терминах лексикографической оптимизации. [c.271]
Динамическая задача прогноза значительно усложняется при наличии корреляции между величинами С", отвечающими разным интервалам времени ( —Tit ti). Вычисление оптимального прогноза оказывается в этом случае многоэтапной задачей стохастического программирования, анализ которой связан с существенно большими трудностями. Решение таких задан, вообще говоря, не сводится к анализу более простых моделей прогноза, как это имело место в задачах, рассмотренных в 6—9. [c.341]
Структура функционалов, отвечающих многоэтапным задачам стохастического программирования, еще более сложна. [c.343]
Юдин Д. Б. Многоэтапные задачи стохастического программирования. ДАН СССР, 1973, т. 210, № 3. [c.394]
Юдин Д. Б. Методы построения решающих правил многоэтапных задач стохастического программирования. ДАН СССР, 1973, т. 210, № 4. [c.394]
Юдин Д. Б., Ц о и Э. В. Многоэтапные задачи стохастического программирования с априорными решающими правилами. — Экономика и математические методы , 1973, т. IX, БЫП. 5. [c.394]
Юдин А. Д. Двойственность в многоэтапных задачах стохастического программирования.— Техническая кибернетика , 1973, № 6. [c.394]
Настоящая монография содержит пятнадцать глав. В гл. 1, носящей вводный характер, классифицируются постановки задач стохастического программирования, приводится краткая историческая оправка и излагается вспомогательный математический аппарат. Глава 2 посвящена анализу постановок различных технических и экономических прикладных задач управления в условиях неполной информации. Содержание последующих девяти глав связано с активным подходом к стохастическому программированию — (формальной основой для выбора решений в условиях неполной информации. В гл. 3—5 исследуются од-ноэтапные стохастические задачи с вероятностными и статистическими ограничениями, решаемые в чистых и смешанных стратегиях, в априорных и апостериорных решающих правилах и решающих распределениях. Главы 6—8 посвящены теории и вычислительным схемам классической двухзтапной задачи стохастического программирования. В гл. 9—11 описаны динамические модели управления в условиях неполной информации — многоэтапные задачи стохастического программирования с условными и безусловными статистическими и вероятностными ограничениями с априорными и апостериорными решающими правилами. [c.6]
Естественным обобщением двухэтапных задач являются многоэтапные задачи стохастического программирования. Часто в процессе управления представляется возможность последовательно наблюдать ряд реализаций параметров условий и соответствующим образом корректировать план. Естественяо, что >при составлении предварительного плана и при последовательной коррекции должны учитываться априор- [c.13]
Среди моделей стохастического программирования значительное место занимают динамические вероятностные модели. Формализация таких моделей и построение соответствующих вычислительных процедур представляют значительные трудности. Продвижение в постановках и анализе таких задач (в частности, многоэтапных задач стохастического программирования) относительно невелико. Здесь следует упомянуть работы А. Чарнса и М. Кирби [308—310], Айзнера, Каплана и Содена [340], Д. Б. Юдина [352—357], Н. 3. Шора [332—336], Д. Б. Юдина и Э. В. Цоя 360]. Значительно боль- [c.17]
В многоэтапной модели фильтрации и прогноза на i -м этапе, исходя из накопленной до сих пор информации и принятых решений, сглаживается или экстраполируется процесс т)(/) при t=ti. При этом, однако, учитывается, что критерий качества и ограничения задачи связывают между собой все оценки j, i—1,. .., п. Многоэтапная модель фильтрации и прогнозирования описывается многоэтапной задачей стохастического программирования с жесткими или условными статистическими или условными вероятностными ограничениями. В зависимости от содержательных особенностей задачи многоэтапная модель, как и одноэтап-ная, решается в априорных или апостериорных решающих правилах или решающих распределениях. [c.39]
В предыдущих параграфах главы мы рассматривали многоэтапные стохастические задачи с условными и безусловными, статистическими и вероятностными ограничениями. Более непосредственным и естественным обобщением классической двухэтапной модели стохастического программирования являются многоэтапные задачи, в которых исключаются невязки условий при всех реализациях случая. На каждом этапе после получения информации о реализованных случайных параметрах условий задачи и о принятом на предыдущем этапе решении вводится коррекция, гарантирующая удовлетворение ограничений при всевозможных состояниях природы oeQ. По аналогии с соответствующими одноэтапными моделями такие задачи естественно называть многоэтапными задачами стохастического программирования в жесткой постановке. В этих задачах ограничены не средние значения некоторых функционалов (как в моделях предыдущих параграфов), а значения случайных функционалов при всех реализациях oeQ. [c.202]
Приведем некоторые качественные характеристики важного частного класса многоэтапных задач стохастического программирования с априорными решающими Правилами. Речь идет о многоэтапных линейных стохастических задачах с условными вероятностными ограничениями. Компоненты вектор-функции i f (u)fe, xk) представляют собой в рассматриваемом классе задач условные характеристические функции полупространств, определяемых строками неравенств [c.234]