EPÄLINEAARINEN OHJELMOINTI: MENETELMÄT JA HARJOITUKSET - MATEMATIIKKA - 2026

Epälineaarinen ohjelmointi on prosessi optimoida funktio, joka riippuu useista riippumattomia muuttujia, jotka puolestaan ovat rajoituksia.

Jos yhtä tai useampaa rajoitusta tai jos maksimoitavaa tai minimoitavaa funktiota (kutsutaan objektiivifunktioksi) ei ilmaista muuttujien lineaarisena yhdistelmänä, sinulla on epälineaarinen ohjelmointiongelma.

Kuva 1. Epälineaarinen ohjelmointiongelma (NLP). jossa G on (epälineaarinen) optimointitoiminto vihreällä alueella, rajoitusten perusteella. Lähde: F. Zapata.

Ja siksi lineaarisen ohjelmoinnin menettelyjä ja menetelmiä ei voida käyttää.

Esimerkiksi tunnettua Simplex-menetelmää ei voida käyttää, jota sovelletaan vain, kun objektiivifunktio ja rajoitukset ovat kaikki ongelman muuttujien lineaarisia yhdistelmiä.

Lineaariset ohjelmointimenetelmät

Epälineaarisissa ohjelmointiongelmissa käytettävät päämenetelmät ovat:

1.- Graafiset menetelmät.

2.- Lagrange-kertoimet tutkiaksesi ratkaisualueen rajaa.

3.- Kaltevuuden laskeminen tavoitefunktion ääripäiden tutkimiseksi.

4.- Laskevien vaiheiden menetelmä nollagradientin pisteiden löytämiseksi.

5.- Lagrange-kertoimien modifioitu menetelmä (Karush-Kuhn-Tucker-olosuhteissa).

Esimerkki ratkaisusta graafisella menetelmällä

Esimerkki ratkaisusta graafisella menetelmällä on sellainen, joka voidaan nähdä kuvasta 2:

Kuva 2. Esimerkki epälineaarisesta ongelmasta epälineaarisilla rajoituksilla ja sen graafinen ratkaisu. Lähde: F. Zapata.

Harjoitukset

- Harjoitus 1 (graafinen menetelmä)

Tietyn yrityksen voitto G riippuu tuotteen X myydystä määrästä ja tuotteen Y myydystä määrästä. Lisäksi voitto määritetään seuraavalla kaavalla:

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

Määrillä X ja Y tiedetään olevan seuraavat rajoitukset:

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

Määritä X: n ja Y: n arvot, jotka tuottavat maksimaalisen vahvistuksen.

Kuva 3. Yrityksen voitto voidaan mallintaa matemaattisesti maksimaalisen voiton löytämiseksi epälineaarisella ohjelmoinnilla. Lähde: Pixabay.

Ratkaisu

Tässä ongelmassa objektiivifunktio on epälineaarinen, kun taas rajoitukset määrittelevät epätasa-arvot ovat. Tämä on epälineaarinen ohjelmointiongelma.

Tämän ongelman ratkaisemiseksi valitaan graafinen menetelmä.

Ensin määritetään ratkaisualue, jonka rajoitukset antavat.

Kuten X≥0; Y≥0, ratkaisu on löydettävä XY-tason ensimmäisestä neljänneksestä, mutta koska on myös totta, että X + Y ≤ 7, ratkaisu on linjan X + Y = 7 alapäätyssä.

Ratkaisualue on ensimmäisen kvadrantin leikkaus linjan alapuoliskon kanssa, mikä johtaa kolmiomaiseen alueeseen, jossa ratkaisu löytyy. Se on sama kuin kuvassa 1.

Toisaalta vahvistusta G voidaan esittää myös Cartesian-tasolla, koska sen yhtälö on keskuksen (2,3) kanssa ellipsin yhtälö.

Ellipsi on esitetty kuvassa 1 G: n eri arvoille. Mitä suurempi on G: n arvo, sitä suurempi on vahvistus.

On ratkaisuja, jotka kuuluvat alueeseen, mutta eivät anna maksimiarvoa G, kun taas toiset, kuten G = 92,4, sijaitsevat vihreän alueen eli ratkaisuvyöhykkeen ulkopuolella.

Sitten G: n maksimiarvo siten, että X ja Y kuuluvat ratkaisualueeseen, vastaa:

G = 77 (suurin vahvistus), joka annetaan arvoille X = 7 ja Y = 0.

Mielenkiintoista on, että suurin voitto syntyy, kun tuotteen Y myyntimäärä on nolla, kun taas tuotteen X määrä saavuttaa suurimman mahdollisen arvon.

- Harjoitus 2 (Analyyttinen menetelmä: Lagrange-kertoimet)

Etsi ratkaisu (x, y), joka tekee funktion f (x, y) = x ² + 2y ² maksimi alueelta g (x, y) = x ² + y ² - 1 = 0.

Ratkaisu

Se on selvästi epälineaarinen ohjelmointiongelma, koska sekä tavoitefunktio f (x, y) että rajoitus g (x, y) = 0, eivät ole muuttujien x ja y lineaarinen yhdistelmä.

Käytetään Lagrange-kertoimia, mikä vaatii ensin Lagrange-funktion määrittämisen L (x, y, λ):

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

Missä λ on parametri, jota kutsutaan Lagrange-kertoimeksi.

Määritä tavoitefunktion f ääriarvot rajoitusten g (x, y) = 0 antamalla ratkaisualueella seuraavilla vaiheilla:

- Löydä Lagrange-funktion L osittaiset johdannaiset suhteessa x, y, λ.

- Tasaa jokainen johdannainen nollaan.

Tässä näiden toimintojen järjestys:

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

Mahdolliset järjestelmäratkaisut

Tämän järjestelmän mahdollinen ratkaisu on λ = 1 niin, että ensimmäinen yhtälö täyttyy, jolloin y = 0 niin, että toinen on tyytyväinen.

Tämä ratkaisu merkitsee, että x = 1 tai x = -1, jotta kolmas yhtälö täyttyisi. Tällä tavalla on saatu kaksi ratkaisua S1 ja S2:

S1: (x = 1, y = 0)

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

Toinen vaihtoehto on, että λ = 2 siten, että toinen yhtälö täyttyy, y-arvosta riippumatta.

Tässä tapauksessa ainoa tapa saavuttaa ensimmäinen yhtälö on x = 0. Kun otetaan huomioon kolmas yhtälö, on olemassa vain kaksi mahdollista ratkaisua, joita kutsutaan S3: ksi ja S4:

S3: (x = 0, y = 1)

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

Jotta saadaan selville, mikä tai mitkä näistä ratkaisuista maksimoi objektiivifunktion, jatkamme korvaamalla 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

Johtopäätöksenä on, että ratkaisut, jotka maksimoivat f: n, kun x ja y kuuluvat kehään g (x, y) = 0, ovat S3 ja S4.

Arvoparit (x = 0, y = 1) ja (x = 0, y = -1) maksimoivat f (x, y) ratkaisualueella g (x, y) = 0.

- Harjoitus 3 (nollagradientti)

Etsi ratkaisut (x, y) objektiivitoiminnolle:

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

Annetaan olla suurin alueella g (x, y) = x ² + y ² - 1 ≤ 0.

Ratkaisu

Tämä tehtävä on samanlainen kuin tehtävä 2, mutta ratkaisu (tai rajoitus) alue ulottuu kehän g (x, y) = 0 sisäalueelle, ts. Ympyrälle g (x, y) ≤ 0. Tähän sisältyy kehälle ja sen sisäalueelle.

Ratkaisu rajalle on jo määritetty harjoituksessa 2, mutta sisustusaluetta on vielä tutkittava.

Tätä varten on laskettava funktion f (x, y) gradientti ja asetettava nollaksi ääriarvojen löytämiseksi ratkaisualueelta. Tämä vastaa f: n osajohdannaisten laskemista suhteessa x: iin ja y: iin ja asettaminen nollaksi:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Tässä yhtälöjärjestelmässä on ainoa ratkaisu (x = 0, y = 0), joka kuuluu ympyrään g (x, y) ≤ 0.

Tämän arvon korvaaminen funktiolla f tuottaa:

f (0, 0) = 0

Yhteenvetona voidaan todeta, että funktion enimmäisarvo ratkaisualueella on 2 ja se tapahtuu ratkaisualueen rajalla arvoille (x = 0, y = 1) ja (x = 0, y = -1).

Viitteet

1. Avriel, M. 2003. Epälineaarinen ohjelmointi. Dover Publishing.
2. BAZARAA. 1979. Epälineaarinen ohjelmointi. John Wiley & Sons.
3. Bertsekas, D. 1999. Epälineaarinen ohjelmointi: 2. painos. Athena tieteellinen.
4. Nocedal, J. 1999. Numerical Optimization. Springer-Verlag.
5. Wikipedia. Epälineaarinen ohjelmointi. Palautettu osoitteesta: es.wikipedia.com