Mirthis

User info:

Registered: Oct 2002
Posts: 87 (0.01 al dì)
Location: Vaprio d'Adda (MI)
Corso: Informatica specialistica
Anno: Primo
Time Online: 1 Day, 20:45:37 [...]
Status: Offline

Post actions:

Ciao, purtroppo non sono riuscito a seguire le ultime lezioni e guardando ora i vecchi temi di esami ho un dubbio (per ora )
In un esercizio c'e' la seguente richiesta:

Si trovi con l'algoritmo di Ford-Fulkerson un fluasso di valore massimo da s a t a partire dal flusso ammissibile da inviare nelle prime due iterazioni da cinque unità lungo il camminos,3,4,2,t e di 5 unità lungo il cammino s,3,4,1,2,t

e viene dato un grafo con le capacità degli archi. La cosa che non capisco e' cosa voglia dire la parte finale (dal grassetto in poi). Qualcuno ha delle idee?

__________________
Land ...of Silence - Sonata Arctica Italian Fan Site

teox1

Consigliere

User info:

Registered: Dec 2003
Posts: 508 (0.06 al dì)
Location: .....
Corso: Telecoz
Anno: Doct
Time Online: 3 Days, 14:43:16 [...]
Status: Offline

Post actions:

per quanto ne ho capito io...vuol dire che i primi due cammini te li da lui e devi rispettarli..poi puoi scegliere tu il cammino che referisci...ma i primi due devono essere quelli li...

Mirthis

User info:

Registered: Oct 2002
Posts: 87 (0.01 al dì)
Location: Vaprio d'Adda (MI)
Corso: Informatica specialistica
Anno: Primo
Time Online: 1 Day, 20:45:37 [...]
Status: Offline

Post actions:

Originally posted by teox1
per quanto ne ho capito io...vuol dire che i primi due cammini te li da lui e devi rispettarli..poi puoi scegliere tu il cammino che referisci...ma i primi due devono essere quelli li...

E le 5 unità sarebbe di quanto aumenta il flusso?

__________________
Land ...of Silence - Sonata Arctica Italian Fan Site

teox1

Consigliere

User info:

Registered: Dec 2003
Posts: 508 (0.06 al dì)
Location: .....
Corso: Telecoz
Anno: Doct
Time Online: 3 Days, 14:43:16 [...]
Status: Offline

Post actions:

caspita...mi metti in difficoltà..ne abbiamo fatto uno simile in classe..ma non ricordo che parlasse di 5 unità..ci dava solo i due cammmini.... o caspita....

teox1

Consigliere

User info:

Registered: Dec 2003
Posts: 508 (0.06 al dì)
Location: .....
Corso: Telecoz
Anno: Doct
Time Online: 3 Days, 14:43:16 [...]
Status: Offline

Post actions:

volevo porre anche io delle domande-.-.- ma quando dobbiamo applicare il taglio di Gomory procediamo con il simplesso primale e successivamente può essere necessario il simplesso duale..finchè non troviamo la soluzione ottima...una volta che troviamo la soluzione ottima ma abbiamo ancora valori frazionari...quali scegliamo?
es: siamo in questo caso...dopo aver applicato il simplesso duale/tableau

x1 x2 x3 x4 x5

0 0 2/3 0 1/3 | -2/3
------------------------------------------
1 0 1 0 0 | 1 x1
0 1 1/3 0 -1/3 | 5/3 x2
0 0 1/3 1 -4/3 | 2/3 x4

il libro sceglie di prendere la seconda riga (quella con 5/3) perchè prende quella e non la terza? posso scegliere quella che voglio??


oltretutto 5/3 ( che fa 1.666) lo fa tendere a 1..io lo avrei fatto tendere a 2....


Una altra cosa che non ho capito riguarda il problema di branch con lo zaino... Sul libro nell'unico esercizio che c'è inizia istanziando la variabile x1=1 e x1=0 invece nell'esercizio che abbiamo fatto in classe(quello della capienza 22 con Pj [52,40,389.1] e Wj [15.5.13.3.1]inizia istanziando x3=1 e x3=0...in base a cosa decido quale variabile utilizzare?

Grazie mille...e preparatevi alle future domande...inquanto ogni giorno mi escono dubbi nuovi...

teox1

Consigliere

User info:

Registered: Dec 2003
Posts: 508 (0.06 al dì)
Location: .....
Corso: Telecoz
Anno: Doct
Time Online: 3 Days, 14:43:16 [...]
Status: Offline

Post actions:

non era riuscita molto bene....

x1 x2 x3 x4 x5

0 0 2/3 0 1/3 | -2/3
------------------------------------------
1 0 1 0 0 | 1 x1
0 1 1/3 0 -1/3 | 5/3 x2
0 0 1/3 1 -4/3 | 2/3 x4

teox1

Consigliere

User info:

Registered: Dec 2003
Posts: 508 (0.06 al dì)
Location: .....
Corso: Telecoz
Anno: Doct
Time Online: 3 Days, 14:43:16 [...]
Status: Offline

Post actions:

vabbè scusate..purtroppo. mi avvicina i valori....

Mirthis

User info:

Registered: Oct 2002
Posts: 87 (0.01 al dì)
Location: Vaprio d'Adda (MI)
Corso: Informatica specialistica
Anno: Primo
Time Online: 1 Day, 20:45:37 [...]
Status: Offline

Post actions:

Teox tra poco guardo quella cosa che hai postato e vedo se posso darti una mano (ci devo pensare). Intanto credo di aver capito la questione dell'esercizio sul flusso massimo.
La cosa che mi aveva messo in crisi in quell'esercizio e che seguendo uno dei due cammini indicati la capacità minima non era 5 e quindi non aveva senso che il flusso aumentasse di quella quantità. Su un altro tema di esame c'e' un esercizio uguale e le unità di cui parla corrispondono al valore dell'arco di capacità minima che si trova sul cammino che indica lui. Quindi o c'era un errore in quell'altro esercizio oppure devo aver visto male io
Ora mi rimane solo da capire la storia del flusso minimo... mah...

__________________
Land ...of Silence - Sonata Arctica Italian Fan Site

Mirthis

User info:

Registered: Oct 2002
Posts: 87 (0.01 al dì)
Location: Vaprio d'Adda (MI)
Corso: Informatica specialistica
Anno: Primo
Time Online: 1 Day, 20:45:37 [...]
Status: Offline

Post actions:

Originally posted by teox1
una volta che troviamo la soluzione ottima ma abbiamo ancora valori frazionari...quali scegliamo?

Mmmh, non ho trovato nessuna informazione. Ho visto anche un esercizio che abbiamo fatto a lezione ma non ho segnato niente sulla regola con cui si sceglie da quale vincolo ricavare il taglio

[QUOTE]
oltretutto 5/3 ( che fa 1.666) lo fa tendere a 1..io lo avrei fatto tendere a 2....

__________________
Land ...of Silence - Sonata Arctica Italian Fan Site

Mirthis

User info:

Registered: Oct 2002
Posts: 87 (0.01 al dì)
Location: Vaprio d'Adda (MI)
Corso: Informatica specialistica
Anno: Primo
Time Online: 1 Day, 20:45:37 [...]
Status: Offline

Post actions:

Un nuovo dubbio
Nel modello del tema d'esame del 10 febbraio

Come cambia il modello se il caseificio deve scegliere in alternativa (o l'uno o l'altro) fra due tipi di mozzarella

come si rappresenta la condizione che può essere prodotto solo uno dei due tipi di mozzarella?

Bulma

.grande:maestro.

User info:

Registered: Jun 2002
Posts: 1706 (0.20 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline

Post actions:

L'abbiamo visto in classe. Introduci due variabili booleane (y_m per la mozzarella M, y_m1 per la mozzarella M1) e imponi che
y_m + y_m1 <= 1.
Inoltre, occorre modificare i vincoli di produzione di M e M1 (non ho gli appunti sottomano, cmq dovresti avere M <= di un certo numero n, M1 <= n1) in modo che diventino:
M <= n * y_m
M1 <= n1 * y_m1

Spero di essermi ricordata correttamente!

__________________
The man in black fled across the desert and the gunslinger followed.

teox1

Consigliere

User info:

Registered: Dec 2003
Posts: 508 (0.06 al dì)
Location: .....
Corso: Telecoz
Anno: Doct
Time Online: 3 Days, 14:43:16 [...]
Status: Offline

Post actions:

ragazzi...perchè continuano a venrrmi dubbi? stavo facendol'esercizio 5 ( solo relativo al taglio di gomory) del tema d'esame del 10/02/04.....
come faccio a iniziare avendo tutte uguaglianze? non ho variabili in base...come si procede?
In più secondo voi nel compitino ci chiederà cose anche riguardanti la prima parte? spero di no anche perchè se no a cosa sarebbe servito fare il 1 compitino?
grazie mille.... a presto con i prossimi dubbi

Mirthis

User info:

Registered: Oct 2002
Posts: 87 (0.01 al dì)
Location: Vaprio d'Adda (MI)
Corso: Informatica specialistica
Anno: Primo
Time Online: 1 Day, 20:45:37 [...]
Status: Offline

Post actions:

Grazie Bulma, credo di aver capito come va fatto il modello
Teox per l'esercizio che dici tu, non e'ì che riesci prima a spiegarmi come si fanno gli altri punti (o meglio il primo)? Così come sono messo ora non ho idea da dove dovrei partire per il taglio

__________________
Land ...of Silence - Sonata Arctica Italian Fan Site

teox1

Consigliere

User info:

Registered: Dec 2003
Posts: 508 (0.06 al dì)
Location: .....
Corso: Telecoz
Anno: Doct
Time Online: 3 Days, 14:43:16 [...]
Status: Offline

Post actions:

ops...non avevo letto il testo...io guaradvo la funzione poi passavo direttamente al taglio di gomory...in effetti mi sembrava che mancasse qualcosa..sono prorpio fuso...la troppa ricerca operativa gioca brutti effetti...
però caspita io non ho ripassato le cose del primo compitino...non ci saranno nella seconda parte giusto??

Mirthis

User info:

Registered: Oct 2002
Posts: 87 (0.01 al dì)
Location: Vaprio d'Adda (MI)
Corso: Informatica specialistica
Anno: Primo
Time Online: 1 Day, 20:45:37 [...]
Status: Offline

Post actions:

però caspita io non ho ripassato le cose del primo compitino...non ci saranno nella seconda parte giusto?? [/B]

__________________
Land ...of Silence - Sonata Arctica Italian Fan Site