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

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

где x_j – переменные, — заданные функции от п переменных, b_i – фиксированные значения.

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

Графический метод

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

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

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

ОТВЕТ. Глобальный минимум, равный нулю, достигается в точке О(0, 0), глобальный максимум, равный , — в точке

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

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

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

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

ОТВЕТ. Глобальный максимум, равный 52, находится в точке О(0, 0). Глобальный минимум, равный 1053/169, находится в точке Е(51/13б21/13).

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

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

ОТВЕТ. Глобальный минимум, равный нулю, достигается в точке О₁(2, 1), глобальный максимум, равный 13, находится в точке А(0, 4).

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

ОТВЕТ. Целевая функция имеет два глобальных минимума, равных 17, в точках А(1, 4) и В(4, 1), глобальный максимум, равный 2417/49, достигается в точке Е(7, 4/7).

Дробно-линейное программирование

Дробно-линейное программирование относится к нелинейному программированию, так как имеет целевую функцию, заданную в нелинейном виде.

Задача дробно-линейного программирования в общем виде записывается следующим образом:

где — постоянные коэффициенты и

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

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

Из выражения, задающего целевую функцию, найдём х₂:

Прямая x₂ = kx₁ проходит через начало координат. При некотором фиксированном значении L угловой коэффициент k тоже фиксирован, и прямая займёт определённое положение. При изменении значений L прямая x₂ = kx₁ будет поворачиваться вокруг начала координат.

Установим, как будет вести себя угловой коэффициент k при монотонном возрастании L. Найдём производную от k по L:

Знаменатель производной всегда положителен, а числитель от L не зависит. Следовательно, производная имеет постоянный знак, и при увеличении L угловой коэффициент будет только возрастать или только убывать, а прямая будет поворачиваться в одну сторону. Если имеет положительное значение, то прямая вращается против часовой стрелки, при отрицательном значении — по часовой стрелке. Установив направление вращения, находим вершину или вершины многогранника, в которых функция принимает max (min) значение, либо устанавливаем неограниченность задачи.

При этом возможны следующие случаи.

1. Область допустимых решений ограничена, максимум и минимум достигаются в её угловых точках (рис. а).

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

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

4. Область допустимых решений неограниченна. Максимум и минимум являются асимптотическими (рис. г).

Источник

Нелинейное программирование. Постановка общей задачи нелинейного программирования

Нелинейное программирование (NLP, англ. NonLinear Programming) — случай математического программирования, в котором целевой функцией или ограничением является нелинейная функция.

Общая задача нелинейного программирования (ОЗНП) определяется как задача нахождения максимума (или минимума) целевой функции f(x₁, х₂. x_n) на множестве D, определяемом системой ограничений

,где хотя бы одна из функций f или g_i является нелинейной.

По аналогии с линейным программированием ЗНП однозначно определяется парой (D, f) и кратко может быть записана в следующем виде

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

Как и в ЗЛП, вектор х* = (x₁*,x₂*. x_n*) D называется допустимым планом, а если для любого x D выполняется неравенство f(x*) ≥ f(x), то х* называют оптимальным планом. В этом случае х* является точкой глобального максимума.

С точки зрения экономической интерпретации f(x) может рассматриваться как доход, который получает фирма (предприятие) при плане выпуска х, а g_i(х) ≤ 0 как технологические ограничения на возможности выпуска продукции. В данном случае они являются обобщением ресурсных ограничений в ЗЛП (а_iх – b_i ≤ 0).

Задача (2.2) является весьма общей, т. к. допускает запись логических условий, например:

или запись условий дискретности множеств:

Набор ограничений, определяющих множество D, при необходимости всегда можно свести либо к системе, состоящей из одних неравенств:

либо, добавив фиктивные переменные у, к системе уравнений:

Свойства ЗНП, которые существенно усложняют процесс их решения по сравнению с задачами линейного программирования:

1. Множество допустимых планов D может иметь очень сложную структуру (например, быть невыпуклым или несвязным).

2. Глобальный максимум (минимум) может достигаться как внутри множества D, так и на его границах (где он, вообще говоря, будет не совпадать ни с одним из локальных экстремумов).

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

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

Практическая часть Метод Ньютона

Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции.

Чтобы численно решить уравнение f(x)=0 методом простой итерации, его необходимо привести к следующей форме: , где— сжимающее отображение.

Для наилучшей сходимости метода в точке очередного приближения должно выполняться условие. Решение данного уравнения ищут в виде, тогда:

В предположении, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна, окончательная формула длятакова:

С учётом этого функция определяется выражением:

Эта функция в окрестности корня осуществляет сжимающее отображение, и алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:

По теореме Банаха последовательность приближений стремится к корню уравнения .

Рис. 2. – Иллюстрация метода Ньютона (синим изображена функция f(x), нуль которой необходимо найти, красным — касательная в точке очередного приближения x_n).

Источник

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

В оптимизационных задачах нелинейного программирования (НЛП) математические модели содержат нелинейные зависимости от переменных. Источники нелинейности относятся в основном к одной из двух категорий:

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

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

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

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

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

Для задач оптимизации имеются функции Minimize(f, х, у …) и Maximize(f‘, х, у…), решающие задачи минимума и максимума соответственно, где f – оптимизируемая функция, остальные параметры — переменные этой функции.

Пример задачи. Известен рыночный спрос на определенное изделие в количестве 180 штук. Это изделие может быть изготовлено двумя предприятиями по различным технологиям. При производстве первым предприятием его затраты составят руб., а при изготовлении изделий вторым предприятием они составят руб. Определить сколько изделий, изготовленных по каждой технологии, может предложить концерн, чтобы общие издержки его производства были минимальными. Решить задачу средствами Mathcad.

Протокол решения задачи в Mathcad приведен ниже.

Общие затраты на производство

Ответ. На первом предприятии надо произвести 91 изделие, на втором предприятии — 89 изделий.

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

Варианты 1-5. Известен рыночный спрос на определенное изделие в количестве N штук. Это изделие может быть изготовлено двумя предприятиями по различным технологиям. При производстве первым предприятием его затраты составят F руб., а при изготовлении изделий вторым предприятием они составят G руб. Определить сколько изделий, изготовленных по каждой технологии, может предложить концерн, чтобы общие издержки его производства были минимальными.

Источник

1.7. Задача нелинейного программирования и условия существования ее решения

называется задачей нелинейного программирования (ЗНЛП), если целевая функция и (или) функции ограничений и в (1.26) являются нелинейными функциями.

В зависимости от вида целевой функции и системы ограничений (1.26), для решения ЗНЛП применяются различные методы. Перед началом поиска решения задачи желательно знать ответ на принципиальный вопрос о его существовании. Достаточные условия существования решения ЗНЛП с ограничениями даются следующей теоремой.

Теорема Вейерштрасса. Пусть допустимое множество задачи (1.25)-(1.26) является непустым и компактным. Тогда непрерывная целевая функция , определенная на этом множестве, достигает глобального максимума (минимума) на внутренней или граничной точке множества .

На рис. 1.2 показаны различные варианты экстремумов функции на компактном одномерном множестве – отрезке

Рис. 1.2. Графическая иллюстрация условных экстремумов

Условия теоремы Вейерштрасса нетрудно проверить, когда решается ЗНЛП с ограничениями. Если же задача не имеет ограничений, то тогда для ее решения применяют классический метод.

1.8. Задачи

Для указанных ниже функций найти все частные производные первого и второго порядка:

Для указанных ниже матриц определить, используя критерий Сильвестра, являются ли они положительно или отрицательно определенными:

Для указанных ниже функций определить, являются ли они выпуклыми или вогнутыми:

13. . 14. . 15. 16.

17. , если . 18. , если .

19. , если . 20. , если .

22. Найти производную функции в точке по направлению к точке .

23. Найти производную функции в точке по направлению к началу координат.

24. Найти производную функции в начале координат в направлении луча, образующего угол с осью .

25. Найти производную функции в точке по направлению к точке .

Для указанных ниже функций найти их стационарные точки:

Найти градиент и матрицу Гессе следующих функций:

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

44. Найти матрицу Якоби вектор-функции в точке .

45. Найти матрицу Якоби вектор-функции в точке .

46. Найти матрицу Якоби вектор-функции в точке .

47. Найти вектор нормали к гиперплоскости, задаваемой уравнением .

48. Найти вектор нормали к гиперплоскости, задаваемой уравнением .

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

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

Источник