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).
In termini generali ed astratti, per definire un problema di ottimizzazione, quindi, è necessario individuare:
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.
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:
I modelli di programmazione matematica possono essere classificati
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 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.
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.
1. Introduzione al corso di Ricerca operativa II
2. Generalità e classificazione dei sistemi di produzione
3. La logistica dei sistemi di produzione
4. Introduzione all'ottimizzazione combinatoria
5. Fondamenti di teoria della complessità computazionale
6. Algoritmi euristici costruttivi e migliorativi
10. Problemi di Localizzazione
12. Introduzione alla gestione delle scorte
13. Modelli stocastici per la gestione delle scorte
14. Modelli discreti per la gestione delle scorte
15. Introduzione allo scheduling
16. Scheduling su macchina singola
17. Problemi di scheduling su macchina singola e su macchine parall...