Chapitre 8 • La pro gram ma tion linéaire
304
Il coupe Ox 1 en α (2 875 ; 0 ; 0), Ox 2 en β (0 ; 958,33 ; 0) et Ox 3 en γ (0; 0; 3 833,33).
Son unique point de contact avec le polyèdre des solu tions est le point Q (250, 500,
1 500), d’où la solu tion opti male :
x
*
1 5 250 ; x
*
2 5 500 ;
x
*
3 5 1 500 ; z
* 5 11 500.
8.1.4 Rai son ne ment éco no mique
On remarque qu’un rai son ne ment pure ment éco no mique suf fit, ici, à résoudre la
ques tion. En effet, les ren de ments horaires peuvent aussi être expri més en uni tés
moné taires ; ils sont res pec ti ve ment, pour les produits P 1 , P 2 et P 3 : 4 euros 3 50 5
200 euros/h, 12 euros 3 25 5 300 euros/h ; 3 euros 3 75 5 225 euros/h. Il appa raît
donc que, si l’on désire maxi mi ser le pro fit, il faut fabri quer d’abord la plus grande
quan tité pos sible du pro duit P 2 , puisqu’il four nit le pro fit horaire le plus élevé ; s’il
reste du temps, on fabri quera ensuite des uni tés P 3 , dont le ren de ment moné taire
vient au second rang ; en der nier lieu, si l’on n’a pas épuisé le temps de pro duc tion
(45 h), il fau dra pro duire des uni tés de P 1 .
En fait, ce rai son ne ment s’appuie sur le fait que, si l’on vou lait fabri quer les
quan ti tés maximales des trois produits, on devrait faire fonc tion ner la machine pen
dant 60 heures. Comme on dis pose de 45 heures seule ment, il est indis pen sable de
les employer au mieux.
Il n’est pas dif fi cile de voir que la solu tion consiste à fabri quer toutes les uni -
tés P 2 , ce qui occupe la machine durant 20 heures, puis toutes les uni tés de P 3 , ce
qui occupe encore la machine pen dant 20 heures ; fina le ment, il ne reste plus que
5 heures pour fabri quer des uni tés de P 1 , ce qui cor res pon dant à une quan tité de
5 3 50 5 250 uni tés de P 1 . Le résul tat s’éta blit donc ainsi :
uni tés de P 1 : 250 ; uni tés de P 2 : 500 ; uni tés de P 3 : 1 500 ;
profit total : (250 3 4) 1 (500 3 12) 1 (1 500 3 3) 5 11 500 euros/semaine.
Mais la méthode que nous venons d’uti li ser n’a pas un carac tère géné ral. Notre but
est d’intro duire un algo rithme per met tant la réso lu tion géné rale des pro grammes
linéaires.
8.1.5 Dif fi cul tés de géné ra li sa tion
Évi dem ment la résolu tion géo mé trique ne peut pas s’étendre au cas d’un nombre
de variables supé rieur à trois, puisqu’il n’est pas pos sible d’effec tuer des repré sen
ta tions géo mé triques dans un espace à n dimen sions dès que n dépasse 3.
D’autre part, même avec seulement 3 variables, le rai son ne ment éco no mique
échoue lorsque le nombre de contraintes aug mente. Sup po sons seule ment que nous
ajou tions ici une contrainte de capa cité de sto ckage :
x 1 1 2x 2 1 2x 3 < 4 000
304
Il coupe Ox 1 en α (2 875 ; 0 ; 0), Ox 2 en β (0 ; 958,33 ; 0) et Ox 3 en γ (0; 0; 3 833,33).
Son unique point de contact avec le polyèdre des solu tions est le point Q (250, 500,
1 500), d’où la solu tion opti male :
x
*
1 5 250 ; x
*
2 5 500 ;
x
*
3 5 1 500 ; z
* 5 11 500.
8.1.4 Rai son ne ment éco no mique
On remarque qu’un rai son ne ment pure ment éco no mique suf fit, ici, à résoudre la
ques tion. En effet, les ren de ments horaires peuvent aussi être expri més en uni tés
moné taires ; ils sont res pec ti ve ment, pour les produits P 1 , P 2 et P 3 : 4 euros 3 50 5
200 euros/h, 12 euros 3 25 5 300 euros/h ; 3 euros 3 75 5 225 euros/h. Il appa raît
donc que, si l’on désire maxi mi ser le pro fit, il faut fabri quer d’abord la plus grande
quan tité pos sible du pro duit P 2 , puisqu’il four nit le pro fit horaire le plus élevé ; s’il
reste du temps, on fabri quera ensuite des uni tés P 3 , dont le ren de ment moné taire
vient au second rang ; en der nier lieu, si l’on n’a pas épuisé le temps de pro duc tion
(45 h), il fau dra pro duire des uni tés de P 1 .
En fait, ce rai son ne ment s’appuie sur le fait que, si l’on vou lait fabri quer les
quan ti tés maximales des trois produits, on devrait faire fonc tion ner la machine pen
dant 60 heures. Comme on dis pose de 45 heures seule ment, il est indis pen sable de
les employer au mieux.
Il n’est pas dif fi cile de voir que la solu tion consiste à fabri quer toutes les uni -
tés P 2 , ce qui occupe la machine durant 20 heures, puis toutes les uni tés de P 3 , ce
qui occupe encore la machine pen dant 20 heures ; fina le ment, il ne reste plus que
5 heures pour fabri quer des uni tés de P 1 , ce qui cor res pon dant à une quan tité de
5 3 50 5 250 uni tés de P 1 . Le résul tat s’éta blit donc ainsi :
uni tés de P 1 : 250 ; uni tés de P 2 : 500 ; uni tés de P 3 : 1 500 ;
profit total : (250 3 4) 1 (500 3 12) 1 (1 500 3 3) 5 11 500 euros/semaine.
Mais la méthode que nous venons d’uti li ser n’a pas un carac tère géné ral. Notre but
est d’intro duire un algo rithme per met tant la réso lu tion géné rale des pro grammes
linéaires.
8.1.5 Dif fi cul tés de géné ra li sa tion
Évi dem ment la résolu tion géo mé trique ne peut pas s’étendre au cas d’un nombre
de variables supé rieur à trois, puisqu’il n’est pas pos sible d’effec tuer des repré sen
ta tions géo mé triques dans un espace à n dimen sions dès que n dépasse 3.
D’autre part, même avec seulement 3 variables, le rai son ne ment éco no mique
échoue lorsque le nombre de contraintes aug mente. Sup po sons seule ment que nous
ajou tions ici une contrainte de capa cité de sto ckage :
x 1 1 2x 2 1 2x 3 < 4 000