Problema dei trasporti: esercizi svolti

Il problema dei trasporti distribuisce un bene da più origini (con offerta) a più destinazioni (con domanda) minimizzando il costo totale di trasporto. È una PL con struttura speciale, risolvibile con metodi dedicati più efficienti del simplesso generale. Questa scheda allena bilanciamento, soluzioni iniziali e il caso particolare dell’assegnazione.

1. Bilanciamento del problema

Esercizio. Tre origini con offerte $20,30,25$ ; tre destinazioni con domande $10,40,15$ . Il problema è bilanciato?

Si confrontano offerta e domanda totali:

$\sum\text{offerta}=20+30+25=75,\qquad \sum\text{domanda}=10+40+15=65.$

Offerta ( $75$ ) $>$ domanda ( $65$ ): problema sbilanciato. Si aggiunge una destinazione fittizia con domanda $75-65=10$ e costi nulli, per assorbire l’eccedenza. Il bilanciamento è il prerequisito dei metodi risolutivi.

2. Soluzione iniziale: angolo nord-ovest

Esercizio. Costruire una soluzione iniziale con il metodo dell’angolo nord-ovest per offerte $(O_1=30,O_2=20)$ e domande $(D_1=25,D_2=25)$ .

Si parte dalla cella in alto a sinistra e si soddisfa il massimo possibile, scorrendo:

$(O_1,D_1)$ : $\min(30,25)=25$ → $D_1$ esaurita, resta $O_1=5$ ;
$(O_1,D_2)$ : $\min(5,25)=5$ → $O_1$ esaurita, resta $D_2=20$ ;
$(O_2,D_2)$ : $\min(20,20)=20$ → completato.

Allocazioni: $25,5,20$ . Il nord-ovest è rapido ma ignora i costi: dà solo un punto di partenza ammissibile da migliorare.

3. Soluzione iniziale a costo minimo

Esercizio. Spiegare il vantaggio del metodo del costo minimo rispetto al nord-ovest.

Il metodo del costo minimo alloca per prima la cella con il costo unitario più basso, poi la successiva più economica, rispettando offerte e domande residue.

A differenza del nord-ovest, tiene conto dei costi: la soluzione iniziale è in genere molto più vicina all’ottimo, riducendo le iterazioni successive. Il prezzo è qualche confronto in più nella scelta delle celle.

4. Numero di celle base

Esercizio. Per un problema di trasporti $m\times n$ bilanciato, quante celle base (allocazioni non nulle) deve avere una soluzione di base?

Una soluzione di base ammissibile ha esattamente:

$\text{celle base}=m+n-1.$

Per un $3\times3$ : $3+3-1=5$ celle. Se sono meno, la soluzione è degenere e va completata con un’allocazione fittizia (zero) per applicare i metodi di ottimizzazione (es. stepping-stone, MODI).

5. Verifica di ottimalità (potenziali)

Esercizio. Su quale criterio si basa l’ottimalità nel metodo dei potenziali (MODI)?

Si calcolano i potenziali $u_i$ (righe) e $v_j$ (colonne) imponendo $u_i+v_j=c_{ij}$ sulle celle base. Poi, per ogni cella fuori base, il costo ridotto:

$\Delta_{ij}=c_{ij}-(u_i+v_j).$

La soluzione è ottima se tutti i $\Delta_{ij}\ge0$ (minimizzazione): nessuna cella fuori base conviene. Un $\Delta_{ij}<0$ indica una rotta più economica da introdurre.

6. Problema dell’assegnazione

Esercizio. Descrivere il problema dell’assegnazione come caso particolare dei trasporti.

L’assegnazione abbina $n$ agenti a $n$ compiti, uno a uno, minimizzando il costo totale. È un trasporto con:

$\text{offerte}=\text{domande}=1\ \text{per ogni nodo.}$

Per la sua struttura si risolve con il metodo ungherese, più efficiente. La soluzione assegna esattamente un compito per agente (matrice di permutazione). È il modello di turni, allocazione macchine-lavori, abbinamenti.

7. Costo di una soluzione di trasporto

Esercizio. Date le allocazioni:

x_{11}=25,\qquad x_{12}=5,\qquad x_{22}=20,

e i costi:

c_{11}=4,\qquad c_{12}=6,\qquad c_{22}=3,

calcolare il costo totale.

Il costo totale è:

C=\sum_i\sum_j c_{ij}x_{ij}.

Quindi:

C=4\cdot25+6\cdot5+3\cdot20.

Calcolando:

C=100+30+60=190.

Risultato:

\boxed{C=190}.

Una soluzione ammissibile non è necessariamente buona: va sempre valutato il costo e poi confrontato con soluzioni alternative.

8. Metodo del costo minimo su un esempio

Esercizio. Risolvere una soluzione iniziale con costo minimo per offerte $(20,30)$ , domande $(10,40)$ e matrice dei costi:

C= \begin{pmatrix} 2&5\\ 4&1 \end{pmatrix}.

La cella più economica è $(2,2)$ con costo $1$ . Allochiamo:

x_{22}=\min(30,40)=30.

L’offerta della seconda origine si esaurisce; resta domanda $D_2=10$ .

Tra le celle residue, per la prima origine restano $D_1=10$ e $D_2=10$ . Allochiamo:

x_{11}=10, \qquad x_{12}=10.

Soluzione:

\boxed{x_{22}=30,\quad x_{11}=10,\quad x_{12}=10}.

Costo:

C=30\cdot1+10\cdot2+10\cdot5=30+20+50=100.

Il metodo non garantisce sempre l’ottimo, ma produce spesso una base iniziale migliore del nord-ovest.

9. Verifica MODI in un problema $2\times2$

Esercizio. Per la soluzione base del punto 8, verificare l’ottimalità con i potenziali MODI.

Le celle base sono:

(2,2),\quad (1,1),\quad (1,2).

Per un problema $2\times2$ servono $m+n-1=3$ celle base: la soluzione non è degenere.

Imponiamo:

u_i+v_j=c_{ij}

sulle celle base. Poniamo $u_1=0$ .

Dalla cella $(1,1)$ :

u_1+v_1=2 \quad\Rightarrow\quad v_1=2.

Dalla cella $(1,2)$ :

u_1+v_2=5 \quad\Rightarrow\quad v_2=5.

Dalla cella $(2,2)$ :

u_2+v_2=1 \quad\Rightarrow\quad u_2=-4.

L’unica cella fuori base è $(2,1)$ , con costo ridotto:

\Delta_{21}=c_{21}-(u_2+v_1)=4-(-4+2)=4-(-2)=6.

Poiché:

\Delta_{21}>0,

la soluzione è ottima per un problema di minimizzazione.

\boxed{\text{soluzione ottima}}

10. Degenerazione

Esercizio. Un problema di trasporti $3\times3$ ha solo $4$ celle allocate positive. È una soluzione di base valida?

Una soluzione di base deve avere:

m+n-1=3+3-1=5

celle base.

Se le celle positive sono solo $4$ , la soluzione è degenere. Per applicare MODI o stepping-stone si aggiunge una cella base con allocazione nulla, scelta in modo da non creare cicli chiusi prematuri.