Сведение задачи стохастического программирования к эквивалентной детерминированной задаче является эффективным средством анализа стохастических моделей лишь в тех случаях, когда детерминированные эквиваленты оказываются задачами линейного или выпуклого программирования. [c.70]
В п. 1.2 рассмотрена линейная стохастическая задача с вероятностными ограничениями, в которых случайными были только независимые между собой составляющие вектора Ь. Эквивалентная детерминированная задача (1.5) — (1.7) в этом случае оказалась линейной. Несколько сложнее обстоит дело в том случае, когда вероятностное ограничение задано в форме (б), даже если при этом отдельные компоненты вектора b независимы между собой. Эквивалентная детерминированная задача в этом случае формулируется следующим образом. Требуется вычислить детерминированные векторы х и g(x) (или х и 5), при которых [c.71]
Преобразование, заменяющее условия вида (2.3) на ограничения (2.5), упрощает, таким образом, решение эквивалентных детерминированных задач. [c.73]
Пусть распределение Рь(Б) — компонент случайного вектора в задаче с вероятностными ограничениями — приводит к эквивалентной задаче выпуклого программирования. Тогда и распределение Fb[h(B)], где h(S) — неотрицательная выпуклая вниз возрастающая функция, не равная тождественно постоянной, сводит стохастическую задачу к эквивалентной детерминированной задаче выпуклого программирования. [c.74]
В предыдущих параграфах рассмотрены частные стохастические задачи с вероятностными ограничениями, порожденные моделями линейного программирования. Специфика стохастического характера условий позволила в каждом из рассмотренных случаев построить эквивалентную детерминированную задачу. Ниже приводится достаточно общий прием построения детерминированного эквивалента для широкого класса задач стохастического программирования, решение которых определяется среди детерминированных векторов. [c.74]
Аналогичным образом формулируется и обосновывается эквивалентная детерминированная задача для стохастических задач, вероятностные условия которых записываются в форме (а) или (в). Например, детерминированный эквивалент задачи [c.76]
Иногда решение эквивалентной детерминированной задачи может быть упрощено, если имеются основания заменить ограничения на линейную комбинацию математического ожидания и среднеквадратической величины невязки ограничениями на линейную комбинацию первых двух моментов распределения невязки. [c.81]
Эквивалентная детерминированная задача [c.159]
Эквивалентная детерминированная задача имеет вид [c.159]
Теорема 4.1. Пусть матрица В удовлетворяет условиям теоремы 3.3 и множество планов задачи (3.8) — (3.9) не пусто. Тогда целевая функция (4.1) эквивалентной детерминированной задачи конечна для любого х<=К2- [c.160]
Рассмотрим несколько других форм записи эквивалентной детерминированной задачи для простейшей постановки двухэтапной задачи. При различных условиях разные формы записи могут оказаться более удобными для анализа. [c.174]
Поэтому эквивалентная детерминированная задача для двухэтапной задачи в простейшей постановке может быть переписана в виде [c.175]
Эквивалентная детерминированная задача для двухэтапной стохастической задачи в простейшей постановке в форме (3.21) — (3.25) линейна относительно переменных Xj, v,t, v-i и выпукла и сепарабельна [c.177]
Как мы видели, наиболее трудная часть решения двухэтапной задачи стохастического программирования—определение предварительного плана — сводится к решению эквивалентной детерминированной задачи. Доказано, что эквивалентная задача является задачей выпуклого программирования. Однако в общем случае для ее решения стандартные методы выпуклого программирования неприменимы. Дело в том, что как целевая функция, так и область определения планов общей двухэтапной задачи заданы неявно. Показатель качества решения эквивалентной задачи далеко не всегда представляет собой дифференцируемую функцию. Вычисление параметров задачи, используемых в стандартных методах решения выпуклых задач, сопряжено со значительными трудностями. Существующие методы решения двухэтапных задач стохастического программирования используют специфические особенности эквивалентной детерминированной задачи. В настоящем параграфе рассмотрены общие и специальные методы вычисления предварительного плана и некоторые неравенства, позволяющие получить и оценить приближенные решения эквивалентной задачи. Ясно, что во всех частных случаях, в которых удается получить явную запись эквивалентной задачи в виде простой линейной, кусочно-линейной или выпуклой задачи, нет необходимости прибегать к предлагаемым здесь, вообще говоря, трудоемким методам. [c.180]
Поэтому для вычисления предварительного плана х двухэтапной задачи или, что то же самое, для решения эквивалентной детерминированной задачи [c.182]
Как мы видели (см. 4 гл. 6), эквивалентная детерминированная задача имеет вид [c.185]
Эквивалентная детерминированная задача имеет в рассматриваемом случае вид [c.188]
Условия г/ 0 вместе с условиями (а) и (б), которым удовлетворяют блоки D и — F матрицы компенсации В, позволяют перейти от решающего правила в форме (3.30) к соотношению (3.27). Подставляя значение у в выражение (3.1) для целевой функции двухэтапной задачи, получаем эквивалентную детерминированную задачу в форме (3.28) — (3.29). 188 [c.188]
Мы видели, что эквивалентная детерминированная задача может быть записана в виде (2.1) — (2.2) [c.189]
Таким образом, модель с построчными вероятностными ограничениями при независимости варьируемых способов производства с учетом структурных и функциональных особенностей математического описания нефтеперерабатывающих производств в задачах технике-экономического планирования преобразуется в эквивалентную детерминированную линейную модель. [c.68]
Отсюда следует эквивалентность задачи стохастического программирования (1.1) — (1.3) и детерминированной задачи линейного программирования [c.65]
Таким образом, детерминированная задача, эквивалентная стохастической задаче с вероятностными ограничениями, в которой случайные составляющие вектора Ъ независимы между собой и распределены по экспоненциальному закону, оказывается задачей. линейного программирования. [c.73]
Детерминированная задача, эквивалентная приведенной стохастической задаче, представляет собой следующую задачу дробно-линейного программирования [c.77]
Построим детерминированную задачу, эквивалентную двух-этапной задаче стохастического программирования. Решением эквивалентной задачи является предварительный план х. По составляющим оптимального предварительного плана и реализациям параметров условий строится задача второго этапа — задача линейного программирования, решение которой определяет необходимую компенсацию плана. [c.159]
Выразим Q(x) через статистические характеристики параметров условий задачи и докажем, что детерминированная задача, эквивалентная задаче стохастического программирования, является задачей выпуклого программирования. [c.159]
Теорема 4.2. Детерминированная задача (4.1) — (4.2), эквивалентная двухэтапной задаче (1.8) — (1.10), является задачей выпуклого программирования. [c.160]
Теорема 5.2. (Необходимое и достаточное условие оптимальности плана двухэтапной задачи.) Пусть х — внутренняя точка множества К, а целевая функция Q(x) детерминированной задачи, эквивалентной двухэтапной задаче, дифференцируема в окрестности х. Тогда задача (3.8), (3.9), двойственная к задаче второго этапа, имеет решение z (А, Ь, х ), такое, что [c.162]
Теорема 1.1. Множество К планов детерминированной задачи, эквивалентной двухэтапной задаче стохастического программирования, в которой случайным является только вектор ограничений Ь, является выпуклым многогранным множеством. [c.170]
Метод основан на общих свойствах детерминированной задачи, эквивалентной двухэтапной стохастической задаче, и на идее выпуклого программирования, принадлежащей Келли. [c.184]
Заметим, что треугольная форма матрицы условий так же, как и детерминированный характер коэффициентов с,-, не использованы для доказательства эквивалентности стохастической задачи с безусловными вероятностными ограничениями и задачи (4.11) — (4.13) линейного программирования. При решающих правилах нулевого порядка вывод об эквивалентности этих задач справедлив для произвольных детерминированных матриц условий и при случайных параметрах j. [c.201]
Таким образом, в разрешимых задачах линейного программирования введенное лексикографическое упорядочивание совпадает с обычным упорядочиванием, обеспечивающим достижение условного экстремума. Следовательно, если набор (А, Ь, с) детерминирован, задача линейного программирования (1.1) — (1.2) эквивалентна следующей задаче лексикографической оптимизации [c.263]
Мы пришли, таким образом, гк обычной форме записи детерминированной задачи, эквивалентной двухэтапной задаче линейного стохастического программирования. [c.268]
Задача планирования для НПП в детерминированной или вероятностной постановке сводится к решению задачи линейного или выпуклого программирования, причем задачи стохастического программирования, характерные для НПП, как показано в работе [47], преобразуется в эквивалентную задачу линейного программирования, которая имеет вид [c.205]
Легко видеть, что условия (1.6), (1.12), (1.13) из 1, эквивалентные вероятностным ограничениям соответствующих стохастических задач, следуют из неравенств (3.8). Естественно, что если стохастическая задача помимо вероятностных ограничений содержит детерминированные условия, то они переносятся и в эквивалентную задачу. [c.76]
В главе предпринята попытка классификации моделей стохастического программирования, основанная на принципах, предложенных в [183]. Как и другие схемы классификации, излагаемая схема не охватывает ряда известных моделей. Тем не менее, приведенный подход представляется интересным, поскольку он порождает оригинальную интерпретацию экстремальных задач и служит основанием для построения детерминированных эквивалентных моделей для задач стохастического программирования. [c.262]
Эквивалентная детерминированная задача незначительно усложняется, если заменить показатель качества решения стохастиче- [c.67]
Эквивалентная детерминированная задача при этом принимает вид сх — нпах, (2.1) [c.71]
В [142] показано, что если выполняются условия теоремы 4.1 и вероятностная мера в пространстве A, b абсолютно непрерывна относительно меры Лебега в пространстве Л, b (т. е. вероятность попасть в шар достаточно малого радиуса сколь угодно мала), то целевая функция Q(x) эквивалентной детерминированной задачи повсюду на К непрерывно дифференцируема. [c.161]
Как уже отмечалось, метод обобщенных стохастических градиентов не требует дифференцируемости целевой функции эквивалентной детерминированной задачи. Здесь мы рассмотрим возможный вариант применения метода возможных направлений к решению двух-этапной задачи линейного стохастического программирования. Использование и обоснование этого метода требует существования и непрерывности градиента целевой функции эквивалентной детерминированной задачи. В 4 гл. 6 указывалось, что для этого достаточно, чтобы вероятностная мера была абсолютно непрерывна относительно меры Лебега. Как и при изложении других методов, будем предполагать возможность вычисления всех математических ожиданий, значения которых используются в излагаемом ниже алгоритме. [c.189]
Можно построить примеры, в которых оба соотношения (4.6) выполняются как строгие неравенства. Это означает, что задача двухэтап-ного стохастического программирования, вообще говоря, не может быть точно решена, если заменить случайные параметры условий их математическими ожиданиями. Можно, однако, указать достаточные условия, при которых замена допустима. В частности, замена допустима [190], если случайным является только вектор ограничений и если функцию Q(x, А, Ь), определяющую показатель качества решения эквивалентной детерминированной задачи (2.1) — (2.2), можно представить в виде [c.191]
Достаточно конструктивные вычислительные алгоритмы и программы для ЦВМ разработаны только для задач линейного и выпуклого программирования. Поэтому целесообразно выделить случаи, в которых можно гарантировать выпуклость целевой функции и области определения детерминированной задачи, эквивалентной той или инойн стохастической постановке. [c.81]
Согласно теореме 4.3 гл. 6 субградиент в точке х0 целевого функционала детерминированной задачи, эквивалентной двухэтапной задаче стохастического программирования, равен [c.182]
Используя псевдообратные матрицы, можно записать детерминированную задачу, эквивалентную задаче двухэтапного стохастического программирования, в форме, позволяющей выделить ряд случаев, для которых могут быть построены эффективные методы анализа [94, 140, 313, 320]. [c.185]
Теорема 4.1. Последовательность Q(Xh) сходится к оптимальному значению целевой функции детерминированной задачи, эквивалентной двухэтапной стохастической задаче линейного программирования. Последовательность лг/J содержит сходящуюся подпоследовательность. Каждая сходящаяся подпоследовательность из Xh сходится к оптимальному предварительному плану х двухэташюй стохастической задачи. [c.190]