Chapitre 8 • La pro gram ma tion linéaire
328
D’une manière géné rale une « solu tion admis sible » (on dit aussi « réa li sable » ou
même « fai sable » : mau vaise re­ traduction de l’anglais « feasible ») est une solu tion
(pas néces sai re ment de base) du sys tème : A # x 5 b, avec x > 0.
Le théo rème sui vant (que nous admet tons sans démons tra tion) pré cise la cor res pon ­
dance entre les som mets du polyèdre  et les solu tions de base admis sibles : il fait le
lien entre l’aspect géo mé trique et l’aspect algé brique en pro gram ma tion linéaire.
Théo rème. À toute solu tion de base admis sible cor res pond un som met du polyèdre
des solu tions admis sibles et un seul.
La réci proque n’est vraie qu’en l’absence de dégé né res cence de deuxième espèce,
c’est­ à­dire si x B est stric te ment posi tif (aucune variable de base nulle).
• À titre d’exemple, repre nons le pro blème res treint de l’ate lier (deux pro duits, 35
heures de tra vail heb do ma daire)
c
x 1 1
1 x 3
5 1 000
x 2
1 x 4
5 500
x 1 1 2x 2
1 x 5 5 1 750
où x 3 , x 4 et x 5 sont des variables d’écart.
Le lec teur véri fiera que :
– au som met Ο cor res pond la base B O 5 C
3 4 5
1 0 0
0 1 0
0 0 1
S et x B O 5 C
1 000
500
1 750
S
3
4
5
– au som met A cor res pond la base B A 5 C
2 3 5
0 1 0
1 0 0
2 0 1
S et x B A 5 C
500
1 000
750
S
2
3
5