Matricea unimodulară

În matematică , o matrice unimodulară este o matrice pătrată cu valori întregi având determinantul 0, +1 sau -1.

Matricea total unimodulară

O matrice total unimodulară este o matrice (nu neapărat pătrată) pentru care fiecare minor non-singular este, de asemenea, unimodular. Rezultă că fiecare dintre elementele sale valorează 0, +1 sau -1.

Un program întreg în care matricea de constrângere este total unimodulară poate fi rezolvată eficient, deoarece relaxarea LP duce la soluții întregi.

Condiții suficiente pentru unimodularitate totală

Condițiile suficiente, dar nu necesare, pentru ca o matrice să fie total unimodulară ^[1] sunt:

Fie A o matrice mxn , ale cărei rânduri sunt partiționabile în două seturi disjuncte B și C , cu următoarele proprietăți:

fiecare coloană din A conține cel mult două componente nenule;
fiecare componentă a lui A ia valoarea 0, +1 sau -1;
dacă două componente diferite de zero dintr-o coloană A au același semn, atunci rândul unuia este în partiția B și rândul celuilalt în C ;
dacă două componente diferite de zero dintr-o coloană A au semne opuse, atunci rândurile lor sunt fie în B, fie ambele în C.

Deci orice mai mic decât A valorează 0, +1 sau -1.

Exemplu

Un exemplu de matrice total unimodulară este următorul:

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}}

{\ 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}}}

{\ 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}}}

Constituie matricea de constrângere a formulării de programare liniară (fără constrângeri de capacitate) a problemei debitului maxim pe următoarea rețea:

Matricea A anterioară are următoarele proprietăți:

toate valorile sale sunt 0, -1 sau +1;
fiecare coloană are cel mult două valori, altele decât 0;
coloanele cu alte două valori decât 0 au aceste componente cu semne opuse.

Aceste proprietăți sunt suficiente pentru a avea o matrice total unimodulară (dar nu sunt proprietăți necesare). Fiecare problemă de flux de rețea implică o serie de constrângeri cu proprietățile precedente (și din acest motiv, fiecare problemă de flux de rețea cu capacități întregi limitate are o soluție de număr întreg optim).

Notă

^ Teorema dovedită de AJ Hofman în apendicele la Heller, I. & Tompkins, CB (1956), "An Extension of a Theorem of Dantzig's", în Kuhn, HW & Tucker, AW, Linear Inequalities and Related Systems, vol. 38, Annals of Mathematics Studies, Princeton (NJ): Princeton University Press, pp. 247-254

Bibliografie

Papadimitriou, Christos H.; Steiglitz, Kenneth (1998): Optimizare combinatorie: algoritmi și complexitate , secțiunea 13.2, Publicații Dover, ISBN 0-486-40258-4

Elemente conexe

linkuri externe

Glosar de programare matematică a lui Harvey J. Greenberg.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Teorema dovedită de AJ Hofman în apendicele la Heller, I. & Tompkins, CB (1956), "An Extension of a Theorem of Dantzig's", în Kuhn, HW & Tucker, AW, Linear Inequalities and Related Systems, vol. 38, Annals of Mathematics Studies, Princeton (NJ): Princeton University Press, pp. 247-254

[1]