Trasporto

P

Ci sono mm fornitori, il fornitore ii offre sis_i unità, e nn clienti, il cliente jj ne chiede djd_j. Spedire un'unità da ii a jj costa cijc_{ij} e fijf_{ij} è la quantità spedita. Si cerca il piano di spedizione di costo minimo in cui ogni cliente riceve esattamente la sua domanda e ogni fornitore spedisce esattamente la sua offerta, con ∑isi=∑jdj\sum_i s_i=\sum_j d_j.

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

Perché è facile

La matrice dei vincoli è la matrice di incidenza del grafo bipartito Km,nK_{m,n} ed è totalmente unimodulare (Teorema 3.2.3). Con offerte e domande intere ogni soluzione di base è intera, quindi basta risolvere con il simplesso il rilassamento continuo, che è una PL.

Da ricordare

  • Se avanza merce (∑isi>∑jdj\sum_i s_i>\sum_j d_j) si aggiunge un cliente fittizio, se ne manca un fornitore fittizio; gli archi fittizi di solito costano 0.
  • Ogni istanza bilanciata ha un ottimo finito (Teorema 3.2.2): fij=sidj/∑isif_{ij}=s_id_j/\sum_i s_i è ammissibile e ogni soluzione ha 0≤fij≤min⁡(si,dj)0\le f_{ij}\le\min(s_i,d_j).
  • Sono intere le soluzioni di base, cioè i vertici: una soluzione ammissibile qualsiasi può essere frazionaria.

Algoritmi

Fonti: dispensa §3.2.2, Teoremi 3.2.2 e 3.2.3, Corollario 3.2.1, appunti Lezione 6, §5, appunti Lezione 1, §8.