TD18 : Matrices totalement unimodulaires

Énoncé

Matrices TUM

1.

Matrices TUM :

toute matrice carrée extraite est de déterminant $∈ \lbrace -1, 0, 1 \rbrace$

$x= (x_1, ⋯ , x_n)$

But : minimiser $c \cdot x$

tel que

A x = b \text{ et } x ≥ 0
  • $A ∈ℤ^{m×n}$
  • $b ∈ ℤ^n$
  • $c ∈ ℤ^n$

On sait que tous les coefficients de $A$ sont $0, 1$ ou $-1$ (cf. les sous-matrices (1,1)).

Donc on prend $B⊆ \lbrace 1, \ldots, n \rbrace$ une base.

On sait que si le problème a une solution optimale $x^\ast$ alors il existe une base $B$ telle que

A_B x_B = b

$A_B$ est une matrice carrée obtenue à partir de $A$ en ne gardant que les colonnes dans $B$.

Règle de Cramer :

x_B(i) = \frac{\det ({A_B}_i)}{\det A_B}

où ${A_B}_i$ est la matrice obtenue à partir de $A_B$ en remplaçant la $i$-ème colonne par $b$.

On sait que $\det A_B ≠ 0$ (car il existe une solution) et par conséquent $\det A_B ∈ \lbrace -1, 1 \rbrace$ (car $A_B$ est extraite de $A$ qui est TUM).

Donc $x_B(i)$ est entier pour tout $i$.

Donc la solution optimale, si elle existe, est entière (dès que $A$ est TUM).

Partie 1

On suppose que toute matrice a ses coefficients dans $\lbrace 0, -1, 1 \rbrace$ et a au plus deux coefficients non nuls par colonne.

Une partition admissible des lignes $I = I’ \sqcup I’’$ :

dans une colonne $j$, deux coefficients $(i, j)$ et $(i’, j)$ non nuls vérifient :

  1. s’ils sont de même signe : l’un appartient à $I’$ ssi l’autre appartient à $I’’$

  2. s’ils sont de signes différents : l’un appartient à $I’$ ssi l’autre appartient à $I’$

On suppose qu’il existe une partition admissible.

2.

Si toute colonne de $A_1$ a deux coefficients non nuls.

Alors les $(A[i, -])_i$ sont liés.

Il suffit de sommer les lignes dont les indices appartiennent au même bloc ($I’$ ou $I’’$), puisque leurs coefficients sont deux-à-deux de signes différents (donc opposés), et de faire leur différence si leurs indices appartiennent à deux blocs différents, puisque leurs coefficients sont deux-à-deux de même signe (donc égaux).

Donc en posant

  • $𝜆_i = 1$ si $i ∈ I’$
  • $𝜆_i = -1$ si $i ∈ I’’$

il vient que

\sum\limits_{ i } 𝜆_i A[i, -] = 0

3.

On montre par réc sur $\dim A_1$ que $\det A_1 ∈ \lbrace 0, 1, -1 \rbrace$.

  • si $\dim A_1 = 1$ : trivial, car $A_1$ est TUM

  • si $\dim A_1 = n+1$ :

    • Sous-Cas 1 : $A_1$ a une colonne avec $0$ coefficients non nuls, alors $\det A_1 = 0$

    • Sous-Cas 2 : $A_1$ a une colonne avec exactement $1$ coefficient non nul en colonne $j$ : alors

      \det A_1 = \sum\limits_{ i=1 }^n a_{i,j} \det A_{i, j} = \underbrace{a_{i,j}}_{=1} \det (A_{i, j})

      et on conclut par hypothèse de réc sur $A_{i, j}$.

    • Sous-Cas 3 : toutes les colonnes de $A_1$ ont exactement $2$ coefficients non nuls : alors en appliquant le résultat de la question précédente, les lignes de $A$ sont liées, et $\det A_1 = 0$

Donc s’il y a une partition admissible, $A_1$ est TUM.

$G = (V,E,c), c : E ⟶ ℕ^\ast$

Minimiser

\sum\limits_{ (i,j)∈E } c(i,j) x_{i,j}

tel que

∀(i, j) ∈ E, \begin{cases} x_{i,j} - x_i + x_j ≥ 0 && (i)\\ x_s - x_t ≥ 1 &&(ii) \end{cases}

Applications

4.

Montrons qu’il existe une solution optimale : il suffit d’exhiber une solution, puisque les variables sont positives.

Une solution possible est :

  • $x_t = 0$
  • $x_i = 1$ pour tout $i≠t$
  • $x_{i, j} = 1$

5.

Il existe une solution optimale telle que

x_s ≥ x_i ≥ x_t

et

x_{i, j} = \max(x_i-x_j, 0)

Montrons la deuxième égalité :

  • Cas 1 : si $x_i - x_j ≤ 0$ : alors en posant $x_{i,j}=0$, $(i)$ reste vérifié.

  • Cas 2 : si $x_i - x_j ≥ 0$ : le plus petit $x_{i,j}$ pour satisfaire $(i)$ est $x_i-x_j$.

Comme $c(i,j) ∈ ℕ$ et $x_{i,j}≥0$, on veut minimiser $x_{i,j}$.

Pour tous les $x_i > x_s$ et $x_t > x_i$, on a un meilleur coût.

Soit $c_{i, j}$ est égal à $0$, et il reste à $0$, soit $c_{i,j} > 0$, et il passe à $0$ ($x_i > x_j > x_s$ ou $x_t > x_i > x_s$); soit $c_{i,j}>0$ et il diminue $x_i > x_s > x_j$.

L’observation à faire est que $c_{s,i} = \max(x_s - x_i, 0)$. Mais si $x_i > x_s$, alors $c_{s,i} = 0$.

Et idem pour $x_t$.

6.

Si $x_t > 0$, alors on peut prendre la solution

x'_i = x_i - x_t

(on enlève $x_t$ partout) et les coûts $x_{i,j} = \max(x_i - x_j, 0)$ restent inchangés.

Si $x_s > 1$, on prend

x''_i = \frac{x_i}{x_s}

et alors on diminue les coûts, qui sont divisés par $x_s$.

Donc on peut supposer que $x_t = 0, x_s = 1$

7.

Montrons qu’on peut prendre les $x_i$ à valeurs entières.

Avec $x_s = 1, x_t = 0$, on a le système suivant :

\underbrace{(I \mid A')}_{ ≝ A} x = 0

  • $x = (x_{i, j} \mid x_1 ⋯ x_n){}^t$

  • à la ligne correspondant à $x_{i,j}$ : la colonne $i$ de $A$ vaut $-1$ , la colonne $j$ de $A$ vaut $+1$

Il suffit de montrer que $A$ est TUM pour avoir des solutions entières.

Or, $A’^t$ est TUM car il existe une partition admissible : $I’ = I, I’’ = ∅$ comme partition des indices de lignes de $A’^t$ (car chaque colonne de $A’^t$ contient un coefficient non nul $=1$ et un coefficient non nul $=-1$), et par la partie précédente, $A’^t$ est TUM, d’où $A’$ est TUM, et enfin $A$ est TUM (facile à montrer par définition de $A$ et comme $A’$ est TUM).

Donc d’après l’exercice 1, il existe des solutions entières.

On a

1 = x_s ≥ x_i ≥ x_t = 0

et $x_i$ entiers.

Ce problème correspond à la $s-t$ coupe minimale : les $x_i = 1$ sont dans le bloc de $s$, les $x_i =0$ sont dans le bloc de $t$.

Pour que

x_{i, j} = \max (x_i - x_j, 0)

soit $>0$, il faut et il suffit que $x_i$ soit dans le bloc de $s$, et $x_t$ dans le bloc de $t$.

Comme on veut minimiser les $x_{i,j}$, on cherche bien à minimiser une $s-t$ coupe.

9.

Minimiser $c \cdot x$ tel que

∀i∈ I, \quad A[i, -] x = b_i \\ ∀i∈ I', A[i, -] x ≥ b_i \\ ∀j ∈ J, x_j ≥ 0
  • $J’ \sqcup J$ est une partition des colonnes de la matrice
  • $I’ \sqcup I$ est une partition des lignes de la matrice

Maximiser $y \cdot b$ tel que

∀j ∈ J, y A[-, j] ≤ c_j \\ ∀j ∈ J', y A[-, j] = c_j \\ ∀i ∈ I', y_i ≥ 0

On veut maximiser $y_{s, t}$ (flot maximum de $s$ vers $t$), tel que

0 ≤ \underbrace{y_{i, j}}_{\text{ borne la capacité de chaque arc}} ≤ c_{i,j}

Pour chaque noeud $i$ :

- \sum\limits_{ (i,j) ∈ E } y_{i, j} + \sum\limits_{ (j,i) ∈E } y_{j,i} = 0

(équation de flot)

Le théorème de dualité forte nous dit qu’il y a une solution optimale au premier problème ssi il y a une au second, et les valeurs optimales coïncident.

La valeur du $s-t$ flot maximal est égal à la valeur de la $s-t$ coupe minimale.

Leave a Comment