.dsy:it. - Appello 13 Febbraio

Calendar

Members

Faq

Logout

.dsy:it. : Powered by vBulletin version 2.3.1

.dsy:it. > Didattica > Corsi N - Z > Ricerca operativa > Appello 13 Febbraio

Pages (5): « 1 2 [3] 4 5 »

Last Thread Next Thread

Author

Thread Expand all | Contract all

nic

.illuminato.

User info:

Registered: Jun 2002
Posts: 154 (0.02 al dì)
Location: Milano
Corso: specialistica, Tico
Anno: 2
Time Online: 2 Days, 20:49:47 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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!!!! ;-)

10-02-2007 11:44

Click here to Send nic a Private Message

DarkStalker

.consigliere.

User info:

Registered: Jun 2002
Posts: 115 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 2 Days, 4:56:07: [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

10-02-2007 11:51

Click here to Send DarkStalker a Private Message

DarkStalker

.consigliere.

User info:

Registered: Jun 2002
Posts: 115 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 2 Days, 4:56:07: [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

10-02-2007 11:53

nic

.illuminato.

User info:

Registered: Jun 2002
Posts: 154 (0.02 al dì)
Location: Milano
Corso: specialistica, Tico
Anno: 2
Time Online: 2 Days, 20:49:47 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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! :-)

10-02-2007 11:54

joker402

dsy core staff

User info:

Registered: Nov 2002
Posts: 2429 (0.29 al dì)
Location: Milano
Corso: TICom
Anno: II+
Time Online: 49 Days, 14:29:03: [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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 ~

10-02-2007 13:39

Click here to Send joker402 a Private Message

ripe

- up in the mountains -

User info:

Registered: Jun 2002
Posts: 9469 (1.10 al dì)
Location: Cinisellooo
Corso: TICO TICO
Anno: Primo
Time Online: 61 Days, 2:33:39 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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!»

Last edited by ripe on 10-02-2007 at 13:51

10-02-2007 13:48

Click here to Send ripe a Private Message

joker402

dsy core staff

User info:

Registered: Nov 2002
Posts: 2429 (0.29 al dì)
Location: Milano
Corso: TICom
Anno: II+
Time Online: 49 Days, 14:29:03: [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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 ~

Last edited by joker402 on 10-02-2007 at 14:05

10-02-2007 14:03

DarkStalker

.consigliere.

User info:

Registered: Jun 2002
Posts: 115 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 2 Days, 4:56:07: [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

Attachment: file0001.pdf
This has been downloaded 21 time(s).

10-02-2007 19:37

ripe

- up in the mountains -

User info:

Registered: Jun 2002
Posts: 9469 (1.10 al dì)
Location: Cinisellooo
Corso: TICO TICO
Anno: Primo
Time Online: 61 Days, 2:33:39 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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!»

10-02-2007 20:36

nic

.illuminato.

User info:

Registered: Jun 2002
Posts: 154 (0.02 al dì)
Location: Milano
Corso: specialistica, Tico
Anno: 2
Time Online: 2 Days, 20:49:47 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

11-02-2007 09:41

nic

.illuminato.

User info:

Registered: Jun 2002
Posts: 154 (0.02 al dì)
Location: Milano
Corso: specialistica, Tico
Anno: 2
Time Online: 2 Days, 20:49:47 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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...

11-02-2007 09:43

nic

.illuminato.

User info:

Registered: Jun 2002
Posts: 154 (0.02 al dì)
Location: Milano
Corso: specialistica, Tico
Anno: 2
Time Online: 2 Days, 20:49:47 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

11-02-2007 10:42

ripe

- up in the mountains -

User info:

Registered: Jun 2002
Posts: 9469 (1.10 al dì)
Location: Cinisellooo
Corso: TICO TICO
Anno: Primo
Time Online: 61 Days, 2:33:39 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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!»

11-02-2007 10:45

nic

.illuminato.

User info:

Registered: Jun 2002
Posts: 154 (0.02 al dì)
Location: Milano
Corso: specialistica, Tico
Anno: 2
Time Online: 2 Days, 20:49:47 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

11-02-2007 10:49

ripe

- up in the mountains -

User info:

Registered: Jun 2002
Posts: 9469 (1.10 al dì)
Location: Cinisellooo
Corso: TICO TICO
Anno: Primo
Time Online: 61 Days, 2:33:39 [...]
Status: Offline