Chapitre 8 • La programmation linéaire
354
Dans le cas géné ral :
f
a 11 ? x 1 + a 12 ? x 2 1 c 1 a 1n ? x n 5 1
(e 1 couvert).
a 21 ? x 1 + a 22 ? x 2 1 c 1 a 2n ? x n 5 1
(e 2 couvert).
– – –
– – –
– – –
– – –
a m1 ? x 1 + a m2 ? x 2 1 c 1 a mn ? x n 5 1
(e n couvert).
x 1
,
x 2
, c ,
x n
5 0 ou 1
c 1 ? x 1 + c 2 ? x 2 1 c 1 c n ? x n 5 x [min]
Le lec teur se convain cra faci le ment de ce que la for mu la tion du pro blème de recou -
vre ment se déduit de celle ci- dessus en rem pla çant cha cune des m contraintes expli -
cites :
a
n
j51
a ij # x j 5 1 , par : a
n
j51
a ij # x j > 1 , où i 5 1, 2, c , m.
Voici une appli ca tion du pro blème de par tition ne ment à un pro blème de tour
nées.
Soient quatre points e 1 , e 2 , e 3 , e 4 repré sen tant quatre clients à qui l’on doit livrer
respectivement 2, 4, 8 et 10 tonnes de mar chan dise, à par tir d’un entre pôt cen tral
e 0 , ceci avec un camion de capa cité C = 16 tonnes. Le tableau (symé trique) des dis -
tances (en km) est le sui vant :
e 1
e 0
e 0
e 1
e 1
e 2
e 2
e 2
e 3
e 3
e 3
e 4
e 4
e 4
P 4 P 5 P 6 P 7 P 8 P 9 P 10 P 11
P 3
P 2
P 1
c j
A
0 0 0
0 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
10
10
15 8 12 9
5
52
20
6
25
12
8
18
15
12
12 25
35
24
16
30
5
9
20
29 30 37 49 34
6
1
1
1
1
1 1
1
1
1
1
1
1
1
1
1
1 1
1
1
.
.
.
.
.
Onpeut,ici,énu mé rertouteslestour nées«admis sibles»P j , c’est- à-dire res pec tant
la contrainte de capa cité (la somme des quan ti tés livrées aux clients d’une même
tour née doit être infé rieure ou égale à 16 tonnes) ; cette énu mé ra tion des 11 tour -
nées admis sibles n’a été pos sible que parce que cet exemple est de très petite taille.
Don nonsledétailducal culducoûtc j de la tour née P j ; ainsi pour la tour née P 11 qui
concerne les clients e 1 , e 2 et e 4 (puisque a 1, 11 = a 2, 11 = a 3, 11 = 1), on cherche l’iti -
né raire de lon gueur (en km) mini male qui, par tant de e 0 , per met de pas ser une fois
et une seule chez ces trois clients, puis de reve nir à e 0 . Ceci revient à résoudre le
« pro blème du voya geur de com merce » (TSP) pour une ins tance de très petite taille,
puisque com por tant seulement quatre points ;
onvéri fieque,parmiles3cycleshamiltoniensdugrapheci- contre,celuidelalon -
gueur mini male est :
354
Dans le cas géné ral :
f
a 11 ? x 1 + a 12 ? x 2 1 c 1 a 1n ? x n 5 1
(e 1 couvert).
a 21 ? x 1 + a 22 ? x 2 1 c 1 a 2n ? x n 5 1
(e 2 couvert).
– – –
– – –
– – –
– – –
a m1 ? x 1 + a m2 ? x 2 1 c 1 a mn ? x n 5 1
(e n couvert).
x 1
,
x 2
, c ,
x n
5 0 ou 1
c 1 ? x 1 + c 2 ? x 2 1 c 1 c n ? x n 5 x [min]
Le lec teur se convain cra faci le ment de ce que la for mu la tion du pro blème de recou -
vre ment se déduit de celle ci- dessus en rem pla çant cha cune des m contraintes expli -
cites :
a
n
j51
a ij # x j 5 1 , par : a
n
j51
a ij # x j > 1 , où i 5 1, 2, c , m.
Voici une appli ca tion du pro blème de par tition ne ment à un pro blème de tour
nées.
Soient quatre points e 1 , e 2 , e 3 , e 4 repré sen tant quatre clients à qui l’on doit livrer
respectivement 2, 4, 8 et 10 tonnes de mar chan dise, à par tir d’un entre pôt cen tral
e 0 , ceci avec un camion de capa cité C = 16 tonnes. Le tableau (symé trique) des dis -
tances (en km) est le sui vant :
e 1
e 0
e 0
e 1
e 1
e 2
e 2
e 2
e 3
e 3
e 3
e 4
e 4
e 4
P 4 P 5 P 6 P 7 P 8 P 9 P 10 P 11
P 3
P 2
P 1
c j
A
0 0 0
0 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
10
10
15 8 12 9
5
52
20
6
25
12
8
18
15
12
12 25
35
24
16
30
5
9
20
29 30 37 49 34
6
1
1
1
1
1 1
1
1
1
1
1
1
1
1
1
1 1
1
1
.
.
.
.
.
Onpeut,ici,énu mé rertouteslestour nées«admis sibles»P j , c’est- à-dire res pec tant
la contrainte de capa cité (la somme des quan ti tés livrées aux clients d’une même
tour née doit être infé rieure ou égale à 16 tonnes) ; cette énu mé ra tion des 11 tour -
nées admis sibles n’a été pos sible que parce que cet exemple est de très petite taille.
Don nonsledétailducal culducoûtc j de la tour née P j ; ainsi pour la tour née P 11 qui
concerne les clients e 1 , e 2 et e 4 (puisque a 1, 11 = a 2, 11 = a 3, 11 = 1), on cherche l’iti -
né raire de lon gueur (en km) mini male qui, par tant de e 0 , per met de pas ser une fois
et une seule chez ces trois clients, puis de reve nir à e 0 . Ceci revient à résoudre le
« pro blème du voya geur de com merce » (TSP) pour une ins tance de très petite taille,
puisque com por tant seulement quatre points ;
onvéri fieque,parmiles3cycleshamiltoniensdugrapheci- contre,celuidelalon -
gueur mini male est :