Dal percorso migliore alla decisione migliore
Nel primo articolo della serie sull’algoritmo di Dijkstra e la Supply Chain siamo partiti da una domanda apparentemente semplice:
Qual è il percorso meno costoso per portare una merce da un punto A a un punto B?
La risposta ci ha portato nel mondo dei grafi, dei pesi sugli archi e degli algoritmi di cammino minimo.
Dijkstra, però, risolve solo una parte del problema logistico.
In una rete reale non basta sapere quale sia il percorso più economico.
Bisogna anche decidere:
- quanta merce inviare;
- da quale magazzino;
- verso quali clienti;
- come utilizzare capacità limitate;
- se conviene utilizzare un nodo intermedio;
- come rispettare i tempi di consegna;
- quanto costa mantenere la merce in magazzino;
- quali combinazioni di decisioni producono il costo complessivo minimo.
Il problema cambia quindi natura.
Non chiediamo più soltanto:
\boxed{\text{Qual è il percorso migliore?}}
[/math]
ma:
\boxed{\text{Qual è la combinazione migliore di decisioni?}}
[/math]
È qui che entrano in gioco programmazione lineare, problemi di trasporto e ottimizzazione vincolata.
In questa seconda parte costruiamo due esercizi progressivi.
Nel primo passeremo da Dijkstra a un problema di trasporto con capacità e transshipment.
Nel secondo aggiungeremo tempi di consegna e costi di stoccaggio, mostrando anche perché una soluzione ottenuta con una regola greedy non è automaticamente una soluzione ottima.
L’obiettivo non è soltanto ottenere un numero con Python.
È capire perché quel numero rappresenta una soluzione ottima e quali ipotesi rendono valida la modellazione.
Esercizio 3 — Ottimizzazione multi-magazzino con vincolo di capacità
Il problema
Una rete di distribuzione dispone di due magazzini:
- M1
- M2
e deve servire tre clienti:
- C1
- C2
- C3.
I costi diretti di trasporto sono:
| Da \ A | C1 | C2 | C3 |
|---|---|---|---|
| M1 | 3 € | 5 € | 7 € |
| M2 | 4 € | 2 € | 8 € |
Le capacità dei magazzini sono:
\begin{aligned}
M1 = 100
\end{aligned}
[/math]
\begin{aligned}
M2 = 80
\end{aligned}
[/math]
Le domande sono:
\begin{aligned}
C1 = 50
\end{aligned}
[/math]
\begin{aligned}
C2 = 60
\end{aligned}
[/math]
\begin{aligned}
C3 = 30
\end{aligned}
[/math]
La domanda complessiva è quindi:
\begin{aligned}
50 + 60 + 30 = 140
\end{aligned}
[/math]
mentre la capacità complessiva è:
\begin{aligned}
100 + 80 = 180.
\end{aligned}
[/math]
La capacità totale è sufficiente, ma non necessariamente dove serve.
Ed è proprio questa la difficoltà.
Il transshipment
Supponiamo inoltre che i clienti possano essere utilizzati come punti di transito.
I costi di transshipment sono:
| Da \ A | C1 | C2 | C3 |
|---|---|---|---|
| C1 | — | 1 € | 4 € |
| C2 | 3 € | — | 2 € |
| C3 | 2 € | 3 € | — |
Per esempio:
\begin{aligned}
M1 \rightarrow C1 \rightarrow C2
\end{aligned}
[/math]
costa:
\begin{aligned}
3 + 1 = 4\ \text{€/unità}.
\end{aligned}
[/math]
Questo è più economico del percorso diretto:
\begin{aligned}
M1 \rightarrow C2 = 5\ \text{€/unità}.
\end{aligned}
[/math]
Un’assunzione importante
In questo esercizio distinguiamo tra:
- domanda finale del cliente;
- flusso di transito attraverso il cliente.
Assumiamo inoltre che la capacità di transito dei clienti sia illimitata.
Questa è una semplificazione didattica.
La matrice dei costi che costruiremo rappresenta quindi il costo minimo per raggiungere la destinazione finale, dopo aver eventualmente utilizzato uno o più nodi intermedi.
Se volessimo invece modellare esplicitamente ogni singolo flusso attraverso C1, C2 e C3, dovremmo introdurre variabili per ogni arco della rete e costruire un vero problema di flusso a costo minimo.
Qui utilizziamo una versione ridotta, utile per collegare il problema dei cammini minimi alla programmazione lineare.
Step 1 — Costi diretti
Senza transshipment abbiamo:
| Da \ A | C1 | C2 | C3 |
|---|---|---|---|
| M1 | 3 | 5 | 7 |
| M2 | 4 | 2 | 8 |
Se scegliessimo sempre il percorso diretto più economico, avremmo:
- C1 ← M1: 3 €/unità;
- C2 ← M2: 2 €/unità;
- C3 ← M1: 7 €/unità.
Ma il transshipment può modificare queste convenienze.
Step 2 — Calcoliamo i costi minimi con transshipment
Possiamo ora applicare la logica del cammino minimo.
Da M1
Per C1:
\begin{aligned}
M1 \rightarrow C1 = 3
\end{aligned}
[/math]
Per C2:
\begin{aligned}
\min(5,\; 3+1) = 4
\end{aligned}
[/math]
quindi:
\begin{aligned}
M1 \rightarrow C1 \rightarrow C2
\end{aligned}
[/math]
è più conveniente del collegamento diretto.
Per C3:
\begin{aligned}
\min(7,\; 3+4,\; 3+1+2) = 6
\end{aligned}
[/math]
quindi il percorso migliore è:
\begin{aligned}
M1 \rightarrow C1 \rightarrow C2 \rightarrow C3
\end{aligned}
[/math]
con costo:
\begin{aligned}
3 + 1 + 2 = 6.
\end{aligned}
[/math]
Da M2
Per C1:
\begin{aligned}
M2 \rightarrow C1 = 4.
\end{aligned}
[/math]
Per C2:
\begin{aligned}
M2 \rightarrow C2 = 2.
\end{aligned}
[/math]
Per C3:
\begin{aligned}
\min(8,\; 4+4,\; 2+2) = 4.
\end{aligned}
[/math]
Il percorso migliore è quindi:
\begin{aligned}
M2 \rightarrow C2 \rightarrow C3.
\end{aligned}
[/math]
Otteniamo:
| Da \ A | C1 | C2 | C3 |
|---|---|---|---|
| M1 | 3 | 4 | 6 |
| M2 | 4 | 2 | 4 |
Questa matrice è il ponte concettuale tra Dijkstra e la programmazione lineare:
Dijkstra ci ha aiutato a trasformare una rete complessa in una matrice di costi minimi; l’ottimizzazione decide ora quanta quantità assegnare a ciascuna destinazione.
Step 3 — Formuliamo il problema di trasporto
Definiamo:
\begin{aligned}
x_{ij} = \text{quantità spedita dal magazzino } M_i \text{ al cliente } C_j.
\end{aligned}
[/math]
Le variabili sono quindi:
\begin{aligned}
x_{11}, x_{12}, x_{13}, x_{21}, x_{22}, x_{23}.
\end{aligned}
[/math]
La funzione obiettivo è:
\begin{aligned}
\min Z ={}& 3x_{11} + 4x_{12} + 6x_{13} \\
&+ 4x_{21} + 2x_{22} + 4x_{23}.
\end{aligned}
[/math]
Vincoli di capacità
Per M1:
\begin{aligned}
x_{11} + x_{12} + x_{13} \leq 100
\end{aligned}
[/math]
Per M2:
\begin{aligned}
x_{21} + x_{22} + x_{23} \leq 80.
\end{aligned}
[/math]
Vincoli di domanda
C1 deve ricevere esattamente 50 unità:
\begin{aligned}
x_{11} + x_{21} = 50
\end{aligned}
[/math]
C2:
\begin{aligned}
x_{12} + x_{22} = 60
\end{aligned}
[/math]
C3:
\begin{aligned}
x_{13} + x_{23} = 30.
\end{aligned}
[/math]
Infine:
\begin{aligned}
x_{ij} \geq 0.
\end{aligned}
[/math]
Abbiamo trasformato una rete logistica in un problema di programmazione lineare.
Step 4 — Una prima soluzione intuitiva
Partiamo dai percorsi più economici per ogni cliente.
| Cliente | Percorso migliore | Costo |
|---|---|---|
| C1 | M1 → C1 | 3 € |
| C2 | M2 → C2 | 2 € |
| C3 | M2 → C3 | 4 € |
Assegniamo quindi:
\begin{aligned}
C1: 50 \text{ unità da M1}
\end{aligned}
[/math]
\begin{aligned}
C2: 60 \text{ unità da M2}
\end{aligned}
[/math]
\begin{aligned}
C3: 30 \text{ unità da M2}.
\end{aligned}
[/math]
Il costo sarebbe:
\begin{aligned}
50(3) + 60(2) + 30(4) = 390.
\end{aligned}
[/math]
Sembra ottimo.
Ma controlliamo le capacità.
M1 utilizza:
\begin{aligned}
50 \leq 100
\end{aligned}
[/math]
mentre M2 utilizza:
\begin{aligned}
60 + 30 = 90 > 80.
\end{aligned}
[/math]
La soluzione è quindi inammissibile.
Questo è un passaggio fondamentale:
Una soluzione può essere localmente conveniente e contemporaneamente impossibile da realizzare.
Dobbiamo liberare almeno:
\begin{aligned}
90 – 80 = 10
\end{aligned}
[/math]
unità di capacità di M2.
Step 5 — Il costo marginale della capacità
Possiamo spostare 10 unità da M2 a M1.
Per C2:
\begin{aligned}
4 – 2 = 2\ \text{€/unità}.
\end{aligned}
[/math]
Per C3:
\begin{aligned}
6 – 4 = 2\ \text{€/unità}.
\end{aligned}
[/math]
I due spostamenti hanno quindi lo stesso costo marginale:
\boxed{2\ \text{€/unità}}.
[/math]
Per 10 unità:
\begin{aligned}
10(2) = 20\ \text{€}.
\end{aligned}
[/math]
Partendo dai 390 € della soluzione iniziale:
\begin{aligned}
390 + 20 = 410\ \text{€}.
\end{aligned}
[/math]
Possiamo ottenere almeno due soluzioni ottime.
Opzione A — Spostiamo 10 unità di C2
| Percorso | Quantità | Costo unitario | Subtotale |
|---|---|---|---|
| M1 → C1 | 50 | 3 € | 150 € |
| M1 → C2 | 10 | 4 € | 40 € |
| M2 → C2 | 50 | 2 € | 100 € |
| M2 → C3 | 30 | 4 € | 120 € |
| Totale | 140 | 410 € |
Capacità:
\begin{aligned}
M1 = 60 \leq 100
\end{aligned}
[/math]
\begin{aligned}
M2 = 80 \leq 80.
\end{aligned}
[/math]
Opzione B — Spostiamo 10 unità di C3
| Percorso | Quantità | Costo unitario | Subtotale |
|---|---|---|---|
| M1 → C1 | 50 | 3 € | 150 € |
| M2 → C2 | 60 | 2 € | 120 € |
| M1 → C3 | 10 | 6 € | 60 € |
| M2 → C3 | 20 | 4 € | 80 € |
| Totale | 140 | 410 € |
Anche in questo caso:
\begin{aligned}
M1 = 60
\end{aligned}
[/math]
e:
\begin{aligned}
M2 = 80.
\end{aligned}
[/math]
Quindi:
\boxed{Z^* = 410\ \text{€}}
[/math]
Step 6 — Perché esistono più soluzioni ottime?
Qui compare un concetto importante della programmazione lineare.
Le due soluzioni hanno lo stesso costo perché trasferire una unità da M2 a M1 per C2 oppure per C3 produce esattamente lo stesso aumento:
\begin{aligned}
+2\ \text{€/unità}.
\end{aligned}
[/math]
Non abbiamo quindi un’unica soluzione ottima.
Esiste una famiglia di allocazioni ottime ottenibile distribuendo opportunamente le 10 unità aggiuntive tra C2 e C3.
In questo caso gli estremi della famiglia comprendono le due soluzioni appena mostrate.
Dal punto di vista aziendale, questo può essere utile.
Quando più soluzioni hanno lo stesso costo, possiamo scegliere quella che offre:
- maggiore robustezza;
- meno movimentazioni;
- maggiore semplicità operativa;
- maggiore flessibilità;
- minore esposizione a un singolo nodo.
L’ottimizzazione non deve quindi necessariamente terminare con:
“abbiamo trovato il minimo”.
Può proseguire con:
“tra le soluzioni che hanno lo stesso costo, quale è operativamente migliore?”
Step 7 — Verifica dell’ottimalità con i costi ridotti
Possiamo ora fare un passo ulteriore.
Una soluzione ammissibile non è automaticamente ottima. Per dimostrare l’ottimalità possiamo utilizzare la formulazione duale e i costi ridotti.
Consideriamo l’Opzione B:
\begin{aligned}
x_{11} = 50,\quad x_{22} = 60,\quad x_{13} = 10,\quad x_{23} = 20.
\end{aligned}
[/math]
Il magazzino M1 non utilizza tutta la capacità:
\begin{aligned}
50 + 10 = 60 < 100.
\end{aligned}
[/math]
Questo dettaglio è importante.
La capacità di M1 non è scarsa nella soluzione considerata.
Possiamo scegliere:
\begin{aligned}
u_1 = 0.
\end{aligned}
[/math]
Per gli archi utilizzati valgono le condizioni:
\begin{aligned}
u_i + v_j = c_{ij}.
\end{aligned}
[/math]
Da M1 → C1:
\begin{aligned}
0 + v_1 = 3
\end{aligned}
[/math]
quindi:
\begin{aligned}
v_1 = 3.
\end{aligned}
[/math]
Da M1 → C3:
\begin{aligned}
0 + v_3 = 6
\end{aligned}
[/math]
quindi:
\begin{aligned}
v_3 = 6.
\end{aligned}
[/math]
Da M2 → C3:
\begin{aligned}
u_2 + 6 = 4
\end{aligned}
[/math]
quindi:
\begin{aligned}
u_2 = -2.
\end{aligned}
[/math]
Infine M2 → C2:
\begin{aligned}
-2 + v_2 = 2
\end{aligned}
[/math]
e quindi:
\begin{aligned}
v_2 = 4.
\end{aligned}
[/math]
Otteniamo:
\begin{aligned}
u_1 = 0,\qquad u_2 = -2
\end{aligned}
[/math]
e:
\begin{aligned}
v_1 = 3,\qquad v_2 = 4,\qquad v_3 = 6.
\end{aligned}
[/math]
Costi ridotti
Per un percorso non utilizzato:
\begin{aligned}
\bar c_{ij} = c_{ij} – (u_i + v_j).
\end{aligned}
[/math]
Per M1 → C2:
\begin{aligned}
\bar c_{12} = 4 – (0 + 4) = 0.
\end{aligned}
[/math]
Per M2 → C1:
\begin{aligned}
\bar c_{21} = 4 – (-2 + 3) = 3.
\end{aligned}
[/math]
Quindi:
\boxed{\bar c_{12} = 0}
[/math]
e:
\boxed{\bar c_{21} = 3}.
[/math]
Tutti i costi ridotti sono non negativi.
La soluzione è quindi ottima.
Il costo ridotto nullo di M1 → C2 spiega anche perché possiamo attivare quel percorso senza peggiorare il valore ottimo.
Una lettura manageriale della dualità
Il risultato contiene un’informazione interessante.
M1 ha ancora:
\begin{aligned}
100 – 60 = 40
\end{aligned}
[/math]
unità di capacità inutilizzata.
Il suo vincolo di capacità non è quindi scarso.
Il fatto che possiamo assumere:
\begin{aligned}
u_1 = 0
\end{aligned}
[/math]
riflette proprio questa situazione.
La dualità non è soltanto uno strumento matematico per dimostrare l’ottimo.
Può essere interpretata come una domanda manageriale:
Quanto migliorerebbe il risultato se avessi una unità aggiuntiva di una risorsa?
Se la risorsa non è realmente scarsa, il suo valore marginale è nullo.
Step 8 — Python con linprog
Ora lasciamo che il solver risolva il problema.
import numpy as np
from scipy.optimize import linprog
def risolvi_trasporto(costi, capacita, domande):
"""
Risolve un problema di trasporto lineare.
costi:
matrice n_magazzini x n_clienti
capacita:
capacità massima di ciascun magazzino
domande:
domanda esatta di ciascun cliente
"""
n_mag, n_cli = costi.shape
n_var = n_mag * n_cli
# Funzione obiettivo
c = costi.flatten()
# ---------------------------------------------------------
# Vincoli di capacità
# ---------------------------------------------------------
A_ub = np.zeros((n_mag, n_var))
for i in range(n_mag):
for j in range(n_cli):
A_ub[i, i * n_cli + j] = 1
b_ub = np.array(capacita, dtype=float)
# ---------------------------------------------------------
# Vincoli di domanda
# ---------------------------------------------------------
A_eq = np.zeros((n_cli, n_var))
for j in range(n_cli):
for i in range(n_mag):
A_eq[j, i * n_cli + j] = 1
b_eq = np.array(domande, dtype=float)
# ---------------------------------------------------------
# Risoluzione
# ---------------------------------------------------------
risultato = linprog(
c,
A_ub=A_ub,
b_ub=b_ub,
A_eq=A_eq,
b_eq=b_eq,
bounds=[(0, None)] * n_var,
method="highs"
)
if not risultato.success:
raise RuntimeError(risultato.message)
allocazione = risultato.x.reshape(n_mag, n_cli)
return allocazione, risultato.fun
# ============================================================
# DATI
# ============================================================
costi_effettivi = np.array([
[3, 4, 6],
[4, 2, 4]
], dtype=float)
capacita = [100, 80]
domande = [50, 60, 30]
allocazione, costo = risolvi_trasporto(
costi_effettivi,
capacita,
domande
)
print("Allocazione ottimale:")
print(allocazione)
print(f"\nCosto totale: {costo:.0f} €")
print("\nVerifica domanda:")
print(allocazione.sum(axis=0))
print("\nUtilizzo magazzini:")
print(allocazione.sum(axis=1))Una possibile uscita è:
Allocazione ottimale:
[[50. 0. 10.]
[ 0. 60. 20.]]
Costo totale: 410 €
Verifica domanda:
[50. 60. 30.]
Utilizzo magazzini:
[60. 80.]Il solver può però restituire un’altra soluzione appartenente alla stessa famiglia di ottimi.
Il punto importante non è che Python restituisca esattamente una particolare matrice.
Il punto è che:
\boxed{Z^* = 410\ \text{€}}
[/math]
e che i vincoli siano rispettati.
Una lezione importante: Dijkstra non è stato sostituito
A questo punto possiamo vedere meglio il collegamento con la prima parte.
Dijkstra risponde a:
\begin{aligned}
\text{Qual è il cammino minimo?}
\end{aligned}
[/math]
La programmazione lineare risponde a:
\begin{aligned}
\text{Come distribuisco le quantità lungo una rete rispettando i vincoli?}
\end{aligned}
[/math]
Sono problemi diversi, ma collegati.
Una possibile pipeline è:
\boxed{
\text{Grafo}
\rightarrow
\text{Cammini minimi}
\rightarrow
\text{Costi effettivi}
\rightarrow
\text{Ottimizzazione}
}
[/math]
Il vero salto concettuale è questo:
il percorso migliore per una singola unità non è necessariamente la soluzione migliore per l’intera rete.
Esercizio 4 — Supply Chain con vincoli di tempo e scorte
Passiamo ora a un problema più vicino a una supply chain reale.
Non dobbiamo più decidere soltanto:
quale magazzino utilizzo?
ma anche:
quanto mi costa arrivare entro una certa scadenza?
Testo del problema
Un’azienda manifatturiera deve rifornire due stabilimenti:
- S1;
- S2.
I componenti arrivano da tre fornitori:
- F1;
- F2;
- F3.
La merce può passare attraverso due magazzini intermedi:
- W1;
- W2.
La rete è descritta dalle seguenti tratte.
| Tratta | Costo €/unità | Tempo giorni |
|---|---|---|
| F1 → W1 | 10 | 2 |
| F1 → W2 | 15 | 1 |
| F2 → W1 | 8 | 3 |
| F2 → W2 | 12 | 2 |
| F3 → W1 | 12 | 1 |
| F3 → W2 | 9 | 2 |
| W1 → S1 | 5 | 2 |
| W1 → S2 | 7 | 3 |
| W2 → S1 | 6 | 2 |
| W2 → S2 | 4 | 1 |
Ogni fornitore può fornire al massimo:
\begin{aligned}
200
\end{aligned}
[/math]
unità.
Le domande sono:
\begin{aligned}
S1 = 150
\end{aligned}
[/math]
\begin{aligned}
S2 = 100.
\end{aligned}
[/math]
La consegna deve avvenire entro:
\begin{aligned}
T_{\max} = 5\ \text{giorni}.
\end{aligned}
[/math]
Assunzione sullo stoccaggio
Per rendere il problema deterministico assumiamo che:
- i fornitori spediscano al tempo 0;
- la merce che arriva in anticipo rispetto alla data di consegna prevista venga mantenuta in magazzino;
- la consegna finale avvenga al giorno 5;
- il costo di stoccaggio sia:
\begin{aligned}
1\ \text{€/unità/giorno}.
\end{aligned}
[/math]
Questa è una politica operativa assunta dal modello, non una proprietà necessaria di ogni supply chain reale.
Se fosse possibile ritardare la partenza dal fornitore senza costi aggiuntivi, il modello di stoccaggio dovrebbe essere formulato diversamente.
Step 1 — Generiamo tutti i percorsi
Ogni percorso ha la forma:
\begin{aligned}
F_i \rightarrow W_j \rightarrow S_k.
\end{aligned}
[/math]
Per ogni percorso calcoliamo:
\begin{aligned}
T = T_{FW} + T_{WS}
\end{aligned}
[/math]
e:
\begin{aligned}
C_{trasporto} = C_{FW} + C_{WS}.
\end{aligned}
[/math]
Se:
\begin{aligned}
T \leq 5
\end{aligned}
[/math]
il percorso è ammissibile.
Il costo di stoccaggio è:
\begin{aligned}
C_{stock} = 1 \cdot (5 – T).
\end{aligned}
[/math]
Quindi:
\begin{aligned}
C_{totale} = C_{trasporto} + C_{stock}.
\end{aligned}
[/math]
Step 2 — Tutti i percorsi ammissibili
| Percorso | Tempo | Trasporto | Stoccaggio | Costo totale |
|---|---|---|---|---|
| F1 → W1 → S1 | 4 | 15 | 1 | 16 |
| F1 → W1 → S2 | 5 | 17 | 0 | 17 |
| F1 → W2 → S1 | 3 | 21 | 2 | 23 |
| F1 → W2 → S2 | 2 | 19 | 3 | 22 |
| F2 → W1 → S1 | 5 | 13 | 0 | 13 |
| F2 → W1 → S2 | 6 | 15 | — | non ammissibile |
| F2 → W2 → S1 | 4 | 18 | 1 | 19 |
| F2 → W2 → S2 | 3 | 16 | 2 | 18 |
| F3 → W1 → S1 | 3 | 17 | 2 | 19 |
| F3 → W1 → S2 | 4 | 19 | 1 | 20 |
| F3 → W2 → S1 | 4 | 15 | 1 | 16 |
| F3 → W2 → S2 | 3 | 13 | 2 | 15 |
Soltanto:
\begin{aligned}
F2 \rightarrow W1 \rightarrow S2
\end{aligned}
[/math]
viene eliminato perché richiede:
\begin{aligned}
6 > 5
\end{aligned}
[/math]
giorni.
Step 3 — Il percorso più economico per ciascuno stabilimento
Per S1 il costo minimo è:
\begin{aligned}
F2 \rightarrow W1 \rightarrow S1 = 13\ \text{€/unità}.
\end{aligned}
[/math]
Per S2:
\begin{aligned}
F3 \rightarrow W2 \rightarrow S2 = 15\ \text{€/unità}.
\end{aligned}
[/math]
Sembrerebbe quindi sufficiente scegliere:
\begin{aligned}
150 \text{ unità da F2 a S1}
\end{aligned}
[/math]
e:
\begin{aligned}
100 \text{ unità da F3 a S2}.
\end{aligned}
[/math]
Controlliamo però le capacità.
F2 utilizza:
\begin{aligned}
150 \leq 200
\end{aligned}
[/math]
F3 utilizza:
\begin{aligned}
100 \leq 200.
\end{aligned}
[/math]
Non esiste quindi un conflitto.
La soluzione è ammissibile.
Step 4 — Perché qui il greedy funziona?
Questa domanda è importante.
Non dobbiamo concludere:
“Il greedy trova sempre la soluzione ottima nei problemi di supply chain.”
Non è vero.
In questo particolare esempio il greedy funziona perché le due destinazioni possono essere servite contemporaneamente dai rispettivi percorsi più economici senza competere per una risorsa scarsa.
Per S1 abbiamo:
\begin{aligned}
150 \times 13 = 1950.
\end{aligned}
[/math]
Per S2:
\begin{aligned}
100 \times 15 = 1500.
\end{aligned}
[/math]
La somma è:
\begin{aligned}
1950 + 1500 = 3450.
\end{aligned}
[/math]
Step 5 — Dimostrazione tramite bound inferiore
Possiamo dimostrare l’ottimalità senza enumerare tutte le possibili allocazioni.
Qualunque soluzione deve spendere almeno:
\begin{aligned}
13\ \text{€/unità}
\end{aligned}
[/math]
per ciascuna delle 150 unità destinate a S1.
Quindi:
\begin{aligned}
C_{S1} \geq 150(13) = 1950.
\end{aligned}
[/math]
Analogamente, ogni unità destinata a S2 costa almeno:
\begin{aligned}
15\ \text{€/unità}.
\end{aligned}
[/math]
Pertanto:
\begin{aligned}
C_{S2} \geq 100(15) = 1500.
\end{aligned}
[/math]
Il bound inferiore complessivo è:
\begin{aligned}
LB = 1950 + 1500 = 3450.
\end{aligned}
[/math]
Ma abbiamo trovato una soluzione che costa esattamente:
\begin{aligned}
3450.
\end{aligned}
[/math]
Quindi:
\boxed{Z^* = 3450\ \text{€}}
[/math]
perché una soluzione che raggiunge il bound inferiore non può essere migliorata.
Questa è una delle idee fondamentali dell’ottimizzazione:
trovare una soluzione non basta; dobbiamo anche avere un argomento che dimostri che non ne esiste una migliore.
Step 6 — Formuliamo il vero modello LP
A questo punto possiamo evitare qualsiasi algoritmo greedy e costruire un modello generale.
Definiamo una variabile per ogni percorso ammissibile:
\begin{aligned}
x_p = \text{quantità assegnata al percorso } p.
\end{aligned}
[/math]
La funzione obiettivo è:
\begin{aligned}
\min Z = \sum_p c_p x_p
\end{aligned}
[/math]
dove [math]c_p[/math] è il costo totale del percorso, comprensivo dello stoccaggio.
Vincolo S1
\begin{aligned}
\sum_{p \rightarrow S1} x_p = 150
\end{aligned}
[/math]
Vincolo S2
\begin{aligned}
\sum_{p \rightarrow S2} x_p = 100.
\end{aligned}
[/math]
Capacità dei fornitori
Per ogni fornitore:
\begin{aligned}
\sum_{p \text{ originati da } F_i} x_p \leq 200.
\end{aligned}
[/math]
Infine:
\begin{aligned}
x_p \geq 0.
\end{aligned}
[/math]
Questo modello è molto più importante del singolo esempio.
Se domani cambiano:
- le domande;
- i costi;
- i tempi;
- le capacità;
- il costo di stoccaggio;
non dobbiamo inventare una nuova regola decisionale.
Cambiamo i dati e risolviamo nuovamente il modello.
Step 7 — Python: formulazione LP generalizzabile
import itertools
import numpy as np
from scipy.optimize import linprog
# ============================================================
# DATI
# ============================================================
fornitori = ["F1", "F2", "F3"]
magazzini = ["W1", "W2"]
stabilimenti = ["S1", "S2"]
domande = {
"S1": 150,
"S2": 100
}
capacita = {
"F1": 200,
"F2": 200,
"F3": 200
}
costi = {
"F1": {"W1": 10, "W2": 15},
"F2": {"W1": 8, "W2": 12},
"F3": {"W1": 12, "W2": 9},
"W1": {"S1": 5, "S2": 7},
"W2": {"S1": 6, "S2": 4}
}
tempi = {
"F1": {"W1": 2, "W2": 1},
"F2": {"W1": 3, "W2": 2},
"F3": {"W1": 1, "W2": 2},
"W1": {"S1": 2, "S2": 3},
"W2": {"S1": 2, "S2": 1}
}
TEMPO_MAX = 5
COSTO_STOCK = 1
# ============================================================
# COSTRUZIONE DEI PERCORSI
# ============================================================
percorsi = []
for f, w, s in itertools.product(
fornitori,
magazzini,
stabilimenti
):
tempo = tempi[f][w] + tempi[w][s]
# Percorso non ammissibile
if tempo > TEMPO_MAX:
continue
costo_trasporto = costi[f][w] + costi[w][s]
giorni_stock = max(0, TEMPO_MAX - tempo)
costo_stock = COSTO_STOCK * giorni_stock
costo_totale = costo_trasporto + costo_stock
percorsi.append({
"fornitore": f,
"magazzino": w,
"stabilimento": s,
"nome": f"{f}→{w}→{s}",
"tempo": tempo,
"costo": costo_totale
})
# ============================================================
# FUNZIONE OBIETTIVO
# ============================================================
c = np.array([
p["costo"]
for p in percorsi
], dtype=float)
# ============================================================
# VINCOLI DI DOMANDA
# ============================================================
A_eq = []
b_eq = []
for s in stabilimenti:
riga = [
1 if p["stabilimento"] == s else 0
for p in percorsi
]
A_eq.append(riga)
b_eq.append(domande[s])
# ============================================================
# VINCOLI DI CAPACITÀ DEI FORNITORI
# ============================================================
A_ub = []
b_ub = []
for f in fornitori:
riga = [
1 if p["fornitore"] == f else 0
for p in percorsi
]
A_ub.append(riga)
b_ub.append(capacita[f])
# ============================================================
# RISOLUZIONE LP
# ============================================================
risultato = linprog(
c=c,
A_ub=np.array(A_ub),
b_ub=np.array(b_ub),
A_eq=np.array(A_eq),
b_eq=np.array(b_eq),
bounds=[(0, None)] * len(percorsi),
method="highs"
)
if not risultato.success:
raise RuntimeError(
f"Ottimizzazione fallita: {risultato.message}"
)
# ============================================================
# OUTPUT
# ============================================================
print("=" * 60)
print("SOLUZIONE OTTIMALE")
print("=" * 60)
for p, x in zip(percorsi, risultato.x):
if x > 1e-8:
print(
f"{p['nome']:18s} "
f"{x:6.0f} unità × "
f"{p['costo']:5.0f} € = "
f"{x * p['costo']:7.0f} €"
)
print("-" * 60)
print(
f"COSTO TOTALE: {risultato.fun:.0f} €"
)L’output atteso è:
============================================================
SOLUZIONE OTTIMALE
============================================================
F2→W1→S1 150 unità × 13 € = 1950 €
F3→W2→S2 100 unità × 15 € = 1500 €
------------------------------------------------------------
COSTO TOTALE: 3450 €Il solver potrebbe teoricamente restituire un’altra soluzione nel caso di ottimi multipli. Ciò che conta è il valore della funzione obiettivo e il rispetto dei vincoli.
Step 8 — Un confronto interessante: cosa succede se F2 ha capacità 100?
Ora possiamo modificare un solo parametro:
\begin{aligned}
cap(F2) = 100.
\end{aligned}
[/math]
Il percorso più economico verso S1 è ancora:
\begin{aligned}
F2 \rightarrow W1 \rightarrow S1
\end{aligned}
[/math]
ma F2 non può più fornire tutte le 150 unità.
Possiamo assegnare:
\begin{aligned}
100
\end{aligned}
[/math]
unità a F2.
Restano:
\begin{aligned}
150 – 100 = 50
\end{aligned}
[/math]
unità di S1 da soddisfare.
Il percorso successivo più economico è:
\begin{aligned}
F1 \rightarrow W1 \rightarrow S1
\end{aligned}
[/math]
con costo:
\begin{aligned}
16\ \text{€/unità}.
\end{aligned}
[/math]
Per S2 possiamo continuare a utilizzare:
\begin{aligned}
F3 \rightarrow W2 \rightarrow S2
\end{aligned}
[/math]
a:
\begin{aligned}
15\ \text{€/unità}.
\end{aligned}
[/math]
Otteniamo:
| Percorso | Quantità | Costo | Subtotale |
|---|---|---|---|
| F2 → W1 → S1 | 100 | 13 € | 1.300 € |
| F1 → W1 → S1 | 50 | 16 € | 800 € |
| F3 → W2 → S2 | 100 | 15 € | 1.500 € |
| Totale | 250 | 3.600 € |
Quindi:
\boxed{Z^* = 3600\ \text{€}}
[/math]
in questo scenario.
Il costo aumenta di:
\begin{aligned}
3600 – 3450 = 150\ \text{€}.
\end{aligned}
[/math]
Una riduzione della capacità di F2 di 100 unità non genera quindi un costo di 100 volte qualcosa in modo automatico: il costo dipende da quali percorsi alternativi diventano necessari.
Step 9 — E se il tempo massimo diventasse 4 giorni?
Ora poniamo:
\begin{aligned}
T_{\max} = 4.
\end{aligned}
[/math]
Diventano inammissibili i percorsi che richiedono più di quattro giorni.
Tra questi c’è:
\begin{aligned}
F2 \rightarrow W1 \rightarrow S1
\end{aligned}
[/math]
che richiede esattamente:
\begin{aligned}
5\ \text{giorni}.
\end{aligned}
[/math]
Per S1 rimangono, tra gli altri:
\begin{aligned}
F1 \rightarrow W1 \rightarrow S1 = 16
\end{aligned}
[/math]
e:
\begin{aligned}
F3 \rightarrow W2 \rightarrow S1 = 16.
\end{aligned}
[/math]
Possiamo quindi assegnare 150 unità a F1 → W1 → S1.
Per S2 il percorso:
\begin{aligned}
F3 \rightarrow W2 \rightarrow S2
\end{aligned}
[/math]
rimane disponibile a 15 €/unità.
La soluzione diventa:
| Stabilimento | Percorso | Quantità | Costo | Subtotale |
|---|---|---|---|---|
| S1 | F1 → W1 → S1 | 150 | 16 € | 2.400 € |
| S2 | F3 → W2 → S2 | 100 | 15 € | 1.500 € |
| Totale | 250 | 3.900 € |
Quindi:
\boxed{Z^* = 3900\ \text{€}}
[/math]
contro i 3450 € dello scenario originale.
Un solo giorno in meno nella finestra temporale provoca:
\begin{aligned}
3900 – 3450 = 450\ \text{€}
\end{aligned}
[/math]
di costo aggiuntivo.
Questo è un esempio semplice di valore economico di un vincolo operativo.
Step 10 — E se il costo di stoccaggio fosse zero?
Poniamo:
\begin{aligned}
C_{stock} = 0.
\end{aligned}
[/math]
I costi diventano semplicemente i costi di trasporto.
Per esempio:
\begin{aligned}
F3 \rightarrow W2 \rightarrow S2
\end{aligned}
[/math]
passa da:
\begin{aligned}
15
\end{aligned}
[/math]
a:
\begin{aligned}
13\ \text{€/unità}.
\end{aligned}
[/math]
Anche:
\begin{aligned}
F1 \rightarrow W2 \rightarrow S2
\end{aligned}
[/math]
passa da:
\begin{aligned}
22
\end{aligned}
[/math]
a:
\begin{aligned}
19\ \text{€/unità}.
\end{aligned}
[/math]
Il ranking dei percorsi cambia.
Tuttavia, in questo specifico problema la soluzione ottima non cambia, perché i percorsi che già soddisfacevano le domande al costo minimo restano sufficientemente convenienti e non esistono conflitti di capacità che rendano necessario utilizzare un’alternativa.
Questo è un punto importante:
Cambiare un parametro del modello non implica necessariamente cambiare la soluzione ottima.
Dipende dalla posizione della soluzione rispetto agli altri percorsi e ai vincoli.
Greedy o Linear Programming?
I due esercizi permettono di chiarire una distinzione importante.
Il greedy può essere molto efficace quando il problema possiede una struttura favorevole.
Ma una supply chain reale può contenere contemporaneamente:
- capacità condivise;
- vincoli temporali;
- costi fissi;
- costi variabili;
- transshipment;
- minimi d’ordine;
- priorità;
- livelli di servizio;
- più periodi temporali.
In questi casi una regola come:
“scegli sempre il percorso più economico”
può fallire.
La programmazione lineare ha invece una struttura diversa:
\boxed{
\text{variabili}
+
\text{vincoli}
+
\text{funzione obiettivo}
}
[/math]
e lascia al solver il compito di cercare la combinazione migliore.
Dal percorso alla decisione
I due esercizi mostrano una progressione precisa.
Livello 1 — Grafo
Abbiamo nodi e archi:
\begin{aligned}
G = (V, E).
\end{aligned}
[/math]
Livello 2 — Cammino minimo
Cerchiamo:
\begin{aligned}
\min \sum_{e \in P} c_e.
\end{aligned}
[/math]
È il territorio di Dijkstra.
Livello 3 — Allocazione
Introduciamo quantità:
\begin{aligned}
x_{ij}.
\end{aligned}
[/math]
Ora non basta più trovare un percorso.
Dobbiamo decidere quanto flusso assegnare.
Livello 4 — Vincoli
Aggiungiamo:
\begin{aligned}
capacità,
\end{aligned}
[/math]
\begin{aligned}
domanda,
\end{aligned}
[/math]
\begin{aligned}
tempo,
\end{aligned}
[/math]
\begin{aligned}
stoccaggio.
\end{aligned}
[/math]
Il problema diventa:
\boxed{
\min f(x)
\quad
\text{soggetto a vincoli}
}
[/math]
Questa è la logica fondamentale della programmazione lineare.
Mini Quiz di consolidamento
Domanda 1
Nell’Esercizio 3, perché non possiamo semplicemente assegnare ogni cliente al magazzino con il costo unitario più basso?
A. Perché Dijkstra non funziona con tre clienti.
B. Perché M2 avrebbe una capacità insufficiente.
C. Perché il costo di M1 è sempre maggiore.
D. Perché i clienti non possono essere serviti contemporaneamente.
Domanda 2
Nell’Esercizio 3, perché esistono più soluzioni ottime?
A. Perché il solver introduce casualità.
B. Perché M1 e M2 hanno la stessa capacità.
C. Perché esiste una direzione di riallocazione con costo marginale nullo.
D. Perché tutte le variabili sono intere.
Domanda 3
Se il costo ridotto di un percorso non utilizzato fosse negativo, cosa indicherebbe?
A. La soluzione è sicuramente ottima.
B. Esiste una direzione di miglioramento: la soluzione corrente non è ottima.
C. Il percorso deve essere eliminato.
D. La domanda è insufficiente.
Domanda 4
Nell’Esercizio 4, perché il greedy funziona nello scenario originale?
A. Perché il greedy è sempre ottimo nei problemi logistici.
B. Perché non esistono capacità.
C. Perché i percorsi minimi per S1 e S2 possono essere utilizzati simultaneamente senza conflitti di capacità.
D. Perché i costi di stoccaggio sono tutti uguali.
Domanda 5
Se il tempo massimo passa da 5 a 4 giorni, perché il costo aumenta?
A. Perché aumenta automaticamente il costo di trasporto.
B. Perché alcuni percorsi diventano inammissibili e possono essere necessari percorsi più costosi.
C. Perché diminuisce la domanda.
D. Perché aumenta la capacità dei fornitori.
Risposte
R1 — B
La soluzione intuitiva utilizza 90 unità di M2:
\begin{aligned}
60 + 30 = 90
\end{aligned}
[/math]
ma M2 dispone soltanto di 80 unità.
La soluzione localmente migliore è quindi inammissibile.
R2 — C
Il costo marginale dello spostamento M2 → M1 è:
\begin{aligned}
4 – 2 = 2
\end{aligned}
[/math]
per C2 e:
\begin{aligned}
6 – 4 = 2
\end{aligned}
[/math]
per C3.
Le due alternative hanno quindi lo stesso costo marginale.
Questo genera una famiglia di soluzioni ottime.
R3 — B
Un costo ridotto negativo segnala che esiste una direzione ammissibile lungo la quale la funzione obiettivo può diminuire.
La soluzione corrente non è quindi ottima.
R4 — C
Il greedy funziona in questo particolare scenario perché i due percorsi più economici utilizzano fornitori diversi e ciascun fornitore ha capacità sufficiente.
Non è una proprietà generale dei problemi di supply chain.
R5 — B
Riducendo il limite temporale, alcuni percorsi vengono eliminati.
Nel nostro caso:
\begin{aligned}
F2 \rightarrow W1 \rightarrow S1
\end{aligned}
[/math]
passa da percorso ottimale a percorso inammissibile.
La domanda deve quindi essere soddisfatta attraverso alternative più costose.
Lezione finale
La prima parte della serie ci aveva insegnato a cercare il percorso migliore.
Questa seconda parte introduce una domanda più difficile:
Come trasformiamo i percorsi disponibili in una decisione complessiva, quando esistono risorse limitate e vincoli operativi?
La risposta passa dalla programmazione lineare.
Il salto concettuale può essere riassunto così:
\boxed{
\text{Dijkstra}
\rightarrow
\text{cammino minimo}
\rightarrow
\text{costi effettivi}
\rightarrow
\text{allocazione}
\rightarrow
\text{vincoli}
\rightarrow
\text{ottimizzazione}
}
[/math]
E c’è una lezione ancora più importante.
Un algoritmo non è una decisione.
Dijkstra può dirci quale percorso è più conveniente.
Un modello di ottimizzazione può dirci come combinare molti percorsi, rispettando capacità, domanda e vincoli.
Ma anche una soluzione matematicamente ottima dipende dalle ipotesi con cui abbiamo costruito il modello.
Se cambiano:
- i costi;
- le capacità;
- i tempi;
- la domanda;
- le regole di transshipment;
- i costi di stoccaggio;
può cambiare anche la decisione.
È per questo che nella Data Science applicata alla supply chain non basta conoscere un algoritmo.
Bisogna saper costruire il modello del problema, verificare le sue ipotesi e interpretare il risultato.
Nella prossima parte il problema può diventare ancora più interessante: cosa succede quando i costi, la domanda o i tempi non sono più certi?
A quel punto non dovremo più ottimizzare soltanto una rete.
Dovremo iniziare a decidere sotto incertezza.
📚 Dijkstra, cammini minimi e strutture dati in Python
Trovare il percorso più breve in una rete è un problema fondamentale dell’algoritmica, con applicazioni che spaziano dalla logistica ai trasporti, dalle reti informatiche alla data science. Questi approfondimenti collegano la teoria dei grafi all’algoritmo di Dijkstra, alla programmazione lineare e alle strutture dati necessarie per ottenere implementazioni efficienti in Python:
👉Algoritmo di Dijkstra: trovare il cammino più breve con Python
👉Cammini minimi: Dijkstra e programmazione lineare su un grafo orientato
👉heapq in Python: code con priorità, heap binari e prestazioni
Related Posts:
