Chapitre 8 • La programmation linéaire
360
ini tial d, une par tie ne conte nant pas de point à coor don nées toutes entières (points
indi­ ­ qués­en­gras­sur­les­figures­ci-­ ­ ­ après).
Figure 8.11
Pour obte nir l’équa tion de la droite qui tronque d
(0)
et ainsi obte nir d
(1)
, il suf -
fit,­dans­la­pre­ ­ mière­tron­ ­ ca­ ­ ture­:1
2
x 4 2 s 2 5
1
2
,­de­ne­faire­figu­ ­ rer­que­les­variablesprin ci pales : x 1 , x 2 , et s. Après intro duc tion de la variable d’écart x 4 dans la seconde
contrainte du PL ini tial, on avait : 2x 2 + x 4 = 3 d’où
1
2
x 4 5
3
2
2 x 2 , que nous repor -
tons dans la tron ca ture : a
3
2
2 x 2 b 2 s 2 5
1
2
soit x 2 + s 2 = 1 qui équi vaut (s 2 étant
une variable d’écart) à la contrainte nou velle : x 2 < 1; la droite tron quant d
(0)
pour
obte nir d
(1)
est donc : x 2 = 1. Pour la seconde tron ca ture (pas sage de d
(1)
à d
(2)
),
il vient :
1
12
x 3 1
2
3
s 2 2 t 1 5
11
12
; or, d’après la pre mière contrainte du PL ini tial :
12x 1 – 8x 2 + x 3 = 3, d’où :
1
12
x 3 5
1
4
2 x 1 1
2
3
x 2 . De plus nous avions, au pas
pré cé dent, x 2 + s 2 = 1, d’où
2
3
s 2 5
2
3
2
2
3
x 2 . La seconde tron ca ture s’écrit donc :
a
1
4
2 x 1 1
2
3
x 2 b 1 a
2
3
2
2
3
x 2 b 2 t 1 5
11
12
, soit x 1 + t 1 = 0 , d’où la nou velle
contrainte : x 1 < 0 ; la droite tron quant d
(1)
pour obte nir d
(2)
, qui n’est autre que le
seg ment [O, C], est donc : x 1 = 0.
Note.­Le­nombre­de­contraintes­(tron­ ­ ca­ ­ tures)­rajou­ ­ tées­au­fil­des­ité­ ­ ra­ ­ tions­peut­êtreexpo nen tiel par rap port à la taille du pro gramme linéaire d’ori gine : la méthode de
Gomory n’est pas poly no miale. Indi quons que – plus géné ra le ment – le pro blème
de­la­pro­ ­ gram­ ­ ma­ ­ tion­linéaire­en­nombres­entiers­est­NP-­ ­ ­ difficile­(le­lec­ ­ teur­se­repor­ -
tera au cha pitre 2, para graphe 2.2.1, com plexité des pro blèmes). Même dans des cas
« simples » comme le pro blème du sac à dos en variables entières (knapsack), c’est-