PROGRAMMAZIONE NON LINEARE: METODI ED ESERCIZI - MATEMATICA - 2026

La programmazione non lineare è il processo di ottimizzazione di una funzione che dipende da più variabili indipendenti, che a loro volta sono soggette a restrizioni.

Se una o più restrizioni, o se la funzione da massimizzare o ridurre a icona (chiamata funzione obiettivo) non è espressa come una combinazione lineare delle variabili, allora hai un problema di programmazione non lineare.

Figura 1. Problema di programmazione non lineare (PNL). dove G è la funzione (non lineare) da ottimizzare nella regione verde, determinata dai vincoli. Fonte: F. Zapata.

E quindi le procedure e i metodi di programmazione lineare non possono essere utilizzati.

Ad esempio, il noto metodo Simplex non può essere utilizzato, che si applica solo quando la funzione obiettivo ei vincoli sono tutte combinazioni lineari delle variabili nel problema.

Metodi di programmazione lineare

Per problemi di programmazione non lineare i principali metodi da utilizzare sono:

1.- Metodi grafici.

2.- Moltiplicatori di Lagrange per esplorare il confine della regione della soluzione.

3.- Calcolo del gradiente per esplorare gli estremi della funzione obiettivo.

4.- Il metodo dei passaggi discendenti, per trovare i punti di gradiente nulli.

5.- Metodo modificato dei moltiplicatori di Lagrange (con la condizione di Karush-Kuhn-Tucker).

Esempio di soluzione con metodo grafico

Un esempio di soluzione con il metodo grafico è quello che si può vedere in figura 2:

Figura 2. Esempio di un problema non lineare con restrizioni non lineari e sua soluzione grafica. Fonte: F. Zapata.

esercizi

- Esercizio 1 (Metodo grafico)

Il profitto G di una certa azienda dipende dalla quantità venduta del prodotto X e dalla quantità venduta del prodotto Y, inoltre, il profitto è determinato dalla seguente formula:

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

È noto che gli importi X e Y hanno le seguenti restrizioni:

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

Determina i valori di X e Y che producono il massimo guadagno.

Figura 3. Il profitto di un'azienda può essere modellato matematicamente per trovare il massimo profitto utilizzando la programmazione non lineare. Fonte: Pixabay.

Soluzione

In questo problema la funzione obiettivo è non lineare, mentre le disuguaglianze che definiscono i vincoli lo sono. Questo è un problema di programmazione non lineare.

Per la soluzione di questo problema verrà scelto il metodo grafico.

In primo luogo, verrà determinata la regione della soluzione, che è data dalle restrizioni.

Come X≥0; Y≥0, la soluzione va trovata nel primo quadrante del piano XY, ma poiché deve anche essere vero che X + Y ≤ 7, la soluzione è nel semipiano inferiore della retta X + Y = 7.

La regione della soluzione è l'intersezione del primo quadrante con il semipiano inferiore della linea, che risulta in una regione triangolare in cui si trova la soluzione. È lo stesso indicato nella figura 1.

D'altra parte, il guadagno G può essere rappresentato anche nel piano cartesiano, poiché la sua equazione è quella di un'ellisse con centro (2,3).

L'ellisse è mostrata nella Figura 1 per vari valori di G. Maggiore è il valore di G, maggiore è il guadagno.

Esistono soluzioni che appartengono alla regione, ma non danno il valore G massimo, mentre altre, come G = 92,4, sono fuori dalla zona verde, cioè dalla zona della soluzione.

Quindi, il valore massimo di G, tale che X e Y appartengono alla regione della soluzione corrisponde a:

G = 77 (guadagno massimo), che è dato per X = 7 e Y = 0.

È interessante notare che il profitto massimo si verifica quando l'importo delle vendite del prodotto Y è zero, mentre la quantità del prodotto X raggiunge il valore più alto possibile.

- Esercizio 2 (Metodo analitico: moltiplicatori di Lagrange)

Trova la soluzione (x, y) che rende la funzione f (x, y) = x ² + 2y ² massimo nella regione g (x, y) = x ² + y ² - 1 = 0.

Soluzione

È chiaramente un problema di programmazione non lineare, poiché sia ​​la funzione obiettivo f (x, y) che la restrizione g (x, y) = 0, non sono una combinazione lineare delle variabili x e y.

Verrà utilizzato il metodo dei moltiplicatori di Lagrange, che richiede prima di definire la funzione di Lagrange L (x, y, λ):

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

Dove λ è un parametro chiamato moltiplicatore di Lagrange.

Per determinare i valori estremi della funzione obiettivo f, nella regione della soluzione data dalla restrizione g (x, y) = 0, seguire questi passaggi:

-Trovare le derivate parziali della funzione di Lagrange L, rispetto a x, y, λ.

-Equalizza ogni derivata a zero.

Ecco la sequenza di queste operazioni:

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

Possibili soluzioni impiantistiche

Una possibile soluzione di questo sistema è λ = 1 in modo che la prima equazione sia soddisfatta, nel qual caso y = 0 in modo che la seconda sia soddisfatta.

Questa soluzione implica che x = 1 o x = -1 perché la terza equazione sia soddisfatta. In questo modo si sono ottenute due soluzioni S1 e S2:

S1: (x = 1, y = 0)

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

L'altra alternativa è che λ = 2 in modo che la seconda equazione sia soddisfatta, indipendentemente dal valore y.

In questo caso, l'unico modo per soddisfare la prima equazione è per x = 0. Considerando la terza equazione, ci sono solo due possibili soluzioni, che chiameremo S3 e S4:

S3: (x = 0, y = 1)

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

Per scoprire quale o quale di queste soluzioni massimizzano la funzione obiettivo, procediamo a sostituire 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

Concludiamo che le soluzioni che massimizzano f, quando xey appartengono alla circonferenza g (x, y) = 0 sono S3 e S4.

Le coppie di valori (x = 0, y = 1) e (x = 0, y = -1) massimizzano f (x, y) nella regione della soluzione g (x, y) = 0.

- Esercizio 3 (gradiente nullo)

Trova soluzioni (x, y) per la funzione obiettivo:

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

Sia massimo nella regione g (x, y) = x ² + y ² - 1 ≤ 0.

Soluzione

Questo esercizio è simile all'esercizio 2, ma la regione di soluzione (o restrizione) si estende alla regione interna della circonferenza g (x, y) = 0, vale a dire al cerchio g (x, y) ≤ 0. Ciò include alla circonferenza e alla sua regione interna.

La soluzione al confine è già stata determinata nell'esercizio 2, ma resta da esplorare la regione interna.

Per fare ciò, il gradiente della funzione f (x, y) deve essere calcolato e posto uguale a zero, per trovare valori estremi nella regione della soluzione. Ciò equivale a calcolare le derivate parziali di f rispetto a xey rispettivamente ea impostarlo uguale a zero:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Questo sistema di equazioni ha l'unica soluzione (x = 0, y = 0) che appartiene al cerchio g (x, y) ≤ 0.

Sostituendo questo valore nella funzione f si ottiene:

f (0, 0) = 0

In conclusione, il valore massimo che la funzione assume nella regione della soluzione è 2 e si verifica al confine della regione della soluzione, per i valori (x = 0, y = 1) e (x = 0, y = -1) .

Riferimenti

1. Avriel, M. 2003. Programmazione non lineare. Dover Publishing.
2. Bazaraa. 1979. Programmazione non lineare. John Wiley & Sons.
3. Bertsekas, D. 1999. Programmazione non lineare: 2a edizione. Athena Scientific.
4. Nocedal, J. 1999. Numerical Optimization. Springer-Verlag.
5. Wikipedia. Programmazione non lineare. Estratto da: es.wikipedia.com