7.3 Soluzioni iniziali di base fattibili

Parte 3 · Flussi · Capitolo 7 · Capitolo 7: Trasporto e assegnamento · Dispensa, volume 3 (PDF) · Esercizi: Trasporto e assegnamento

• Una soluzione fattibile di base viene creata riempiendo il tableau una cella alla volta. Una riga o una colonna lo è attivo finché non viene cancellato; l'offerta residua \(\bar{a}_i\) e la domanda residua \(\bar{d}_j\) sono ciò che è rimasti da spedire e da ricevere.

• Le due regole seguenti differiscono solo per la scelta della cella successiva.

Algoritmo: Soluzione fattibile di base iniziale

Input: un'istanza bilanciata con forniture \(a_i\), richieste \(d_j\) e costi \(c_{ij}\)

Output: una base \(T\) e la sua soluzione di base ammissibile \(\bar{\vet{x}}\)

1Passaggio 0 (inizializzazione). Tutte le righe e le colonne sono attive; \(\bar{a}_i:=a_i\), \(\bar{d}_j:=d_j\), \(T:=\emptyset\).

2Passaggio 1 (scelta della cella). Scegli una cella \((i,j)\) con riga e colonna attive:

3 regola dell'angolo nord-ovest: la cella con il più piccolo \(i\) e il più piccolo \(j\);

4 regola del costo minimo: la cella con il più piccolo \(c_{ij}\) (il più piccolo \(i\), poi \(j\), in parità).

5Passaggio 2 (importo). Imposta \(\bar{x}_{ij}:=\min\{\bar{a}_i,\bar{d}_j\}\), aggiungi \((i,j)\) a \(T\) e sottrai \(\bar{x}_{ij}\) da \(\bar{a}_i\) e da \(\bar{d}_j\).

6Passaggio 3 (cancellazione). Se \(\bar{a}_i=0\) e un'altra riga sono attivi, cancella la riga \(i\); altrimenti cancellalo colonna \(j\).

7 Se nessuna colonna è attiva, STOP; altrimenti vai al passo 1.

• Quando \(\bar{a}_i=\bar{d}_j=0\) contemporaneamente viene barrata solo la riga: la colonna rimane attiva con residuo richiedono \(0\) e una cella successiva di quella colonna ottiene l'importo \(0\). Questa cella base con valore \(0\) mantiene \(T\) un intervallo albero e la soluzione è degenere.

Teorema 7.8: la soluzione iniziale è semplice

Con entrambe le regole, l'algoritmo «Soluzione di base ammissibile iniziale» si ferma dopo i passaggi \(m+n-1\) e \(T\) è una base con soluzione di base ammissibile \(\bar{\vet{x}}\).

Dimostrazione

1. Invariante. Le forniture residue delle righe attive e le richieste residue delle colonne attive hanno somme uguali: vero all'inizio e il passaggio 2 sottrae lo stesso importo da entrambi i lati.

2. Una linea incrociata ha un residuo \(0\). Una riga incrociata ha \(\bar{a}_i=0\). Una colonna viene attraversata quando \(\bar{a}_i>0\), e poi \(\bar{x}_{ij}=\bar{d}_j\) e \(\bar{d}_j=0\), o quando la riga \(i\) è l'unica riga attiva con \(\bar{a}_i=0\), e poi ogni colonna attiva ha \(0\) residuo rispetto all'invariante.

3. Conteggio. Una riga viene barrata solo se un'altra riga è attiva, quindi una riga \(r\) non viene mai barrata e la l'algoritmo si interrompe quando le colonne \(n\) vengono cancellate. All'arresto le righe attive hanno \(0\) residuo dall'invariante, e una riga che raggiunge \(0\) senza essere barrata è l'unica riga attiva. Quindi i passaggi sono \((m-1)+n=m+n-1\), una cella ciascuna, tutte diverse, poiché una cella viene scelta in due righe attive e una di queste viene poi barrata.

4. Fattibilità. Alla fine ogni riga e ogni colonna ha un residuo \(0\), quindi \(\bar{\vet{x}} \ge \vet{0}\) soddisfa tutti i vincoli.

5. Albero. Sia \(L_t\) la linea attraversata nel passaggio \(t\): nessuna cella successiva si trova in \(L_t\). All'indietro rispetto all'ultimo passo, le celle dei passi \(t,t+1,\dots\) formano un albero: la cella del passo \(t\) unisce il nuovo nodo \(L_t\) alla sua altra linea, che è ancora attivo, quindi un nodo delle celle successive ovvero la riga \(r\). In \(t=1\) l'albero si estende su tutti i nodi \(m+n\). □

7.3.1 La regola dell'angolo nord-ovest

Esempio 7.5: la regola dell'angolo nord-ovest

Su Esempio 7.1 la regola dell'angolo nord-ovest inizia dalla cella \((1,4)\) e si sposta verso destra o verso il basso. Suo i passaggi sono:

passo	cella	importo	barrato
\(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 di base ammissibile, con le celle 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 è

\[ 1 \cdot 10+9 \cdot 20+4 \cdot 5+2 \cdot 15+2 \cdot 10+6 \cdot 30=440 . \]

Le sei celle base formano l'albero di copertura sottostante, con gli importi sugli archi.

• La regola dell'angolo nord-ovest ignora i costi: in questo caso spedisce unità \(20\) sulla cella \((1,5)\), di costo Unità \(9\) e \(30\) su \((3,7)\), al costo di \(6\).

7.3.2 La regola del costo minimo

Esempio 7.6: la regola del costo minimo

Su Esempio 7.1 la regola del costo minimo sceglie, ad ogni passo, la cella più economica tra le righe attive e colonne:

passo	cella	importo	barrato
\(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\)

• Nel passaggio \(1\) le celle \((1,4)\) e \((3,5)\) costano entrambe \(1\) e \((1,4)\) inizia per prima, poiché la sua riga è più piccola. Al passo \(3\) le celle \((1,6)\), \((2,6)\), \((2,7)\) costano \(2\) e \((1,6)\) vanno per prime.

• Al passo \(4\) è attiva solo la colonna \(7\): prende tutta la fornitura della riga \(2\), quindi le unità \(5\) dalla riga \(1\) e \(5\) dalla riga \(3\).

La soluzione fattibile 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

\[ 1 \cdot 10+2 \cdot 15+3 \cdot 5+2 \cdot 30+1 \cdot 25+6 \cdot 5=170 . \]

Riempiendo una cella per passaggio e cancellando una riga per passaggio si ottiene una soluzione di base fattibile con le celle di base \(m+n-1\). La regola dell'angolo nord-ovest ignora i costi; la regola del costo minimo di solito inizia molto più vicino al valore ottimale (\(170\) invece di \(440\) nell'esempio).

---

Avanti: 7.4 Il metodo potenziale