Matrice unimodulare
Da Wikipedia, l'enciclopedia libera.
In matematica, una matrice unimodulare è una matrice quadrata con determinante +1 o -1.
Una matrice totalmente unimodulare è una matrice unimodulare per la quale anche ogni sottomatrice quadrata non singolare è unimodulare.
Un programma intero nel quale la matrice dei vincoli è totalmente unimodulare può essere risolto efficentemente, in quanto il suo rilassamento LP porta a soluzioni intere.
Un esempio di una matrice totalmente unimodulare
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à:
- tutte le sue entrate sono 0,-1 o +1;
- ogni colonna ha al più due entrate diverse da 0;
- le colonne con due entrate diverse 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).
Vedi anche:
[modifica] Collegamenti esterni
[http://carbon.cudenver.edu/~hgreenbe/glossary/second.php?page=U.html Mathematical Programming Glossary] by Harvey J. Greenberg.
Bibliografia
Papadimitriou, Christos H.; Steiglitz, Kenneth (1998): Combinatorial Optimization: Algorithms and Complexity, Section 13.2, Dover Publications, ISBN 0-486-40258-4
