Problemi di Ottimizzazione Combinatoria

Analisi dettagliata con formule ed esempi

Tre Takeaways Principali

• Problema di Assegnamento: Si risolve in tempo polinomiale e richiede l'assegnazione di risorse a compiti minimizzando il costo totale.
• Problema dello Zaino: Un problema NP-completo che massimizza il valore degli oggetti entro la capacità dello zaino.
• Problema del Commesso Viaggiatore: Un problema NP-difficile che cerca il percorso più breve per visitare tutte le città una volta sola e ritornare alla città di partenza.

---

Problema di Assegnamento

Descrizione

Il problema di assegnamento è un problema di ottimizzazione combinatoria che consiste nell'assegnare un insieme di risorse (o agenti) a un insieme di attività (o compiti) in modo da minimizzare o massimizzare un obiettivo specifico, generalmente il costo o il profitto. Questo problema è considerato "facile" rispetto ad altri problemi combinatori perché può essere risolto in tempo polinomiale.

Formulazione Matematica

Supponiamo di avere \( n \) agenti e \( n \) compiti. Ogni agente \( i \) può essere assegnato a un compito \( j \) con un costo \( c_{ij} \). L'obiettivo è trovare un'assegnazione che minimizzi il costo totale.

La formulazione del problema come programmazione lineare intera è la seguente:

\[ \min \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij} x_{ij} \]

soggetto a:

\[ \sum_{i=1}^{n} x_{ij} = 1 \quad \forall j \in \{1, 2, ..., n\} \] \[ \sum_{j=1}^{n} x_{ij} = 1 \quad \forall i \in \{1, 2, ..., n\} \] \[ x_{ij} \in \{0, 1\} \quad \forall i, j \in \{1, 2, ..., n\} \]

Dove \( x_{ij} \) è una variabile binaria che vale 1 se l'agente \( i \) è assegnato al compito \( j \), e 0 altrimenti.

Esempio

Consideriamo un esempio con 3 agenti e 3 compiti. I costi di assegnazione sono dati dalla seguente matrice:

\[ \begin{bmatrix} 9 & 2 & 7 \\ 6 & 4 & 3 \\ 5 & 8 & 1 \end{bmatrix} \]

L'assegnazione ottimale che minimizza il costo totale è:

• Agente 1 al compito 2 (costo: 2)
• Agente 2 al compito 3 (costo: 3)
• Agente 3 al compito 1 (costo: 5)

Il costo totale è quindi \( 2 + 3 + 5 = 10 \).

Considerazioni Finali

Il problema di assegnamento, pur essendo un problema lineare con vincoli semplici, può essere risolto in tempo polinomiale tramite algoritmi come il metodo ungherese. Questo rende il problema di assegnamento particolarmente utile in contesti pratici come la gestione delle risorse umane e la logistica.

---

Problema dello Zaino

Descrizione

Il problema dello zaino è un problema di ottimizzazione combinatoria che consiste nel selezionare un sottoinsieme di oggetti, ciascuno con un peso e un valore, da inserire in uno zaino con capacità limitata, in modo da massimizzare il valore totale degli oggetti inseriti senza superare la capacità dello zaino.

Formulazione Matematica

Supponiamo di avere \( n \) oggetti, ciascuno con un peso \( w_i \) e un valore \( v_i \). La capacità dello zaino è \( W \). L'obiettivo è massimizzare il valore totale degli oggetti inseriti nello zaino.

La formulazione del problema come programmazione lineare intera è la seguente:

\[ \max \sum_{i=1}^{n} v_i x_i \]

soggetto a:

\[ \sum_{i=1}^{n} w_i x_i \leq W \] \[ x_i \in \{0, 1\} \quad \forall i \in \{1, 2, ..., n\} \]

Dove \( x_i \) è una variabile binaria che vale 1 se l'oggetto \( i \) è inserito nello zaino, e 0 altrimenti.

Esempio

Consideriamo un esempio con 4 oggetti:

• Oggetto 1: peso 2, valore 10
• Oggetto 2: peso 3, valore 5
• Oggetto 3: peso 6, valore 15
• Oggetto 4: peso 7, valore 7

La capacità dello zaino è \( W = 10 \).

La soluzione ottimale che massimizza il valore totale è:

• Inserire l'oggetto 1 (peso: 2, valore: 10)
• Inserire l'oggetto 3 (peso: 6, valore: 15)

Il valore totale è quindi \( 10 + 15 = 25 \).

Considerazioni Finali

Il problema dello zaino (nel caso 0/1) è NP-completo; esistono algoritmi esatti (programmazione dinamica, branch and bound) e approssimazioni (algoritmi greedy, approssimazioni pseudo-polinomiale) per risolverlo. Questo problema ha applicazioni in vari campi, come la logistica, la pianificazione finanziaria e la gestione delle risorse.

---

Problema del Commesso Viaggiatore

Descrizione

Il problema del commesso viaggiatore (TSP, Traveling Salesman Problem) è un problema di ottimizzazione combinatoria che consiste nel trovare il percorso più corto che visita una serie di città e ritorna alla città di partenza, visitando ciascuna città esattamente una volta.

Formulazione Matematica

Supponiamo di avere \( n \) città e una matrice dei costi \( c_{ij} \) che rappresenta il costo di viaggio tra la città \( i \) e la città \( j \). L'obiettivo è trovare un ciclo hamiltoniano di costo minimo.

La formulazione del problema come programmazione lineare intera è la seguente:

\[ \min \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij} x_{ij} \]

soggetto a:

\[ \sum_{j=1}^{n} x_{ij} = 1 \quad \forall i \in \{1, 2, ..., n\} \] \[ \sum_{i=1}^{n} x_{ij} = 1 \quad \forall j \in \{1, 2, ..., n\} \] \[ \sum_{i \in S} \sum_{j \notin S} x_{ij} \geq 1 \quad \forall S \subset \{1, 2, ..., n\}, 2 \leq |S| \leq n-1 \] \[ x_{ij} \in \{0, 1\} \quad \forall i, j \in \{1, 2, ..., n\} \]

Dove \( x_{ij} \) è una variabile binaria che vale 1 se il percorso va dalla città \( i \) alla città \( j \), e 0 altrimenti. Le ultime condizioni sono dette "condizioni di sottotour" e impediscono la formazione di cicli che non visitano tutte le città.

Esempio

Consideriamo un esempio con 4 città. La matrice dei costi è:

\[ \begin{bmatrix} 0 & 10 & 15 & 20 \\ 10 & 0 & 35 & 25 \\ 15 & 35 & 0 & 30 \\ 20 & 25 & 30 & 0 \end{bmatrix} \]

La soluzione ottimale che minimizza il costo totale è:

• Partire dalla città 1, andare alla città 2 (costo: 10)
• Dalla città 2 alla città 4 (costo: 25)
• Dalla città 4 alla città 3 (costo: 30)
• Dalla città 3 tornare alla città 1 (costo: 15)

Il costo totale del percorso è quindi \( 10 + 25 + 30 + 15 = 80 \).

Considerazioni Finali

Il problema del commesso viaggiatore è NP-hard; esistono metodi esatti (branch and cut, programmazione lineare intera) per istanze piccole e algoritmi euristici (ad esempio, nearest neighbor, 2-opt, metaeuristiche come l’algoritmo genetico) per istanze di grandi dimensioni. Questo problema ha applicazioni pratiche in vari campi come la logistica, la pianificazione e la ricerca operativa.

Strategie di Soluzione per il TSP

Le strategie tradizionali per risolvere il TSP includono:

• Trovare un caso specifico del problema (sottoproblema) per il quale sia possibile una soluzione esatta o un'euristica migliore.
• Progettare algoritmi euristici che producono soluzioni probabilmente buone, ma impossibili da provare essere ottimali.
• Progettare algoritmi per trovare la soluzione esatta, ragionevolmente veloci solo per problemi con un numero di città relativamente basso.

Algoritmi e Metodi

Alcuni degli algoritmi e metodi utilizzati per risolvere il TSP includono:

• Algoritmi branch and bound, adatti per problemi con 50-60 città.
• Algoritmi che procedono per raffinamenti successivi usando tecniche derivate dalla programmazione lineare, adatti per problemi fino a 120-200 città.
• Implementazioni recenti di branch and bound e branch and cut basati sulla programmazione lineare, adatti per problemi contenenti fino a 5.000 città.

Euristiche

Esistono vari tipi di euristiche per il TSP:

• L'algoritmo nearest neighbor, che normalmente è abbastanza vicino alla soluzione ottima, ma può produrre soluzioni pessime in alcuni casi.
• Euristica Pairwise exchange, o euristica di Lin-Kernighan.
• Euristica k-opt.

TSP Euclideo

Il TSP euclideo è un caso particolare del TSP con disuguaglianza triangolare, poiché le distanze nel piano obbediscono a tale vincolo. Questo problema, sebbene ancora NP-difficile, può essere risolto con euristiche che lavorano meglio rispetto al caso generale.

TSP Asimmetrico

Il TSP asimmetrico si verifica quando la distanza tra due nodi non è la stessa in entrambe le direzioni. Questo caso è più complesso del TSP simmetrico e ha applicazioni pratiche, ad esempio nella pianificazione di percorsi in strade con sensi unici.

Esempi di Applicazioni del TSP

Il TSP ha trovato applicazioni in vari settori:

• Logistica: Pianificazione delle rotte per la consegna di merci o per i trasporti pubblici.
• Produzione: Ottimizzazione dei percorsi delle macchine o dei robot all'interno di una fabbrica.
• Informatica: Progettazione di circuiti stampati e ottimizzazione del cablaggio.

Tabella di Confronto

Problema	Obiettivo	Complessità	Algoritmi Tipici
Assegnamento	Minimizzare il costo totale	Polinomiale	Metodo Ungherese
Zaino	Massimizzare il valore totale	NP-completo	Programmazione Dinamica, Branch and Bound
Commesso Viaggiatore	Trovare il percorso più breve	NP-hard	Branch and Cut, Euristiche (Nearest Neighbor, 2-opt)

Conclusione

I problemi di assegnamento, dello zaino e del commesso viaggiatore rappresentano sfide fondamentali nell'ottimizzazione combinatoria. Ognuno di essi ha applicazioni pratiche in vari campi come la logistica, la produzione, la pianificazione e la ricerca operativa. La comprensione di questi problemi e delle tecniche per risolverli è cruciale per affrontare problemi reali di ottimizzazione.

Riferimenti