Programmazione Lineare Intera
Una panoramica approfondita con formulazioni, formule e esempi matriciali
Principali Takeaways
- Definizione e formulazione: La programmazione lineare intera estende la programmazione lineare standard imponendo che alcune o tutte le variabili decisionali siano intere.
- Metodi di risoluzione: Tecniche come il Branch and Bound, i tagli di Gomory e metodi ibridi sono utilizzati per individuare soluzioni ottimali non frazionarie.
- Applicazioni pratiche: Questa metodologia è fondamentale per problemi reali come pianificazione della produzione, gestione delle risorse, problemi di assegnazione e scheduling.
Introduzione alla Programmazione Lineare Intera
La programmazione lineare intera (PLI) rappresenta una branca avanzata della ricerca operativa che si occupa di problemi di ottimizzazione in cui le variabili decisionali devono assumere valori interi. Diversamente dalla programmazione lineare classica, dove le variabili possono assumere valori continui, la PLI impone restrizioni di integralità che rendono il problema molto più complesso. Tale complessità deriva dal fatto che l'insieme delle soluzioni ammissibili non forma un poliedro liscio, ma un insieme discreto di punti, rendendo il problema NP-hard in molti casi.
Formulazione matematica
Un tipico problema di PLI può essere formalizzato come:
$$\begin{aligned} & \text{minimizzare (o massimizzare)}\quad c^T x\\[6pt] & \text{soggetto a} \quad Ax \geq b,\\[6pt] & \quad x \geq 0,\\[6pt] & \quad x \in \mathbb{Z}^n. \end{aligned}$$
Dove:
- c: vettore dei coefficienti della funzione obiettivo,
- x: vettore delle variabili decisionali,
- A: matrice dei coefficienti dei vincoli,
- b: vettore delle risorse o dei termini noti,
- \(\mathbb{Z}^n\): insieme delle soluzioni intere per le variabili.
Esempio Esplorativo con Matrici
Per illustrare concretamente la programmazione lineare intera, consideriamo un esempio pratico di un’azienda che produce due tipologie di prodotti, A (definito da \(x_1\)) e B (definito da \(x_2\)). L’obiettivo è massimizzare il profitto, tenendo conto delle restrizioni dovute alla capacità delle macchine disponibili.
Dati del problema
I dati relativi al problema sono i seguenti:
- Profitto per unità del prodotto A: 3 euro
- Profitto per unità del prodotto B: 5 euro
- Disponibilità oraria: 100 ore per la prima macchina e 80 ore per la seconda macchina
- Consumo orario:
- Prodotto A: 1 ora sulla prima macchina, 2 ore sulla seconda macchina
- Prodotto B: 2 ore sulla prima macchina, 1 ora sulla seconda macchina
- Vincoli di non negatività e integralità: \(x_1, x_2 \geq 0\) e \(x_1, x_2 \in \mathbb{Z}\)
Formulazione del problema
L’obiettivo è massimizzare il profitto totale, espresso dalla funzione:
$$\text{massimizzare } Z = 3x_1 + 5x_2$$
I vincoli sono:
$$\begin{aligned} x_1 + 2x_2 &\leq 100 \quad &\text{(Vincolo sulla prima macchina)}\\[6pt] 2x_1 + x_2 &\leq 80 \quad &\text{(Vincolo sulla seconda macchina)}\\[6pt] x_1, x_2 &\geq 0 \quad &\text{(Non negatività)}\\[6pt] x_1, x_2 &\in \mathbb{Z} \quad &\text{(Interezza)} \end{aligned}$$
Rappresentazione Matriciale
Possiamo rappresentare il problema in forma matriciale. Siano:
$$x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix},\quad c = \begin{pmatrix} 3 \\ 5 \end{pmatrix},\quad A = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix},\quad b = \begin{pmatrix} 100 \\ 80 \end{pmatrix}.$$
Quindi, il problema si esprime come:
$$\text{massimizzare } Z = c^T x$$
$$\text{soggetto a } Ax \leq b, \quad x \geq 0, \quad x \in \mathbb{Z}^2.$$
Soluzione del problema
Per trovare la soluzione ottimale, si potrebbe adottare un algoritmo specifico per la PLI, come il Branch and Bound o il metodo dei tagli di Gomory. Tuttavia, per semplicità, consideriamo il controllo manuale di alcune soluzioni ammissibili:
Caso 1
Supponiamo di provare la combinazione \(x_1 = 20\) e \(x_2 = 30\). Verifichiamo i vincoli:
- Primo vincolo: \(20 + 2(30) = 20 + 60 = 80 \leq 100\)
- Secondo vincolo: \(2(20) + 30 = 40 + 30 = 70 \leq 80\)
Il profitto calcolato è:
$$Z = 3(20) + 5(30) = 60 + 150 = 210\text{ euro}.$$
Caso 2
Supponiamo di provare \(x_1 = 30\) e \(x_2 = 20\). Verifichiamo i vincoli:
-
Primo vincolo: \(30 + 2(20) = 30 + 40 = 70 \leq 100\)
-
Secondo vincolo: \(2(30) + 20 = 60 + 20 = 80 \leq 80\)
Il profitto in questo caso è:
$$Z = 3(30) + 5(20) = 90 + 100 = 190\text{ euro}.$$
Tra le soluzioni esaminate, la combinazione \(x_1 = 20\) e \(x_2 = 30\) risulta ottimale con un profitto pari a 210 euro.
Metodi di Risoluzione della Programmazione Lineare Intera
Data la natura discreta dei problemi PLI, i metodi classici come il simplesso non sono direttamente applicabili. Di seguito vengono descritti alcuni metodi principali:
1. Branch and Bound
Questo è forse il metodo più comunemente utilizzato per la PLI. L’idea di base è di risolvere il problema rilassato, cioè quello dove il vincolo di integralità viene rimosso, ottenendo così una soluzione (generalmente frazionaria) per il problema lineare continuo. Successivamente, si crea una struttura ad albero in cui, ad ogni nodo, viene imposto un vincolo aggiuntivo per forzare una delle variabili a assumere un valore intero. Se una soluzione intera viene trovata e il valore della funzione obiettivo è migliore rispetto ai sottoproblemi ancora in fase di esplorazione, allora viene aggiornata la soluzione migliore. I rami che non possono produrre una soluzione migliore vengono potati per ridurre il tempo di calcolo.
2. Tagli di Gomory (Cutting Planes)
Questa tecnica parte dalla soluzione ottima del problema rilassato (in cui le variabili possono essere frazionarie) e introduce, iterativamente, nuovi vincoli che eliminano le soluzioni frazionarie, mantenendo però inalterata la soluzione ottima intera. I tagli di Gomory sono calcolati analizzando la parte frazionaria dei coefficienti nella soluzione di base e formulando nuove disuguaglianze, che vengono aggiunte al sistema dei vincoli.
3. Metodi Ibridi e Metaeuristiche
Per problemi di grande dimensione o particolarmente complessi vengono impiegati metodi ibridi, come il Branch and Cut, che combina il Branch and Bound con le Cutting Planes, oppure tecniche metaeuristiche (algoritmi genetici, ricerca tabù, ecc.) per ottenere soluzioni approssimate in tempi più brevi.
Approfondimento: Un Esercizio con Matrici e Tagli di Gomory
Vediamo un altro esercizio illustrativo che evidenzia sia la formulazione matriciale che l'applicazione di un metodo di taglio per raggiungere la soluzione intera ottimale.
Dati dell’Esercizio
Consideriamo il seguente problema:
$$\begin{aligned} \text{minimizzare} \quad & Z = c^T x = -x_1 - x_2\\[6pt] \text{soggetto a} \quad & x_1 + 2x_2 \leq 15,\\[6pt] & 3x_1 - x_2 \leq 6,\\[6pt] & x_1, x_2 \geq 0,\\[6pt] & x_1, x_2 \in \mathbb{Z}. \end{aligned}$$
Qui la funzione obiettivo è stata scelta in forma di minimizzazione, ma è facile trasformarla, se ad esempio si volesse massimizzare il profitto. L’obiettivo di questo esempio è mostrare come, a partire da una soluzione frazionaria, sia possibile applicare un taglio di Gomory per ottenere una soluzione intera.
Rappresentazione Matriciale
Possiamo rappresentare il problema con le seguenti matrici:
| Matrice A | Vincolo |
|---|---|
|
riga 1: x₁ + 2x₂ ≤ 15 |
|
Funzione obiettivo: Z = -x₁ - x₂ |
Risoluzione del Problema Rilassato
Innanzitutto, rimuoviamo il vincolo di integralità e risolviamo il problema in forma continua. Supponiamo che la soluzione ottima frazionaria ottenuta sia:
$$x_1^* = 4.5,\quad x_2^* = 3.25,\quad Z^* = -(4.5 + 3.25) = -7.75.$$
Notiamo che i valori trovati non sono interi. Per ottenere una soluzione valida per il problema PLI, dobbiamo escludere questa soluzione frazionaria.
Applicazione del Taglio di Gomory
L’idea è quella di aggiungere un vincolo supplementare che elimini la soluzione frazionaria ma che non escluda nessuna soluzione intera ammissibile. La procedura classica richiede:
- Identificare la riga della base in cui compare un valore frazionario.
- Scrivere la relazione corrispondente nel formato: $$x_B + \sum_{j \notin B} a_{ij} x_j = b_i,$$ dove \(b_i\) è frazionario.
- Formulare il taglio: $$\sum_{j \notin B} \{a_{ij}\} x_j \geq \{b_i\},$$ dove \(\{a_{ij}\}\) denota la parte frazionaria di \(a_{ij}\) e \(\{b_i\}\) quella di \(b_i\).
Supponiamo che, analizzando la soluzione, si identifichi un vincolo che, dopo opportune manipolazioni matriciali, fornisca il seguente taglio:
$$x_1 \leq 4$$
Questo nuovo vincolo, aggiunto al sistema originario, costringe la soluzione a cercare interi e, risolvendo nuovamente il problema rilassato, si ottiene ad esempio:
$$x_1 = 4,\quad x_2 = 3,\quad Z = -(4 + 3) = -7.$$
Questa nuova soluzione è intera e ammissibile e, verificando tutti i vincoli, risulta essere ottimale rispetto all’obiettivo del problema.
Considerazioni Finali e Conclusione
La programmazione lineare intera, pur disponendo di una formulazione simile a quella della programmazione lineare standard, introduce una complessità aggiuntiva derivante dal vincolo di integralità. Nei contesti reali, dove la discrepanza degli output è fondamentale – come il numero di prodotti da produrre, la quantità di risorse da assegnare o il numero di veicoli da utilizzare – le tecniche di PLI assumono una rilevanza strategica.
I principali metodi di soluzione, come il Branch and Bound e i tagli di Gomory, permettono di navigare attraverso lo spazio discreto delle soluzioni alla ricerca della soluzione ottimale. L’utilizzo di questi metodi richiede una profonda comprensione delle proprietà algebriche e dei sistemi di vincoli, e spesso viene supportato da software specializzati (ad esempio CPLEX, Gurobi, CBC) per problemi di grande scala.
In conclusione, la programmazione lineare intera offre strumenti teorici e pratici fondamentali per risolvere problemi ottimizzati in cui le variabili devono assumere valori discreti. Il rigore matematico nella formulazione—attraverso matrici e vettori—coniugato a metodi algoritmici sofisticati, rende questa disciplina un pilastro della ricerca operativa.
Riferimenti
Di seguito, l’elenco completo degli URL che contengono ulteriori approfondimenti e spiegazioni dettagliate:
Conclusioni
Abbiamo esplorato in dettaglio la programmazione lineare intera, analizzando la sua formulazione matematica, i metodi risolutivi e applicandola a un esercizio pratico con l’uso di matrici. La combinazione di rigorose tecniche algebriche e metodi algoritmici consente di applicare la PLI a una vasta gamma di problemi reali. Sebbene la complessità computazionale possa essere elevata in certi casi, la capacità di modellare in modo preciso scenari in cui le decisioni devono essere discrete rende questo strumento indispensabile in molti settori, dalla logistica alla pianificazione industriale.
Last updated February 17, 2025