Solutions
474
On peut donc affec ter le zéro (A, a) mar qué ①, ce qui
entraîne la sup pres sion de quatre zéros. Il reste alors un
seul zéro dans les lignes Β et D.
On peut alors affec ter le zéro (B, c) mar qué ②, ce qui entraîne
la sup pres sion d’un autre zéro. Il ne reste plus alors qu’un
zéro sur cha cune des lignes C et D. On peut donc affec ter le
zéro (C, d) mar qué ③, ce qui entraîne la sup pres sion du der -
nier zéro figu rant encore dans la matrice.
Si l’on appli que alors le mar quage hon grois, on voit que
l’on peut mar quer toutes les lignes et toutes les colonnes... alors que le pro blème n’est
pas résolu. C’est que l’on a affaire à un cou plage non maximal, ainsi que le prouve le
fait que, sur le réseau de trans port associé à ce tableau, on peut mar quer S :
A
O
a
b
+b
+O
+D
-a
S
c
d
D
C
B
+A
L’amé lio ra tion du cou plage, par la chaîne ODaAbS donne l’une des trois solu tions opti -
males équi va lentes : A S b ; B S c ; C S d ; D S a . Les 2 autres solutions optimales sont :
3A b ; Ba ; Cc ; Dd4 et 3Ab ; Bc ; Ca ; Dd4 .
4.14 1) Il s’agit d’un pro blème de tran sport clas sique. On prend comme unité la cen taine de
tonnes. On rap pelle que, si ;
x 11 , x 12 , c , x 16 , x 21 , x 22 , c , x 26 , c , x 41 , x 42 , c , x 46
sont les quan ti tés à tran spor ter des ori gines 1, 2, c , 4 aux des ti nations 1, 2, 3, c , 6 on a :
x 11 1 x 12 1 c 1 x 16 5 5
x 21 1 x 22 1 c 1 x 26 5 6
4 équa tions en ligne :
cccccccccc
x 41 1 x 42 1 c 1 x 46 5 9
6 équa tions en colonne :
x 11 1 x 21 1 x 31 1 x 41 5 4
x 12 1 x 22 1 x 32 1 x 42 5 3
cccccccccc
x 16 1 x 26 1 x 36 1 x 46 5 2
et l’on doit minimi ser :
F 5 9x 11 1 12x 12 1 9x 13 1 c 1 7x 21 1 c 1 6x 31 1 c 1 6x 41 1 c 1 10x 46 .
La théo rie des équa tions linéaires nous apprend que le sys tème de solu tions com por tera
au moins 24 2 (4 1 6 2 1) 5 15 valeurs nulles.
couplage amélioré :
A
B
C
D
0
0
0
0
0
0
a
b
c
d
0
0
0
474
On peut donc affec ter le zéro (A, a) mar qué ①, ce qui
entraîne la sup pres sion de quatre zéros. Il reste alors un
seul zéro dans les lignes Β et D.
On peut alors affec ter le zéro (B, c) mar qué ②, ce qui entraîne
la sup pres sion d’un autre zéro. Il ne reste plus alors qu’un
zéro sur cha cune des lignes C et D. On peut donc affec ter le
zéro (C, d) mar qué ③, ce qui entraîne la sup pres sion du der -
nier zéro figu rant encore dans la matrice.
Si l’on appli que alors le mar quage hon grois, on voit que
l’on peut mar quer toutes les lignes et toutes les colonnes... alors que le pro blème n’est
pas résolu. C’est que l’on a affaire à un cou plage non maximal, ainsi que le prouve le
fait que, sur le réseau de trans port associé à ce tableau, on peut mar quer S :
A
O
a
b
+b
+O
+D
-a
S
c
d
D
C
B
+A
L’amé lio ra tion du cou plage, par la chaîne ODaAbS donne l’une des trois solu tions opti -
males équi va lentes : A S b ; B S c ; C S d ; D S a . Les 2 autres solutions optimales sont :
3A b ; Ba ; Cc ; Dd4 et 3Ab ; Bc ; Ca ; Dd4 .
4.14 1) Il s’agit d’un pro blème de tran sport clas sique. On prend comme unité la cen taine de
tonnes. On rap pelle que, si ;
x 11 , x 12 , c , x 16 , x 21 , x 22 , c , x 26 , c , x 41 , x 42 , c , x 46
sont les quan ti tés à tran spor ter des ori gines 1, 2, c , 4 aux des ti nations 1, 2, 3, c , 6 on a :
x 11 1 x 12 1 c 1 x 16 5 5
x 21 1 x 22 1 c 1 x 26 5 6
4 équa tions en ligne :
cccccccccc
x 41 1 x 42 1 c 1 x 46 5 9
6 équa tions en colonne :
x 11 1 x 21 1 x 31 1 x 41 5 4
x 12 1 x 22 1 x 32 1 x 42 5 3
cccccccccc
x 16 1 x 26 1 x 36 1 x 46 5 2
et l’on doit minimi ser :
F 5 9x 11 1 12x 12 1 9x 13 1 c 1 7x 21 1 c 1 6x 31 1 c 1 6x 41 1 c 1 10x 46 .
La théo rie des équa tions linéaires nous apprend que le sys tème de solu tions com por tera
au moins 24 2 (4 1 6 2 1) 5 15 valeurs nulles.
couplage amélioré :
A
B
C
D
0
0
0
0
0
0
a
b
c
d
0
0
0