ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ—совокупность методов решения нелинейных экстремальных задач с выпуклыми функциями — раздел нелинейного программирования (т. е. дисциплины, занимающейся решением таких задач, в которых действуют не только линейные, но и другие, более сложные зависимости). Выпуклым этот вид математического программирования называется потому, что име ет дело с выпуклыми целевыми функциями (они минимизируются) и ВЫПУКЛЫМИ системами ограничений. (выпуклость — математический термин. Считается, что область в системе координат является выпуклой, если прямая, соединяющая любые две точки этой области, лежит полностью внутри этой области. Выпуклые функции не имеют перемежающихся подъемов и спусков и. следовательно, лекальных экстремумов и, кроме того, дуга между двумя точками на кривой, выражающей такую функцию, всегда лежит ниже прямой, соединяющей эти точки). [c.117]
Методы решения оптимизационных задач, в которых целевая функция является функцией п переменных, часто называют методами математического программирования. (Термин программирование в данном случае обусловлен тем, что в задачах ищется некоторая программа действий.) В математическом программировании традиционно выделяют следующие основные разделы линейное программирование, целочисленное программирование, выпуклое программирование. [c.185]
Чем удачнее подобрана модель, тем точнее она отражает характерные черты анализируемого процесса, тем достовернее полученные результаты. К построению моделей подходят по-разному используют методы математического программирования (линейное, динамичное, выпуклое, стохастическое), сетевого и матричного планирования, математической статистики (дисперсионный и регрессионный анализы, группировка совокупностей по статистическим критериям) и т.д. [c.33]
Другой математической записью данной задачи, эквивалентной по результату, является ее постановка в виде модели выпуклого программирования (функции ср, выпуклые). [c.199]
Аналогичная по математической постановке задача линейного программирования с переменными вектор-столбцами, заданными на выпуклых множествах, приведена в работе [14]. Показана принципиальная возможность применения декомпозиционной процедуры для данного типа задач. В результате решения определяются как основные переменные, так и значения элементов матрицы условий. Применение принципа декомпозиции для решения задачи линейного программирования с переменными параметрами модели (обобщенная задача линейного программирования) рассмотрено в работах [15, 16]. Особенностью алгоритма является то, что в процессе решения осуществляется одновременный поиск вершин выпуклых многогранников, на которых заданы варьируемые векторы, и значений интенсивностей технологических процессов. [c.15]
Графики и диаграммы незаменимы для иллюстрации результатов экономико-математических методов, которые находят все более широкое применение в экономическом анализе. К ним относятся корреляционный и регрессионный анализ, линейное, динамическое и выпуклое программирование, теории игр и теории массового обслуживания, матричные методы, эвристические методы и др. Об этом более подробно — в следующей главе. [c.72]
Для разработки наилучших стандартпланов работы поточных линий и предметных участков используются различные современные математические методы линейное и выпуклое программирование, метод ветвей и границ и "различные приближенные методы. [c.4]
Выпуклые многогранники и выпуклые многогранные конусы принадлежат к числу наиболее распространенных понятий математической экономики. В линейном и выпуклом программировании используются обязательно выпуклые области изменения переменных (допустимые множества по теоретико-множественной терминологии, многогранники — по геометрической) и выпуклые целевые функции. [c.57]
Заметим, что для непрерывных функций, которые являются дифференцируемыми не во всех точках, также используется понятие выпуклости кривой. Оно возникает, например, в математическом программировании. Здесь не может быть использовано наше определение, использующее понятие касательной (касательной в этом случае может и не быть). Поэтому пользуются другим определением, основанном на понятии хорды. График функции (или сама функция) называется выпуклым (выпуклой) вниз, если каждая дуга кривой лежит не выше своей хорды. График функции (или сама функция) называется выпуклым (выпуклой) вверх, если каждая дуга кривой лежит не ниже своей хорды. [c.164]
В 1—2 рассматриваются стохастические задачи с вероятностными ограничениями, порожденные моделями линейного программирования. В 1 оператор вероятности применяется к каждой строке ограничений в отдельности, а в 2 — одновременно к совокупности всех ограничений. В обоих параграфах рассматриваются такие распределения случайных параметров условий, при которых эквивалентные детерминированные задачи оказываются задачами выпуклого программирования. Параграф 3 посвящен построению эквивалентных детерминированных моделей для общей одноэтапной стохастической задачи с вероятностными ограничениями, порожденной, вообще говоря, нелинейной моделью математического программирования. В 4 рассматриваются две простые, но представляющие интерес для приложений частные модели стохастических задач, в которых решения определяются в детерминированных векторах. Параграфы 5—6 посвящены стохастическим моделям оценки невязок с детерминированными оптимальными планами. В 5 рассматривается классификация таких моделей. В 6 исследуются условия, при которых соответствующие детерминированные эквивалентные задачи являются задачами выпуклого программирования. Ясно, что только в таких случаях можно говорить о конструктивных методах решения задачи. [c.62]
Для вычисления апостериорных решающих правил выпуклых задач стохастического программирования может быть использован любой численный метод выпуклого программирования в гильбертовом пространстве. Для решения стохастических задач могут быть, в частности, использованы методы, изложенные в [218]. Достаточно конструктивным численным методом решения задач математического программирования в функциональных пространствах является метод возможных направлений, обобщенный и обоснованный в [127] для решения бесконечномерных выпуклых задач. [c.123]
Если распределение случайных элементов набора (А, Ь, с) не зависит от х, то для любой пары (А, Ь) норма невязки Ах — Ь и математическое ожидание этой нормы — выпуклые вниз функции х. Следовательно, задача (4.7) является задачей выпуклого программирования и множество Qi — выпуклая область в Rn. В этом случае и задача (4.8), как задача максимизации линейной формы на выпуклом множестве, является задачей выпуклого программирования. [c.269]
Математически — это задачи линейного или выпуклого программирования (см. гл. 8). [c.150]
Математическое программирование — раздел математики. Он изучает методы решения задач на нахождение экстремума функций (показателя качества решения) при ограничениях в форме уравнений и неравенств. Объединяет разные математические методы и дисциплины исследования операций программирование, которое подразделяется на линейное и нелинейное, динамическое и выпуклое, геометрическое и целочисленное и др. [c.510]
Основные понятия линейной алгебры и выпуклого анализа, применяемые в теории математического программирования. Кратко напомним некоторые фундаментальные определения и теоремы линейной алгебры и выпуклого анализа, которые широко применяются при решении проблем как линейного, так и нелинейного программирования. [c.21]
Целевая функция — в экстремальных задачах — функция, минимум или максимум которой требуется найти. Это ключевое понятие оптимального программирования. Найдя экстремум целевой функции и, следовательно, определив значения управляемых переменных, которые к нему приводят, мы тем самым находим оптимальное решение задачи. Таким образом, целевая функция выступает как критерий оптимальности решения задачи. Различается ряд видов целевых функций линейная, нелинейная, выпуклая, квадратичная и др. — в соответствии с формой математической зависимости, которую они отображают. Следует также выделить термин целевой функционал он применяется обычно, если целевая функция задачи является функцией от некоторых функций-ограничений. [c.226]
Поясним содержание данного утверждения. Первые пять пунктов данного утверждения достаточно прозрачны, и являются стандартными свойствами задач математического программирования. В них показано существование решения задачи потребителя и базовые свойства, которым удовлетворяет отображение спроса однородность, выпуклость, выполнение закона Вальраса (в точке оптимума бюджетное ограничение выходит на равенство). Наибольший интерес вызывает свойство под номером 6. Его удобно пояснять в терминах теории выбора, которая подробно будет рассмотрена в дальнейшем. Если в некоторой ситуации потребителю были доступны потребительские наборы ж, ж и был выбран (однозначно ) потребительский набор ж, то тем самым, выбор явно указывает, что набор ж лучше набора ж. Таким образом, если в какой либо другой ситуации рациональный потребитель выбирает набор ж, то, следовательно, набор ж ему не доступен, не удовлетворяет бюджетному ограничению. Данное свойство запрещает ситуацию, когда в двух ситуациях выбора в первой ситуации потребитель своим выбором сигнализирует, что ж >-ж, и в то же время выбирает ж, когда в другой ситуации ему доступны и ж, и ж. [c.58]
Для понимания изложенного достаточно начальных сведений по математическому программированию и теории игр, выпуклому анализу, микро- и макроэкономике. [c.3]
Нелинейные задачи о дополнительности и вариационные неравенства являются обобщением для многих оптимизационных постановок, таких, как задачи математического (нелинейного) программирования, минимаксные задачи и задачи о седловой точке выпукло-вогнутых функций, задачи поиска равновесия в играх п лиц и др. Многие развиваемые для их решения итерационные методы могут быть с успехом применены и к линейным задачам о дополнительности. [c.30]
Третий пример связан с поиском седловых точек выпукло-вогнутых функций (и теми задачами из теории игр и математического программирования, которые сводятся к такому поиску). Пусть X и Y — непустые замкнутые выпуклые подмножества W1 и Rm соответственно, / W1 х Rm —> R — дифференцируемая числовая функция двух векторных аргументов. Седловой точкой функции f(x,y) относительно области X х Y называется пара (х,у) е X х У, удовлетворяющая неравенствам [c.31]
ГЛОБАЛЬНЫЙ МАКСИМУМ [global maximum] — (в общей задаче математического программирования, в задачах линейного программирования, выпуклого про- [c.63]
МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ [mathemati al programming] (см. также Оптимачьное программирование) — раздел математики, который "... изучает методы решения задач на нахождение экстремума функций (показателя качества решения) при ограничениях в форме уравнений и неравенств"40. Оно объединяет различные математические методы и дисциплины исследования операций линейное программирование, нелинейное программирование, динамическое программирование, выпуклое программирование, геометрическое программирование, целочисленное программирование и др. [c.186]
ПРОГРАММИРОВАНИЕ ВЫПУКЛОЕ ( onvex programming) — раздел программирования математического, целевая функция и системы ограничений являются выпуклыми В П в локальный и глобальный экстремумы совпадают Задача П в сводится к отысканию минимума выпуклой вниз ф-ции Ею могут быть, напр, издержки производства [c.202]
Во-вторых, специфика зависимости величины минимума расхода электроэнергии на перекачку от ее объема (в соответствии с принципом 1 это и отображено в критерии оптимальности) такова, что эта зависимость выражается кусочно-линейной выпуклой (вниз) функцией. Это позволило построить точный, быстро сходящийся алгоритм решения задачи, являющейся обобщением метода потенциалов решения сетевой транспортной задачи линейного программирования (СТЗ ЛП) для случая кусочно-линейного выпуклого функционала [41, 47]. Для построения экономико-математической модели задачи введем обозначения г — номер вершины сети 3 (г, s) —дуга сети между вершинами г и s R(E) — множество вершин (дуг) сети Rir(R r< R) [R2t(R2r z zR) подмножество вершин сети, из которых выходят дуги, входящие в r-ю вершину (в которые входят дуги, выходящие из г-й вершины) ur(vr) — объем поступления (потребления) нефти в r-й вершине за плановый период . х — объем перекачки нефти по дуге (г, s) за плановый период ars(Prs) — нижний (верхний) предел значений xrs frs(xrs) — функция зависимости расхода электроэнергии от объема перекачки для дуги (г, s). [c.156]
Исследование многих классов задач стохастического программирования основано на численных методах решения условных экстремальных задач в функциональных пространствах и теории двойственности бесконечномерного математического программирования. В работах по теории и методам стохастического программирования используются результаты С. И. Зуховицкого, Р. А. Поляка и М. Е. Примака [127] по численному решению задач выпуклого программирования в гильбертовых пространствах и работы Е. Г. Голынтейна [79, 80] и А. Д. Иоффе и В. М. Тихомирова [136] по двойственным задачам в функциональных пространствах. [c.18]
Напомним, что фо(ю) называется борелевской функцией, если множества, определяемые неравенства фо(со) А, при любом k являются борелевекими. Борелевская вектор-функция ф( Ш) —это вектор, все составляющие которого борелевские функции. Подчеркнем, что к функции фо( Ш, л) и к составляющим вектор-функции ф(со, л ) не предъявляются обычные для теории двойственности в конечно-мерном математическом программировании требования выпуклости. [c.26]
В настоящей главе обсуждаются методы построения решающих правил для одноэтапных задач стохастического программирования, а для отдельных моделей приводятся и явные выражения для решающих правил. В 1 рассматриваются частные модели первого класса, в которых предполагается, что решающие правила — линейные функции случайных составляющих условий задачи. Вычисление параметров решающих правил сводится к задачам выпуклого программирования. Параграф 2 посвящен изучению. М-модели с вероятностным ограничением общего вида. Относительно решающего правила л (со) не делается никаких предположений, кроме того, что л (со)—измеримая вектор-функция на множестве X произвольной структуры, на котором она определена. В 3 метод построения решающих правил из предыдущего параграфа обобщается на М-модель с конечнозначным ограничением — с условием, ограничивающим математическое ожидание случайной функции от х, принимающей конечное число значений. Таким условием может быть аппроксимировано любое статистическое ограничение. В 4 построены решающие правила (точнее, решающие таблицы) дляч Р-мо-дели с вероятностными ограничениями общего вида. В 5 рассматривается стохастическая задача со смешанными ограничениями. Эта модель отличается от задачи 4 дополнительными условиями, которые могут существенно изменить структуру решения. В 6—8 построены решающие правила для одноэтапных задач стохастического программирования со статистическими ограничениями достаточно общего вида. Модель, изученная в 6, представляет собой стохастический аналог общей задачи линейного программирования с двухсторонними ограничениями. Модель из 7 — стохастический аналог общей задачи квадратичного программирования. Модель, исследованная в 8, является стохастическим аналогом частной задачи выпуклого программирования с квадратичной целевой функцией и квадратичными ограничениями. Заключительный параграф главы ( 9) посвящен итеративным методам построения решающих правил одноэтапных задач стохастического программирования. [c.84]
Гольштейн Е. Г. Двойственные задачи выпуклого и дробновыпуклого программирования в функциональных. пространствах. В кн. Исследования по математическому программированию , М., Наука , 1968. [c.384]
Полтерович В.М. Блочные методы выпуклого программирования и их экономическая интерпретация.— Экономика и математические методы, 1969, т. V, № 6. [c.378]
К М. м. в з. и. относят след, разделы прикладной математики математическое программирование, теорию игр, теорию массового обслуживания, теорию расписании, теорию управления запасами и теорию износа п замены оборудования. М а т е м а т и ч. (или оптимальное) п р о г р а м м н р о в а н и о разрабатывает теорию и методы решения условных экстремальных адач, является осн. частью формального аппарата анализа разнообразных задач управления, планирования и проектирования. Играет особую роль в задачах оптимизации планирования нар. х-ва и управления нронз-вом. Задачи планирования экономики п управления техникой сводятся обычно к выбору совокупности чисел (т. н. параметров управления), обеспечивающих оптимум пек-рой функции (целевой функции пли показателя качества решения) при ограничениях вида равенств и неравенств, определяемых условиями работы системы. В зависимости от свойств функций, определяющих показатель качества и ограничения задачи, математич. программирование делится на линейное и нелинейное. Задачи, и к-рых целевая функция — линейная, а условия записываются в виде линейных равенств и неравенств, составляют предмет линейного программа-ронпии.ч. Задачи, в к-рых показатель качества решения или нек-рые из функций, определяющих ограничения, нелинейны, относятся к н е л и н е и н о м у п р о-г р а м м и [) о н а н п го. Нелинейное программирование, в свою очередь, делится на выпуклое и невынуклое программирование. В зависимости от того, являются лп исходные параметры, характеризующие условия задачи, вполне определёнными числами или случайными величинами, в математич. программировании различаются методы управления и планирования в условиях полной и неполной информации. Методы постановки и решения условных экстремальных задач, условия к-рых содержат случайные параметры, составляют предмет с т о х а с т и ч о с к о г о п р о г р а м м и р о в а- [c.403]
В отличие от задач математического программирования для моделей равновесия условия типа строгой вогнутости функций и строгой выпуклости допустимых множеств не обеспечивают единственности, нужны более ограничительные предположения. Одним из таких предположений является так называемая слабая аксиома выявленного предпочтения (САВП), введенная А. Вальдом и П. Самуэльсоном. Выполнение САВП для некоторой функции спроса С(р) означает справедливость следующей импликации для любых векторов цен р, q из неравенства p (q) < рС(р) следует q (p) > q (q). Иными словами, если стоимость вектора потребления (q) в ценах р не превосходит стоимости вектора С(р), то стоимость вектора С(р) в ценах q больше стоимости (q). Основанием для признания этой аксиомы является следующее рассуждение. Вектор (q) удовлетворяет бюджетному ограничению при ценах р, но потребитель отвергает его и выбирает С(р), выявляя тем самым, что для него С(р) лучше (q). Но при ценах q выбирается вектор (q), значит, в этом случае выбор С(р) невозможен.5 [c.494]
Экономико-математическое моделирование и оптимальное программирование Дескриптивные (описательные), предикат) ные (предсказательные, прогностические нормативные модели системный анализ, машинная имитация линейное, нелинейж динамическое, выпуклое программирован [c.15]