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

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

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

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

Источник

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

Нелинейное программирование занимается оптимизацией моделей задач, в которых либо ограничения q_i(x) либо целевая функция Z(X) либо то и другое нелинейны.
Найти max(min)=Z=z(X)
в области
где R – отношение порядка (=, ≥, ≤), Ω– область допустимых решений; b_i– константа, i= 1,m ;
X=(x₁,…,x_n)=j>, j=1..n – план или вектор управления.
Для выяснения трудностей решения задач данного класса, порождаемых нелинейностью, сопоставим задачи линейного и нелинейного программирования. Можно указать три характерные особенности для каждого класса.

Задачи линейного программирования	Задачи нелинейного программирования
1. Область Ω допустимых планов – выпуклое множество с конечным числом угловых (крайних) точек.	1. Множество Ω допустимых планов может быть невыпуклым, несвязным, иметь бесконечное число крайних точек.
2. Экстремальное значение линейная целевая функция z(X) достигает в одной из крайних точек (на границе области Ω допустимых решений).	2. Экстремум может достигаться не только на границе, но и внутри области Ω допустимых решений.
3. Экстремальное значение z(X) целевой функции является и глобальным значением.	3. Целевая функция z(X) в области Ω может иметь несколько локальных экстремумов.

На рисунке приводится классификация задач и методов нелинейного программирования.

Большинство существующих методов в нелинейном программировании можно разделить на два больших класса:

1. Прямые методы — методы непосредственного решения исходной задачи. Прямые методы порождают последовательность точек – решений, удовлетворяющих ограничениям, обеспечивающим монотонное убывание целевой функции.
   Недостаток: трудно получить свойство глобальной сходимости.
   Задачи с ограничениями в виде равенств.
   Метод замены переменных (МЗП)
2. Двойственные методы — методы, использующие понятие двойственности. В этом случае легко получить глобальную сходимость.
   Недостаток: не дают решения исходной задачи в ходе решения – оно реализуемо лишь в конце итерационного процесса.
   • Метод множителей Лагранжа (ММЛ)
   • Методы штрафов
   • Метод множителей
   • Методы линеаризации для задач условной оптимизации
     Алгоритм Франка–Вульфа
     Метод допустимых направлений Зойтендейка
   • Метод условного градиента
   • Метод проекции градиента
   • Сепарабельное программирование.
   • Квадратичное программирование

Методы поиска нулей функции

Методы минимизации функций

Функция одной переменной

Функция двух переменных

1. Матрица Гессе. . Позволяет ответить на вопрос является ли функция выпуклой или вогнутой, а также определить тип экстремума (минимум или максимум).
2. Производные второго порядка
3. Экстремум функции двух переменных.

Методы прямого поиска

1. Метод Хука–Дживса
2. Метод сопряженных направлений (метод Пауэлла). Найти минимум целевой функции методом сопряженных направлений: f(x)=3x₁ – x₁ 3 + 3x₂ 2 + 4x₂. x 0 =(0.78;1)

Градиентные методы

1. Метод наискорейшего спуска (метод Коши).
2. Метод Ньютона
3. Метод Марквардта. Найти минимум функции: y=x₁ 2 +4x₂ 2 +x₁x₂+1-5x₂ методом Марквардта с начальной точкой (10;10) и ε_x=ε_y= ε_|▽f(x)|=0.5. Предельное число итераций равно M=5.
4. Метод сопряженных градиентов (метод Флетчера-Ривса).
5. Метод Бройдена–Флетчера–Гольдфарба–Шанно (квазиньютоновские методы).

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

Прямые методы

1. Метод множителей Лагранжа. В задачах 301-320 используя метод множителей Лагранжа найти точки экстремума функции z=f(x,y) при заданном условии: z=xy+7x , 2x+y=1
2. Условия Куна-Таккера.

Метод проекции градиента.
Метод условного градиента.

Методы линеаризации для задач условной оптимизации

Методы перебора применимы для отыскания экстремумов унимодальных целевых функций. Действие любого из методов поиска заключается в сужении области поиска экстремума (длины _{l 0}):
а) до области заданной длины (_e> 0), проводя минимальное число измерений значений функции (методы дихотомии, золотого сечения);
б) до наименьших возможных размеров _ln при заданном числе измерений n (метод Фибоначчи).
Первая формулировка целесообразна в том случае, если с каждым измерением связаны значительные затраты средств или времени, однако на поиск отпускаются неограниченные средства, которые мы все же стремимся минимизировать; вторая – когда исследователь располагает ограниченными средствами и, зная расходы, связанные с каждым измерением, стремится получить наилучший результат.

Классические методы нахождения экстремумов функций предполагают, что целевые функции непрерывные и гладкие. Для существования точки экстремума должны выполняться необходимые и достаточные условия. Необходимыми условиями существования экстремума являются требования обращения в нуль частных производных первого порядка целевой функции по каждой из переменных. Точка, найденная из необходимых условий, называется стационарной (подозрительной на оптимальную). В качестве стационарных точек могут быть точки перегиба, седловые точки и др. Поэтому необходим учет достаточных условий нахождения экстремумов функций. Он сложен для функций многих переменных как в алгебраическом, так и в вычислительном плане. Так в случае функции двух переменных достаточным условием существования экстремума будет положительная определенность матрицы А размером 2×2 (условие Лежандра-Клебша), составленной из вторых частных производных функции. Недостатком классического метода дифференциального исчисления является и то, что он дает возможность найти экстремум только в том случае, если он лежит внутри области определения функции. Если экстремум находится на границе области определения, то этот метод становится бессильным.

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

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

Источник

Графический метод решения задач нелинейного программирования

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

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

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

Шаг 1. На плоскости строят область допустимых реше­ний, опреде­ляемую ограничениями. Если она пуста, т.е. если ограни­чения несовместны, то задача не имеет решений. В противном случае переходят к шагу 2.

Шаг 2. Строят линию уровня целевой функции: , где C – неко­торая константа. Переходят к шагу 3.

Шаг 3. Определяют направление возрастания (при задаче на максимум) или убывания (при задаче на минимум) целевой функции посредством вычисле­ния координат и построения вектора градиента целевой функции.

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

Шаг 5. Определяют значения координат для точки, найденной на шаге 4, а также значение целевой функции в этой точке, т.е. при найденных зна­чениях координат этой точки.

ПРИМЕР: Найдите графическим методом оптимальные решения задачи нелинейного программирования, заданной математической моделью вида:

В соответствии с алгоритмом построим на плоскости об­ласть допустимых решений. Ограничения выделяют первую чет­верть. Границей полуплоскости по первому ограничению является гипербола с уравнением: , причем неравенство ограничения выполняется для точек, лежащих выше этой гиперболы. Второй границей является окружность, точнее ее четвер­тая часть в первой четверти, с радиусом 3 и центром в начале координат. На рис. 5 область допустимых решений задачи выделена штрихов­кой.

Очевидно, что вектор градиента целевой функции определяется координа­тами: и, следовательно, направлен вправо вверх, как указано стрел­кой. Как известно, целевая функция возрастает в направлении вектора гра­диента и убывает в направлении вектора антиградиента, и, кроме того, любая линия уровня целевой функции перпендикулярна этому вектору. Поэтому мак­симум целевой функции достигается в точке В, а минимум – в точке А. И задача сводится к нахождению координат этих точек.

Заметим, что в точке В совпадают тангенсы углов наклона касательной к окружности и прямой – линии уровня целевой функции к оси , а также, что эти тангенсы численно равны производным этих функций (вычисленным в точке В). Для линии уровня угловой коэффициент (тангенс угла наклона) очевидно равен: , а для окружности угловой коэффициент касательной равен: , поэтому можно записать уравнение: . Если к этому уравнению добавить уравнение окружности, то получится система уравнений вида:

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

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

Метод множителей Лагранжа

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

Причем в этой модели функции и непрерывны вместе со своими частными производными по всем управляющим переменным: .

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

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

,

где переменные называются множителями Лагранжа.

Шаг 2. Находят частные производные функции Лагранжа по всем перемен­ным и приравнивают их к нулю:

Шаг 3. Решают систему уравнений, полученную на шаге 2, и находят ста­ционарные точки, т.е. точки, в которых функция F (и, следовательно, исходя из структуры функции F, целевая функция f) может иметь экстремум.

Шаг 4. Проверяют полученные на шаге 3 стационарные точки на наличие в них экстремума и находят экстремальное значение целевой функ­ции задачи в найденной точке условного (в смысле не глобального) экстрему­ма.

ПРИМЕР: Фирма реализует автомобили двумя способами: через магазин и через торговых агентов. При реализации автомобилей через магазин расходы на реализацию составляют: условных единиц, а при продаже автомобилей через торговых агентов расходы составляют условных единиц. Найти оптимальный способ реа­лизации автомобилей, обеспечивающий минимум суммарных расходов, если общее число автомобилей, предназначенных для продажи, составляет 200 штук.

Очевидно, что математическая модель задачи будет иметь вид:

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

В рассматриваемом случае функция Лагранжа будет иметь вид:

.

Вычислив частные производные и приравняв их нулю, полу­­чим следующую систему уравнений:

Решив эту систему, получим: и . Этим зна­че­ниям управляющих переменных соответствует значение целевой функции, равное: .

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

.

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

Таким образом, для получения минимальных расходов на реализацию, фирме следует реализовать 99 автомобилей через магазин и 101 автомобиль че­рез торговых агентов. При этом расходы на реализацию составят 20398 условных единиц.

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

Рекомендуемая литература по теме 4: [1 ÷ 4].

ВОПРОСЫ для самопроверки знаний по теме 4:

1. Для решения каких экономических задач чаще всего приме­няются нелиней­ные математические модели?

2. При каких условиях задача нелинейного программирования может быть решена графическим методом?

3. В каком виде должна быть записана математическая модель задачи нелинейного программирования для решения ее методом множителей Лагранжа?

4. В чем заключается основная идея метода множителей Лагранжа?

Источник