Chapitre 8 • La pro gram ma tion linéaire
308
Ainsi, la contrainte x 1 < 1 000 signi fie que x 1 étant infé rieur (resp : égal) à 1 000,
il faut lui ajou ter une quan tité posi tive (resp. nulle) que nous note rons x 4 , pour ame
ner sa valeur à 1 000 :
x 1 < 1 000 équi vaut à : x 1 1 x 4 5 1 000 et x 4 > 0
1
.
La variable x 4 est nom mée « variable d’écart » et repré sente, dans le contexte de
l’exemple, l’écart à la satu ra tion du mar ché en pro duit P 1 . Les contraintes (1) à (5)
peuvent s’écrire sous forme d’équa tions en intro dui sant des variables d’écart x 4 , x 5 ,
x 6 et x 7 :
(1)
(2)
(3)
(4)
(5)
e
x 1
1 x 4
5 1 000
x 2
1 x 5
5 500
x 3
1 x 6
5 1 500
3x 1 1 6x 2 1 2x 3
1 x 7 5 6 750
x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 >
0
(x 7 repré sente 150 fois le nombre d’heures de tra vail par semaine non employées :
l’ate lier est dis po nible 45 heures par semaine ; le fac teur 150 vient du fait que pour
chas ser les déno mi na teurs de (4), on a mul ti plié chaque membre par 150 ; ainsi :
6 750 5 45 3 150).
Les variables d’écart
2
ont une contri bu tion nulle à la fonc tion éco no mique z :
z 5 4x 1 1 12x 2 1 3x 3 1 0x 4 1 0x 5 1 0x 6 1 0x 7 .
En effet ne pas satu rer un mar ché, ou encore ne pas uti li ser des machines à 100 %,
cela ne rap porte aucun béné fice.
Pre nons comme solu tion ini tiale le som met O : x 1 5 0, x 2 5 0, x 3 5 0 (c’est la
solu tion « du mois d’août » : on ne fabrique rien, on ne gagne rien ; mais cette solu
tion est admis sible au sens mathéma tique puisque les contraintes du PL sont véri
fiées).
Les m 5 4 variables qui sont alors posi tives (autant que de contraintes) sont x 4 ,
x 5 , x 6 et x 7 . On les nomme variables de base en O. De même, les variables nulles
au som met Ο : x 1 , x 2 et x 3 sont nom mées variables hors- base en Ο (on écarte de cet
exposé intro duc tif les cas de dégé né res cence – dits de « seconde espèce » – où une
variable de base serait nulle : tel serait le cas si, par exemple, quatre plans déli mi tant
des contraintes étaient concou rants en un même som met. Ce cas sera traité en détail
plus loin).
On peut expri mer faci le ment les variables de base en Ο (qui forment l’ensemble
@ o ) en fonc tion des variables hors base en O, de même que la fonc tion éco no mique
z :
1. Si l’on avait affaire à une contrainte en sens inverse, par exemple 2x 1 1 x 2 1 5x 3 > 1 000, on
retran cherait une variable d’écart (x 8 ) pour obte nir 2x 1 1 x 2 1 5x 3 2 x 8 5 1 000 et x 8 > 0.
2. On aurait pu noter dif fé re ment les variables d’écart : x 1 , x 2 , x 3 et x 4 .
308
Ainsi, la contrainte x 1 < 1 000 signi fie que x 1 étant infé rieur (resp : égal) à 1 000,
il faut lui ajou ter une quan tité posi tive (resp. nulle) que nous note rons x 4 , pour ame
ner sa valeur à 1 000 :
x 1 < 1 000 équi vaut à : x 1 1 x 4 5 1 000 et x 4 > 0
1
.
La variable x 4 est nom mée « variable d’écart » et repré sente, dans le contexte de
l’exemple, l’écart à la satu ra tion du mar ché en pro duit P 1 . Les contraintes (1) à (5)
peuvent s’écrire sous forme d’équa tions en intro dui sant des variables d’écart x 4 , x 5 ,
x 6 et x 7 :
(1)
(2)
(3)
(4)
(5)
e
x 1
1 x 4
5 1 000
x 2
1 x 5
5 500
x 3
1 x 6
5 1 500
3x 1 1 6x 2 1 2x 3
1 x 7 5 6 750
x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 >
0
(x 7 repré sente 150 fois le nombre d’heures de tra vail par semaine non employées :
l’ate lier est dis po nible 45 heures par semaine ; le fac teur 150 vient du fait que pour
chas ser les déno mi na teurs de (4), on a mul ti plié chaque membre par 150 ; ainsi :
6 750 5 45 3 150).
Les variables d’écart
2
ont une contri bu tion nulle à la fonc tion éco no mique z :
z 5 4x 1 1 12x 2 1 3x 3 1 0x 4 1 0x 5 1 0x 6 1 0x 7 .
En effet ne pas satu rer un mar ché, ou encore ne pas uti li ser des machines à 100 %,
cela ne rap porte aucun béné fice.
Pre nons comme solu tion ini tiale le som met O : x 1 5 0, x 2 5 0, x 3 5 0 (c’est la
solu tion « du mois d’août » : on ne fabrique rien, on ne gagne rien ; mais cette solu
tion est admis sible au sens mathéma tique puisque les contraintes du PL sont véri
fiées).
Les m 5 4 variables qui sont alors posi tives (autant que de contraintes) sont x 4 ,
x 5 , x 6 et x 7 . On les nomme variables de base en O. De même, les variables nulles
au som met Ο : x 1 , x 2 et x 3 sont nom mées variables hors- base en Ο (on écarte de cet
exposé intro duc tif les cas de dégé né res cence – dits de « seconde espèce » – où une
variable de base serait nulle : tel serait le cas si, par exemple, quatre plans déli mi tant
des contraintes étaient concou rants en un même som met. Ce cas sera traité en détail
plus loin).
On peut expri mer faci le ment les variables de base en Ο (qui forment l’ensemble
@ o ) en fonc tion des variables hors base en O, de même que la fonc tion éco no mique
z :
1. Si l’on avait affaire à une contrainte en sens inverse, par exemple 2x 1 1 x 2 1 5x 3 > 1 000, on
retran cherait une variable d’écart (x 8 ) pour obte nir 2x 1 1 x 2 1 5x 3 2 x 8 5 1 000 et x 8 > 0.
2. On aurait pu noter dif fé re ment les variables d’écart : x 1 , x 2 , x 3 et x 4 .