Ricerca Operativa 2012/2013

Definizioni relative ai problemi di programmazione matematica: variabili decisionali, vincoli, funzione obiettivo. Problema vuoto, illimitato con ottimo finito. Problemi di ottimizzazione combinatoria. Problemi di programmazione lineare e lineare intera. Problemi di Ottimizzazione Combinatoria e relazione con la PLI. Problemi di programmazione matematica vuoti, illimitati, con ottimo finito. Teoremi. (1) In un problema di programmazione matematica con f.o. concava e regione ammissibile P, polìtopo non vuoto, esiste un ottimo su un vertice di P. (2) L'ottimo locale di un problema di programmazione convessa è anche ottimo globale. Elementi di geometria di R^n. Problemi di PL in forma standard. Definizioni di base, matrice di base, soluzione base (ammissibile). Thm. x è SBA di un PL in forma standard se e solo se è un vertice del poliedro regione ammissibile del PL: dimostrazione. Fase I del metodo del simplesso: condizione di ottimo per una SBA, cambiamento di base, definizione di una nuova SBA con valore migliore della f.o. Forma tableau del metodo del simplesso. Fase I del metodo del simplesso: definizione del problema artificiale. Determinazione di una SBA/condizioni di "vuotezza" di un PL. Metodo delle due fasi. Metodo del simplesso revised: condizione di ottimo per una SBA, cambiamento di base, definizione di una nuova SBA ottima. Teoria della dualità per la PL: introduzione. Rilassamento lagrangiano di un PL e determinazione del duale di un PL. Calcolo del duale di PL in formati diversi. Proprietà di dualità forte. Condizioni di ortogonalità per una coppia di PL Primale/Duale. Teoria della dualità per la PL: esempi sull'applicazione delle condizioni di ortogonalità. Analisi di sensibilità. Interpretazione economica del problema della dieta e del problema dei trasporti.  Il metodo del simplesso duale. Introduzione di vincoli aggiuntivi. Simplesso su reti: applicazione ai problemi di flusso a costo minimo. Formulazione di problemi di PL: Problema dei trasporti, minimizzazione di funzioni modulo e massimo di funzioni lineari come PL. Scheduling su macchina singola. Composizione di portfolio titoli. Problema di cutting stock unidimensionale (o minimizzazione degli "sfridi")