355
© Dunod – Toute reproduction non autorisée est un délit.
8.8 Pro gramme linéaire en nombres entiers…
[e 0 , e 2 , e 1 , e 4 , e 0 ] avec 34 km.
Dans un exemple de taille indus trielle, l’énu mé ra tion exhaus -
tive des tour nées admis sibles serait impra ti cable et l’on
pro cé de rait à une géné ra tion pro gres sive de tour nées « inté -
res santes », sans les énu mé rer toutes : il s’agit là d’une tech
nique de « géné ra tion de colonnes » per met tant de trai ter
cer tains PL com por tant, a priori, un très grand nombre de colonnes (dont l’exposé
sort du cadre de cet ouvrage). Les pro blèmes de tour nées peuvent être réso lus, de
manière appro chée, par des heu ris tiques « gour mandes » comme la méthode des
écar te ments de Fletcher.
Voici la for mu la tion de notre pro blème de tour nées en tant que pro blème de par -
tition ne ment avec 11 variables binaires :
e
x 1
+ x 5 + x 6 + x 7
+ x 10 + x 11 = 1
x 2
x 5 +
+ x 8 + x 9 + x 10 + x 11 = 1
x 3
+ x 6
+ x 8
+ x 10
= 1
x 4
+ x 7
+ x 9
+ x 11 = 1
30x 1 + 16x 2 + 24x 3 + 18x 4 + 35x 5 + 52x 6 + 29x 7 + 30x 8 + 37x 9 + 49x 10 + 34x 11 = z
La solu tion opti male de ce pro blème est : x 3 = x 11 =1;elleapourcoûtz* = 58. Elle
cor res pond aux deux tour nées [e 0 , e 2 , e 1 , e 4 , e 0 ] et [e 0 , e 3 , e 0 ].
Nous pas sons main te nant à une méthode de réso lu tion dif fé rente de celles évo
quées ci dessus, fon dée uni que ment sur la pro gram ma tion linéaire et per met tant de
trai ter des PL en variables entières.
8.8.1 Méthode des tron ca tures de Gomory
Soit à résoudre le PL : d
12x 1
2
8x 2
<
3
2x 2
<
3
x 1
,
x 2
entiers positifs ou nuls
x 1
1
x 2
5
z 3max4
Onintro duitdeuxvariablesd’écart:x 3 et x 4 . Après deux ité ra tions, on obtient l’opti -
mum du PL « continu » (c’est- à-dire pour les quels les variables ne sont pas astreintes
à être entières) :
0
0
0
0
0
3
4
5/ 6
1/ 12
5/ 4
1/ 12 1/ 3
1/ 2
3/ 2
1
1
1
2
x 2
x 1
j
z 11/ 4
e 0
e 1
e 2
e 4
15
9 8
20
12
5
© Dunod – Toute reproduction non autorisée est un délit.
8.8 Pro gramme linéaire en nombres entiers…
[e 0 , e 2 , e 1 , e 4 , e 0 ] avec 34 km.
Dans un exemple de taille indus trielle, l’énu mé ra tion exhaus -
tive des tour nées admis sibles serait impra ti cable et l’on
pro cé de rait à une géné ra tion pro gres sive de tour nées « inté -
res santes », sans les énu mé rer toutes : il s’agit là d’une tech
nique de « géné ra tion de colonnes » per met tant de trai ter
cer tains PL com por tant, a priori, un très grand nombre de colonnes (dont l’exposé
sort du cadre de cet ouvrage). Les pro blèmes de tour nées peuvent être réso lus, de
manière appro chée, par des heu ris tiques « gour mandes » comme la méthode des
écar te ments de Fletcher.
Voici la for mu la tion de notre pro blème de tour nées en tant que pro blème de par -
tition ne ment avec 11 variables binaires :
e
x 1
+ x 5 + x 6 + x 7
+ x 10 + x 11 = 1
x 2
x 5 +
+ x 8 + x 9 + x 10 + x 11 = 1
x 3
+ x 6
+ x 8
+ x 10
= 1
x 4
+ x 7
+ x 9
+ x 11 = 1
30x 1 + 16x 2 + 24x 3 + 18x 4 + 35x 5 + 52x 6 + 29x 7 + 30x 8 + 37x 9 + 49x 10 + 34x 11 = z
La solu tion opti male de ce pro blème est : x 3 = x 11 =1;elleapourcoûtz* = 58. Elle
cor res pond aux deux tour nées [e 0 , e 2 , e 1 , e 4 , e 0 ] et [e 0 , e 3 , e 0 ].
Nous pas sons main te nant à une méthode de réso lu tion dif fé rente de celles évo
quées ci dessus, fon dée uni que ment sur la pro gram ma tion linéaire et per met tant de
trai ter des PL en variables entières.
8.8.1 Méthode des tron ca tures de Gomory
Soit à résoudre le PL : d
12x 1
2
8x 2
<
3
2x 2
<
3
x 1
,
x 2
entiers positifs ou nuls
x 1
1
x 2
5
z 3max4
Onintro duitdeuxvariablesd’écart:x 3 et x 4 . Après deux ité ra tions, on obtient l’opti -
mum du PL « continu » (c’est- à-dire pour les quels les variables ne sont pas astreintes
à être entières) :
0
0
0
0
0
3
4
5/ 6
1/ 12
5/ 4
1/ 12 1/ 3
1/ 2
3/ 2
1
1
1
2
x 2
x 1
j
z 11/ 4
e 0
e 1
e 2
e 4
15
9 8
20
12
5