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

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

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

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

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

Источник

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

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

Теорема. Если — точка локального минимума дифференцируемой функции , то при ограничениях , удовлетворяющих некоторому условию регулярности, для функции Лагранжа

существует вектор множителей Лагранжа такой, что

Замечания. 1.Множители Лагранжа имеют произвольные знаки.

2. Если f и выпуклы, то необходимые условия (4.4.), (4.5.) являются и достаточными для существования решения задачи (4.1.), (4.2.).

3. Требование регулярности связано с существованием решения системы (4.4.), (4.5.).

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

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

Для того чтобы вектор являлся решением задачи (4.6.), (4.7.) , необходимо существование такого вектора , чтобы пара векторов удовлетворяла системе уравнений:

Пример 11. В двух цехах предприятия нужно изготовить 20 изделий некоторой продукции. Затраты, связанные с изготовлением х₁ изделий в 1-м цехе, равны руб., а затраты при изготовлении х₂ изделий во 2-м цехе равны руб. Составить план производства изделий в двух цехах с минимальными затратами.

Решение. Математическая модель задачи:

Для данной точки получим в точке экстремума:

Исследуем характер функции f в окрестности точки , для этого находим

Так как и , то функция выпукла, и точка — точка минимума.

Ответ: Оптимальный план изделий.

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

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

Допустим, что функции и все , выпуклы по Х. Такая задача носит название выпуклого программирования и множество решений , определяемое условиями (4.9), является выпуклым. Для задачи (4.8), (4.9) справедлива теорема Куна-Таккера.

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

Последнее условие называется условием дополняющей нежесткости.

Если функции и — выпуклы по Х, то условия оптимальности (4.10), (4.11) будут не только необходимыми, но и достаточными. В этом случае условие существования решения Х и , удовлетворяющего (4.10), (4.11), которое называют условием регулярности, примет вид

Пользуясь теоремой Куна-Таккера, задачу нелинейного программирования решают следующим образом.

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

Шаг 2. Составляют систему уравнений вида (4.10), (4.11).

Шаг 3. Находят ее решение . В отличие от задачи с ограничениями-равенствами вектор должен в этом случае удовлетворять условию неотрицательности.

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

Основные положения теории могут быть легко распространены на этот случай. Тогда к ограничению (4.9) следует добавить следующее ограничение:

Это ограничение в общем виде можно записать как

Задача представлена в каноническом виде. Применим к ней теорему Куна-Таккера, для чего составим функцию Лагранжа

где — множители, связанные с ограничениями (4.12). Условия теоремы Куна-Таккера выглядят так:

Последнее соотношение представляет собой условия дополняющей нежесткости для ограничений неотрицательности.

Теорема. Пусть задача нелинейного программирования имеет вид

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

Пример 12. Предприятие выпускает два вида изделий А и Б. Норма расхода на производство каждого вида изделий приведены в таблице. При этом известно, что сырья имеется 12 т, а оборудования — 30 станко-часов.

Источник

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

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

Источник