Home

Federica EU

1/9

Paola Festa » 12.PLI con matrice dei vincoli unimodulare

PLI con matrice dei vincoli unimodulare

Di seguito verranno descritti due problemi di ottimizzazione classici la cui matrice dei coefficienti tecnologici è unimodulare ed il vettore dei termini noti è intero:

il Problema del Trasporto;
il Problema dell’Assegnamento.

Il Problema del Trasporto, 1

Supponiamo che un certo bene M possa essere fornito da $m$ fornitori. Ciascun fornitore $i\in \{1,2,\ldots,m\}$ è in grado di fornire $s_i\in {\mathbb Z}$ unità di M.

Supponiamo che $n$ clienti facciamo richiesta del bene M. Ciascun cliente $j\in\{1,\ldots,n\}$ richiede $d_j\in {\mathbb Z}$ unità di M.

Il costo legato al trasporto di un’unità di bene M dal fornitore $i\in \{1,2,\ldots,m\}$ al cliente $j\in \{1,2,\ldots,n\}$ è indicato con $c_{ij}$ .

Supponiamo, inoltre, che
$\begin{equation} \displaystyle{\sum_{i=1}^m s_i=\sum_{j=1}^n d_j}.\end{equation}$

Obiettivo: minimizzare il costo totale del trasporto dai fornitori ai clienti nel rispetto delle loro rispettive esigenze.

Il Problema del Trasporto, 2

Indicando con $f_{ij}$ la quantità di bene trasportata dal fornitore $i$ al cliente $j,\ i=1,2,\ldots,m,\ j=1,2,\ldots,n,$ il problema del trasporto ha la seguente formulazione matematica

$\begin{array}{llllll}\mbox{{\rm min}}&\displaystyle{\sum_{i=1}^m\sum_{j=1}^n c_{ij}f_{ij}}\\\mbox{{\rm s.a}}\\&\displaystyle{\sum_{i=1}^m f_{ij}}&=&d_j,&j=1,2,\ldots,n& \mbox{(a)}\\&\displaystyle{\sum_{j=1}^n f_{ij}}&=&s_i,& i=1,2,\ldots,m&\mbox{(b)}\\&\ \ f_{ij}\geq 0,&&& i=1,2,\ldots,m,\ j=1,2,\ldots,n.\end{array}$

Il Problema del Trasporto, 3

Si noti che

le variabili di decisione $f_{ij}$ sono $m\times n$ ;
$\displaystyle{\sum_{j=1}^n (a)=\sum_{i=1}^m (b)}$ ;
la matrice dei coefficienti tecnologici $A$ è unimodulare, per cui, anche se le variabili $f_{ij}$ sono solo ristrette in segno, una qualunque soluzione al problema avrà componenti intere.

Il Problema del Trasporto, 4

Inoltre, il grafo rappresentante il Problema del Trasporto è bipartito, come mostrato in Figura.

Grafo bipartito rappresentante il Problema del Trasporto. Disegnata da Paola Festa

Il Problema dell’Assegnamento, 1

Il Problema dell’Assegnamento è un caso speciale del Problema del Trasporto in cui

$m=n$ , cioè il numero di fornitori coincide con il numero di clienti;
$s_i=d_j=1,\ \forall\ i=1,2,\ldots,n,\ j=1,2,\ldots,n$ .

Obiettivo: individuare la corrispondenza 1-a-1 tra fornitori e clienti cui corrisponda il costo totale minimo.

Il Problema dell’Assegnamento, 2

Dunque, il Problema dell’Assegnamento ha la seguente formulazione matematica

$\begin{array}{llllll}\mbox{{\rm min}} &\displaystyle{\sum_{i=1}^n \sum_{j=1}^n c_{ij}f_{ij}}\\\mbox{{\rm s.a}} \\&\displaystyle{\sum_{i=1}^n f_{ij}}&= &1,& j=1,2,\ldots,n &\mbox{(a)}\\&\displaystyle{\sum_{j=1}^n f_{ij}}&=&1,&i=1,2,\ldots,n&\mbox{(b)}\\&\\ f_{ij}\geq0,&&&i=1,2,\ldots,n,\ j=1,2,\ldots,n.\end{array}$

Il Problema dell’Assegnamento, 3

Come per il Problema del Trasporto, la matrice dei vincoli è unimodulare, per cui qualunque soluzione ammissibile al Problema dell’Assegnamento ha componenti intere, più precisamente è un vettore Booleano con il seguente significato:

$\begin{array}{llllll} \mbox{{\rm min}} & \displaystyle{\sum_{i=1}^n \sum_{j=1}^n c_{ij}f_{ij}}\\ \mbox{{\rm s.a}} \\ & \displaystyle{\sum_{i=1}^n f_{ij}} & = & 1, & j=1,2,\ldots,n & \mbox{(a)}\\ & \displaystyle{\sum_{j=1}^n f_{ij}} & = & 1, & i=1,2,\ldots,n& \mbox{(b)}\\ &\ \ f_{ij}\geq 0, & & & i=1,2,\ldots,n,\ j=1,2,\ldots,n. \end{array}$