Нелинейное программирование: графический метод и метод множителей Лагранжа

1. Общий вид задач нелинейного программирования. Графический метод решения задач нелинейного программирования. Метод множителей

Лагранжа.
Преподаватель: Ясин Эминович

2. План изучения

• Что такое нелинейное программирование и чем оно
отличается от линейного.
• Общий вид задачи нелинейного программирования.
• Графический метод решения (для двух переменных).
• Метод множителей Лагранжа (для задач с
ограничениями-равенствами).
• Примеры и выводы.

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

Линейное программирование:
Целевая функция и ограничения — линейные (прямые
линии, плоскости).
Область допустимых решений — выпуклый
многогранник.
Оптимум всегда в вершине.

4. Что такое Нелинейное программирование

• Нелинейное программирование (НЛП) — это раздел
математического программирования, который
изучает методы решения оптимизационных задач, в
которых либо целевая функция, либо хотя бы одно из
ограничений, либо и то и другое являются
нелинейными функциями переменных.
• Простыми словами, это более сложный вид линейного
программирования. Если в линейных задачах все
зависимости — прямые линии (например, «доход =
цена × количество»), то в нелинейных задачах
появляются кривые, изгибы, овраги и холмы.

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

6. Что за элементы?

Переменные x1,x2,…,xn
Это то, что мы можем менять (например, объёмы выпуска продукции,
размеры детали, дозы лекарства). Они могут быть любыми действительными
числами, но часто на них накладываются дополнительные условия (например,
не отрицательность).
Целевая функция F(X)
Это критерий, по которому мы оцениваем решение. Она
называется нелинейной, если её график — не прямая линия.
Примеры:
Ограничения
Они описывают, какие значения переменных допустимы. Каждое ограничение
задаёт некоторую область в пространстве переменных.
Примеры нелинейных ограничений:

7. Классификация нелинейного программирования

Есть много видов классификации :
1По наличию ограничений.
2По типу ограничений.
3По свойствам целевой функции и ограничений.
4По количеству экстремумов.
5По размерности
Безусловная / условная
Равенства / неравенства
Выпуклая / невыпуклая
Одноэкстремальная / многоэкстремальная
Если кратко перечислить

8. Графический метод (для двух переменных)

• нарисовать область допустимых решений и линии
уровня целевой функции, найти точку касания.
• Алгоритм:

9. Пример решения

10. Плюсы и минусы метода

• Плюсы:
Наглядно, понятно.
Хорош для понимания сути.
Минусы:
Только для двух переменных.
Неточность при рисовании от руки.
Не работает для сложных ограничений.

11. Метод Лагранжа

Метод Лагранжа применяется для решения задач
условной оптимизации, когда нужно найти экстремум
(максимум или минимум) функции при наличии
ограничений типа равенств.
Общая постановка:
Идея: мы вводим дополнительную переменную λ
(множитель Лагранжа) и составляем новую функцию —
функцию Лагранжа:
Если теперь искать безусловный экстремум функции L (то
есть брать частные производные по всем переменным и
приравнивать к нулю), то условия экстремума L
автоматически включают в себя и исходное ограничение, и
необходимое условие экстремума исходной задачи.

12. Геометрический смысл

Рассмотрим случай двух переменных. У нас есть функция F(x,y),
которую мы хотим максимизировать при условии g(x,y)=0.
Линии уровня функции F — это кривые, на
которых F постоянна. Ограничение g(x,y)=0— тоже кривая.
В точке экстремума (максимума или минимума) на
кривой g=0 линии уровня F должны касаться этой кривой.
Потому что если бы они пересекались, то, двигаясь вдоль
кривой, мы могли бы перейти на другую линию уровня с
большим (или меньшим) значением F, то есть точка не была бы
экстремальной.
Касание кривых означает, что их нормали (градиенты) в точке
касания параллельны. То есть существует такое число λ, что
Это и есть условие, которое получается из производных
функции Лагранжа.

13. Алгоритм решения с помощью метода Лагранжа

14. Пример решения

15. В итоге про метод

• Метод множителей Лагранжа - это мощный
инструмент для решения задач с ограничениямиравенствами. Он превращает условную задачу в
безусловную путем введения дополнительных
переменных (множителей). Геометрически он
соответствует условию параллельности градиентов
целевой функции и функции ограничения в точке
экстремума
1. Составляем L=F+λg.
2. Берём частные производные по всем переменным и по λ.
3. Решаем систему.
4. Проверяем, что получили.

16. Итоги

• Нелинейное программирование — важный раздел
оптимизации с широкими приложениями.
• Графический метод хорош для понимания, но
ограничен двумя переменными.
• Метод множителей Лагранжа — мощный
аналитический инструмент для задач с
ограничениями-равенствами.