Il metodo ''Feasibility Pump'' per un problema MIP

L'anteprima di questa tesi è scaricabile in PDF gratuitamente.
Per scaricare il file PDF è necessario essere iscritto a Tesionline.
L'iscrizione non comporta alcun costo. Mostra/Nascondi contenuto.

M.Mastromarino: Il metodo ’Feasibility Pump’ per un problema MIP 3 INTRODUZIONE Un problema di Programmazione Lineare (PL) ` e un particolare Proble- ma di Ottimizzazione che ha come obiettivo la minimizzazione o la mas- simizzazione di una funzione lineare c T x sull’insieme delle soluzioni di un sistema di equazioni e disequazioni lineari. La funzione lineare c T x viene detta funzione obiettivo e le disequazioni ed equazioni lineari che definisco- no le soluzioni ammissibili vengono dette vincoli del problema. Risolvere un problema di Programmazione Lineare significa individuare una soluzio- ne ottima x ∗ o concludere che il problema ` e inferiormente illimitato (se il problema ` e di minino), superiormente illimitato ( se il problema ` e di massi- mo) o inammissibile. Un generico problema MIP (Programmazione Intera Mista) ` e un problema della forma:          min c T x Ax≥b x j intero ∀j∈ I dove A ` e una matrice mxn e I ` e il sottinsieme delle variabili vincolate ad essere intere. Lo scopo della mia tesi ` e quello di discutere un metodo per trovare una soluzione ammissibile per un generico problema MIP. Questo problema f` a parte della classe dei problemi NP-hard, che, a differenza del- le classi P, NP e degli NP-completi, non ` e limitata per definizione ai soli problemi di decisione [5]; vi appartengono infatti anche problemi di ottimiz- zazione e di altri generi. In particolare, discuter` o un nuovo approccio per calcolare le soluzioni MIP euristiche,chiamato‘Feasibility Pump’. Coniltermineeuristicosiintende

Anteprima della Tesi di Mariangela Mastromarino

Anteprima della tesi: Il metodo ''Feasibility Pump'' per un problema MIP, Pagina 2

Laurea liv.I

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Mariangela Mastromarino Contatta »

Composta da 30 pagine.

 

Questa tesi ha raggiunto 258 click dal 09/06/2011.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.