7.5 Il problema di assegnamento¶
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
Definizione 7.14: problema di assegnamento
Ci sono \(n\) lavoratori, le origini \(P=\{1,2,\dots,n\}\), e \(n\) lavori, le destinazioni \(D=\{n+1,n+2,\dots,2n\}\); \(c_{ij}\) è il costo di assegnare il lavoratore \(i\) al lavoro \(j\). Un assegnamento dà a ogni lavoratore esattamente un lavoro e ogni lavoro a esattamente un lavoratore. Il problema di assegnamento chiede un assegnamento di costo totale minimo.
- Usiamo una variabile binaria \(x_{ij}\) per ogni coppia \(i \in P\), \(j \in D\), uguale a \(1\) se il lavoratore \(i\) riceve il lavoro \(j\).
Con queste variabili, un modello di programmazione lineare intera (ILP) per il problema di assegnamento è il seguente:
Questo modello è detto modello \(\mathrm{AP}\).
-
Descrizione della funzione obiettivo e dei vincoli del modello \(\mathrm{AP}\):
-
la funzione obiettivo \(\eqref{ta:aobj}\) minimizza il costo totale dell'assegnamento;
-
i vincoli \(\eqref{ta:arow}\) danno a ogni lavoratore esattamente un lavoro;
-
i vincoli \(\eqref{ta:acol}\) danno ogni lavoro a esattamente un lavoratore;
-
infine, i vincoli \(\eqref{ta:adom}\) definiscono le variabili binarie del modello.
-
-
Una matrice \(n \times n\) con elementi in \(\{0,1\}\) ed esattamente un \(1\) in ogni riga e in ogni colonna è una matrice di permutazione. Le soluzioni ammissibili del modello \(\mathrm{AP}\) sono le matrici di permutazione: ci sono \(n!\) assegnamenti.
Proposizione 7.15: il rilassamento LP del modello di assegnamento
Il rilassamento LP del modello \(\mathrm{AP}\), con \(x_{ij} \ge 0\) al posto di \(\eqref{ta:adom}\), è il modello \(\mathrm{TP}\) con \(a_i=1\) e \(d_j=1\). I suoi vertici sono matrici di permutazione, e ha una soluzione ottima che è un assegnamento.
Dimostrazione
I vincoli \(\eqref{ta:arow}\) e \(\eqref{ta:acol}\) sono i vincoli (7.1b) e (7.1c) con offerte e domande unitarie, e l'istanza è bilanciata, con totale \(n\). Per la Proposizione 7.2 ha una soluzione ottima in un vertice, e ogni vertice è intero per il Teorema «vertici interi» del Capitolo 4. Una soluzione ammissibile intera ha \(0 \le x_{ij} \le 1\), perché \(x_{ij}\) è al più la somma della sua riga: è una matrice di permutazione. □
Esempio 7.9: quattro lavoratori e quattro lavori
Quattro lavoratori \(1,2,3,4\) e quattro lavori \(5,6,7,8\) hanno i costi
I \(4!=24\) assegnamenti, enumerati, hanno un unico minimo: il lavoratore \(1\) riceve il lavoro \(7\), il lavoratore \(2\) il lavoro \(8\), il lavoratore \(3\) il lavoro \(6\), il lavoratore \(4\) il lavoro \(5\), con costo \(3+1+6+1=11\). Gurobi dà lo stesso assegnamento come soluzione ottima del rilassamento LP.
7.5.1 Degenerazione del metodo dei potenziali¶
-
Una base del rilassamento LP ha \(2n-1\) celle, ma un assegnamento ha solo \(n\) celle con \(x_{ij}=1\): ogni soluzione ammissibile di base ha \(n-1\) celle di base con valore \(0\), ed è degenere.
-
Il metodo dei potenziali risolve il rilassamento LP, ma molti suoi pivot hanno \(\theta=0\). Sull'Esempio 7.9 la regola dell'angolo nord-ovest dà la base qui sotto, con tre zeri di base; da questa base il metodo dei potenziali arriva all'ottimo dopo \(6\) pivot, \(4\) dei quali degeneri.
| \(\bar{x}_{ij}\) | \(5\) | \(6\) | \(7\) | \(8\) | \(a_i\) |
|---|---|---|---|---|---|
| \(1\) | \(1\) | \(1\) | |||
| \(2\) | \(0\) | \(1\) | \(1\) | ||
| \(3\) | \(0\) | \(1\) | \(1\) | ||
| \(4\) | \(0\) | \(1\) | \(1\) | ||
| \(d_j\) | \(1\) | \(1\) | \(1\) | \(1\) |
7.5.2 Riduzioni e potenziali¶
Lemma 7.16: costi ridotti di un assegnamento
Dati i potenziali \(\vet{\pi}\), sia \(\bar{c}_{ij}=c_{ij}-\pi_i+\pi_j\). Per ogni \(\vet{x}\) che soddisfa \(\eqref{ta:arow}\) e \(\eqref{ta:acol}\),
Quindi sottrarre una costante da una riga o da una colonna della matrice dei costi cambia il costo di ogni assegnamento della stessa costante, e gli assegnamenti ottimi non cambiano.
Dimostrazione
È l'identità della Sezione 7.4 con \(a_i=d_j=1\). Sottrarre \(r\) dalla riga \(i\) dà i costi ridotti di \(\pi_i=r\) con gli altri potenziali uguali a \(0\); sottrarre \(s\) dalla colonna \(j\) dà quelli di \(\pi_j=-s\). □
Corollario 7.17: gli assegnamenti a costo ridotto nullo sono ottimi
Se \(\bar{c}_{ij} \ge 0\) per ogni cella e un assegnamento usa solo celle con \(\bar{c}_{ij}=0\), allora è ottimo, anche per il rilassamento LP, il suo costo è \(\sum_{i \in P}\pi_i-\sum_{j \in D}\pi_j\), e \(\vet{\pi}\) è ottima per il duale del rilassamento LP, il modello \(D(\mathrm{TP})\) con \(a_i=d_j=1\).
Dimostrazione
Per il Lemma 7.16, l'assegnamento costa \(\sum_{i \in P}\pi_i-\sum_{j \in D}\pi_j\), e ogni \(\vet{x} \ge \vet{0}\) che soddisfa \(\eqref{ta:arow}\) e \(\eqref{ta:acol}\) costa almeno altrettanto, perché \(\bar{c} \ge 0\). I potenziali soddisfano \(\pi_i-\pi_j \le c_{ij}\) con lo stesso valore, quindi sono ottimi per la dualità debole. □
7.5.3 Zeri indipendenti e linee¶
Definizione 7.18: zeri indipendenti e coperture
Sia \(\bar{c}\) una matrice \(n \times n\) con elementi non negativi. Un insieme di elementi nulli è indipendente se due di essi non stanno mai nella stessa riga o nella stessa colonna. Un insieme di linee, righe e colonne, copre gli zeri se ogni elemento nullo sta in almeno una delle linee.
-
\(n\) zeri indipendenti formano un assegnamento di costo ridotto nullo, ottimo per il Corollario 7.17.
-
Nella rete bipartita i cui archi sono le celle con \(\bar{c}_{ij}=0\), un insieme di zeri indipendenti è un matching, cioè un insieme di archi senza estremi in comune, come nel Capitolo 5 «Flusso massimo», e una copertura è un insieme di nodi che tocca ogni arco.
Teorema 7.19: König ed Egerváry
Il numero massimo di zeri indipendenti di una matrice è uguale al numero minimo di linee che coprono tutti i suoi zeri.
Dimostrazione
Sia \(M\) un insieme massimo di zeri indipendenti. Una riga o una colonna è accoppiata se contiene uno zero di \(M\).
-
Linee \(\ge\) zeri. Gli zeri di \(M\) stanno in righe e colonne diverse, quindi una linea ne contiene al più uno, e una copertura richiede almeno \(|M|\) linee.
-
Cammini alternanti. Un cammino alternante parte da una riga non accoppiata, va da una riga a una colonna attraverso uno zero non in \(M\), e da una colonna a una riga attraverso lo zero di \(M\) di quella colonna. Siano \(R\) e \(K\) le righe e le colonne raggiunte da cammini alternanti, comprese le righe non accoppiate.
-
Ogni colonna di \(K\) è accoppiata. Altrimenti un cammino alternante termina in una colonna non accoppiata. Lungo di esso, gli zeri non in \(M\) sono uno in più degli zeri di \(M\): scambiandoli si ottiene un insieme indipendente con \(|M|+1\) zeri, contro la massimalità di \(M\).
-
Le linee. Sia \(L\) l'insieme delle righe non in \(R\) e delle colonne in \(K\). Uno zero \((i,j)\) con riga \(i \in R\) ha colonna \(j \in K\): se non è in \(M\), un cammino fino a \(i\) prosegue fino a \(j\); se è in \(M\), la riga \(i\) è accoppiata, quindi è stata raggiunta dalla sua colonna \(j\). Quindi \(L\) copre tutti gli zeri.
-
Conteggio. Le righe non in \(R\) sono accoppiate, perché le righe non accoppiate stanno in \(R\), e le colonne di \(K\) sono accoppiate. Uno zero di \(M\) in una colonna di \(K\) ha la sua riga in \(R\), quindi sta esattamente su una linea di \(L\). Linee e zeri di \(M\) si corrispondono uno a uno, e \(|L|=|M|\). □
- La dimostrazione è costruttiva: dà le linee di una copertura minima a partire da un insieme massimo di zeri indipendenti, e un insieme che non è massimo si allarga lungo un cammino alternante che termina in una colonna non accoppiata.
7.5.4 L'algoritmo ungherese¶
Algoritmo: L'algoritmo ungherese
STOP: \(M\) è un assegnamento ottimo.-
Regola degli esempi. Al Passo 1 l'insieme \(M\) si costruisce riga per riga, in ordine crescente: ogni riga cerca un cammino alternante verso una colonna non accoppiata, in profondità, provando le colonne in ordine crescente.
-
L'algoritmo è dovuto a H. W. Kuhn (1955), che lo chiamò così in onore dei matematici ungheresi D. König e J. Egerváry.
Teorema 7.20: correttezza dell'algoritmo ungherese
A ogni iterazione \(\bar{c}_{ij}=c_{ij}-\pi_i+\pi_j \ge 0\) per ogni cella, e il Passo 3 aumenta il valore duale \(\sum_{i \in P}\pi_i-\sum_{j \in D}\pi_j\) di \(\delta\,(n-k)>0\), dove \(k<n\) è il numero di linee. Con costi interi l'algoritmo si ferma dopo un numero finito di iterazioni con un assegnamento ottimo, e \(\vet{\pi}\) è ottima per il duale del rilassamento LP.
Dimostrazione
-
Passo 0. Sottrarre il minimo di una riga lascia elementi non negativi e uno zero nella riga; i minimi di colonna sono allora \(\ge 0\), e sottrarli mantiene gli elementi non negativi. Per costruzione \(\bar{c}_{ij}=c_{ij}- \pi_i+\pi_j\).
-
Passo 3. Tutti gli zeri sono coperti, quindi \(\delta>0\), e gli elementi non coperti restano \(\ge 0\). L'aggiornamento dei potenziali dà \(-\delta\) su riga e colonna non coperte, \(-\delta+\delta=0\) su riga non coperta e colonna coperta, \(+\delta\) su riga e colonna coperte, \(0\) su riga coperta e colonna non coperta: esattamente l'aggiustamento.
-
Valore duale. Con \(k_r\) righe coperte e \(k_c\) colonne coperte, il valore cresce di \(\delta\,(n-k_r)-\delta\,k_c=\delta\,(n-k)\), e \(k=|M|<n\) per il Teorema 7.19.
-
Terminazione. Per il Lemma 7.16 il valore duale non supera mai il costo di un assegnamento. Con costi interi ogni \(\delta\) è un intero \(\ge 1\), quindi il numero di aggiustamenti è finito. All'arresto \(M\) è un assegnamento di zeri, ottimo con \(\vet{\pi}\) per il Corollario 7.17. □
7.5.5 L'algoritmo ungherese sull'esempio¶
Esempio 7.10: l'algoritmo ungherese
Eseguiamo l'algoritmo sull'Esempio 7.9.
Passo 0. I minimi di riga sono \(2,1,2,1\), quindi \(\pi_1=2\), \(\pi_2=1\), \(\pi_3=2\), \(\pi_4=1\), e le righe diventano
I minimi di colonna sono \(0,2,0,0\): cambia solo la colonna \(6\), e \(\pi_6=-2\). Il valore duale \(2+1+2+1+2=8\) è un lower bound sul costo di ogni assegnamento.
In ciascuna delle matrici che seguono gli zeri indipendenti sono riquadrati, le linee sono blu e la cella di \(\delta\) è rossa; i potenziali sono sui margini.
| Iterazione 1 | |||||
|---|---|---|---|---|---|
| \(\bar{c}_{ij}\) | \(5\) | \(6\) | \(7\) | \(8\) | \(\pi_i\) |
| \(1\) | \(0\) | \(\boxed{0}\) | \(1\) | \(3\) | \(2\) |
| \(2\) | \(3\) | \(5\) | \(\boxed{0}\) | \(0\) | \(1\) |
| \(3\) | \(\boxed{0}\) | \(2\) | \(7\) | \(4\) | \(2\) |
| \(4\) | \(0\) | \(6\) | \(7\) | \(5\) | \(1\) |
| \(\pi_j\) | \(0\) | \(-2\) | \(0\) | \(0\) | |
-
Un insieme massimo di zeri indipendenti (riquadrati) ha \(3\) elementi: \((1,6)\), \((2,7)\), \((3,5)\).
-
Le \(3<4\) linee (blu) sono le righe \(1\) e \(2\) e la colonna \(5\).
-
Il minimo elemento non coperto è \(\delta=2\), nella cella \((3,6)\) (rossa). Lo sottraiamo dagli elementi non coperti e lo aggiungiamo agli elementi coperti due volte: \(\pi_i\) cresce di \(2\) per le righe non coperte \(3\) e \(4\), 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\) | \(2\) | \(\boxed{0}\) | \(1\) | \(3\) | \(2\) |
| \(2\) | \(5\) | \(5\) | \(\boxed{0}\) | \(0\) | \(1\) |
| \(3\) | \(\boxed{0}\) | \(0\) | \(5\) | \(2\) | \(4\) |
| \(4\) | \(0\) | \(4\) | \(5\) | \(3\) | \(3\) |
| \(\pi_j\) | \(2\) | \(-2\) | \(0\) | \(0\) | |
-
Un insieme massimo di zeri indipendenti (riquadrati) ha \(3\) elementi: \((1,6)\), \((2,7)\), \((3,5)\).
-
Le \(3<4\) linee (blu) sono la riga \(2\) e le colonne \(5\) e \(6\).
-
Il minimo elemento non coperto è \(\delta=1\), nella cella \((1,7)\) (rossa). Lo sottraiamo dagli elementi non coperti e lo aggiungiamo agli elementi coperti due volte: \(\pi_i\) cresce di \(1\) per le righe non coperte \(1\), \(3\) e \(4\), e \(\pi_j\) cresce di \(1\) per le colonne coperte \(5\) e \(6\). Il valore duale cresce di \(1\cdot(4-3)=1\).
| Iterazione 3 | |||||
|---|---|---|---|---|---|
| \(\bar{c}_{ij}\) | \(5\) | \(6\) | \(7\) | \(8\) | \(\pi_i\) |
| \(1\) | \(2\) | \(0\) | \(\boxed{0}\) | \(2\) | \(3\) |
| \(2\) | \(6\) | \(6\) | \(0\) | \(\boxed{0}\) | \(1\) |
| \(3\) | \(0\) | \(\boxed{0}\) | \(4\) | \(1\) | \(5\) |
| \(4\) | \(\boxed{0}\) | \(4\) | \(4\) | \(2\) | \(4\) |
| \(\pi_j\) | \(3\) | \(-1\) | \(0\) | \(0\) | |
-
Un insieme massimo di zeri indipendenti (riquadrati) ha \(4\) elementi: \((1,7)\), \((2,8)\), \((3,6)\), \((4,5)\).
-
Formano un assegnamento di costo ridotto nullo: l'algoritmo si ferma, e l'assegnamento è ottimo.
-
L'assegnamento ottimo è \(1 \to 7\), \(2 \to 8\), \(3 \to 6\), \(4 \to 5\), con costo \(3+1+6+1=11\), l'unico ottimo dell'Esempio 7.9.
-
I potenziali finali \(\pi_1=3\), \(\pi_2=1\), \(\pi_3=5\), \(\pi_4=4\) e \(\pi_5=3\), \(\pi_6=-1\), \(\pi_7=0\), \(\pi_8=0\) sono una soluzione duale ottima, di valore \((3+1+5+4)-(3-1+0+0)=11\). Il valore duale è cresciuto da \(8\) a \(10\) e poi a \(11\).
-
Le linee sono quelle della dimostrazione del Teorema 7.19. Nell'iterazione \(1\) la riga \(4\) non è accoppiata; da essa un cammino alternante raggiunge la colonna \(5\) attraverso il suo zero, e poi la riga \(3\), accoppiata alla colonna \(5\). Quindi \(R=\{3,4\}\), \(K=\{5\}\), e le linee sono le righe \(1\), \(2\) e la colonna \(5\).
Il problema di assegnamento è un problema di trasporto con offerte e domande unitarie, sul quale il metodo dei potenziali fa molti pivot degeneri. L'algoritmo ungherese mantiene \(\bar{c}_{ij}=c_{ij}-\pi_i+\pi_j \ge 0\), copre gli zeri con il numero minimo di linee (König–Egerváry) e aumenta il valore duale finché \(n\) zeri indipendenti danno un assegnamento ottimo.
7.6 Errori tipici¶
Attenzione
-
Risolvere un'istanza non bilanciata così com'è. Con più offerta che domanda i vincoli di uguaglianza non hanno soluzione: aggiungere una destinazione fittizia a costi nulli, oppure un'origine fittizia quando la domanda supera l'offerta.
-
Togliere uno zero di base. Una base degenere ha comunque \(m+n-1\) celle; senza la cella di valore \(0\) l'albero è sconnesso e i potenziali non si possono calcolare.
-
Prendere come base un insieme con un ciclo. \(m+n-1\) celle sono una base solo se non contengono un cammino chiuso che alterna righe e colonne.
-
Mescolare le convenzioni di segno. Qui \(\bar{c}_{ij}=c_{ij}-\pi_i+\pi_j\) con \(\pi_i-\pi_j=c_{ij}\) sulle celle di base; con \(u_i+v_j=c_{ij}\) i potenziali delle destinazioni cambiano segno.
-
Calcolare \(\theta\) su tutte le celle del ciclo. \(\theta\) è il minimo sulle sole celle con segno \(-\); la cella entrante riceve \(\theta\).
-
Coprire gli zeri con troppe linee. Le linee dell'algoritmo ungherese devono essere una copertura minima, tante quanti gli zeri indipendenti; con più linee \(\delta\) può essere sbagliato o si può mancare l'arresto.
-
Dimenticare gli elementi coperti due volte. Al Passo 3 dell'algoritmo ungherese \(\delta\) si sottrae dagli elementi non coperti e si aggiunge a quelli coperti da una riga e da una colonna.
-
Eseguire gli algoritmi sui profitti. Gli algoritmi minimizzano: con profitti \(p_{ij}\) da massimizzare, usare i costi \(c_{ij}=-p_{ij}\), oppure \(c_{ij}=p_{\max}-p_{ij}\) con \(p_{\max}\) il profitto più grande, per tenerli non negativi.
7.7 In sintesi¶
In sintesi
-
Il modello \(\mathrm{TP}\) spedisce le offerte \(a_i\) di \(m\) origini alle domande \(d_j\) di \(n\) destinazioni; è un modello \(\mathrm{MCF}\) sulla rete bipartita completa, ammissibile esattamente quando è bilanciato.
-
Un'istanza di trasbordo senza capacità diventa un'istanza di trasporto con le distanze come costi.
-
Una base è un albero ricoprente della rete bipartita, con \(m+n-1\) celle; la sua soluzione di base si trova foglia per foglia ed è intera per dati interi.
-
Le regole dell'angolo nord-ovest e del costo minimo costruiscono una soluzione ammissibile di base, una linea per passo.
-
Il metodo dei potenziali: potenziali con \(\bar{c}_{ij}=0\) sulla base e \(\pi_{m+n}=0\); ottimo quando \(\bar{c} \ge 0\); altrimenti \(\theta\) unità si spostano lungo il ciclo della cella entrante, e il costo scende di \(\theta\,|\bar{c}_e|\).
-
Il modello \(\mathrm{AP}\) è un modello \(\mathrm{TP}\) con dati unitari; l'algoritmo ungherese riduce righe e colonne, copre gli zeri con un numero minimo di linee (König–Egerváry) e aggiusta di \(\delta\), aumentando il valore duale.
Le istanze in breve.
| magazzini e negozi | nord-ovest \(440\), costo minimo \(170\), ottimo \(165\) |
| metodo dei potenziali | \(4\) pivot dal nord-ovest, \(1\) dal costo minimo |
| potenziali ottimi | \(\tilde{\vet{\pi}}=(3,2,5,2,4,1,0)\), con \(\pi_7=0\) |
| con \(a_1=40\) | destinazione fittizia \(8\), ottimo \(155\) |
| istanza degenere | \(\theta=0\), poi \(\theta=5\); ottimo \(235\) |
| trasbordo, senza capacità | ottimo \(49\) |
| lavoratori e lavori | lower bound \(8\), \(\delta=2\), \(\delta=1\), ottimo \(11\) |
Esercizi su questo capitolo: Trasporto e assegnamento