Chapitre 8 • La programmation linéaire
356
L’opti mum du PL continu : x 1 = 5/4, x 2 = 3/2 n’est pas entier. En outre, si l’on arron -
dit x 1 par défaut à 1 : E(5/4) = 1, et de même pour x 2 : E(3/2) = 1, on obtient un point
qui n’est pas admis sible Ρ : (x 1 = 1, x 2 = 1) (en dehors du domaine $) ; il en va de
même pour l’arrondi par excès : E*(3/4) = 2 et E*(3/2) = 2 , car le point Q : (x 1 = 2,
x 2 = 2) n’est pas non plus admis sible.
Voici la méthode pro po sée par Gomory pour obte nir l’opti mum d’un PLNE :
pour la base opti male du PL continu, expri mons les variables de base (ici x 1 et x 2 ) et
la fonc tion éco no mique z en fonc tion des variables hors- base :
f
x 1
1
a
1
12
# x 3 1
1
3
x 4 b
5
5
4
x 2
1
a
1
2
x 4 b
5
3
2
z
1
a
1
12
x 3 1
5
6
x 4 b
5
11
4
D’une manière géné rale on a, à l’opti mum du PL continu :
(1)
(2)
d
x i
+
a a ij ·
x j
=
b i pour toute variable x i de base ; x i P@
x j [N
z
+
a D j ·
x j
=
z*
x j [N
N désigne ici l’ensemble des variables hors- base et @, l’ensemble des variables de
base, à l’opti mum.
On­a­tou­ ­ jours­a ij > Ε(a ij ), car Ε(a ij ) est le plus grand entier infé rieur ou égal à a ij .
Pre nons une variable hors- base x j ; puisqu’elle est posi tive ou nulle, on a
a ij # x j > E(a ij ) # x j .
Som mons toutes ces rela tions pour x j Pn; il vient : a
x j Pn
a ij # x ij > a
x j Pn
E(a ij ) # x j .
Par ajout de x i à chaque membre, il vient :
b i 5 x i 1 a
x j Pn
a ij # x j > x i 1 a
x j Pn
E(a ij ) # x j .
(8.1)
On­a­aussi­b i > E(b i ). Si x i doit être entier, de même que x j pour tout x j PN, on a
donc :
E(b i ) > x i 1 a
x j Pn
E(a ij ) # x j
(8.2)