Esercizi · Trasporto e assegnamento¶

Esercizi · Capitolo 7 · ogni soluzione si apre con un clic · Capitolo 7: Trasporto e assegnamento · Eserciziario, volume 3 (PDF)

Regole utilizzate in questi esercizi

Le definizioni e i risultati del capitolo «Trasporto e assegnazione». Il le origini sono \(1,2,\dots,m\) con rifornimenti \(a_i\), le destinazioni \(m+1,m+2,\dots,m+n\) con richieste \(d_j\) e le celle \((i,j)\) vengono presi in ordine riga-colonna.

(F1) Model. \(\min \sum_{i}\sum_{j} c_{ij}x_{ij}\) con somme di riga \(a_i\), somme di colonna \(d_j\) e \(\vet{x} \ge \vet{0}\); feasible if and only if \(\sum_i a_i=\sum_j d_j\). Un eccesso di offerta va verso una destinazione fittizia costa \(0\).
(F2) Basi. Una base è un insieme di celle \(m+n-1\) che formano uno albero ricoprente della rete bipartita (non percorso chiuso alternando righe e colonne). La sua soluzione fondamentale si trova foglia per foglia; è degenerato se basilare la cella ha valore \(0\).
(F3) Soluzioni iniziali. Angolo nord-ovest: la cella attiva con la riga e la colonna più piccole. Minimo costo: la cella attiva più economica, la più piccola \(i\) e poi \(j\) in parità. L'importo è \(\min\{\bar{a}_i,\bar{d}_j\}\); se \(\bar{a}_i=0\) ed è attiva un'altra riga, la riga viene barrata, altrimenti la colonna.
(F4) Metodo potenziale. \(\pi_i-\pi_j=c_{ij}\) sulle celle base, \(\pi_{m+n}=0\); \(\bar{c}_{ij}=c_{ij}-\pi_i+\pi_j\). Ottimale se \(\bar{c} \ge 0\), unico se \(\bar{c}_{ij}>0\) fuori base. Altrimenti entra il \(\bar{c}_e\) più negativo (a pari merito: il più piccolo \(i\), poi \(j\)); il ciclo inizia da \(e\) lungo la sua fila con segnaletica \(+,-,+,\dots\); \(\theta\) è il minimo sulle celle \(-\) e il primo di essi con \(\bar{x}=\theta\) in righe-colonne in ordine di foglie; il costo varia in base a \(\theta\,\bar{c}_e\).
(F5) Algoritmo ungherese. Sottrai i minimi di riga (\(\pi_i\)) e poi i minimi di colonna (\(-\pi_j\)). Trova un insieme massimo di zeri indipendenti (riga per riga, percorsi alternati, colonne in ordine crescente); se ha \(n\) zeri, fermati. Altrimenti, partendo dalle righe senza assegnazione, si tracciano i cammini alternati. Le righe non raggiunte e le colonne raggiunte definiscono le linee di copertura; \(\delta\) è lo scoperto minimo, sottratto agli scoperti e sommato a quelli coperti due volte (\(\pi_i \mathrel{+}=\delta\) sulle righe scoperte, \(\pi_j \mathrel{+}=\delta\) su colonne coperte). Il valore duale \(\sum_i\pi_i-\sum_j\pi_j\) cresce di \(\delta\,(n-k)\) con le linee \(k\).

Esercizio 7.1: Prime soluzioni ammissibili di base

Esercizio

Tre stabilimenti \(1,2,3\) forniscono unità \(a_1=30\), \(a_2=40\), \(a_3=20\) di un prodotto e tre clienti \(4,5,6\) richiedono unità \(d_4=15\), \(d_5=25\), \(d_6=40\). Ogni domanda deve essere soddisfatta e ogni stabilimento spedisce al massimo la sua offerta. Le spese di spedizione unitarie sono:

\[ \begin{array}{c|ccc|c} \hline {c_{ij}} & {4} & {5} & {6} & {a_i} \\ \hline {1} & {7} & {4} & {7} & {30} \\ {2} & {1} & {6} & {8} & {40} \\ {3} & {9} & {9} & {6} & {20} \\ \hline {d_j} & {15} & {25} & {40} & \\ \hline \end{array} \]

Domande

L'istanza è bilanciata? Aggiungi una destinazione fittizia come in (F1) e scrivi la tabella dei trasporti.
Costruisci una prima soluzione ammissibile di base con la regola dell'angolo nord-ovest: elenca i passaggi, scrivi la soluzione nel tableau e calcolane il costo.
Costruisci una soluzione fattibile di base iniziale con la regola del costo minimo e confronta i due costi.
Verificare che entrambe le soluzioni abbiano celle base \(m+n-1\) che formano uno albero ricoprente. Quanta scorta lascia inutilizzata ciascuna pianta nelle due soluzioni?

Soluzione

Usiamo le regole (F1)–(F5) del riquadro all'inizio di questi esercizi.

L'offerta totale è \(30+40+20=90\) e la domanda totale è \(15+25+40=80\): l'istanza non è bilanciata, con un eccesso di unità \(10\). Aggiungiamo la destinazione fittizia \(7\) con domanda \(d_{7}=10\) e costi \(c_{17}=c_{27}=c_{37}=0\):

\[ \begin{array}{c|cccc|c} \hline {c_{ij}} & {4} & {5} & {6} & {7} & {a_i} \\ \hline {1} & {7} & {4} & {7} & {0} & {30} \\ {2} & {1} & {6} & {8} & {0} & {40} \\ {3} & {9} & {9} & {6} & {0} & {20} \\ \hline {d_j} & {15} & {25} & {40} & {10} & {90} \\ \hline \end{array} \]

I passaggi della regola dell'angolo nord-ovest sono

passo	cella	importo	barrato
\(1\)	\((1,4)\)	\(15\)	colonna \(4\)
\(2\)	\((1,5)\)	\(15\)	riga \(1\)
\(3\)	\((2,5)\)	\(10\)	colonna \(5\)
\(4\)	\((2,6)\)	\(30\)	riga \(2\)
\(5\)	\((3,6)\)	\(10\)	colonna \(6\)
\(6\)	\((3,7)\)	\(10\)	riga \(3\), colonna \(7\)

e la soluzione è

\(\bar{x}_{ij}\)	\(4\)	\(5\)	\(6\)	\(7\)	\(a_i\)
\(1\)	\(15\)	\(15\)			\(30\)
\(2\)		\(10\)	\(30\)		\(40\)
\(3\)			\(10\)	\(10\)	\(20\)
\(d_j\)	\(15\)	\(25\)	\(40\)	\(10\)

Il suo costo è \(7 \cdot 15+4 \cdot 15+6 \cdot 10+8 \cdot 30+6 \cdot 10+0 \cdot 10=525\).

I passaggi della regola del costo minimo sono

passo	cella	importo	barrato
\(1\)	\((1,7)\)	\(10\)	colonna \(7\)
\(2\)	\((2,4)\)	\(15\)	colonna \(4\)
\(3\)	\((1,5)\)	\(20\)	riga \(1\)
\(4\)	\((2,5)\)	\(5\)	colonna \(5\)
\(5\)	\((3,6)\)	\(20\)	riga \(3\)
\(6\)	\((2,6)\)	\(20\)	riga \(2\), colonna \(6\)

Nel passaggio \(1\) le tre celle fittizie costano \(0\) e la regola accetta \((1,7)\), la riga più piccola. La soluzione è

\(\bar{x}_{ij}\)	\(4\)	\(5\)	\(6\)	\(7\)	\(a_i\)
\(1\)		\(20\)		\(10\)	\(30\)
\(2\)	\(15\)	\(5\)	\(20\)		\(40\)
\(3\)			\(20\)		\(20\)
\(d_j\)	\(15\)	\(25\)	\(40\)	\(10\)

Il suo costo è \(4 \cdot 20+0 \cdot 10+1 \cdot 15+6 \cdot 5+8 \cdot 20+6 \cdot 20=405\), inferiore allo \(525\) della regola dell'angolo nord-ovest.

Ogni regola esegue passi \(m+n-1=3+4-1=6\), una cella per passo; le celle formano un albero di copertura perché la linea incrociata di ogni passaggio non contiene celle successive. Il flusso sulla colonna fittizia è la fornitura non utilizzata: con la regola dell'angolo nord-ovest l'impianto \(1\) mantiene \(0\), l'impianto \(2\) mantiene \(0\) e l'impianto \(3\) mantiene \(10\); con la regola del costo minimo l'impianto \(1\) mantiene \(10\), l'impianto \(2\) mantiene \(0\) e l'impianto \(3\) mantiene \(0\).

Con la destinazione fittizia \(7\) (\(d_{7}=10\), costi zero) la regola dell'angolo nord-ovest costa \(525\) e la regola del costo minimo \(405\).

Esercizio 7.2: Il metodo potenziale

Esercizio

Consideriamo l'istanza di trasporto con origini \(1,2,3\), destinazioni \(4,5,6,7\) e i costi, le forniture e le domande del tableau:

\[ \begin{array}{c|cccc|c} \hline {c_{ij}} & {4} & {5} & {6} & {7} & {a_i} \\ \hline {1} & {4} & {6} & {8} & {8} & {30} \\ {2} & {2} & {2} & {7} & {7} & {15} \\ {3} & {8} & {7} & {3} & {2} & {25} \\ \hline {d_j} & {15} & {5} & {45} & {5} & {70} \\ \hline \end{array} \]

Domande

Costruisci la soluzione ammissibile di base iniziale con la regola dell'angolo nord-ovest e calcolane il costo.
Calcola i potenziali della sua base (\(\pi_7=0\)) e i costi ridotti. La soluzione è ottimale?
Eseguire il metodo potenziale fino alla soluzione ottima, con le regole di (F4).
Scrivi i potenziali ottimali e verifica che il valore del modello duale sia uguale al costo ottimale. La soluzione ottimale è unica?

Soluzione

Usiamo le regole (F1)–(F5) del riquadro all'inizio di questi esercizi.

La regola dell'angolo nord-ovest dà

passo	cella	importo	barrato
\(1\)	\((1,4)\)	\(15\)	colonna \(4\)
\(2\)	\((1,5)\)	\(5\)	colonna \(5\)
\(3\)	\((1,6)\)	\(10\)	riga \(1\)
\(4\)	\((2,6)\)	\(15\)	riga \(2\)
\(5\)	\((3,6)\)	\(20\)	colonna \(6\)
\(6\)	\((3,7)\)	\(5\)	riga \(3\), colonna \(7\)

\(\bar{x}_{ij}\)	\(4\)	\(5\)	\(6\)	\(7\)	\(a_i\)
\(1\)	\(15\)	\(5\)	\(10\)		\(30\)
\(2\)			\(15\)		\(15\)
\(3\)			\(20\)	\(5\)	\(25\)
\(d_j\)	\(15\)	\(5\)	\(45\)	\(5\)

con costo \(4 \cdot 15+6 \cdot 5+8 \cdot 10+7 \cdot 15+3 \cdot 20+2 \cdot 5=345\).

Da \(\pi_7=0\) lungo le celle base: \(\pi_{1}=7,\ \pi_{2}=6,\ \pi_{3}=2,\ \pi_{4}=3,\ \pi_{5}=1,\ \pi_{6}=-1,\ \pi_{7}=0\). I costi ridotti delle celle non basiche si trovano nel primo tableau della risposta successiva; \(\bar{c}_{25}=-3\) e \(\bar{c}_{24}=-1\) sono negativi, quindi la soluzione non è ottimale.

I tableaux contengono gli importi delle celle base (blu, grassetto) ed i costi ridotti delle altre celle; i potenziali sono ai margini.
Iterazione 1
Potenziali: \(\pi_{1}=7,\ \pi_{2}=6,\ \pi_{3}=2,\ \pi_{4}=3,\ \pi_{5}=1,\ \pi_{6}=-1,\ \pi_{7}=0\).

	\(4\)	\(5\)	\(6\)	\(7\)	\(\pi_i\)
\(1\)	\(\mathbf{15}\)	\(\mathbf{5}\,\ominus\)	\(\mathbf{10}\,\oplus\)	\(1\)	\(7\)
\(2\)	\(-1\)	\(-3\,\oplus\)	\(\mathbf{15}\,\ominus\)	\(1\)	\(6\)
\(3\)	\(9\)	\(6\)	\(\mathbf{20}\)	\(\mathbf{5}\)	\(2\)
\(\pi_j\)	\(3\)	\(1\)	\(-1\)	\(0\)

I costi ridotti negativi sono \(\bar{c}_{25}=-3\), \(\bar{c}_{24}=-1\); la cella \((2,5)\) entra nella base.
Il ciclo è \(\,(2,5)^{+},\ (2,6)^{-},\ (1,6)^{+},\ (1,5)^{-}\).
Le celle con segno \(-\) hanno \(\bar{x}_{26}=15\) e \(\bar{x}_{15}=5\): \(\theta=5\) e la cella \((1,5)\) lascia la base.
Il costo va da \(345\) a \(345+5\cdot(-3)=330\).

Iterazione 2
Potenziali: \(\pi_{1}=7,\ \pi_{2}=6,\ \pi_{3}=2,\ \pi_{4}=3,\ \pi_{5}=4,\ \pi_{6}=-1,\ \pi_{7}=0\).

	\(4\)	\(5\)	\(6\)	\(7\)	\(\pi_i\)
\(1\)	\(\mathbf{15}\,\ominus\)	\(3\)	\(\mathbf{15}\,\oplus\)	\(1\)	\(7\)
\(2\)	\(-1\,\oplus\)	\(\mathbf{5}\)	\(\mathbf{10}\,\ominus\)	\(1\)	\(6\)
\(3\)	\(9\)	\(9\)	\(\mathbf{20}\)	\(\mathbf{5}\)	\(2\)
\(\pi_j\)	\(3\)	\(4\)	\(-1\)	\(0\)

L'unico costo ridotto negativo è \(\bar{c}_{24}=-1\): la cella \((2,4)\) entra nella base.
Il ciclo è \(\,(2,4)^{+},\ (2,6)^{-},\ (1,6)^{+},\ (1,4)^{-}\).
Le celle con segno \(-\) hanno \(\bar{x}_{26}=10\) e \(\bar{x}_{14}=15\): \(\theta=10\) e la cella \((2,6)\) lascia la base.
Il costo va da \(330\) a \(330+10\cdot(-1)=320\).

Iterazione 3
Potenziali: \(\pi_{1}=7,\ \pi_{2}=5,\ \pi_{3}=2,\ \pi_{4}=3,\ \pi_{5}=3,\ \pi_{6}=-1,\ \pi_{7}=0\).

	\(4\)	\(5\)	\(6\)	\(7\)	\(\pi_i\)
\(1\)	\(\mathbf{5}\)	\(2\)	\(\mathbf{25}\)	\(1\)	\(7\)
\(2\)	\(\mathbf{10}\)	\(\mathbf{5}\)	\(1\)	\(2\)	\(5\)
\(3\)	\(9\)	\(8\)	\(\mathbf{20}\)	\(\mathbf{5}\)	\(2\)
\(\pi_j\)	\(3\)	\(3\)	\(-1\)	\(0\)

Tutti i costi ridotti sono non negativi: la soluzione di base ammissibile è ottimale, con costo \(z=320\).

I potenziali ottimali sono \(\pi_{1}=7,\ \pi_{2}=5,\ \pi_{3}=2,\ \pi_{4}=3,\ \pi_{5}=3,\ \pi_{6}=-1,\ \pi_{7}=0\) e il valore duale è

\[ \sum_{i} a_i\pi_i-\sum_{j} d_j\pi_j=335-15=320, \]

pari al costo ottimale. Ogni cella non di base dispone di \(\bar{c}_{ij}>0\), quindi la soluzione ottimale è unica.

Dall'angolo nord-ovest (costo \(345\)) il metodo potenziale fa ruotare \(2\) e raggiunge l'ottimo unico \(\tilde{x}_{14}=5\), \(\tilde{x}_{16}=25\), \(\tilde{x}_{24}=10\), \(\tilde{x}_{25}=5\), \(\tilde{x}_{36}=20\), \(\tilde{x}_{37}=5\), con costo \(320\).

Esercizio 7.3: Degenerazione

Esercizio

Consideriamo l'istanza di trasporto con origini \(1,2,3\) e destinazioni \(4,5,6\):

\[ \begin{array}{c|ccc|c} \hline {c_{ij}} & {4} & {5} & {6} & {a_i} \\ \hline {1} & {7} & {3} & {7} & {20} \\ {2} & {5} & {3} & {1} & {10} \\ {3} & {6} & {7} & {8} & {25} \\ \hline {d_j} & {10} & {10} & {35} & {55} \\ \hline \end{array} \]

Domande

Costruisci la soluzione all'angolo nord-ovest. In quale passaggio una riga e una colonna vengono esaurite contemporaneamente? Quale cella base ha valore \(0\) e perché deve rimanere nella base?
Eseguire il metodo potenziale da questa soluzione, con le regole di (F4).
Quale perno è degenerato e cosa cambia in esso? Fornire la soluzione ottimale e il suo costo.

Soluzione

Usiamo le regole (F1)–(F5) del riquadro all'inizio di questi esercizi.

La regola dell'angolo nord-ovest dà

passo	cella	importo	barrato
\(1\)	\((1,4)\)	\(10\)	colonna \(4\)
\(2\)	\((1,5)\)	\(10\)	riga \(1\)
\(3\)	\((2,5)\)	\(0\)	colonna \(5\)
\(4\)	\((2,6)\)	\(10\)	riga \(2\)
\(5\)	\((3,6)\)	\(25\)	riga \(3\), colonna \(6\)

Al passo \(2\) la cella \((1,5)\) scarica sia la riga \(1\) che la colonna \(5\). Viene barrata solo la riga e la cella successiva \((2,5)\) della colonna \(5\) ottiene l'importo \(0\):

\(\bar{x}_{ij}\)	\(4\)	\(5\)	\(6\)	\(a_i\)
\(1\)	\(10\)	\(10\)		\(20\)
\(2\)		\(0\)	\(10\)	\(10\)
\(3\)			\(25\)	\(25\)
\(d_j\)	\(10\)	\(10\)	\(35\)

La soluzione, del costo \(310\), è degenerata. La base necessita di celle \(m+n-1=5\): senza \((2,5)\) le altre celle non si estendono sui nodi \(6\) e i potenziali non possono essere calcolati.

Iterazione 1
Potenziali: \(\pi_{1}=1,\ \pi_{2}=1,\ \pi_{3}=8,\ \pi_{4}=-6,\ \pi_{5}=-2,\ \pi_{6}=0\).

	\(4\)	\(5\)	\(6\)	\(\pi_i\)
\(1\)	\(\mathbf{10}\,\ominus\)	\(\mathbf{10}\,\oplus\)	\(6\)	\(1\)
\(2\)	\(-2\)	\(\mathbf{0}\,\ominus\)	\(\mathbf{10}\,\oplus\)	\(1\)
\(3\)	\(-8\,\oplus\)	\(-3\)	\(\mathbf{25}\,\ominus\)	\(8\)
\(\pi_j\)	\(-6\)	\(-2\)	\(0\)

I costi ridotti negativi sono \(\bar{c}_{34}=-8\), \(\bar{c}_{35}=-3\), \(\bar{c}_{24}=-2\); la cella \((3,4)\) entra nella base.
Il ciclo è \(\,(3,4)^{+},\ (3,6)^{-},\ (2,6)^{+},\ (2,5)^{-},\ (1,5)^{+},\ (1,4)^{-}\).
Le celle con segno \(-\) hanno \(\bar{x}_{36}=25\), \(\bar{x}_{25}=0\) e \(\bar{x}_{14}=10\): \(\theta=0\) e la cella \((2,5)\) lascia la base.
Il perno è degenerato: la soluzione ed il suo costo \(z=310\) non cambiano, cambia solo la base.

Iterazione 2
Potenziali: \(\pi_{1}=9,\ \pi_{2}=1,\ \pi_{3}=8,\ \pi_{4}=2,\ \pi_{5}=6,\ \pi_{6}=0\).

	\(4\)	\(5\)	\(6\)	\(\pi_i\)
\(1\)	\(\mathbf{10}\,\ominus\)	\(\mathbf{10}\)	\(-2\,\oplus\)	\(9\)
\(2\)	\(6\)	\(8\)	\(\mathbf{10}\)	\(1\)
\(3\)	\(\mathbf{0}\,\oplus\)	\(5\)	\(\mathbf{25}\,\ominus\)	\(8\)
\(\pi_j\)	\(2\)	\(6\)	\(0\)

L'unico costo ridotto negativo è \(\bar{c}_{16}=-2\): la cella \((1,6)\) entra nella base.
Il ciclo è \(\,(1,6)^{+},\ (1,4)^{-},\ (3,4)^{+},\ (3,6)^{-}\).
Le celle con segno \(-\) hanno \(\bar{x}_{14}=10\) e \(\bar{x}_{36}=25\): \(\theta=10\) e la cella \((1,4)\) esce dalla base.
Il costo va da \(310\) a \(310+10\cdot(-2)=290\).

Iterazione 3
Potenziali: \(\pi_{1}=7,\ \pi_{2}=1,\ \pi_{3}=8,\ \pi_{4}=2,\ \pi_{5}=4,\ \pi_{6}=0\).

	\(4\)	\(5\)	\(6\)	\(\pi_i\)
\(1\)	\(2\)	\(\mathbf{10}\)	\(\mathbf{10}\)	\(7\)
\(2\)	\(6\)	\(6\)	\(\mathbf{10}\)	\(1\)
\(3\)	\(\mathbf{10}\)	\(3\)	\(\mathbf{15}\)	\(8\)
\(\pi_j\)	\(2\)	\(4\)	\(0\)

Tutti i costi ridotti sono non negativi: la soluzione di base ammissibile è ottimale, con costo \(z=290\).

Il primo pivot ha \(\theta=0\): la cella \((3,4)\) entra con valore \(0\) ed esce \((2,5)\); la soluzione ed il suo costo non cambiano, ma i nuovi potenziali mostrano un costo ridotto negativo. La soluzione ottimale è \(\tilde{x}_{15}=10\), \(\tilde{x}_{16}=10\), \(\tilde{x}_{26}=10\), \(\tilde{x}_{34}=10\), \(\tilde{x}_{36}=15\), con costo \(290\), ed è unica, poiché ogni cella non di base ha \(\bar{c}_{ij}>0\).

La soluzione dell'angolo nord-ovest è degenere (la cella base \((2,5)\) ha valore \(0\)); il primo perno ha \(\theta=0\), il secondo perno raggiunge l'ottimale, di costo \(290\).

Esercizio 7.4: L'algoritmo ungherese

Esercizio

Cinque lavoratori \(1,2,3,4,5\) devono essere assegnati a cinque lavori \(6,7,8,9,10\), un lavoro ciascuno, al costo totale minimo. I costi sono:

\[ \begin{array}{c|ccccc} \hline {c_{ij}} & {6} & {7} & {8} & {9} & {10} \\ \hline {1} & {6} & {10} & {10} & {5} & {3} \\ {2} & {11} & {12} & {9} & {7} & {7} \\ {3} & {8} & {1} & {12} & {6} & {11} \\ {4} & {12} & {7} & {10} & {8} & {2} \\ {5} & {3} & {4} & {11} & {6} & {1} \\ \hline \end{array} \]

Domande

Ridurre le righe e poi le colonne della matrice. Quali potenziali offrono le riduzioni e quale limite inferiore al costo ottimale?
Eseguire l'algoritmo ungherese: ad ogni iterazione fornire un insieme massimo di zeri indipendenti, le linee di (F5) e la regolazione \(\delta\).
Fornire l'assegnazione ottimale e il relativo costo, e verificare che i potenziali finali siano una soluzione duale ottimale.

Soluzione

Usiamo le regole (F1)–(F5) del riquadro all'inizio di questi esercizi.

I minimi di riga sono \(3,7,1,2,1\), quindi \(\pi_{1}=3\), \(\pi_{2}=7\), \(\pi_{3}=1\), \(\pi_{4}=2\), \(\pi_{5}=1\):

\[ \begin{array}{c|ccccc} \hline {c_{ij}-\pi_i} & {6} & {7} & {8} & {9} & {10} \\ \hline {1} & {3} & {7} & {7} & {2} & {0} \\ {2} & {4} & {5} & {2} & {0} & {0} \\ {3} & {7} & {0} & {11} & {5} & {10} \\ {4} & {10} & {5} & {8} & {6} & {0} \\ {5} & {2} & {3} & {10} & {5} & {0} \\ \hline \end{array} \]

I minimi di colonna sono quindi \(2,0,2,0,0\), quindi \(\pi_{6}=-2\) e \(\pi_{8}=-2\), e gli altri \(\pi_j\) sono \(0\). Il valore duale \(\sum_i\pi_i-\sum_j\pi_j=18\) rappresenta un limite inferiore al costo di ogni incarico.

In ciascuna matrice gli zeri indipendenti sono riquadrati, le linee blu e la cella di \(\delta\) rossa; i potenziali sono ai margini.
Iterazione 1

\(\bar{c}_{ij}\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)	\(\pi_i\)
\(1\)	\(1\)	\(7\)	\(5\)	\(2\)	\(\boxed{0}\)	\(3\)
\(2\)	\(2\)	\(5\)	\(\boxed{0}\)	\(0\)	\(0\)	\(7\)
\(3\)	\(5\)	\(\boxed{0}\)	\(9\)	\(5\)	\(10\)	\(1\)
\(4\)	\(8\)	\(5\)	\(6\)	\(6\)	\(0\)	\(2\)
\(5\)	\(\boxed{0}\)	\(3\)	\(8\)	\(5\)	\(0\)	\(1\)
\(\pi_j\)	\(-2\)	\(0\)	\(-2\)	\(0\)	\(0\)

Un set massimo di zeri indipendenti (riquadro) ha elementi \(4\): \((1,10)\), \((2,8)\), \((3,7)\), \((5,6)\).
Le righe \(4<5\) (blu) sono le righe \(2\), \(3\) e \(5\) e la colonna \(10\).
La voce minima scoperta è \(\delta=1\), nella cella \((1,6)\) (rossa). Lo sottraiamo dalle voci scoperte e lo aggiungiamo alle voci coperte due volte: \(\pi_i\) cresce di \(1\) per le righe scoperte \(1\) e \(4\) e \(\pi_j\) cresce di \(1\) per la colonna coperta \(10\). Il valore duale cresce di \(1\cdot(5-4)=1\).

Iterazione 2

\(\bar{c}_{ij}\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)	\(\pi_i\)
\(1\)	\(\boxed{0}\)	\(6\)	\(4\)	\(1\)	\(0\)	\(4\)
\(2\)	\(2\)	\(5\)	\(\boxed{0}\)	\(0\)	\(1\)	\(7\)
\(3\)	\(5\)	\(\boxed{0}\)	\(9\)	\(5\)	\(11\)	\(1\)
\(4\)	\(7\)	\(4\)	\(5\)	\(5\)	\(\boxed{0}\)	\(3\)
\(5\)	\(0\)	\(3\)	\(8\)	\(5\)	\(1\)	\(1\)
\(\pi_j\)	\(-2\)	\(0\)	\(-2\)	\(0\)	\(1\)

Un set massimo di zeri indipendenti (riquadro) ha elementi \(4\): \((1,6)\), \((2,8)\), \((3,7)\), \((4,10)\).
Le righe \(4<5\) (blu) sono le righe \(2\) e \(3\) e le colonne \(6\) e \(10\).
La voce minima scoperta è \(\delta=1\), nella cella \((1,9)\) (rossa). Lo sottraiamo dalle voci scoperte e lo aggiungiamo alle voci coperte due volte: \(\pi_i\) cresce di \(1\) per le righe scoperte \(1\), \(4\) e \(5\) e \(\pi_j\) cresce di \(1\) per le colonne coperte \(6\) e \(10\). Il valore duale cresce di \(1\cdot(5-4)=1\).

Iterazione 3

\(\bar{c}_{ij}\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)	\(\pi_i\)
\(1\)	\(0\)	\(5\)	\(3\)	\(\boxed{0}\)	\(0\)	\(5\)
\(2\)	\(3\)	\(5\)	\(\boxed{0}\)	\(0\)	\(2\)	\(7\)
\(3\)	\(6\)	\(\boxed{0}\)	\(9\)	\(5\)	\(12\)	\(1\)
\(4\)	\(7\)	\(3\)	\(4\)	\(4\)	\(\boxed{0}\)	\(4\)
\(5\)	\(\boxed{0}\)	\(2\)	\(7\)	\(4\)	\(1\)	\(2\)
\(\pi_j\)	\(-1\)	\(0\)	\(-2\)	\(0\)	\(2\)

Un set massimo di zeri indipendenti (riquadro) ha elementi \(5\): \((1,9)\), \((2,8)\), \((3,7)\), \((4,10)\), \((5,6)\).
Formano un'assegnazione a costo ridotto pari a zero: l'algoritmo si ferma e l'assegnazione è ottimale.

L'assegnazione ottimale è \(1 \to 9\), \(2 \to 8\), \(3 \to 7\), \(4 \to 10\), \(5 \to 6\), con costo \(5+9+1+2+3=20\). I potenziali finali danno \(\sum_i\pi_i-\sum_j\pi_j=19-(-1)=20\), pari al costo; tutti i costi ridotti sono non negativi, quindi i potenziali sono duali ed entrambe le soluzioni sono ottimali. L'ottimale è unico, come conferma l'enumerazione delle assegnazioni \(120\).

Le riduzioni danno il limite \(18\); due aggiustamenti, con \(\delta=1\) e \(\delta=1\), portano all'assegnazione ottimale \(1 \to 9\), \(2 \to 8\), \(3 \to 7\), \(4 \to 10\), \(5 \to 6\), di costo \(20\).

Esercizio 7.5: Basi, cicli e regola del costo minimo

Esercizio

Consideriamo l'istanza di trasporto con origini \(1,2,3\) e destinazioni \(4,5,6\):

\[ \begin{array}{c|ccc|c} \hline {c_{ij}} & {4} & {5} & {6} & {a_i} \\ \hline {1} & {2} & {4} & {1} & {30} \\ {2} & {4} & {8} & {5} & {20} \\ {3} & {9} & {1} & {1} & {15} \\ \hline {d_j} & {35} & {10} & {20} & {65} \\ \hline \end{array} \]

e i tre gruppi di celle

\[ T_1=\{(1,4),(2,4),(2,6),(3,5),(3,6)\},\qquad T_2=\{(1,6),(2,4),(2,6),(3,5),(3,6)\}, \]

\[ T_3=\{(2,4),(2,5),(2,6),(3,5),(3,6)\}. \]

Domande

Quali tra \(T_1\), \(T_2\), \(T_3\) sono basi? Per ciascuna base calcola la sua soluzione di base e indica se è ammissibile.
Dimostrare che aggiungendo una costante \(k\) a tutti i costi della riga \(i\) si aggiunge \(k\,a_i\) al costo di ogni soluzione fattibile, in modo che le soluzioni ottime non cambino. Cosa succede aggiungendo \(k\) ad una colonna \(j\)?
Costruisci la soluzione a costo minimo e decidi con i potenziali se è ottimale. La regola del costo minimo è sempre ottimale?

Soluzione

Usiamo le regole (F1)–(F5) del riquadro all'inizio di questi esercizi.

Ogni insieme ha celle \(m+n-1=5\), quindi è una base esattamente quando non contiene cicli (F2).
- \(T_1\) non ha ciclo: è uno albero ricoprente. Anta per anta, anta \(1\) dà \(x_{14}=30\), anta \(4\) dà \(x_{24}=5\), anta \(2\) dà \(x_{26}=15\), anta \(5\) dà \(x_{35}=10\), anta \(3\) dà \(x_{36}=5\): la soluzione base è fattibile.
- \(T_2\) non ha ciclo: è uno albero ricoprente. Anta per anta, anta \(1\) dà \(x_{16}=30\), anta \(4\) dà \(x_{24}=35\), anta \(2\) dà \(x_{26}=-15\), anta \(5\) dà \(x_{35}=10\), anta \(3\) dà \(x_{36}=5\): il valore \(-15\) è negativo e la soluzione di base non è fattibile.
- \(T_3\) contiene le celle \((2,5)\), \((3,5)\), \((3,6)\), \((2,6)\), che formano il ciclo \(2,5,3,6,2\) alternando righe e colonne: le loro colonne sono linearmente dipendenti e \(T_3\) non è un base.
Lascia che \(c'_{ij}=c_{ij}+k\) per ogni \(j\) e \(c'_{hj}=c_{hj}\) per \(h \neq i\). Per ogni \(\vet{x}\) ammissibile

\[ \sum_{h}\sum_{j} c'_{hj}x_{hj}=\sum_{h}\sum_{j} c_{hj}x_{hj}+k\sum_{j} x_{ij}=\sum_{h}\sum_{j} c_{hj}x_{hj}+k\,a_i , \]

perché la riga \(i\) di una soluzione fattibile sommata dà \(a_i\). Tutti i costi cambiano della stessa costante, quindi l'ordine delle soluzioni ammissibili e di quelle ottimali non cambia. Allo stesso modo, aggiungendo \(k\) alla colonna \(j\) si aggiunge \(k\,d_j\) a ogni costo. Nel metodo potenziale si tratta di una modifica di \(\pi_i\) con \(k\) (o di \(\pi_j\) con \(-k\)), fino alla normalizzazione, e i costi ridotti non cambiano.

La regola del costo minimo dà

passo	cella	importo	barrato
\(1\)	\((1,6)\)	\(20\)	colonna \(6\)
\(2\)	\((3,5)\)	\(10\)	colonna \(5\)
\(3\)	\((1,4)\)	\(10\)	riga \(1\)
\(4\)	\((2,4)\)	\(20\)	riga \(2\)
\(5\)	\((3,4)\)	\(5\)	riga \(3\), colonna \(4\)

\(\bar{x}_{ij}\)	\(4\)	\(5\)	\(6\)	\(a_i\)
\(1\)	\(10\)		\(20\)	\(30\)
\(2\)	\(20\)			\(20\)
\(3\)	\(5\)	\(10\)		\(15\)
\(d_j\)	\(35\)	\(10\)	\(20\)

con costo \(175\). Le sue potenziali e i costi ridotti lo sono

	\(4\)	\(5\)	\(6\)	\(\pi_i\)
\(1\)	\(\mathbf{10}\,\oplus\)	\(10\)	\(\mathbf{20}\,\ominus\)	\(1\)
\(2\)	\(\mathbf{20}\)	\(12\)	\(2\)	\(3\)
\(3\)	\(\mathbf{5}\,\ominus\)	\(\mathbf{10}\)	\(-7\,\oplus\)	\(8\)
\(\pi_j\)	\(-1\)	\(7\)	\(0\)

L'unico costo ridotto negativo è \(\bar{c}_{36}=-7\): la cella \((3,6)\) entra nella base.
Il ciclo è \(\,(3,6)^{+},\ (3,4)^{-},\ (1,4)^{+},\ (1,6)^{-}\).
Le celle con segno \(-\) hanno \(\bar{x}_{34}=5\) e \(\bar{x}_{16}=20\): \(\theta=5\) e la cella \((3,4)\) lascia la base.
Il costo va da \(175\) a \(175+5\cdot(-7)=140\).

La soluzione non è ottimale: un perno dà l'ottimo, di costo \(140\). La regola del costo minimo considera una cella alla volta e non è sempre ottimale; questo caso è un controesempio.

\(T_1\) è una base con una soluzione base ammissibile, \(T_2\) una base con valore negativo, \(T_3\) contiene un ciclo. La soluzione di costo minimo (costo \(175\)) non è ottimale: l'ottimale è \(140\).

Esercizio 7.6: Un incarico di massimo profitto

Esercizio

Quattro venditori \(1,2,3,4\) devono essere assegnati a quattro regioni \(5,6,7,8\), una regione ciascuna. I profitti attesi \(p_{ij}\) sono:

\[ \begin{array}{c|cccc} \hline {p_{ij}} & {5} & {6} & {7} & {8} \\ \hline {1} & {9} & {4} & {5} & {1} \\ {2} & {8} & {5} & {3} & {3} \\ {3} & {2} & {1} & {1} & {1} \\ {4} & {2} & {2} & {6} & {8} \\ \hline \end{array} \]

Cerchiamo un incarico di massimo profitto totale.

Domande

Trasformare il problema in un problema di assegnazione di costo minimo con costi non negativi.
Risolvilo con l'algoritmo ungherese.
Dare l'assegnazione del massimo profitto e del relativo profitto.

Soluzione

Usiamo le regole (F1)–(F5) del riquadro all'inizio di questi esercizi.

Il profitto più grande è \(p_{\max}=9\). Con \(c_{ij}=9-p_{ij}\) ogni incarico costa \(4 \cdot 9\) meno il profitto, quindi minimizzare il costo massimizza il profitto:

\[ \begin{array}{c|cccc} \hline {c_{ij}} & {5} & {6} & {7} & {8} \\ \hline {1} & {0} & {5} & {4} & {8} \\ {2} & {1} & {4} & {6} & {6} \\ {3} & {7} & {8} & {8} & {8} \\ {4} & {7} & {7} & {3} & {1} \\ \hline \end{array} \]

I minimi di riga sono \(0,1,7,1\) e poi i minimi di colonna \(0,1,1,0\):
Iterazione 1

\(\bar{c}_{ij}\)	\(5\)	\(6\)	\(7\)	\(8\)	\(\pi_i\)
\(1\)	\(\boxed{0}\)	\(4\)	\(3\)	\(8\)	\(0\)
\(2\)	\(0\)	\(2\)	\(4\)	\(5\)	\(1\)
\(3\)	\(0\)	\(\boxed{0}\)	\(0\)	\(1\)	\(7\)
\(4\)	\(6\)	\(5\)	\(1\)	\(\boxed{0}\)	\(1\)
\(\pi_j\)	\(0\)	\(-1\)	\(-1\)	\(0\)

Un insieme massimo di zeri indipendenti (riquadro) ha elementi \(3\): \((1,5)\), \((3,6)\), \((4,8)\).
Le linee \(3<4\) (blu) sono le righe \(3\) e \(4\) e la colonna \(5\).
La voce minima scoperta è \(\delta=2\), nella cella \((2,6)\) (rossa). Lo sottraiamo dalle voci scoperte e lo aggiungiamo alle voci coperte due volte: \(\pi_i\) cresce di \(2\) per le righe scoperte \(1\) e \(2\) e \(\pi_j\) cresce di \(2\) per la colonna coperta \(5\). Il valore duale cresce di \(2\cdot(4-3)=2\).

Iterazione 2

\(\bar{c}_{ij}\)	\(5\)	\(6\)	\(7\)	\(8\)	\(\pi_i\)
\(1\)	\(\boxed{0}\)	\(2\)	\(1\)	\(6\)	\(2\)
\(2\)	\(0\)	\(\boxed{0}\)	\(2\)	\(3\)	\(3\)
\(3\)	\(2\)	\(0\)	\(\boxed{0}\)	\(1\)	\(7\)
\(4\)	\(8\)	\(5\)	\(1\)	\(\boxed{0}\)	\(1\)
\(\pi_j\)	\(2\)	\(-1\)	\(-1\)	\(0\)

Un set massimo di zeri indipendenti (riquadro) ha elementi \(4\): \((1,5)\), \((2,6)\), \((3,7)\), \((4,8)\).
Formano un'assegnazione a costo ridotto zero: l'algoritmo si ferma e l'assegnazione è ottimale.

L'assegnazione ottimale è \(1 \to 5\), \(2 \to 6\), \(3 \to 7\), \(4 \to 8\), con costo \(13\) e profitto

\[ 9+5+1+8=23=4 \cdot 9-13. \]

L'enumerazione delle assegnazioni \(24\) conferma che si tratta dell'unico ottimale.

Con \(c_{ij}=9-p_{ij}\) l'algoritmo ungherese dà \(1 \to 5\), \(2 \to 6\), \(3 \to 7\), \(4 \to 8\), con profitto \(23\).