НЕЛИНЕАРНО ПРОГРАМИРАЊЕ: МЕТОДЕ И ВЈЕЖБЕ - МАТХС - 2025

Нелинеарни програмирање је процес оптимизације функцију која зависи од неколико независних варијабли, што заузврат су подвргнути ограничењима.

Ако једно или више ограничења или ако функција која ће бити максимизирана или минимизирана (која се назива циљна функција) није изражена као линеарна комбинација варијабли, тада имате нелинеарни проблем програмирања.

Слика 1. Проблем нелинеарног програмирања (НЛП). где је Г (нелинеарна) функција за оптимизацију у зеленој области, одређена ограничењима. Извор: Ф. Запата.

Стога се процедуре и методе линеарног програмирања не могу користити.

На пример, добро позната Симплек метода се не може користити, која се примењује само када су циљна функција и ограничења све линеарне комбинације променљивих у проблему.

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

За проблеме са нелинеарним програмирањем главне методе које се користе су:

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

2. - Лагрангеов мултипликатор како би се истражила граница региона.

3. - Израчунавање градијента за истраживање крајности циљне функције.

4.- Метода силазних степеница за проналажење тачака нагиба са нулом.

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

Пример раствора графичким поступком

Пример решења са графичким методом је онај који се може видети на слици 2:

Слика 2. Пример нелинеарног проблема са нелинеарним ограничењима и његово графичко решење. Извор: Ф. Запата.

Вежбе

- Вежба 1 (графички метод)

Добит Г одређене компаније зависи од продате количине производа Кс и количине производа И, осим тога профит се утврђује следећом формулом:

Г = 2 (Кс - 2) ² + 3 (И - 3) ²

Познато је да износи Кс и И имају следећа ограничења:

Кс≥0; И≥0 и Кс + И ≤ 7

Одредите вредности Кс и И које производе максимално појачање.

Слика 3. Добит фирме се може математички моделирати тако да пронађе максимални профит користећи нелинеарно програмирање. Извор: Пикабаи.

Решење

У овом проблему је циљна функција нелинеарна, док су неједнакости које дефинирају ограничења. Ово је проблем нелинеарног програмирања.

За решење овог проблема биће изабран графички метод.

Прво, биће одређено подручје решења, које је дато ограничењима.

Ас Кс≥0; И≥0, решење се мора наћи у првом квадранту равнине КСИ, али пошто мора такође бити тачно да је Кс + И ≤ 7, решење је у равнини доње половине линије Кс + И = 7.

Подручје решења је пресек првог квадранта са равном доњом половином линије, што резултира троуглом регијом у којој се решење налази. То је исто као што је приказано на слици 1.

С друге стране, добитак Г такође може бити представљен у картезијанској равни, јер је његова једначина елипса са центром (2,3).

Елипса је приказана на слици 1 за различите вредности Г. Што је већа вредност Г, то је већи добитак.

Постоје решења која припадају региону, али не дају максималну вредност Г, док су друга, као што је Г = 92.4, изван зелене зоне, односно зоне раствора.

Затим, максимална вредност Г, таква да Кс и И припадају решењу, одговара:

Г = 77 (максимални добитак), који је дат за Кс = 7 и И = 0.

Интересантно је да максимална добит настаје када је количина продаје производа И једнака нули, док количина производа Кс достиже највећу могућу вредност.

- Вежба 2 (Аналитичка метода: Лагрангеови мултипликатори)

Пронађите рјешење (к, и) које функцију ф (к, и) = к ² + 2и ^{2 чини} максимумом у региону г (к, и) = к ² + и ² - 1 = 0.

Решење

Јасно је нелинеарни проблем програмирања, јер и циљна функција ф (к, и) и ограничење г (к, и) = 0 нису линеарна комбинација променљивих к и и.

Користиће се метода Лагранге мултипликатора, која прво захтева дефинисање Лагранге функције Л (к, и, λ):

Л (к, и, λ) = ф (к, и) - λ г (к, и) = к ² + 2и ² - λ (к ² + и ² - 1)

Где је λ параметар који се зове Лагрангеов множитељ.

Да бисте одредили екстремне вредности циљне функције ф, у решењу које је дато ограничењем г (к, и) = 0, следите ове кораке:

- Пронађите делимичне деривате Лагрангеове функције Л у односу на к, и, λ.

-Уједначите сваки дериват на нулу.

Ево редоследа ових операција:

1. ∂Л / ∂к = 2к - 2λк = 0
2. ∂Л / ∂и = 4и - 2λи = 0
3. ∂Л / ∂λ = - (к ² + и ² - 1) = 0

Могућа системска решења

Могуће решење овог система је λ = 1 тако да је прва једначина задовољена, у том случају и = 0 тако да је друга задовољена.

Ово решење подразумева да је к = 1 или к = -1 да би се задовољила трећа једначина. На овај начин су добијена два решења С1 и С2:

С1: (к = 1, и = 0)

С2: (к = -1, и = 0).

Друга алтернатива је да је λ = 2 тако да је задовољена друга једначина, без обзира на вредност и.

У овом случају, једини начин да се задовољи прва једначина је к = 0. С обзиром на трећу једначину, постоје само два могућа решења, која ћемо назвати С3 и С4:

С3: (к = 0, и = 1)

С4: (к = 0, и = -1)

Да бисмо сазнали која или која од ових решења максимизирају циљну функцију, прелазимо на супституцију у ф (к, и):

С1: ф (1, 0) = 1 ² + 2,0 ² = 1

С2: ф (-1, 0) = (-1) ² + 2.0 ² = 1

С3: ф (0, 1) = 0 ² + 2,1 ² = 2

С4: ф (0, -1) = 0 ² + 2 (-1) ² = 2

Закључујемо да су решења која максимизују ф, када к и и припадају ободу г (к, и) = 0, јесу С3 и С4.

Парови вредности (к = 0, и = 1) и (к = 0, и = -1) максимизирају ф (к, и) у региону решења г (к, и) = 0.

- Вежба 3 (Нулти градијент)

Пронађите решења (к, и) за циљну функцију:

ф (к, и) = к ² + 2 и ²

Нека буде максималан у региону г (к, и) = к ² + и ² - 1 ≤ 0.

Решење

Ова вежба је слична вежби 2, али се решење (или ограничење) шири на унутрашњу област обима г (к, и) = 0, то јест на круг г (к, и) ≤ 0. Ово укључује до обима и његове унутрашње области.

Решење на граници већ је одређено у вежби 2, али унутрашњост остаје да се истражи.

Да бисте то учинили, градијент функције ф (к, и) мора се израчунати и поставити једнак нули, да би се пронашле екстремне вредности у региону решења. Ово је еквивалентно израчунавању парцијалних деривата ф у односу на к и и, и постављање истог на нулу:

∂ф / ∂к = 2 к = 0

∂ф / ∂и = 4 и = 0

Овај систем једначина има једино решење (к = 0, и = 0) које припада кругу г (к, и) ≤ 0.

Замјена ове вриједности у функцији ф резултата:

ф (0, 0) = 0

Закључно, максимална вредност коју функција узима у региону решења је 2 и јавља се на граници подручја решења, за вредности (к = 0, и = 1) и (к = 0, и = -1) .

Референце

1. Авриел, М. 2003. Нелинеарно програмирање. Довер Публисхинг.
2. Базараа. 1979. Нелинеарно програмирање. Јохн Вилеи & Сонс.
3. Бертсекас, Д. 1999. Нелинеарно програмирање: друго издање. Атхена Сциентифиц.
4. Ноцедал, Ј. 1999. Нумеричка оптимизација. Спрингер-Верлаг
5. Википедиа. Нелинеарно програмирање. Опоравак од: ес.википедиа.цом