2. Docenti
  3. Didattica

RICERCA OPERATIVA

Francesco CARRABS RICERCA OPERATIVA

0512100012
DIPARTIMENTO DI INFORMATICA
CORSO DI LAUREA
INFORMATICA
2022/2023

OBBLIGATORIO
ANNO CORSO 3
ANNO ORDINAMENTO 2017
SECONDO SEMESTRE
CFUOREATTIVITÀ
432LEZIONE
216ESERCITAZIONE


FRANCESCO CARRABS T Curriculum
Obiettivi
IL CORSO DI RICERCA OPERATIVA SI PROPONE DI FORNIRE LE CONOSCENZE PER LA RISOLUZIONE DI PROBLEMI DI OTTIMIZZAZIONE FORMULATI TRAMITE MODELLI MATEMATICI DI PROGRAMMAZIONE LINEARE CONTINUA (PL).

CONOSCENZA E CAPACITÀ DI COMPRENSIONE
ALLA FINE DEL CORSO LO STUDENTE CONOSCERÀ:
- GLI STRUMENTI NECESSARI ALLA FORMULAZIONE DI PROBLEMI REALI TRAMITE L’UTILIZZO DI MODELLI MATEMATICI DI PL;
- IL METODO DI RISOLUZIONE GRAFICA DI PROBLEMI DI PL IN DUE VARIABILI;
- IL FUNZIONAMENTO DEL METODO DEL SIMPLESSO PER LA RISOLUZIONE DEI PROBLEMI DI PL;
- L'ANALISI DI SENSITIVITÀ DELLE SOLUZIONI OTTIME INDIVIDUATE;
- I MODELLI MATEMATICI E GLI ALGORITMI RISOLUTIVI PER I PRINCIPALI PROBLEMI DI PL DEFINITI SU GRAFI.

CAPACITÀ DI APPLICARE CONOSCENZE E COMPRENSIONE
ALLA FINE DEL CORSO LO STUDENTE SARÀ IN GRADO DI:
- FORMULARE (QUANDO POSSIBILE) PROBLEMI DI OTTIMIZZAZIONE TRAMITE MODELLI MATEMATICI DI PL;
- RISOLVERE GRAFICAMENTE PROBLEMI DI PL IN DUE VARIABILI;
- APPLICARE IL METODO DEL SIMPLESSO PER LA RISOLUZIONE DI PROBLEMI DI PL;
- EFFETTUARE L'ANALISI DELLA SENSITIVITÀ DELLE SOLUZIONI OTTIME DEI PROBLEMI RISOLTI;
- UTILIZZARE IL SOFTWARE EXCEL PER INDIVIDUARE LA SOLUZIONE OTTIMA DEI PROBLEMI DI PL E PER EFFETTUARNE L'ANALISI DELLA SENSITIVITÀ DI QUESTA SOLUZIONE;
- MODELLARE I PROBLEMI DI PL SU GRAFI E RISOLVERLI TRAMITE GLI ALGORITMI PRESENTATI AL CORSO.
Prerequisiti
L’INSEGNAMENTO PRESUPPONE LA CONOSCENZA DELLE NOZIONI DI BASE DI ALGEBRA LINEARE E GEOMETRIA ANALITICA E CHE LO STUDENTE SAPPIA RISOLVERE I SISTEMI DI EQUAZIONI LINEARI ED ESEGUIRE LE OPERAZIONI SUI VETTORI E SULLE MATRICI.
Contenuti
1. LA PROGRAMMAZIONE LINEARE (PL) (10 ORE DI LEZIONE E 4 DI ESERCITAZIONE)
- RICHIAMI DI ALGEBRA LINEARE, OPERAZIONI SUI VETTORI E SULLE MATRICI, SISTEMI DI EQUAZIONI LINEARI;
- PASSAGGIO DAL PROBLEMA REALE AL MODELLO DI OTTIMIZZAZIONE;
- IPERPIANI, SEMISPAZI, POLIEDRI, DIREZIONI ESTREME DI UN POLIEDRO, TEOREMA DELLA RAPPRESENTAZIONE.
2. IL METODO DEL SIMPLESSO (6 ORE DI LEZIONE E 4 DI ESERCITAZIONE)
- PUNTI ESTREMI DI UN POLIEDRO E SOLUZIONI DI BASE AMMISSIBILI, CONDIZIONI DI OTTIMALITÀ E DI ILLIMITATEZZA, L'ALGEBRA DEL METODO DEL SIMPLESSO, SOLUZIONI DI BASE DEGENERI E FENOMENO DEL CYCLING, CONVERGENZA DEL METODO DEL SIMPLESSO;
- RICERCA DI UNA SOLUZIONE AMMISSIBILE DI BASE INIZIALE: METODO DELLE DUE FASI E METODO DEL BIG-M (SOLO DEFINIZIONE DEL PROBLEMA).
3. TEORIA DELLA DUALITÀ (6 ORE DI LEZIONE E 4 DI ESERCITAZIONE)
- FORMULAZIONE DEL PROBLEMA DUALE, TEOREMA DEBOLE E TEOREMA FORTE DELLA DUALITÀ, TEOREMA DEGLI SCARTI COMPLEMENTARI, RELAZIONI PRIMALE-DUALE;
- INTERPRETAZIONE ECONOMICA DELLE VARIABILI DUALI;
- ANALISI DELLA SENSITIVITÀ ED ANALISI PARAMETRICA: ANALISI POST-OTTIMALE, VARIAZIONE DELLA SOLUZIONE OTTIMA E DEL VALORE OTTIMO DI UN PROBLEMA DI PL AL VARIARE DEI DATI;
- UTILIZZO DEL SOFTWARE EXCEL PER LA RISOLUZIONE DI PROBLEMI DI PROGRAMMAZIONE LINEARE.
4. PROBLEMI DI OTTIMIZZAZIONE SU GRAFI (10 ORE DI LEZIONE E 4 DI ESERCITAZIONE)
MODELLI MATEMATICI E ALGORITMI RISOLUTIVI PER I SEGUENTI PROBLEMI DI OTTIMIZZAZIONE SU GRAFI:
- FLUSSO A COSTO MINIMO;
- TRASPORTO;
- MASSIMO FLUSSO;
- CAMMINI MINIMI;
- ALBERO DI COPERTURA DI PESO MINIMO.
Metodi Didattici
L’INSEGNAMENTO PREVEDE LEZIONI FRONTALI DELLA DURATA DI 48 ORE COMPLESSIVE (6 CFU), CHE SI SVOLGONO IN AULA CON L’AUSILIO DI PROIEZIONI; ALLA FINE DELLA PRESENTAZIONE DI UN ARGOMENTO SONO PREVISTI VARI ESEMPI APPLICATIVI ED ESERCITAZIONI IN AULA. NELLE ESERCITAZIONI IN AULA VIENE ASSEGNATO AGLI STUDENTI UN ESERCIZIO DA RISOLVERE UTILIZZANDO LE TECNICHE PRESENTATE NELLE LEZIONI TEORICHE. LO SVOLGIMENTO DEL PROBLEMA È GUIDATO DAL DOCENTE E TENDE A SVILUPPARE E RAFFORZARE LE CAPACITÀ DELL’ALLIEVO DI IDENTIFICARE LE TECNICHE PIÙ IDONEE ALLA RISOLUZIONE DELL’ESERCIZIO. VENGONO ANCHE PROPOSTE LE METODICHE PER PRODURRE UN ELABORATO CHIARO NEL PROCEDIMENTO ED ACCURATO NEI RISULTATI DA CONSEGUIRE.
Verifica dell'apprendimento
L'ESAME NON PREVEDE PROVE INTERCORSO.
LA PROVA DI ESAME È FINALIZZATA A VALUTARE NEL SUO COMPLESSO LE CONOSCENZE E LE CAPACITÀ DI COMPRENSIONE DEI CONCETTI PRESENTATI A LEZIONE, NONCHÉ LA CAPACITÀ DI APPLICARE TALI CONOSCENZE NELLA RISOLUZIONE DI PROBLEMI DI PROGRAMMAZIONE LINEARE CONTINUA.
LA PROVA DI ESAME SI ARTICOLA IN UNA PROVA SCRITTA SELETTIVA ED UN COLLOQUIO ORALE.
- LA PROVA SCRITTA È TESA A VALUTARE LE CAPACITÀ DI RISOLUZIONE DEI PROBLEMI DI OTTIMIZZAZIONE ED HA, DI NORMA, UNA DURATA DI 120 MINUTI. ESSA È COMPOSTA DA 4 O 5 ESERCIZI E EVENTUALI DOMANDE A RISPOSTA APERTA, A CUI È ASSOCIATO UN PUNTEGGIO. LA SOMMA DI QUESTI PUNTEGGI È PARI A 30. ALCUNI DEI TIPICI ARGOMENTI PROPOSTI NEGLI ESERCIZI RIGUARDANO: LA RISOLUZIONE GRAFICA DI PROBLEMI DI PL ED IL CALCOLO DELLE DIREZIONI ESTREME, LA FORMULAZIONE DI PROBLEMI DI OTTIMIZZAZIONE, LA COSTRUZIONE DEL PROBLEMA DUALE, L'ANALISI DELLA SENSITIVITÀ, E LA RISOLUZIONE DEI PROBLEMI SU GRAFI PRESENTATI AL CORSO. IL PUNTEGGIO DELLA PROVA SCRITTA È PARI ALLA SOMMA DEI PUNTI ASSEGNATI DAL DOCENTE AI SINGOLI QUESITI SVOLTI DALLO STUDENTE. È AMMESSO ALLA PROVA ORALE LO STUDENTE CHE HA CONSEGUITO UN PUNTEGGIO NON INFERIORE A 18.

- CON IL COLLOQUIO ORALE SARANNO VALUTATE LE CONOSCENZE ACQUISITE IN MERITO ALLA MODELLAZIONE E RISOLUZIONE DI PROBLEMI DI PROGRAMMAZIONE LINEARE. IL COLLOQUIO PREVEDE LA PRELIMINARE DISCUSSIONE DEL COMPITO E VARIE DOMANDE RIGUARDANTI GLI ARGOMENTI DEL PROGRAMMA DEL CORSO. IL LIVELLO DI VALUTAZIONE MINIMO (18) È ATTRIBUITO QUANDO LO STUDENTE MOSTRA UNA CONOSCENZA FRAMMENTARIA DEI CONTENUTI TEORICI E UNA LIMITATA CAPACITÀ DI FORMULARE I PROBLEMI DI OTTIMIZZAZIONE E DI APPLICARE GLI ALGORITMI RISOLUTIVI. IL LIVELLO MASSIMO (30) È ATTRIBUITO QUANDO LO STUDENTE DIMOSTRA UNA CONOSCENZA COMPLETA ED APPROFONDITA DEGLI ARGOMENTI DEL CORSO E UNA NOTEVOLE CAPACITÀ DI APPLICAZIONE DEI METODI RISOLUTIVI PRESENTATI.

- PER DECIDERE IL VOTO FINALE, IL DOCENTE TIENE PRESENTE I RISULTATI DELLE DUE PROVE. IN OGNI CASO, IL VOTO FINALE NON PUÒ SUPERARE DI OLTRE 6 PUNTI IL VOTO DELLA PROVA SCRITTA.

- LA LODE VIENE ATTRIBUITA QUANDO LO STUDENTE DIMOSTRA SIGNIFICATIVA PADRONANZA DEI CONTENUTI TEORICI ED OPERATIVI E MOSTRA DI SAPER PRESENTARE GLI ARGOMENTI CON NOTEVOLE PROPRIETÀ DI LINGUAGGIO E CAPACITÀ DI ELABORAZIONE AUTONOMA ANCHE IN CONTESTI DIVERSI DA QUELLI PROPOSTI DAL DOCENTE NELLE ATTIVITÀ DIDATTICHE.

NELL'EVENTUALITÀ IN CUI L'ESAME DOVESSE SVOLGERSI A DISTANZA A CAUSA DELL'EMERGENZA COVID-19, IL DOCENTE PUÒ DECIDERE (DANDONE TEMPESTIVA COMUNICAZIONE AGLI STUDENTI), DI ABOLIRE LA PROVA SCRITTA. IN TAL CASO DURANTE LA PROVA ORALE VERRÀ ANCHE RICHIESTO AGLI STUDENTI DI RISOLVERE UNO O PIÙ ESERCIZI DELLA TIPOLOGIA DI QUELLI PROPOSTI NELLA PROVA SCRITTA.
Testi
- M.S. BAZARAA, J.J. JARVIS & H.D. SHERALI, LINEAR PROGRAMMING AND NETWORK FLOWS, FOURTH EDITION, JOHN WILEY, 2010.
- DIAPOSITIVE DELLE LEZIONI DISPONIBILI SULLA PAGINA WEB DEL DOCENTE: HTTPS://DOCENTI.UNISA.IT/020511/RISORSE
PER APPROFONDIMENTI:
HILLIER FREDERICK S., RICERCA OPERATIVA, MCGRAW-HILL EDUCATION, 2010.
Altre Informazioni
- IL CORSO È EROGATO IN ITALIANO;
- LA FREQUENZA NON È OBBLIGATORIA MA CALDAMENTE CONSIGLIATA;
- GLI ESERCIZI SVOLTI E LE PRECEDENTI TRACCE DI ESAME SONO DISPONIBILI SULLA PAGINA WEB DEL DOCENTE:
HTTPS://DOCENTI.UNISA.IT/020511/RISORSE
- L’ORARIO DI RICEVIMENTO È DISPONIBILE SULLA PAGINA WEB DEL DOCENTE: HTTPS://DOCENTI.UNISA.IT/020511/HOME
  BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2024-08-21]