Chapitre 8 • La pro gram ma tion linéaire
298
Les m contraintes, si elles sont com pa tibles, déli mitent dans un espace à n dimen sions
(autant que de variables) un hyper volume convexe
1
à l’inté rieur ou à la péri phérie duquel
se trouve(nt) le (ou les) point(s) dont les coor don nées (x 1 , x 2 , c , x n ) satis font aux
contraintes. En outre les variables x 1 , x 2 , c , x n sont toujours positives ou nulles.
La pro gram ma tion linéaire a pour objet de résoudre le pro blème d’opti mi sation
qui consiste à maxi mi ser une fonc tion nelle linéaire (la « fonc tion éco no mique »)
dans le domaine ainsi défini.
Nous pen sons qu’il sera plus adapté, au niveau que nous nous fixons, de l’expo ser
sur un exemple concret.
8.1 exempLe de pro gramme Linéaire – aspect
géo mé trique
8.1.1 Pro blème de maxi mi sa tion
Une entre prise peut fabri quer, sur une machine don née, tra vaillant 45 heures par
semaine
2
trois pro duits dif fé rents P 1 , P 2 et P 3 . Cette machine peut fabriquer un seul
type de produits à la fois ; ses temps de réglage sont négligeables. Une unité du pro
duit P 1 laisse un pro fit net de 4 euros, une de P 2 , un pro fit de 12 euros, et enfin, pour
P 3 , de 3 euros. Les ren de ments de la machine sont, res pec ti ve ment pour les trois pro
duits, et dans le même ordre : 50, 25 et 75 uni tés par heure. On sait d’autre part, grâce
à une étude de mar ché, que les pos si bi li tés de vente ne dépassent pas 1 000 uni tés de
P 1 , 500 uni tés de P 2 et 1 500 uni tés de P 3 , par semaine. On se pose le pro blème de
répar tir la capa cité de pro duc tion entre les trois pro duits, de manière à maxi mi ser le
pro fit heb do ma daire.
8.1.2 For mu la tion algé brique
Posons main te nant le pro blème sous forme algé brique. Appe lons x 1 , x 2 et x 3 les quan
ti tés res pec tives (inconnues) des pro duits P 1 , P 2 et P 3 que nous avons à fabri quer
pour obte nir le pro fit maximal. Les quan ti tés des pro duits P 1 , P 2 et P 3 ne doivent pas
dépas ser, res pec ti ve ment 1 000, 500 et 1 500 par semaine ; on peut donc écrire :
1) x 1 < 1 000 ;
2) x 2 < 500 ;
3) x 3 < 1 500.
D’autre part, le temps employé pour pro duire x 1 uni tés de P 1 est en heures :
x 1 3
1
50
; celui qui cor res pond à la fabri ca tion de x 2 uni tés de P 2 est : x 2 3
1
25
; enfin,
pour confec tion ner x 3 uni tés de P 3 , il fau dra x 3 3
1
75
heures. Or, la somme des temps
1. “Convexe” signifie que si l’on prend deux points situés à l’intérieur (ou à la surface) de ce
volume d, le segment les joignant ne sort pas de d.
2. Ce qui n’entraîne pas, bien sûr, que chaque ouvrier doive travailler 45 h par semaine !
298
Les m contraintes, si elles sont com pa tibles, déli mitent dans un espace à n dimen sions
(autant que de variables) un hyper volume convexe
1
à l’inté rieur ou à la péri phérie duquel
se trouve(nt) le (ou les) point(s) dont les coor don nées (x 1 , x 2 , c , x n ) satis font aux
contraintes. En outre les variables x 1 , x 2 , c , x n sont toujours positives ou nulles.
La pro gram ma tion linéaire a pour objet de résoudre le pro blème d’opti mi sation
qui consiste à maxi mi ser une fonc tion nelle linéaire (la « fonc tion éco no mique »)
dans le domaine ainsi défini.
Nous pen sons qu’il sera plus adapté, au niveau que nous nous fixons, de l’expo ser
sur un exemple concret.
8.1 exempLe de pro gramme Linéaire – aspect
géo mé trique
8.1.1 Pro blème de maxi mi sa tion
Une entre prise peut fabri quer, sur une machine don née, tra vaillant 45 heures par
semaine
2
trois pro duits dif fé rents P 1 , P 2 et P 3 . Cette machine peut fabriquer un seul
type de produits à la fois ; ses temps de réglage sont négligeables. Une unité du pro
duit P 1 laisse un pro fit net de 4 euros, une de P 2 , un pro fit de 12 euros, et enfin, pour
P 3 , de 3 euros. Les ren de ments de la machine sont, res pec ti ve ment pour les trois pro
duits, et dans le même ordre : 50, 25 et 75 uni tés par heure. On sait d’autre part, grâce
à une étude de mar ché, que les pos si bi li tés de vente ne dépassent pas 1 000 uni tés de
P 1 , 500 uni tés de P 2 et 1 500 uni tés de P 3 , par semaine. On se pose le pro blème de
répar tir la capa cité de pro duc tion entre les trois pro duits, de manière à maxi mi ser le
pro fit heb do ma daire.
8.1.2 For mu la tion algé brique
Posons main te nant le pro blème sous forme algé brique. Appe lons x 1 , x 2 et x 3 les quan
ti tés res pec tives (inconnues) des pro duits P 1 , P 2 et P 3 que nous avons à fabri quer
pour obte nir le pro fit maximal. Les quan ti tés des pro duits P 1 , P 2 et P 3 ne doivent pas
dépas ser, res pec ti ve ment 1 000, 500 et 1 500 par semaine ; on peut donc écrire :
1) x 1 < 1 000 ;
2) x 2 < 500 ;
3) x 3 < 1 500.
D’autre part, le temps employé pour pro duire x 1 uni tés de P 1 est en heures :
x 1 3
1
50
; celui qui cor res pond à la fabri ca tion de x 2 uni tés de P 2 est : x 2 3
1
25
; enfin,
pour confec tion ner x 3 uni tés de P 3 , il fau dra x 3 3
1
75
heures. Or, la somme des temps
1. “Convexe” signifie que si l’on prend deux points situés à l’intérieur (ou à la surface) de ce
volume d, le segment les joignant ne sort pas de d.
2. Ce qui n’entraîne pas, bien sûr, que chaque ouvrier doive travailler 45 h par semaine !