Assegnamento

P

Ci sono nn persone e nn compiti: ogni persona fa un solo compito e ogni compito va a una sola persona. Assegnare la persona ii al compito jj costa cijc_{ij}, e fij=1f_{ij}=1 se ii fa jj. Si cerca l'assegnamento di costo totale minimo.

min⁡ ∑i=1n∑j=1ncijfijs.a. ∑i=1nfij=1j=1,…,n∑j=1nfij=1i=1,…,nfij≥0∀ i,j\begin{aligned} \min\ & \sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}f_{ij}\\ \text{s.a.}\ & \sum_{i=1}^{n}f_{ij}=1 && j=1,\dots,n\\ & \sum_{j=1}^{n}f_{ij}=1 && i=1,\dots,n\\ & f_{ij}\ge 0 && \forall\, i,j \end{aligned}

Perché è facile

È un trasporto con m=nm=n e si=dj=1s_i=d_j=1 sul grafo Kn,nK_{n,n}, quindi la matrice dei vincoli è totalmente unimodulare e le soluzioni di base valgono 0 o 1. Il simplesso sul rilassamento trova l'assegnamento ottimo senza elencare gli n!n! assegnamenti possibili.

Da ricordare

  • Basta il vincolo fij≥0f_{ij}\ge 0: l'interezza viene dalla matrice, non va imposta.
  • In una soluzione di base c'è un solo 1 per riga e per colonna.
  • Far scegliere a ognuno il compito più economico non funziona, perché due persone possono volere lo stesso compito.

Algoritmi

Fonti: dispensa §3.2.2, Esempio 3.2.3, appunti Lezione 6, §6.