• Document: Totale Unimodularità. Sapienza Universitàdi Roma - Dipartimento di Ingegneria Informatica, Automatica e Gestionale.
  • Size: 223.86 KB
  • Uploaded: 2019-02-13 17:24:58
  • Status: Successfully converted


Some snippets from your converted document:

“Sapienza” Sapienza” Università Università di Roma - Dipartimento di Ingegneria Informatica, Automatica e Gestionale Totale Unimodularità Unimodularità Docente: Renato Bruni bruni@dis.uniroma1.it bruni@dis.uniroma1.it Corso di: Ottimizzazione Combinatoria Questa sezione è tratta dal materiale del prof. A. Sassano Come vedere se la Formulazione è Ottima? Problema di PL01: z*= min {cTx : x∈S} ∈Rn: Dx < d} formulazione di S Abbiamo P = {x∈ ∈Rn: Ax < b} = Conv(S) ?? Sarà P = PS = {x∈ Si può rispondere dimostrando che : • Ogni disequazione del sistema Ax < b è implicata dal sistema Dx < d; 3x1+2x2+ x3−2x4 ≤ 2 (1/2) 2x1−2x2-2x3+2x4 ≤ 2 4x1+x2 -x4 ≤ 3 ∈P }∈ • Oppure che argmin {cTx : x∈ ∈S per ogni c∈ ∈Rn • Oppure che ogni vertice di P ha componenti 0-1 Iniziamo da quest’ultimo caso ... Definizioni di Unimodularità Definizione 1: Una matrice A (m× ×n) è detta unimodulare se se per ogni sotto-matrice quadrata B (m× e solo se, ×m) di A (base) si ha det(B)∈{0,1,-1} ×n) di è detta totalmente Definizione 2: Una matrice A (m× se per ogni sotto-matrice quadrata di A unimodulare se e solo se, B (p××p) con p>0 (=1,…,m) si ha det(B)∈{0,1,-1} 3 2 1 1 0 0 1 1 1 1 0 1 1 1 0 1 unimodulare 1 0 1 det(A)=3x1-1x2=1 unimodulare e ma non Non unimodulare totalmente totalmente det(A)=1(1x1-0x1) unimodulare unimodulare -0(1x1-0x0) det(B)∈{0,1,-1} det(B)=3,2,1,1 +1(1x1-1x0)=2) Unimodularità e Interezza TEOREMA 1: Sia A una matrice a componenti intere con rank(A)=m. Allora le seguenti affermazioni sono equivalenti: 1. A è unimodulare; 2. I vertici di P = {x∈Rn: Ax=b , x≥0n } sono interi per ogni vettore b∈∈Zm (intero) 3. Ogni sotto-matrice quadrata B (m××m) non-singolare di A ha una matrice inversa B-1 a componenti intere DIMOSTRAZIONE: L’equivalenza si dimostra provando che: (1 ⇒ 2) (2 ⇒ 3) (3 ⇒ 1) Unimodularità e vertici interi (1 ⇒ 2) A è unimodulare ⇒ Vertici di P interi per b∈ ∈Zm DIMOSTRAZIONE: x° vertice di P = {x∈Rn: Ax=b , x≥0 } n ⇔ x° SBA (Soluzione di Base Ammissibile) ⇔ Esiste B sotto-matrice (m××m) di A con det(B)≠ ≠0  xB ∈ R m  tale che, posto: x =   e A = (B N ) abbiamo: x ∈R n − m   N   x oB   B −1b  Ax = b ⇒ Bx B + Nx N = b x ° =  o  =   ≥ 0n  x  0 +  N   n −m  −1 B B = matrice aggiunta (trasposta dei compl. alg.) di B det(B) A matrice intera (a componenti intere) ⇒ B+ intera A matrice unimodulare ⇒ |det(B)|=1 ⇒ B-1b∈Zm per ogni b∈ ∈Zm ⇒ x°∈Zn per ogni b∈ ∈ Zm Vertici interi e interezza di B-1 (2 ⇒ 3) ∈Zm ⇒ B non-singolare ha B-1 intera Vertici di P interi per b∈ DIMOSTRAZIONE: ≠0 ×m) di A con det(B)≠ - Sia B una sotto-matrice (m× −1 [ ] con B = π 1 π 2 π 3 L π m ( πk colonna di B-1 ) Dimostriamo che una generica colonna πk è intera: intera - Sia t un vettore intero tale che t+πk ≥ 0m - Sia b(t)= Bt+uk (uk k-esimo vettore unitario) unitario  B −1b(t )   B −1 (Bt + uk )   t + B −1uk   t + π k    = =  =   ≥ 0n  0       n −m   0n − m   0n − m   0n − m  ⇒ SBA del sistema Ax=b(t) , x≥ ≥ 0n [per ipotesi] ⇒ Vertice di P = {x∈R : Ax=b(t) , x≥0n } ⇒ n ⇒ t+πk un vettore intero ⇒ πk

Recently converted files (publicly available):