Aituo, problema knapsack
ciao a tutti , vi ringrazio subito per l'aiuto
devo consegnare un progetto di ricerca operativa in cplex tra pochi giorni ma non riesco ad arrivare alla soluzione
il testo dice:
in una strada si può parcheggiare su entrambi i lati, il signor rossi ha una trentina di ospiti che arriveranno scaglionati in 15 auto, l'i-esima automobile ha lunghezza Li espressa in metri
i 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15
Li 4 |4.5| 5 |4.1|2.4|5.2|3.7|3.5|3.2|4.5|2.3 | 3.3|3.8| 4.6| 3
il signor rossi vorrebbe trovare una disposizione dei parcheggi sui due lati della strada in modo che i segmento della via occupato dalle auto sia di lunghezza minima. si formuli e si risolva il problema
come cambiano il modello e la sua soluzione se esattamente uno dei 2 lati della strada ha capacità 15.
io ho risolto la prima parte mettendo come funzione obiettivo la differenza tra la sommatoria delle auto nel segmento k - la sommatoria delle auto nel segmento k+1 e mettendo come vincolo che somm di k > somm di k+1
il problema sorge ne secondo punto perchè se la strada 2 ha capacità 15 allora nessun problema, ma se invece è la 1 ad avere cap=15 allora la funzione obiettivo non potrà mai essere verificata.
qualche idea?
grazie..
devo consegnare un progetto di ricerca operativa in cplex tra pochi giorni ma non riesco ad arrivare alla soluzione
il testo dice:
in una strada si può parcheggiare su entrambi i lati, il signor rossi ha una trentina di ospiti che arriveranno scaglionati in 15 auto, l'i-esima automobile ha lunghezza Li espressa in metri
i 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15
Li 4 |4.5| 5 |4.1|2.4|5.2|3.7|3.5|3.2|4.5|2.3 | 3.3|3.8| 4.6| 3
il signor rossi vorrebbe trovare una disposizione dei parcheggi sui due lati della strada in modo che i segmento della via occupato dalle auto sia di lunghezza minima. si formuli e si risolva il problema
come cambiano il modello e la sua soluzione se esattamente uno dei 2 lati della strada ha capacità 15.
io ho risolto la prima parte mettendo come funzione obiettivo la differenza tra la sommatoria delle auto nel segmento k - la sommatoria delle auto nel segmento k+1 e mettendo come vincolo che somm di k > somm di k+1
il problema sorge ne secondo punto perchè se la strada 2 ha capacità 15 allora nessun problema, ma se invece è la 1 ad avere cap=15 allora la funzione obiettivo non potrà mai essere verificata.
qualche idea?
grazie..
Risposte
Non so se ho capito bene il problema. Pensi vada bene il seguente:
$min t$
$s.t.$
$t>=sum_{i=1}^{15} x_i * l_i$
$t>=sum_{i=1}^{15} (1-x_i)*l_i$
$x_i in {0,1} text( ) i=1,...,15$
$t in RR^+ $
Dove i primi due vincoli servono per determinare la lunghezza del lato di strada occupato attraverso una variabile x che assume valore 1 se l'auto è sul lato 1 e zero se è sul lato 2. Niente di più. Non dovrebbe cambiare nulla neppure nel secondo caso.
Dimmi se ho capito bene il problema e se ci fosse qualcosa che non ti torna!
$min t$
$s.t.$
$t>=sum_{i=1}^{15} x_i * l_i$
$t>=sum_{i=1}^{15} (1-x_i)*l_i$
$x_i in {0,1} text( ) i=1,...,15$
$t in RR^+ $
Dove i primi due vincoli servono per determinare la lunghezza del lato di strada occupato attraverso una variabile x che assume valore 1 se l'auto è sul lato 1 e zero se è sul lato 2. Niente di più. Non dovrebbe cambiare nulla neppure nel secondo caso.
Dimmi se ho capito bene il problema e se ci fosse qualcosa che non ti torna!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo