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

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

Ако едно или повече от ограниченията или функцията, която трябва да бъде максимизирана или сведена до минимум (наречена обективна функция), не е изразена като линейна комбинация от променливи, тогава имате проблем с нелинейно програмиране.

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

Затова процедурите и методите на линейното програмиране не могат да се използват.

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

Линейни методи за програмиране

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

1.- Графични методи.

2. - Умножители на Lagrange за изследване на границата на района на разтвора.

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.

Ще се използва методът на множители на Lagrange, който първо изисква дефиниране на функцията на Lagrange L (x, y, λ):

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

Къде λ е параметър, наречен множител на Lagrange.

За да определите крайните стойности на обективната функция f, в областта на разтвора, дадена от ограничението g (x, y) = 0, следвайте тези стъпки:

-Намерете частичните производни на функцията на Lagrange 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.

В този случай единственият начин за удовлетворяване на първото уравнение е за x = 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. Нелинейно програмиране. Публикуване в Дувър
2. Bazaraa. 1979. Нелинейно програмиране. John Wiley & Sons.
3. Bertsekas, D. 1999. Нелинейно програмиране: 2-ро издание. Атина научна.
4. Nocedal, J. 1999. Числена оптимизация. Springer-Verlag.
5. Wikipedia. Нелинейно програмиране. Възстановено от: es.wikipedia.com