НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ: МЕТОДЫ И УПРАЖНЕНИЯ - МАТЕМАТИКА - 2025

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

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

Рисунок 1. Задача нелинейного программирования (НЛП). где G - (нелинейная) функция для оптимизации в зеленой области, определяемая ограничениями. Источник: Ф. Сапата.

И поэтому нельзя использовать процедуры и методы линейного программирования.

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

Методы линейного программирования

Для задач нелинейного программирования используются следующие основные методы:

1.- Графические методы.

2.- Множители Лагранжа для исследования границы области решения.

3.- Расчет градиента для исследования крайних значений целевой функции.

4.- Метод нисходящих шагов, чтобы найти точки нулевого градиента.

5.- Модифицированный метод множителей Лагранжа (с условием Каруша-Куна-Таккера).

Пример решения графическим методом

Пример решения с использованием графического метода - это то, что можно увидеть на рисунке 2:

Рисунок 2. Пример нелинейной задачи с нелинейными ограничениями и ее графическое решение. Источник: Ф. Сапата.

упражнения

- Упражнение 1 (Графический метод)

Прибыль G определенной компании зависит от количества проданного продукта X и количества проданного продукта Y, кроме того, прибыль определяется по следующей формуле:

G = 2 (X - 2) ² + 3 (Y - 3) ²

Известно, что суммы X и Y имеют следующие ограничения:

X≥0; Y≥0 и X + Y ≤ 7

Определите значения X и Y, которые обеспечивают максимальное усиление.

Рисунок 3. Прибыль компании можно математически смоделировать, чтобы найти максимальную прибыль с помощью нелинейного программирования. Источник: Pixabay.

Решение

В этой задаче целевая функция нелинейна, а неравенства, определяющие ограничения, являются. Это проблема нелинейного программирования.

Для решения этой проблемы будет выбран графический метод.

Сначала будет определена область решения, которая задается ограничениями.

Поскольку X≥0; Y≥0, решение должно быть найдено в первом квадранте плоскости XY, но поскольку также должно быть верно, что X + Y ≤ 7, решение находится в нижней полуплоскости прямой X + Y = 7.

Область решения - это пересечение первого квадранта с нижней полуплоскостью линии, в результате чего получается треугольная область, в которой находится решение. Это то же самое, что показано на рисунке 1.

С другой стороны, коэффициент усиления G также может быть представлен в декартовой плоскости, поскольку его уравнение представляет собой уравнение эллипса с центром (2,3).

Эллипс показан на рисунке 1 для различных значений G. Чем выше значение G, тем больше усиление.

Есть решения, которые относятся к области, но не дают максимального значения G, а другие, например G = 92,4, находятся за пределами зеленой зоны, то есть зоны решения.

Тогда максимальное значение G, такое, что X и Y принадлежат области решения, соответствует:

G = 77 (максимальное усиление), что дается для X = 7 и Y = 0.

Интересно, что максимальная прибыль возникает, когда объем продаж продукта Y равен нулю, а количество продукта X достигает максимально возможного значения.

- Упражнение 2 (Аналитический метод: множители Лагранжа)

Найдите решение (x, y), которое делает функцию f (x, y) = x ² + 2y ² максимальной в области g (x, y) = x ² + y ² - 1 = 0.

Решение

Очевидно, что это проблема нелинейного программирования, поскольку и целевая функция f (x, y), и ограничение g (x, y) = 0 не являются линейной комбинацией переменных x и y.

Будет использован метод множителей Лагранжа, который сначала требует определения функции Лагранжа L (x, y, λ):

L (x, y, λ) = f (x, y) - λ g (x, y) = x ² + 2y ² - λ (x ² + y ² - 1).

Где λ - параметр, называемый множителем Лагранжа.

Чтобы определить экстремальные значения целевой функции f, в области решения, заданной ограничением g (x, y) = 0, выполните следующие действия:

-Найти частные производные функции Лагранжа L по x, y, λ.

-Уравнять каждую производную до нуля.

Вот последовательность этих операций:

1. ∂L / ∂x = 2x - 2λx = 0
2. ∂L / ∂y = 4y - 2λy = 0
3. ∂L / ∂λ = - (х ² + y ² - 1) = 0

Возможные системные решения

Возможным решением этой системы является λ = 1, так что первое уравнение удовлетворяется, и в этом случае y = 0, так что выполняется второе.

Это решение означает, что x = 1 или x = -1 для выполнения третьего уравнения. Таким образом были получены два решения S1 и S2:

S1: (х = 1, у = 0)

S2: (х = -1, у = 0).

Другой альтернативой является λ = 2, так что второе уравнение удовлетворяется независимо от значения y.

В этом случае единственный способ удовлетворить первое уравнение - это x = 0. Учитывая третье уравнение, есть только два возможных решения, которые мы назовем S3 и S4:

S3: (х = 0, у = 1)

S4: (х = 0, у = -1)

Чтобы выяснить, какое или какое из этих решений максимизирует целевую функцию, мы переходим к замене в f (x, y):

S1: f (1, 0) = 1 ² + 2,0 ² = 1

S2: f (-1, 0) = (-1) ² + 2,0 ² = 1

S3: f (0, 1) = 0 ² + 2,1 ² = 2

S4: f (0, -1) = 0 ² + 2 (-1) ² = 2

Мы заключаем, что решения, которые максимизируют f, когда x и y принадлежат окружности g (x, y) = 0, - это S3 и S4.

Пары значений (x = 0, y = 1) и (x = 0, y = -1) максимизируют f (x, y) в области решения g (x, y) = 0.

- Упражнение 3 (нулевой градиент)

Найдите решения (x, y) для целевой функции:

е (х, у) = х ² + 2 у ²

Пусть будет максимумом в области g (x, y) = x ² + y ² - 1 ≤ 0.

Решение

Это упражнение аналогично упражнению 2, но область решения (или ограничения) простирается до внутренней области окружности g (x, y) = 0, то есть до круга g (x, y) ≤ 0. Сюда входит к окружности и ее внутренней области.

Решение на границе уже было определено в упражнении 2, но внутреннюю область еще предстоит изучить.

Для этого необходимо вычислить градиент функции f (x, y) и установить равным нулю, чтобы найти экстремальные значения в области решения. Это эквивалентно вычислению частных производных f по x и y соответственно и установке их равной нулю:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Эта система уравнений имеет единственное решение (x = 0, y = 0), которое принадлежит окружности g (x, y) ≤ 0.

Подставляя это значение в функцию f, получаем:

f (0, 0) = 0

В заключение, максимальное значение, которое функция принимает в области решения, равно 2 и встречается на границе области решения для значений (x = 0, y = 1) и (x = 0, y = -1) .

Ссылки

1. Авриэль, м. 2003. Нелинейное программирование. Dover Publishing.
2. Базараа. 1979. Нелинейное программирование. Джон Вили и сыновья.
3. Бертсекас, Д. 1999. Нелинейное программирование: 2-е издание. Athena Scientific.
4. Нокедал, Дж. 1999. Численная оптимизация. Springer-Verlag.
5. Wikipedia. Нелинейное программирование. Получено с: es.wikipedia.com