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

Giuseppe Bruno » 4.Introduzione all'ottimizzazione combinatoria


Argomenti della lezione

  • Alcune definizioni fondamentali
  • La programmazione matematica
  • Classificazione dei modelli di programmazione matematica
  • Ottimizzazione combinatoria
  • Alcune considerazioni conclusive

Alcune definizioni fondamentali

Ottimizzare significa adottare la decisione migliore tra un insieme di alternative possibili.

L’ottimizzazione quindi presuppone la presenza di soluzioni alternative da comparare sulla base di un determinato criterio o obiettivo, e la scelta della decisione che ottimizzi (massimizzi o minimizzi) l’obiettivo assunto.

Nella maggior parte delle applicazioni il criterio di valutazione è un costo (da minimizzare) o un beneficio (da massimizzare).

Alcune definizioni fondamentali (segue)

In termini generali ed astratti, per definire un problema di ottimizzazione, quindi, è necessario individuare:

  • un insieme X di soluzioni ammissibili;
  • una funzione obiettivo z=f(x) definita per ogni xX che rappresenta il criterio di valutazione.

Una soluzione x*∈X è un massimo (minimo) locale se f(x*)≥f(x) (f(x*)≤f(x)) per ogni x ∈Iε(x).

Una soluzione x*∈X è un massimo (minimo) globale se f(x*)≥f(x) (f(x*)≤f(x)) per ogni x ∈X.

L’insieme X può essere rappresentato in diversi modi.
Un modo frequente è quello di descriverlo attraverso un insieme di relazioni matematiche (equazioni e/o disequazioni) che costituiscono i vincoli del problema.

La programmazione matematica


La programmazione matematica (segue)

Modello, problema e metodo di risoluzione

In questo contesto, i termini modello e problema possono essere utilizzati come sinonimi: in pratica, una volta formalizzato un modello matematico, si pone il problema di individuarne le soluzioni.

Un metodo di risoluzione è una tecnica che consente di trovare soluzioni del problema.

Un metodo di risoluzione può essere:

  • esatto se individua un ottimo globale ammissibile
  • euristico se è orientato alla ricerca di una buona soluzione (ma non necessariamente ottima).

Classificazione dei modelli di programmazione matematica

I modelli di programmazione matematica possono essere classificati

  • Sulla base delle caratteristiche delle funzioni (funzione obiettivo e vincoli) che compaiono nel modello.
  • Sulla base dei valori che possono assumere le variabili decisionali.

Classificazione dei modelli di programmazione matematica (segue)

Classificazione sulla base
delle funzioni che compaiono nel modello

Si basa sulle caratteristiche e e sulle proprietà della funzione obiettivo e dei vincoli.

Se tutte le funzioni del modello (funzione obiettivo e vincoli) sono lineari il modello è di programmazione lineare.

Se una qualsiasi delle funzioni è non lineare il modello è di programmazione non lineare.

Classificazione dei modelli di programmazione matematica (segue)


Classificazione dei modelli di programmazione matematica (segue)


Classificazione dei modelli di programmazione matematica (segue)

Classificazione dei problemi di programmazione lineare in base ai valori che possono assumere le variabili decisionali

In un problema di programmazione lineare continua tutte le variabili decisionali sono di tipo continuo.

In un problema di programmazione lineare intera alcune delle variabili decisionali sono vincolate ad assumere valori interi.

Un problema si dice di ottimizzazione combinatoria se tutte le variabili decisionali sono vincolate ad assumere valori interi e quindi la sua risoluzione consiste nella individuazione della combinazione ottimale dei valori delle variabili intere.

In un problema di programmazione lineare mista intera soltanto un sottoinsieme delle variabili decisionali è vincolato ad assumere valori interi mentre le restanti sono continue.

Classificazione dei modelli di programmazione matematica (segue)


Ottimizzazione combinatoria


Ottimizzazione combinatoria (segue)


Ottimizzazione combinatoria (segue)


Ottimizzazione combinatoria (segue)


Ottimizzazione combinatoria (segue)


Ottimizzazione combinatoria (segue)


Alcune considerazioni conclusive

Molti problemi di pianificazione, programmazione e gestione possono essere formulati come problemi di ottimizzazione combinatoria.

I problemi di ottimizzazione combinatoria risultano, in generale, di particolare complessità.

La scelta del metodo di risoluzione da utilizzare per risolvere un problema di ottimizzazione combinatoria dipende dalla sua complessità.

Risulta pertanto necessario avere a disposizione un sistema di classificazione dei problemi di ottimizzazione in modo da scegliere conseguentemente il metodo di risoluzione più opportuno.

  • 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