Programmazione lineare con parametro
Salve mi servirebbe capire come risolvere questo esercizio di programmazione lineare, il professore ci ha spiegato un metodo che sono riuscito a capire solo fino a un certo punto.
max f (x, y) = x + 2y
sub
x+ay<=1, a>=0
x>=0
y>= 0
Il metodo è: in questo caso di porre a = 0, poi a = ad un valore che faccia in modo che i due coefficienti angolari siano uguali (funzione e vincolo), poi a compreso tra 0 e il valore del coefficiente angolare, e infine a maggiore del coefficiente angolare.
Nel caso di questo esercizio il valore è 2.
Quindi:
per a = 0 non abbiamo massimi per il teorema di Wierstrass,
per a = 2 il massimo è lo stesso vincolo (con x compreso tra 0 e 1)
per 0
Stessa cosa per a>2 in cui il punto di massimo dovrebbe essere (0; 1). Anche qui non riesco a capire come arrivarci..
max f (x, y) = x + 2y
sub
x+ay<=1, a>=0
x>=0
y>= 0
Il metodo è: in questo caso di porre a = 0, poi a = ad un valore che faccia in modo che i due coefficienti angolari siano uguali (funzione e vincolo), poi a compreso tra 0 e il valore del coefficiente angolare, e infine a maggiore del coefficiente angolare.
Nel caso di questo esercizio il valore è 2.
Quindi:
per a = 0 non abbiamo massimi per il teorema di Wierstrass,
per a = 2 il massimo è lo stesso vincolo (con x compreso tra 0 e 1)
per 0
Stessa cosa per a>2 in cui il punto di massimo dovrebbe essere (0; 1). Anche qui non riesco a capire come arrivarci..
Risposte
Io ti consiglio di procedere, dato che siamo in $RR^2$, facendo un bel disegno e risolvendo per via grafica.
Per disegnare la funzione obiettivo basta fissare un valore costante e scriverla. La massimizzazione/minimizzazione la si otterrà muovendo idealmente la funzione (in questo caso la retta) verso il basso o verso l'alto a seconda dei casi. Nel nostro caso la retta tenderà a muoversi verso l'alto poiché stiamo massimizzando e quindi, idealmente, vorremmo un $x$ e un $y$ "quanto più grandi possibile".
In questo caso io scriverei:
$x+2y=c$
Ad esempio quindi, con $c=1$, ottengo che, nel piano cartesiano, la retta risulta essere: $y=1/2 - 1/2x$ come riportato nel disegno. [geogebra]
Fatto questo disegni anche i vincoli, ovviamente al variare di $a$. Una scelta logica sarà analizzare i tre casi in cui il variare di $a$ porta (almeno intuitivamente) a risultati diversi. Ovvero studi i casi:
$i)$ $ a>2$
$ii)$ $ a<2$
$iii)$ $ a=2$
Dati gli altri vincoli l'unica regione interessante è il primo quadrante perché, escluso il vincolo che dipende da $a$, rappresenta la regione ammissibile.
Quindi:
$i)$ $text(se ) a>2$ allora la retta intersecherà l'asse $x$ in $x=1$ mentre intersecherà l'asse $y$ in $y=1/a<1/2$ ovvero la retta ha una pendenza minore rispetto alla funzione obiettivo.
[geogebra]
Quindi, traslando idealmente la funzione obiettivo, si trova che "l'ultimo punto" che essa interseca è l'ottimo. In questo caso si ha che l'ottimo è in $(x,y)=(1,0)$
[geogebra]
$ii)$ $text(se ) a<2$ allora la retta intersecherà l'asse $x$ in $x=1$ mentre l'asse $y$ in $y=1/a>1/2$ ovvero il vincolo ha una pendenza maggiore rispetto alla funzione obiettivo.
[geogebra]
L'ottimo lo si ricava graficamente e sarà in $(x,y)=(0,1/a)$, come si vede zoomando in tale punto.
[geogebra]
$iii)$ $text(se ) a=2$ allora il vincolo sarà parallelo alla funzione obiettivo quindi tutti i punti del vincolo per $x>=0, y>=0$ sono soluzioni ottime del problema. Ovvero saranno proprio gli $(x,y) in {x>=0, y>=0, x+ay=1}$
[geogebra]
Riepilogando ottengo che:
$(x^**,y^**)={((0,1/a),if 0=0 text( ) y>=0),((1,0),if a>2 ) :}$
Come dicevi tu, se $a=0$ allora il problema è illimitato perché si può prendere un $y$ grande quanto si vuole (e quindi $y to oo$) poiché l'unico vincolo che lo riguarda diventa $y>=0$.
Mi sembra che i risultati siano coerenti con quelli sugeriti dal tuo professore. Spero tu abbia capito il mio metodo che poi dovrebbe essere molto simile a quello del professore.
Per disegnare la funzione obiettivo basta fissare un valore costante e scriverla. La massimizzazione/minimizzazione la si otterrà muovendo idealmente la funzione (in questo caso la retta) verso il basso o verso l'alto a seconda dei casi. Nel nostro caso la retta tenderà a muoversi verso l'alto poiché stiamo massimizzando e quindi, idealmente, vorremmo un $x$ e un $y$ "quanto più grandi possibile".
In questo caso io scriverei:
$x+2y=c$
Ad esempio quindi, con $c=1$, ottengo che, nel piano cartesiano, la retta risulta essere: $y=1/2 - 1/2x$ come riportato nel disegno. [geogebra]
Fatto questo disegni anche i vincoli, ovviamente al variare di $a$. Una scelta logica sarà analizzare i tre casi in cui il variare di $a$ porta (almeno intuitivamente) a risultati diversi. Ovvero studi i casi:
$i)$ $ a>2$
$ii)$ $ a<2$
$iii)$ $ a=2$
Dati gli altri vincoli l'unica regione interessante è il primo quadrante perché, escluso il vincolo che dipende da $a$, rappresenta la regione ammissibile.
Quindi:
$i)$ $text(se ) a>2$ allora la retta intersecherà l'asse $x$ in $x=1$ mentre intersecherà l'asse $y$ in $y=1/a<1/2$ ovvero la retta ha una pendenza minore rispetto alla funzione obiettivo.
[geogebra]
Quindi, traslando idealmente la funzione obiettivo, si trova che "l'ultimo punto" che essa interseca è l'ottimo. In questo caso si ha che l'ottimo è in $(x,y)=(1,0)$
[geogebra]
$ii)$ $text(se ) a<2$ allora la retta intersecherà l'asse $x$ in $x=1$ mentre l'asse $y$ in $y=1/a>1/2$ ovvero il vincolo ha una pendenza maggiore rispetto alla funzione obiettivo.
[geogebra]
L'ottimo lo si ricava graficamente e sarà in $(x,y)=(0,1/a)$, come si vede zoomando in tale punto.
[geogebra]
$iii)$ $text(se ) a=2$ allora il vincolo sarà parallelo alla funzione obiettivo quindi tutti i punti del vincolo per $x>=0, y>=0$ sono soluzioni ottime del problema. Ovvero saranno proprio gli $(x,y) in {x>=0, y>=0, x+ay=1}$
[geogebra]
Riepilogando ottengo che:
$(x^**,y^**)={((0,1/a),if 0
Come dicevi tu, se $a=0$ allora il problema è illimitato perché si può prendere un $y$ grande quanto si vuole (e quindi $y to oo$) poiché l'unico vincolo che lo riguarda diventa $y>=0$.
Mi sembra che i risultati siano coerenti con quelli sugeriti dal tuo professore. Spero tu abbia capito il mio metodo che poi dovrebbe essere molto simile a quello del professore.
Grazie mille chiaro e preciso
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo