Задача (3.1)-(3.4) является задачей со смешанными условиями в жесткой постановке и в частных случаях путем исключения тех или иных ограничений может быть преобразована в задачу с вероятностными ограничениями или в задачу со статистическими условиями. [c.55]
Заметим, что в задачах стохастического программирования со статистическими условиями связка в ограничениях исключена не во всех случаях, как IB жестких постановках, и не в большинстве случаев, как в задачах с вероятностными ограничениями (при j>V2), а в среднем. Это значит, что невязки могут возникнуть при каждой реализации условий. Однако невязки условий, отвечающие различным реализациям состояния природы, компенсируют друг друга так, что средняя невязка условий равна нулю. [c.10]
Таким образом, запись (1.4) — (1.6) включает в себя и задачи с вероятностными ограничениями. Некоторые усложнения позволяют в аналогичной форме записывать и многоэтапные стохастические задачи с условными и безусловными ограничениями. 10 [c.10]
Оптимальные планы многоэтапных задач с условными статистическими или вероятностными ограничениями представляют собой решающие правила или решающие распределения — зависимости компонент решения или статистических характеристик распределения составляющих решения от реализованных и наблюденных к моменту выбора решения значений случайных параметров условий задачи. [c.14]
Если по условиям работы можно отказаться от жесткого выполнения плана по всем контрольным показателям, целесообразно перейти от классической двухэтапной задачи к двухэтапной задаче с вероятностными ограничениями [c.35]
В 1—2 рассматриваются стохастические задачи с вероятностными ограничениями, порожденные моделями линейного программирования. В 1 оператор вероятности применяется к каждой строке ограничений в отдельности, а в 2 — одновременно к совокупности всех ограничений. В обоих параграфах рассматриваются такие распределения случайных параметров условий, при которых эквивалентные детерминированные задачи оказываются задачами выпуклого программирования. Параграф 3 посвящен построению эквивалентных детерминированных моделей для общей одноэтапной стохастической задачи с вероятностными ограничениями, порожденной, вообще говоря, нелинейной моделью математического программирования. В 4 рассматриваются две простые, но представляющие интерес для приложений частные модели стохастических задач, в которых решения определяются в детерминированных векторах. Параграфы 5—6 посвящены стохастическим моделям оценки невязок с детерминированными оптимальными планами. В 5 рассматривается классификация таких моделей. В 6 исследуются условия, при которых соответствующие детерминированные эквивалентные задачи являются задачами выпуклого программирования. Ясно, что только в таких случаях можно говорить о конструктивных методах решения задачи. [c.62]
В стохастических задачах с вероятностными ограничениями можно определять решение в виде детерминированных или случайных векторов х, в чистых или смешанных стратегиях. [c.62]
В качестве целевой функции задачи стохастического линейного программирования с вероятностными ограничениями обычно принимают такие функционалы, как математическое ожидание или дисперсию линейной формы или вероятность превышения линейной формой некоторого фиксированного порога. Задачи с целевой функцией сх = 62 [c.62]
Будем называть задачи с вероятностными ограничениями, заданными в форме (а), задачами с построчными вероятностными ограничениями, а задачи с ограничениями в форме (б) — задачами с вероятностным ограничением. [c.63]
Рассмотрим задачу линейного стохастического программирования с вероятностными ограничениями типа (а) [c.64]
Для стохастической задачи (1.1) — (1.3) с детерминированной матрицей А, т. е. для задачи (1.5) — (1.7), можно записать двойственную задачу с вероятностными ограничениями. [c.65]
Как мы видели, далеко не во всех случаях имеются конструктивные подходы к построению детерминированных эквивалентов стохастических задач с вероятностными ограничениями. Предположение о нормальном распределении случайных параметров условий задачи, [c.69]
Задачи с вероятностным ограничением [c.70]
В п. 1.2 рассмотрена линейная стохастическая задача с вероятностными ограничениями, в которых случайными были только независимые между собой составляющие вектора Ь. Эквивалентная детерминированная задача (1.5) — (1.7) в этом случае оказалась линейной. Несколько сложнее обстоит дело в том случае, когда вероятностное ограничение задано в форме (б), даже если при этом отдельные компоненты вектора b независимы между собой. Эквивалентная детерминированная задача в этом случае формулируется следующим образом. Требуется вычислить детерминированные векторы х и g(x) (или х и 5), при которых [c.71]
Таким образом, детерминированная задача, эквивалентная стохастической задаче с вероятностными ограничениями, в которой случайные составляющие вектора Ъ независимы между собой и распределены по экспоненциальному закону, оказывается задачей. линейного программирования. [c.73]
Пусть распределение Рь(Б) — компонент случайного вектора в задаче с вероятностными ограничениями — приводит к эквивалентной задаче выпуклого программирования. Тогда и распределение Fb[h(B)], где h(S) — неотрицательная выпуклая вниз возрастающая функция, не равная тождественно постоянной, сводит стохастическую задачу к эквивалентной детерминированной задаче выпуклого программирования. [c.74]
Задачи с вероятностными ограничениями. Общий случай [c.74]
В предыдущих параграфах рассмотрены частные стохастические задачи с вероятностными ограничениями, порожденные моделями линейного программирования. Специфика стохастического характера условий позволила в каждом из рассмотренных случаев построить эквивалентную детерминированную задачу. Ниже приводится достаточно общий прием построения детерминированного эквивалента для широкого класса задач стохастического программирования, решение которых определяется среди детерминированных векторов. [c.74]
По аналогии с тремя формами записи области определения линейных стохастических задач с вероятностными ограничениями приведем три формы записи вероятностных условий для общего случая [c.74]
Введенные понятия позволяют сформулировать детерминированные задачи математического программирования, решения которых совпадают с решениями соответствующих стохастических задач с вероятностными ограничениями. Такие задачи мы будем называть детерминированными эквивалентами стохастической задачи. [c.75]
Легко видеть, что конкретизация полученных условий применительно к задаче с вероятностным ограничением, рассмотренной в предыдущем параграфе, приводит в точности к выведенным там соотношениям. [c.95]
Во-вторых, верхняя грань в задаче (5.4) — (5.6) в точности равна верхней грани соответствующей задачи с вероятностными ограничениями, получающейся из (5.4) — (5.6) исключением последнего условия. [c.106]
Решением этой задачи является детерминированный план х, т. е. оптимальная стратегия первого, игрока — чистая стратегия. Подобные стохастические задачи с вероятностными ограничениями подробно рассмотрены в 1, 2 гл. 3. [c.136]
Теория многоэтапного стохастического программирования еще слабо развита. Конструктивных методов решения задач достаточно общего вида в настоящее время нет. Имеются лишь методы решения частных классов многоэтапных стохастических задач с условными или безусловными вероятностными ограничениями. Чтобы расширить круг приложений разрабатываемых конструктивных вычислительных методов, естественно попытаться установить связь между задачами с условными и безусловными статистическими ограничениями, отвечающими одним и тем же функциям фо(ы", хп) и г з/((сой, xh), k = ],. .., п. [c.198]
Используя схему построения апостериорного решающего правила одноэтапной задачи с вероятностным ограничением, изложенную в 2 гл. 4, и результаты предыдущего параграфа, можно получить полное описание решения задачи (3.1) — (3.2). [c.212]
Специальный интерес представляет вырожденный случай многоэтапной стохастической задачи с вероятностными ограничениями, ког- [c.238]
Если, кроме того, составляющие векторов i детерминированы, то многоэтапная стохастическая задача с вероятностными ограничениями сведется к задаче линейного программирования с блочно-треугольной матрицей условий [c.239]
Отметим, что многоэтапные задачи стохастического программирования не являются тривиальными обобщениями двухэтапных задач. Многие результаты, справедливые для двухэтапных задач общего вида, неверны для многоэтапных. Например, оптимальные решающие правила линейных двухэтапных задач с вероятностными ограничениями — кусочно-линейные функции от некоторых случайных параметров условий задачи. Для многоэтапных задач это утверждение, вообще говоря, неверно [70]. [c.256]
В тех случаях, когда по содержательным соображениям можно допустить, чтобы невязки в условиях не превышали заданных с вероятностями, небольшими а/ > 0, говорят о стохастических задачах с вероятностными ограничениями [c.21]
Для решения задачи стохастического программирования в Р- постановке и с вероятностными ограничениями переходят к детерминированному эквиваленту [c.148]
Задача стохастического программирования (3.1) -(3.3) в зависимости от вида целевого функционала (3.1) преобразуется в одноэтапную М -модель с вероятностными ограничениями, одноэтапную /"-модель с вероятностными ограничениями, одноэтапную /"-модель со смешанными условиями (для решения этих моделей используются априорные или апостериорные решающие правила) либо в одноэтапную задачу с построчными вероятностными ограничениями и решающими правилами нулевого порядка. [c.57]
Организационно-экономическому содержанию и целевому назначению задачи планирования производственной программы НПП в условиях неполноты технике-экономической информации соответствует следующая постановка с вероятностными ограничениями, учитывающая директивный характер текущих плановых решений [c.61]
Мы рассматривали стохастические аналоги задач линейного программирования. Как легко видеть, детерминированные эквиваленты задач линейного программирования со случайными параметрами условий, соответствующие, например, моделям с вероятностными ограничениями, представляют собой, вообще говоря, задачи нелинейного, а иногда и невыпуклого программирования. Поэтому в стохастическом программировании обычно несущественно, порождена ли стохастическая задача линейной или нелинейной экстремальной задачей. Если не ограничиваться стохастическими аналогами линейных моделей, можно привести более общую запись задачи стохастического программирования, объединяющую различные постановки стохастических задач. [c.10]
Обычно процесс разведки и установления характеристик природных факторов растянут во времени. Различные характеристики угольных пластов могут быть получены и учтены на разных этапах работы. В таких случаях естественно рассматривать задачу планирования развития горнорудного комбината как многоэтапную с жесткими или условными вероятностными ограничениями и с априорными решающими правилами. [c.35]
Менее жесткая постановка задачи идентификации объекта может быть представлена в виде следующей задачи стохастического программирования с вероятностными ограничениями. [c.47]
По-видимому, наиболее естественная постановка задачи перспективного планирования представляет собой многоэтапную задачу стохастического программирования с жесткими или условными вероятностными ограничениями и с априорными решающими правилами. [c.61]
Постановки задач стохастического программирования с вероятностными ограничениями естественным образом возникают в двух классах ситуаций. Задачи планирования или управления в условиях неполной информации, соответствующие первому классу ситуаций, требуют по своему содержанию жесткой постановки, но при этом множество планов задачи оказывается пустым. В таких ситуациях задача становится осмысленной только в том случае, если допустить нарушение ограничений на некотором множестве состояний природы. В ситуациях второго класса затраты на исключение невязок условий задачи при относительно редко встречающихся состояниях природы не окупаются достигаемым при этом эффектом от оптимизации целевой функции. [c.62]
Не имея возможности остановиться на многочисленных публикациях по указанной проблеме, отметим лишь соответствующие наши публикации [24, 37, 39, 40, 42, 44, 51, 52, 93, 97 и др.]. Подчеркнем, что в наиболее полном, хотя и давнем, обзоре [42] представлена довольно обширная библиография и систематически излагаются идеи постановок, модели и методы соответствующих задач общего и частного характера (жесткие и нежесткие постановки, задачи с вероятностными ограничениями, двухэтапные, на отыскание случайных наборов параметров и других). Ряд упомянутых выше работ [24, 52, 93, 97, 37] непосредственно реализует модели и методы, связанные с задачами развития ТЭК. [c.67]
Стохастические задачи с вероятностными ограничениями впервые были рассмотрены в работах А. Чарнса, В. Купера и Дж. Саймондса [317,318]. В дальнейшем моде-лч с вероятностными ограничениями изучались в ряде работ тех же авторов [314—316,. 240, 241], в статьях Б. Миллера и X. Вагнера (203], С. Катаока [155—158] и др. [c.17]
Этот результат, принадлежащий Бен-Израэлю, позволяет для рассматриваемого частного класса стохастических задач с вероятностными ограничениями использовать интерпретации теорем двойственности для качественного анализа решения и оценки параметров задачи. [c.66]
Приведем некоторые классы линейных стохастических задач с вероятностными ограничениями, для которых детерминированные эквива- [c.70]
Первой попыткой перехода от статических моделей стохастического программирования к динамическим была, по-видимому, двухэтапная задача Данцига — Маданского. Двухэтапная задача может быть обобщена в различных направлениях. Естественно, например, перейти к многоэтапной задаче с жесткими ограничениями (с ограничениями, которые должны выполняться при всех возможных реализациях случая, подобно тому, как это предполагается в классической двухэтапной задаче). Такого рода подходы рассматривались Беллманом [10], Дж. Данцигом [88], Н. 3. Шором и др. [332, 334—336]. Здесь мы, однако, рассмотрим более широкие обобщения двухэтапной задачи — различные постановки многоэтапных стохастических задач с безусловными и условными статистическими, вероятностными и жесткими ограничениями. Частные модели подобного типа обсуждались в [70, 308—310] и других работах. Многоэтапные модели стохастического программирования имеют многочисленные приложения к задачам планирования в экономике и технике. Ряд практических проблем, возникающих при перспективном планировании, при многостадийном проектировании, при управлении боевыми операциями, при планировании экспериментов и оперативном управлении космическими объектами, при регулировании технологических процессов, подверженных случайным возмущениям, может быть рассмотрен как многоэтапные стохастические задачи со статистическими вероятностными и жесткими ограничениями. [c.192]
Настоящая монография содержит пятнадцать глав. В гл. 1, носящей вводный характер, классифицируются постановки задач стохастического программирования, приводится краткая историческая оправка и излагается вспомогательный математический аппарат. Глава 2 посвящена анализу постановок различных технических и экономических прикладных задач управления в условиях неполной информации. Содержание последующих девяти глав связано с активным подходом к стохастическому программированию — (формальной основой для выбора решений в условиях неполной информации. В гл. 3—5 исследуются од-ноэтапные стохастические задачи с вероятностными и статистическими ограничениями, решаемые в чистых и смешанных стратегиях, в априорных и апостериорных решающих правилах и решающих распределениях. Главы 6—8 посвящены теории и вычислительным схемам классической двухзтапной задачи стохастического программирования. В гл. 9—11 описаны динамические модели управления в условиях неполной информации — многоэтапные задачи стохастического программирования с условными и безусловными статистическими и вероятностными ограничениями с априорными и апостериорными решающими правилами. [c.6]
Во многих задачах управления в условиях неполной информации, свя занных с повторяющимися ситуациями, нет необходимости в том, чтобы ограничения задачи удовлетворялись при каждой реализации случая (или, как говорят, при каждой реализации состояния природы). Затраты на накопление информации или другие затраты, обеспечивающие исключение невязок в условиях задачи, могут превышать достигаемый при этом эффект. Часто конкретное содержание задачи требует лишь, чтобы вероятность попадания решения в допустимую область превышала некоторое заранее заданное число а>0. В тех случаях, когда возможные невязки в отдельных ограничениях вызьшают различный ущерб, целесообразно дифференцированно подходить к разным условиям. Чтобы уравновесить ущерб, определяемый невязками в разных условиях задачи, естественно ограничить снизу вероятность выполнения каждого из них различными числами а >0. Обычно аг>]/2- Подобные постановки задач стохастического программирования называются моделями с вероятностными ограничениями. Если коэффициенты линейной формы сх задачи детерминированы, то показатель 1 качества (1.1) является в то же время и целевой функцией задачи с вёроятност-ными ограничениями. Если компоненты вектора с случайны , TQ в качестве целевой функции задачи с вероятностными ограничениями обычно выбирают математическое ожидание линейной формы (1.1) или вероятность превышения линейной формой сх некоторого фиксированного порога. [c.9]