Esercizio di programmazione lineare con parametro - help
per favore domani ho l'esame di Ricerca Operativa e ho trovato un tipo di esercizio di programmazione lineare che non capisco come impostare e risolvere. Questo è il testo:
Dato il seguente sistema di vincoli:
`-7x_1 + 8x_2 <= 6`
` 3x_1 + 6x_2 <=56`
`ul x>=0`
Determinare, se esiste, una funzione obiettivo che dia luogo ad una soluzione ottima unica.
Ho tentato di risolverlo imponendo che i coefficienti di costo ridotto siano strettamente minori di zero ponendo una funzione generica `z=k_1x_1+k_2x_2` con parametri k1, k2 ma alla fine mi trovo che sia k1 che k2 devono essere solo >0 il che contrasterebbe con il presupposto che la soluzione deve essere unica quindi andrebbero esclusi i valori per cui k1,k2 mi rendono la funzione obiettivo parallela ad uno dei vincoli (nel qual caso le soluzioni ottime sarebbero infinite).
Spero di essere stata chiara.
Vi prego datemi una mano!!
Grazie
Dato il seguente sistema di vincoli:
`-7x_1 + 8x_2 <= 6`
` 3x_1 + 6x_2 <=56`
`ul x>=0`
Determinare, se esiste, una funzione obiettivo che dia luogo ad una soluzione ottima unica.
Ho tentato di risolverlo imponendo che i coefficienti di costo ridotto siano strettamente minori di zero ponendo una funzione generica `z=k_1x_1+k_2x_2` con parametri k1, k2 ma alla fine mi trovo che sia k1 che k2 devono essere solo >0 il che contrasterebbe con il presupposto che la soluzione deve essere unica quindi andrebbero esclusi i valori per cui k1,k2 mi rendono la funzione obiettivo parallela ad uno dei vincoli (nel qual caso le soluzioni ottime sarebbero infinite).
Spero di essere stata chiara.
Vi prego datemi una mano!!
Grazie
Risposte
Il poligono ottenuto dalle condizioni offre 4 vertici che possono essere delle soluzioni uniche al problema, dipende ora quale vertice ti piace di più: imposti la funzione obiettivo in modo tale che il gradiente di questa sia compreso nella parte di piano formato dai gradienti delle 2 condizioni che si congiungono nel vertice prescelto.
Cmq se stai studiando Ricerca Operativa ti consiglio di scaricarti Lindo.
Io quando ho dato l'esame l'ho usato per imparare a leggere l'analisi di sensitività e i vari report..
ti assicuro che si capisce mooolto meglio
MCM
Io quando ho dato l'esame l'ho usato per imparare a leggere l'analisi di sensitività e i vari report..
ti assicuro che si capisce mooolto meglio
MCM
scusa ma a me sembra che la regione ammissibile sia formata da un triangolo quindi da soli tre punti estremi, questo è il grafico che ho ottenuto: (abbiate pazienza per il grafico forse è un po pesante, ma così si vede bene)
[img=http://www.hostfiles.org/miniature/20060419074411_grafico.jpg]
in ogni caso credi che non sia necessaria una funzione obiettivo parametrica? Come faccio a descrivere analiticamente che la funzione scelta, abbia effettivamente un punto di ottimo unico se non verifico i coefficienti di costo ridotto? In effetti graficamente si potrebbe già intuire che un punto di ottimo unico si può avere in P1 con una funzione di MINIMO, ma il mio problema è analitico.
[img=http://www.hostfiles.org/miniature/20060419074411_grafico.jpg]
in ogni caso credi che non sia necessaria una funzione obiettivo parametrica? Come faccio a descrivere analiticamente che la funzione scelta, abbia effettivamente un punto di ottimo unico se non verifico i coefficienti di costo ridotto? In effetti graficamente si potrebbe già intuire che un punto di ottimo unico si può avere in P1 con una funzione di MINIMO, ma il mio problema è analitico.
Controlla il grafico, hai sbagliato a tracciare il primo vincolo.
si hai ragione avevo dimenticato un meno. Si in effetti sono 4 i punti estremi, ecco il grafico modificato
[img=http://www.hostfiles.org/miniature/20060419112117_grafico.jpg]
però amcora non ho capito come impostare la funzione, prendiamo ad esempio il punto P1, esso si trova all'intersezione dei due vincoli x1=0 e x2=0. Come sarà in questo caso la funzione? Puoi farmi un esempio pratico?
[img=http://www.hostfiles.org/miniature/20060419112117_grafico.jpg]
però amcora non ho capito come impostare la funzione, prendiamo ad esempio il punto P1, esso si trova all'intersezione dei due vincoli x1=0 e x2=0. Come sarà in questo caso la funzione? Puoi farmi un esempio pratico?
vediamo se ho capito:
scelgo il punto P3 che è dato dall'intersezione dei due vincoli.
Il gradiente del primo vincolo è `p' =(-7;8) `
Il gradiente del secondo vincolo è `p'' =(3;6)`
Questo vulo dire che data la funzione `z=k_1x_1+k_2x_2`
`-7<=K_1<=3 ` e `6<=K_2<=8 `
spero che riuscirari a darmi la conferma per stasera ...domani ho il compito.
Cmq grazie dell'attenzione.
scelgo il punto P3 che è dato dall'intersezione dei due vincoli.
Il gradiente del primo vincolo è `p' =(-7;8) `
Il gradiente del secondo vincolo è `p'' =(3;6)`
Questo vulo dire che data la funzione `z=k_1x_1+k_2x_2`
`-7<=K_1<=3 ` e `6<=K_2<=8 `
spero che riuscirari a darmi la conferma per stasera ...domani ho il compito.
Cmq grazie dell'attenzione.
il compito, credo sia andato proprio bene, per fortuna le funzioni obiettivo con parametro erano di facile soluzione, però sono rimasta con la curiosità per questo esercizio, se vorrai rispondermi ne sarò felice.
Grazie
Ciao
Grazie
Ciao
E' molto semplice: i gradienti dei vincoli non sono altro che dei vettori in 2 dimensioni, li puoi anche tracciare sul grafico. Per avere l'ottimo su un determinato vertice basta che il gradiente della funzione obiettivo (anch'esso vettore di R^2) giaccia sulla porzione di piano compresa tra i vettori dei 2 vincoli presi in esame.
"uranya":
Questo vulo dire che data la funzione `z=k_1x_1+k_2x_2`
`-7<=K_1<=3 ` e `6<=K_2<=8 `
No, controesempio: k1=4 e k2=9.
pensavo di aver capito come calcolare i gradienti dei vincoli.... 
non devo calcolare la derivata delle equazioni associate?
percio avevo calcolato: per il 1° vincolo `p' =(-7;8) ` e per il 2° vincolo `p'' =(3;6)`
puoi allora scrivermi anche i gradienti dei due vincoli e come li hai calcolati?
non devo calcolare la derivata delle equazioni associate?
percio avevo calcolato: per il 1° vincolo `p' =(-7;8) ` e per il 2° vincolo `p'' =(3;6)`
puoi allora scrivermi anche i gradienti dei due vincoli e come li hai calcolati?
non ho detto che i gradienti sono sbagliati
va bene!! Te li ho riscritti solo per semplicità di lettura, ma la mia domanda era un'altra...
.. puoi allora scrivermi anche i gradienti dei due vincoli e come li hai calcolati?..........
.. puoi allora scrivermi anche i gradienti dei due vincoli e come li hai calcolati?..........
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo