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

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. Решение задачи нелинейного программирования без ограничений

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

Источник

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

где 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. Область допустимых решений неограниченна. Максимум и минимум являются асимптотическими (рис. г).

Источник

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

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

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

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

Вы найдете подробные примеры решений по этой теме — изучайте, ищите похожие, решайте. Если вам нужна помощь в выполнении заданий, перейдите в раздел: Контрольные работы по линейному программированию.

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

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

$$ \max(-6x_1^2-x_2^2+2x_1x_2+10x_2)\\ 2x_1+x_2 \le 5,\\ 2x_1+x_2 \ge 2,\\ x_1,x_2 \ge 0,\\ x_0=(0,4). $$

Задача 2. Решить задачу методом Франка-Вульфа (расчеты вести с точностью до 4 знаков после запятой).

$$ \max(-x_1^2+x_1x_2 -2x_2^2+4x_1+6x_2)\\ x_1+x_2 \le 4,\\ x_1+2x_2 \ge 2,\\ x_1,x_2 \ge 0,\\ x_0=(3,1). $$

Задача 3. Решить задачу методом возможных направлений (расчеты вести с точностью до 4 знаков после запятой).

$$ \max(-x_1^2+x_1x_2 -2x_2^2+4x_1+6x_2)\\ x_1+x_2 \le 4,\\ x_1+2x_2 \ge 2,\\ x_1,x_2 \ge 0,\\ x_0=(3,1), \xi=0,4. $$

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

$$ \min f =x_1^2+2x_2^2-16x_1-20x_2,\\ 2x_1+5x_2 \le 40,\\ 2x_1+x_2 \le 16,\\ x_1,x_2 \ge 0. $$

Задача 5. Используя графический метод, найдите решение задачи нелинейного программирования

$$ F =(x_1-1)^2+(x_2-1)^2 \to extr,\\ 3x_1+5x_2 \le 15,\\ 5x_1+3x_2 \le 15,\\ x_1,x_2 \ge 0. $$

Задача 6. Для следующей задачи нелинейного программирования $$ F=3/2x_1^2+1/2x_2^2-x_1x_2-12x_1+2x_2 \to \min,\\ 4x_1+3x_2 \ge 12,\\ x_1+3x_2\le 6,\\ x_1,x_2 \ge 0. $$ a) доказать, что функция является выпуклой
b) найти минимум целевой функции без учета ограничений с помощью градиентных методов
c) найти минимум целевой функции с учетом ограничений

Задача 7. Решить задачу нелинейного программирования методом проектируемых градиентов Розена

$$ Z=8+8x_1+10x_2-2x_1^2-x_2^2\to \max,\\ 4x_1+3x_2 \le 24,\\ x_1+4x_2\le 16,\\ x_1,x_2 \ge 0. $$

Задача 8. Решить задачу безусловной оптимизации методом покоординатного спуска Пауэлла. Выполнить 2 итерации.

$$ F(x)=x_1+4x_2+x_1x_2-2x_1^2-2x_2^2\to \max,\\ x_1,x_2 \in E^2,\\ x_0=(-1;4). $$

Задача 9. Используя графический метод, решить следующую задачу квадратического программирования: $$f(x) = 9(x_1-9)^2+9(x_2-9)^2 \to \min,$$ при ограничениях:

$$ x_1+2x_2\ge 2,\\ x_1+x_2\le 6,\\ 2x_1+x_2 \le 11,\\ x_1,x_2 \ge 0. $$

Задача 10. Дана задача выпуклого программирования. Требуется: 1) найти решение графическим методом, 2) написать функцию Лагранжа данной задачи и найти её седловую точку, используя решение задачи, полученное графически:

$$ (x_1-5)^2+(x_2-1)^2 \to \min,\\ 2x_1-x_2\ge -4,\\ 2x_1-3x_2\le -6,\\ x_1+x_2 \le 11,\\ x_1,x_2 \ge 0. $$

Полезные ссылки

Источник