Modellazione di Problemi di Ottimizzazione

Author

Your Name

Published

January 30, 2025

Introduction

Questa lezione si concentra sul processo di formalizzazione e modellazione di problemi di ottimizzazione. L’obiettivo principale è quello di aiutare a comprendere come un ricercatore operativo affronta un problema pratico, traducendolo in un modello matematico risolvibile.

Definizione di problema e istanza.
Ruolo del ricercatore operativo nel processo di ottimizzazione.
Formalizzazione del problema: identificazione di dati, variabili, e obiettivo.
Modellazione del problema: scelta delle variabili e definizione dei vincoli.
Esempi di modellazione del problema del commesso viaggiatore (TSP).
Problemi di ammissibilità: modelli infeasible e istanze non ammissibili.
Esempi pratici di problemi di ammissibilità.

La lezione fornirà gli strumenti per comprendere come affrontare la modellazione di problemi complessi, trasformandoli in formulazioni matematiche trattabili e risolvibili mediante algoritmi di ottimizzazione.

Problemi, Istanze e Ruolo del Ricercatore Operativo

Un problema è una descrizione generale di una situazione che richiede di trovare una soluzione ottima, data una serie di requisiti e un obiettivo da ottimizzare. In altre parole, è la descrizione di un compito da svolgere, con specifici vincoli da rispettare e un criterio per valutare la qualità delle possibili soluzioni.

Un’istanza di un problema è una specifica realizzazione del problema, ottenuta assegnando valori concreti ai dati del problema. Un’istanza è quindi un caso particolare del problema generale, con dati specifici che definiscono un contesto univoco.

Esempio:

Problema: Organizzare il trasporto di merci da un magazzino a diversi negozi minimizzando i costi di trasporto.
Istanza: Trasportare 100 unità di prodotto A dal magazzino X al negozio Y, 50 unità di prodotto B dal magazzino X al negozio Z, e 70 unità di prodotto C dal magazzino X al negozio W, con costi di trasporto specifici per ogni tratta e tipo di prodotto.

Il ruolo del ricercatore operativo è quello di assistere chi deve risolvere un problema pratico, aiutandolo a:

Formalizzare il problema: tradurre il problema, spesso espresso in linguaggio naturale e in modo informale, in un modello matematico ben definito. Questo implica identificare gli aspetti fondamentali del problema, rimuovendo dettagli irrilevanti o contraddittori, e definire chiaramente le relazioni tra i diversi elementi del problema.
Studiare strumenti algoritmici: identificare o sviluppare algoritmi appropriati per risolvere il problema formalizzato. Questo può richiedere l’adattamento di algoritmi esistenti o la creazione di nuovi algoritmi specifici per il problema in questione. L’obiettivo è trovare un metodo efficiente per ottenere una soluzione ottima o una buona approssimazione di essa.

In sintesi, il ricercatore operativo agisce come un "traduttore" tra il mondo reale e il mondo matematico, trasformando problemi complessi in modelli risolvibili e fornendo gli strumenti per trovare le soluzioni ottime.

Formalizzazione del Problema

Per formalizzare un problema, è necessario identificare chiaramente tre elementi chiave:

Dati: Sono le informazioni note a priori, che costituiscono l’input del problema e non possono essere modificate dal decisore. Rappresentano le "costanti" del problema.
- Esempio: In un problema di produzione, i dati potrebbero includere la disponibilità di materie prime, la capacità produttiva degli impianti, i costi unitari di produzione, la domanda di mercato per ciascun prodotto, etc.
Variabili: Sono le decisioni che devono essere prese per risolvere il problema. Rappresentano le "incognite" del problema, i valori che devono essere determinati per ottenere una soluzione.
- Esempio: Nel problema di produzione, le variabili potrebbero rappresentare la quantità di ciascun prodotto da realizzare, il numero di ore di lavoro da allocare a ciascuna attività, etc.
Obiettivo: È la funzione da ottimizzare (massimizzare o minimizzare), che rappresenta il criterio di valutazione delle soluzioni. Definisce cosa si intende per "soluzione ottima".
- Esempio: Nel problema di produzione, l’obiettivo potrebbe essere la massimizzazione del profitto totale, la minimizzazione dei costi di produzione, la minimizzazione del tempo di completamento, etc.

Consideriamo un’azienda che produce prodotti di tipo A, B, e C.

Dati:
- Risorse disponibili (materie prime, ore di lavoro, capacità degli impianti).
- Costi di produzione unitari per ciascun prodotto.
- Domanda di mercato per ciascun prodotto.
Variabili:
- $x_A$: quantità di prodotti di tipo A da produrre.
- $x_B$: quantità di prodotti di tipo B da produrre.
- $x_C$: quantità di prodotti di tipo C da produrre.
Obiettivo: Massimizzare il profitto totale, che potrebbe essere espresso come: $Profitto = (PrezzoVendita_A * x_A - Costo_A * x_A) + (PrezzoVendita_B * x_B - Costo_B * x_B) + (PrezzoVendita_C * x_C - Costo_C * x_C)$.

Chiarire questi tre aspetti è fondamentale per costruire un modello matematico corretto ed efficace, che possa essere utilizzato per trovare la soluzione ottima del problema.

Modellazione del Problema

La modellazione del problema è il processo di traduzione della formalizzazione del problema in una rappresentazione matematica completa, che include la definizione delle variabili, dei vincoli e della funzione obiettivo.

Tipi di Variabili

Le variabili rappresentano le decisioni da prendere e possono essere di diverse tipologie, tra cui:

Variabili Booleane (o Binarie): Rappresentano decisioni di tipo sì/no, assumendo solo i valori 0 (no) o 1 (sì).
- Esempio: Aprire o meno un punto vendita in una determinata città (1 se si apre, 0 altrimenti).
- Esempio: Assegnare o meno un determinato compito a una specifica persona (1 se si assegna, 0 altrimenti).
Variabili Intere: Rappresentano quantità numeriche che possono assumere solo valori interi.
- Esempio: Numero di unità di un prodotto da produrre.
- Esempio: Numero di persone da assegnare a un team.
Variabili Continue: Rappresentano quantità numeriche che possono assumere qualsiasi valore all’interno di un determinato intervallo.
- Esempio: Quantità di una risorsa da utilizzare (e.g., litri di carburante, metri di tessuto).
- Esempio: Percentuale di un budget da allocare a un progetto.

Scelta delle Variabili

La scelta delle variabili è un passo cruciale nella modellazione. Spesso, lo stesso problema può essere rappresentato con diversi insiemi di variabili, portando a modelli con caratteristiche differenti in termini di complessità, numero di variabili e vincoli. La scelta delle variabili deve essere guidata dalla necessità di rappresentare in modo accurato le decisioni da prendere e di facilitare la formulazione dei vincoli e della funzione obiettivo.

Vincoli

I vincoli sono delle equazioni o disequazioni che limitano i valori che le variabili possono assumere. Servono a garantire che le soluzioni siano ammissibili, cioè che rispettino le specifiche e le limitazioni del problema reale.

Esempio: Se una variabile $x$ rappresenta il numero di prodotti da realizzare, un vincolo potrebbe essere $x \ge 0$, che indica che non è possibile produrre una quantità negativa di prodotti.
Esempio: Se una variabile $y_i$ rappresenta l’apertura (1) o la chiusura (0) di un impianto $i$, e si possono aprire al massimo 3 impianti, un vincolo potrebbe essere $\sum_{i=1}^n y_i \le 3$.
Esempio: Se le variabili $x_1$ e $x_2$ rappresentano le ore di lavoro dedicate a due attività, e il totale di ore disponibili è 40, un vincolo potrebbe essere $x_1 + x_2 \le 40$.

I vincoli sono essenziali per definire lo spazio delle soluzioni ammissibili. Senza vincoli, il modello potrebbe ammettere soluzioni che non hanno senso nel contesto reale del problema.

Una corretta definizione dei vincoli è fondamentale per ottenere un modello che rappresenti fedelmente la realtà e che permetta di trovare soluzioni ottime e applicabili.

Esempio: Problema del Commesso Viaggiatore (TSP)

Il problema del commesso viaggiatore (Traveling Salesman Problem, TSP) è un classico problema di ottimizzazione combinatoria che consiste nel trovare il percorso più breve che un commesso viaggiatore deve compiere per visitare un insieme di $n$ città, partendo e tornando alla città di partenza, e visitando ogni città esattamente una volta.

Formal Definition of the Traveling Salesman Problem (TSP): Given a complete graph $G = (V, E)$ with $V = \{1, 2, ..., n\}$ the set of nodes (cities) and $E$ the set of edges, and a cost function $c: E \rightarrow \mathbb{R}^+$ that associates with each edge $(i, j) \in E$ a cost $c_{ij}$ (distance between city $i$ and city $j$), the objective of the TSP is to find a Hamiltonian cycle (a path that visits each node exactly once and returns to the starting node) of minimum cost.

Mostreremo ora quattro possibili modelli matematici per il TSP, evidenziando come la scelta delle variabili e dei vincoli possa portare a formulazioni diverse dello stesso problema.

Modello 1: Città Successiva

In questo modello, le variabili decisionali indicano la città successiva a ciascuna città nel ciclo.

Variabili: $x_i$ rappresenta la città successiva alla città $i$ nel tour, per $i = 1, \dots, n$. Ogni $x_i$ può assumere un valore intero compreso tra 1 e $n$.
Vincoli:
- $x_i \in \{1, \dots, n\}$ per ogni $i = 1, \dots, n$ (ogni città deve avere una città successiva).
- $x_i \neq x_j$ per ogni $i \neq j$ (due città diverse non possono avere la stessa città successiva).
- $x_i \neq i$ per ogni $i$ (una città non può essere la successiva di se stessa).
- Vincoli aggiuntivi per evitare sotto-cicli (da approfondire in seguito). Questi vincoli sono necessari per garantire che la soluzione sia un unico ciclo hamiltoniano e non un insieme di cicli disgiunti.

Esempio: Per il tour 2-1-4-5-3-6, le variabili assumono i valori: $x_1 = 4, x_2 = 1, x_3 = 6, x_4 = 5, x_5 = 3, x_6 = 2$.

Modello 2: Posizione della Città

In questo modello, le variabili decisionali indicano la posizione di ciascuna città nel ciclo.

Variabili: $x_i$ rappresenta la posizione della città $i$ nel tour, per $i = 1, \dots, n$. Ogni $x_i$ può assumere un valore intero compreso tra 1 e $n$.
Vincoli:
- $x_i \in \{1, \dots, n\}$ per ogni $i = 1, \dots, n$ (ogni città deve avere una posizione nel tour).
- $x_i \neq x_j$ per ogni $i \neq j$ (due città diverse non possono avere la stessa posizione).

Esempio: Per il tour 2-1-4-5-3-6, le variabili assumono i valori: $x_1 = 2, x_2 = 1, x_3 = 5, x_4 = 3, x_5 = 4, x_6 = 6$.

Modello 3: Variabili Booleane per Coppie di Città

Questo modello utilizza variabili booleane per indicare se un arco tra due città è presente nel ciclo.

Variabili: $x_{ij}$ è una variabile booleana che vale 1 se si va dalla città $i$ alla città $j$ (cioè se l’arco $(i, j)$ è presente nel tour), 0 altrimenti, per $i, j = 1, \dots, n$, $i \neq j$.
Vincoli:
- $\sum_{j=1, j\neq i}^n x_{ij} = 1$ per ogni $i = 1, \dots, n$ (da ogni città si va a esattamente una città).
- $\sum_{i=1, i\neq j}^n x_{ij} = 1$ per ogni $j = 1, \dots, n$ (in ogni città si arriva da esattamente una città).
- Vincoli aggiuntivi per evitare sotto-cicli (da approfondire in seguito). Questi vincoli sono più complessi e richiedono un numero esponenziale di disequazioni, oppure l’introduzione di variabili aggiuntive.

Esempio: Per il tour 2-1-4-5-3-6, la matrice delle variabili avrà un 1 in posizione (2,1), (1,4), (4,5), (5,3), (3,6), (6,2) e 0 altrove.

Modello 4: Variabili Booleane per Permutazioni

Questo modello utilizza variabili booleane per indicare quale permutazione delle città (esclusa la città di partenza) viene scelta per il ciclo.

Variabili: $x_\pi$ è una variabile booleana che vale 1 se si sceglie la permutazione $\pi$ delle città $1, \dots, n-1$, 0 altrimenti. $S_{n-1}$ rappresenta l’insieme di tutte le possibili permutazioni di $n-1$ elementi.
Vincoli:
- $\sum_{\pi \in S_{n-1}} x_\pi = 1$ (si sceglie esattamente una permutazione).

Esempio: Per il tour 2-1-4-5-3-6, la variabile corrispondente alla permutazione $\pi = (2,1,4,5,3)$ vale 1 (cioè $x_{(2,1,4,5,3)} = 1$), tutte le altre variabili valgono 0.

Nota: Il numero di variabili in questo modello è $(n-1)!$, dove $n$ è il numero di città. Questo rende il modello impraticabile per valori di $n$ anche moderatamente grandi, a causa della crescita fattoriale del numero di variabili.

Confronto tra i modelli: I quattro modelli presentati differiscono per il numero di variabili e la complessità dei vincoli. I modelli 1 e 2 hanno $n$ variabili, il modello 3 ne ha $n(n-1)$, mentre il modello 4 ne ha $(n-1)!$. La scelta del modello migliore dipende da vari fattori, tra cui la dimensione del problema, la facilità di implementazione e l’efficienza degli algoritmi di risoluzione disponibili. I modelli 3 e 4, pur essendo più complessi, offrono una rappresentazione più diretta del problema e possono essere vantaggiosi in alcuni contesti.

Problemi di Ammissibilità

Nella modellazione di problemi di ottimizzazione, è fondamentale verificare l’**ammissibilità** del modello e delle sue istanze. Un modello o un’istanza non ammissibili indicano la presenza di errori o inconsistenze nella formulazione del problema.

Un modello si dice inammissibile (o infeasible) se non esiste alcuna soluzione che soddisfi tutti i vincoli, indipendentemente dai valori assunti dai dati del problema. In altre parole, l’insieme delle soluzioni ammissibili è vuoto a causa di vincoli contraddittori o eccessivamente stringenti.

Un’istanza di un problema si dice non ammissibile se, per quella specifica combinazione di valori dei dati, non esiste alcuna soluzione che soddisfi tutti i vincoli del modello. L’inammissibilità, in questo caso, non è intrinseca al modello, ma dipende dai valori specifici dei dati.

Consideriamo un modello con le variabili $x_3$ e $x_6$ e i seguenti vincoli: \[\begin{aligned} x_3 + x_6 &\ge 12 \\ x_3 + x_6 &\le 2 \end{aligned}\] Questo modello è inammissibile perché non esistono valori di $x_3$ e $x_6$ che possano soddisfare contemporaneamente entrambi i vincoli. La somma di $x_3$ e $x_6$ non può essere allo stesso tempo maggiore o uguale a 12 e minore o uguale a 2.

Consideriamo un modello con le variabili $x_3$ e $x_6$ e i seguenti vincoli: \[\begin{aligned} x_3 + x_6 &\ge A \\ x_3 + x_6 &\le B \end{aligned}\] dove $A$ e $B$ sono parametri che definiscono l’istanza del problema.

Se $A = 12$ e $B = 2$, l’istanza non è ammissibile per lo stesso motivo dell’esempio precedente.
Se $A = 5$ e $B = 20$, l’istanza è ammissibile perché esistono valori di $x_3$ e $x_6$ che soddisfano entrambi i vincoli (ad esempio, $x_3 = 10$ e $x_6 = 5$).

Questo esempio mostra come l’ammissibilità di un’istanza dipenda dai valori dei dati.

Supponiamo di voler modellare l’organizzazione dei turni in un pronto soccorso con le seguenti specifiche:

3 turni di 8 ore al giorno (copertura completa delle 24 ore).
Almeno 3 medici devono essere presenti per ogni turno.
Ogni medico può lavorare al massimo 1 turno al giorno.
Sono disponibili 8 medici in totale.

Questo problema, con il vincolo "ogni medico può lavorare al massimo 1 turno al giorno", è inammissibile.

Dimostrazione:

Nel primo turno, devono lavorare almeno 3 medici.
Nel secondo turno, devono lavorare almeno altri 3 medici, diversi dai primi 3 (per il vincolo di al massimo 1 turno al giorno per medico).
Dopo due turni, abbiamo impiegato almeno 6 medici.
Per il terzo turno, rimangono solo 2 medici disponibili (8 in totale - 6 già impiegati), il che non è sufficiente a soddisfare il requisito di "almeno 3 medici per turno".

Pertanto, non esiste una combinazione di turni che soddisfi tutti i vincoli contemporaneamente.

Conseguenze dell’inammissibilità:

Un modello inammissibile indica un errore nella formulazione del problema, che deve essere corretto rivedendo i vincoli.
Un’istanza non ammissibile indica che, per quei dati specifici, il problema non ha soluzione. In questo caso, si può riconsiderare il modello, rilassare alcuni vincoli o accettare che il problema non possa essere risolto con quei dati.

Rilevare l’inammissibilità è cruciale per evitare di sprecare tempo e risorse cercando di risolvere un problema che non ha soluzione.

Conclusion

In questa lezione, abbiamo esplorato il processo di formalizzazione e modellazione di problemi di ottimizzazione. Abbiamo imparato come un ricercatore operativo trasforma un problema reale, spesso espresso in modo informale e con dettagli ridondanti, in un modello matematico ben definito, identificando dati, variabili e obiettivo. Abbiamo analizzato diversi modelli per il problema del commesso viaggiatore (TSP), evidenziando come la scelta delle variabili influenzi la complessità del modello e il numero di vincoli necessari. Infine, abbiamo discusso i problemi di ammissibilità, distinguendo tra modelli infeasible (inammissibili) e istanze non ammissibili, e fornendo esempi pratici per illustrare questi concetti.

Domande e spunti di riflessione:

Come si può modificare il problema dei turni in pronto soccorso per renderlo ammissibile? (Suggerimento: rilassare il vincolo sul numero di turni per medico o aumentare il numero di medici disponibili).
Quali altri vincoli potrebbero essere aggiunti al modello 3 del TSP per garantire che la soluzione sia un circuito hamiltoniano e non un insieme di sotto-cicli disgiunti? (Suggerimento: vincoli di connessione o vincoli di eliminazione dei sotto-cicli).
Come si può gestire un modello con un numero esponenziale di variabili, come il modello 4 del TSP? (Suggerimento: tecniche di generazione di colonne o algoritmi specifici per il TSP).
Come influisce la scelta del modello sulla complessità computazionale della risoluzione del problema? (Suggerimento: numero di variabili e vincoli, struttura del problema).
Quali sono le implicazioni pratiche di un modello infeasible o di un’istanza non ammissibile? (Suggerimento: impossibilità di trovare una soluzione, necessità di rivedere il modello o i dati).

Nella prossima lezione, approfondiremo le tecniche per la risoluzione di problemi di ottimizzazione, con particolare attenzione agli algoritmi e alla loro complessità computazionale. Esamineremo come affrontare problemi di grandi dimensioni e come valutare l’efficienza delle diverse soluzioni algoritmiche.

--- title: "Modellazione di Problemi di Ottimizzazione" author: "Your Name" date: "2025-01-30" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction Questa lezione si concentra sul processo di formalizzazione e modellazione di problemi di ottimizzazione. L'obiettivo principale è quello di aiutare a comprendere come un ricercatore operativo affronta un problema pratico, traducendolo in un modello matematico risolvibile. ::: tcolorbox - Definizione di **problema** e **istanza**. - Ruolo del **ricercatore operativo** nel processo di ottimizzazione. - Formalizzazione del problema: identificazione di **dati**, **variabili**, e **obiettivo**. - Modellazione del problema: scelta delle **variabili** e definizione dei **vincoli**. - Esempi di modellazione del **problema del commesso viaggiatore (TSP)**. - Problemi di **ammissibilità**: modelli *infeasible* e istanze non ammissibili. - Esempi pratici di problemi di **ammissibilità**. ::: La lezione fornirà gli strumenti per comprendere come affrontare la modellazione di problemi complessi, trasformandoli in formulazioni matematiche trattabili e risolvibili mediante algoritmi di ottimizzazione. # Problemi, Istanze e Ruolo del Ricercatore Operativo ::: tcolorbox Un problema è una descrizione generale di una situazione che richiede di trovare una soluzione ottima, data una serie di requisiti e un obiettivo da ottimizzare. In altre parole, è la descrizione di un compito da svolgere, con specifici vincoli da rispettare e un criterio per valutare la qualità delle possibili soluzioni. ::: ::: tcolorbox Un'istanza di un problema è una specifica realizzazione del problema, ottenuta assegnando valori concreti ai dati del problema. Un'istanza è quindi un caso particolare del problema generale, con dati specifici che definiscono un contesto univoco. ::: ::: tcolorbox **Esempio:** - **Problema**: Organizzare il trasporto di merci da un magazzino a diversi negozi minimizzando i costi di trasporto. - **Istanza**: Trasportare 100 unità di prodotto A dal magazzino X al negozio Y, 50 unità di prodotto B dal magazzino X al negozio Z, e 70 unità di prodotto C dal magazzino X al negozio W, con costi di trasporto specifici per ogni tratta e tipo di prodotto. ::: ::: tcolorbox Il ruolo del ricercatore operativo è quello di assistere chi deve risolvere un problema pratico, aiutandolo a: 1. **Formalizzare il problema**: tradurre il problema, spesso espresso in linguaggio naturale e in modo informale, in un modello matematico ben definito. Questo implica identificare gli aspetti fondamentali del problema, rimuovendo dettagli irrilevanti o contraddittori, e definire chiaramente le relazioni tra i diversi elementi del problema. 2. **Studiare strumenti algoritmici**: identificare o sviluppare algoritmi appropriati per risolvere il problema formalizzato. Questo può richiedere l'adattamento di algoritmi esistenti o la creazione di nuovi algoritmi specifici per il problema in questione. L'obiettivo è trovare un metodo efficiente per ottenere una soluzione ottima o una buona approssimazione di essa. ::: In sintesi, il ricercatore operativo agisce come un \"traduttore\" tra il mondo reale e il mondo matematico, trasformando problemi complessi in modelli risolvibili e fornendo gli strumenti per trovare le soluzioni ottime. # Formalizzazione del Problema Per formalizzare un problema, è necessario identificare chiaramente tre elementi chiave: - **Dati**: Sono le informazioni note a priori, che costituiscono l'input del problema e non possono essere modificate dal decisore. Rappresentano le \"costanti\" del problema. - *Esempio*: In un problema di produzione, i dati potrebbero includere la disponibilità di materie prime, la capacità produttiva degli impianti, i costi unitari di produzione, la domanda di mercato per ciascun prodotto, etc. - **Variabili**: Sono le decisioni che devono essere prese per risolvere il problema. Rappresentano le \"incognite\" del problema, i valori che devono essere determinati per ottenere una soluzione. - *Esempio*: Nel problema di produzione, le variabili potrebbero rappresentare la quantità di ciascun prodotto da realizzare, il numero di ore di lavoro da allocare a ciascuna attività, etc. - **Obiettivo**: È la funzione da ottimizzare (massimizzare o minimizzare), che rappresenta il criterio di valutazione delle soluzioni. Definisce cosa si intende per \"soluzione ottima\". - *Esempio*: Nel problema di produzione, l'obiettivo potrebbe essere la massimizzazione del profitto totale, la minimizzazione dei costi di produzione, la minimizzazione del tempo di completamento, etc. ::: tcolorbox Consideriamo un'azienda che produce prodotti di tipo A, B, e C. - **Dati**: - Risorse disponibili (materie prime, ore di lavoro, capacità degli impianti). - Costi di produzione unitari per ciascun prodotto. - Domanda di mercato per ciascun prodotto. - **Variabili**: - $x_A$: quantità di prodotti di tipo A da produrre. - $x_B$: quantità di prodotti di tipo B da produrre. - $x_C$: quantità di prodotti di tipo C da produrre. - **Obiettivo**: Massimizzare il profitto totale, che potrebbe essere espresso come: $Profitto = (PrezzoVendita_A * x_A - Costo_A * x_A) + (PrezzoVendita_B * x_B - Costo_B * x_B) + (PrezzoVendita_C * x_C - Costo_C * x_C)$. ::: Chiarire questi tre aspetti è fondamentale per costruire un modello matematico corretto ed efficace, che possa essere utilizzato per trovare la soluzione ottima del problema. # Modellazione del Problema La modellazione del problema è il processo di traduzione della formalizzazione del problema in una rappresentazione matematica completa, che include la definizione delle variabili, dei vincoli e della funzione obiettivo. ## Tipi di Variabili Le variabili rappresentano le decisioni da prendere e possono essere di diverse tipologie, tra cui: - **Variabili Booleane (o Binarie)**: Rappresentano decisioni di tipo sì/no, assumendo solo i valori 0 (no) o 1 (sì). - *Esempio*: Aprire o meno un punto vendita in una determinata città (1 se si apre, 0 altrimenti). - *Esempio*: Assegnare o meno un determinato compito a una specifica persona (1 se si assegna, 0 altrimenti). - **Variabili Intere**: Rappresentano quantità numeriche che possono assumere solo valori interi. - *Esempio*: Numero di unità di un prodotto da produrre. - *Esempio*: Numero di persone da assegnare a un team. - **Variabili Continue**: Rappresentano quantità numeriche che possono assumere qualsiasi valore all'interno di un determinato intervallo. - *Esempio*: Quantità di una risorsa da utilizzare (e.g., litri di carburante, metri di tessuto). - *Esempio*: Percentuale di un budget da allocare a un progetto. ## Scelta delle Variabili La scelta delle variabili è un passo cruciale nella modellazione. Spesso, lo stesso problema può essere rappresentato con diversi insiemi di variabili, portando a modelli con caratteristiche differenti in termini di complessità, numero di variabili e vincoli. La scelta delle variabili deve essere guidata dalla necessità di rappresentare in modo accurato le decisioni da prendere e di facilitare la formulazione dei vincoli e della funzione obiettivo. ## Vincoli I vincoli sono delle equazioni o disequazioni che limitano i valori che le variabili possono assumere. Servono a garantire che le soluzioni siano ammissibili, cioè che rispettino le specifiche e le limitazioni del problema reale. - *Esempio*: Se una variabile $x$ rappresenta il numero di prodotti da realizzare, un vincolo potrebbe essere $x \ge 0$, che indica che non è possibile produrre una quantità negativa di prodotti. - *Esempio*: Se una variabile $y_i$ rappresenta l'apertura (1) o la chiusura (0) di un impianto $i$, e si possono aprire al massimo 3 impianti, un vincolo potrebbe essere $\sum_{i=1}^n y_i \le 3$. - *Esempio*: Se le variabili $x_1$ e $x_2$ rappresentano le ore di lavoro dedicate a due attività, e il totale di ore disponibili è 40, un vincolo potrebbe essere $x_1 + x_2 \le 40$. ::: tcolorbox I vincoli sono essenziali per definire lo spazio delle soluzioni ammissibili. Senza vincoli, il modello potrebbe ammettere soluzioni che non hanno senso nel contesto reale del problema. ::: Una corretta definizione dei vincoli è fondamentale per ottenere un modello che rappresenti fedelmente la realtà e che permetta di trovare soluzioni ottime e applicabili. # Esempio: Problema del Commesso Viaggiatore (TSP) Il problema del commesso viaggiatore (Traveling Salesman Problem, TSP) è un classico problema di ottimizzazione combinatoria che consiste nel trovare il percorso più breve che un commesso viaggiatore deve compiere per visitare un insieme di $n$ città, partendo e tornando alla città di partenza, e visitando ogni città esattamente una volta. ::: tcolorbox **Formal Definition of the Traveling Salesman Problem (TSP):** Given a complete graph $G = (V, E)$ with $V = \{1, 2, ..., n\}$ the set of nodes (cities) and $E$ the set of edges, and a cost function $c: E \rightarrow \mathbb{R}^+$ that associates with each edge $(i, j) \in E$ a cost $c_{ij}$ (distance between city $i$ and city $j$), the objective of the TSP is to find a Hamiltonian cycle (a path that visits each node exactly once and returns to the starting node) of minimum cost. ::: Mostreremo ora quattro possibili modelli matematici per il TSP, evidenziando come la scelta delle variabili e dei vincoli possa portare a formulazioni diverse dello stesso problema. ## Modello 1: Città Successiva In questo modello, le variabili decisionali indicano la città successiva a ciascuna città nel ciclo. - **Variabili**: $x_i$ rappresenta la città successiva alla città $i$ nel tour, per $i = 1, \dots, n$. Ogni $x_i$ può assumere un valore intero compreso tra 1 e $n$. - **Vincoli**: - $x_i \in \{1, \dots, n\}$ per ogni $i = 1, \dots, n$ (ogni città deve avere una città successiva). - $x_i \neq x_j$ per ogni $i \neq j$ (due città diverse non possono avere la stessa città successiva). - $x_i \neq i$ per ogni $i$ (una città non può essere la successiva di se stessa). - *Vincoli aggiuntivi per evitare sotto-cicli (da approfondire in seguito)*. Questi vincoli sono necessari per garantire che la soluzione sia un unico ciclo hamiltoniano e non un insieme di cicli disgiunti. **Esempio:** Per il tour 2-1-4-5-3-6, le variabili assumono i valori: $x_1 = 4, x_2 = 1, x_3 = 6, x_4 = 5, x_5 = 3, x_6 = 2$. ::: center ::: ## Modello 2: Posizione della Città In questo modello, le variabili decisionali indicano la posizione di ciascuna città nel ciclo. - **Variabili**: $x_i$ rappresenta la posizione della città $i$ nel tour, per $i = 1, \dots, n$. Ogni $x_i$ può assumere un valore intero compreso tra 1 e $n$. - **Vincoli**: - $x_i \in \{1, \dots, n\}$ per ogni $i = 1, \dots, n$ (ogni città deve avere una posizione nel tour). - $x_i \neq x_j$ per ogni $i \neq j$ (due città diverse non possono avere la stessa posizione). **Esempio:** Per il tour 2-1-4-5-3-6, le variabili assumono i valori: $x_1 = 2, x_2 = 1, x_3 = 5, x_4 = 3, x_5 = 4, x_6 = 6$. ::: center ::: ## Modello 3: Variabili Booleane per Coppie di Città Questo modello utilizza variabili booleane per indicare se un arco tra due città è presente nel ciclo. - **Variabili**: $x_{ij}$ è una variabile booleana che vale 1 se si va dalla città $i$ alla città $j$ (cioè se l'arco $(i, j)$ è presente nel tour), 0 altrimenti, per $i, j = 1, \dots, n$, $i \neq j$. - **Vincoli**: - $\sum_{j=1, j\neq i}^n x_{ij} = 1$ per ogni $i = 1, \dots, n$ (da ogni città si va a esattamente una città). - $\sum_{i=1, i\neq j}^n x_{ij} = 1$ per ogni $j = 1, \dots, n$ (in ogni città si arriva da esattamente una città). - *Vincoli aggiuntivi per evitare sotto-cicli (da approfondire in seguito)*. Questi vincoli sono più complessi e richiedono un numero esponenziale di disequazioni, oppure l'introduzione di variabili aggiuntive. **Esempio:** Per il tour 2-1-4-5-3-6, la matrice delle variabili avrà un 1 in posizione (2,1), (1,4), (4,5), (5,3), (3,6), (6,2) e 0 altrove. ::: center ::: ## Modello 4: Variabili Booleane per Permutazioni Questo modello utilizza variabili booleane per indicare quale permutazione delle città (esclusa la città di partenza) viene scelta per il ciclo. - **Variabili**: $x_\pi$ è una variabile booleana che vale 1 se si sceglie la permutazione $\pi$ delle città $1, \dots, n-1$, 0 altrimenti. $S_{n-1}$ rappresenta l'insieme di tutte le possibili permutazioni di $n-1$ elementi. - **Vincoli**: - $\sum_{\pi \in S_{n-1}} x_\pi = 1$ (si sceglie esattamente una permutazione). **Esempio:** Per il tour 2-1-4-5-3-6, la variabile corrispondente alla permutazione $\pi = (2,1,4,5,3)$ vale 1 (cioè $x_{(2,1,4,5,3)} = 1$), tutte le altre variabili valgono 0. ::: tcolorbox **Nota:** Il numero di variabili in questo modello è $(n-1)!$, dove $n$ è il numero di città. Questo rende il modello impraticabile per valori di $n$ anche moderatamente grandi, a causa della crescita fattoriale del numero di variabili. ::: **Confronto tra i modelli:** I quattro modelli presentati differiscono per il numero di variabili e la complessità dei vincoli. I modelli 1 e 2 hanno $n$ variabili, il modello 3 ne ha $n(n-1)$, mentre il modello 4 ne ha $(n-1)!$. La scelta del modello migliore dipende da vari fattori, tra cui la dimensione del problema, la facilità di implementazione e l'efficienza degli algoritmi di risoluzione disponibili. I modelli 3 e 4, pur essendo più complessi, offrono una rappresentazione più diretta del problema e possono essere vantaggiosi in alcuni contesti. # Problemi di Ammissibilità Nella modellazione di problemi di ottimizzazione, è fondamentale verificare l'\*\*ammissibilità\*\* del modello e delle sue istanze. Un modello o un'istanza non ammissibili indicano la presenza di errori o inconsistenze nella formulazione del problema. ::: tcolorbox Un modello si dice **inammissibile** (o *infeasible*) se non esiste alcuna soluzione che soddisfi tutti i vincoli, indipendentemente dai valori assunti dai dati del problema. In altre parole, l'insieme delle soluzioni ammissibili è vuoto a causa di vincoli contraddittori o eccessivamente stringenti. ::: ::: tcolorbox Un'istanza di un problema si dice **non ammissibile** se, per quella specifica combinazione di valori dei dati, non esiste alcuna soluzione che soddisfi tutti i vincoli del modello. L'inammissibilità, in questo caso, non è intrinseca al modello, ma dipende dai valori specifici dei dati. ::: ::: tcolorbox Consideriamo un modello con le variabili $x_3$ e $x_6$ e i seguenti vincoli: $$\begin{aligned} x_3 + x_6 &\ge 12 \\ x_3 + x_6 &\le 2 \end{aligned}$$ Questo modello è **inammissibile** perché non esistono valori di $x_3$ e $x_6$ che possano soddisfare contemporaneamente entrambi i vincoli. La somma di $x_3$ e $x_6$ non può essere allo stesso tempo maggiore o uguale a 12 e minore o uguale a 2. ::: ::: tcolorbox Consideriamo un modello con le variabili $x_3$ e $x_6$ e i seguenti vincoli: $$\begin{aligned} x_3 + x_6 &\ge A \\ x_3 + x_6 &\le B \end{aligned}$$ dove $A$ e $B$ sono parametri che definiscono l'istanza del problema. - Se $A = 12$ e $B = 2$, l'istanza **non è ammissibile** per lo stesso motivo dell'esempio precedente. - Se $A = 5$ e $B = 20$, l'istanza è **ammissibile** perché esistono valori di $x_3$ e $x_6$ che soddisfano entrambi i vincoli (ad esempio, $x_3 = 10$ e $x_6 = 5$). Questo esempio mostra come l'ammissibilità di un'istanza dipenda dai valori dei dati. ::: ::: tcolorbox Supponiamo di voler modellare l'organizzazione dei turni in un pronto soccorso con le seguenti specifiche: - 3 turni di 8 ore al giorno (copertura completa delle 24 ore). - Almeno 3 medici devono essere presenti per ogni turno. - Ogni medico può lavorare al massimo 1 turno al giorno. - Sono disponibili 8 medici in totale. Questo problema, con il vincolo \"ogni medico può lavorare al massimo 1 turno al giorno\", è **inammissibile**. **Dimostrazione:** 1. Nel primo turno, devono lavorare almeno 3 medici. 2. Nel secondo turno, devono lavorare almeno altri 3 medici, diversi dai primi 3 (per il vincolo di al massimo 1 turno al giorno per medico). 3. Dopo due turni, abbiamo impiegato almeno 6 medici. 4. Per il terzo turno, rimangono solo 2 medici disponibili (8 in totale - 6 già impiegati), il che non è sufficiente a soddisfare il requisito di \"almeno 3 medici per turno\". Pertanto, non esiste una combinazione di turni che soddisfi tutti i vincoli contemporaneamente. ::: **Conseguenze dell'inammissibilità:** - Un modello inammissibile indica un errore nella formulazione del problema, che deve essere corretto rivedendo i vincoli. - Un'istanza non ammissibile indica che, per quei dati specifici, il problema non ha soluzione. In questo caso, si può riconsiderare il modello, rilassare alcuni vincoli o accettare che il problema non possa essere risolto con quei dati. Rilevare l'inammissibilità è cruciale per evitare di sprecare tempo e risorse cercando di risolvere un problema che non ha soluzione. # Conclusion In questa lezione, abbiamo esplorato il processo di formalizzazione e modellazione di problemi di ottimizzazione. Abbiamo imparato come un ricercatore operativo trasforma un problema reale, spesso espresso in modo informale e con dettagli ridondanti, in un modello matematico ben definito, identificando **dati**, **variabili** e **obiettivo**. Abbiamo analizzato diversi modelli per il problema del commesso viaggiatore (TSP), evidenziando come la scelta delle variabili influenzi la complessità del modello e il numero di vincoli necessari. Infine, abbiamo discusso i problemi di **ammissibilità**, distinguendo tra modelli *infeasible* (inammissibili) e istanze non ammissibili, e fornendo esempi pratici per illustrare questi concetti. ::: tcolorbox **Domande e spunti di riflessione**: - Come si può modificare il problema dei turni in pronto soccorso per renderlo ammissibile? (Suggerimento: rilassare il vincolo sul numero di turni per medico o aumentare il numero di medici disponibili). - Quali altri vincoli potrebbero essere aggiunti al modello 3 del TSP per garantire che la soluzione sia un circuito hamiltoniano e non un insieme di sotto-cicli disgiunti? (Suggerimento: vincoli di connessione o vincoli di eliminazione dei sotto-cicli). - Come si può gestire un modello con un numero esponenziale di variabili, come il modello 4 del TSP? (Suggerimento: tecniche di generazione di colonne o algoritmi specifici per il TSP). - Come influisce la scelta del modello sulla complessità computazionale della risoluzione del problema? (Suggerimento: numero di variabili e vincoli, struttura del problema). - Quali sono le implicazioni pratiche di un modello *infeasible* o di un'istanza non ammissibile? (Suggerimento: impossibilità di trovare una soluzione, necessità di rivedere il modello o i dati). ::: ::: tcolorbox Nella prossima lezione, approfondiremo le tecniche per la risoluzione di problemi di ottimizzazione, con particolare attenzione agli algoritmi e alla loro complessità computazionale. Esamineremo come affrontare problemi di grandi dimensioni e come valutare l'efficienza delle diverse soluzioni algoritmiche. :::