NONLINEAR PROGRAMMING: MGA PAMAMARAAN AT PAGSASANAY - MGA MATEMATIKA - 2025

Ang nonlinear programming ay ang proseso ng pag-optimize ng isang function na nakasalalay sa ilang mga malayang variable, na kung saan ay sumasailalim sa mga paghihigpit.

Kung ang isa o higit pa sa mga hadlang, o kung ang pag-andar na mai-maximize o mai-minimize (tinatawag na ang layunin na function), ay hindi ipinahayag bilang isang linear na kumbinasyon ng mga variable, kung gayon mayroon kang isang problema sa nonlinear programming.

Larawan 1. Hindi liham na problema sa programming (NLP). kung saan ang G ay ang (non-linear) na pag-andar upang mai-optimize sa berdeng rehiyon, na tinutukoy ng mga hadlang. Pinagmulan: F. Zapata.

At samakatuwid ang mga pamamaraan at pamamaraan ng pag-programming ng linear ay hindi maaaring gamitin.

Halimbawa, ang hindi kilalang paraan ng Simplex ay hindi magagamit, na nalalapat lamang kapag ang layunin na pag-andar at ang mga hadlang ay lahat ng mga magkakasamang kombinasyon ng mga variable sa problema.

Mga paraan ng pag-programming ng linear

Para sa mga di-linear na mga problema sa programming ang pangunahing pamamaraan na gagamitin ay:

1.- Mga pamamaraan ng graphic.

2.- Lagrange multiplier upang galugarin ang hangganan ng solusyon sa rehiyon.

3.- Pagkalkula ng gradient upang galugarin ang mga sukdulan ng pagpapaandar ng layunin.

4.- Ang pamamaraan ng pababang mga hakbang, upang mahanap ang mga walang saysay na puntos ng gradient.

5.- Binago na pamamaraan ng mga Lagrange multiplier (kasama ang Karush-Kuhn-Tucker kondisyon).

Halimbawa ng solusyon na may pamamaraan ng grapiko

Ang isang halimbawa ng isang solusyon sa pamamaraan ng grapiko ay ang isa na makikita sa figure 2:

Larawan 2. Halimbawa ng isang di-linear na problema sa mga di-linear na paghihigpit at ang graphic na solusyon nito. Pinagmulan: F. Zapata.

Pagsasanay

- Ehersisyo 1 (Paraan ng grapiko)

Ang tubo G ng isang tiyak na kumpanya ay nakasalalay sa halagang naibenta ng produkto X at ang halagang naibenta ng produkto Y, bilang karagdagan, ang kita ay tinutukoy ng mga sumusunod na pormula:

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

Ang mga halaga ng X at Y ay kilala na mayroong mga sumusunod na paghihigpit:

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

Alamin ang mga halaga ng X at Y na gumagawa ng maximum na pakinabang.

Larawan 3. Ang kita ng isang kumpanya ay maaaring maging modelo ayon sa matematika upang mahanap ang maximum na kita gamit ang nonlinear programming. Pinagmulan: Pixabay.

Solusyon

Sa problemang ito ang layunin na pag-andar ay hindi linya, habang ang mga hindi pagkakapareho na tumutukoy sa mga hadlang. Ito ay isang nonlinear na problema sa programming.

Para sa solusyon ng problemang ito, pipiliin ang paraan ng grapiko.

Una, ang rehiyon ng solusyon ay matukoy, na ibinibigay ng mga paghihigpit.

Bilang X≥0; Y≥0, ang solusyon ay matatagpuan sa unang kuwadrante ng XY na eroplano, ngunit dahil dapat din itong totoo na X + Y ≤ 7, ang solusyon ay nasa ibabang kalahating eroplano ng linya X + Y = 7.

Ang rehiyon ng solusyon ay ang intersection ng unang kuwadrante na may mas mababang kalahating eroplano ng linya, na nagreresulta sa isang tatsulok na rehiyon kung saan natagpuan ang solusyon. Ito ay katulad ng ipinahiwatig sa figure 1.

Sa kabilang banda, ang kikitain G ay maaari ring irepresenta sa eroplano ng Cartesian, dahil ang katumbas nito ay ang isang ellipse na may gitna (2,3).

Ang ellipse ay ipinapakita sa Figure 1 para sa iba't ibang mga halaga ng G. Ang mas mataas na halaga ng G, mas malaki ang pakinabang.

Mayroong mga solusyon na kabilang sa rehiyon, ngunit hindi nagbibigay ng maximum na halaga ng G, habang ang iba, tulad ng G = 92.4, ay nasa labas ng berdeng sona, iyon ay, ang solution zone.

Pagkatapos, ang maximum na halaga ng G, tulad ng X at Y ay kabilang sa solusyon sa rehiyon ay tumutugma sa:

G = 77 (maximum na pakinabang), na ibinibigay para sa X = 7 at Y = 0.

Kapansin-pansin, ang pinakamataas na kita ay nangyayari kapag ang halaga ng benta ng produkto Y ay zero, habang ang halaga ng produkto X ay umaabot sa pinakamataas na posibleng halaga.

- Ehersisyo 2 (Paraan ng analytical: Mga multiplier ng Lagrange)

Hanapin ang solusyon (x, y) na gumagawa ng pag-andar f (x, y) = x ² + 2y ² maximum sa rehiyon g (x, y) = x ² + y ² - 1 = 0.

Solusyon

Ito ay malinaw na isang di-linear na problema sa pagprograma, dahil kapwa ang layunin na function f (x, y) at ang paghihigpit g (x, y) = 0, ay hindi isang guhit na kumbinasyon ng mga variable x at y.

Ang paraan ng multiplier ng Lagrange ay gagamitin, na una ay nangangailangan ng pagtukoy sa Lagrange function L (x, y, λ):

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

Kung saan ang λ ay isang parameter na tinatawag na Lagrange multiplier.

Upang matukoy ang matinding halaga ng pagpapaandar ng layunin f, sa rehiyon ng solusyon na ibinigay ng paghihigpit g (x, y) = 0, sundin ang mga hakbang na ito:

-Nagpahiwatig ng bahagyang derivatives ng Lagrange function L, na may paggalang sa x, y, λ.

-Magtimbang ng bawat isa na nagmula sa zero.

Narito ang pagkakasunud-sunod ng mga operasyong ito:

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

Posibleng mga solusyon sa system

Ang isang posibleng solusyon ng sistemang ito ay λ = 1 upang ang unang equation ay nasiyahan, kung saan ang y = 0 upang ang pangalawa ay nasiyahan.

Ang solusyon na ito ay nagpapahiwatig na x = 1 o x = -1 para sa ikatlong equation na nasiyahan. Sa ganitong paraan, nakuha ang dalawang solusyon na S1 at S2:

S1: (x = 1, y = 0)

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

Ang iba pang kahalili ay ang λ = 2 upang ang pangalawang equation ay nasiyahan, anuman ang halaga ng y.

Sa kasong ito, ang tanging paraan para sa unang equation na nasiyahan ay para sa x = 0. Isinasaalang-alang ang pangatlong equation, mayroong dalawang posibleng solusyon, na tatawagin namin ang S3 at S4:

S3: (x = 0, y = 1)

S4: (x = 0, y = -1)

Upang malaman kung alin o alin sa mga solusyon na ito na i-maximize ang layunin na pag-andar, nagpapatuloy kaming kapalit sa 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

Napagpasyahan namin na ang mga solusyon na pinalaki ang f, kapag ang x at y ay kabilang sa circumference g (x, y) = 0 ay S3 at S4.

Ang mga pares ng mga halaga (x = 0, y = 1) at (x = 0, y = -1) i-maximize ang f (x, y) sa rehiyon ng solusyon g (x, y) = 0.

- Ehersisyo 3 (Null gradient)

Maghanap ng mga solusyon (x, y) para sa layunin na pag-andar:

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

Hayaan ang maximum sa rehiyon g (x, y) = x ² + y ² - 1 ≤ 0.

Solusyon

Ang ehersisyo na ito ay katulad ng ehersisyo 2, ngunit ang solusyon (o paghihigpit) na rehiyon ay umaabot sa panloob na rehiyon ng circumference g (x, y) = 0, iyon ay, sa bilog g (x, y) ≤ 0. Kabilang dito ang sa circumference at panloob na rehiyon nito.

Ang solusyon sa hangganan ay natukoy na sa ehersisyo 2, ngunit ang panloob na rehiyon ay nananatiling mai-explore.

Upang gawin ito, ang gradient ng function f (x, y) ay dapat kalkulahin at itakda nang pantay sa zero, upang makahanap ng matinding halaga sa rehiyon ng solusyon. Katumbas ito sa pagkalkula ng mga bahagyang derivatives ng f na may paggalang sa x at y ayon sa pagkakabanggit at pagtatakda ng pantay-pantay sa zero:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Ang sistemang ito ng mga equation ay may tanging solusyon (x = 0, y = 0) na kabilang sa bilog g (x, y) ≤ 0.

Pagsusulat ng halagang ito sa mga resulta ng f f:

f (0, 0) = 0

Sa konklusyon, ang maximum na halaga na ang function ay tumatagal sa rehiyon ng solusyon ay 2 at nangyayari sa hangganan ng rehiyon ng solusyon, para sa mga halaga (x = 0, y = 1) at (x = 0, y = -1) .

Mga Sanggunian

1. Avriel, M. 2003. Nonlinear Programing. Pag-publish ng Dover.
2. Bazaraa. 1979. Nonlinear Programing. John Wiley at Mga Anak.
3. Bertsekas, D. 1999. Nonlinear Programing: 2nd edition. Athena Siyentipiko.
4. Nocedal, J. 1999. Numerical Optimization. Springer-Verlag.
5. Wikipedia. Nonlinear programming. Nabawi mula sa: es.wikipedia.com