8.1 Exemple de pro gramme linéaire – Aspect géo mé trique
305
© Dunod – Toute reproduction non autorisée est un délit.
On peut encore espé rer, par des rai son ne ments du type « fausse hypo thèse », et des
subs ti tutions mutuelles d’uni tés des dif fé rents pro duits, se tirer d’affaire et trou ver le
nou vel opti mum (point W) que confir me rait la construc tion géo mé trique :
x 1 5 375 ; x 2 5 500 ; x 3 5 2 625/2 ; z 5 11 437, 5.
Notons qu’en W, la variable x 3 n’a pas une valeur entière.
En effet, la pré sence d’une nou velle contrainte conduit à tron quer le polyèdre des
solu tions, qui se réduit alors au solide OABCDEFXWR et c’est le point W dont les
coor don nées forment la solu tion opti male.
Mais, avec m contraintes (m grand), il n’est plus pos sible de s’y retrou ver dans des
rai son ne ments de ce type, qui deviennent par trop com bi na toires.
Il faut donc tenter d’uti li ser les infor ma tions obte nues jus qu’ici pour tenter de géné
ra li ser le pro blème par une autre voie.
Nous allons énon cer, dans le théo rème qui suit, une prop riété qui nous per met tra de
carac té ri ser une solu tion opti male d’un pro gramme linéaire (PL).
Théo rème. Si l’ensemble des contraintes d’un pro gramme linéaire forme un polyèdre
1
non vide, il existe (au moins) une solu tion opti male qui est un som met de ce polyèdre.
Preuve. Le polyèdre formé par les contraintes du PL étant sup posé non vide, le PL
admet au moins une solu tion optimale. Nous allons sup po ser dans un pre mier temps,
que cette solu tion est unique. Cidessous, z désigne un point du polyèdre (et non pas
la fonction économique)
La démons tra tion se fait par récur rence sur la dimen sion d du polyèdre. Si d 5 0,
le polyèdre se réduit à un point qui est aussi un som met, le résul tat est donc véri fié.
Sup po sons main te nant d . 0. Mon trons que le point repré sen ta tif de la solu tion ne
peut se trou ver à l’inté rieur du polyèdre. Soit z un point situé à l’inté rieur du polyèdre
et sup po sons que z cor res ponde à la solu tion opti male. Consi dé rons P z l’hyper plan
pas sant par z et dont la direc tion est fixée par les coef fi cients de la fonc tion éco no
mique. P z par tage le polyèdre en deux par ties non vides. Il existe alors un point z r à
l’inté rieur de l’une de ces deux par ties, cor res pon dant à une solu tion réa li sable du
PL dont la valeur sera stric te ment supé rieure à la valeur du point z. Cela contre dit le
fait que z soit la solu tion opti male. La solu tion opti male est donc située sur une face
du polyèdre. Une face d’un polyèdre de dimen sion d étant un polyèdre de dimen sion
dr , d, en appli quant à nou veau le même rai son ne ment, nous avons mon tré le résul
tat, mais seulement lorsque la solu tion opti male est unique.
❑
Dans le cas géné ral où la solu tion opti male n’est pas néces sai re ment unique (cf le
N.B. du cas de n = 2 variables), un rai son ne ment ana logue peut s’appli quer, dans lequel
le point z r consi déré cor res pond à une solu tion de valeur supé rieure ou égale (mais non
néces sai re ment stric te ment) à la valeur du point z. Le théo rème est alors démon tré.
L’ensemble des contraintes d’un PL ne forme pas tou jours un polyèdre convexe.
En effet, il peut arri ver que cet ensemble com porte des points à l’infini et donc forme
un poly tope convexe ouvert (un polyèdre étant un poly tope fermé). Dans ce der nier
1. Par défi ni tion un polyèdre est fini (il ne pos sède pas de points à l’infini).
305
© Dunod – Toute reproduction non autorisée est un délit.
On peut encore espé rer, par des rai son ne ments du type « fausse hypo thèse », et des
subs ti tutions mutuelles d’uni tés des dif fé rents pro duits, se tirer d’affaire et trou ver le
nou vel opti mum (point W) que confir me rait la construc tion géo mé trique :
x 1 5 375 ; x 2 5 500 ; x 3 5 2 625/2 ; z 5 11 437, 5.
Notons qu’en W, la variable x 3 n’a pas une valeur entière.
En effet, la pré sence d’une nou velle contrainte conduit à tron quer le polyèdre des
solu tions, qui se réduit alors au solide OABCDEFXWR et c’est le point W dont les
coor don nées forment la solu tion opti male.
Mais, avec m contraintes (m grand), il n’est plus pos sible de s’y retrou ver dans des
rai son ne ments de ce type, qui deviennent par trop com bi na toires.
Il faut donc tenter d’uti li ser les infor ma tions obte nues jus qu’ici pour tenter de géné
ra li ser le pro blème par une autre voie.
Nous allons énon cer, dans le théo rème qui suit, une prop riété qui nous per met tra de
carac té ri ser une solu tion opti male d’un pro gramme linéaire (PL).
Théo rème. Si l’ensemble des contraintes d’un pro gramme linéaire forme un polyèdre
1
non vide, il existe (au moins) une solu tion opti male qui est un som met de ce polyèdre.
Preuve. Le polyèdre formé par les contraintes du PL étant sup posé non vide, le PL
admet au moins une solu tion optimale. Nous allons sup po ser dans un pre mier temps,
que cette solu tion est unique. Cidessous, z désigne un point du polyèdre (et non pas
la fonction économique)
La démons tra tion se fait par récur rence sur la dimen sion d du polyèdre. Si d 5 0,
le polyèdre se réduit à un point qui est aussi un som met, le résul tat est donc véri fié.
Sup po sons main te nant d . 0. Mon trons que le point repré sen ta tif de la solu tion ne
peut se trou ver à l’inté rieur du polyèdre. Soit z un point situé à l’inté rieur du polyèdre
et sup po sons que z cor res ponde à la solu tion opti male. Consi dé rons P z l’hyper plan
pas sant par z et dont la direc tion est fixée par les coef fi cients de la fonc tion éco no
mique. P z par tage le polyèdre en deux par ties non vides. Il existe alors un point z r à
l’inté rieur de l’une de ces deux par ties, cor res pon dant à une solu tion réa li sable du
PL dont la valeur sera stric te ment supé rieure à la valeur du point z. Cela contre dit le
fait que z soit la solu tion opti male. La solu tion opti male est donc située sur une face
du polyèdre. Une face d’un polyèdre de dimen sion d étant un polyèdre de dimen sion
dr , d, en appli quant à nou veau le même rai son ne ment, nous avons mon tré le résul
tat, mais seulement lorsque la solu tion opti male est unique.
❑
Dans le cas géné ral où la solu tion opti male n’est pas néces sai re ment unique (cf le
N.B. du cas de n = 2 variables), un rai son ne ment ana logue peut s’appli quer, dans lequel
le point z r consi déré cor res pond à une solu tion de valeur supé rieure ou égale (mais non
néces sai re ment stric te ment) à la valeur du point z. Le théo rème est alors démon tré.
L’ensemble des contraintes d’un PL ne forme pas tou jours un polyèdre convexe.
En effet, il peut arri ver que cet ensemble com porte des points à l’infini et donc forme
un poly tope convexe ouvert (un polyèdre étant un poly tope fermé). Dans ce der nier
1. Par défi ni tion un polyèdre est fini (il ne pos sède pas de points à l’infini).