7.3 Soluzioni ammissibili di base iniziali¶
Parte 3 · Flussi · Capitolo 7 · Capitolo 7: Trasporto e assegnamento · Dispensa, volume 3 (PDF) · Slide · Esercizi: Trasporto e assegnamento · App: Trasporto: soluzione iniziale e metodo dei potenziali · App: Assegnamento: l'algoritmo ungherese
-
Una soluzione ammissibile di base si costruisce riempiendo la tabella una cella alla volta. Una riga o una colonna è attiva finché non viene barrata; l'offerta residua \(\bar{a}_i\) e la domanda residua \(\bar{d}_j\) sono ciò che resta da spedire e da ricevere.
-
Le due regole che seguono differiscono solo nella scelta della cella successiva.
Algoritmo: Soluzione ammissibile di base iniziale
STOP; altrimenti andare al Passo 1.- Quando \(\bar{a}_i=\bar{d}_j=0\) nello stesso momento, viene barrata solo la riga: la colonna resta attiva con domanda residua \(0\), e una cella successiva di quella colonna riceve la quantità \(0\). Questa cella di base con valore \(0\) mantiene \(T\) un albero ricoprente, e la soluzione è degenere.
Teorema 7.8: la soluzione iniziale è di base
Con entrambe le regole, l'algoritmo «Soluzione ammissibile di base iniziale» si ferma dopo \(m+n-1\) passi, e \(T\) è una base con soluzione ammissibile di base \(\bar{\vet{x}}\).
Dimostrazione
-
Invariante. Le offerte residue delle righe attive e le domande residue delle colonne attive hanno somme uguali: vale all'inizio, e il Passo 2 sottrae la stessa quantità dalle due parti.
-
Una linea barrata ha residuo \(0\). Una riga barrata ha \(\bar{a}_i=0\). Una colonna viene barrata quando \(\bar{a}_i>0\), e allora \(\bar{x}_{ij}=\bar{d}_j\) e \(\bar{d}_j=0\), oppure quando la riga \(i\) è l'unica riga attiva con \(\bar{a}_i=0\), e allora ogni colonna attiva ha residuo \(0\) per l'invariante.
-
Conteggio. Una riga viene barrata solo se un'altra riga è attiva, quindi una riga \(r\) non viene mai barrata, e l'algoritmo si ferma quando le \(n\) colonne sono barrate. All'arresto le righe attive hanno residuo \(0\) per l'invariante, e una riga che arriva a \(0\) senza essere barrata è l'unica riga attiva. Quindi i passi sono \((m-1)+n=m+n-1\), una cella ciascuno, tutte diverse, perché una cella si sceglie in due linee attive e una delle due viene poi barrata.
-
Ammissibilità. All'arresto ogni riga e ogni colonna ha residuo \(0\), quindi \(\bar{\vet{x}} \ge \vet{0}\) soddisfa tutti i vincoli.
-
Albero. Sia \(L_t\) la linea barrata al passo \(t\): nessuna cella successiva sta in \(L_t\). Procedendo all'indietro dall'ultimo passo, le celle dei passi \(t,t+1,\dots\) formano un albero: la cella del passo \(t\) collega il nuovo nodo \(L_t\) alla sua altra linea, ancora attiva, quindi un nodo delle celle successive o la riga \(r\). Per \(t=1\) l'albero ricopre tutti gli \(m+n\) nodi. □
7.3.1 La regola dell'angolo nord-ovest¶
Esempio 7.5: la regola dell'angolo nord-ovest
Sull'Esempio 7.1 la regola dell'angolo nord-ovest parte dalla cella \((1,4)\) e si sposta a destra o in basso. I suoi passi sono:
| passo | cella | quantità | barrata |
|---|---|---|---|
| \(1\) | \((1,4)\) | \(10\) | colonna \(4\) |
| \(2\) | \((1,5)\) | \(20\) | riga \(1\) |
| \(3\) | \((2,5)\) | \(5\) | colonna \(5\) |
| \(4\) | \((2,6)\) | \(15\) | colonna \(6\) |
| \(5\) | \((2,7)\) | \(10\) | riga \(2\) |
| \(6\) | \((3,7)\) | \(30\) | riga \(3\), colonna \(7\) |
La soluzione ammissibile di base, con le celle di base in blu, è
| \(\bar{x}_{ij}\) | \(4\) | \(5\) | \(6\) | \(7\) | \(a_i\) |
|---|---|---|---|---|---|
| \(1\) | \(10\) | \(20\) | \(30\) | ||
| \(2\) | \(5\) | \(15\) | \(10\) | \(30\) | |
| \(3\) | \(30\) | \(30\) | |||
| \(d_j\) | \(10\) | \(25\) | \(15\) | \(40\) |
Il suo costo è
Le sei celle di base formano l'albero ricoprente qui sotto, con le quantità sugli archi.
- La regola dell'angolo nord-ovest ignora i costi: su questa istanza spedisce \(20\) unità sulla cella \((1,5)\), di costo \(9\), e \(30\) unità su \((3,7)\), di costo \(6\).
7.3.2 La regola del costo minimo¶
Esempio 7.6: la regola del costo minimo
Sull'Esempio 7.1 la regola del costo minimo sceglie, a ogni passo, la cella più economica fra le righe e le colonne attive:
| passo | cella | quantità | barrata |
|---|---|---|---|
| \(1\) | \((1,4)\) | \(10\) | colonna \(4\) |
| \(2\) | \((3,5)\) | \(25\) | colonna \(5\) |
| \(3\) | \((1,6)\) | \(15\) | colonna \(6\) |
| \(4\) | \((2,7)\) | \(30\) | riga \(2\) |
| \(5\) | \((1,7)\) | \(5\) | riga \(1\) |
| \(6\) | \((3,7)\) | \(5\) | riga \(3\), colonna \(7\) |
-
Al passo \(1\) le celle \((1,4)\) e \((3,5)\) costano entrambe \(1\), e \((1,4)\) viene prima, perché la sua riga è più piccola. Al passo \(3\) le celle \((1,6)\), \((2,6)\), \((2,7)\) costano \(2\), e \((1,6)\) viene prima.
-
Al passo \(4\) è attiva solo la colonna \(7\): prende tutta l'offerta della riga \(2\), poi \(5\) unità dalla riga \(1\) e \(5\) dalla riga \(3\).
La soluzione ammissibile di base è
| \(\bar{x}_{ij}\) | \(4\) | \(5\) | \(6\) | \(7\) | \(a_i\) |
|---|---|---|---|---|---|
| \(1\) | \(10\) | \(15\) | \(5\) | \(30\) | |
| \(2\) | \(30\) | \(30\) | |||
| \(3\) | \(25\) | \(5\) | \(30\) | ||
| \(d_j\) | \(10\) | \(25\) | \(15\) | \(40\) |
con costo
Riempiendo una cella per passo e barrando una linea per passo si ottiene una soluzione ammissibile di base con \(m+n-1\) celle di base. La regola dell'angolo nord-ovest ignora i costi; la regola del costo minimo di solito parte molto più vicino all'ottimo (\(170\) invece di \(440\) nell'esempio).
Avanti: 7.4 Il metodo dei potenziali