Chapitre 8 • La pro gram ma tion linéaire
306
cas, bien que des solu tions réa li sables du PL existent, il n’existe pas néces sai re ment
de solu tion opti male (les solu tions opti males peuvent être reje tées à l’infini). Alors, si
une solu tion opti male finie existe, on peut mon trer avec une démons tra tion simi laire
à la pré cé dente qu’il existe une solu tion opti male située en un som met du poly tope.
Mais, dans les applications de R.O. ce cas est pratiquement exclu : les ressources, les
temps, les capacités, etc. y sont en effet finis !
Dans d’autres cas, les contraintes capacités peuvent être contra dic toires : alors le
polyèdre est vide et le PL est impos sible.
On pour rait alors en déduire qu’il suf fit de déter mi ner les coor don nées de tous les
som mets du polyèdre et de cal cu ler la valeur de la fonc tion éco no mique qui cor res
pond à cha cun d’eux : il res te rait à choi sir la plus grande de ces valeurs. Mais, s’il
y a n variables et m contraintes, il y a n 1 m plans, dont les inter sec tions n à n sont
au nombre de :
C
n
n1m 5
(m 1 n)!
m!n!
,
pour n 5 15 et m 5 10, on a 3 268 760 points d’inter sec tion et pour tant il ne s’agit
encore que d’un petit pro gramme linéaire. Même avec de très puis sants ordi na teurs,
d’aujourd’hui ou de demain, l’énu mé ra tion de tous les som mets est impra ti cable
dès que n et m dépassent 20 : elle condui rait à des durées pro hi bi tives sur des P.L.
de taille indus trielle, pou vant dépas ser des milliards d’années, ou plus !
1
Il est exclu
d’énu mé rer dans le com bi na toire !
L’algo rithme le plus connu pour la réso lu tion des pro grammes linéaires : l’algo
rithme du sim plexe, au lieu de cal cu ler la valeur de z pour tous les som mets (donc en
les énumérant), la cal cule seule ment pour une suite de som mets telle que la valeur
de z pour le n
ième
ne soit pas infé rieure à la valeur z pour le (n 2 1)
ième
. Ainsi, on est
sûr de par ve nir à l’opti mum au bout d’un nombre de pas fini, puisque le nombre de
som mets est fini, à condi tion que la valeur de la fonc tion éco no mique z aug mente
stric te ment pour un cer tain nombre de ces pas. Rappelons que l’on maximise z.
Les som mets qui consti tuent la suite envi sa gée sont adja cents, c’est àdire le k
ième
et le (k 1 1)
ième
sont les extré mi tés d’une même arête ; il est donc néces saire que,
quelque soit le som met de départ, on puisse tou jours trou ver, étant donné un som met
auquel on est par venu, un som met adja cent dont les coor don nées donnent une valeur
non infé rieure à z, tant qu’on n’est pas arrivé à l’opti mum.
Or, ceci est pos sible, en rai son d’une prop riété des polyèdres engen drés par des
contraintes linéaires : la « convexité ».
1. Les points d’inter sec tion ne sont pas tous des som mets du polyèdre des solu tions dans l’espace
à n dimen sions ; autre ment dit, les coor don nées de cer tains de ces points ne véri fient pas une ou
plu sieurs contraintes. Ainsi, le polyèdre que nous avons consi déré plus haut, comme exemple, ne
compte que 10 som mets, alors qu’il existe @
3
7 5 35 points d’inter sec tion des plans 3 à 3. Mais ce
fait ne res treint pas le pro blème, puisqu’il fau drait exa mi ner toutes les inter sec tions pour déter mi
ner les som mets « admis sibles » c’est àdire véri fiant toutes les contraintes.
306
cas, bien que des solu tions réa li sables du PL existent, il n’existe pas néces sai re ment
de solu tion opti male (les solu tions opti males peuvent être reje tées à l’infini). Alors, si
une solu tion opti male finie existe, on peut mon trer avec une démons tra tion simi laire
à la pré cé dente qu’il existe une solu tion opti male située en un som met du poly tope.
Mais, dans les applications de R.O. ce cas est pratiquement exclu : les ressources, les
temps, les capacités, etc. y sont en effet finis !
Dans d’autres cas, les contraintes capacités peuvent être contra dic toires : alors le
polyèdre est vide et le PL est impos sible.
On pour rait alors en déduire qu’il suf fit de déter mi ner les coor don nées de tous les
som mets du polyèdre et de cal cu ler la valeur de la fonc tion éco no mique qui cor res
pond à cha cun d’eux : il res te rait à choi sir la plus grande de ces valeurs. Mais, s’il
y a n variables et m contraintes, il y a n 1 m plans, dont les inter sec tions n à n sont
au nombre de :
C
n
n1m 5
(m 1 n)!
m!n!
,
pour n 5 15 et m 5 10, on a 3 268 760 points d’inter sec tion et pour tant il ne s’agit
encore que d’un petit pro gramme linéaire. Même avec de très puis sants ordi na teurs,
d’aujourd’hui ou de demain, l’énu mé ra tion de tous les som mets est impra ti cable
dès que n et m dépassent 20 : elle condui rait à des durées pro hi bi tives sur des P.L.
de taille indus trielle, pou vant dépas ser des milliards d’années, ou plus !
1
Il est exclu
d’énu mé rer dans le com bi na toire !
L’algo rithme le plus connu pour la réso lu tion des pro grammes linéaires : l’algo
rithme du sim plexe, au lieu de cal cu ler la valeur de z pour tous les som mets (donc en
les énumérant), la cal cule seule ment pour une suite de som mets telle que la valeur
de z pour le n
ième
ne soit pas infé rieure à la valeur z pour le (n 2 1)
ième
. Ainsi, on est
sûr de par ve nir à l’opti mum au bout d’un nombre de pas fini, puisque le nombre de
som mets est fini, à condi tion que la valeur de la fonc tion éco no mique z aug mente
stric te ment pour un cer tain nombre de ces pas. Rappelons que l’on maximise z.
Les som mets qui consti tuent la suite envi sa gée sont adja cents, c’est àdire le k
ième
et le (k 1 1)
ième
sont les extré mi tés d’une même arête ; il est donc néces saire que,
quelque soit le som met de départ, on puisse tou jours trou ver, étant donné un som met
auquel on est par venu, un som met adja cent dont les coor don nées donnent une valeur
non infé rieure à z, tant qu’on n’est pas arrivé à l’opti mum.
Or, ceci est pos sible, en rai son d’une prop riété des polyèdres engen drés par des
contraintes linéaires : la « convexité ».
1. Les points d’inter sec tion ne sont pas tous des som mets du polyèdre des solu tions dans l’espace
à n dimen sions ; autre ment dit, les coor don nées de cer tains de ces points ne véri fient pas une ou
plu sieurs contraintes. Ainsi, le polyèdre que nous avons consi déré plus haut, comme exemple, ne
compte que 10 som mets, alors qu’il existe @
3
7 5 35 points d’inter sec tion des plans 3 à 3. Mais ce
fait ne res treint pas le pro blème, puisqu’il fau drait exa mi ner toutes les inter sec tions pour déter mi
ner les som mets « admis sibles » c’est àdire véri fiant toutes les contraintes.