Il problema dei trasporti è un modello speciale di programmazione lineare usato per decidere quante unità spedire da più origini a più destinazioni minimizzando il costo totale. È centrale in logistica, distribuzione, supply chain, pianificazione della produzione e allocazione di risorse perché conserva una struttura matematica molto regolare.
Formulazione
Si considerino m origini e n destinazioni. L’origine i ha offerta a_i, la destinazione j ha domanda b_j, e la rotta (i,j) ha costo unitario c_{ij}. La variabile decisionale è:
e rappresenta la quantità spedita dall’origine i alla destinazione j.
Il modello bilanciato è:
Il primo gruppo di vincoli impone che ogni origine spedisca tutta la propria offerta; il secondo che ogni destinazione riceva esattamente la propria domanda. Il modello è bilanciato quando:
Se offerta e domanda non coincidono, si aggiunge una origine o una destinazione fittizia. Se l’offerta totale supera la domanda, la destinazione fittizia assorbe l’eccedenza; se la domanda totale supera l’offerta, l’origine fittizia fornisce la quantità mancante. I costi fittizi vanno scelti in modo coerente con il significato operativo: costo nullo per eccedenza senza penalità, oppure costo di mancata consegna se la scarsità ha conseguenze economiche.
Struttura della base
Il problema dei trasporti ha m+n vincoli di uguaglianza, ma uno è ridondante: la somma dei vincoli sulle origini coincide con la somma dei vincoli sulle destinazioni quando il problema è bilanciato. Per questo una soluzione di base non degenere ha:
variabili di base. In tabella, queste variabili corrispondono alle celle occupate. Se una soluzione ammissibile ha meno di m+n-1 celle di base effettive, si parla di degenerazione: può essere necessario inserire una quantità nulla simbolica in una cella opportuna per mantenere la struttura della base e poter calcolare correttamente i potenziali.
La struttura è quella di un problema di ottimizzazione su reti: origini e destinazioni sono nodi, le rotte sono archi, le quantità sono flussi e i costi sono pesi sugli archi. La matrice dei vincoli è totalmente unimodulare; se offerte e domande sono intere, anche una soluzione estrema ottima può essere scelta intera senza imporre esplicitamente vincoli di integrità.
Soluzioni iniziali
Per avviare l’algoritmo serve una soluzione ammissibile iniziale. I metodi più comuni sono:
| Metodo | Idea | Pregio | Limite |
|---|---|---|---|
| angolo nord-ovest | riempire progressivamente la prima cella disponibile | molto rapido | ignora i costi |
| costo minimo | assegnare prima alle rotte più economiche | semplice e più sensibile ai costi | può essere miope |
| approssimazione di Vogel | usare penalità tra i costi migliori di righe e colonne | spesso produce buone basi iniziali | richiede più calcolo manuale |
Questi metodi non garantiscono in generale l’ottimo; servono a costruire una base ammissibile da migliorare.
Metodo dei potenziali
Il metodo dei potenziali, o metodo MODI, è una specializzazione del metodo del simplesso alla tabella dei trasporti. Per le celle di base si cercano potenziali u_i e v_j tali che:
Per le celle non di base si calcola il costo ridotto:
In minimizzazione, la condizione:
per tutte le celle non di base certifica l’ottimalità. Se esiste una cella con \Delta_{ij}\lt0, introdurre quella rotta può ridurre il costo totale. Si costruisce allora un ciclo chiuso alternando celle di base e la nuova cella, si aggiunge e sottrae una quantità lungo il ciclo, e si aggiorna la base mantenendo invariati i vincoli di offerta e domanda.
Dualità e interpretazione
I potenziali u_i e v_j sono variabili duali associate rispettivamente ai vincoli di offerta e domanda. La condizione u_i+v_j\le c_{ij} per le celle non di base dice che il valore marginale di origine e destinazione non deve superare il costo della rotta. Quando una rotta è usata in base, la condizione è attiva:
Questa lettura collega il problema alla dualità lineare e ai prezzi ombra: i potenziali misurano quanto cambierebbe il costo ottimo al variare di offerte, domande o costi unitari, entro l’intervallo di validità della base corrente.
Varianti e casi collegati
Il problema di assegnamento è un caso particolare del problema dei trasporti con offerte e domande unitarie. Se compaiono capacità sulle rotte, costi fissi di apertura, lotti minimi, divieti, priorità o più prodotti, il modello base va esteso: si passa a flussi a costo minimo, programmazione intera o modelli multi-commodity.
Nelle applicazioni reali bisogna curare bene la matrice dei costi. Un costo c_{ij} può includere trasporto, handling, ritardi, emissioni, rischio, dazi o penalità di servizio. Se il costo non rappresenta il compromesso operativo reale, il modello può produrre una soluzione matematicamente ottima ma logisticamente fragile.
Errori comuni
Gli errori più frequenti sono dimenticare il bilanciamento, contare m+n variabili di base invece di m+n-1, ignorare la degenerazione e applicare il criterio dei potenziali con segno sbagliato. Un altro errore è confondere il modello dei trasporti con un problema di percorso: qui si decide quanto spedire su tutte le rotte disponibili, non quale singolo cammino seguire in una rete.
Per esercizi collegati: problema dei trasporti e programmazione lineare. Vedi anche: formulario di ricerca operativa, ricerca operativa e ottimizzazione su reti.