Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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

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

  1. m=n , cioè il numero di fornitori coincide con il numero di clienti;
  2. 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} \]

Grafo bipartito rappresentante il Problema dell’Assegnamento. Disegnato da Paola Festa

Grafo bipartito rappresentante il Problema dell'Assegnamento. Disegnato da Paola Festa


Il Problema dell’Assegnamento, 4

Come per il Problema del Trasporto, il grafo rappresentante il Problema dell’Assegnamento è bipartito (vedi Figura).

Grafo bipartito rappresentante il Problema dell’Assegnamento. Disegnato da Paola Festa

Grafo bipartito rappresentante il Problema dell'Assegnamento. Disegnato da Paola Festa


I materiali di supporto della lezione

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.

M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.

S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.

S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.

Dispense del Corso di Ricerca Operativa presso l'Università degli Studi di Pisa.

Dispense ed Appunti del Corso prodotte da Paola Festa.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion