La Ricerca Operativa è la disciplina che studia e mette a punto metodologie ed algoritmi per la risoluzione di problemi di ottimizzazione, ossia problemi in cui tipicamente occorre prendere decisioni circa l’uso di risorse disponibili solo in quantità limitate in modo tale da rispettare un assegnato insieme di vincoli e da massimizzare il beneficio ottenibile dall’uso delle risorse o minimizzare il costo totale che comporta l’utilizzo delle risorse stesse.
Un processo decisionale alla base dell’analisi e risoluzione di un problema di ottimizzazione può essere scomposto nelle seguenti fasi:
L’insegnamento di Ricerca Operativa si prefigge quale obiettivo principale l’introduzione degli studenti all’uso dei modelli di programmazione matematica ed in particolare ai modelli di ottimizzazione lineare (sia continui che a variabili intere) ed alle loro applicazioni nei campi della logistica, dei servizi e della produzione industriale.
L’impostazione metodologica del Corso, inoltre, punta al conseguimento dei seguenti ulteriori obiettivi intermedi:
Tipicamente, un problema viene definito per mezzo di:
Un altro modo per definire un problema è fornire l’insieme P di tutte le sue possibili soluzioni.
P è detto insieme ammissibile ed i suoi elementi soluzioni ammissibili.
Un problema di ottimizzazione è un problema tale che sull’insieme delle sue soluzioni ammissibili è definita una funzione obiettivo da massimizzare, se c esprime un profitto o beneficio associato ad ogni soluzione, oppure da minimizzare se c ne esprime un costo.
Dunque, una soluzione ottima al problema è una soluzione che rende minima o massima la funzione obiettivo.
Tale tipo di problema può essere genericamente scritto come
Dato un problema (P), indichiamo con il valore ottimo della funzione obiettivo ed una soluzione tale che è detta soluzione ottima di (P).
In alcuni casi, invece di richiedere una soluzione ottima di un problema, può essere richiesto di individuarne una qualsiasi soluzione ammissibile, ossia di determinare se l’insieme delle soluzioni ammissibili sia vuoto o meno.
In casi del genere, si parla di problema decisionale o problema di esistenza.
Una volta formulato, un problema di ottimizzazione va chiaramente risolto tramite applicazione di un metodo che, data una qualunque istanza del problema, fornisca una soluzione in un tempo finito.
Dal punto di vista computazionale-algoritmico, i problemi di ottimizzazione si suddividono in:
problemi computazionalmente trattabili e problemi computazionalmente intrattabili.
Tali due classi coincidono in larga parte rispettivamente con la classe dei problemi polinomiali (cioè che richiedono un tempo polinomiale per essere risolti) e la classe dei problemi NP-ardui.
Nel corso delle lezioni seguenti impareremo a costruire il modello logico-matematico a partire dalla descrizione verbale di un problema e delle sue caratteristiche, ossia definiremo formalmente un problema di Programmazione Matematica ed in particolare un problema di Programmazione Lineare (PL).
Saranno, inoltre, descritti alcuni esempi di problemi di PL che chiariranno i concetti esposti.
Gli algoritmi utilizzati per risolvere i problemi di ottimizzazione si suddividono in tre categorie principali:
- Metodi esatti.
Essi risolvono il problema all’ottimo. In caso di problemi difficili, essi richiedono complessità computazionale esponenziale o comunque superpolinomiale.
- Metodi di approssimazione:
Essi trovano una soluzione subottima, garantendo un indice della qualità della soluzione approssimata individuata.
La loro applicazione risulta utile in caso di problemi difficili. E’ chiaro che in tal caso sarebbe auspicabile che il tempo di computazione da essi richiesto sia polinomiale (se avessero complessità superpolinomiale, non si avrebbe alcun vantaggio nell’applicarli!).
- Metodi euristici.
Essi trovano una soluzione subottima senza alcuna garanzia circa la qualità della soluzione individuata, per cui è ovvio che ha senso la messa a punto di euristiche solo polinomiali.
L’applicazione di tali metodi è particolarmente indicata per risolvere problemi del mondo reale di grandi dimensioni o problemi talmente difficili dal punto di vista computazionale che per essi non esiste neanche un algoritmo capace di trovare una soluzione approssimata in tempo polinomiale.
Siano
una variabile vettoriale ad n componenti, dette variabili di decisione;
m funzioni scalari del vettore
decisionale x;
un vettore a componenti scalari detto vettore dei termini noti,
la variabile x è detta vincolata se per ogni deve essere soddisfatta almeno una delle seguenti relazioni
Le relazioni (1) e (3) sono dette vincoli di disuguaglianza, mentre la relazione (2) è detta vincolo di uguaglianza.
L’insieme , dove con il simbolo si intende che per ogni i vale uno dei tre simboli , è detto insieme ammissibile ed è l’insieme dei punti che soddisfano i vincoli sulle variabili.
Si consideri ora un’ulteriore funzione scalare z(x) della variabile x detta funzione obiettivo e si consideri il problema di determinare il valore della variabile x che renda minima (risp. massima) la funzione obiettivo z(x) sull’insieme S, cioè nel rispetto dei vincoli sulle variabili di decisione del tipo (1), (2) o (3).
In termini formali, consideriamo il seguente problema:
Il problema appena descritto è un problema di Programmazione Matematica, la cui soluzione è chiaramente un punto appartenente ad S ed inoltre risulta che
è detto un punto di minimo vincolato}(risp. massimo vincolato) per la funzione obiettivo z(x)
1. Presentazione del Corso ed Introduzione alla Programmazione Mat...
2. Introduzione ai Problemi di PL
6. Algoritmo del Simplesso Revisionato
7. Algoritmo del Simplesso Tabellare
10. Soluzione di Problemi di PL tramite Algoritmo del Simplesso
11. Problemi di Programmazione Lineare Intera
12. PLI con matrice dei vincoli unimodulare
13. Problemi di PLI: Branch & Bound
14. Il Problema dello Zaino 0/1 e il Problema dello Zaino Frazionar...
15. Il Problema dello Zaino 0/1: un algoritmo B&B
16. Il Problema dello Zaino 0/1: un algoritmo di Programmazione Din...
17. Richiami di Teoria dei Grafi: definizioni e notazioni
18. Il Problema del Vertex Cover Minimo di un Grafo
19. Il Problema dell'Albero di Copertura Minimo (MST)
20. Il Problema dell'Albero di Copertura Minimo (MST): esempio
D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.
M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.
S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.
S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.
Dispense ed Appunti del Corso.