357
© Dunod – Toute reproduction non autorisée est un délit.
8.8 Pro gramme linéaire en nombres entiers…
Intro dui sons la par tie fractionnaire f i de b i : b i 5 E(b i ) 1 f i où 0 < f i , 1 ;
par exemple
19
7
5 2 1
5
7
donc E a
19
7
b 5 2 et f a
19
7
b 5
5
7
; il en va de même
pour la par tie fractionnaire f ij de a ij : a if 5 E(a ij ) 1 f ij où 0 < f ij , 1.
La rela tion (1) s’écrit :
x i 1 a
x j Pn
(E(a ij ) 1 f ij ) # x j 5 b i
(8.2bis)
Intro dui sons une variable d’écart s i > 0 dans la rela tion (8.2) :
x i 1 a
x j Pn
E(a ij ) # x j 1 s i 5 E(b i )
(8.2ter)
La sous trac tion membre à membre (8.2bis) et (8.2ter) four nit :
a
x j Pn
f ij # x j 2 s i 5 f i
(8.3)
Consi dé rons maintenant une variable de base x i qui, à l’opti mum du PL continu,
ne serait pas entière ; alors on a : f i . 0 . Pour pas ser aux valeurs numé riques des
variables à cet optimum, on annule les variables hors- base : x j = 0 pour x j Pn; (8.3)
donne alors –s i = f i , or –s i est néga tif ou nul, tan dis que f i est stric te ment posi tif. Ainsi
lacontrainte(3)n’estpasvéri fiéeàl’opti mumduPLcontinu;sionlarajouteauxcontraintes du PL, elle sup prime une par tie du domaine admis sible $, d’où son nom
de « tron ca ture » ; on peut démon trer que la par tie sup pri mée ne contient pas de point
à coor don nées qui seraient toutes entières.
Notons que l’on peut faire subir à l’expres sion (2) de la fonc tion éco no mique :
z 1 a
x j Pn
D j # x j 5 z*,
(8.4)
un trai te ment ana logue à celui de la rela tion (2).
Reve nons à notre exemple. Les rela tions (8.3) s’écrivent :
pour i = 1 :
1
12
x 3 1
1
3
x 4 2 s 1 5 f a
5
4
b 5
1
4
pour i = 2 :
1
2
x 4 2 s 2 5 f a
3
2
b 5
1
2
Nous choi sis sons d’inté grer la seconde :
1
2
x 4 2 s 2 5
1
2
dans notre pro gramme
linéaire ; pour cette nou velle contrainte, la solu tion cou rante du primal n’est pas
admis sible. Mais nous pou vons l’inté grer au primal
1
, à condi tion d’ajou ter dans
1. Cette contrainte est « duale admissible » et pour rait être direc te ment inté grée au dual. Notre
démarche, ici, est seule ment didac tique.
© Dunod – Toute reproduction non autorisée est un délit.
8.8 Pro gramme linéaire en nombres entiers…
Intro dui sons la par tie fractionnaire f i de b i : b i 5 E(b i ) 1 f i où 0 < f i , 1 ;
par exemple
19
7
5 2 1
5
7
donc E a
19
7
b 5 2 et f a
19
7
b 5
5
7
; il en va de même
pour la par tie fractionnaire f ij de a ij : a if 5 E(a ij ) 1 f ij où 0 < f ij , 1.
La rela tion (1) s’écrit :
x i 1 a
x j Pn
(E(a ij ) 1 f ij ) # x j 5 b i
(8.2bis)
Intro dui sons une variable d’écart s i > 0 dans la rela tion (8.2) :
x i 1 a
x j Pn
E(a ij ) # x j 1 s i 5 E(b i )
(8.2ter)
La sous trac tion membre à membre (8.2bis) et (8.2ter) four nit :
a
x j Pn
f ij # x j 2 s i 5 f i
(8.3)
Consi dé rons maintenant une variable de base x i qui, à l’opti mum du PL continu,
ne serait pas entière ; alors on a : f i . 0 . Pour pas ser aux valeurs numé riques des
variables à cet optimum, on annule les variables hors- base : x j = 0 pour x j Pn; (8.3)
donne alors –s i = f i , or –s i est néga tif ou nul, tan dis que f i est stric te ment posi tif. Ainsi
lacontrainte(3)n’estpasvéri fiéeàl’opti mumduPLcontinu;sionlarajouteauxcontraintes du PL, elle sup prime une par tie du domaine admis sible $, d’où son nom
de « tron ca ture » ; on peut démon trer que la par tie sup pri mée ne contient pas de point
à coor don nées qui seraient toutes entières.
Notons que l’on peut faire subir à l’expres sion (2) de la fonc tion éco no mique :
z 1 a
x j Pn
D j # x j 5 z*,
(8.4)
un trai te ment ana logue à celui de la rela tion (2).
Reve nons à notre exemple. Les rela tions (8.3) s’écrivent :
pour i = 1 :
1
12
x 3 1
1
3
x 4 2 s 1 5 f a
5
4
b 5
1
4
pour i = 2 :
1
2
x 4 2 s 2 5 f a
3
2
b 5
1
2
Nous choi sis sons d’inté grer la seconde :
1
2
x 4 2 s 2 5
1
2
dans notre pro gramme
linéaire ; pour cette nou velle contrainte, la solu tion cou rante du primal n’est pas
admis sible. Mais nous pou vons l’inté grer au primal
1
, à condi tion d’ajou ter dans
1. Cette contrainte est « duale admissible » et pour rait être direc te ment inté grée au dual. Notre
démarche, ici, est seule ment didac tique.