Из задач выпуклого программирования подробно разработаны задачи квадратичного программирования, в которых требуется найти максимум (или минимум) квадратичной функции при условии, что ее переменные удовлетворяют некоторой системе линейных уравнений. [c.104]
Рассматриваемая стохастическая задача при этом преобразуется в детерминированную задачу выпуклого программирования с линейной целевой функцией и квадратичными ограничениями. [c.69]
Утверждение 3.2. Задача (3.98) -(3.1 00), (3.104) является задачей выпуклого программирования. [c.80]
Таким образом, приближенный детерминированный аналог многоэтапной стохастической задачи (3.92) -(3.96) при сделанных допущениях оказывается задачей выпуклого программирования, решение которой может быть осуществлено известными методами [46, 56]. [c.84]
Задача (3.120) —(3.123) является задачей выпуклого программирования с вогнутой целевой функцией и линейной системой ограничений. [c.85]
Модель (4.20) — (4.22), (4.25) является статической энтропийной моделью ЗОК. Она представляет собой (ввиду выпуклости каждого слагаемого и в связи с известной теоремой [56] о выпуклости функции, равной сумме выпуклых функций) задачу выпуклого программирования с ограничениями транспортного типа. [c.119]
Так как задача (4.29) — (4.31) является задачей выпуклого программирования, то к ней может быть применен любой из известных алгоритмов решения. Однако специальный тип ограничений обусловил возможность [c.125]
Прежде чем переходить к его описанию, рассмотрим результаты работы [94], имеющие непосредственное отношение к рассматриваемой проблеме. Изложение будем вести в обозначениях работы [94]. Рассмотрим задачу выпуклого программирования [c.133]
Наряду с (4.64) рассмотрим задачу выпуклого программирования с линейными ограничениями [c.133]
Согласно теореме 1 это задача выпуклого программирования. [c.36]
Запись многих задач стохастического программирования в терминах гильбертова пространства Hin более прозрачна, чем в первичных вероятностных терминах. Ряд естественных для стохастических задач целевых функций оказываются линейными или выпуклыми функционалами в Hin. Некоторые ограничения, используемые в разных постановках задач стохастического программирования, высекают в Htn выпуклые множества. Таким образом, многие задачи стохастического программирования могут рассматриваться как задачи выпуклого программирования в гильбертовом пространстве Н п. [c.20]
Рассмотрим задачу выпуклого программирования в банаховом пространстве В [c.23]
Таким образом, детерминированный эквивалент стохастической транспортной задачи представляет собой задачу выпуклого программирования [c.36]
При принятых допущениях об информационной структуре модели детерминированный эквивалент задачи перспективного планирования представляет собой следующую задачу выпуклого программирования [c.61]
В 1—2 рассматриваются стохастические задачи с вероятностными ограничениями, порожденные моделями линейного программирования. В 1 оператор вероятности применяется к каждой строке ограничений в отдельности, а в 2 — одновременно к совокупности всех ограничений. В обоих параграфах рассматриваются такие распределения случайных параметров условий, при которых эквивалентные детерминированные задачи оказываются задачами выпуклого программирования. Параграф 3 посвящен построению эквивалентных детерминированных моделей для общей одноэтапной стохастической задачи с вероятностными ограничениями, порожденной, вообще говоря, нелинейной моделью математического программирования. В 4 рассматриваются две простые, но представляющие интерес для приложений частные модели стохастических задач, в которых решения определяются в детерминированных векторах. Параграфы 5—6 посвящены стохастическим моделям оценки невязок с детерминированными оптимальными планами. В 5 рассматривается классификация таких моделей. В 6 исследуются условия, при которых соответствующие детерминированные эквивалентные задачи являются задачами выпуклого программирования. Ясно, что только в таких случаях можно говорить о конструктивных методах решения задачи. [c.62]
При сделанных предположениях линейная стохастическая задача (1.1) — (1.3), решение которой определяется в решающих правилах нулевого порядка, сводится к детерминированной задаче выпуклого программирования с линейной целевой функцией и квадратичными ограничениями. [c.66]
Задача (1.18) — (1.20) представляет собой задачу выпуклого программирования. Для решения ее может быть использован метод секущих плоскостей или один из вариантов метода возможных направлений. [c.69]
Оптимальный план полученной задачи выпуклого программирования равен =(0 0,68) А = 0,346. , [c.69]
Заметим, кроме того, что не все задачи выпуклого программирования приспособлены к использованию ряда известных эффективных методов решения. Применение таких методов выпуклого программирования, как методы возможных направлений, метод секущих плоскостей и других методов, связанных с вычислением градиентов функций, определяющих ограничения задачи, предполагает выпуклость каждой из этих функций в соответствующую сторону (в зависимости от знака неравенства). [c.70]
Во всех этих случаях задача (2.1) — (2.4) — задача выпуклого программирования. Однако левые части ограничений (2.3) не являются выпуклыми вверх функциями. Замена условий (2.3) эквивалентными неравенствами [c.72]
Пусть два распределения случайных векторов b приводят к выпуклым детерминированным задачам вида (2.1) — (2.4). Тогда их свертке соответствует также задача выпуклого программирования. [c.74]
Пусть распределение Рь(Б) — компонент случайного вектора в задаче с вероятностными ограничениями — приводит к эквивалентной задаче выпуклого программирования. Тогда и распределение Fb[h(B)], где h(S) — неотрицательная выпуклая вниз возрастающая функция, не равная тождественно постоянной, сводит стохастическую задачу к эквивалентной детерминированной задаче выпуклого программирования. [c.74]
В этих обозначениях задача выпуклого программирования — детерминированный эквивалент задачи (1.1) — (1.3) — принимает вид [c.87]
К- задаче выпуклого программирования может быть сведена и -Р-модель [c.87]
Запишем задачу выпуклого программирования в Hni в виде [c.123]
Мы пришли к решающему правилу вида (7.12). Вычисление параметров К г сводится к решению детерминированной задачи выпуклого программирования, которая может быть получена подстановкой х из (9.19) в условия задачи (7.1) — (7.2). Легко видеть, что сформированная при этом задача может быть приведена к виду (7.11). [c.131]
В предыдущем пункте использованы процедуры итеративных методов решения задач выпуклого программирования в функциональных пространствах для установления вида решающих правил некоторых задач стохастического программирования. Следует, однако, подчеркнуть, что в приведенных рассуждениях существенной была не столько схема 1эе [c.132]
Подставляя выражения для х в условия исходной стохастической задачи, получаем детерминированную задачу выпуклого программирования для вычисления параметров А <. [c.133]
Выразим Q(x) через статистические характеристики параметров условий задачи и докажем, что детерминированная задача, эквивалентная задаче стохастического программирования, является задачей выпуклого программирования. [c.159]
КУНА—ТАККЕРА УСЛОВИЯ [Kuhn—Tu ker onditions] — условия существования оптимальной точки (оптимального решения) в задачах выпуклого программирования и, в частности, — линейного программирования. Соответственно этим условиям для того чтобы точка х была оптимальной, необходимо и достаточно, чтобы пара точек (х, X ) образовала седло функции Лагранжа (см. Лагранжиан, Седловая точка). Таким образом, задача сводится к нахождению совместного решения прямой (поиск ж ) и двойственной (поиск X ) задач. Сформулированы американскими математиками X. Куном и А. Таккером. [c.165]
МНОЖИТЕЛИ ЛАГРАНЖА [Lagrange multipliers] — дополнительные множители, преобразующие целевую функцию экстремальной задачи выпуклого программирования (в частности, линейного программирования) при ее решении одним из классических методов — методом разрешающих множителей (методом Л агранжа). Полученная функция носит название лагранжиан, или функция Лагранжа. Подробнее об этом методе см. в ст. "Лагранжиан". [c.202]
Среди вычислительных алгоритмов Н.п. большое место занимают градиентные методы. Универсального же метода для нелинейных задач нет и, по-видимому, может не быть, поскольку они чрезвычайно разнообразны. Особенно трудно решаются многоэкстремалъпые задачи. Для некоторых типов задач выпуклого программирования (вид нелинейного) разработаны эффективные численные методы оптимизации. [c.222]
Исследование многих классов задач стохастического программирования основано на численных методах решения условных экстремальных задач в функциональных пространствах и теории двойственности бесконечномерного математического программирования. В работах по теории и методам стохастического программирования используются результаты С. И. Зуховицкого, Р. А. Поляка и М. Е. Примака [127] по численному решению задач выпуклого программирования в гильбертовых пространствах и работы Е. Г. Голынтейна [79, 80] и А. Д. Иоффе и В. М. Тихомирова [136] по двойственным задачам в функциональных пространствах. [c.18]
Качественный анализ и методы построения решающих правил и решающих распределений задач стохастического программирования существенно используют утверждения выпуклого анализа, основанные на теоремах Ляпунова, Каратеодори и Хелли, и принципы оптимальности (необходимые условия экстремума) задач выпуклого программирования в функциональных пространствах. Приведем соответствующие утверждения. [c.21]
Таким образом, при принятых допущениях линейная стохастическая задача (1.1) — (1.3) с вероятностными ограничениями сводится к детер минированной задаче выпуклого программирования с линейной делевой функцией и квадратичными условиями-неравенствами [c.67]
Заметим, что при ао<0,5 Ф 1(ао)<0, и целевая функция k (1.18) представляет собой выпуклую вверх функцию компонент вектора х. Задача (1.18) — (1.20) оказывается в этом случае многоэкстремальной. Однако задача максимизации k при условиях (1.19) — (1.20) снова оказывается задачей выпуклого программирования. [c.69]
В настоящей главе обсуждаются методы построения решающих правил для одноэтапных задач стохастического программирования, а для отдельных моделей приводятся и явные выражения для решающих правил. В 1 рассматриваются частные модели первого класса, в которых предполагается, что решающие правила — линейные функции случайных составляющих условий задачи. Вычисление параметров решающих правил сводится к задачам выпуклого программирования. Параграф 2 посвящен изучению. М-модели с вероятностным ограничением общего вида. Относительно решающего правила л (со) не делается никаких предположений, кроме того, что л (со)—измеримая вектор-функция на множестве X произвольной структуры, на котором она определена. В 3 метод построения решающих правил из предыдущего параграфа обобщается на М-модель с конечнозначным ограничением — с условием, ограничивающим математическое ожидание случайной функции от х, принимающей конечное число значений. Таким условием может быть аппроксимировано любое статистическое ограничение. В 4 построены решающие правила (точнее, решающие таблицы) дляч Р-мо-дели с вероятностными ограничениями общего вида. В 5 рассматривается стохастическая задача со смешанными ограничениями. Эта модель отличается от задачи 4 дополнительными условиями, которые могут существенно изменить структуру решения. В 6—8 построены решающие правила для одноэтапных задач стохастического программирования со статистическими ограничениями достаточно общего вида. Модель, изученная в 6, представляет собой стохастический аналог общей задачи линейного программирования с двухсторонними ограничениями. Модель из 7 — стохастический аналог общей задачи квадратичного программирования. Модель, исследованная в 8, является стохастическим аналогом частной задачи выпуклого программирования с квадратичной целевой функцией и квадратичными ограничениями. Заключительный параграф главы ( 9) посвящен итеративным методам построения решающих правил одноэтапных задач стохастического программирования. [c.84]
Каждое из условий вида (1.7) определяет полупространство в пространстве переменных с1ц и z (г=1,. ... т /=1,. . ., п). Пересечение этих полупространств для t=l, 2,. . ., т отвечает выпуклому многогранному множеству. Можно доказать, что при каждом i пара условий вида (1.8), (1.9) высекает в -пространстве переменных da и Zi выпуклое множество. Это множество представляет собой верхнюю (в смысле оси zt) полость двухполостного гиперболоида. Таким образом, условия (1.7) — (1.9) высекают в пространстве переменных da и г выпуклое множество. Мы пришли к задаче выпуклого программирования. Перепишем ее в более компактном виде. Введем обозначения [c.86]
В новых переменных (Sij=tda, Zi = tzit i=l,. .., m j=l,. .., n zo= — tea) задача стохастического программирования (1.16) — (1.18) записывается как следующая детерминированная задача выпуклого программирования [c.88]
При заданых Мць. полученная задача выпуклого программирования может быть решена непосредственно. При отсутствии статистических характеристик случайных параметров условий вычисляем К г и У по после- [c.120]
Вычисление параметров Я, сводится к детерминированной задаче выпуклого программирования с линейной целевой функцией иквадратич- [c.130]
Смотреть страницы где упоминается термин Задача выпуклого программирования
: [c.122] [c.75] [c.144] [c.83] [c.116] [c.111] [c.20] [c.71] [c.87]Приближенное решение задач оптимального управления (1978) -- [ c.373 ]