Задача (3.1)-(3.4) является задачей со смешанными условиями в жесткой постановке и в частных случаях путем исключения тех или иных ограничений может быть преобразована в задачу с вероятностными ограничениями или в задачу со статистическими условиями. [c.55]
Заметим, что в задачах стохастического программирования со статистическими условиями связка в ограничениях исключена не во всех случаях, как IB жестких постановках, и не в большинстве случаев, как в задачах с вероятностными ограничениями (при j>V2), а в среднем. Это значит, что невязки могут возникнуть при каждой реализации условий. Однако невязки условий, отвечающие различным реализациям состояния природы, компенсируют друг друга так, что средняя невязка условий равна нулю. [c.10]
Таким образом, запись (1.4) — (1.6) включает в себя и задачи с вероятностными ограничениями. Некоторые усложнения позволяют в аналогичной форме записывать и многоэтапные стохастические задачи с условными и безусловными ограничениями. 10 [c.10]
Если по условиям работы можно отказаться от жесткого выполнения плана по всем контрольным показателям, целесообразно перейти от классической двухэтапной задачи к двухэтапной задаче с вероятностными ограничениями [c.35]
В 1—2 рассматриваются стохастические задачи с вероятностными ограничениями, порожденные моделями линейного программирования. В 1 оператор вероятности применяется к каждой строке ограничений в отдельности, а в 2 — одновременно к совокупности всех ограничений. В обоих параграфах рассматриваются такие распределения случайных параметров условий, при которых эквивалентные детерминированные задачи оказываются задачами выпуклого программирования. Параграф 3 посвящен построению эквивалентных детерминированных моделей для общей одноэтапной стохастической задачи с вероятностными ограничениями, порожденной, вообще говоря, нелинейной моделью математического программирования. В 4 рассматриваются две простые, но представляющие интерес для приложений частные модели стохастических задач, в которых решения определяются в детерминированных векторах. Параграфы 5—6 посвящены стохастическим моделям оценки невязок с детерминированными оптимальными планами. В 5 рассматривается классификация таких моделей. В 6 исследуются условия, при которых соответствующие детерминированные эквивалентные задачи являются задачами выпуклого программирования. Ясно, что только в таких случаях можно говорить о конструктивных методах решения задачи. [c.62]
В стохастических задачах с вероятностными ограничениями можно определять решение в виде детерминированных или случайных векторов х, в чистых или смешанных стратегиях. [c.62]
Будем называть задачи с вероятностными ограничениями, заданными в форме (а), задачами с построчными вероятностными ограничениями, а задачи с ограничениями в форме (б) — задачами с вероятностным ограничением. [c.63]
Для стохастической задачи (1.1) — (1.3) с детерминированной матрицей А, т. е. для задачи (1.5) — (1.7), можно записать двойственную задачу с вероятностными ограничениями. [c.65]
Как мы видели, далеко не во всех случаях имеются конструктивные подходы к построению детерминированных эквивалентов стохастических задач с вероятностными ограничениями. Предположение о нормальном распределении случайных параметров условий задачи, [c.69]
В связи с изложенными соображениями о трудностях, возникающих при анализе задач стохастического программирования с вероятностными ограничениями, представляет интерес предложенный в [246] приближенный подход к выбору решения подобных задач. Здесь предполагается, что принимающему решение в условиях неполной информации важно во что -бы то вди стало сократить вероятность чрезвычайного события, связанного с превышением целевой функцией некоторого порога. Вероятность этого события так же, как и вероятности выполнения ограничений, может быть оценена сверху с помощью неравенства Чебышева или различных его модификаций. Таким образом, вместо минимизации вероятности соблюдения некоторого неравенства (например, вероятности того, что линейная форма не превысит заданный порог) предлагается минимизировать верхнюю границу этой вероятности. Вместо ограничений снизу вероятностей некоторых событий (например, соблюдения неравенств со случайными коэффициентами) предлагается ограничить снизу верхние границы этих вероятностей. Можно указать случаи, когда границы,. получаемые с помощью неравенства Чебышева или его модификаций, оказываются недостаточно эффективными. Кроме того, детерминированные экстремальные задачи, получаемые при замене вероятностного показателя качества решения и вероятностных ограничений их оценками, могут оказаться невыпуклыми задачами. Тем не менее указанный приближенный подход, не требующий информации о распределении случайных параметров условий, может в ряде случаев, как об этом свидетельствуют примеры, рассмотренные в (246], оказаться полезным для оценки решения трудоемких стохастических задач с вероятностными ограничениями. [c.70]
Задачи с вероятностным ограничением [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]
Используя схему построения апостериорного решающего правила одноэтапной задачи с вероятностным ограничением, изложенную в 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.47]
Постановки задач стохастического программирования с вероятностными ограничениями естественным образом возникают в двух классах ситуаций. Задачи планирования или управления в условиях неполной информации, соответствующие первому классу ситуаций, требуют по своему содержанию жесткой постановки, но при этом множество планов задачи оказывается пустым. В таких ситуациях задача становится осмысленной только в том случае, если допустить нарушение ограничений на некотором множестве состояний природы. В ситуациях второго класса затраты на исключение невязок условий задачи при относительно редко встречающихся состояниях природы не окупаются достигаемым при этом эффектом от оптимизации целевой функции. [c.62]
Постановки задач стохастического программирования с вероятностными ограничениями различаются по трем признакам 1) по характеру решений 2) по выбору показателя качества решения 3) по способу расчленения ограничений задачи. [c.62]
В качестве целевой функции задачи стохастического линейного программирования с вероятностными ограничениями обычно принимают такие функционалы, как математическое ожидание или дисперсию линейной формы или вероятность превышения линейной формой некоторого фиксированного порога. Задачи с целевой функцией сх = 62 [c.62]
Рассмотрим задачу линейного стохастического программирования с вероятностными ограничениями типа (а) [c.64]
Сравнивая последнюю задачу с исходной (1.1) — (1-3), приходим к выводу, что при p = G( ) следующие две одноэтапные задачи стохастического программирования с вероятностными ограничениями и априорными решающими правилами представляют собой двойственную [c.65]
Класс задач стохастического программирования с вероятностными ограничениями, которым соответствуют выпуклые детерминированные эквиваленты, можно расширить, если учесть следующие замечания. [c.73]
Не имея возможности остановиться на многочисленных публикациях по указанной проблеме, отметим лишь соответствующие наши публикации [24, 37, 39, 40, 42, 44, 51, 52, 93, 97 и др.]. Подчеркнем, что в наиболее полном, хотя и давнем, обзоре [42] представлена довольно обширная библиография и систематически излагаются идеи постановок, модели и методы соответствующих задач общего и частного характера (жесткие и нежесткие постановки, задачи с вероятностными ограничениями, двухэтапные, на отыскание случайных наборов параметров и других). Ряд упомянутых выше работ [24, 52, 93, 97, 37] непосредственно реализует модели и методы, связанные с задачами развития ТЭК. [c.67]
Во многих задачах управления в условиях неполной информации, свя занных с повторяющимися ситуациями, нет необходимости в том, чтобы ограничения задачи удовлетворялись при каждой реализации случая (или, как говорят, при каждой реализации состояния природы). Затраты на накопление информации или другие затраты, обеспечивающие исключение невязок в условиях задачи, могут превышать достигаемый при этом эффект. Часто конкретное содержание задачи требует лишь, чтобы вероятность попадания решения в допустимую область превышала некоторое заранее заданное число а>0. В тех случаях, когда возможные невязки в отдельных ограничениях вызьшают различный ущерб, целесообразно дифференцированно подходить к разным условиям. Чтобы уравновесить ущерб, определяемый невязками в разных условиях задачи, естественно ограничить снизу вероятность выполнения каждого из них различными числами а >0. Обычно аг>]/2- Подобные постановки задач стохастического программирования называются моделями с вероятностными ограничениями. Если коэффициенты линейной формы сх задачи детерминированы, то показатель 1 качества (1.1) является в то же время и целевой функцией задачи с вёроятност-ными ограничениями. Если компоненты вектора с случайны , TQ в качестве целевой функции задачи с вероятностными ограничениями обычно выбирают математическое ожидание линейной формы (1.1) или вероятность превышения линейной формой сх некоторого фиксированного порога. [c.9]
Стохастические задачи с вероятностными ограничениями впервые были рассмотрены в работах А. Чарнса, В. Купера и Дж. Саймондса [317,318]. В дальнейшем моде-лч с вероятностными ограничениями изучались в ряде работ тех же авторов [314—316,. 240, 241], в статьях Б. Миллера и X. Вагнера (203], С. Катаока [155—158] и др. [c.17]
Этот результат, принадлежащий Бен-Израэлю, позволяет для рассматриваемого частного класса стохастических задач с вероятностными ограничениями использовать интерпретации теорем двойственности для качественного анализа решения и оценки параметров задачи. [c.66]
Приведем некоторые классы линейных стохастических задач с вероятностными ограничениями, для которых детерминированные эквива- [c.70]
Настоящая монография содержит пятнадцать глав. В гл. 1, носящей вводный характер, классифицируются постановки задач стохастического программирования, приводится краткая историческая оправка и излагается вспомогательный математический аппарат. Глава 2 посвящена анализу постановок различных технических и экономических прикладных задач управления в условиях неполной информации. Содержание последующих девяти глав связано с активным подходом к стохастическому программированию — (формальной основой для выбора решений в условиях неполной информации. В гл. 3—5 исследуются од-ноэтапные стохастические задачи с вероятностными и статистическими ограничениями, решаемые в чистых и смешанных стратегиях, в априорных и апостериорных решающих правилах и решающих распределениях. Главы 6—8 посвящены теории и вычислительным схемам классической двухзтапной задачи стохастического программирования. В гл. 9—11 описаны динамические модели управления в условиях неполной информации — многоэтапные задачи стохастического программирования с условными и безусловными статистическими и вероятностными ограничениями с априорными и апостериорными решающими правилами. [c.6]
Таким образом, при принятых допущениях линейная стохастическая задача (1.1) — (1.3) с вероятностными ограничениями сводится к детер минированной задаче выпуклого программирования с линейной делевой функцией и квадратичными условиями-неравенствами [c.67]