.dsy:it. (http://www.dsy.it/forum/)
- Ricerca operativa (http://www.dsy.it/forum/forumdisplay.php?forumid=228)
-- Appello 05/04/2006 (http://www.dsy.it/forum/showthread.php?threadid=29426)

Appello 05/04/2006

ecco..partiamo dal 2 come sempre ;-)

qui abbiamo una variabile libera.. bisogna stare attenti sia nello scrivere la forma standard sia nel duale...

Intanto posto il grafico giusto per precauzione

Merda ho sbagliato appello AAAARGH!
Ho preso quello del 13/04/05

* POST CANCELLATO *

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

Ho un dubbio atroce, a me risulta che il vertice ottimo per via grafica sia (0,-2)
ma non dovrebbe essere degenere dato che x2 non e' libera in segno?

Merda! Ho risolto il problema di massimo, ma era di minimo...

Se faccio un errore del genere all'esame mi ammazzo!
Ora correggo tutto!

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

Niente come non detto mi sono accorto di una cappellata, sto perdendo colpi
Non puo' essere 0,-2 perche' ho il vincolo x2 > 0

Originally posted by DarkStalker
Ho un dubbio atroce, a me risulta che il vertice ottimo per via grafica sia (0,-2)
ma non dovrebbe essere degenere dato che x2 non e' libera in segno?

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

Me ne er0 accorto
Dovrebbe ora essere (-1,0)

L'es 2 è bastardo, spero di non averlo cannato del tutto!
Corretto!

2.1.

z = -1
x1 = -1
x2 = 0
x3 = 16
x4 = 4
x5 = 0

2.2

-2 <= b3 <= 30

2.3

min z = x1 + - x1- + x2

-x1+ + x1- + 3x2 + x3 = 15
2x1+ - 2x1- - x2 + x4 = 2
-2x1+ + 2x1- - x2 + x5 = 2
xi >= 0 per ogni i

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

Originally posted by DarkStalker
Me ne er0 accorto
Dovrebbe ora essere (-1,0)

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

Anche il 3 non mi convince molto...

max 15y1 + 2y2 + 2y3

-y1 + 2y2 - 2y3 = 1
3y1 - y2 - y3 >= 1
y1, y2, y3 >= 0

Y* = (0, 0, -1/2, -1/2)

Il sistema risolto è:

-2y3 = 1
-y3 - y4 = 1

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

ok per ora viene cosi' anche a me il 2

Questa 3y1 - y2 - y3 >= 2 non dovrebbe essere invece <= 1 (stai passando da min a max e il coeff di costo di x2 e' 1)?

Originally posted by DarkStalker
Questa 3y1 - y2 - y3 >= 2 non dovrebbe essere invece <= 1 (stai passando da min a max e il coeff di costo di x2 e' 1)?

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

Il taglio di Gomory invece mi sembra giusto:

z = 10

x = (4, 6, 4, 0, 0)

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

Originally posted by ripe
E' maggiore o uguale a 1... hai ragione, che disastro!

(maggiore o uguale, perchè x2 >= 0)

questo mi sembra tosto come tema.. adesso inizio anche io...

Nell'esercizio 5 gli archi riportati a destra sono (1,2) (1,3) (1,4) (2,5) (5,6) (5,7) ?

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

Originally posted by DarkStalker
Sul mio libro dice:

primale min xj >=0 -> duale max utAj <= cj
ovvero devi invertire il segno di diseguaglianza
Da max a min avresti ragione tu e devi invertire i voncoli di segno invece
Ste regole del menga nn me le ricordo mai

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

Nel 6 il flusso massimo DOVREBBE essere 18... dico dovrebbe perchè mi sono perso per strada qualche conto!

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

Argh raga io stacco per un po' mi sta girando la testa

Si, anche io mi sa che per oggi passo! Sono distrutto!

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

:-) io ero già crollato :-) se mi viene voglia faccio qualcosa dopo cena... ma nn credo.
Domani mattina si riparte ;-)
sinceramente i miei dubbi sono
1) flusso massimo inviato a costo minimo.. come si farà?
2) non sono riuscito ancora a fare un esercizio sul taglio di gomory intero
3) gli altri tipi di rilassamento
4) ovviamente l'esercizio numero uno maledetto.

Buonasera.
nell'esercizio 1 x3 non è 14?

nei tagli di gomory invece mi viene x3=1. avrò sbagliato i conti (capita spesso con fro)

nel 5 io ho usato dijkstra (non so però se è giusto)
e mi viene: ops... avevo preso un 15 per un 5... quindi mi viene uguale a quello che c'è già

su quello del flusso massimo ho tagliato i nodi 1,2,3,4 ed il flusso mi viene 20.

Sulla questione del costo mi risulta che sia sufficiente verificare che non ci siano cicli con costo negativo. Chiaramente non ne sono sicuro.

Scusate ma l'errore di calcolo lo considera come esercizio sbagliato o da qualche punticino?

Originally posted by Tbbaaa
Buonasera.
nell'esercizio 1 x3 non è 14?

nei tagli di gomory invece mi viene x3=1. avrò sbagliato i conti (capita spesso con fro)

ESERCIZIO 3

Originally posted by ripe
E' maggiore o uguale a 1... hai ragione, che disastro!

(maggiore o uguale, perchè x2 >= 0)

Avrò scritto qualche cazzata, sicuramente... ero fuso!

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

Originally posted by Tbbaaa

Sulla questione del costo mi risulta che sia sufficiente verificare che non ci siano cicli con costo negativo. Chiaramente non ne sono sicuro.

Ok adesso inizio anche io partendo dai tagli di gomory che ho lasciato in sospeso ieri (cheppalle nn ho voglia di passare la giornata a fare esercizi)

Non ho capito questo passaggio : "Gli eventuali tagli vanno
trovati a partire dal primo vincolo al quale corrisponda una variabile frazionaria in base"
Se vedete il pdf ho la prima var in base x2 e poi x1, quindi quale scelgo?

Il primo vincolo con variabile frazionaria è quello con termine noto 32/5, quindi dovresti partire da quello... a meno che non abbia capito male io!

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

ok denghiu

Bene i tagli di gomory mi vengono z = 10 x1=4 x2=6 x3=1

Sisi vengono anche a me x1=4, x2=6 e x3=1. Il taglio introdotto è x2<=6.

Speriamo che quello di domani sia un appello "passabile". Adesso corro a vedermi la history di tutti gli appelli di febbraio

__________________
Computer Science: solving today's problems tomorrow.

febbraio scorso era molto tranquillo ;-) ripeto, speriamo non sia un caso...

Voi che esempi seguite per effettuare i tagli? Per esempio seguendo l'eserciziario ho fatto cosi': se date un occhiata al pdf ho preso il vincolo con 32/5 come termine noto cioe':
0 | 1 | 2/5 | .1/5 | 32/5
calcolando le parti frazionarie avrei
0x1 + 0x2 + 2/5x3 + 4/5x4 + x5 = 2/5

Oddio quello di febbraio del 2004/05 era un massacro