Metodi di programmazione non lineari ed esercizi

IL Programmazione non lineare È il processo di ottimizzazione di una funzione che dipende da diverse variabili indipendenti, che a loro volta sono soggette a restrizioni.

Se una o più delle restrizioni o se la funzione per massimizzare o minimizzare (chiamata Funzione obiettivo), non è espresso come una combinazione lineare delle variabili, quindi esiste un problema di programmazione non lineare.

Figura 1. Problema di programmazione non lineare (NLP). in cui G è la funzione (non lineare) da ottimizzare nella regione verde, determinata dalle restrizioni. Fonte: f. Zapata.

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

Ad esempio, il metodo ben noto non può essere utilizzato Simplex, che si applica solo quando la funzione e le restrizioni oggettive sono tutte una combinazione lineare delle variabili del problema.

[TOC]

Metodi di programmazione lineari

Per la programmazione non lineare i metodi principali da utilizzare sono: 

1.- Metodi grafici.

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

3.- Calcolo del gradiente per esplorare le estremità della funzione obiettivo.

4.- Il metodo dei passaggi discendenti, per trovare i punti del gradiente zero.

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 è ciò che può essere visto nella Figura 2:

figura 2. Esempio di problema non lineare con restrizioni non lineari e la sua soluzione grafica. Fonte: f. Zapata.

Esercizi

- Esercizio 1 (metodo grafico)

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

Può servirti: binomiale coniugata: come viene risolto, esempi, esercizi

G = 2 (x - 2)² + 3 (e - 3)²

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

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

Determina i valori di xey che producono il guadagno massimo.

Figura 3. Il guadagno dell'azienda può essere matematicamente modellato per trovare il guadagno massimo mediante programmazione non lineare. Fonte: Pixabay.

Soluzione 

In questo problema la funzione obiettivo non è lineare, mentre le disuguaglianze che definiscono le restrizioni sono. È un problema di Programmazione non lineare.

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

Innanzitutto, la regione della soluzione verrà determinata, che è data dalle restrizioni.

Come x≥0; Y≥0, la soluzione deve essere cerca nel primo quadrante del piano XY, ma anche se si deve soddisfare che x + y ≤ 7, la soluzione è nel semiplano inferiore della linea x + y = 7.

La regione della soluzione è l'intersezione del primo quadrante con il semiplano inferiore della linea, che dà origine a una regione triangolare in cui si trova la soluzione. È lo stesso come 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 il centro (2,3).

L'ellisse è mostrata nella Figura 1 per diversi valori G. Un valore più elevato di g, maggiore guadagno.

Ci sono soluzioni che appartengono alla regione, ma non danno il valore massimo G, mentre altre, come G = 92.4, sono fuori dalla zona verde, cioè la zona di soluzione.

Quindi, il valore massimo di G, in modo tale che X e y appartiene alla regione della soluzione corrisponde a: 

Può servirti: probabilità teorica: come tirarlo fuori, esempi, esercizi

G = 77 (guadagno massimo), che si verifica per x = 7 e y = 0. 

È interessante notare che il guadagno massimo si verifica quando la quantità di vendite di prodotti ed è nullo, mentre la quantità di prodotto X raggiunge il massimo valore possibile.

- Esercizio 2 (Metodo analitico: moltiplicatori di Lagrange) 

Trova la soluzione (x, y) che rende la funzione f (x, y) = x² + 2 e² essere massimo nella regione g (x, y) = x² + E² - 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 xey.

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

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

Dove λ è un parametro chiamato Moltiplicatore di Lagrange.

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

-Trova i derivati ​​parziali della funzione di Lagrange L, rispetto a x, y, λ.

-Zero ogni derivato.

Qui la sequenza di queste operazioni:

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

Possibili soluzioni di sistema

Una possibile soluzione di questo sistema è λ = 1 per soddisfare la prima equazione, nel qual caso y = 0 per soddisfare la seconda.

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

S1: (x = 1, y = 0)

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

L'altra alternativa è che λ = 2 per la seconda equazione da soddisfare, indipendentemente dal valore e.

Può servirti: limite di fermat: ciò che consiste ed esercitazioni risolte

In questo caso, l'unico modo per soddisfare la prima equazione è che 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 sapere quale o quale di queste soluzioni massimizza la funzione obiettivo, procedere 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² + ventuno)² = 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) y (x = 0, y = -1) massimizzano f (x, y) nella regione della soluzione g (x, y) = 0.

- Esercizio 3 (gradiente null)

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

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

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

Soluzione

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

La soluzione di confine era già determinata nell'esercizio 2, ma è necessario esplorare la regione interna.

Per fare ciò, il gradiente della funzione f (x, y) deve essere calcolato e uguale a zero, per cercare valori estremi nella regione della soluzione. Ciò equivale a calcolare i derivati ​​parziali di F rispetto a X e rispettivamente e equalizzare 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.

Sostituzione di questo valore nei risultati della funzione F:

f (0, 0) = 0

In conclusione, il valore massimo che prende la funzione nella regione della soluzione è 2 e si verifica sul bordo della regione della soluzione, per valori (x = 0, y = 1) y (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. Ottimizzazione numerica. Springer-Verlag.
5. Wikipedia. Programmazione non lineare. Recuperato da: è.Wikipedia.com