Решение задач нелинейного программирования
В задачах нелинейного программирования целевая функция уже не линейно зависит от переменных, а иным образом (чаще всего встречается квадратичная зависимость - задачи квадратичного программирования), что усложняет задачу и делает невозможным применение стандартных методов (симплекс-метода и его производных).
Тем не менее, в случае 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. $$
