 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
[compitino] secondo compitino
Clicca QUI per vedere il messaggio nel forum |
| Archimonde |
ho fatto l'es 6!! flusso massimo 35, cammini aumentanti:
- s,3,4,2,t
-s,3,4,1,2,t
-s,3,4,t
-s,1,2,t
sezione minima s,1
Concordi? |
| XXXX |
mmm ma io ho capito che i cammini aumentanti a partire dalle sue 2 iterazioni no?!?
Ps. ma aumentanti nn significa aggiungere ogni volta un nodo in piu al cammino? |
| Archimonde |
| si i primi due sono quelli imposti |
| Archimonde |
| intendi a scannerizzarlo? aspè ci provo |
| Archimonde |
| no aumentanti credo si riferisca al flusso massimo... |
| XXXX |
| perche dice aumentanti come sequenze d nodi...nn come flusso |
| Archimonde |
| ok è venuto stramale!! cmq non pretendiamo dai... |
| Archimonde |
| ma quello credo si riferisca al modo di scriverglielo... cmq potrei sbagliarmi.. ma a te veniva diverso?? |
| XXXX |
si perche io aumentavo sempre la sequenza dei nodi ma mi sn bloccata..nn so..
cmq ho fatto gli stessi passaggi tuoi e nn mi viene cosi..perche ho un arco dal nodo s al nodo 1 d 15 e uno dal nodo 1 al nodo s di 10..
quindi posso fare altri cammini per raggiungere t ovvero...
s-1-4-t
oppure
s-1-2-4-t
no? |
| monik |
Originally posted by Archimonde
ho fatto l'es 6!! flusso massimo 35, cammini aumentanti:
- s,3,4,2,t
-s,3,4,1,2,t
-s,3,4,t
-s,1,2,t
sezione minima s,1
Concordi?
a me viene flusso massimo 40, perche ho fatto anche il cammino: s,1,2,4,t e ls sezione minima viene s,1,2 |
| Archimonde |
| alla fine lui nella domanda chiede cmq flussi e i flussi son quelli fidati ;) non è detto che abbia fatto giusto l'ordine ma almeno la tipologia credo sia giusta :P |
| dicane |
Secondo me il problema qui e' l'arco 1-4, quando fai passare il flusso indicato dall'esercizio la freccia si inverte e diventa 1->4 con capacita'5 . A quel punto puoi utilizzare quel percorso per raggiungere t quindi puoi inviare un flusso ulteriore di 5 seguendo il percorso s,1,4,t. Di conseguenza il flusso massimo dovrebbe essere 40 non 35.
Sbaglio qualcosa? |
| Archimonde |
| ma com'è possibile che tu abbia avuto flusso 40 senza saturare l'arco 1-2 :| da dove sei passato?? |
| Archimonde |
| intendi dire che dopo averlo caricato lo scarico ripassandoci? si è possibile... |
| Archimonde |
| ok ho capito.. |
| monik |
Qualcuno sa risolvere l'es 6 dell'appello 01/06/04?
e l'es 5 dell'appello 17/11/04? |
| XXXX |
ma quindi nn c'entra niente che i cammini siano aumentanti?
lo rifaccio perche a me viene piu d 40 |
| Archimonde |
| si si rifai... qkn sa risolvere i tagli di gomoury senza incertezze? |
| XXXX |
| io penso d riuscirci finisco qui e facciamo un ese ok?tu sceglilo intanto :) |
| Archimonde |
| grazie :D :D l'esercizio è il 4 del 05-04-06 |
| dicane |
A me non tornano i conti con la sezione di capacita' minima... restano raggiungibili da s i nodi: 1,2,3 e ho flusso uscente dalla sezione pari a 45, il flusso entrante invece mi risulta 0.
Non so se devo considerare l'arco 4-1 con flusso entrante 5.. pero' avendolo caricato con 5 e successivamente scaricato di 5 il suo flusso dovrebbe essere 0... |
| monik |
Originally posted by monik
Qualcuno sa risolvere l'es 6 dell'appello 01/06/04?
e l'es 5 dell'appello 17/11/04?
proviamo a fare questi? |
| Archimonde |
xkè 0??
xkè è scarico? |
| XXXX |
fatto
mi viene 45
S=0,1,2,3
archi uscenti grafo originale=20+25=45
ok!!
cammini:
s-3,4,2-t
s-3-4-1-2-t
s-1-2-4-t
s-3-4-t
s-1-2-t
s-1-4-t
|
| Archimonde |
| aspè a me il flusso ora viene 45... xkè c'è anche s,1,2,4,t di flusso 5, cioè quello residuo sull'arco 2-4... |
| Archimonde |
| ottimo allora ^^ |
| monik |
Originally posted by XXXX
fatto
mi viene 45
S=0,1,2,3
archi uscenti grafo originale=20+25=45
ok!!
cammini:
s-3,4,2-t
s-3-4-1-2-t
s-1-2-4-t
s-3-4-t
s-1-2-t
s-1-4-t
ma non puo essere 20+25=45 perchè S=0,1,2,3 ha anche un 15 in uscita da S quindi è: 20+25+15=60 |
| XXXX |
quindi valore flusso max=45?
sezione d capacita minima?!?
e l'opportuno insieme d archi cn un associato peso unitario etc etc
come s fanno?sono domande sempre dello stesso esercizio.. |
| XXXX |
Originally posted by monik
ma non puo essere 20+25=45 perchè S=0,1,2,3 ha anche un 15 in uscita da S quindi è: 20+25+15=60
no perche il valore 15 è tra l'arco 2 e 3
ma siccome fanno entrambi parte d s nn s considera |
| Archimonde |
| allora mi illuminate sui tagli di gomoury? |
| monik |
Originally posted by XXXX
no perche il valore 15 è tra l'arco 2 e 3
ma siccome fanno entrambi parte d s nn s considera
ma 3 non fa parte di S perche non è piu raggiungibile da s! |
| Archimonde |
| si valore flusso max 45, la sezione di capacitò minima non è s,1,2,3? o mi confondo con il taglio di F-F?? |
| XXXX |
| dal nodo 2 è raggiungibile...e alla fine nn devi considerare tutti i nodi raggiungibili da quelli che fanno gia parte d s?!? |
| Archimonde |
| non è raggiungibile? intendi non posso percorrere la strada s-1-2-3? |
| monik |
Originally posted by XXXX
dal nodo 2 è raggiungibile...e alla fine nn devi considerare tutti i nodi raggiungibili da quelli che fanno gia parte d s?!?
ah si hai ragione non avevo visto l'arco 2-3!
ma come si risolvono gli es che sugli archi hanno 2 numeri come l'es 4 del secondo compitino? |
| XXXX |
| certo che s puo..infatti mi fermo li e nn considro anche il nodo 4 perche nn è raggiungibile da nessuno.. |
| Archimonde |
| si riferiscono al costo unitario ma noi non l'avremo domani... |
| monik |
Originally posted by Archimonde
si riferiscono al costo unitario ma noi non l'avremo domani...
ah non c'è....sicuro?! perche io sapevo che non metteva quello sui flussi minimi e basta! |
| Archimonde |
| lol nn abbiamo fatto esercizi sul costo unitario!! |
| XXXX |
mmm...
pero l'ha spiegato no? |
| Archimonde |
| si certo a noi che siam rimasti ad ascoltarlo alla fine dell'ultima lezione ;) |
| monik |
Originally posted by XXXX
mmm...
pero l'ha spiegato no?
si l'ha spiegato, è per quello che avevo dei dubbi! |
| Archimonde |
| mmm se volete esercitarvi fate pure.. a me sembra che l'ultima lezione abbia detto che non c'era... tnt già ci son 4 algoritmi e le arborescenze... |
| XXXX |
quindi lo mette...
pero nel programma nn c'è...mm ma se proviamo a farlo lo stesso?!?nn si sa mai..no? |
| Archimonde |
| mandategli un email!!! così ne avrete la certezza no? |
| XXXX |
mmm..ma l'ese 4 del secondo compitino?!?:?
altra domanda ma se nell'esercizio precedente mi avesse chiesto d cercare il flusso minimo come avrei dovuto fare?!? |
| dicane |
| io avrei scritto 0 :D |
| XXXX |
per trovare il flusso massimo prendo il peso minimo...
e per il flusso minimo il peso massimo??!
mmm...hihi nn penso.. |
| dicane |
| Cmq non mette esercizi con i pesi, l'ha detto a lezione! |
| XXXX |
nn pesi ma capacita residua scusa
ora sto facendo il 4 del 2 compitino..l'avete fatto? |
| dicane |
io ho usato questi percorsi:
1)s,a,d,t -> 6
2)s,b,d,t -> 4
3)s,c,t -> 8
4)s,b,e,t -> 5
Il flusso mi viene 23 e la sezione a,b,c,d,e |
| monik |
Originally posted by dicane
io ho usato questi percorsi:
1)s,a,d,t -> 6
2)s,b,d,t -> 4
3)s,c,t -> 8
4)s,b,e,t -> 5
Il flusso mi viene 23 e la sezione a,b,c,d,e
per favore mi spieghi come si fa quando ci sono due numeri sugli archi? |
| XXXX |
anche a me viene 23
s-a-d-t
s-b-e-t
s-b-d-t
s-b-e-c-t
s-c-t
S= s,a,c,b,e,d
il 4.3 come s fa??:?
|
| dicane |
| credo che il secondo numero sia il costo, non l'ha fatto e non lo mette nel compitino |
| XXXX |
| ma la scelta dei cammini casuale vero? |
| dicane |
| a lezione l'ha sempre fatto in modo casuale se non sbaglio.. |
| XXXX |
no ma ce li mette cosi?:cry:
io sto provando a fare il 4 del 13/4/05 qualcuno l'ha fatto? |
| dicane |
Originally posted by XXXX
no ma ce li mette cosi?:cry:
io sto provando a fare il 4 del 13/4/05 qualcuno l'ha fatto?
Beh penso proprio che uno del genere ci sara'...
Per quanto riguarda lesercizio 4 del 13/04/05 l'avevo gia postato, guarda qua verso fine pagina http://www.dsy.it/forum/showthread....15&pagenumber=2 |
| monik |
Originally posted by dicane
Beh penso proprio che uno del genere ci sara'...
Per quanto riguarda lesercizio 4 del 13/04/05 l'avevo gia postato, guarda qua verso fine pagina http://www.dsy.it/forum/showthread....15&pagenumber=2
sai fare anche il 5 dello stesso appello? |
| dicane |
ho provato intanto a fare il rilassamento lagrangiano che credo venga:
max 15x1 + 18x2 + 16x3 + 15x4 - 18
3x1 + 9x2 + 4x3 + 4x4 <= 14 |
| dicane |
Questa frase pero' per me rimane un mistero:
"Si riordinino gli indici delle variabili in base all'ordinamento utilizzato per risolvere il rilassamento continuo." |
| XXXX |
anche a me viene cosi :-D
poi nn so piu andare avanti |
| monik |
Originally posted by dicane
ho provato intanto a fare il rilassamento lagrangiano che credo venga:
max 15x1 + 18x2 + 16x3 + 15x4 - 18
3x1 + 9x2 + 4x3 + 4x4 <= 14
come si fa? |
| XXXX |
| chiede anche i tagli di chvatal?!o l'analisi di sensitivita che nn l'ha messa nel primo compitino? |
| dicane |
| beh mi pare ci fosse l'analisi di sensitivita' nel primo... per quanto riguarda i tagli di chavtal non lo so (non c'ero quando li ha fatti) |
| XXXX |
| manco io e nn li so fare...:-D |
| monik |
Originally posted by monik
come si fa?
puoi spiegarmi come si fa il rilassamento lagrangiano :) |
| dicane |
| sapreste per caso quali sono le diferenze tra un problema branch & bound di min e uno di max? Il lower bound e l'upper bound si calcolano allo stesso modo? |
| monik |
Originally posted by dicane
sapreste per caso quali sono le diferenze tra un problema branch & bound di min e uno di max? Il lower bound e l'upper bound si calcolano allo stesso modo?
penso che in un problema di min tendi a trovare il minore lower bound, mentre in quello di max quello maggiore!
ad esempio l'es 5 del 17/11/2004 e col min....ma io non riesco proprio a risolverlo! |
| dicane |
Originally posted by monik
puoi spiegarmi come si fa il rilassamento lagrangiano :)
4x1+4x2+4x3+4x4 +
+ 4(3x1+4x2+2x3+x4 - 6) +
+ 1(6 - (x1+2x2-4x3-7x4))
prendi la funzione obiettivo e aggiungi lambda*(Ax-b) o lambda*(b-Ax)
a seconda dei casi.
Nel primo caso hai lambda*(Ax-b) perche' il vincolo e' di >= in un problema di max
nel secondo caso hai un vincolo <= e quindi e' lambda*(b-Ax) |
| dicane |
| Ma la regola di fermarsi quando si incontra un upper bound <= rispetto al lower bound attuale in un problema di max (ammesso che sia giusta :|) va applicata sempre o solo se lo dice esplicitamente il testo? |
| Archimonde |
| non ce la faccio piuuuuuuuuuuuuuuuuuuuuuuuu |
| Archimonde |
| in genere lo dice esplicitamente il testo.. cmq credo sia una regola di logica... o mi sbaglio? |
| dicane |
| daidai ce la puoi fare :D posta un esercizio sul branch & bound (senza zaino) che ti facciamo santo :lode: |
| XXXX |
io so ch eogni nodo ha UB e LB allora il LB è l'arrotondamento per eccesso e UB per difetto
in un prob di min si prende il nodo foglia che ha Ub minore e di max quello maggiore...
no?! |
| XXXX |
l'ese 1 del 13/4/05?!?
:?:?:?
anche io sn fusaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa:shock: |
| Archimonde |
| mi prendo una pausa proseguo dopo mangiato :P se no mi esaurisco tr presto.. |
| monik |
| ragazzi.... io ho scoperto di non saper fare il branch & bound standard (non zaino)...dovete aiutarmi!!! |
| Archimonde |
| tranquillo, la notte è giovane :D |
| XXXX |
ho fatto l'esercizio num 5 sul rilassamento surrogato del tema d'esame 15/06/05
e mi viene:
max 2x1+6x2+3x3+4x4
4x2+5x4<=6
poi come si procede?mi chiede d risolvere il modello rilassato mediante semplici considerazioni dui coef..:? |
| UncleBo |
| considera che la somma di 4x2 + 5x4 deve essere minore di 6 (quindi uno dei due deve andare a zero..se metti a zero x2 nella f.ne obiettivo azzeri un + 6, se metti a zero x4 azzeri un + 4..ti conviene quindi avere una soluzione tipo (1,1,1,0), in questo modo il vincolo è rispettato (4*1 + 5*0 è minore di 6) e la tua sol vale 2+6+3=11 al posto di 2+0+3+4=9... |
| XXXX |
grazie...ma le ha spiegate a lezione?
quindi azzero il valore che mi fa aumentare la soluzione ottima?! |
| dicane |
esendo un problema di max devi trovare il valore massimo possibile, visto che su x1 e x3 non hai vincoli li poni a 1 (il massimo possibile definito nei vincoli) per quanto riguarda x2 e x4 solo una di esse puo essere 1 per via del vincolo 4x2+5x4<=6. Conviene ovviamente scegliere x2=1 perche' ha moltiplicatore 6 e quindi massimizza la funzione obiettivo.
di conseguenza hai 2+6+3 = 11 |
| XXXX |
ooook
arigrazie...
un altro dubbio nn mi va d rileggere
sul simplesso duale
se io ho 2 termini noti negativi quale scelgo per poi andare a calcolare il pivot? |
| dicane |
| quello che da valore frazionario piu vicino a 1/2 se non sbaglio |
| Archimonde |
| parliamo della capacità superiore e il flusso inviato... in realtà la capacità superiore non mi riguarda nei calcoli... vero? |
| dicane |
| cos'e' la capacita' superiore? |
| monik |
Originally posted by dicane
quello che da valore frazionario piu vicino a 1/2 se non sbaglio
ma nei post precedenti evevate detto che si sceglie in ordine lessicografico! |
| Archimonde |
| uno rappresenta il fluso max ipoteticamente inviabile e l'altro quello effettivamente inviato.. |
| dicane |
Originally posted by monik
ma nei post precedenti evevate detto che si sceglie in ordine lessicografico!
E cosa ci vuoi fare.. facciamo un sondaggio? :D
Io inizialmente ero convinto fosse in ordine lessicografico, ma se guardi i post di qualche giorno fa qualcuno ha detto che e' il valore piu vicino a 1/2 e se non sbaglio lo ha anche accennato lunedi a lezione. |
| Archimonde |
| si è vero mi ricordo anche io dell'1/2... |
| Konrad |
Quindi esercizi come il 4-5 del secondo compitino non li mette?
Qualuno puo' mettere un esercizio sul rilassamento lagrangiano?
Uff non so una ceppa :D |
| monik |
Originally posted by dicane
E cosa ci vuoi fare.. facciamo un sondaggio? :D
Io inizialmente ero convinto fosse in ordine lessicografico, ma se guardi i post di qualche giorno fa qualcuno ha detto che e' il valore piu vicino a 1/2 e se non sbaglio lo ha anche accennato lunedi a lezione.
anche io avevo sentito dell' 1/2...va beh...grazie comunque! |
| Archimonde |
| non sei l'unico... |
| Archimonde |
| mai i modelli di programmazione lineare c'è qkn che li sa??? |
|
|
|
|
