Математическое программирование — раздел математики. Он изучает методы решения задач на нахождение экстремума функций (показателя качества решения) при ограничениях в форме уравнений и неравенств. Объединяет разные математические методы и дисциплины исследования операций программирование, которое подразделяется на линейное и нелинейное, динамическое и выпуклое, геометрическое и целочисленное и др. [c.510]
Напомним, что функция называется выпуклой, если для любой пары точек xi и х% из области ее определения (которая предполагается выпуклой) и для всех чисел А,, 0 А < 1 выполняется неравенство / (kxi + (1 — A,) ia) < A,/ (n) -f (1— ) / (xi) График такой функции изображен на рис. 11. [c.102]
Рассмотрим вопрос об условиях, достаточных для того, чтобы множество допустимых значений X, описываемое соотношениями (3.8), было выпуклым. Этот вопрос решается на основе введения понятия выпуклой функции. Функция g(x), где х е Еп,- называется выпуклой вниз (или просто выпуклой), если для любых значений х и ж и при любом числе ос, изменяющемся от нуля до единицы, выполнено неравенство [c.34]
А Действительно, из (с, х) 0 следует справедливость неравенства (ас, х) = (с, ах) 0 для любого положительного множителя а. Значит, L — конус. Убедимся, что это выпуклый конус. С этой целью возьмем две произвольные точки х и х" конуса L. Для них выполнены неравенства с,х ) 0 и (с, х") 0. Умножим первое неравенство на произвольное число X е [0,1], а второе — на 1 - X. Складывая почленно полученные неравенства, придем к неравенству Х(с,х + (1 - Х) с,х") = с,Хх + (1 -- Х)х") 0, устанавливающему выпуклость конуса Z,.v [c.53]
Множество всех оптимальных решений ЗЛП выпукло. Если допустимая область образована п неравенствами х. > О, j = , n и т [c.199]
Теоретически возможность абсолютного равенства распределения доходов представлена биссектрисой, которая указывает на то, что любой данный процент населения получает соответствующий процент дохода (т.е. 20% населения получают 20% дохода, 40% населения — 40% дохода и т. д.). Кривая Лоренца демонстрирует фактическое распределение дохода и используется для сравнения степени неравенства в различные периоды между различными группами населения или странами. График демонстрирует изменение степени неравенства доходов населения РФ в 1990—99 гг. при этом ясно видно усиление расслоения населения по доходам — кривая стала более выпуклой, а пространство между воображаемой линией всеобщего равенства (биссектрисой) и реальным распределением доходов увеличилось. [c.72]
Далее, ф строго выпукла на S тогда и только тогда, когда неравенство (3) строгое для всех х ф у S. [c.171]
Так как система неравенств (9.3) в случае непротиворечивости экспертных оценок совместна, задача минимизации имеет решение, и это решение единственно в силу строгой выпуклости функции R и, следовательно, функции D. [c.353]
Пусть в банаховом пространстве В задан выпуклый ограниченный функционал-гро( ) и выпуклое множество X, определяемое системой неравенств [c.22]
Заметим, кроме того, что не все задачи выпуклого программирования приспособлены к использованию ряда известных эффективных методов решения. Применение таких методов выпуклого программирования, как методы возможных направлений, метод секущих плоскостей и других методов, связанных с вычислением градиентов функций, определяющих ограничения задачи, предполагает выпуклость каждой из этих функций в соответствующую сторону (в зависимости от знака неравенства). [c.70]
Согласно теореме 2.2 гл. 6 для общей двухэтапной задачи множество К предварительных планов выпукло. Для рассматриваемого частного случая можно доказать более сильное утверждение. Оказывается, что в этом случае множество К не только выпуклое, но и многогранное. Более того, удается явно записать систему линейных неравенств, определяющих множество К. [c.168]
Как мы видели, наиболее трудная часть решения двухэтапной задачи стохастического программирования—определение предварительного плана — сводится к решению эквивалентной детерминированной задачи. Доказано, что эквивалентная задача является задачей выпуклого программирования. Однако в общем случае для ее решения стандартные методы выпуклого программирования неприменимы. Дело в том, что как целевая функция, так и область определения планов общей двухэтапной задачи заданы неявно. Показатель качества решения эквивалентной задачи далеко не всегда представляет собой дифференцируемую функцию. Вычисление параметров задачи, используемых в стандартных методах решения выпуклых задач, сопряжено со значительными трудностями. Существующие методы решения двухэтапных задач стохастического программирования используют специфические особенности эквивалентной детерминированной задачи. В настоящем параграфе рассмотрены общие и специальные методы вычисления предварительного плана и некоторые неравенства, позволяющие получить и оценить приближенные решения эквивалентной задачи. Ясно, что во всех частных случаях, в которых удается получить явную запись эквивалентной задачи в виде простой линейной, кусочно-линейной или выпуклой задачи, нет необходимости прибегать к предлагаемым здесь, вообще говоря, трудоемким методам. [c.180]
В общем случае при постановке задачи о сглаживании и прогнозе случайных процессов исключение систематических ошибок экстраполяции (равенство нулю первого момента ошибок упреждения) не является обязательным и тем более единственным требованием рациональной фильтрации или рационального прогнозирования. Больше того, в ряде случаев целесообразно расширить область определения задачи и заменить требование о нулевых систематических ошибках ограничениями на их величину. Могут быть указаны и другие неравенства и логические соотношения, которым в тех или иных содержательных задачах фильтрации и прогноза должны удовлетворять, сглаженные или упрежденные точки. Например, может быть ограничена дисперсия или корреляционные моменты случайных величин, зависящих от г (/о + п) и (М- Можно указать содержательные постановки, в которых область определения задачи естественно задавать вероятностными или жесткими ограничениями. Таким образом, в общем случае ограничения задачи сглаживания и экстраполяции высекают в Я не линейное подпространство и не линейное многообразие, а некоторую выпуклую или невыпуклую область G. [c.309]
Таким образом, решение задачи стохастического программирования— задачи сглаживания и упреждения по минимуму второго момента ошибок при любых ограничениях, высекающих выпуклую область в гильбертовом пространстве Я, сводится к решению неравенства (3.13). [c.310]
Второй аргумент в пользу перераспределения доходов в обществе носит макроэкономический характер — это существование определенной взаимосвязи между уровнем социального неравенства и темпами экономического роста. По сути, этот аргумент несколько противоречив и используется и сторонниками, и противниками процессов перераспределения. С одной стороны, чем менее интенсивный характер носят перераспределительные процессы, тем сильнее стимулирование индивидов к производительному труду, которое проявляется в возможности получения ими высоких реальных доходов. В этом смысле неравенство — это цена, которую общество вынуждено платить за эффективную экономическую систему и стабильный экономический рост. Однако слишком высокий уровень неравенства приводит, напротив, к снижению экономического роста в стране (т. е. между неравенством и темпами экономического роста существует взаимосвязь в форме выпуклой вверх параболы — с ростом неравенства происходит увеличение темпов экономического роста только до определенного уровня, начиная с которого при дальнейшем увеличении неравенства темпы экономического роста снижаются). Поэтому целесообразно регулировать неравенство путем проведения политики перераспределения и не допускать слишком высокий его уровень. [c.342]
Таким образом, функция f(x), заданная на выпуклом множестве, выпукла вниз, если она обладает следующим свойством для любых двух чисел хг и х2 из области определения функции и любого числа А, из отрезка [О, 1 ] выполняется неравенство (3). [c.573]
Аналогично можно определить и функции, выпуклые вверх для этого нужно знаки неравенства (3) и (4) заменить на противоположные. Функции, выпуклые вниз, часто называют просто выпуклыми . Выпуклые функции обладают свойством более общим, чем не- [c.574]
Аналогично можно определить и функции, выпуклые вверх для этого нужно знаки неравенства (3) и (4) заменить на противоположные. [c.187]
Если при z1 Ф z" и при Х= 0и = 1в (12.1) имеет место строгое неравенство, то функция р называется строго выпуклой, [c.118]
Применяя к выпуклой функции Н(х, ) и мере Y неравенство (21.1), мы получаем при любом х Е х [c.136]
МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ [mathemati al programming] (см. также Оптимачьное программирование) — раздел математики, который "... изучает методы решения задач на нахождение экстремума функций (показателя качества решения) при ограничениях в форме уравнений и неравенств"40. Оно объединяет различные математические методы и дисциплины исследования операций линейное программирование, нелинейное программирование, динамическое программирование, выпуклое программирование, геометрическое программирование, целочисленное программирование и др. [c.186]
Поэтому, если нам удастся показать, что t2 < w l -f w2tl, мы докажем, что вторая производная облигации 1 меньше, чем вторая производная для облигации 2. Это следует из неравенства Иенсена и того, что t2 — выпуклая функция. Неравенство Йенсена утверждает, что если /(х) — строго выпуклая функция, то /( Xi + (1 — а)х2) < < J(x ) + (1 — a)f(xy). Обозначив а = 7i, I — a = №2Hi = i, получим требуемый результат. [c.29]
К М. м. в з. и. относят след, разделы прикладной математики математическое программирование, теорию игр, теорию массового обслуживания, теорию расписании, теорию управления запасами и теорию износа п замены оборудования. М а т е м а т и ч. (или оптимальное) п р о г р а м м н р о в а н и о разрабатывает теорию и методы решения условных экстремальных адач, является осн. частью формального аппарата анализа разнообразных задач управления, планирования и проектирования. Играет особую роль в задачах оптимизации планирования нар. х-ва и управления нронз-вом. Задачи планирования экономики п управления техникой сводятся обычно к выбору совокупности чисел (т. н. параметров управления), обеспечивающих оптимум пек-рой функции (целевой функции пли показателя качества решения) при ограничениях вида равенств и неравенств, определяемых условиями работы системы. В зависимости от свойств функций, определяющих показатель качества и ограничения задачи, математич. программирование делится на линейное и нелинейное. Задачи, и к-рых целевая функция — линейная, а условия записываются в виде линейных равенств и неравенств, составляют предмет линейного программа-ронпии.ч. Задачи, в к-рых показатель качества решения или нек-рые из функций, определяющих ограничения, нелинейны, относятся к н е л и н е и н о м у п р о-г р а м м и [) о н а н п го. Нелинейное программирование, в свою очередь, делится на выпуклое и невынуклое программирование. В зависимости от того, являются лп исходные параметры, характеризующие условия задачи, вполне определёнными числами или случайными величинами, в математич. программировании различаются методы управления и планирования в условиях полной и неполной информации. Методы постановки и решения условных экстремальных задач, условия к-рых содержат случайные параметры, составляют предмет с т о х а с т и ч о с к о г о п р о г р а м м и р о в а- [c.403]
Из нелинейных задач выделяются задачи выпуклого программирования. В этих задачах вычисляется максимум вогнутой функции на выпуклом множестве1. Решение задач выпуклого программирования значительно упрощается, если исходные условия (ограничения) представлены в виде линейных равенств и неравенств. К числу подобных задач относятся задачи квадратического программирования. [c.164]
Заметим, что Th o) и Тс(уо-Ах0) выпуклые и замкнутые конусы в А. В первую очередь рассмотрим тот случай, когда q ё Т .(у0 — Ах0). Тогда для такого q X можно выбрать элемент w=w(q)<=T (yQ-AxQ), такой, что
Так как feQ, Jy-jJ O. Учитывая положительность г, убеждаемся в противоречивости неравенства (86). Это и означает включение q e FrQ. Кроме того, отображение X -> Е U -ню выпукло и конечнозначно на Q, следовательно, е int/ЭотпЩ. Согласно хорошо известному факту [15], отображение Щ X -> Е U +< субдифференцируемо в точке q e FrQ. Это означает, что [c.186]
Математически это требование формулируется следующим образом / (х) — вогнутая (выпуклая вверх) функция своих аргументов на неотрицательном ортанте. Напомним, что функция называется вогнутой на множестве X, если для любых двух точек (векторов) xt и л 2 из множества X и любого числа а е [О, 1] справедливо неравенство [c.93]
Часто вместо условия (2.13) формулируется более сильное математическое требование, близкое к (2.13). по смыслу f(x) — вогнутая (выпуклая вверх) функция своих аргументов на неотрицательном ортанте, т. е. для любых двух неотрицательных векторов х и х и любого числа a tO, 11 справедливо неравенство [c.73]
Для того чтобы решение было единственным, достаточно выпуклости функции Лагранжа R исходной неусредненной задачи по вектору Р. Вследствие сепарабельной структуры этой функции условия постоянства оптимального вектора цен, а, следовательно, потоков д и д2 (условия нецелесообразности складов) принимают форму неравенств [c.287]
Из теоремы 14 вытекает, что (ац,. . . , ann) мажорируется (Ai,. . . , Лп) в смысле 16. Тогда неравенство Карамата (теорема 19) приводит к (1). Для строго выпуклой ф из теоремы 19 следует, что равенство в (1) выполняется в том и только том случае, когда Л = ац для г = 1,. . . , гг, а по теореме 1.30 это может быть только в случае, когда Л диагональна. П [c.277]
Напомним, что фо(ю) называется борелевской функцией, если множества, определяемые неравенства фо(со) А, при любом k являются борелевекими. Борелевская вектор-функция ф( Ш) —это вектор, все составляющие которого борелевские функции. Подчеркнем, что к функции фо( Ш, л) и к составляющим вектор-функции ф(со, л ) не предъявляются обычные для теории двойственности в конечно-мерном математическом программировании требования выпуклости. [c.26]
Таким образом, при принятых допущениях линейная стохастическая задача (1.1) — (1.3) с вероятностными ограничениями сводится к детер минированной задаче выпуклого программирования с линейной делевой функцией и квадратичными условиями-неравенствами [c.67]
Проще всего определить выпуклую функцию геометрически. Для этого полезно ввести понятие надграфика функции. Надграфиком функции называется множество точек, расположенных над графиком функции и на самом графике. Более строго, надграфик функции f(x) — это множество таких точек, координата х которых лежит в области определения функции, а координата у удовлетворяет неравенству у > f(x). [c.572]
Выпуклость функций в а) и б) проверяется непосредственно с помощью неравенства (3) или (4). Функция в) при каждом х принимает значение, равное большему из значений f(x) и g(x) (и любому из них, если они равны). Надграфик функции max(/(x), g(x)) есть пересечение надграфиков функций f(x) и g(x) (проверьте ) — отсюда и выпуклость функции в). [c.575]