Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Paola Festa » 1.Presentazione del Corso ed Introduzione alla Programmazione Matematica


Cos’è la Ricerca Operativa?

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:

  1. individuazione del problema e delle sue caratteristiche;
  2. costruzione di un modello logico-matematico che lo rappresenti;
  3. determinazione di una o più soluzioni;
  4. analisi dei risultati ottenuti.

Obiettivi del Corso

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:

  • capacità di formularizzazione dei modelli di ottimizzazione per problemi di logistica, organizzazione, pianificazione, scheduling, trasporto, flusso su reti e problemi su grafi;
  • conoscenza della teoria e dei metodi di ottimizzazione lineare continua, di ottimizzazione lineare discreta e di ottimizzazione su grafi;
  • capacità di utilizzazione dei modelli matematici dei classici problemi di ottimizzazione e dei relativi algoritmi di risoluzione nei campi della Pianificazione della Produzione, della Localizzazione, della Gestione delle Scorte e della Logistica.

Classificazione dei problemi di ottimizzazione, 1

Tipicamente, un problema viene definito per mezzo di:

  • una descrizione dei suoi parametri, lasciati in generale indeterminati;
  • una descrizione delle proprietà che deve esibire la soluzione desiderata.

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 c:P\rightarrow {\mathbb R} 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 x\in Pche rende minima o massima la funzione obiettivo.

Tale tipo di problema può essere genericamente scritto come

\[(P)\ \ \ \min\{c(x):\ x\in P\}.\]

Dato un problema (P), indichiamo con z^*=\min\{c(x):\ x\in P\} il valore ottimo della funzione obiettivo ed una soluzione x^*\in P tale che x^*\in P è detta soluzione ottima di (P).

Classificazione dei problemi di ottimizzazione, 2

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.

Classificazione dei metodi risolutivi

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.

Problemi di Programmazione Matematica, 1

Siano

(x_1,x_2,\ldots,x_n)=x\in {\mathbb R}^n una variabile vettoriale ad n componenti, dette variabili di decisione;

\{g_i(x):{\mathbb R}^n\rightarrow {\mathbb R},\ i=1,2,\ldots,m\} m funzioni scalari del vettore

decisionale x;

(b_1,b_2,\ldots,b_m)=b\in {\mathbb R}^mun vettore a componenti scalari detto vettore dei termini noti,

la variabile x è detta vincolata se per ogni i=1,2,\ldots,m deve essere soddisfatta almeno una delle seguenti relazioni

\[\begin{array}{llll}\mbox{{\rm (1)}} & g_i(x) & \leq & b_i\ ; \\\mbox{{\rm (2)}} & g_i(x) & =    & b_i\ ; \\\mbox{{\rm (3)}} & g_i(x) & \geq & b_i\ .\end{array}\]

Problemi di Programmazione Matematica, 2

Le relazioni (1) e (3) sono dette vincoli di disuguaglianza, mentre la relazione (2) è detta vincolo di uguaglianza.

L’insieme S=\{x\in {\mathbb R}^n\ \vert\ g_i(x)\approx b_i\}, dove con il simbolo \approx si intende che per ogni i vale uno dei tre simboli \leq, \geq, =, è detto insieme ammissibile ed è l’insieme dei punti x\in {\mathbb R}^n 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).

Problemi di Programmazione Matematica, 3

In termini formali, consideriamo il seguente problema:

\begin{array}{llll}\mbox{{\rm min}} & z(x) & \mbox{{\rm (risp. max $z(x)$)}} \\\mbox{{\rm s.a (soggettoa)}}\\&g_1(x) & \approx & b_1 \\& g_2(x) & \approx & b_2 \\& \cdots & \approx & \cdots \\& g_m(x) & \approx& b_m.\end{array}

Il problema appena descritto è un problema di Programmazione Matematica, la cui soluzione x^* è chiaramente un punto appartenente ad S ed inoltre risulta che

\forall\ x\in S\ \ z(x^*)\leq z(x)\ \mbox{{\rm (risp. $z(x^*)\geq z(x)$)}}.

\[x^*\] è detto un punto di minimo vincolato}(risp. massimo vincolato) per la funzione obiettivo z(x)

I materiali di supporto della lezione

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.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion