Formulario completo di ricerca operativa per i corsi di ingegneria gestionale. Lo scopo è offrire un riferimento autosufficiente e ragionato che parta dalla programmazione lineare, sviluppi la dualità e i modelli classici (trasporti, scorte, code), e fornisca gli strumenti per modellare e risolvere problemi di ottimizzazione e decisione.
La ricerca operativa è la disciplina che usa modelli matematici per prendere decisioni ottime: come allocare risorse scarse, quanto produrre, come instradare, quando riordinare. Il suo metodo è sempre lo stesso: tradurre un problema reale in un modello (variabili, obiettivo, vincoli), risolverlo, interpretare il risultato. Ogni sezione spiega il significato delle formule e include esempi commentati.
Le grandezze sono adimensionali o in unità coerenti col problema. Si assume nota l’algebra lineare di base.
L’ordine consigliato è:
- programmazione lineare;
- forma standard e soluzioni;
- dualità;
- problema dei trasporti;
- gestione delle scorte (EOQ);
- teoria delle code;
- modelli decisionali.
Mappa di lettura operativa:
| Problema | Strumento principale | Controllo |
|---|---|---|
| ottimizzare con vincoli lineari | programmazione lineare | funzione e vincoli lineari |
| risolvere un PL | metodo del simplesso | forma standard |
| valore dei vincoli | problema duale | corrispondenza primale-duale |
| minimizzare costi di trasporto | modello dei trasporti | offerta = domanda |
| quanto ordinare | lotto economico EOQ | costi di ordine e mantenimento |
| dimensionare un servizio | teoria delle code | tasso di arrivo e servizio |
| decidere in incertezza | criteri decisionali | scenari e probabilità |
1. Programmazione lineare
Forma generale
La programmazione lineare (PL) è il modello di ottimizzazione più importante: ottimizza una funzione lineare soggetta a vincoli lineari:
dove x è il vettore delle variabili decisionali (cosa decidere), c i coefficienti dell’obiettivo (cosa massimizzare, es. il profitto), A e b i vincoli (risorse disponibili). La condizione x \ge 0 esprime che le quantità sono non negative. Modellare un problema reale come PL — individuare variabili, obiettivo e vincoli — è già metà del lavoro.
Regione ammissibile
L’insieme dei punti che soddisfano tutti i vincoli è la regione ammissibile, un poliedro convesso (intersezione di semispazi). Qui sta il risultato chiave che rende la PL trattabile: se esiste un ottimo, almeno un vertice del poliedro è ottimo. La ragione geometrica: una funzione lineare cresce in una direzione fissa, quindi il suo massimo su un poliedro si raggiunge sempre su un vertice (o su uno spigolo, ma allora anche su un vertice). Questo trasforma un problema continuo (infiniti punti) in uno finito: basta esaminare i vertici, non tutto l’interno.
2. Forma standard e soluzioni
Forma standard
Per applicare gli algoritmi si porta il PL in forma standard, con vincoli di uguaglianza, introducendo variabili di scarto (slack) che misurano la risorsa non usata:
Una disuguaglianza a^T x \le b diventa a^T x + s = b con s \ge 0: la variabile s “riempie” la distanza dal limite. Se s>0 il vincolo non è saturo; se s=0 è attivo (la risorsa è esaurita).
Metodo del simplesso
Il metodo del simplesso sfrutta il fatto che l’ottimo è su un vertice: invece di esaminarli tutti (sarebbero troppi), parte da un vertice e si sposta a quello adiacente che migliora di più l’obiettivo, ripetendo finché nessuno spostamento migliora — quello è l’ottimo. È come scalare una collina seguendo sempre il pendio più ripido lungo gli spigoli. Nel caso peggiore è esponenziale, ma in pratica trova l’ottimo in pochi passi, ed è efficientissimo. I metodi del punto interno (che attraversano l’interno del poliedro) offrono in più garanzie polinomiali, utili per problemi enormi.
3. Dualità
Problema duale
A ogni PL (primale) corrisponde un secondo problema, il duale, che guarda lo stesso problema dal punto di vista dei vincoli/risorse. Per un primale di massimizzazione:
| Primale (max) | Duale (min) |
|---|---|
| \max c^T x | \min b^T y |
| Ax \le b | A^T y \ge c |
| x \ge 0 | y \ge 0 |
Ogni vincolo del primale diventa una variabile del duale e viceversa: c’è una simmetria profonda.
Teorema della dualità e prezzi ombra
Il risultato centrale: i valori ottimi di primale e duale coincidono (dualità forte): c^T x^* = b^T y^*. Questo è utile sia per verificare una soluzione (i due valori devono combaciare) sia per risolvere il problema più facile dei due. Ma l’interpretazione più preziosa è economica: le variabili duali y sono i prezzi ombra delle risorse, ovvero di quanto migliorerebbe l’obiettivo se si avesse un’unità in più di quella risorsa. Un prezzo ombra alto segnala una risorsa “strozzante”, su cui conviene investire; un prezzo ombra nullo indica una risorsa abbondante (vincolo non attivo). È l’informazione che guida le decisioni gestionali, non solo il numero ottimo.
4. Problema dei trasporti
Modello
Il problema dei trasporti è un PL con struttura speciale: minimizzare il costo di spedire merce da m origini (offerta a_i) a n destinazioni (domanda b_j), dato il costo unitario c_{ij} da i a j:
I vincoli dicono: ogni origine spedisce tutta la sua offerta, ogni destinazione riceve tutta la sua domanda. Le variabili x_{ij} sono le quantità su ciascuna rotta.
Condizione di bilanciamento
Il problema ha soluzione “pulita” se è bilanciato, cioè se l’offerta totale uguaglia la domanda totale:
Se non lo è (più offerta che domanda o viceversa), si introduce un’origine o destinazione fittizia che assorbe l’eccesso a costo nullo, riportando il problema a forma bilanciata. La struttura particolare (matrice dei vincoli speciale) permette algoritmi dedicati (metodo del trasporto, dell’angolo nord-ovest, dei costi minimi) molto più efficienti del simplesso generale.
5. Gestione delle scorte (EOQ)
Lotto economico
Quanto ordinare a ogni riapprovvigionamento? Troppo spesso e poco → molti costi d’ordine; troppo di rado e tanto → molte scorte da mantenere. Il lotto economico (EOQ) trova il compromesso che minimizza il costo totale:
con D domanda annua, S costo per ordine, H costo di mantenimento unitario annuo. La formula nasce annullando la derivata del costo totale (somma di costo d’ordine \propto 1/Q e costo di mantenimento \propto Q): il minimo è dove le due componenti si bilanciano. La radice quadrata ha una conseguenza utile: per dimezzare il numero di ordini bisogna quadruplicare la domanda — l’EOQ cresce lentamente, quindi economie di scala modeste.
Costo totale e punto di riordino
All’ottimo, il costo d’ordine totale uguaglia quello di mantenimento (equilibrio simmetrico). Sapere quanto ordinare non basta: serve quando. Il punto di riordino è il livello di scorta che innesca un nuovo ordine, calcolato perché la scorta basti a coprire il tempo di approvvigionamento L:
con d domanda nell’unità di tempo. Si ordina quando la scorta scende a ROP, così la merce nuova arriva proprio quando la vecchia finisce. Con domanda incerta si aggiunge una scorta di sicurezza sopra il ROP, per assorbire i picchi.
6. Teoria delle code
Modello M/M/1
Le code (clienti a uno sportello, pacchetti in un router, pezzi a una macchina) si studiano con la teoria delle code. Il modello base M/M/1 assume arrivi e tempi di servizio esponenziali (casuali) e un singolo servente, caratterizzato dal tasso di arrivo \lambda e di servizio \mu. Il parametro chiave è il fattore di utilizzo:
che è la frazione di tempo in cui il servente è occupato. Condizione di stabilità: \rho < 1, cioè il servizio deve essere mediamente più veloce degli arrivi. Se \rho \ge 1 la coda cresce all’infinito.
Grandezze caratteristiche
Per il modello M/M/1 stabile:
| Grandezza | Formula |
|---|---|
| Numero medio nel sistema | L = \dfrac{\rho}{1-\rho} |
| Tempo medio nel sistema | W = \dfrac{1}{\mu - \lambda} |
| Numero medio in coda | L_q = \dfrac{\rho^2}{1-\rho} |
Il risultato più istruttivo è la divergenza per \rho \to 1: avvicinandosi alla saturazione, code e attese non crescono linearmente ma esplodono. A \rho = 0{,}9 ci sono in media 9 utenti nel sistema; a \rho = 0{,}99 ben 99. È il motivo per cui un sistema vicino al 100% di utilizzo è ingestibile: serve sempre un margine di capacità. Lega tutto la legge di Little L = \lambda W: il numero medio nel sistema è il prodotto del tasso di arrivo per il tempo medio di permanenza — relazione universale, valida per qualunque coda stabile.
7. Modelli decisionali
Criteri di decisione in incertezza
Quando l’esito di una scelta dipende da scenari futuri incerti, non esiste una decisione “giusta” assoluta: dipende dall’atteggiamento verso il rischio. I criteri principali:
| Criterio | Logica | Atteggiamento |
|---|---|---|
| Maximax | massimizza il guadagno migliore | ottimista |
| Maximin (Wald) | massimizza il guadagno peggiore | pessimista/prudente |
| Minimax regret | minimizza il rammarico massimo | avverso al rimpianto |
| Valore atteso | massimizza il guadagno medio | neutrale (con probabilità) |
Il maximin sceglie l’alternativa il cui caso peggiore è il meno cattivo (prudenza); il maximax punta al massimo guadagno possibile (azzardo); il minimax regret minimizza il rimpianto di aver scelto male a posteriori. Quale usare dipende dal contesto e dalla tolleranza al rischio.
Valore atteso
Quando agli scenari si possono assegnare probabilità, il criterio razionale è il valore atteso: si sceglie l’alternativa che massimizza la media dei guadagni pesata sulle probabilità:
con p_i probabilità dello scenario i e v_i il guadagno relativo. È ottimale quando le probabilità sono affidabili e la decisione si ripete molte volte (la media si realizza). Per decisioni uniche ad alto rischio, però, il solo valore atteso può ingannare (una scommessa col valore atteso positivo ma rovinosa se va male): in quei casi si considera anche la varianza o l’utilità del decisore. È la base della teoria delle decisioni e degli alberi decisionali.
Note d’uso ed errori comuni
- In programmazione lineare l’ottimo (se esiste) è sempre su un vertice: è ciò che rende il problema finito e il simplesso efficiente.
- Verificare sempre che il problema dei trasporti sia bilanciato prima di risolverlo; altrimenti aggiungere origine/destinazione fittizia.
- Nell’EOQ usare costi e domanda riferiti allo stesso periodo (di norma annuo); l’EOQ cresce con la radice della domanda.
- La teoria delle code M/M/1 richiede \rho < 1: avvicinandosi a 1 le attese divergono, serve margine di capacità.
- I prezzi ombra (variabili duali) valgono solo per variazioni limitate del vincolo: oltre un certo range cambiano.
- Il valore atteso è razionale per decisioni ripetute; per decisioni uniche ad alto rischio considerare anche la varianza.
- La legge di Little (L = \lambda W) vale per qualunque sistema di coda stabile, non solo M/M/1: è uno strumento generale.