In matematica, una matrice unimodulare è una matrice quadrata con valori interi avente determinante +1 o -1.
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 ma non necessarie perché una matrice risulti totalmente unimodulare sono:
Sia A una matrice m x n, le cui righe siano partizionabili in due insiemi disgiunti B e C, con le seguenti proprietà:
Quindi ogni minore di A vale 0, +1 o -1.
Un esempio di una matrice totalmente unimodulare è il seguente:
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à:
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).