Prog. Lineare: Determinare una funzione obiettivo
Ciao raga.
Qualcuno sarebbe così gentile da aiutarmi a capire come posso risolvere questi esercizi:
1)
<
$-7x_1+8x_2 <=6$
$3x_1+6x_2<=56$
$x_1,x_2 >=0$
Determinare, se esiste, una funzione obiettivo che dia luogo ad una soluzione ottima unica.>>
2)
<
$-7x_1+7x_2 <=6$
$8x_1+6x_2<=56$
$x_1,x_2 >=0$
Determinare, se esiste, una funzione obiettivo tale che l'ottimo sia il punto(0,0).>>
3)
<
$-7x_1+7x_2 <=6$
$8x_1+6x_2<=56$
$x_1,x_2 >=0$
Determinar una funzione obiettivo tale che l'ottimo si ottenga con Base=(1,2).>>
Ci tengo a sottolineare che non mi interessa la soluzione, ma vorrei capire il ragionamento che devo fare per ricavare la funzione obiettivo. Spero tanto che qualcuno mi aiuti, grazie.
Qualcuno sarebbe così gentile da aiutarmi a capire come posso risolvere questi esercizi:
1)
<
$-7x_1+8x_2 <=6$
$3x_1+6x_2<=56$
$x_1,x_2 >=0$
Determinare, se esiste, una funzione obiettivo che dia luogo ad una soluzione ottima unica.>>
2)
<
$-7x_1+7x_2 <=6$
$8x_1+6x_2<=56$
$x_1,x_2 >=0$
Determinare, se esiste, una funzione obiettivo tale che l'ottimo sia il punto(0,0).>>
3)
<
$-7x_1+7x_2 <=6$
$8x_1+6x_2<=56$
$x_1,x_2 >=0$
Determinar una funzione obiettivo tale che l'ottimo si ottenga con Base=(1,2).>>
Ci tengo a sottolineare che non mi interessa la soluzione, ma vorrei capire il ragionamento che devo fare per ricavare la funzione obiettivo. Spero tanto che qualcuno mi aiuti, grazie.
Risposte
"Skeggia":
Ci tengo a sottolineare che non mi interessa la soluzione, ma vorrei capire il ragionamento che devo fare per ricavare la funzione obiettivo. Spero tanto che qualcuno mi aiuti, grazie.
penso si possa risolvere in vari modi. Ma se vuoi vederci più chiaro, prova a disegnarti il simplesso così puoi vedere qual è la regione ammissibile data dai vincoli, prova con l'1)
Si l'ho fatto...ora ho la regione ammissibile, se non erro è chiusa. Come procedo?
"Skeggia":
Si l'ho fatto...ora ho la regione ammissibile, se non erro è chiusa. Come procedo?
bhe tipo nel primo chiede di trovare una funzione obbiettivo.
Mettiamo sia $a,b in RR$, la nostra funzione è
$ax_1 + bx_2$ prova con alcuni valori a vedere che succede con il metodo grafico a massimizzare o minimizzare.
Ok. Se metto $min z=x_1+x_2$, ottengo come punto di ottimo l'origine, che è un vertice della regione ammissibile. Quindi, la funzione obbiettivo da luogo ad una soluzione ottima e unica...giusto?
Se mi confermi la correttezza del primo anche per il 2° va bene. Mentre per il 3 esercizio, che devo fare??
Se mi confermi la correttezza del primo anche per il 2° va bene. Mentre per il 3 esercizio, che devo fare??
"Skeggia":
Ok. Se metto $min z=x_1+x_2$, ottengo come punto di ottimo l'origine, che è un vertice della regione ammissibile. Quindi, la funzione obbiettivo da luogo ad una soluzione ottima e unica...giusto?
mi pare troppo semplice ridursi al punto (0,0) che è la soluzione del 2)
Riprova con maximize, secondo me è più interessante.
Mentre per il 3 esercizio, che devo fare??
mmm questa ci devo pensare.
Ma penso sia utile utilizzare la controparte algebrica del metodo grafico e trasformarlo in un sistema lineare. Alla fine è tra trovare una soluzione, prova a sostituire e vedere che succede alle variabili slack.
Ciao per il primo esercizio se massimizzo con la funzione obbiettivo che ho indicato su, ottengo come punto di ottimo, il punto dato dall'intersezione delle due rette dei vincoli.
Per il secondo lascio tutto invariato...
Mentre per il terzo ho fatto questo ragionamento e non so se è corretto:
Per prima cosa, ho trasformato i vincoli in forma standard, quindi ho aggiunto le variabili di slack $x_3$ e $x_4$ dopodiché ho riflettuto sul fatto che l'ottimo deve essere ottenuto con B={1,2}, ciò significa che le variabili di slack per il punto di ottimo devono valere zero. Pertanto ho provato a vedere che succedeva con questa funzione obiettivo $max z=x_1 + 3x_2$ ed il punto di ottimo è il vertice della regione ammissibile che è dato dall'intersezione delle rette dei due vincoli. In pratica, il punto è individuato dal vincolo 1 dove $x_3$ vale zero ed il vincolo 2 su cui $x_4$ vale zero. Pertanto la base associata al punto è quella richiesta dalla traccia.
Intanto sono andato avanti e c'è un altro esercizio con altri vincoli:
$5x_1 + 6x_2 <=30$
$-4x_1+5x_2<=20$
$x_1>=0,x_2>=0$
dove devo esibire una funzione obbiettivo che dia luogo ad infinite soluzioni ottime.
Ho disegnato la regione ammissibile che è chiusa e limitata. Qua non riesco a capire come trovare queste infinite soluzioni ottime. Cioè devo avere infiniti punti di ottimo?E come è possibile?
Spero sia stato chiaro. E soprattutto spero di aver fatto bene...
Per il secondo lascio tutto invariato...
Mentre per il terzo ho fatto questo ragionamento e non so se è corretto:
Per prima cosa, ho trasformato i vincoli in forma standard, quindi ho aggiunto le variabili di slack $x_3$ e $x_4$ dopodiché ho riflettuto sul fatto che l'ottimo deve essere ottenuto con B={1,2}, ciò significa che le variabili di slack per il punto di ottimo devono valere zero. Pertanto ho provato a vedere che succedeva con questa funzione obiettivo $max z=x_1 + 3x_2$ ed il punto di ottimo è il vertice della regione ammissibile che è dato dall'intersezione delle rette dei due vincoli. In pratica, il punto è individuato dal vincolo 1 dove $x_3$ vale zero ed il vincolo 2 su cui $x_4$ vale zero. Pertanto la base associata al punto è quella richiesta dalla traccia.
Intanto sono andato avanti e c'è un altro esercizio con altri vincoli:
$5x_1 + 6x_2 <=30$
$-4x_1+5x_2<=20$
$x_1>=0,x_2>=0$
dove devo esibire una funzione obbiettivo che dia luogo ad infinite soluzioni ottime.
Ho disegnato la regione ammissibile che è chiusa e limitata. Qua non riesco a capire come trovare queste infinite soluzioni ottime. Cioè devo avere infiniti punti di ottimo?E come è possibile?
Spero sia stato chiaro. E soprattutto spero di aver fatto bene...
"Skeggia":
Ciao per il primo esercizio se massimizzo con la funzione obbiettivo che ho indicato su, ottengo come punto di ottimo, il punto dato dall'intersezione delle due rette dei vincoli.
ok.
Per il secondo lascio tutto invariato...
intendi utilizzano min, giusto?
Mentre per il terzo ho fatto questo ragionamento e non so se è corretto:
Per prima cosa, ho trasformato i vincoli in forma standard, quindi ho aggiunto le variabili di slack $x_3$ e $x_4$ dopodiché ho riflettuto sul fatto che l'ottimo deve essere ottenuto con B={1,2},
ho provato a risolvera con un solutore, ma non risulta (1,2) come base di ottimo con quella funzione
Intanto sono andato avanti e c'è un altro esercizio con altri vincoli:
$5x_1 + 6x_2 <=30$
$-4x_1+5x_2<=20$
$x_1>=0,x_2>=0$
dove devo esibire una funzione obbiettivo che dia luogo ad infinite soluzioni ottime.
Ho disegnato la regione ammissibile che è chiusa e limitata. Qua non riesco a capire come trovare queste infinite soluzioni ottime. Cioè devo avere infiniti punti di ottimo?E come è possibile?
l'unica cosa che mi viene in mente ora, avendo la regione chiusa, è esporre una funzione con dei parametri liberi tipo:
$ax_1 + bx_2$
"hamming_burst":
Per il secondo lascio tutto invariato...
intendi utilizzano min, giusto?
Esatto. Quindi i primi due li possiamo archiviare.
"hamming_burst":Mentre per il terzo ho fatto questo ragionamento e non so se è corretto:
Per prima cosa, ho trasformato i vincoli in forma standard, quindi ho aggiunto le variabili di slack $x_3$ e $x_4$ dopodiché ho riflettuto sul fatto che l'ottimo deve essere ottenuto con B={1,2},
ho provato a risolvera con un solutore, ma non risulta (1,2) come base di ottimo con quella funzione
Hai ragione ho provato anche io con il solutore ed esce (2,1) che è diverso giusto da (1,2)?
Forse il procedimento logico che ho usato non è del tutto errato...ovviamente devo cambiare funzione obiettivo. Qualche suggerimento?
"hamming_burst":
Intanto sono andato avanti e c'è un altro esercizio con altri vincoli:
$5x_1 + 6x_2 <=30$
$-4x_1+5x_2<=20$
$x_1>=0,x_2>=0$
dove devo esibire una funzione obbiettivo che dia luogo ad infinite soluzioni ottime.
Ho disegnato la regione ammissibile che è chiusa e limitata. Qua non riesco a capire come trovare queste infinite soluzioni ottime. Cioè devo avere infiniti punti di ottimo?E come è possibile?
l'unica cosa che mi viene in mente ora, avendo la regione chiusa, è esporre una funzione con dei parametri liberi tipo:
$ax_1 + bx_2$
Credo che il problema sta nel fatto che non ho capito come si ottengono questi infiniti punti di ottimo, cioè proprio a livello di astrazione. Anche gli esempi che ho visto non mi sono chiari.
tra una fetta di torta pasqualina e l'altra mi son completamente scordato di risponderti...
esatto
a me risulta:
forse ho capito male io, ma B=(1,2) per te cosa significa? E' l'insieme delle basi, o il punto di ottimo?
se aiuta questa è la regione ammissibile:
Se non fosse chiusa la regione sarebbe abbastanza facile, se non è chiaro cosa vuol dire ottimo illimitato qui un esempio:
risoluzione-grafica-problema-di-pl-t89881.html
ma qua invece siamo in un caso particolare, bisogna ragionare sui fattori di crescita slack. Con il metodo algebrico penso sia più chiaro come arrivare ad una soluzione.
C'è un caso particolare che può indurre il problema ad avere soluzioni illimitazione durante lo svolgimento dell'algoritmo/metodo del simplesso, qui ne accenno. Se vedi uno spiraglio nel comprendere: bene, se no ne riparliamo e ci ragioniamo insieme (è solo una supposizione che si risolva in questo modo, avendo la regione chiusa...)
"Skeggia":
Esatto. Quindi i primi due li possiamo archiviare.
esatto
Hai ragione ho provato anche io con il solutore ed esce (2,1) che è diverso giusto da (1,2)?
Forse il procedimento logico che ho usato non è del tutto errato...ovviamente devo cambiare funzione obiettivo. Qualche suggerimento?
a me risulta:
Optimal Solution: p = 17.102; x1 = 3.63265, x2 = 4.4898
forse ho capito male io, ma B=(1,2) per te cosa significa? E' l'insieme delle basi, o il punto di ottimo?
Credo che il problema sta nel fatto che non ho capito come si ottengono questi infiniti punti di ottimo, cioè proprio a livello di astrazione. Anche gli esempi che ho visto non mi sono chiari.
se aiuta questa è la regione ammissibile:
Se non fosse chiusa la regione sarebbe abbastanza facile, se non è chiaro cosa vuol dire ottimo illimitato qui un esempio:
risoluzione-grafica-problema-di-pl-t89881.html
ma qua invece siamo in un caso particolare, bisogna ragionare sui fattori di crescita slack. Con il metodo algebrico penso sia più chiaro come arrivare ad una soluzione.
C'è un caso particolare che può indurre il problema ad avere soluzioni illimitazione durante lo svolgimento dell'algoritmo/metodo del simplesso, qui ne accenno. Se vedi uno spiraglio nel comprendere: bene, se no ne riparliamo e ci ragioniamo insieme (è solo una supposizione che si risolva in questo modo, avendo la regione chiusa...)
"hamming_burst":
a me risulta:
Optimal Solution: p = 17.102; x1 = 3.63265, x2 = 4.4898
forse ho capito male io, ma B=(1,2) per te cosa significa? E' l'insieme delle basi, o il punto di ottimo?
B=(1,2) E' l'insieme delle basi...Quindi?
"hamming_burst":
Se non fosse chiusa la regione sarebbe abbastanza facile, se non è chiaro cosa vuol dire ottimo illimitato qui un esempio:
risoluzione-grafica-problema-di-pl-t89881.html
ma qua invece siamo in un caso particolare, bisogna ragionare sui fattori di crescita slack. Con il metodo algebrico penso sia più chiaro come arrivare ad una soluzione.
C'è un caso particolare che può indurre il problema ad avere soluzioni illimitazione durante lo svolgimento dell'algoritmo/metodo del simplesso, qui ne accenno. Se vedi uno spiraglio nel comprendere: bene, se no ne riparliamo e ci ragioniamo insieme (è solo una supposizione che si risolva in questo modo, avendo la regione chiusa...)
L'ottimo illimitato l'ho capito proprio da quell'esempio in quel forum mentre gli infiniti punti di ottimo su un altro esempio simile, quindi sempre graficamente...mentre l'altro post che mi hai suggerito sul metodo del simplesso non mi è tanto chiaro, ma non mi sono applicato troppo.
Comunque l'esercizio:
$5x_1+6x_2≤30$
$−4x_1+5x_2≤20$
$x_1≥0,x_2≥0$
dove devo esibire una funzione obiettivo che dia luogo ad infinite soluzioni ottime, l'ho risolto così, guardando il grafico:
$min z=x_2$
In questo modo ottengo gli infiniti punti di ottimo sul lato della regione ammissibile che risiede sull'asse delle ascisse.
Concordi?
B=(1,2) E' l'insieme delle basi...Quindi?
bho
appena ho un po' di tempo guardo meglio l'esercizio, è questione di terminologia.
Comunque l'esercizio:
$5x_1+6x_2≤30$
$−4x_1+5x_2≤20$
$x_1≥0,x_2≥0$
dove devo esibire una funzione obiettivo che dia luogo ad infinite soluzioni ottime, l'ho risolto così, guardando il grafico:
$min z=x_2$
In questo modo ottengo gli infiniti punti di ottimo sul lato della regione ammissibile che risiede sull'asse delle ascisse.
Concordi?
mmm non mi convince.
la funzione obiettivo penso sia da scrivere meglio cosi: $min z= 0x_1 + x_2$ ma non ha ottimo illimitato.
Almeno la definizione di ottimo illimitato vuol dire avere $z= oo$ e la funzione che proponti ha semplicemente $(0,0)$ come punto di ottimo...
Perciò non concorda con quella che conosco, forse con il metodo algebrico che ho proposto si può far qualcosa, ma devo avere un po' di tempo per vederlo.
Cmq è legato a tipo alla Regola di Bland e cosa evita tale regola se appliacata, è il ragionamento al contrario cioè noi cerchiamo di ottenere l'ottimo illimitao non evitarlo.
Scusami ma avere infinite soluzioni equivale ad avere infiniti punti di ottimo? Perché io non sto considerando l'ottimo illimitato ma infiniti punti di ottimo...non so se mi sono spiegato...ecco perché ho dato quella soluzione.
Ricapitoliamo i due quesiti:
la soluzione secondo me è:
sia $a in RR\ |\ \max_{x_1,x_2} {a*x_1 + x_2}$
è l'unico caso che si può dire produce infinite soluzioni ottime essendo $a$ uno scalare e la regione è chiusa. Non vedo altre possibili soluzioni.
se si parla di base devi utilizzare il metodo algebrico, qua ti si richiede che la soluzione di base sia nell'insieme (1,2) cioè manipolando le scelte di entranti ed uscienti devi ottenere una forma finale con base con quegli indici.
"Skeggia":
Intanto sono andato avanti e c'è un altro esercizio con altri vincoli:
$5x_1 + 6x_2 <=30$
$-4x_1+5x_2<=20$
$x_1>=0,x_2>=0$
dove devo esibire una funzione obbiettivo che dia luogo ad infinite soluzioni ottime.
la soluzione secondo me è:
sia $a in RR\ |\ \max_{x_1,x_2} {a*x_1 + x_2}$
è l'unico caso che si può dire produce infinite soluzioni ottime essendo $a$ uno scalare e la regione è chiusa. Non vedo altre possibili soluzioni.
3)
<
$-7x_1+7x_2 <=6$
$8x_1+6x_2<=56$
$x_1,x_2 >=0$
Determinar una funzione obiettivo tale che l'ottimo si ottenga con Base=(1,2).>>
se si parla di base devi utilizzare il metodo algebrico, qua ti si richiede che la soluzione di base sia nell'insieme (1,2) cioè manipolando le scelte di entranti ed uscienti devi ottenere una forma finale con base con quegli indici.
"hamming_burst":
Ricapitoliamo i due quesiti:
[quote="Skeggia"]
Intanto sono andato avanti e c'è un altro esercizio con altri vincoli:
$5x_1 + 6x_2 <=30$
$-4x_1+5x_2<=20$
$x_1>=0,x_2>=0$
dove devo esibire una funzione obbiettivo che dia luogo ad infinite soluzioni ottime.
la soluzione secondo me è:
sia $a in RR\ |\ \max_{x_1,x_2} {a*x_1 + x_2}$
è l'unico caso che si può dire produce infinite soluzioni ottime essendo $a$ uno scalare e la regione è chiusa. Non vedo altre possibili soluzioni.
[/quote]
Ok, concordo. Archiviato anche questo
[quote]3)
<
$-7x_1+7x_2 <=6$
$8x_1+6x_2<=56$
$x_1,x_2 >=0$
Determinar una funzione obiettivo tale che l'ottimo si ottenga con Base=(1,2).>>
se si parla di base devi utilizzare il metodo algebrico, qua ti si richiede che la soluzione di base sia nell'insieme (1,2) cioè manipolando le scelte di entranti ed uscenti devi ottenere una forma finale con base con quegli indici.[/quote]
Ok ma quale metodo algebrico usare?
Ok ma quale metodo algebrico usare?
bhe si parla di PL reale, in due variabili.... più che il metodo del simplesso
forse ti serve un esempio per capire cosa chieda l'esercizio. Prendiamo questo: post611703.html#p611703 solo perchè ci son tutti i passaggi. Non è il metodo del simplesso che è insegnato in corsi di Ottimizzazione (con tableau&baguette), ma è una versione semplificata che da il Cormen.
$z = 26 - 7x_1 - 4/3x_2 - 1/3x_5 - 7/3x_7$
${(x_3 = 10 - x_1 - x_7),(x_4 = 6 - x_1 - 1/3x_2 - 1/3x_5 - 1/3x_7),(x_6 = 10 + x_1 - 4/3x_2 + 2/3x_5 - 4/3x_7),(x_i >= 0\ |\ i=1..7):}$
$B={x_3,x_4,x_6}$ e $N={x_1,x_2,x_5,x_7}$
soluzione di base: $(0,0,10,6,0,10,0)$ trovata azzerando le variabili non-di-base e $z=26$
questa è l'ultima iterazione di un problema di massimo (lo si può notare visto che ha tutti i coefficienti della funzione obiettivo negativi).
Quella che il problema chiede è che $B$ sia uguale a $B={x_1,x_2}$ cioè l'ultima itarazione la soluzione di base sia composta dalle variabili non di base ${x_3,x_4}$.
Te devi cercare una funzione obiettivo che permetta questo. Più chiaro?
Si ora è più chiaro. Grazie!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo