Problema di programmazione lineare
Ciao a tutti!
Da poco ho iniziato a studiare ricerca operativa all'università. Mi sono imbattuto in questo problema a cui non riesco a dare una soluzione:
Problema
Determinare il valore di t in modo tale che la funzione obiettivo del seguente PPL ha valore massimo nei Punti Soluzione indicati. Giustificare la risposta.
Z= 3x+ty
sbj
x+2y <= 4
x – y <= 1
x,y>=0
Punti Soluzione
1) (0,0)
2) (1,0)
3) (2,1)
4) (0,2)
Non riesco a capire come trovare i valori della t per i diversi punti soluzioni. Ci ho perso molte ore senza arrivare a niente
Non essendo un esercizio per casa non vorrei solamente la soluzione ma anche una spiegazione perchè sono esercizi che possono capitare all'esame.
Grazie dell'aiuto
Da poco ho iniziato a studiare ricerca operativa all'università. Mi sono imbattuto in questo problema a cui non riesco a dare una soluzione:
Problema
Determinare il valore di t in modo tale che la funzione obiettivo del seguente PPL ha valore massimo nei Punti Soluzione indicati. Giustificare la risposta.
Z= 3x+ty
sbj
x+2y <= 4
x – y <= 1
x,y>=0
Punti Soluzione
1) (0,0)
2) (1,0)
3) (2,1)
4) (0,2)
Non riesco a capire come trovare i valori della t per i diversi punti soluzioni. Ci ho perso molte ore senza arrivare a niente
Non essendo un esercizio per casa non vorrei solamente la soluzione ma anche una spiegazione perchè sono esercizi che possono capitare all'esame.
Grazie dell'aiuto
Risposte
Teoricamente, da regolamento, dovresti proporre l'approccio che hai usato tu. In ogni caso non mi sembra un problema difficile, hai disegnato la regione ammissibile? Una volta fatto ciò, di fatto, hai risolto l'esercizio.
NB: Mi sembra evidente che questo esercizio abbia quattro domande cioè ti chiede la $t$ per ciascuno dei 4 punti di ottimo trovati. E' l'interpretazione giusta?
NB: Mi sembra evidente che questo esercizio abbia quattro domande cioè ti chiede la $t$ per ciascuno dei 4 punti di ottimo trovati. E' l'interpretazione giusta?
Ciao e grazie della risposta.
Si, ho disegnato la regione ammissibile e risulta che i vertici del poligono sono esattamente quei punti.
Si, la tua interpetazione è giusta. E' proprio qui che non riesco ad andare avanti....
Si, ho disegnato la regione ammissibile e risulta che i vertici del poligono sono esattamente quei punti.
Si, la tua interpetazione è giusta. E' proprio qui che non riesco ad andare avanti....
"CoCoyN-CB":
Ciao e grazie della risposta.
Si, ho disegnato la regione ammissibile e risulta che i vertici del poligono sono esattamente quei punti.
Si, la tua interpetazione è giusta. E' proprio qui che non riesco ad andare avanti....
Scusa ma a questo punto basta che disegni la funzione obiettivo e applichi la risoluzione grafica. Considera che, a meno che non mi stia sfuggendo qualcosa, la f.o. fondamentalmente può essere di tre tipi:
$z= {(3x-y),(3x+y),(3x):}$
Altri valori di $t$ semplicemente farebbero variare il valore nel punto di ottimo ma non il punto stesso. Quindi, se non mi fosse sfuggito niente, dovresti avere che:
1) $z=3x-y$ (in pratica $t>=0$)
2) mai
3) mai
4) $z=3x-y$ (in pratica $t<=0$)
I punti 2) e 3) dovrebbero non essere mai un ottimo perché il valore del coefficiente della $x$ è positivo quindi la minimizzazione la ottieni sempre muovendoti verso sinistra. Ne consegue che se $t>0$ allora trovi come ottimo il punto 1), se invece $t<0$ trovi il punto 4). Nel caso in cui $t=0$ tutti i punti sullo spigolo di vertici 1), 4) contiene i punti di ottimo.
Grazie mille della risposta 
Sono d'accordo con te in questa cosa: "Altri valori di t semplicemente farebbero variare il valore nel punto di ottimo ma non il punto stesso. Quindi, se non mi fosse sfuggito niente, dovresti avere che"
Quindi mi trovo che le f.o. fondamentali sono quelle 3. Mi hai aperto la mente con questa considerazione
Ma non mi trovo sulla seconda parte:
Tua risposta:
1) z=3x−y (in pratica t≥0)
2) mai
3) mai
4) z=3x−y (in pratica t≤0)
Miei quesiti:
1) Non dovrebbe essere f.o. z=3x+y? dato che t è positiva.
4) La f.o. z=3x−y, non minimizza la z=-2 invece di massimizzare?
2) Il punto 2) (1,0) non ha l'ottimo con f.o. z=3x?
EDIT: Riflettendoci non riesco nemmeno ad essere d'accordo sulle f.o. fondamentali. Penso che a seconda della t, le rette costruite cambiano l'angolo nel piano e quindi a seconda della grandezza dei valori (infatti il simplesso lavora prendndo prima la variabile col valore maggiore) vanno in direzione di uno o un altro vertice.
Grazie.
Sono d'accordo con te in questa cosa: "Altri valori di t semplicemente farebbero variare il valore nel punto di ottimo ma non il punto stesso. Quindi, se non mi fosse sfuggito niente, dovresti avere che"
Quindi mi trovo che le f.o. fondamentali sono quelle 3. Mi hai aperto la mente con questa considerazione
Ma non mi trovo sulla seconda parte:
Tua risposta:
1) z=3x−y (in pratica t≥0)
2) mai
3) mai
4) z=3x−y (in pratica t≤0)
Miei quesiti:
1) Non dovrebbe essere f.o. z=3x+y? dato che t è positiva.
4) La f.o. z=3x−y, non minimizza la z=-2 invece di massimizzare?
2) Il punto 2) (1,0) non ha l'ottimo con f.o. z=3x?
EDIT: Riflettendoci non riesco nemmeno ad essere d'accordo sulle f.o. fondamentali. Penso che a seconda della t, le rette costruite cambiano l'angolo nel piano e quindi a seconda della grandezza dei valori (infatti il simplesso lavora prendndo prima la variabile col valore maggiore) vanno in direzione di uno o un altro vertice.
Grazie.
"CoCoyN-CB":
EDIT: Riflettendoci non riesco nemmeno ad essere d'accordo sulle f.o. fondamentali. Penso che a seconda della t, le rette costruite cambiano l'angolo nel piano e quindi a seconda della grandezza dei valori (infatti il simplesso lavora prendndo prima la variabile col valore maggiore) vanno in direzione di uno o un altro vertice.
Grazie.
Guarda, applicato a questo esercizio non mi sembra che variando le $t$ cambi qualcosa. Sulla generalizzazione di questo concetto non ci metterei la mano sul fuoco! Anzi molto probabilmente è vero il contrario.
Ad esempio: se avessi dovuto massimizare $z=x-2y$ oppure $z=x-y/2$ quindi considerando $t$ sempre il coefficiente di $y$ avresti avuto in un caso $t=-2$ e nell'altro $t=-1/2$ e avresti trovato come ottimi, se non sbaglio, i punti $(1,0)$ e $(1,2)$. Spero di non aver sbagliato a fare il disegno, prova a vedere se ti torna!
Però ritornando all'esercizio che hai proposto credo che quanto ti dicevo funzioni. Tra l'altro solo ora noto come io ho risolto dei problemi di minimizzazione mentre si chiedeva di massimizzare. Il discorso cambia. Finisco il mio discorso per il concetto di minimizzazione (e non di massimizzazione, magari prova a vedere se ti torna, tanto in un futuro di esercizio d'esame potrebbe capitare tanto uno quanto l'altro!).
"CoCoyN-CB":
1) Non dovrebbe essere f.o. z=3x+y? dato che t è positiva.
Si, come vedi c'è un errore di battitura, tra parentesi ho scritto che $t>0$. Sempre riferito alla minimizzazione.
"CoCoyN-CB":
4) La f.o. z=3x−y, non minimizza la z=-2 invece di massimizzare?
Non capisco bene cosa vuoi dire.
"CoCoyN-CB":
2) Il punto 2) (1,0) non ha l'ottimo con f.o. z=3x?
Probabilmente se si doveva massimizzare potresti avere ragione.
Mi dispiace, c'è stato un fraintendimento. Il fatto è che, solitamente, non si risolvono problemi di massimizzazione ma di minimizzazione. Inoltre tu l'hai scritto nel testo ma non quando hai riportato la formulazione.
Si per questo esercizio avevi ragione. Ma sulla generalizzazione di questo concetto effettivamente penso sia come dico io.
Comunque il mio pensiero è che ci fosse un modo "meccanico" per trovare le t perfette per i punti. Invece sono d'accordo con te che trovandole un po aiutandoti dal disegno è molto più facile.
Grazie mille per l'aiuto
Comunque il mio pensiero è che ci fosse un modo "meccanico" per trovare le t perfette per i punti. Invece sono d'accordo con te che trovandole un po aiutandoti dal disegno è molto più facile.
Grazie mille per l'aiuto
"CoCoyN-CB":
Si per questo esercizio avevi ragione. Ma sulla generalizzazione di questo concetto effettivamente penso sia come dico io.
Si, infatti ti dovrei aver fatto un esempio nel caso di massimizzazione nel quale il discorso di "per ogni $t$" non vale. Non voleva essere mia intenzione generalizzare a tutto il mondo della PL. In questo esercizio (nel caso di minimizzazione) però è chiaro sia così.
"CoCoyN-CB":
Comunque il mio pensiero è che ci fosse un modo "meccanico" per trovare le t perfette per i punti. Invece sono d'accordo con te che trovandole un po aiutandoti dal disegno è molto più facile.
Non credo esista. Potresti provare a risolvere dei sistemi di disequazioni nei quali valuti, tenendo come incognita $t$, il valore della f.o. per ogni spigolo della regione ammissibile. Non ho mai risolto in questo modo, però forse potrebbe funzionare. Magari provaci ed eventualmente posta il risultato.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo