Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Решить и проанализировать задачу нелинейного программирования

Общий вид задач нелинейного программирования

Математическая модель задачи нелинейного программиро­вания в общем виде формулируется следующим образом: найти вектор = 1, x2, …, xn), удовлетворяющий системе ограни­чений и доставляющий экстремум (наибольшее или наименьшее зна­чение) целевой функции: L=f(x1,x2,x3,…xn), где xj переменные, j = ; L, f, gi заданные функции от n переменных, bi — фиксированные значения.

В системе ограничений, уравнения и неравенства, а также и целевая функция могут быть сколь угодной сложности.

Нелинейное программирование применяется при прогнози­ровании промышленного производства, управлении товарными ресурсами, планировании обслуживания и ремонта оборудова­ния и т.д.

Для задачи нелинейного программирования нет единого метода решения.

В зависимости от вида целевой функции и системы ограничений разработаны специальные методы решения, например, такие как:

методы множителей Лагранжа,

квадратичное и выпуклое программи­рование,

приближенные методы реше­ния,

Из нелинейного программирования наиболее разработаны задачи, в которых система ограничений линейная, а целевая функция нелинейная.

Однако даже для таких задач оптималь­ное решение может быть найдено для определенного класса це­левых функций. В отличие от задач линейного программирования, где точками экстремума являются верши­ны многогранника решений, в задачах с нелинейной целевой функцией точки могут находиться внутри многогранника, на его ребре или в вершине.

При решении задач нелинейного программирования для це­левой функции необходимо определить глобальный максимум или глобальный минимум.

Глобальный максимум функции — наибольшее значение из ло­кальных максимумов.

Глобальный минимум функции — наименьшее значение из ло­кальных минимумов.

Наличие локальных экстремумов затрудняет решение за­дач, так как большинство существующих методов нелинейного программирования не позволяет установить, является найден­ный экстремум локальным или глобальным. Поэтому имеется возможность в качестве оптимального решения принять ло­кальный экстремум, который может существенно отличаться от глобального экстремума.

2. Графический метод решения задач нелинейного программирования.

Рассмотрим примеры решения задач нелинейного програм­мирования с двумя переменными, причем их целевые функции и системы ограничений могут быть заданы в линейном и не­линейном виде. Так же как и в задачах линейного программи­рования, они могут быть решены графически.

2.1. Задача с линейной целевой функцией и нелинейной системой ограничений

Пример 1. Найти глобальные экстремумы..

Целевая функция . Ограничения:

Решение. Область допустимых решений — часть окруж­ности с радиусом 4, которая расположена в первой четверти.

Линиями уровня целевой функции являются параллельные прямые с угловым коэффициентом, равным -2.

Глобальный минимум достигается в точке O (0, 0), глобальный максимум — в точке А касания линии уровня и окружности. Проведем че­рез точку А прямую, перпендикулярную линии уровня.

Прямая проходит через начало координат, имеет угловой коэффициент 1/2 и уравнение x2 = 1/2х1.

Решение системы, очевидно:

х1 = 8 /5, x2 = 4 /5, при этом L = 16 /5 + 4 /5 = 4 .

Ответ. Глобальный минимум, равный нулю, достигается в точке O (0, 0), глобальный максимум, равный 4 , — в точке А(8 /5, 4 /5).

2.2. Задача с нелинейной целевой функцией и линейной системой ограничений

Пример 2. Найти глобальные экстремумы.

Целевая функция Ограничения:

Решение. Область допустимых решений – фигура OABD .

Линиями уровня будут окружности с центром в точке O1. Максимальное значение целевая функция имеет в точке D(9, 0), минимальное — в точке O1 (2, 3). Поэтому

Ответ. Глобальный максимум, равный 58, достигается в точке D (9, 0), глобальный минимум, равный нулю, — в точке O1 (2, 3).

3. Метод множителей Лагранжа

Дана задача нелинейного программирования

при ограничениях:

Ограничения заданы в виде уравнений, поэтому для ре­шения задачи воспользуемся методом отыскания условного эк­стремума функции нескольких переменных.

Для решения задачи составляется функция Лагранжа

где λi множители Лагранжа.

Пояснения. Функция Лагранжа есть сумма целевой функции и ограничений, умноженных на множитель, который будет получен при решении системы составленной из частных производных функции Лагранжа

Затем определяются частные производные:

Приравняв к нулю частные производные, получим систему

Решая систему, получим множество точек, в которых целевая функция L может иметь экстремальные значения. Следует отметить, что условия рассмотренной системы являются необходимыми, но недостаточными. Поэтому не всякое полученное решение определяет точку экстремума целевой функции. Применение метода бывает оправданным, когда заранее предполагается существование глобального экстремума, совпадающего с единственным локальным максимумом или минимумом целевой функции.

Пример 8. Найти точку условного экстремума функции

Решение. Составим функцию Лагранжа:

Пояснения. Для составления функции Лагранжа запишем ограничения в виде: q1=x1-x2-2 и q2=x2+2x3-4. Функция Лагранжа есть сумма целевой функции и ограничений, умноженных на множитель, который будет получен при решении системы составленной из частных производных функции Лагранжа.

Найдем частные производные функции Лагранжа по пере­менным x1, x2, x3, λ1, λ2. Приравняв к нулю полученные вы­ражения, решим систему

Определим характер экстремума, изменяя полученные зна­чения переменных.

Измененные значения должны удовлетво­рять заданной системе ограничений.

Возьмем х1 f2(2), т.е. в данный момент оборудование необходимо заменить, так как величина прибыли, получаемая в результате замены оборудования, больше, чем в случае ис­пользования старого. Результаты расчетов помещаем в табли­цу, момент замены отмечаем звездочкой, после чего дальней­шие вычисления по строчке прекращаем (табл. 29.2).

Можно не решать каждый раз уравнение, а вычис­ления проводить в таблице. Например, вычислим f4(t):

Дальнейшие расчеты для f4(t) прекращаем, так как f4(4) = 23

Особенности задач нелинейного программирования

Большинство существующих методов в нелинейном программировании можно разделить на два больших класса:

  1. Прямые методы — методы непосредственного решения исходной задачи. Прямые методы порождают последовательность точек – решений, удовлетворяющих ограничениям, обеспечивающим монотонное убывание целевой функции.
    Недостаток: трудно получить свойство глобальной сходимости.
    Задачи с ограничениями в виде равенств.
    Метод замены переменных (МЗП)
  2. Двойственные методы — методы, использующие понятие двойственности. В этом случае легко получить глобальную сходимость.
    Недостаток: не дают решения исходной задачи в ходе решения – оно реализуемо лишь в конце итерационного процесса.
    • Метод множителей Лагранжа (ММЛ)
    • Методы штрафов
    • Метод множителей
    • Методы линеаризации для задач условной оптимизации
      Алгоритм Франка–Вульфа
      Метод допустимых направлений Зойтендейка
    • Метод условного градиента
    • Метод проекции градиента
    • Сепарабельное программирование.
    • Квадратичное программирование
Читать еще:  Интегрирование это в программировании

Методы поиска нулей функции

  1. Метод Ньютона (Метод касательных)
  2. Метод хорд
  3. Комбинированный метод
  4. Метод итераций
  5. Метод секущих

Методы минимизации функций

Функция одной переменной

Функция двух переменных

  1. Матрица Гессе. . Позволяет ответить на вопрос является ли функция выпуклой или вогнутой, а также определить тип экстремума (минимум или максимум).
  2. Производные второго порядка
  3. Экстремум функции двух переменных.

Методы прямого поиска

  1. Метод Хука–Дживса
  2. Метод сопряженных направлений (метод Пауэлла). Найти минимум целевой функции методом сопряженных направлений: f(x)=3x1 – x1 3 + 3x2 2 + 4x2. x 0 =(0.78;1)

Градиентные методы

  1. Метод наискорейшего спуска (метод Коши).
  2. Метод Ньютона
  3. Метод Марквардта. Найти минимум функции: y=x1 2 +4x2 2 +x1x2+1-5x2 методом Марквардта с начальной точкой (10;10) и εxy= ε|f(x)|=0.5. Предельное число итераций равно M=5.
  4. Метод сопряженных градиентов (метод Флетчера-Ривса).
  5. Метод Бройдена–Флетчера–Гольдфарба–Шанно (квазиньютоновские методы).

Нелинейное программирование

Прямые методы

  1. Метод множителей Лагранжа. В задачах 301-320 используя метод множителей Лагранжа найти точки экстремума функции z=f(x,y) при заданном условии: z=xy+7x , 2x+y=1
  2. Условия Куна-Таккера.

Метод проекции градиента.
Метод условного градиента.

Методы линеаризации для задач условной оптимизации

Методы перебора применимы для отыскания экстремумов унимодальных целевых функций. Действие любого из методов поиска заключается в сужении области поиска экстремума (длины l 0):
а) до области заданной длины (e> 0), проводя минимальное число измерений значений функции (методы дихотомии, золотого сечения);
б) до наименьших возможных размеров ln при заданном числе измерений n (метод Фибоначчи).
Первая формулировка целесообразна в том случае, если с каждым измерением связаны значительные затраты средств или времени, однако на поиск отпускаются неограниченные средства, которые мы все же стремимся минимизировать; вторая – когда исследователь располагает ограниченными средствами и, зная расходы, связанные с каждым измерением, стремится получить наилучший результат.

Классические методы нахождения экстремумов функций предполагают, что целевые функции непрерывные и гладкие. Для существования точки экстремума должны выполняться необходимые и достаточные условия. Необходимыми условиями существования экстремума являются требования обращения в нуль частных производных первого порядка целевой функции по каждой из переменных. Точка, найденная из необходимых условий, называется стационарной (подозрительной на оптимальную). В качестве стационарных точек могут быть точки перегиба, седловые точки и др. Поэтому необходим учет достаточных условий нахождения экстремумов функций. Он сложен для функций многих переменных как в алгебраическом, так и в вычислительном плане. Так в случае функции двух переменных достаточным условием существования экстремума будет положительная определенность матрицы А размером 2×2 (условие Лежандра-Клебша), составленной из вторых частных производных функции. Недостатком классического метода дифференциального исчисления является и то, что он дает возможность найти экстремум только в том случае, если он лежит внутри области определения функции. Если экстремум находится на границе области определения, то этот метод становится бессильным.

Методы покоординатного спуска относятся к группе приближенных методов нелинейной оптимизации и направлены на уменьшение трудностей, связанных с отысканием экстремума функции цели со сложной аналитической структурой классическими методами дифференциального исчисления. Суть этих методов заключается в продвижении от исходной точки в области определения функции к точке оптимума итеративно; в методе Гаусса – последовательно по каждой из переменных (покоординатно); в градиентных методах – одновременно по всем переменным в направлении градиента или антиградиента.

Критерием окончания итеративных процедур является равенство нулю всех частных производных целевой функции, или квадрат суммы всех частных производных целевой функции должен быть не более заданного числа e, или разность достигнутого значения целевой функции и значения в предыдущей точке должна быть не более e и другие.

Решить и проанализировать задачу нелинейного программирования

Задачи математического программирования

max (min) Z = ƒ(x); (6.1)

в которой либо целевая функция (6.1), либо ограничения (6.2), либо и то и другое не линейны, называются нелинейными.

Сложность решения задач нелинейного планирования заключается кроме нелинейности условий задачи еще и в том, что некоторые переменные могут изменяться не непрерывно, а принимать ряд заданных фиксированных значений. Кроме того, сложность решений и в том, что целевые функции могут иметь не один, а несколько максимумов (минимумов), и нужно найти глобальный экстремум.

Геометрическая интерпретация задач нелинейного планирования аналогична задачам линейного планирования.

Общая постановка задачи нелинейного планирования может быть сформулирована следующим образом: найти параметры Х * (х1, х2,…, хп), обращающих целевую функцию W = ƒ(х1, х2,…, хп) в mах(min) при условии наложенных ограничений

число ограничений меньше числа переменных; и (или) целевая функция, и (или) ограничения представляются нелинейными зависимостями.

Нелинейные задачи составляют широкий класс настолько сложных задач, что до сих пор невозможно разработать общие методы, подобные симплекс-методу в линейном программировании, которые позволяли бы решать любые нелинейные задачи. Но, несмотря на отсутствие универсальных методов, разработаны способы решения специальных классов задач, и прежде всего задач с выпуклыми (вогнутыми) функциями ƒ(х) и φi(x).

Особенности решения задач нелинейного программирования.

При решении задач нелинейного программирования очень важно знать: 1) выпукло или не выпукло множество решений? 2) является ли критериальная функция W = ƒ(х) выпуклой или вогнутой, или не относится ни к тому, ни к другому классу?

Множество выпукло, если оно содержит точки А и В, а так же все точки прямой АВ.

Функция у = ƒ(х), определенная на выпуклом множестве Х, называется выпуклой, если отрезок, соединяющий любые две его точки, принадлежит графику или располагается выше его (рис. 6.1. а). Функция у= ƒ(х), определенная на выпуклом множестве Х, называется вогнутой, если отрезок, соединяющий любые две его точки, принадлежит графику или располагается ниже его (рис. 6.1. б).

Аналогичные понятия можно привести и для функций многих переменных.

В математике доказывается ряд теорем, которые позволяют определять глобальные экстремумы. Так, для задач, в которых множество допустимых решений выпукло: 1) если ƒ(х) – выпуклая функция, то локальный минимум, определенный на выпуклом множестве Х, совпадает с ее глобальным минимумом на этом множестве; 2) если ƒ(х) – вогнутая функция на заданном выпуклом множестве Х, то локальный максимум ƒ(х) является глобальным.

Читать еще:  Электрически стираемое перепрограммируемое пзу

Решение задач линейного программирования симплекс-методом Калькулятор онлайн

Симплексный метод является универсальным методом решения оптимизационных задач. За исходное решение берётся одно из возможных базисных решений (или «план», «программа»). Затем эта программа улучшается до тех пор, пока не будет найдена оптимальная программа. Наш калькулятор онлайн позволяет решать задачи как на максимум целевой функции, так и на минимум. При решении задач на минимум исходная задача линейного программирования сводится к двойственной задаче. При выполнении этих операций на бумаге часто возникают ошибки, а наш калькулятор онлайн поможет своевременно проверить ошибки.

Симплекс метод онлайн

Вычисление происходит за время немногим более секунды. Этот калькулятор находит максимум целевой функции. Если требуется найти минимум целевой функции, то следует воспользоваться калькулятором Решение двойственной задачи линейного программирования.

Как онлайн калькулятор находит решение задачи линейного программирования?

Он выдаёт шаги решения задачи симплекс методом, на которых преобразуется система ограничений и целевая функция. Это значит, что на соответствующем шаге функция цели не принимает оптимального значения и по определённому правилу совершается переход от одной вершины многогранника решений к другой пока функция цели не примет оптимального значения. По шагам решения можно наблюдать, как переменные, которые входят в выражение целевой функции с коэффициентом 0, являются неосновными, а остальные — основными. Таким образом осуществляется перевод переменных в основные и неосновные.

Материалы по теме Линейное программирование

Поделиться с друзьями

Введите данные вашей задачи, и вы получите подробное решение.
Используются лучшие онлайн-калькуляторы интернета.

Математический анализ

Предел

Производная

Производная функции от одной переменной

Производная функции от двух переменных

Производная функции от трех переменных

Производная параметрической функции

Вторая и третья производные

Интеграл

Разложение дроби на сумму элементарных дробей (для метода неопределнных коэффициентов)

Построение графиков

Построение графика функции (2D) в декартовых координатах

Построение графика функции в полярных координатах

Построение графика функции, заданного параметрически

Построение поверхности (3D)

Сумма числового ряда(см. пример…)

Разложение в ряд Фурье

Дифференциальные уравнения:

Линейное однородное уравнение

Линейное неоднородное уравнение

Уравнение в полных дифференциалах

Линейное однородное уравнение второго порядка с постоянными коэффициентами

Линейное однородное уравнения 2-го порядка вида ay»+by’+cy=0 с начальными условиями

Линейное неоднородное уравнение второго порядка с постоянными коэффициентами

Векторная алгебра и аналитическая геометрия

Пирамида. Задача расчета параметров пространственной пирамиды по координатам вершин. Позволяет найти длины ребер, площади граней, объем пирамиды, длины высот, углы между ребрами, углы между гранями, углы между ребрами и гранями.

Получить уравнение прямой по двум точкам

Получить уравнение плоскости по трем точкам

Разложение вектора по базису

Линейная алгебра

Матрицы

Разложение определителя по строке или столбцу

Обратная матрица (метод алгебраических дополнений)

Обратная матрица (метод присоединенной матрицы)

Характеристическое уравнение матрицы

Собственные значения (числа)

Возведение матрицы в степень

Приведение матрицы к треугольному виду

Системы уравнений

Решение системы линейных уравнений методом Крамера

Решение системы линейных уравнений методом Гаусса

Решение системы линейных уравнений методом обратной матрицы (матричный метод)

Любая система уравнений

Теория вероятностей и математическая статистика

Биномиальное распределение: расчет Pn(k) при данных p и n

Гистограмма: группировка результатов эксперимента, подсчет частот

Обработка выборки (простой статистической совокупности) — будут построены: статистические ряды частот, полигоны частот, гистограмма, функция распределения, найдены точечные оценки математического ожидания и дисперсии.

Особенности задач нелинейного программирования

Обработка группированного ряда абсолютных частот — будут построены: статистические ряды относительных частот, полигоны частот, гистограмма, функция распределения, найдены точечные оценки математического ожидания и дисперсии. ( см.пример…)

и – функции, непрерывные вместе со своими частными производными. Ограничения в задаче заданы уравнениями, поэтому для ее решения можно воспользоваться классическим методом отыскания условного экстремума функций нескольких переменных. Вводят набор переменных , называемых множителями Лагранжа, и составляют функцию Лагранжа

находят частные производные

и рассматривают систему n + m уравнений

(15.3)

с n + m неизвестными , . Решив систему уравнений (15.3), получают все точки, в которых функция (15.1) может иметь экстремальные значения.

решение задачи нелинейного программирования онлайн

Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума. Метод множителей Лагранжа имеет ограниченное применение, так как система (15.3), как правило, имеет несколько решений.

Пример. Найти точку условного экстремума функции при ограничениях

Составим функцию Лагранжа:

Продифференцируем ее по переменным . Приравнивая полученные выражения к нулю, получим следующую систему уравнений:

Из второго и третьего уравнений следует, что ; тогда

Решив данную систему, получим:

и

Задачи нелинейного программирования

Лекция 16

Нелинейное программирование – раздел математического программирования, изучающий методы решения экстремальных задач с нелинейной целевой функцией и (или) областью допустимых решений, определенной нелинейными ограничениями. К нелинейному программированию относят квадратичное, дробное, выпуклое, дискретное, целочисленное и геометрическое программирование.

В общем виде задачу нелинейного программирования можно сформулировать так:

где х – вектор искомых переменных; F(х) — целевая числовая функция; g(x) – вектор-функция системы ограничений.

При этом могут быть разные случаи:

1) целевая функция – нелинейная, а ограничения – линейны;

2) целевая функция – линейная, а ограничения (хотя бы одно из них) – нелинейные;

3) целевая функция и ограничения нелинейные.

Задачи условной оптимизации нелинейного программирования бывают двух типов: когда в ограничениях (2) имеют место:

а) знаки равенства;

б) знаки неравенства.

Решение задачи нелинейного программирования (поиск глобального минимума или максимума) состоит в отыскании таких значений переменных, подчиненных системе ограничений, при которых достигает минимума или максимума данная целевая функция.

При решении некоторых нелинейных задач иногда удается использовать линейную теорию. Для этого вводят допущение, что на том или ином участке целевая функция возрастает или убывает пропорционально изменению переменных. Такой подход называется методом кусочно-линейных приближений.

Читать еще:  Задачи математического программирования делятся на

Среди большого числа вычислительных алгоритмов нелинейного программирования значительное место занимают:

— различные варианты градиентных методов (метод проекции градиента, метод условного градиента и т. п.);

— методы штрафных функций;

— методы барьерных функций;

— метод модифицированных функций Лагранжа и др.

Нелинейные задачи с ограничениями в форме равенств нередко решаются с помощью введения функции Лагранжа:

где L(x, λ) — лагранжиан; φ(x) — целевая функция; λi (i = 1, 2, . k) – множители Лагранжа; k — число ограничений gi(x).

Универсального метода, позволяющего находить наиболее эффективным способом решение любой нелинейной задачи, не существует. Поэтому для каждой конкретной задачи, учитывая ее специфику, подбирают тот или иной наиболее подходящий метод (и алгоритм) решения.

Задачи нелинейного программирования на практике возникают довольно часто, например, когда затраты растут непропорционально количеству закупленных или произведенных товаров. Хорошо известно, что чем больше партия закупаемого товара, тем меньше стоимость единицы продукта. Каждому знакомо понятие розничных и оптовых цен.

Рассмотрим частный случай общей задачи нелинейного программирования (1), предполагая, что система ограничений (2) содержит только уравнения, отсутствуют условия неотрицательности переменных, F(х) и g(x) – функции, непрерывные вместе со своими частными производными. Ограничения в задаче заданы уравнениями, поэтому для ее решения можно воспользоваться классическим методом отыскания условного экстремума функций нескольких переменных. Вводят набор переменных, называемых множителями Лагранжа, и составляют функцию Лагранжа:

находят частные производные

и рассматривают систему n + m уравнений:

с n + m неизвестными , . Решив систему уравнений (3), получают все точки, в которых функция (1) может иметь экстремальные значения. Метод множителей Лагранжа имеет ограниченное применение, так как система (3), как правило, имеет несколько решений.

Пример. Найти точку условного экстремума функции при ограничениях:

Составим функцию Лагранжа:

Продифференцируем ее по переменным . Приравнивая полученные выражения к нулю, получим следующую систему уравнений:

Из второго и третьего уравнений следует, что ; тогда

Геометрическая интерпретация задачи нелинейного программирования

Геометрический способ решения задачи нелинейного программирования

В евклидовом пространстве Еn система ограничений gi (x1, x2, . xn)=bi, i=1, 2, . k, определяет область допустимых решений задачи (ОДР). В отличие от ЗЛП она не всегда является выпуклой.

Если определена ОДР, то нахождение решения задачи сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня: f (x1, x2, . xn)=h. Указанная точка может находиться как на границе ОДР, так и внутри нее.

Если в ЗЛП точки экстремума являются вершинами многогранников решений, то в задачах с нелинейной целевой функцией они могут лежать внутри области, на ребре (грани) или в вершине многогранника. Таким образом, с помощью методов линейного программирования, позволяющих осуществить переход из одной вершины многогранника в другую, можно получить оптимальное решение нелинейных задач при условии, что целевая функция удовлетворяет добавочным ограничениям.

Рассмотрение ЗНЛП начинают с классической задачи оптимизации. Задачи такого рода имеют место, если система (3.2) содержит только уравнения, отсутствуют условия не отрицательности и цело численности переменных, а функции gi (x1, x2, . xn) и f (x1, x2, . xn) непрерывны и имеют частные производные не ниже второго порядка. Классические методы оптимизации при этом являются теоретическим аппаратом, позволяющим в ряде случаев обосновать разработку соответствующего вычислительного метода.

Глобальный (абсолютный) и локальный экстремум функции

Т . Любой локальный максимум (минимум) задачи выпуклого программирования является глобальным максимумом (минимумом).

Условный экстремум функции

Метод неопределенных множителей Лагранжа.

Функцией Лагранжа задачи выпуклого программирования (3.3) — (3.5) называется функция

Метод множителей Лагранжа имеет ограниченное применение, т. к. система , как правило, имеет несколько решений. Нелинейное программирование как новая математическая дисциплина возникла главным образом в связи с указанной ограниченностью метода множителей Лагранжа.

Таким образом, определение экстремальных точек задачи методом множителей Лагранжа включает следующие этапы:

1. Составление функции Лагранжа.

2. Нахождение частных производных от функции Лагранжа по переменным xj и li и приравнивание их к нулю.

3. Решая систему уравнений находят точки, в которых целевая функция задачи может иметь экстремум.

4. Среди точек, подозрительных на экстремум, находят такие, в которых достигается экстремум, и вычисляют значение функции в этих точках.


54. Определение выпуклой и вогнутой функции

Точка А, для которой выполняются условия (2.44) и (2.45), называется выпуклой линейной комбинацией точек А1 и А2. Множество называется выпуклым, если вместе с любыми двумя своими точками оно содержит и их произвольную выпуклую линейную комбинацию. Геометрический смысл этого определения состоит в том, что множеству вместе с его двумя произвольными точками полностью принадлежит и прямолинейный отрезок, их соединяющий.

Общая постановка задачи выпуклого программирования. Теорема о существовании решения задачи ВП (формулировка)

Рассмотрим задачу нелинейного программирования:

Для решения сформулированной задачи в такой общей постановке не существует универсальных методов. Однако для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функций f и gi, разработаны эффективные методы их решения. В частности, ряд таких методов имеется для решения ЗНЛП (3.3) — (3.5) при условии, что f — вогнутая (выпуклая) функция и ОДР, определяемая ограничениями (3.4) — (3.5), — выпуклая.

Функция f(x1, x2, . xn), заданная на выпуклом множестве X, называется выпуклой, если для любых двух точек X1 и X2 из X и любого 0£l£1 выполняется соотношение

Функция f(x1, x2, . xn), заданная на выпуклом множестве X, называется вогнутой, если для любых двух точек X1, X2 из X и любого 0£l£1 выполняется соотношение

Если f (X) — выпуклая функция, то –f (X) — вогнутая функция, и наоборот.

Сумма выпуклых (вогнутых) функций есть выпуклая (вогнутая) функция. Задача (3.3) — (3.5) является задачей выпуклого программирования, если функция f(x1, x2, . xn) является вогнутой (выпуклой), а функции gi (X) (i=1, . m) — выпуклыми.

Т е о р е м а. Любой локальный максимум (минимум) задачи выпуклого программирования является глобальным максимумом (минимумом).

Говорят, что множество допустимых решений задачи (3.3) — (3.5) удовлетворяет условию регулярности, если существует по крайней мере одна точка Xi, принадлежащая ОДР такая, что gi (Xi)

Дата добавления: 2018-05-12 ; просмотров: 568 ;

Ссылка на основную публикацию
Adblock
detector