Matrice unimodulare

In matematica, una matrice unimodulare è una matrice quadrata con valori interi avente determinante +1 o -1.

Matrice totalmente unimodulare

Una matrice totalmente unimodulare è una matrice (non necessariamente quadrata) per la quale anche ogni minore non singolare è unimodulare. Ne consegue che ogni suo elemento vale 0, +1 o -1.

Un programma intero nel quale la matrice dei vincoli è totalmente unimodulare può essere risolto efficientemente, in quanto il suo rilassamento LP porta a soluzioni intere.

Condizioni sufficienti per la totale unimodularità

Condizioni sufficienti ma non necessarie perché una matrice risulti totalmente unimodulare[1] sono:

Sia A una matrice m x n, le cui righe siano partizionabili in due insiemi disgiunti B e C, con le seguenti proprietà:

• ogni colonna di A contiene al massimo due componenti non nulli;
• ogni componente di A assume il valore di 0, +1 o -1;
• se due componenti non nulle in una colonna di A hanno lo stesso segno, allora la riga di una è nella partizione B e la riga dell'altra nella C;
• se due componenti non nulle in una colonna di A hanno segno opposto, allora le loro righe sono o entrambe in B o entrambe in C.

Quindi ogni minore di A vale 0, +1 o -1.

Esempio

Un esempio di una matrice totalmente unimodulare è il seguente:

${\displaystyle A={\begin{bmatrix}-1&-1&0&0&0&+1\\+1&0&-1&-1&0&0\\0&+1&+1&0&-1&0\\0&0&0&+1&+1&-1\\\end{bmatrix}}}$

Essa costituisce la matrice dei vincoli della formulazione di programmazione lineare (senza vincoli di capacità) del problema del massimo flusso sulla seguente rete:

La precedente matrice A ha le seguenti proprietà:

• tutti suoi valori sono 0,-1 o +1;
• ogni colonna ha al più due valori diversi da 0;
• le colonne con due valori diversi da 0 presentano tali componenti con segni opposti.

Queste proprietà sono sufficienti per aver una matrice totalmente unimodulare (ma non sono proprietà necessarie). Ogni problema di flusso di rete comporta una matrice dei vincoli con le proprietà precedenti (e per questo motivo ogni problema di flusso di rete con capacità intere limitate possiede una soluzione ottimale intera).

Note

1. Teorema dimostrato da A.J. Hofman in appendice a Heller, I. & Tompkins, C.B. (1956), "An Extension of a Theorem of Dantzig's", in Kuhn, H.W. & Tucker, A.W., Linear Inequalities and Related Systems, vol. 38, Annals of Mathematics Studies, Princeton (NJ): Princeton University Press, pp. 247-254

Bibliografia

• Papadimitriou, Christos H.; Steiglitz, Kenneth (1998): Combinatorial Optimization: Algorithms and Complexity, Section 13.2, Dover Publications, ISBN 0-486-40258-4

Voci correlate

• Glossario sulle matrici
• Programmazione lineare intera
• Teoria dei grafi

Collegamenti esterni

• Mathematical Programming Glossary di Harvey J. Greenberg.