 | |
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 |
[esame] 27 Luglio
Clicca QUI per vedere il messaggio nel forum |
| luna |
| C'è qualcuno che sta preparando l'esame di venerdì?io sono in crisi totale :( |
| luna |
| :( ho seri problemi sul taglio di gomory..non capisco neanche l'esercizio che si trova negli appunti di Polsy..qualcuno puo' aiutarmi???si trova a pagina 79 del pdf!!!!:please: |
| DarkStalker |
Ciao io e' la terza volta che lo provo sto esame :(, stanotte faccio degli esercizi
sui tdg e poi li posto |
| luna |
| dai se vuoi ci mettiamo d'accordo e ci aiutiamo :) io ora sto guardando sul libro gli esempi che ci sono sul taglio di gomory,spero di capirci qualcosa!con gli altri es come sei messo?io quelli della programmazione lineare abbastanza bene..gli altri devo ancora approfondirli! |
| DarkStalker |
Beh io ho difficolta' soprattutto per quanto riguarda i primi esercizi dei vari temi
(quelli che generalmente richiedono la stesura di un modello matematico)
per quanto riguarda il resto, a parte eventuali errori di calcolo, li so fare anche se quando introduce delle sottili variazioni vado in panico (es leggi i rilassamenti nei problemi di zaino). |
| luna |
| io purtroppo ho avuto poco tempo per prepararlo quindi son messa piuttosto male sugli esercizi dei grafi..tra l'altro ho visto che l'ultimo tema di giugno non era per niente facile :shock: |
| DarkStalker |
Ti posto l'esercizio incompleto solo per farti vedere il procedimento
occhio che devo aver sbagliato i calcoli durante la fase del simplesso
quindi prendilo con le pinze. |
| luna |
| scusa se rispondo solo ora ma ero a lavoro...una cosa non mi è chiara..magari è anche stupida..ma cosa hai fatto dopo aver trascritto nel tableu i valori dei vincoli?come sei arrivato al secondo schema?perchè ho una confusione in testa mostruosa..ad esempio ma il duale e il simplesso duale son la stessa cosa?:oops: :( |
| DarkStalker |
Ciao, cosa intendi per secondo schema? Intendi il secondo tableau? Beh ho semplicemente applicato l'algoritmo del simplesso.
Poi vedendo che le 2 soluzioni sono frazionarie decido di generare un taglio
selezionando quella col rapporto frazionario maggiore.
"Duale" e "simplesso duale" indicano 2 cose legate tra loro ma differenti.
Per "Duale" si intende il problema, "simplesso duale" e' una variante del simplesso "liscio" (o primale) utilizzato per risolvere problemi duali. |
| luna |
Originally posted by DarkStalker
Ciao, cosa intendi per secondo schema? Intendi il secondo tableau? Beh ho semplicemente applicato l'algoritmo del simplesso.
Per "Duale" si intende il problema, "simplesso duale" e' una variante del simplesso "liscio" (o primale) utilizzato per risolvere problemi duali.
si intendevo il secondo tableu :)
ma il simplesso duale si applica nel caso in cui ci sia un termine b negativo, giusto?:look: |
| luna |
mi è venuto un dubbio sull'algoritmo del simplesso :look: ma per scegliere chi deve "uscire" e chi deve "entrare" che formuletta devo utilizzare?sto impazzendo :ueee:
Grazie mille comunque :) |
| DarkStalker |
Ordunque, io faccio cosi', scelgo la colonna con la variabile col valore piu' "alto" (se e' un prob di max) o piu' "basso" (se e' un prob di min).
Per scegliere la riga devi fare il rapporto tra i l termine noto e la variabile della riga corrispondente e scegli la riga in cui hai il valore positivo piu' basso |
| luna |
ma la variabile col valore piu' alto intendi il termine aij giusto?nell'esempio che hai postato te, nel primo tableu te hai scelto di far entrare x1 perchè come valori ha 2 e -1 giusto?ma anche x2 ha gli stessi valori..perchè hai scelto x1?per la regola lessicografica?:D
comunque, sempre nell'esempio, entra x1 ed esce x3 perchè nella riga corrispondente avevi x3 con 1 e x4 con 0?e il valore 0 non si deve considerare giusto?quindi rimane x3 ed è lui che esce!:look:
scusami,ti sto prosciugando! |
| DarkStalker |
Originally posted by luna
ma la variabile col valore piu' alto intendi il termine aij giusto?nell'esempio che hai postato te, nel primo tableu te hai scelto di far entrare x1 perchè come valori ha 2 e -1 giusto?ma anche x2 ha gli stessi valori..perchè hai scelto x1?per la regola lessicografica?:D
Si diciamo che l'hp scelto in base a tale regola ma devi considerare il coefficiente di costo ridotto non gli elementi della matrice
Ho scelto
comunque, sempre nell'esempio, entra x1 ed esce x3 perchè nella riga corrispondente avevi x3 con 1 e x4 con 0?e il valore 0 non si deve considerare giusto?quindi rimane x3 ed è lui che esce!:look:
scusami,ti sto prosciugando!
Esce x3 perche' facendo i rapporti con i termini noti e gli elementi della colonna di x1 ho
6/2 = 3
2 / -1 = -2 <- e' negativo quindi non va bene
Nota che se avessi avuto 2/1 = 2 avrei fatto uscire x4 perche' appunto 2 < 3
Qui se vuoi c'e' un po' di roba
http://ulisse.polito.it/matdid/3ing...download/eserc/ |
| luna |
grazie mille per il link!:) lo sto guardando!:)
quindi ricapitolando per capire quale variabile deve entrare in base:
- guardo il coefficiente di costo, quelli negativi nel caso di un problema di minimo, quelli positivi nel problema di massimo
- dagli elementi di queste colonne guardo quello col valore più alto nel caso del massimo e quello col valore più piccolo nel caso del minimo :look: e sarà questa variabile la candidata ad entrare!
e poi scelgo chi esce dal procedimento che mi hai spiegato prima! |
| DarkStalker |
| Si in genere uso questo metodo |
| luna |
ok,grazie :) per i tagli di gomory invece, sempre nell'esercizio che hai postato..come primo vincolo hai scelto R1..ma poi il passaggio successivo,dove hai aggiunto x5 da dove è saltato fuori?non capisco il procedimento di questi tagli :(
forse c'è un errore quando hai scritto il primo vincolo..dopo il >= mi sembra che ci sia scritto 10/5 quando credo ci vada 14/3 :look: ma magari sbaglio!
il primo taglio dovrebbe quindi essere 2/3 x3+1/3 x4 - x5 >= 2/3
o no?:) |
| DarkStalker |
C'e' scritto 10/3, si in effetti ho commesso un errore adesso correggo.
La x5 e' la variabile di scarto che deve essere sottratta per portare la diseguaglianza a un'uguaglianza esattamente come si farebbe per un qualsiasi vincolo |
| DarkStalker |
| Il primo taglio mi viene x1 < 4 |
| luna |
come primo vincolo senza rifare i conti dei tableu mi viene x1<=4 :)
per la x5 io guardando l'esempio dagli appunti di Polsy avevo capito che la variabile di scarto si poteva aggiungere quando al tableu aggiungevo il taglio..o mi sbaglio?
e poi un'ultima cosa..quando ho trovato quale variabile entra e quale esce bisogna fare i vari conti tra R0,R1 ed R2 (ad esempio)..ma c'è una qualche regola a riguardo?
Grazie mille :) |
| DarkStalker |
Allora, le variabili di scarto e surplus vanno aggiunte a tutti i vincoli di un problema (sia quelli esistenti che quelli aggiunti coi tagli), per sapere come fare guarda la parte relativa alle trasformazioni dalla forma standard a quella canonica (o viceversa? boh)
Per quando riguarda i calcoli da fare sulle varie righe funziona cosi'.
Dopo che hai trovato il pivot devi dividere tutta la riga per tale vaore del pivot in modo tale che il pivot diventi 1.
Per uqndo riguarda le righe sopra e/o sotto la riga del pivot, devi fare in modo
che i valori nella colonna del pivot diventino 0 (pivot escluso) altrimenti nn potrai considerarla una variabile in base |
| luna |
Originally posted by DarkStalker
Per uqndo riguarda le righe sopra e/o sotto la riga del pivot, devi fare in modo
che i valori nella colonna del pivot diventino 0 (pivot escluso) altrimenti nn potrai considerarla una variabile in base
e qui vado a caso basta che diventino zero?
edit: sorry ho sbagliato io!:D
però proprio in quel passaggio dal 2° al 3° tableu nella seconda riga te hai usato r1+1/2 R2 (anche se credo che qui sia 1/3 o sbaglio?) però si poteva anche usare R1 al posto di R2 e in quella riga di x2 dove c'è necessità dello zero avremmo avuto lo stesso risultato..ma nelle altre x1,x3 e x4 no...è normale?:D |
| DarkStalker |
Occhi che la mia grafia fa schifo quindi quello che tu leggi 3 potrebbe essere 5.
Cmq si diciamo che vai a "casaccio" ovvero devi moltiplicare opportunamente la riga col pivot in modo tale che sottraendola dalle altre l'unico elemento a 1 nella colonna del pivot e' il pivot stesso e tutti gli altri stanno a zero
esempio semplice
ho questa colonna
5 R1
1 R2 <- questa e' la riga col pivot
3 R3
per mandare a zero il 5 dovro' fare R1 - 5R2
per mandare a zero il 3 dovro fare R3 - 3R2
Cioe' sto dicendo che devo sottrarre tutta la riga 1 per la riga 2 moltiplicata per 5
e sottrarre la riga 3 per la riga 2 moltiplicata per 3 |
| luna |
| ok!:D ho risolto i dubbi :D |
| luna |
| a te come è andato?io sicuramente non l'ho passato...a un certo punto mi si fondeva il cervello! |
| DarkStalker |
Boh il prof ha detto che dovrei essere intorno al 23-24 cmq incrocio le dita
nn lo sopporto piu' sto esame,ormai vedo grafi dappertutto |
| luna |
ma ha corretto subito dopo?ma te dov'eri seduto?:D
ma te dove hai studiato?libri/dispense/appunti?
io ho due libricini e gli appunti presi da Polsy però sinceramente moltissime cose non le capisco.. |
| DarkStalker |
Ero il tipo in prima fila con la camicia bianca.
Sono uscito praticamente per ultimo.
Non ha proprio corretto subito, gli ho chiesto un parare rapido sull'andazzo del mio compito, infatti per la valutazione finale sto aspettando.
Ordunque, io ho praticamente tutti 3 i libri.
Quello arancione e' un mezzo cesso e praticamente nn l'ho mai letto, se non per quanto riguarda la teoria dei grafi.
Io ho comincato gia' a gennaio con gli appunti di polsy per capire un po' il simplesso
e qlche altra cosa ma tieni presente che alcuni dettagli vengono tralasciati
(es i rilassamenti nel BnB e le varie tecniche di attraversamento), che puoi trovare nelle slide usate al lezione (Fondamenti di ricerca operativa).
L'eserciziario e' utilissimo se vuoi imparare le cose al volo pero' tieni presente
che nn copre tutti i casi possibili che potresti incontrare in un esame, pero' nn e' detto che tu debba farlo alla perfezione per passarlo ;).
Cmq nn ti preoccupare rileggiti attentamente gli appunti di Polsy,
io le prime volte che ho aperto il libro non capivo nemmeno l'indice :-D |
| luna |
:D beh tieni conto che io l'ho preparato in due settimane lavorando 8 ore e alla fine son riuscita su per giù a fare 3 esercizi su 6 :D magari per settembre capirò gli altri!:D
io di libri ho un fondamenti di ricerca operativa di Pitagora Editrice Bologna che presumo siano le slide e un altro "Lezioni di ricerca operativa" che forse dà le spiegazioni :look: mi confermi?quindi mi manca l'eserciziario? |
| DarkStalker |
| Si, quello ha un bel po' di esercizi soprattutto svolti passo passo |
| luna |
| ah cavoli..mi puoi dire il nome di questo eserciziario?dove lo trovo?perchè a questo punto mi conviene comprarlo! |
| DarkStalker |
"120 Esercizi di ricerca operativa" Mauro Dell'amico Pitagora Editrice Bologna.
Occhio che io l'ho trovato alla clup in via Ampere 20 |
|
|
|
|
