In termini generali un problema di ottimizzazione può essere formulato come
z = f (x) Max!
x ∈ X
con
Una soluzione x*∈X è un massimo locale se f(x*)≥f(x) per ogni x ∈Iε(x).
Una soluzione x*∈X è un massimo globale se f(x*)≥f(x) per ogni x ∈X.
Per definire un problema di ottimizzazione è 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.
Problema e metodo di risoluzione
Una volta formalizzato un problema di ottimizzazione si pone il problema di individuarne le soluzioni (ottimi globali o locali).
Un metodo di risoluzione è una tecnica che consente di trovare soluzioni del problema.
Un metodo di risoluzione può essere
Istanza e dimensione di un problema
Un’istanza di un problema rappresenta un esempio del problema in esame
Dato un problema Π, si dice che un’istanza I di Π ha dimensione n, nell’alfabeto (finito) Σ, se la sequenza di simboli di Σ necessaria per codificare i dati di ingresso richiede n simboli.
Un alfabeto classicamente adottato per la codifica è l’alfabeto binario (Σ={0,1}); in questo caso la dimensione di I è pari al numero di bit necessari per la codifica dei dati di input.
Notazione O(.)
Una funzione f(n) è detta O(g(n)) (f(n)=O(g(n)) se esistono un n*≥0 e un c≥1 tali che f(n)≤c g(n) per ogni n≥n*.
La notazione O(.) consente di definire, per una data funzione, un limite superiore rispetto ad un fattore moltiplicativo.
Notazione Ω(.)
Una funzione f(n) è detta Ω(g(n)) (f(n)=Ω(g(n)) se esistono un n*≥0 e un c≥1 tali che f(n)≤c g(n) per ogni n≥n*.
La notazione Ω(.) consente di definire, per una data funzione, un limite inferiore rispetto ad un fattore moltiplicativo.
Funzione di complessità di un algoritmo f(n)
Rappresenta, per ogni possibile valore n della dimensione del problema, il massimo numero di operazioni necessario all’algorimo a risolvere un problema di dimensione n.
Un algoritmo è di tipo polinomiale se la sua funzione di complessità f(n)=O(nk).
Ogni algoritmo la cui funzione di complessità non è polinomiale è detto di tipo esponenziale.
Un problema si dice trattabile se esiste un algoritmo polinomiale in grado di risolverlo.
In caso contrario, ovvero se non può esistere un algoritmo polinomiale in grado di risolverlo, si dice intrattabile.
La ragione di questa distinzione risulta evidente dalla tabella fornita da Garey and Johnson (1979).
Limiti classificazione
Per dimostrare che un problema è intrattabile bisogna dimostrare che non può esistere un algoritmo polinomiale in grado di risolverlo.
Si pone la questione di come si classifichino quei problemi per i quali
La teoria della complessità computazionale o della “NP completezza” (NP-Completeness) punta ad un’ulteriore classificazione dei problemi facendo riferimento ai cosiddetti problemi decisionali.
Un problema decisionale è un problema formulato in modo da ammettere due sole possibili risposte: SI o NO.
Esempio:
Dato un numero intero K, esiste una coppia di numeri interi m ed n (con m,n>1) tali che K=mn ?
Ogni problema di ottimizzazione può essere formulato come problema decisionale.
Esempio del problema del commesso viaggiatore (TSP)
Problema di ottimizzazione del TSP
Date n città, si individui il circuito di lunghezza minima che un commesso viaggiatore deve effettuare per visitare ciascuna città una sola volta.
Problema decisionale del TSP
Date n città, esiste un circuito che un commesso viaggiatore può effettuare per visitare ciascuna città una sola volta che risulti di lunghezza non superiore ad un valore B (≤B)?
Poiché per risolvere un problema di ottimizzazione si devono risolvere più problemi di decisione ad esso associati, si può concludere che la complessità di un problema di ottimizzazione sarà almeno pari a quello del problema di decisione ad esso associato.
Un problema decisionale è di tipo P se esiste un algoritmo polinomiale in grado di fornire una risposta di tipo SI o NO, ossia se è trattabile.
Un problema decisionale è di tipo NP se esiste un algoritmo polinomiale in grado di verificare una risposta di tipo SI.
Differenza tra P ed NP
Mentre in un problema P bisogna trovare la risposta in tempo polinomiale, in un problema NP, nel caso ci venga fornita una risposta di tipo SI, bisogna verificare che la risposta fornita sia effettivamente di tipo SI in tempo polinomale.
Ad esempio il TSP non è un problema di tipo P perché non siamo in grado di fornire una risposta in tempo polinomiale. Tuttavia il TSP è di tipo NP, perché, dato un circuito hamiltoniano di lunghezza ≤B, è possible verificare che si tratta di un circuito hamiltoniano di lunghezza ≤B in tempo polinomiale,
Risulta evidente che un problema di tipo P è certamente di tipo NP (P ⊆ NP) dal momento che l’algoritmo utilizzato per fornire una risposta in tempo polinomiale può essere utilizzato anche per verificare una risposta di tipo SI.
Non è stato ancora dimostrato che P⊂NP, ovvero che esistono problemi NP che non possano certamente essere risolti in tempo polinomiale.
Anche se non dimostrato formalmente si ritiene (congettura) che P⊂NP ovvero (vedi figura).
All’interno della classe dei problemi NP è possibile individuare un sottoinsieme di problemi “più difficili” detti NP-completi.
A tal fine è necessario introdurre il concetto di riducibilità tra due problemi.
Un problema Π è riducibile ad un problema Π* (Π ∝ Π*) se ogni istanza di Π può essere trasformato in tempo polinomiale in un’istanza di Π*.
Sia Π ∝Π *
↓
Esempio di riducibilità
Problema del sequenziamento di operazioni su una macchina
Siano date n operazioni da assegnare ad una macchina. Siano:
Esiste un sequenziamento delle operazioni tale che la somma dei tempi di setup non superi il valore B (Cmax≤ B)?)
Il problema può essere ridotto ad un problema di commesso viaggiatore su n+1 città.
Un problema decisionale Π è di tipo NP-completo se:
Importanza della classe dei problemi NP-completi
La classe dei problemi NP-completi è una classe di problemi più difficili all’interno della classe NP.
Se si individuasse un algoritmo polinomiale per risolvere un qualsiasi problema NP-completo allora tutti i problemi NP sarebbero trattabili ovvero P=NP.
Se si dimostrasse che un problema NP-completo è intrattabile, allora tutti i problemi NP sarebbero intrattabili ovvero P≠NP.
Un problema di ottimizzazione la cui versione decisionale appartiene alla classe dei problemi NP-completi è detto NP-hard (NP-difficile).
Per dimostrare che un Π è di tipo NP-completo bisogna:
Per poter applicare questa procedura è necessario conoscere un primo problema di tipo NP-completo (vedi figura).
Nel 1971 il matematico inglese Cook individuò un primo problema tipo NP-completo.
Da allora, attraverso il procedimento descritto, sono stati individuati numerosi problemi NP-completi.
Anche se non è stato dimostrato formalmente si adotta la congettura (l’ipotesi) P≠NP, ovvero si ritiene che i problemi NP siano intrattabili.
La teoria della NP-completezza consente di classificare nella classe dei problemi NP e NP-completo, problemi che non risultano né trattabili, né intrattabili.
Anche se non è stato dimostrato formalmente si adotta la congettura (l’ipotesi) P≠NP, ovvero si ritiene che i problemi NP siano intrattabili.
Ne consegue che i problemi NP vanno trattati, in pratica, come se fossero intrattabili. Pertanto poiché i tempi di calcolo di algoritmi risolutivi esatti applicati a questi problemi risultano esponenziali, nelle applicazioni pratiche bisogna ricorrere ad algoritmi di risoluzione euristici.
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...