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

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

Тем не менее, в случае 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.$$

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

• Нелинейное программирование - глава из учебника
• Примеры решений по методам оптимизации
• Учебники и лекции по линейному программированию