 | |
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 |
| dicane |
| sapete se per caso e' stata accennata una possibile data per il secondo compitino? |
| Drake83 |
Originally posted by dicane
sapete se per caso e' stata accennata una possibile data per il secondo compitino?
yes si è parlato del 25 o 26. + probabile 25 però! |
| supponiamoche |
| facciamo qualche tema d'esame insieme in preparazione del 2 compitino? |
| monik |
Originally posted by dicane
sapete se per caso e' stata accennata una possibile data per il secondo compitino?
è stata confermato il 25 come data per il secondo compitino!
http://www.ccdi.unimi.it/it/avvisi/4657.html |
| dicane |
Purtroppo non ho potuto seguire molte lezioni dopo il primo compitino quindi non sono molto informato... Bisogna iscriversi tramite sifa all'appello di gennaio o a quello di febbraio??
Vi ringrazio! |
| XXXX |
| il prof nn ha detto nulla a riguardo..penso che tutti quelli che sono passati al 1 compitino siano matematicamente iscritti al secondo! |
| dicane |
| si ma per registrare l'esame finiti i 2 compitini bisogna in ogni caso iscriversi a un appello... cmq se non ha detto niente probabilmente sara' quello di febbraio |
| dicane |
bene, leggo questo avviso sul sito di Trubian:
AVVISI
Gli studenti che il 25 gennaio intendono svolgere la seconda prova in itinere di FRO sono pregati di NON iscriversi all’appello mediante il sistema SIFA e di disiscriversi qualora lo avessero fatto. Grazie per la collaborazione. |
| dicane |
Qualcuno e' in grado di fare l'esercizio 1 preso da questo pdf: http://homes.dsi.unimi.it/~trubian/EserciziiPLI0.pdf
???
A parte che non so come si dovrebbe eliminare "opportunamente" la var x3... ho provato a risolverlo come un problema di PL aggiungendo una var ausiliaria, ma mi viene w*>0 (impossibile). |
| XXXX |
| qualcuno ha fatto l'esercizio num 4 del tema d'esame del 13/4/05 d fro?!? |
| dicane |
Originally posted by XXXX
qualcuno ha fatto l'esercizio num 4 del tema d'esame del 13/4/05 d fro?!?
Ho provato a risolvere l'esercizio 4 del 13/04/05 ma mi sono bloccato a un certo punto, posto cmq quello che ho fatto magari qualcuno puo darmi una mano :-) |
| dicane |
| io comunque ho un dubbio sui problemi di max da risolvere con il simplesso duale... Bisogna trasformarli in problemi di min?? altrimenti sapreste dirmi qual'e' la regola per selezionare il pivot per problemi di max? |
| XXXX |
a me l'esercizio è diverso gia dal primo pivot..perche io prendo quello sotto al tuo ovvero entra x2 esce x4.perche da quel che ho capito per trovare la soluzione ottima si mettono a sistema i 2 vincoli e prima d passare al simplesso duale devi ritrovare qst soluzione cn il simplesso primale...
3x1+2x2=6
-3x1+2x2=0
x1=1
x2=3/2
0 1 0 0 | 0
---------------
3 2 1 0 | 6
3 2 0 1 | 0
esce x4 entra x2
3/2 0 0 -1/2 | 0
------------------------
6 0 1 -1/2 | 6
-3/2 1 0 1/2 | 0
esce x3 entra x2
0 0 -1/4 -3/8 |-3/2
------------------------
1 0 1/6 -1/2 | 1
0 1 1/4 1/2 | 3/2
ora che ho la soluzione ottima faccio il primo taglio d gomory
x3=1/4
x4=1/2
termine noto= 3/2-1=1/2
tdg#1
1/4x3+1/2x4>=1/2
inserisco nel tabluau qst riga e applico il simplesso duale solo che poi nn mi viene mai una soluzione intera ma sempre frazionaria...boh...
per la regola dei problemi d max:
1)prendo il termine noto frazionario maggiore
2)divido ogni costo peri valori della riga in cui si trova il termine noto che ho scelto...
3)il pivot sarebbe il valore minore... |
| dicane |
Hai ragione per quanto riguarda il pivot.. poi per quanto riguarda il simplesso duale, l'ho usato perche' avendo sbagliato pivot mi sono ritrovato un valore negativo tra le b...
Per quanto riguarda il pivot del simplesso duale,
se ho un prob di min:
1)determino la riga del pivot prendendo il valore di b negativo lessicograficamente piu piccolo
2)determino la colonna prendendo il rapporto piu piccolo tra i coefficenti e gli elementi negativi della riga selezionata
Per un problema di massimo invece com ci si comporta? |
| XXXX |
l'ho scritto sopra..
prendo il valore di b (negativo) piu grande..
e poi fai la stessa cosa del min
ma quindi l'esercizio?poi mi sn bloccata..tu hai provato a rifarlo? |
| dicane |
comunque non va preso il valore negativo di b piu grande...
Il libro dice il valore di b negativo lessicograficamente piu piccolo
e fin qui non ci sono dubbi, nel senso che questa regola vale sia per problemi di min che per problemi di max...
Per quanto invece riguarda il determinare la colonna del pivot, in un problema di max ho la riga 0 con valori negativi, in un problema di min ho valori positivi. Quindi quando faccio il rapporto in un problema di max ho come risultato un valore negativo... ad esempio se ho -1/|-2| e -1/|-4| quello piu piccolo in valore assoluto e' -1/4, quello piu piccolo (nel senso di piu negativo) e' -1/2. Quale dei due va scelto??
Cmq no non ho provato ad andare avanti con l'esercizio, dopo provo... |
| XXXX |
| il piu piccolo in valore assoluto...ovvero 1/4 |
| dicane |
ok ti ringrazio.
Provando a rifarlo ho notato che all'ultimo passaggio del simplesso fai uscire x3 e entrare x2, secondo me deve entrare x1 non x2... perche' tra 6/6 e 0/-(2/3) devi scegliere il primo.. visto che la regola dice che il termine sotto la frazione deve essere > 0 (se non ricordo male).
Ho provato a continuare l'esercizio applicando il taglio di gomory ma a quel punto mi esce una soluzione non ammissibile perche' ho tra i coefficenti un valore positivo. Ho tolto il coeff positivo applicando il simplesso dopodiche' ho fatto un altro taglio, e un altro simplesso duale, ma viene una cosa eterna.. a un certo punto mi sono fermato perche' non credo possa venire cosi' lungo un esercizio.....
Spero qualcuno sappia come risolverlo.... :help: |
| Drake83 |
Originally posted by dicane
ok ti ringrazio.
Provando a rifarlo ho notato che all'ultimo passaggio del simplesso fai uscire x3 e entrare x2, secondo me deve entrare x1 non x2... perche' tra 6/6 e 0/-(2/3) devi scegliere il primo.. visto che la regola dice che il termine sotto la frazione deve essere > 0 (se non ricordo male).
Ho provato a continuare l'esercizio applicando il taglio di gomory ma a quel punto mi esce una soluzione non ammissibile perche' ho tra i coefficenti un valore positivo. Ho tolto il coeff positivo applicando il simplesso dopodiche' ho fatto un altro taglio, e un altro simplesso duale, ma viene una cosa eterna.. a un certo punto mi sono fermato perche' non credo possa venire cosi' lungo un esercizio.....
Spero qualcuno sappia come risolverlo.... :help:
si applicano i tagli di gomory finchè si deve. Il prof ha detto che lo farà applicare un pò di volte nell'esercizio. e tra l'altro mi sa che ci fa partire con il tableu già rilassato. mi pare eh... |
| dicane |
| Ah quindi tu l'hai fatto? puoi mica postare la soluzione ? :D |
| Drake83 |
Originally posted by dicane
Ah quindi tu l'hai fatto? puoi mica postare la soluzione ? :D
no nn l'ho finito :D ma era giusto quello che hai fatto. con il duale hai trovato una sol frazionaria. riapplichi i tagli di gomory e ti ritrovi un tablue con 6 variabili e risolvi n'altra volta il tableu. Provo a farlo. |
| XXXX |
| provo a farlo anche io...hai ragione ho sbagliato |
| XXXX |
| a me gia la prima matrice che hai scritto mi viene diversa...o meglio la z e le b uguali il resto tutto diverso.. :sad: |
| dicane |
| Ho fatto l'esercizio 5 dell'appello del 14/09/2004 sull'algoritmo di dijkstra, se qualcuno vuole confrontare i rusulatati.... |
| Drake83 |
Originally posted by dicane
Ho fatto l'esercizio 5 dell'appello del 14/09/2004 sull'algoritmo di dijkstra, se qualcuno vuole confrontare i rusulatati....
uki ora lo guardo e vediamo :D |
| Drake83 |
| si coincide con quanto partorito dal mio cervello :D |
| Drake83 |
| si coincide con quanto partorito dal mio cervello :D |
| XXXX |
qualcuno sa spiegarmi la disuguaglianza di chvatal...
:sad: |
| Drake83 |
| è simile a gomory con la differenza che chavatal usa tutte le var del problema. Gomory usa solo le var della base ottima rilassata. |
| dicane |
| credo di essere riuscito a fare l'esercizio 4 del tema d'esame del 13/04/2005. |
| dicane |
| Ho fatto l'esercizio 6 del 17/11/2004 vi viene uguale? |
| Drake83 |
allura per l'esrcizio 4 perchè hai preso il pivot con c(traslato) = 0 e non il negativo? nel simplesso duale bisogna prendere i negativi, no ?
ora provo a guardare il 6! |
| dicane |
secondo me 0 lo puoi prendere, perche' i coeff di un problema di max devono essere <=0, non < 0 e basta!
Quindi quello con rapporto minimo e' lo 0, se guardi nel libro c'e' un esempio praticamente uguale a questo esercizio dove prende lo zero. |
| Drake83 |
Originally posted by dicane
secondo me 0 lo puoi prendere, perche' i coeff di un problema di max devono essere <=0, non < 0 e basta!
Quindi quello con rapporto minimo e' lo 0, se guardi nel libro c'e' un esempio praticamente uguale a questo esercizio dove prende lo zero.
cazzo hai ragione è <= :D
sorry :D |
| Drake83 |
Originally posted by dicane
Ho fatto l'esercizio 6 del 17/11/2004 vi viene uguale?
zì uguale! |
| dicane |
| Sai mica fare gli esercizi branch & bound con rilassamento lagrangiano o con rilassamento per eliminazione? Io quei due metodi di rilassamento non li ho mica capiti.. |
| Drake83 |
Originally posted by dicane
Sai mica fare gli esercizi branch & bound con rilassamento lagrangiano o con rilassamento per eliminazione? Io quei due metodi di rilassamento non li ho mica capiti..
sto per uscire domani provo a rispondere :D |
| Drake83 |
Originally posted by dicane
Sai mica fare gli esercizi branch & bound con rilassamento lagrangiano o con rilassamento per eliminazione? Io quei due metodi di rilassamento non li ho mica capiti..
Se non sbaglio avevo visto un esercizio che diceva di applicare il rilassamento lagrangiano e poi risolvere il problema dello zaiono con b&b.
Considerando che il libro nn li spiega e che mi affido a ciò che ricordo mi pare di aver capito che il rilassamento lagrangiano funziona così:
lui ti da dei coefficenti (che sia chiamano duale del lagrangiano se nn sbaglio);
moltiplichi ogni coefficente al vincolo che ti comunica lui;
prendi i vincoli che hai moltiplicato e li sommi sulla funzione obbiettivo. Ora il problema è che devi assegnare (ai vincoli spostati) i segni correttamente in modo tale che se la funzione obbiettivo è un max allora il valore di c (traslato)x aumenti e nel caso del minimo diminuisca.
Il rilassamento surrogato invece moltiplica i vincoli che comunica lui e poi esegue la somma algebrica tra i vari vincoli.
cortesemente chi mi dice quante cagate ho scritto? :D
e poi mi sapreste spiegare come calcolare i flussi ad ogni iterazione per le reti incrementali ?
:D |
| dicane |
Ti ringrazio per la risposta anche se questi argomenti continuano a rimanermi un po oscuri visto che non c'ero quando li ha spiegati...
Nel compitino secondo te le mettera' queste cose?
Ha fatto esercizi su questi metodi?
se si puoi mica postarli?! |
| Drake83 |
ma secondo me li metterà ma stand-alone nel senso non applicati a b&b ad esempio. Ha lezione ha detto una cosa del tipo: "sono boiate gli esercizi sui rilassamenti che vi metto ma nn li fate mai e perdete sempre 3 punti"
:D boh!
Sui flussi nada? :D |
| dicane |
Da quel che ho capito io per i flussi, inizi con un percorso a caso (a meno che l'esercizio non ti dia dei flussi di partenza) poi man mano aggiungi percorsi finche non riesci piu a raggiungere t partendo da s. Ogni volta che utilizzi un percorso devi tener traccia della capacita' residua e del flusso attuale, la capacita' residua la segni con una freccia nel verso del flusso originale, il flusso utilizzato lo segni nel verso opposto. Quando non riesci piu a creare dei percorsi che da s arrivano a t dovresti avere la soluzione ottima.
Io ho rifatto l'esempio che aveva fatto a lezione con dei percorsi alternativi, lo metto in allegato se ti interessa. |
| dicane |
| Tu per caso riesci a postare qualche esempio sui rilassamenti??? |
| Drake83 |
| grazie mille! :D ora vedo l'esempio postato da te e provo a vedere se ho degli esercizi sui rilassamenti. Ma credo e spero che lunedì ci faccia vedere degli esercizi sui rilassamenti! |
| Drake83 |
| sarò tedioso ma come si fa a calcolare il flusso di volta in volta? faccio la somma tra i tagli entranti e uscenti dei noti che uso per il percorso ? |
| dicane |
| Tu provi un percorso, da s a t.. per vedere la capacita' massima di quel percorso, se durante il percorso passi tra un arco con capacita' residua 5, e il successivo con capacita' residua 3, il flusso massimo e' 3, perche' non puoi far passare 5 in un arco con capacita' 3. In questo caso il primo arco diventera' con capacita' residua 2 e flusso 3, il secondo arco con capacita' residua 0 e flusso 3. |
| Drake83 |
Originally posted by dicane
Tu provi un percorso, da s a t.. per vedere la capacita' massima di quel percorso, se durante il percorso passi tra un arco con capacita' residua 5, e il successivo con capacita' residua 3, il flusso massimo e' 3, perche' non puoi far passare 5 in un arco con capacita' 3. In questo caso il primo arco diventera' con capacita' residua 2 e flusso 3, il secondo arco con capacita' residua 0 e flusso 3.
ok provo a fare un po di esercizi. Provo a fare il secondo compitino del 2004/2005! se riesco a scannerizzare posto il mio obrobrio! :) |
| joker402 |
Mi inserisco con una domanda! Nel simplesso duale, con che criterio va scelto l'elemento di pivot??
sul libro dice di fare c/|a| e prendere il valore minore, ma il prof a lezione mi sembra che abbia fatto in modo diverso... Il dubbio mi sorge soprattutto quando c è negativo. |
| Drake83 |
Originally posted by joker402
Mi inserisco con una domanda! Nel simplesso duale, con che criterio va scelto l'elemento di pivot??
sul libro dice di fare c/|a| e prendere il valore minore, ma il prof a lezione mi sembra che abbia fatto in modo diverso... Il dubbio mi sorge soprattutto quando c è negativo.
si considera la riga in cui il termine noto è negativo. da quella riga uscirà fori il pivot e lo si ricava con la formuletta che hai postato. si prendono i c negativi o uguali a 0 e si fa il rapporto con gli elementi della riga pivot. se ci sn più righe pivot si sceglie l'ordine lessicografico.
giusto? |
| joker402 |
Originally posted by Drake83
si considera la riga in cui il termine noto è negativo. da quella riga uscirà fori il pivot e lo si ricava con la formuletta che hai postato. ok. la formuletta era la cosa su cui ero dubbioso.
si prendono i c negativi o uguali a 0 e si fa il rapporto con gli elementi della riga pivot. se ci sn più righe pivot si sceglie l'ordine lessicografico.
uhm... non è: si prendono gli A negativi o uguali a 0 ? cioè cerco fra gli elementi non positivi della riga pivot, e li considero per fare i rapporti c/|a| |
| dicane |
| si prendi gli a < di 0, se hai un problema di max le c sono per forza <= 0 poi scegli la colonna che ha il rapporto c/|a| minimo in valore assoluto |
| dicane |
| qualcuno puo postare qualche esercizio sui rilassamenti? :D |
| joker402 |
Originally posted by dicane
poi scegli la colonna che ha il rapporto c/|a| minimo in valore assoluto
quindi devo fare i rapporti c/|a|, e poi farne il valore assoluto per prendere il minore?
o basta prendere il minore fra i c/|a|?
Ad esempio:
c=-1/4 a=-1/4 --> c/|a| = (-1/4)/(1/4) = -1
c=-1/4 a=-3/4 --> c/|a| = (-1/4)/(3/4) = -1/3
quale prendo? -1 perchè è il più piccolo? o devo fare il valore assoluto anche di questi due valori trovati?
(credo di aver capito cosa avevi scritto, ma vorrei esserne certo :D )
sui rilassamenti invece non ci sono ancora... mi spiace! |
| XXXX |
qualcuno oggi è andato a lezione e puo postare gli esercizi fatti?!?
graziee |
| dicane |
Ah dimenticavo... qualcuno sa dirmi come si calcola l'upper bound di dantzig? (magari con un esempio..)
Grazie :-) |
| dicane |
| ah, dimenticavo l'allegato... |
| dicane |
| ops, ho fatto un po di casini.. eccolo |
| Drake83 |
Originally posted by dicane
Ah dimenticavo... qualcuno sa dirmi come si calcola l'upper bound di dantzig? (magari con un esempio..)
Grazie :-)
intendi nei problemi dello zaino vero? l'ub sarebbe il rilassamento della soluzione migliore di un problema di zaino. ad un certo punto hai una variabile che nn puoi usare completamente e che arrotondi. prendi i profitti delle variabili che hai usato per riempire lo zaino (compresa quella frazionaria) e le usi nella funzione obiettivo. arrotondi poi per difetto se il rislutato uscirà con la virgola. Intendevi questo o nn ho capito un cazzo di ciò che chiedevi? :D |
| dicane |
Ti ringrazio per la risposta, io pensavo che l'upper bound di dantzig fosse qualcos'altro vedendo la definizione del libro (che non capivo).
Quindi in conclusione e' l'upper bound che si usa nei problemi dello zaino... grazie. |
| dicane |
Per caso puoi anche togliermi un ultimo dubbio che mi e' venuto sui tagli di gomory? ...avendo piu valori frazionari nelle b non mi ricordo come va scelta la riga sulla quale fare il taglio.
Ad esempio tra 27/8 e 9/4 quale scelgo?
Io inizialmente credevo andassero scelte in ordine lessicografico ma l'ultima volta a lezione ha detto che bisogna scegliere quelli con valore piu vicino a 1/2.
Qui pero' si ha 27/8 = 3.375 e 9/4=2,25. Secondo la mia logica e' piu vicino 2,25.. ma il libro sceglie 27/8. |
| Drake83 |
Originally posted by dicane
Per caso puoi anche togliermi un ultimo dubbio che mi e' venuto sui tagli di gomory? ...avendo piu valori frazionari nelle b non mi ricordo come va scelta la riga sulla quale fare il taglio.
Ad esempio tra 27/8 e 9/4 quale scelgo?
Io inizialmente credevo andassero scelte in ordine lessicografico ma l'ultima volta a lezione ha detto che bisogna scegliere quelli con valore piu vicino a 1/2.
Qui pero' si ha 27/8 = 3.375 e 9/4=2,25. Secondo la mia logica e' piu vicino 2,25.. ma il libro sceglie 27/8.
aspè se parli dei valori noti negativi dei prendere quelli in ordine lessicografico...tu parli del rapporto tra |c / a| una volta scelta la riga di pivot...giusto ? |
| dicane |
| nono io parlo di come scegliere la riga dalla quale generare il taglio avendo piu di un valore frazionario nelle b |
| UncleBo |
| di solito la da il testo..in caso contrario,secondo teoria,dovresti scegliere quella con il termine frazionario più grande |
| dicane |
| ok ti ringrazio, ma allora il valore frazionario piu vicino a 1/2 in quale caso andava usato?? |
| UncleBo |
| nella scelta della colonna pivot |
| XXXX |
| qualcuno ha fatto il secondo compitino del 2004/2005?!?:-D |
| Konrad |
Originally posted by Drake83
si considera la riga in cui il termine noto è negativo. da quella riga uscirà fori il pivot e lo si ricava con la formuletta che hai postato. si prendono i c negativi o uguali a 0 e si fa il rapporto con gli elementi della riga pivot. se ci sn più righe pivot si sceglie l'ordine lessicografico.
giusto?
ma quando la c e' uguale a zero come si fa a fare il rapporto? :? |
| XXXX |
qualcuno puo farmi un riassuntino del Branch&bound quando fermarsi e che ramo scegliere?!?magari cn un esempio?!
uff sono in crisi :( |
| dicane |
Originally posted by Konrad
ma quando la c e' uguale a zero come si fa a fare il rapporto? :?
Allora se parli del simplesso duale il pivot lo scegli in questo modo:
1) va scelta la riga con b < 0 (se ce n'e' piu di una: ordine lesicografico )
2) la colonna va scelta facendo il rapporto |Cij/Aij| dove Cij in un problema di max e' <= 0 (in un problema di min e' >=0) Aij deve sempre essere < 0. La colonna da scegliere e' quella per cui il rapporto e' piu vicino a 1/2.
Spero di non aver detto cazzate, se qualcuno puo confermare... |
| dicane |
Originally posted by XXXX
qualcuno puo farmi un riassuntino del Branch&bound quando fermarsi e che ramo scegliere?!?magari cn un esempio?!
uff sono in crisi :(
Mi associo, anch'io ho qualche dubbio sul branch & bound, magari qualcuno puo risolvere l'esercizio 5 di questo tema d'esame?
http://homes.dsi.unimi.it/~trubian/ROAppello171104.pdf |
| dicane |
Originally posted by XXXX
qualcuno ha fatto il secondo compitino del 2004/2005?!?:-D
Io ho provato a fare l'esercizio 2, se vuoi possiamo confrontare i risultati... |
| monik |
Originally posted by dicane
Ho fatto l'esercizio 6 del 17/11/2004 vi viene uguale?
ma scusa nel primo passaggio devi prendere il 2 sulla prima riga, e non quello sulla seconda, perche il pivot è il min >0!!!no?! |
| XXXX |
Originally posted by dicane
Io ho provato a fare l'esercizio 2, se vuoi possiamo confrontare i risultati...
ok ora lo faccio...
il 3 intano mi viene:
3-6
5-6
5-2
2-1
2-4
4-7
peso minimo 68
ps: qualcuno puo postare gli esercizi fatti a lezione lunedi?!? |
| dicane |
Originally posted by Drake83
intendi nei problemi dello zaino vero? l'ub sarebbe il rilassamento della soluzione migliore di un problema di zaino. ad un certo punto hai una variabile che nn puoi usare completamente e che arrotondi. prendi i profitti delle variabili che hai usato per riempire lo zaino (compresa quella frazionaria) e le usi nella funzione obiettivo. arrotondi poi per difetto se il rislutato uscirà con la virgola. Intendevi questo o nn ho capito un cazzo di ciò che chiedevi? :D
Sisi mi avevano gia risposto a riguardo, ti ringrazio lo stesso! :D |
| dicane |
Originally posted by XXXX
ok ora lo faccio...
il 3 intano mi viene:
3-6
5-6
5-2
2-1
2-4
4-7
peso minimo 68
ps: qualcuno puo postare gli esercizi fatti a lezione lunedi?!?
Anch'io ho appena fatto il 3 e mi viene uguale :) |
| XXXX |
ma nel testo nn dice che bisogna esplorare prima la radice in cui la variabile xi=0?!?
quindi mi sa che viene
0
x=1 x=0
2 1
no?!? |
| dicane |
Originally posted by monik
ma scusa nel primo passaggio devi prendere il 2 sulla prima riga, e non quello sulla seconda, perche il pivot è il min >0!!!no?!
L'esercizio a cui ti riferisci e' su Dijkstra... mi sa che hai sbagliato a quotare, se mi dici quale esercizio intendi controllo.
Ciao! |
| dicane |
Originally posted by XXXX
ma nel testo nn dice che bisogna esplorare prima la radice in cui la variabile xi=0?!?
quindi mi sa che viene
0
x=1 x=0
2 1
no?!?
Si hai ragione non avevo letto, per il resto il risultato non dovrebbe cambiare se si esplora in maniera diversa.. a te viene uguale?
Ma poi highest first e' uguale e best bound o cosa intende? |
| XXXX |
no è l'esercizio 2 del secondo compitino...
nella descrizione c'è scritto si esplori per primo il ramo dell'albero associato al vincolo xi=0.
un'altra domanda: nel tuo primo nodo si ha che x=(1,1/2,1,0,0,0)
e a me la b ovvero la capacita residua mi viene =(7,6,0,0,0,0)
è giusto? facendo cosi pero l'ub = 40+38+7(14/2) =127
mmm..mi sa che faccio un po d casino...
:( |
| monik |
Originally posted by dicane
L'esercizio a cui ti riferisci e' su Dijkstra... mi sa che hai sbagliato a quotare, se mi dici quale esercizio intendi controllo.
Ciao!
ah scusa intendevo l'es 4 del 13/04/05... |
| dicane |
Originally posted by XXXX
no è l'esercizio 2 del secondo compitino...
nella descrizione c'è scritto si esplori per primo il ramo dell'albero associato al vincolo xi=0.
un'altra domanda: nel tuo primo nodo si ha che x=(1,1/2,1,0,0,0)
e a me la b ovvero la capacita residua mi viene =(7,6,0,0,0,0)
è giusto? facendo cosi pero l'ub = 40+38+7(14/2) =127
mmm..mi sa che faccio un po d casino...
:(
il 7*(14/2) non ho capito da dove esce, il mio conto e' 40+14/2+38 = 85 |
| XXXX |
scusa allora come hai calcolato l'ub del nodo 0?!?
io ho fatto 40+14+ arrotondamento per difetto di 5(38/6)
dove il 5 è il valore della capacita dello zaino al passo precedente..
b=(7,5 ,0,0,0,0) |
| dicane |
l'ub nel nodo 0 l'ho calcolato provando a mettere per primi gli elementi con rapporto massimo... quindi 1,1... a questo punto ho cap residua 5, a quel punto uso 5/6 del terzo per "riempirlo". l'UB allora viene 1*40 + 1*14 + 5/6*38 = 85
Comunque non so se il mio procedimento e' corretto, infatti continuavo a chiedere spiegazioni sul branch & bound nei post precedenti (purtroppo senza avere risposte) :D |
| XXXX |
si cosi è giusto e quindi devi fare la stessa cosa nel nodo 1 no?!
anche se secondo me c'è qulcosa che nn va...provo a rifarlo...uff ma nessuno l'ha fatto?!?
:razz: |
| dicane |
Originally posted by monik
ah scusa intendevo l'es 4 del 13/04/05...
Se guardi sul libro a pag 86 c'e' un esempio praticamente uguale
comunque le b devono essere >= 0 non > e basta. Sono gli elementi di A che devono essere > 0. |
| monik |
Originally posted by dicane
Se guardi sul libro a pag 86 c'e' un esempio praticamente uguale
comunque le b devono essere >= 0 non > e basta. Sono gli elementi di A che devono essere > 0.
ahhh...hai ragione...mi confondevo con le A!
GRAZIE! |
| Archimonde |
| c'è qkn che ha fatto il primo esercizio degli ultimi tre appelli? |
| XXXX |
io nn li so proprio fare.c'è qualche regola??
altra domanda: qualcuno sa fare i modelli matematici ? ad esempio l'esercizio numero 5 del 2 compitino? |
| Archimonde |
| perdonami son un pò nel pallone.. cosa intendi con secondo compitino? quello del 5-4-06? |
| XXXX |
| qualcuno ha fatto l'ese 6 del 27/07/04? |
| XXXX |
Originally posted by Archimonde
perdonami son un pò nel pallone.. cosa intendi con secondo compitino? quello del 5-4-06?
no del 19/01/05 |
| Archimonde |
| l'ese 6 è quello eseguibile con l'algoritmo di ford-fulkerson... quello con cui ti trovi tt i cammini ammissibili e vai a incrementare il flusso di volta in volta... |
| Drake83 |
Originally posted by dicane
l'ub nel nodo 0 l'ho calcolato provando a mettere per primi gli elementi con rapporto massimo... quindi 1,1... a questo punto ho cap residua 5, a quel punto uso 5/6 del terzo per "riempirlo". l'UB allora viene 1*40 + 1*14 + 5/6*38 = 85
Comunque non so se il mio procedimento e' corretto, infatti continuavo a chiedere spiegazioni sul branch & bound nei post precedenti (purtroppo senza avere risposte) :D
Allora io ho provato a farlo ed esplorandolo succede che ho trovato 4 nodi.L' ub rilassato mi viene 85. esploro prima x1= 0 e trovo subito un LB= 84 (le var 1 2 e 4 sono intere). passo al nodo 2 (con x3=1). Con tale nodo ho ub=85. creo altri due nodi (x2=0 e x2=1). Il nodo 3 ha ub < del LB quindi è inutile considerarlo. Stesso vale per il nodo 4 che ha UB=84 valore uguale a LB. erro? :D |
| XXXX |
| anche a me viene cosi pero ho preso la soluzione cn ub=84 perche intera...no?!? |
| XXXX |
Originally posted by Archimonde
l'ese 6 è quello eseguibile con l'algoritmo di ford-fulkerson... quello con cui ti trovi tt i cammini ammissibili e vai a incrementare il flusso di volta in volta...
si lo so..ma era per confrontare i risultati...:-D |
| Drake83 |
Originally posted by XXXX
anche a me viene cosi pero ho preso la soluzione cn ub=84 perche intera...no?!?
si si :D quello è il lb che corrisponde alla soluzione intera del nodo 1 :D |
| XXXX |
| provi a fare il 6 del 27/07/04? |
|
|
|
|
