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

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

Якщо одне або більше обмежень, або якщо функція, яку потрібно максимізувати або мінімізувати (називається цільовою функцією), не виражається як лінійна комбінація змінних, тоді у вас виникає нелінійна проблема програмування.

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

Тому процедури та методи лінійного програмування використовувати не можна.

Наприклад, відомий метод Simplex не може бути використаний, який застосовується лише тоді, коли цільова функція та обмеження є всіма лінійними комбінаціями змінних у задачі.

Лінійні методи програмування

Для проблем з нелінійним програмуванням основними методами, які слід використовувати:

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 / ∂λ = - (x ² + y ² - 1) = 0

Можливі системні рішення

Можливим рішенням цієї системи є λ = 1, так що перше рівняння виконується, в цьому випадку y = 0, так що друге задовольняється.

З цього рішення випливає, що x = 1 або x = -1 для виконання третього рівняння. Таким чином було отримано два рішення S1 і S2:

S1: (x = 1, y = 0)

S2: (x = -1, y = 0).

Інша альтернатива полягає в тому, що λ = 2, так що виконується друге рівняння незалежно від значення y.

У цьому випадку єдиний спосіб задоволення першого рівняння - це х = 0. Розглядаючи третє рівняння, є лише два можливі рішення, які ми будемо називати S3 і S4:

S3: (x = 0, y = 1)

S4: (x = 0, y = -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) для цільової функції:

f (x, y) = x ² + 2 y ²

Нехай максимум в області 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
2. Базара. 1979. Нелінійне програмування. Джон Вілі та сини.
3. Берцекас, Д. 1999. Нелінійне програмування: 2-е видання. Афіна Наукова.
4. Nocedal, J. 1999. Числова оптимізація. Спрингер-Верлаг.
5. Вікіпедія. Нелінійне програмування. Відновлено з: es.wikipedia.com