Risoluzione grafica
Ciao a tutti!
Sto iniziando a studiare ricerca operativa per un esame universitario.
Non riesco a capire come si risolve graficamente un problema di programmazione lineare.
Nell'esempio svolto che allego non capisco perchè le coordinate siano [2,0] [0,1] e [-2,0] [0,1]
Vi prego, illuminatemi perchè non riesco ad andare avanti
Grazir
Sto iniziando a studiare ricerca operativa per un esame universitario.
Non riesco a capire come si risolve graficamente un problema di programmazione lineare.
Nell'esempio svolto che allego non capisco perchè le coordinate siano [2,0] [0,1] e [-2,0] [0,1]
Vi prego, illuminatemi perchè non riesco ad andare avanti
Grazir
Risposte
Risolvere graficamente un problema (semplice) di programmazione lineare è semplicissimo.
In pratica i passi sono i seguenti:
1) Rappresentare la regione ammissibile
2) Rappresentare la funzione obiettivo (f.o.) per un qualsiasi valore di $z$. Serve solamente per poterla rappresentare graficamente (altrimenti avresti tre variabili: $z, x_1, x_2$. Verificare "in quale direzione" la funzione obiettivo viene minimizzata (e quindi in quale massimizzata)
3) "Muovere" la f.o. sulla rappresentazione grafica.
NB: Ti devi sempre ricordare che è possibile dimostrare che in una regione ammissibile convessa un punto di ottimo si trova sempre su un vertice (o meglio su uno spigolo).
Applicando quei tre passi al tuo problema si ha:
1) Rappresenti i vincoli: evidentemente $x_2>=0$ e poi gli altri due. Si vede che, essendo disequazioni e considerando il tipo ($>= , <=$), si ottiene proprio la regione rappresentata. Per disegnarla ti consiglio di disegnare i vincoli come se fossero equazioni (quindi rette) e poi prendere un punto qualsiasi fuori da queste rette e vedere se verifica la disequazione. Se risultasse ammissibile allora "da quel lato" della retta avresti il semipiano con i punti ammissibili, altrimenti il semipiano con i punti ammssibili sarebbe l'altro. Facendolo per ogni vincolo ottieni la regione ammissibile, questa può: non esistere, essere limitata, essere illimitata. Evidentemente in questo caso è limitata.
2)Rappresenti la funzione obiettivo: semplicemente prendi la funzione obiettivo e poi poni $z=k$ dove $k$ è un valore qualsiasi che vuoi tu. Serve solamente per poter rappresentare la funzione in quanto in questo modo le uniche variabili sono $x_1 , x_2$. Ad esempio prova con $z=0$. In questo caso avrai: $2x_1 + x_2=0$. In questo modo puoi rappresentare la f.o. per una coppia di valori $(x_1, x_2)$. Tutte le altre rette rappresentanti la f.o. (per altri valori di $z$) saranno parallele a quella disegnata. A questo punto vedi in che verso viene minimizzata la f.o.. Per capire quale è questa direzione basta che consideri il gradiente della f.o.. In questo caso hai $grad z= (2,1)$. Ne consegue che se $x_1$ e $x_2$ crescono allora f.o. cresce mentre se diminuiscono allora f.o. diminuisce. Questo che vuol dire? In pratica sulla rappresentazione grafica che hai disegnato (quella per $z=0$) ti permette di disegnare una freccetta. Questa freccetta indicherà in che verso muoverti e la otterrai dal gradiente. In pratica avrai che muovendoti verso destra (ovvero crescono sia $x_1$ sia $x_2$) starai massimizzando mentre muovendoti verso sinistra (ovvero decrescono sia $x_1$ sia $x_2$) starai minimizzando.
3) A seconda se l'esercizio è di minimizzazione o di massimizzazione metterai sul disegno della f.o. la freccetta giusta. Vediamo prima il caso della minimizzazione e poi quello della massimizzazione.
3.1) Minimizzazione: La freccetta (come detto in 2) ) è rivolta verso sinistra. In pratica se muoverai la f.o. verso sinistra troverai di volta in volta coppie di $(x_1, x_2)$ che restituiscono valori di f.o. sempre più piccoli. Ovviamente se disegni graficamente altre rette (per diversi valori di z) avrai che sulle singole rette tutte le coppie di $(x_1, x_2)$ restituiranno punti aventi stesso valore della f.o.. Ora la domanda che ti dovresti porre è: quale è il minimo del mio problema? La risposta te la puoi dare semplicemente muovendo verso la direzione che la freccetta ti indica la stessa f.o.. L'ultimo punto ammissibile (ovvero appartenente alla regione ammissibile) che questa incontra sarà il minimo che cercavi.
Potrebbe accadere che, per qualche motivo, hai scelto un valore di $z$ per rappresentare la f.o. che è più piccolo del minimo (in questo caso capita se scegli ad es. $z=-3$). In questo caso (lo vedi graficamente), muovendo la f.o. nella direzione della freccetta non incontrerai mai la regione ammissibile, non vuol dire che il minimo non esiste. In questo caso devi muovere la f.o. nel verso opposto e il minimo sarà il primo punto ammissibile che incontrerai. Se non ti fosse chiaro il perché allora rappresenta la f.o. per una nuova coppia $(x_1, x_2)$ per i quali la f.o. intercetta la regione ammissibile e applica quello che ti ho detto in precedenza. Vedrai che il risultato sarà proprio lo stesso.
3.2) Massimizzazione: La freccetta (come detto in 2) ) è rivolta verso destra. In pratica se muoverai la f.o. verso destra troverai di volta in volta coppie di $(x_1, x_2)$ che restituiscono valori di f.o. sempre più grandi. Ovviamente se disegni graficamente altre rette (per diversi valori di z) avrai che sulle singole rette tutte le coppie di $(x_1, x_2)$ restituiranno punti aventi stesso valore della f.o.. Ora la domanda che ti dovresti porre è: quale è il massimo del mio problema? La risposta te la puoi dare semplicemente muovendo verso la direzione che la freccetta ti indica la stessa f.o.. L'ultimo punto ammissibile che questa incontra sarà il massimo che cercavi. Sarà diverso dal minimo perché ti stai muovendo nella direzione opposta (in pratica il metodo per trovarlo è lo stesso, cambia la direzione verso la quale sposti la f.o.).
Potrebbe accadere che, per qualche motivo, hai scelto un valore di $z$, per rappresentare la f.o., che è più grande del massimo (in questo caso capita se scegli ad es. $z=3$). In questo caso (lo vedi graficamente), muovendo la f.o. nella direzione della freccetta non incontrerai mai la regione ammissibile, non vuol dire che il massimo non esiste. In questo caso devi muovere la f.o. nel verso opposto e il massimo sarà il primo punto ammissibile che incontrerai. Se non ti fosse chiaro il perché allora rappresenta la f.o. per una nuova coppia $(x_1, x_2)$ per i quali f.o. intercetta la regione ammissibile e applica quello che ti ho detto in precedenza. Vedrai che il risultato sarà proprio lo stesso.
Spero di essere stato sufficientemente chiaro, se non hai capito qualcosa o hai qualche dubbio (magari mi è sfuggita una stupidaggine!) chiedi pure!
In pratica i passi sono i seguenti:
1) Rappresentare la regione ammissibile
2) Rappresentare la funzione obiettivo (f.o.) per un qualsiasi valore di $z$. Serve solamente per poterla rappresentare graficamente (altrimenti avresti tre variabili: $z, x_1, x_2$. Verificare "in quale direzione" la funzione obiettivo viene minimizzata (e quindi in quale massimizzata)
3) "Muovere" la f.o. sulla rappresentazione grafica.
NB: Ti devi sempre ricordare che è possibile dimostrare che in una regione ammissibile convessa un punto di ottimo si trova sempre su un vertice (o meglio su uno spigolo).
Applicando quei tre passi al tuo problema si ha:
1) Rappresenti i vincoli: evidentemente $x_2>=0$ e poi gli altri due. Si vede che, essendo disequazioni e considerando il tipo ($>= , <=$), si ottiene proprio la regione rappresentata. Per disegnarla ti consiglio di disegnare i vincoli come se fossero equazioni (quindi rette) e poi prendere un punto qualsiasi fuori da queste rette e vedere se verifica la disequazione. Se risultasse ammissibile allora "da quel lato" della retta avresti il semipiano con i punti ammissibili, altrimenti il semipiano con i punti ammssibili sarebbe l'altro. Facendolo per ogni vincolo ottieni la regione ammissibile, questa può: non esistere, essere limitata, essere illimitata. Evidentemente in questo caso è limitata.
2)Rappresenti la funzione obiettivo: semplicemente prendi la funzione obiettivo e poi poni $z=k$ dove $k$ è un valore qualsiasi che vuoi tu. Serve solamente per poter rappresentare la funzione in quanto in questo modo le uniche variabili sono $x_1 , x_2$. Ad esempio prova con $z=0$. In questo caso avrai: $2x_1 + x_2=0$. In questo modo puoi rappresentare la f.o. per una coppia di valori $(x_1, x_2)$. Tutte le altre rette rappresentanti la f.o. (per altri valori di $z$) saranno parallele a quella disegnata. A questo punto vedi in che verso viene minimizzata la f.o.. Per capire quale è questa direzione basta che consideri il gradiente della f.o.. In questo caso hai $grad z= (2,1)$. Ne consegue che se $x_1$ e $x_2$ crescono allora f.o. cresce mentre se diminuiscono allora f.o. diminuisce. Questo che vuol dire? In pratica sulla rappresentazione grafica che hai disegnato (quella per $z=0$) ti permette di disegnare una freccetta. Questa freccetta indicherà in che verso muoverti e la otterrai dal gradiente. In pratica avrai che muovendoti verso destra (ovvero crescono sia $x_1$ sia $x_2$) starai massimizzando mentre muovendoti verso sinistra (ovvero decrescono sia $x_1$ sia $x_2$) starai minimizzando.
3) A seconda se l'esercizio è di minimizzazione o di massimizzazione metterai sul disegno della f.o. la freccetta giusta. Vediamo prima il caso della minimizzazione e poi quello della massimizzazione.
3.1) Minimizzazione: La freccetta (come detto in 2) ) è rivolta verso sinistra. In pratica se muoverai la f.o. verso sinistra troverai di volta in volta coppie di $(x_1, x_2)$ che restituiscono valori di f.o. sempre più piccoli. Ovviamente se disegni graficamente altre rette (per diversi valori di z) avrai che sulle singole rette tutte le coppie di $(x_1, x_2)$ restituiranno punti aventi stesso valore della f.o.. Ora la domanda che ti dovresti porre è: quale è il minimo del mio problema? La risposta te la puoi dare semplicemente muovendo verso la direzione che la freccetta ti indica la stessa f.o.. L'ultimo punto ammissibile (ovvero appartenente alla regione ammissibile) che questa incontra sarà il minimo che cercavi.
Potrebbe accadere che, per qualche motivo, hai scelto un valore di $z$ per rappresentare la f.o. che è più piccolo del minimo (in questo caso capita se scegli ad es. $z=-3$). In questo caso (lo vedi graficamente), muovendo la f.o. nella direzione della freccetta non incontrerai mai la regione ammissibile, non vuol dire che il minimo non esiste. In questo caso devi muovere la f.o. nel verso opposto e il minimo sarà il primo punto ammissibile che incontrerai. Se non ti fosse chiaro il perché allora rappresenta la f.o. per una nuova coppia $(x_1, x_2)$ per i quali la f.o. intercetta la regione ammissibile e applica quello che ti ho detto in precedenza. Vedrai che il risultato sarà proprio lo stesso.
3.2) Massimizzazione: La freccetta (come detto in 2) ) è rivolta verso destra. In pratica se muoverai la f.o. verso destra troverai di volta in volta coppie di $(x_1, x_2)$ che restituiscono valori di f.o. sempre più grandi. Ovviamente se disegni graficamente altre rette (per diversi valori di z) avrai che sulle singole rette tutte le coppie di $(x_1, x_2)$ restituiranno punti aventi stesso valore della f.o.. Ora la domanda che ti dovresti porre è: quale è il massimo del mio problema? La risposta te la puoi dare semplicemente muovendo verso la direzione che la freccetta ti indica la stessa f.o.. L'ultimo punto ammissibile che questa incontra sarà il massimo che cercavi. Sarà diverso dal minimo perché ti stai muovendo nella direzione opposta (in pratica il metodo per trovarlo è lo stesso, cambia la direzione verso la quale sposti la f.o.).
Potrebbe accadere che, per qualche motivo, hai scelto un valore di $z$, per rappresentare la f.o., che è più grande del massimo (in questo caso capita se scegli ad es. $z=3$). In questo caso (lo vedi graficamente), muovendo la f.o. nella direzione della freccetta non incontrerai mai la regione ammissibile, non vuol dire che il massimo non esiste. In questo caso devi muovere la f.o. nel verso opposto e il massimo sarà il primo punto ammissibile che incontrerai. Se non ti fosse chiaro il perché allora rappresenta la f.o. per una nuova coppia $(x_1, x_2)$ per i quali f.o. intercetta la regione ammissibile e applica quello che ti ho detto in precedenza. Vedrai che il risultato sarà proprio lo stesso.
Spero di essere stato sufficientemente chiaro, se non hai capito qualcosa o hai qualche dubbio (magari mi è sfuggita una stupidaggine!) chiedi pure!
Ma non ho capito perche si prendono quelle coordinate!
Cioe da dove si prendono
Cioe da dove si prendono
"mistergks":
Ma non ho capito perche si prendono quelle coordinate!
Cioe da dove si prendono
Magari se usassi il tasto quote per farmi capire i singoli punti che non hai chiari sarebbe decisamente meglio.
NB:Inoltre, per i prossimi messaggi, ti consiglio di scrivere "a mano" il testo e di suggerire una modalità di risoluzione (anche completamente sbagliata, basta che ci sia un segnale di impegno da parte tua). Al termine della quale potresti allegare, come hai fatto, una soluzione già proposta ed in tuo possesso. Te lo dico perché proprio in questi giorni se ne stava parlando giusto qui. Ovviamente io non sono un moderatore però, dato che sto cercando di aiutarti, ti ricordo di attenerti quanto più possibile al regolamento...
"mistergks":
Ma non ho capito perche si prendono quelle coordinate!
Cioe da dove si prendono
Se ho capito bene la domanda (non credo) la risposta dovrebbe essere che derivano dai vincoli!
Il dominio lo individui con i vincoli che essendo Programmazione Lineare sono delle semplici rette,quindi puoi disegnare il tutto e utilizzare formule banali per calcolarti robe banali quali punti di intersezione tra assi cartesiani e rette, o robe così!
Si il succo del discorso è quello...
Lo so che i punti di coordinate si ricavano dai vincoli...
Quello che non capisco...è...
Si prendono punti a "scelta"?
Cioe come per una normale retta di equazione Scelgo la x ad esempio e sostituendo nell'equazione (vincolo) ricavo la y?
X intermat: la tua spiegazione mi è risultata piu chiara rileggendola ora... Ma ho solo questo dubbio... Ne hai parlato all'inizio del messaggio
Lo so che i punti di coordinate si ricavano dai vincoli...
Quello che non capisco...è...
Si prendono punti a "scelta"?
Cioe come per una normale retta di equazione Scelgo la x ad esempio e sostituendo nell'equazione (vincolo) ricavo la y?
X intermat: la tua spiegazione mi è risultata piu chiara rileggendola ora... Ma ho solo questo dubbio... Ne hai parlato all'inizio del messaggio
L'unica cosa che devi prendere a caso è il valore di $z$ poiché serve solo per avere una retta del tipo $y=mx+z$ dove $z$ è un termine noto (una volta fissato). Il resto dei punti ovvero gli spigoli e il punto di ottimo li trovi quindi non sono casuali. Continuo però a non capire quali sono i punti di cui non capisci le coordinate!
"Intermat":
L'unica cosa che devi prendere a caso è il valore di $z$ poiché serve solo per avere una retta del tipo $y=mx+z$ dove $z$ è un termine noto (una volta fissato). Il resto dei punti ovvero gli spigoli e il punto di ottimo li trovi quindi non sono casuali. Continuo però a non capire quali sono i punti di cui non capisci le coordinate!
$y=mx+z$ sarebbe $x1=2x2+z$ al primo vincolo?
No, intendo la funzione obiettivo. I vincoli già sono solo in funzione delle due variabili $x$ $ y$ o, nel tuo caso, $x_1$ $x_2$. I vincoli quindi sono solo da disegnare, non devi fare altro. L'unica cosa a cui devi prestare attenzione è la f.o. nella quale devi fissare un valore di $z$ arbitrario per poterla disegnare.
Ti darei un consiglio, studia una qualsiasi dispensa online, mi sembra che proprio non ti è chiaro questo argomento. Non mi sembra solo un dubbio su questo esercizio.
Ti darei un consiglio, studia una qualsiasi dispensa online, mi sembra che proprio non ti è chiaro questo argomento. Non mi sembra solo un dubbio su questo esercizio.
"Intermat":
No, intendo la funzione obiettivo. I vincoli già sono solo in funzione delle due variabili $x$ $ y$ o, nel tuo caso, $x_1$ $x_2$. I vincoli quindi sono solo da disegnare, non devi fare altro. L'unica cosa a cui devi prestare attenzione è la f.o. nella quale devi fissare un valore di $z$ arbitrario per poterla disegnare.
Ti darei un consiglio, studia una qualsiasi dispensa online, mi sembra che proprio non ti è chiaro questo argomento. Non mi sembra solo un dubbio su questo esercizio.
Il problema è proprio quello...
Il disegno dei vincoli non ho capito.
Come escono quelle coordinate da quei vincoli??
Saró ebete ma non ci arrivo proprio...
Ad esempio al primo vincolo perchè dice le rette passanti per i punti [2,0] [0,1]? Come calcola i punti?
Si è un dubbio che ho su tutti gli esercizi...
"mistergks":
[quote="Intermat"]No, intendo la funzione obiettivo. I vincoli già sono solo in funzione delle due variabili $x$ $ y$ o, nel tuo caso, $x_1$ $x_2$. I vincoli quindi sono solo da disegnare, non devi fare altro. L'unica cosa a cui devi prestare attenzione è la f.o. nella quale devi fissare un valore di $z$ arbitrario per poterla disegnare.
Ti darei un consiglio, studia una qualsiasi dispensa online, mi sembra che proprio non ti è chiaro questo argomento. Non mi sembra solo un dubbio su questo esercizio.
Il problema è proprio quello...
Il disegno dei vincoli non ho capito.
Come escono quelle coordinate da quei vincoli??
Saró ebete ma non ci arrivo proprio...
Ad esempio al primo vincolo perchè dice le rette passanti per i punti [2,0] [0,1]? Come calcola i punti?
Si è un dubbio che ho su tutti gli esercizi...[/quote]
Secondo me ti stai perdendo in un bicchier d'acqua!
Ogni vincolo è rappresentanto da una disquazione, tu non devi far altro che scrivere l'equazione associata e riportarla sul piano cartesiano!
Hai un'equazione, sai che per due punti passa solo e soltanto una retta, non serve nessuna conoscenza specifica dell'argomento,basta disegnarla!
"mistergks":
Il problema è proprio quello...
Il disegno dei vincoli non ho capito.
Come escono quelle coordinate da quei vincoli??
Saró ebete ma non ci arrivo proprio...
Ad esempio al primo vincolo perchè dice le rette passanti per i punti [2,0] [0,1]? Come calcola i punti?
Si è un dubbio che ho su tutti gli esercizi...
Come ti ha suggerito Ste_1990 non c'è molto da fare. Basta che rappresenti la retta e poi capisci il verso della disequazione (per farlo, dato che la reta divide il piano in due semipiani, basta che prendi un punto fuori di essa e vedi se soddisfa la disequazione). Non c'è altro.
Quindi ad esempio al primo vincolo la disequazione diventa:
$x1=-2 x2 + 2$
Assegno un valore (ad esempio 0) alla x2 e sostituisco... Quindi x1=2
Cosi ?
$x1=-2 x2 + 2$
Assegno un valore (ad esempio 0) alla x2 e sostituisco... Quindi x1=2
Cosi ?
"mistergks":
Quindi ad esempio al primo vincolo la disequazione diventa:
$x1=-2 x2 + 2$
Assegno un valore (ad esempio 0) alla x2 e sostituisco... Quindi x1=2
Cosi ?
Si, e così trovi un punto. Poi fai la stessa cosa ad esempio fissando $x_2 = 0$ e ottieni $x_1=2$. Ora, per due punti passa una e una sola retta, ottieni la retta che descrive una parte del perimetro della regione ammissibile. Per vedere "in che verso" è soddisfatto il vincolo prendi un qualsiasi punto, non appartenente alla retta, e vedi se soddisfa il vincolo. Ad esempio prendi $x_1=0$ $x_2=0$. Ottieni $0<=2$ quindi il vincolo è verificato. Tutti i punti "da questo stesso lato della retta" soddisferanno questo vincolo e quindi potrebbero appartenere alla regione ammissibile (se poi ci appartengono davvero dipenderà dagli altri vincoli per i quali ragionerai allo stesso modo!).
Ora ti è più chiaro?
PS: Una curiosità, ricerca operativa la stai studiando per tuo interesse personale o all'interno di un corso universitario?
Si finalmente ho capito!!! Per l'università ma la odio... E poi non ho seguito il corso e sto facendo da solo purtroppo
"mistergks":
Si finalmente ho capito!!! Per l'università ma la odio... E poi non ho seguito il corso e sto facendo da solo purtroppo
Però, lasciatelo dire, qui il problema non era tanto di ricerca operativa. Il problema era che non riuscivi a rappresentare un semipiano su un piano cartesiano. In ogni caso, non so cosa studi, però ricerca operativa non è così brutta. Se fai ing. Gestionale è molto importante, se fai ing. Informatica forse un po' meno. Tu cosa studi?
Informatica....
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo