Выпуклые многогранники и выпуклые многогранные конусы принадлежат к числу наиболее распространенных понятий математической экономики. В линейном и выпуклом программировании используются обязательно выпуклые области изменения переменных (допустимые множества по теоретико-множественной терминологии, многогранники — по геометрической) и выпуклые целевые функции. [c.57]
Выпуклая область 57 Выпуклая оболочка 57 Выпуклая целевая функция 385 Выпуклое программирование 57 Выпуклость 57 Выпуклость функции 57 Выпуклые множества 57 Выпуклые функции 57 Выпуклый многогранник 198 Выпуск (годовое производство) товаров и [c.462]
Рассмотрим стохастический аналог общей задачи квадратичного программирования со строго выпуклой целевой функцией и линейными ограничениями [351] [c.114]
ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ—совокупность методов решения нелинейных экстремальных задач с выпуклыми функциями — раздел нелинейного программирования (т. е. дисциплины, занимающейся решением таких задач, в которых действуют не только линейные, но и другие, более сложные зависимости). Выпуклым этот вид математического программирования называется потому, что име ет дело с выпуклыми целевыми функциями (они минимизируются) и ВЫПУКЛЫМИ системами ограничений. (выпуклость — математический термин. Считается, что область в системе координат является выпуклой, если прямая, соединяющая любые две точки этой области, лежит полностью внутри этой области. Выпуклые функции не имеют перемежающихся подъемов и спусков и. следовательно, лекальных экстремумов и, кроме того, дуга между двумя точками на кривой, выражающей такую функцию, всегда лежит ниже прямой, соединяющей эти точки). [c.117]
У рассматриваемых задач все ограничения линейные. Следовательно, множество допустимых решений выпукло. Целевая функция также выпукла, и ее значение ограничено снизу нулем. Поэтому имеется оптимальное решение. Обозначим входящие в него перемен- [c.137]
Рассматриваемая стохастическая задача при этом преобразуется в детерминированную задачу выпуклого программирования с линейной целевой функцией и квадратичными ограничениями. [c.69]
Задача (3.120) —(3.123) является задачей выпуклого программирования с вогнутой целевой функцией и линейной системой ограничений. [c.85]
Специфика задачи оптимизации транспортировки нефти проявилась также в выборе критерия оптимальности. В качестве последнего принят минимум расхода энергозатрат — важнейшей составляющей себестоимости, зависящей от объема перекачки. Поскольку эта зависимость нелинейна, то в модели задачи целевая функция нелинейна, в частности, кусочно-линейна, выпукла вниз. [c.72]
Если допустимая область ограничена и непуста, то она является выпуклым многогранником, и задача ЗЛП в этом случае всегда разрешима, а оптимальное значение целевой функции достигается, по крайней мере, в одной из вершин многогранника. [c.199]
Названные выше разнообразные дисциплины отличаются друг от друга видом целевой функции fix) и области М. Напр., если fix) линейна, а М— выпуклый многогранник, имеем задачу линейного программирования если же дополнительно ставится условие, чтобы переменные были целочисленными, то имеем задачу целочисленного программирования если зависимость U отд (т.е. форма f) носит нелинейный характер, то задачу нелинейного программирования. [c.187]
В зависимости от вида используемых критериев оптимальности целевых функций или функционалов) и ограничений модели (множества допустимых решений) различают скалярную О., векторную О., многокритериальную О., стохастическую О. (см. Стохастическое программирование), гладкую и негладкую (см. Гладкая функция), дискретную и непрерывную (см. Дискретность, Непрерывность), выпуклую и вогнутую (см. Выпуклость, вогнутость) и др. Численные методы О., т.е. методы построения алгоритмов нахождения оптимальных значений целевых функций и соответствующих точек области допустимых значений,—развитый отдел современной вычислительной математики. См. Оптимальная задача. [c.247]
Проверка оптимальности, вытекающая из сказанного если небольшое передвижение от проверяемой точки уменьшает (для задачи максимизации) целевую функцию (функционал), то это О. Такое правило, однако, относится лишь к выпуклой области допустимых решений. Если она невыпуклая, то данная точка может оказаться лишь локальным О. (см. Градиентные методы). [c.249]
Линейное программирование как научно-практическая дисциплина. Из всех задач оптимизации задачи линейного программирования выделяются тем, что в них ограничения — это системы линейных неравенств или равенств. Ограничения задают выпуклые линейные многогранники в конечном линейном пространстве. Целевые функции также линейны. [c.164]
Симплекс-метод. Это один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Он был предложен американцем Г.Данцигом в 1951 г. Симплекс-метод состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум. [c.170]
Условие (6.15) показывает ограничения на объемы перекачки, в том числе сверху — на пропускную способность соответствующего участка нефтепровода. Формула (6.16) выражает для каждой вершины сети баланс между суммарным поступлением нефти извне системы и от других вершин сети- и суммарным потреблением, включая собственно потребление в самой вершине и перекачку нефти к другим вершинам сети и вне системы. Целевая функция (6.17)—критерий минимизации суммарных энергозатрат перекачки по всей системе. Функции frs(xrs) — кусочно-линейные и выпуклые (вниз). Каждая из них соответствует минимально возможным энергозатратам на перекачку различных объемов нефти по отдельным участкам системы. Строятся функции frs(XrS) по методу огибающей, т. е. находится нижняя граница выпуклой оболочки точек, характеризующих фиксированные режимы работы соответствующих насосных агрегатов и их комбинаций [26]. [c.156]
Запись многих задач стохастического программирования в терминах гильбертова пространства Hin более прозрачна, чем в первичных вероятностных терминах. Ряд естественных для стохастических задач целевых функций оказываются линейными или выпуклыми функционалами в Hin. Некоторые ограничения, используемые в разных постановках задач стохастического программирования, высекают в Htn выпуклые множества. Таким образом, многие задачи стохастического программирования могут рассматриваться как задачи выпуклого программирования в гильбертовом пространстве Н п. [c.20]
Целевой функционал Q(x, у) стохастической транспортной задачи— выпуклая вниз функция переменных yj. Действительно, [c.36]
При сделанных предположениях линейная стохастическая задача (1.1) — (1.3), решение которой определяется в решающих правилах нулевого порядка, сводится к детерминированной задаче выпуклого программирования с линейной целевой функцией и квадратичными ограничениями. [c.66]
Как мы видели, наиболее трудная часть решения двухэтапной задачи стохастического программирования—определение предварительного плана — сводится к решению эквивалентной детерминированной задачи. Доказано, что эквивалентная задача является задачей выпуклого программирования. Однако в общем случае для ее решения стандартные методы выпуклого программирования неприменимы. Дело в том, что как целевая функция, так и область определения планов общей двухэтапной задачи заданы неявно. Показатель качества решения эквивалентной задачи далеко не всегда представляет собой дифференцируемую функцию. Вычисление параметров задачи, используемых в стандартных методах решения выпуклых задач, сопряжено со значительными трудностями. Существующие методы решения двухэтапных задач стохастического программирования используют специфические особенности эквивалентной детерминированной задачи. В настоящем параграфе рассмотрены общие и специальные методы вычисления предварительного плана и некоторые неравенства, позволяющие получить и оценить приближенные решения эквивалентной задачи. Ясно, что во всех частных случаях, в которых удается получить явную запись эквивалентной задачи в виде простой линейной, кусочно-линейной или выпуклой задачи, нет необходимости прибегать к предлагаемым здесь, вообще говоря, трудоемким методам. [c.180]
Другими словами, оператор проектирования у = пн(х) представляет собой решение следующей задачи выпуклого программирования с квадратичной целевой функцией [c.181]
При п= выпуклость S(,bi) следует из теоремы Ляпунова о векторных мерах [189] таким же образом, например, как в [137]. Для справедливости утверждения при п=1 нет необходимости в допущении о выпуклости г 50 и — i >i. При п>1 обеспечение выпуклости 5( п(сои 1)) требует некоторых предположений о структуре целевой функции и ограничений задачи, например выпуклости tyo и — 1 )ь, k 1,. . . , п. [c.209]
При аа 0,5 целевая функция n-.ro этапа выпукла относительно хп-Можно показать, что при тех же условиях функция [c.243]
КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ — раздел выпуклого программирования, при котором целевая функция представляет собой многочлен второй степени, а ограничения линейны. [c.120]
Рассмотрим теперь случай, когда целевые функции владельцев ft (z,-), zt Г> 0 являются выпуклыми. Предположим, что каждый владелец готов полностью обменять ресурсы, находящиеся у него в распоряжении 5,- = Rt, i E / Обозначим [c.336]
Задачи, в к-рых целевая функция / или функции /, ограничений нелинейно зависит от переменных, паз. задачами п е л и н е ii н о г о п р о г р а м м п-]) о в а п п я. Ii ним относятся задачи выпуклого программирования, где функции /к (/ -Н, 1,. . ., ц) — вогнутые, т.е. удовлетворяют при всех ii ((he ii 1) и для любой пары точек х п. / неравенствам [c.407]
Доказано [51], что при выполнении условия (2.3.32) множество допустимых векторов у образует выпуклое множество. Поскольку в целевую функцию (2.3.29) входят только переменные /, то указанное свойство позволяет представить модель (2.3.29) - (2.3.31) как задачу выпуклого программирования относительно только переменных ,. На основе этого свойства можно пытаться строить эффективные алгоритмы решения задачи, гарантируемо приводя- [c.140]
Целевая функция. Функция в экстремальных задачах, минимум или максимум которой необходимо найти, называется целевой. Экстремальному значению целевой функции обычно соответствует оптимальное решение. Различают линейные, нелинейные, выпуклые и другие целевые функции. В том случае, если допустимое множество экстремальной задачи есть пространство функций, тогда используют термин целевой функционал . [c.12]
Доказано, что минимум выпуклой функции на выпуклом множестве точек может быть только один и, следовательно, локальный минимум совпадает с глобальным минимумом. В этом случае возможно сколь угодно точно аппроксимировать (заменять) задачу выпуклого программирования задачей линейного программирования. Для такой аппроксимации в данной задаче нужно заменить кривые / fa) вписанными в них ломаными линиями (рис. 12), а затем преобразовать целевую функцию в линейную, используя уравнения звеньев этих ломаных линий и вводя дополнительные ограничения. Полученная при этом задача линейного программирования имеет точное решение, которое одновременно является приближенным ответом для исходной нелинейной задачи. Разумеется, точность такого ответа будет тем выше, чем точнее кривая аппроксимирована ломаными прямыми линиями. [c.102]
ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ [ onvex programming] — раздел нелинейного программирования, совокупность методов решения нелинейных экстремальных задач с выпуклыми целевыми функциями (они минимизируются) и выпуклыми системами ограничений. (См. Выпуклость, Вогнутость ) [c.57]
Достаточно конструктивные вычислительные алгоритмы и программы для ЦВМ разработаны только для задач линейного и выпуклого программирования. Поэтому целесообразно выделить случаи, в которых можно гарантировать выпуклость целевой функции и области определения детерминированной задачи, эквивалентной той или инойн стохастической постановке. [c.81]
МНОЖИТЕЛИ ЛАГРАНЖА [Lagrange multipliers] — дополнительные множители, преобразующие целевую функцию экстремальной задачи выпуклого программирования (в частности, линейного программирования) при ее решении одним из классических методов — методом разрешающих множителей (методом Л агранжа). Полученная функция носит название лагранжиан, или функция Лагранжа. Подробнее об этом методе см. в ст. "Лагранжиан". [c.202]
РАЦИОНАЛЬНОЕ ЭКОНОМИЧЕСКОЕ ПОВЕДЕНИЕ [e onomi rationality, e onomizing] — поведение экономического объекта (потребителя, производителя, хозяйственной организации и т.п.), которое удовлетворяет некоторым заданным правилам установления предпочтений. Напр., для потребителей — это правила (или аксиомы) транзитивности предпочтений, выпуклости кривых безразличия и др. Для производителя — целевая функция максимизации прибыли, или объема продаж и др., для правительства —целевая функция потребления, социально-экономический критерий оптимальности, [c.302]
Заметим, что множество допустимых решений задачи нелинейного программирования (9.81) может быть пусто, т.е. внутри Vx, например, нет элементов, для которых fi(x) равнялись бы нулю. При этом функция /о (С) не определена в точке С = 0. Однако для построения ova/Q множество V дополняют до его выпуклой оболочки, и на дополнительных участках / (С) считают достаточно малой. При этом oy /Q на этих участках определена. На рис. 9.17 приведен пример функции достижимости и ее выпуклой оболочки. Решение исходной задачи отсутствует, так как для любого х Е Vx функция / не равна нулю. Усредненная задача имеет решение, которому соответствует значение целевой функции, равное " v /g(0). [c.368]
ПРОГРАММИРОВАНИЕ ВЫПУКЛОЕ ( onvex programming) — раздел программирования математического, целевая функция и системы ограничений являются выпуклыми В П в локальный и глобальный экстремумы совпадают Задача П в сводится к отысканию минимума выпуклой вниз ф-ции Ею могут быть, напр, издержки производства [c.202]
Заметим, что при ао<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]
Вычисление параметров Я, сводится к детерминированной задаче выпуклого программирования с линейной целевой функцией иквадратич- [c.130]
Теорема 1.1. Целевая функция Qi(xt) f -го этапа многоэтапной ли-нейной задачи стохастического программирования с условными вероятностными ограничениями является выпуклой вверх функцией на множестве Ki допустимых решающих правил. [c.235]
К М. м. в з. и. относят след, разделы прикладной математики математическое программирование, теорию игр, теорию массового обслуживания, теорию расписании, теорию управления запасами и теорию износа п замены оборудования. М а т е м а т и ч. (или оптимальное) п р о г р а м м н р о в а н и о разрабатывает теорию и методы решения условных экстремальных адач, является осн. частью формального аппарата анализа разнообразных задач управления, планирования и проектирования. Играет особую роль в задачах оптимизации планирования нар. х-ва и управления нронз-вом. Задачи планирования экономики п управления техникой сводятся обычно к выбору совокупности чисел (т. н. параметров управления), обеспечивающих оптимум пек-рой функции (целевой функции пли показателя качества решения) при ограничениях вида равенств и неравенств, определяемых условиями работы системы. В зависимости от свойств функций, определяющих показатель качества и ограничения задачи, математич. программирование делится на линейное и нелинейное. Задачи, и к-рых целевая функция — линейная, а условия записываются в виде линейных равенств и неравенств, составляют предмет линейного программа-ронпии.ч. Задачи, в к-рых показатель качества решения или нек-рые из функций, определяющих ограничения, нелинейны, относятся к н е л и н е и н о м у п р о-г р а м м и [) о н а н п го. Нелинейное программирование, в свою очередь, делится на выпуклое и невынуклое программирование. В зависимости от того, являются лп исходные параметры, характеризующие условия задачи, вполне определёнными числами или случайными величинами, в математич. программировании различаются методы управления и планирования в условиях полной и неполной информации. Методы постановки и решения условных экстремальных задач, условия к-рых содержат случайные параметры, составляют предмет с т о х а с т и ч о с к о г о п р о г р а м м и р о в а- [c.403]