.dsy:it. (http://www.dsy.it/forum/)
- Ricerca operativa (http://www.dsy.it/forum/forumdisplay.php?forumid=228)
-- [Fondamenti di Ricerca Operativa] Diario del corso 04/05 (http://www.dsy.it/forum/showthread.php?threadid=13649)

[Diario del corso] Fondamenti di Ricerca Operativa

"Fondamenti di Ricerca Operativa" è un corso complementare per le lauree triennali.
Seguono alcune informazioni generali sul corso:

Docente: M. Trubian

Orari delle lezioni:
mercoledì 14.30- 16.30
giovedì 14.15- 16.15

in aula V6 (via Venezian).

Orario di ricevimento del docente:
Lunedì dalle ore 15.00 alle ore 17.00

Sito del corso:
Sul sito del corso potete trovare avvisi, il programma del corso, vecchi temi di esame e altre utili informazioni.

Materiale didattico: Il testo principale è:
M. Fischetti: "Lezioni di Ricerca Operativa", Edizioni Libreria Progetto Padova, 1995.

Altri testi utili sono
- R. Baldacci, M. Dell'Amico: Fondamenti di Ricerca Operativa, Pitagora Editrice Bologna, 2002. (si tratta di una raccolta dei lucidi utilizzati a lezione)

e

- M. Dell’Amico: 120 esercizi di ricerca operativa, Pitagora Editrice Bologna, 1996.

Per ulteriori libri di testo consigliati, consultare il sito del corso.

Modalità d'esame: L'esame prevede uno scritto per tutti. E' poi previsto un orale obbligatorio per voti appena sufficienti (17-18) e molti alti (più di 27). Se uno studente prende nello scritto un voto maggiore di 27, per verbalizzarlo deve perciò passare attraverso l'orale; altrimenti, verbalizzerà un 27.
L'orale può comunque essere sostenuto da tutti coloro che lo desiderino. L'orale parte dalla discussione dello scritto.

Prerequisiti: Algebra lineare (matrici etc.).


La frequenza non è obbligatoria.
A metà corso, molto probabilmente, verrà tenuto un compitino.

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

Lezione dl 29-09-04

Argomenti trattati nella lezione di oggi:

- Cosa è la Ricerca Operativa? Sue origini
- Esempi di campi di applicazione della RO
- Programmazione matematica: definizione, problemi di minimo, problemi impossibili, problemi illimitati
- Convessità: combinazione convessa, insieme convesso, funzione convessa (concava); minimo locale, minimo globale; proprietà di funzioni convesse.

---

Link a siti relativi alla RO:
www.informs.org
www.airo.org

---

Avviso: La lezione di oggi, 30 Settembre, è sospesa. Verrà poi recuperata in seguito.
Appuntamento a mercoledì prossimo!

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

Off-Topic:
ma il libro dove si può recuperare, io non lo trovo da nessuna parte ne in biblioteca, ne in libreria, ne di qua ne di la... qualcuno mi informa?

__________________
http://www.twitter.com/0m4r

Originally posted by 0m4r

Off-Topic:
ma il libro dove si può recuperare, io non lo trovo da nessuna parte ne in biblioteca, ne in libreria, ne di qua ne di la... qualcuno mi informa?

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

lo stanno ordinando alla clued...sono andato subito dopo lezione...
Il tipo pensava fosse un corso del secondo semestre...
Ce l'hanno anche alla clup di ingegneria, quella nella via parallela alla fermata di piola...

__________________
"Ognuno di noi possiede dentro di sè la capacità di forgiare il proprio destino ed ha un'eguale possibilità di forgiare il destino degli altri e del mondo. Nella vastità dell'oceano forse una goccia è maggiore di un'altra???"

"E così stava suonando la grande arpa, piangendo tutte le cose che se ne andavano e che sarebbero forse tornate ma irrimediabilmente diverse. E attraverso la musica il suo dolore e la sua paura si mutavano in armonia."

Lezione del 06-10-04

Argomenti trattati nella lezione di oggi:

- Spazio delle soluzioni ammissibili: introdurre vincoli sotto forma di disequazioni (o equazioni)
- Esempi di problemi di programmazione lineare:
* Produzione di merci
* Miscelazione ottimale
* Turnazione del personale
* Il problema dei trasporti

Avviso: La lezione del giovedi' viene anticipata alle ore 14.00 a partire dalla lezione del 7 Ottobre.

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

Lezione del 07-10-04

Argomenti trattati nella lezione di oggi:

- Problema di assegnamento lineare
- Cenni al rilassamento dei vincoli
- Modelli matematici: condizioni e vincoli logici
- Esempi di problemi di programmazione matematica:
* Localizzazione di servizi
* Il problema Knapsack
* Bin Packing (caricamento)
* Fixed charge
* Scheduling su singolo processore

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

Lezione del 13-10-04

Argomenti trattati nella lezione di oggi:

- Programmazione lineare continua (plc)
- Forma standard di un problema; trasformazione dalla forma generale alla forma standard
- Soluzione grafica di problemi di plc
- Geometria della programmazione lineare

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

Lezione del 14-10-04

Argomenti trattati nella lezione di oggi:

- Soluzione algebrica di un problema di plc
- vincoli attivi, rappresentazione in forma compatta (matriciale) del problema, base, variabili in base e fuori base, soluzione di base, vertice
- Metodo del simplesso: algoritmo (versione base), test di ottimalità
- Teorema + dimostrazione: una soluzione di base di un problema di plc in forma di minimo è ottima se i costi ridotti sono non negativi

Avviso:: La lezione del giovedì si terrà in orario 14.15-16.15 a partire da giovedì 21 ottobre.

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

Bulma grazie per il tuo lavoro di aggiornamento!
avresti per caso un link con delle dispense per poter studiare???
Inoltre non si trovano copie dei compitini degli anni passati???
diciamo così tanto per fare un pò di pratica in vista del prossimo compitino....

__________________
Le frasi mitiche...
::mm...ma nel compito mette anche le domande??::
::.. compilare compila... è tutto corretto, il fatto è che non fa quello che dico io.. cosa potrebbe essere?::
::Il fatto è che io le cose le so...poi dopo quando sono all'interrogazione non mi vengono...::

Che io sappia, non ci sono dispense per questo corso (cmq non tra i testi consigliati dal docente). Dovresti acquistare il libro di testo che trovi indicato nel primo post del thread.

Inoltre, se vai sul sito del corso, troverai i link agli anni accademici passati. Nella pagina dell'anno 2003/2004 ci sono alcuni esercizi da svolgere e i temi d'esame.

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

Lezione del 20-10-04

Argomenti trattati nella lezione di oggi:

- Svolgimento di alcuni esercizi
- Cambiamento di base
- Algoritmo del simplesso (versione matriciale)
- Introduzione alla forma tableau del simplesso

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

Lezione del 21-10-04

Argomenti trattati nella lezione di oggi:

- Cambio di base e tableau (con esercizio)
- Determinazione di una base iniziale:
* Metodo del big M
* Metodo delle due fasi

Avviso:
Il primo compitino di Fondamenti di Ricerca Operativa si terrà il giorno 17 novembre. Gli argomenti su cui verterà sono quelli trattati fino a pag. 72 del libro di Fischetti e fino a pag. 40 dei lucidi.

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

Lezione del 27-10-04

Argomenti trattati nella lezione di oggi:

- Esempi sul metodo delle due fasi
- Convergenza e degenerazioni; regola di Bland
- Dualità; lemma di Farkas (+ dim.)
- Problema duale; esempio

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

Lezione del 28-10-04

Argomenti trattati nella lezione di oggi:

- Il problema del trasporto: esempio per illustrare il concetto di problema primale-duale
- Il problema duale: regole generali e esempio
- Teorema (+ dim.): il duale del duale è il primale
- Teorema di dualità forte e teorema di dualità debole (+ dim.); corollario
- Esempio per illustrare il caso di soluzione ottima multipla


Potete trovare informazioni relative al PRIMO COMPITINO a questo link.

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

Lezione del 03-11-2004

Argomenti trattati nella lezione di oggi:

- Condizioni di ortogonalità
- Scarti complementari
- Interpretazione delle variabili duali come prezzi ombra (interpretazione economica)


Aggiornamenti relativi al compitino sono disponibili qui.

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

Lezione del 04-11-2004

Argomenti trattati nella lezione di oggi:

- Analisi di sensitività: punto di vista geometrico e punto di vista algebrico
- Algoritmo del simplesso (primale e duale) e ottimalità
- Inserimento di nuovi vincoli


Nelle prossime due lezioni il docente presenterà esercizi in preparazione al compitino.

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

Lezione del 10-11-04

Oggi sono stati svolti esercizi in preparazione al primo compitino. In particolare, abbiamo visto esercizi relativi all'interpretazione geometrica e quella algebrica dell'analisi di sensitività.

Nota relativa al primo compitino: la parte di modellazione non sarà argomento del compito.

Avviso: La lezione di domani, 11 novembre, è sospesa per protesta contro il DDL Moratti. La lezione verrà recuperata martedì 16 novembre, dalle ore 13.30 in poi, in aula V7; durante tale lezione verranno affrontati altri esericizi in preparazione al compitino.

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

Ragazzi ma non ho capito cosa non metterà nel primo compitino...i modelli?? cioè??
quali sono??i primi esercizi che avevamo fattoi?dove bisognava scrivere un problema in forma algebrica?

Esatto. Dato un problema in linguaggio naturale, individuare le variabili decisionali, imporre i vincoli, scrivere la funzione obiettivo etc.

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

che bello.... :-)

Lezione del 18-11-04

Argomenti trattati nella lezione di oggi:

- Programmazione lineare intera: definizione
- Rilassamento continuo
- Chiusura convessa, convex hull
- Unimodularità e totale unimodularità
- Algoritmo cutting plane; come generare piani di taglio; tagli di Gomory

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

Lezione del 24-11-04

Argomenti trattati nella lezione di oggi:

- Branch and Bound; albero decisionale; Lower e Upper bound
- Rilassamento: definizione generale; rilassamento per eliminazione di vincoli; rilassamento continuo; rilassamento lagrangiano; rilassamento surrogato

Avviso: il docente ha fatto presente che chi volesse recuperare la parte relativa al simplesso (esercizi 2 e 3 del primo compitino) potrà svolgere esercizi aggiuntivi (su questo argomento) nel corso del secondo compitino.

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

Lezione del 25-11-04

Argomenti trattati nella lezione di oggi:

- Riepilogo di quanto visto nella scorsa lezione
- Esempio del knapsack bidimensionale
- Strategie di esplorazione: depth-first, lowest-(highest-) first
- Branch and bound standard per problemi di PLI

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

Lezione del 01-12-04

Avviso: La lezione dell'1 Dicembre è sospesa a causa del concomitante sciopero dei mezzi. Potete trovare l'avviso sul sito del corso

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

Lezione del 02-11-04

Argomenti trattati nella lezione di oggi:

- Branch and Bound per problemi Knapsack
- Esercizi di modellazione e su branch and bound

La prossima lezione di terrà giovedì 9 Novembre.

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

Lezione del 09-12-04

Argomenti trattati nella lezione di oggi:

- Esercizi su modellazione, Branch and Bound, Tagli di Gomory

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

Lezione del 15-12-04

Argomenti trattati nella lezione di oggi:

- Grafi: definizioni e notazione:
grafi non orientati, grafi orientati, grafi pesati, taglio di un grafo, cammini, circuiti e cicli, grafi parziali e sottografi, connessioni e componenti connesse, grafi aciclici, alberi
- Rappresentazione di grafi: matrice di adiacenza, matrice di incidenza
- Alberi di costo minimo: formulazione matematica

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

qualcuno potrebbe gentilemnte postare gli esercizi fatti in classe in queste ultime settimane?purtroppo non ho potuto seguire la lezione di giovedì 9 ne quella di oggi ne quella che terrà domani...qualcuno potrebebe farmi questa enorme gentilezza??mi è spiaciuto perderle come lezioni ma prorpio non ho potuto,,,mi fareste un enorme favore

Lezione del 16-12-04

Argomenti trattati nella lezione di oggi:

- Teorema (sul lato di costo minimo in un taglio) e dimostrazione
- Algoritmo di Prim-Dijkstra: prima versione, versione migliorata con etichette; formato tabellare
- Algoritmo di Kruskal: prima versione, versione migliorata con etichetta
- Cammini minimi: definizione del problema, formulazione matematica

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

proprio nessuno riesce ad aiutarmi??
mi fareste un enorme favore

sigh sigh,.....vabbè grazie lo stesso...

Lezione del 22-12-04

Argomenti trattati nella lezione di oggi:

- Algoritmo di Dijkstra: teorema su cui l'algoritmo è basato, versione con complessità O(nm) e versione O(n^2)
- Cammini minimi tra tutte le coppie di vertici: algoritmo di Floyd-Warshall
- Variante dell'algoritmo di Dijkstra per grafi con archi con costi negativi (NON RICHIESTA PER IL COMPITINO)
- Flusso massimo in un grafo: formulazione matematica, s-t tagli, capacità di un s-t taglio, flusso attraverso un taglio, Teorema del max flow/min cut, rete incrementale

Avviso: Il secondo compitino si terrà il giorno 19 gennaio alle ore 14.30 in aula G21 (via Golgi).

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

ciao ragazzi..ma alla fine nel secondo compitino ci sarà anche il flusso minimo? prima delle vacanze..ultima lezione..aveva detto che lo avrebbe fatto m,a non sarebbe stato presente nel compito...che dite?

Lezione del 12-01-05

Argomenti trattati nella lezione di oggi:

- archi non saturi, non scarichi, cammino aumentante
- Teorema 3 (flusso ottimo sse non esiste cammino aumentante) + dim.
- Algoritmo di Ford-Fulkerson (prima versione), complessità
- Flusso a costo minimo: descrizione del problema, formulazione matematica, esempi di problemi formulabili come problemi di flusso a costo minimo; rete incrementale, circuito di costo negativo, esercizio

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

Lezione del 13-01-05

Durante la lezione di oggi sono stati svolti esercizi (soprattutto di modellazione, ma anche uno sui flussi di costo minimo).

Questa era l'ultima lezione del corso, tuttavia il docente ha ancora un argomento in sospeso (complessità) che farà parte del programma da portare per l'orale.
Sarà allora tenuta una lezione supplementare la prossima settimana (giovedì o venerdì) per illustrare questo argomento. Il giorno, l'ora e il luogo della lezione saranno comunicati dal docente sul sito del corso.



Per proporre esercizi in preparazione al secondo compitino e esporre i vostri dubbi, postate qui.

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

Avviso ultima lezione

Avviso: l'ultima lezione di Fondamenti di Ricerca Operativa (cenni di Complessità Computazionale) si svolgerà in aula 304 di via Celoria 20, dalle ore 14,30 alle ore 16,30 di venerdì 21 gennaio '05.

[dal sito del corso]

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

Lezione del 21-01-05

Argomenti trattati nella lezione di oggi:

- Problema, istanza, dimensione di un'istanza; codifica ragionevole; ordine di grandezze
- Complessità in tempo e spazio; modello di calcolo, criterio di costo (uniforme e logaritmico); analisi worst-case
- Algoritmo polinomiale, esponenziale, efficiente; classificazione dei problemi; classe P
- Modello di calcolo non deterministico; classe NP, certificato polinomiale
- P sottoinsieme di NP
- Cenni alla classe Co-NP
- Cenni alla riduzione polinomiale; problemi NP-completi.


Vi ricordo che le slide relative a questa lezione (l'ultima del corso) saranno pubblicate sul sito del corso.

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

Ciao a tutti, vorrei sapere quando è possibile verbalizzare il voto di RO, e se è necessario iscriversi via sifa, visto il nuovo procedimento di verbalizzazione elettronica???

Grazie in anticipo.

__________________
"The POP3 server service depends on the SMTP server service, which failed to start because of the following error: The operation completed successfully." (Windows NT Server v3.51)

mi autorispondo visto che è appena uscito l'avviso sulle modalità di verbalizzazione:

http://homes.dsi.unimi.it/~trubian/aa200405.htm

__________________
"The POP3 server service depends on the SMTP server service, which failed to start because of the following error: The operation completed successfully." (Windows NT Server v3.51)

Un'informazione: sono iscritto alla specialistica, ma tra gli esami a cui é possibile iscriversi tramite SIFA ro non c'e'. Come si fa?

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

Anche io sono iscritta alla specialistica ma non ho avuto problemi. Considera però che le iscrizioni chiudono una settimana prima dell'appello, quindi l'ultimo giorno per iscriversi era il 9 febbraio... probabilmente è per questo che l'esame non compare sul sifa.

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

Ok, grazie! Avevo pensato che potese essere per quello, ma mi era rimasto qualche dubbio perche' mi é capitato con un altro esame di questo semestre di potermi iscrivere 2 giorni prma della data dell'appello.

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

Qualcuno ha sostenuto l'esame orale di Ricerca Operativa e ha qualche consiglio da dare ?

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

Gli eventuali orali e la verbalizzazione del voto dell'appello (e dei compitini) di FRO si svolgeranno in aula 5 del DSI a partire dalle ore 9,30 di martedì 22 febbraio
non credo abbiano fatto orali....

Beh, mi riferivo a chi ha fatto appelli precedenti di Ricerca Operativa

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

Io li ho fatti e ti consiglio di non studiare da sola....magari ci possiamo trovare in uni...o cmq ti conviene risolvere gli esercizi e farli controllare al docente, come ho fatto io....

__________________
Spaghetti!!!

Originally posted by Nonsaprei
Io li ho fatti e ti consiglio di non studiare da sola....magari ci possiamo trovare in uni...o cmq ti conviene risolvere gli esercizi e farli controllare al docente, come ho fatto io....

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

Dunque, ieri ho sostenuto l'orale per questo corso.
Scrivo le domande che mi ricordo, magari risulteranno utili per chi in futuro vorrà sostenere l'esame orale

- La dualità: dualità forte, debole, lemma di Farkas (con dimostrazione)
- Il modello dei trasporti e l'interpretazione del suo duale
- Cos'è un prezzo ombra; analisi di sensitività: variazione del termine noto
- I problemi NP-Completi, certificato polinomiale, riduzione in tempo polinomiale

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

appello 27 luglio

Scusate,
qualcuno potrebbe indicarmi dove posso trovare esercizi d'esame svolti ?

C'e' qualcuno che si e' iscritto per l'appello del 27 luglio e vuole fare un po' di esercizi insieme ?

Grazie.

Buona giornata.