NIET-LINEAIR PROGRAMMEREN: METHODEN EN OEFENINGEN - WISKUNDE - 2026

De niet-lineaire programmering is het proces van het optimaliseren van een functie die afhangt van verschillende onafhankelijke variabelen, die op hun beurt onderhevig zijn aan beperkingen.

Als een of meer van de beperkingen, of als de functie die moet worden gemaximaliseerd of geminimaliseerd (de doelfunctie genoemd), niet wordt uitgedrukt als een lineaire combinatie van de variabelen, dan heb je een niet-lineair programmeerprobleem.

Figuur 1. Niet-lineair programmeerprobleem (NLP). waarbij G de (niet-lineaire) functie is om te optimaliseren in het groene gebied, bepaald door de beperkingen. Bron: F. Zapata.

En daarom kunnen de procedures en methoden van lineair programmeren niet worden gebruikt.

De bekende Simplex-methode kan bijvoorbeeld niet worden gebruikt, wat alleen van toepassing is als de doelfunctie en de beperkingen allemaal lineaire combinaties zijn van de variabelen in het probleem.

Lineaire programmeermethoden

Voor niet-lineaire programmeerproblemen zijn de belangrijkste te gebruiken methoden:

1. - Grafische methoden.

2.- Lagrange-multipliers om de grens van het oplossingsgebied te verkennen.

3.- Berekening van de gradiënt om extremen van de doelfunctie te onderzoeken.

4.- De methode van aflopende stappen om de nulgradiëntpunten te vinden.

5.- Gewijzigde methode van de Lagrange-vermenigvuldigers (met de voorwaarde Karush-Kuhn-Tucker).

Voorbeeld van oplossing met grafische methode

Een voorbeeld van een oplossing met de grafische methode is te zien in figuur 2:

Figuur 2. Voorbeeld van een niet-lineair probleem met niet-lineaire beperkingen en de grafische oplossing. Bron: F. Zapata.

Opdrachten

- Oefening 1 (Grafische methode)

De winst G van een bepaald bedrijf is afhankelijk van de verkochte hoeveelheid product X en de verkochte hoeveelheid product Y, daarnaast wordt de winst bepaald door de volgende formule:

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

Van de bedragen X en Y is bekend dat ze de volgende beperkingen hebben:

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

Bepaal de waarden van X en Y die de maximale versterking produceren.

Figuur 3. De winst van een bedrijf kan wiskundig worden gemodelleerd om de maximale winst te vinden met behulp van niet-lineaire programmering. Bron: Pixabay.

Oplossing

In dit probleem is de doelfunctie niet-lineair, terwijl de ongelijkheden die de beperkingen bepalen, dat wel zijn. Dit is een niet-lineair programmeerprobleem.

Voor de oplossing van dit probleem wordt de grafische methode gekozen.

Eerst wordt het oplossingsgebied bepaald, dat wordt bepaald door de beperkingen.

Zoals X≥0; Y≥0, de oplossing moet gevonden worden in het eerste kwadrant van het XY-vlak, maar aangezien het ook zo moet zijn dat X + Y ≤ 7, zit de oplossing in het onderste halve vlak van de lijn X + Y = 7.

Het oplossingsgebied is het snijpunt van het eerste kwadrant met het onderste halve vlak van de lijn, wat resulteert in een driehoekig gebied waar de oplossing wordt gevonden. Het is hetzelfde als aangegeven in figuur 1.

Aan de andere kant kan de versterking G ook worden weergegeven in het cartesische vlak, aangezien de vergelijking die van een ellips met middelpunt (2,3) is.

De ellips wordt getoond in Figuur 1 voor verschillende waarden van G. Hoe hoger de waarde van G, hoe groter de versterking.

Er zijn oplossingen die tot de regio behoren, maar niet de maximale G-waarde geven, terwijl andere, zoals G = 92,4, buiten de groene zone liggen, dat wil zeggen de oplossingszone.

Dan komt de maximale waarde van G, zodat X en Y tot het oplossingsgebied behoren, overeen met:

G = 77 (maximale versterking), die wordt gegeven voor X = 7 en Y = 0.

Interessant is dat de maximale winst optreedt wanneer de verkoophoeveelheid van product Y nul is, terwijl de hoeveelheid product X de hoogst mogelijke waarde bereikt.

- Oefening 2 (Analytische methode: Lagrange-vermenigvuldigers)

Zoek de oplossing (x, y) die de functie f (x, y) = x ² + 2y ² maximaal maakt in de regio g (x, y) = x ² + y ² - 1 = 0.

Oplossing

Het is duidelijk een niet-lineair programmeerprobleem, aangezien zowel de doelfunctie f (x, y) als de beperking g (x, y) = 0 geen lineaire combinatie zijn van de variabelen x en y.

De Lagrange-vermenigvuldigingsmethode zal worden gebruikt, waarvoor eerst de Lagrange-functie L (x, y, λ) moet worden gedefinieerd:

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

Waar λ een parameter is die de Lagrange-vermenigvuldiger wordt genoemd.

Om de extreme waarden van de doelfunctie f te bepalen, in het oplossingsgebied gegeven door de beperking g (x, y) = 0, volgt u deze stappen:

-Vind de partiële afgeleiden van de Lagrange-functie L, met betrekking tot x, y, λ.

- Stel elke afgeleide in op nul.

Hier de volgorde van deze bewerkingen:

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

Mogelijke systeemoplossingen

Een mogelijke oplossing van dit systeem is λ = 1 zodat aan de eerste vergelijking wordt voldaan, in welk geval y = 0 zodat aan de tweede wordt voldaan.

Deze oplossing houdt in dat x = 1 of x = -1 voor de derde vergelijking waaraan moet worden voldaan. Op deze manier zijn twee oplossingen S1 en S2 verkregen:

S1: (x = 1, y = 0)

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

Het andere alternatief is dat λ = 2 zodat aan de tweede vergelijking wordt voldaan, ongeacht de y-waarde.

In dit geval is x = 0 de enige manier om aan de eerste vergelijking te voldoen. Gezien de derde vergelijking, zijn er slechts twee mogelijke oplossingen, die we S3 en S4 zullen noemen:

S3: (x = 0, y = 1)

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

Om erachter te komen welke of welke van deze oplossingen de doelfunctie maximaliseren, gaan we verder met het substitueren in 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

We concluderen dat de oplossingen die f maximaliseren, wanneer x en y tot de omtrek g (x, y) = 0 behoren, S3 en S4 zijn.

De paren waarden (x = 0, y = 1) en (x = 0, y = -1) maximaliseren f (x, y) in het oplossingsgebied g (x, y) = 0.

- Oefening 3 (nulgradiënt)

Vind oplossingen (x, y) voor de doelfunctie:

f (X, Y) = X ² + 2 Y ²

Laat het maximum zijn in het gebied g (x, y) = x ² + y ² - 1 ≤ 0.

Oplossing

Deze oefening is vergelijkbaar met oefening 2, maar het oplossings- (of beperkings) gebied strekt zich uit tot het binnengebied van de omtrek g (x, y) = 0, dat wil zeggen tot de cirkel g (x, y) ≤ 0. Dit omvat naar de omtrek en het binnenste gebied.

De oplossing aan de grens is al bepaald in opgave 2, maar het binnengebied moet nog worden verkend.

Om dit te doen, moet de gradiënt van de functie f (x, y) worden berekend en gelijk aan nul worden ingesteld om extreme waarden in het oplossingsgebied te vinden. Dit komt overeen met het berekenen van de partiële afgeleiden van f ten opzichte van respectievelijk x en y en het gelijk stellen aan nul:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Dit stelsel van vergelijkingen heeft de enige oplossing (x = 0, y = 0) die behoort tot de cirkel g (x, y) ≤ 0.

Het vervangen van deze waarde in de functie f resulteert:

f (0, 0) = 0

Concluderend, de maximale waarde die de functie aanneemt in het oplossingsgebied is 2 en komt voor op de grens van het oplossingsgebied, voor de waarden (x = 0, y = 1) en (x = 0, y = -1) .

Referenties

1. Avriel, M. 2003. Niet-lineaire programmering. Dover Publishing.
2. Bazaraa. 1979. Niet-lineaire programmering. John Wiley & Sons.
3. Bertsekas, D. 1999. Niet-lineaire programmering: 2e editie. Athena Scientific.
4. Nocedal, J. 1999. Numerieke optimalisatie. Springer-Verlag.
5. Wikipedia. Niet-lineaire programmering. Hersteld van: es.wikipedia.com