.dsy:it. - Appello 13 Febbraio

Pages (5): « 1 2 [3] 4 5 »
Show 150 posts per page

.dsy:it. (http://www.dsy.it/forum/)
- Ricerca operativa (http://www.dsy.it/forum/forumdisplay.php?forumid=228)
-- Appello 13 Febbraio (http://www.dsy.it/forum/showthread.php?threadid=29339)

Posted by nic on 10-02-2007 11:44:

da quanto ho capito io vuol dire che puoi scegliere come variabile di branch solo quella che non ci sta... metti ad esempio che nello zaino ci stanno A, B, C e D invece non ci sta... allora metti D=0 nel ramo in cui non prendi D e D=1 nel ramo in cui la prendi....
Ti dice soltanto di scegliere come variabile per il branch l'elemento che non ci sta...
spero di essere stato un pò + chiaro di prima :-)

Questo thread comunque è pieno di lurkoni!!! dai scrivete un pò!! l'esame si avvicina ed è crisi nera!!!! ;-)

Posted by DarkStalker on 10-02-2007 11:51:

Originally posted by nic
Da quanto ho capito l' LB è l'UB senza la parte frazionaria... lo usi per evitare di esplorare alcuni rami! senza di quello ti vengono comunque gli esercizi ma sono più lunghi...e soprattutto non so se poi ti da punteggio pieno!! :-)

Si ok, quella e' la spiegazione corretta nel caso generico

cioe' dato un valore ottimo in un nodo il suo LB e' solo la parte intera, l'UB e' la parte intera +1,
in questo caso specifico non capisco perche' tiri in ballo anche l'LB

Posted by DarkStalker on 10-02-2007 11:53:

Originally posted by nic
da quanto ho capito io vuol dire che puoi scegliere come variabile di branch solo quella che non ci sta... metti ad esempio che nello zaino ci stanno A, B, C e D invece non ci sta... allora metti D=0 nel ramo in cui non prendi D e D=1 nel ramo in cui la prendi....
Ti dice soltanto di scegliere come variabile per il branch l'elemento che non ci sta...
spero di essere stato un pò + chiaro di prima :-)

Questo thread comunque è pieno di lurkoni!!! dai scrivete un pò!! l'esame si avvicina ed è crisi nera!!!! ;-)

Spero sia cosi'

almeno (a quanto pare) l'esercizio si semplifica di un po' .
Io posto le mie soluzioni nel pomeriggio (devo rifare tutto) sperando di non avere contrattempi (adesso sono le 13 e vo' a magna').
Ciauz

Posted by nic on 10-02-2007 11:54:

probabilmente perchè confrontando l'Ub nel nodo attuale con gli LB degli altri già esplorati puoi trarre conclusioni... è un ricordo vago quindi non lo prenderei per certo! :-)

Posted by joker402 on 10-02-2007 13:39:

Originally posted by ripe
Non ho proprio capito cosa significa la frase che il prof mette negli esercizi di B&B:

Se hai
pesi: 6,7,3,1
b=12

e nell'albero che stai costruendo, sei a un punto in cui devi prendere per forza l'elemento 1, avrai che la capacità residua è b-(il peso dell'elem.1) cioè 12-6=6.
A questo punto dovresti fare branching sul secondo elemento, ma il peso è 7, e non ci starà mai... quindi puoi già fissarla a zero e guardare quello dopo.
Io l'avevo capita così e spero di non ricordarmi male!

La cosa assolutamente sicura è che "capacità residua" vuol dire la cosa che ho scritto: capacità totale, meno il peso degli elementi già presi (quelli fissati a 1).

__________________
Ogni uomo mente, ma dategli una maschera e sarà sincero.
~ joker402 ~

Posted by ripe on 10-02-2007 13:48:

Ok, grazie!
Vedo se applicato all'esercizio è giusto!

EDIT: ma l'algoritmo non prevederebbe che se l'oggetto ha peso maggiore della capacità residua, ne entri solo una quantità frazionaria su cui fare poi il branching al passo successivo?

Facendo come mi hai detto tu ho risolto un esercizio al primo colpo, senza creare neanche un nodo nuovo! :asd:

__________________
«And if you ever smell christian blood up in the mountains, then get your axe and chop them down!»

Posted by joker402 on 10-02-2007 14:03:

Originally posted by ripe
Ok, grazie!
Vedo se applicato all'esercizio è giusto!

EDIT: ma l'algoritmo non prevederebbe che se l'oggetto ha peso maggiore della capacità residua, ne entri solo una quantità frazionaria su cui fare poi il branching al passo successivo?

Facendo come mi hai detto tu ho risolto un esercizio al primo colpo, senza creare neanche un nodo nuovo!

oh cavolo... allora mi ricordavo male qualche pezzo...
era qualcosa di simile, ma forse fatto più avanti, però non riesco a ritrovare gli appunti :sad:

__________________
Ogni uomo mente, ma dategli una maschera e sarà sincero.
~ joker402 ~

Posted by DarkStalker on 10-02-2007 19:37:

Ho provato a fare il branch & bound di FROAppello140606
Qualcuno puo' confermare?

Posted by ripe on 10-02-2007 20:36:

Fate il tema d'esame dell'08/02/2006 così confrontiamo tutti gli es (a parte il primo)!

__________________
«And if you ever smell christian blood up in the mountains, then get your axe and chop them down!»

Posted by nic on 11-02-2007 09:41:

Originally posted by DarkStalker
Ho provato a fare il branch & bound di FROAppello140606
Qualcuno puo' confermare?

Così guardandolo velocemente un errore sicuro c'è..

l'esercizio ti dice di esplorarlo in profondità prendendo come variabile di branch sempre quella che non ci sta ed esplorando per primo il ramo a 0.

Poi non trovi soluzioni intere alla fine.. mi sa che è tutto sballato....non ho modo di uploadarti l'esercizio intero purtroppo... speriamo in qualche altra anima pia

Posted by nic on 11-02-2007 09:43:

Originally posted by ripe
Fate il tema d'esame dell'08/02/2006 così confrontiamo tutti gli es (a parte il primo)!

Ok parto ora :-) saltando ovviamente l'esercizio 1...

Posted by nic on 11-02-2007 10:42:

Esercizio 2

2.1

z=22 x1=7 x2=1 x3=0 x4=7 x5=9 x6=0

2.2

<x1,x2,x3,x6>

2.3

b compreso tra 6 e 26

Come viene a voi? intanto passo al 3

Posted by ripe on 11-02-2007 10:45:

Mi viene tutto esattamente come te!

__________________
«And if you ever smell christian blood up in the mountains, then get your axe and chop them down!»

Posted by nic on 11-02-2007 10:49:

esercizio 3

il duale è
minz*= 8y1+y2+4y3+6y4
y1+y2-y3+y4>=3
y1+y2+2y3-y4>=1
y1,3,4>=0
y2<=0

le y da trovare sono y1 e y4 e le trovo risolvendo il sistema
y1+y4=3
y1-y4=1

(dal sistema ho già tolto le y che valgono 0)

Soluzione y1=2 e y4=1

Posted by ripe on 11-02-2007 10:53:

Perfetto!

__________________
«And if you ever smell christian blood up in the mountains, then get your axe and chop them down!»

All times are GMT. The time now is 17:36.

Pages (5): « 1 2 [3] 4 5 »
Show all 74 posts from this thread on one page