Exemples de problème
- Une usine produit deux modèles de machines, l'une que l'on appellera modèle A exige 2 kg de matière première et de 30 heures de fabrication et donne un bénéfice de 7€. L'autre que l'on appellera B exige 4 kg de matière première et de 15 heures de fabrication et donne un bénéfice de 6€. On dispose de 200 kg de matière première et de 1200 h de travail.
Quelle production doit on avoir pour obtenir un bénéfice maximal ?
- Renault fabrique des voitures
et des camions. Chaque véhicule doit être traité dans
l'atelier de peinture et dans l'atelier de carrosserie. La
capacité de l'atelier de peinture permet de traiter 40
camions par jour (si l'on ne peint que des camions), ou 60
voitures par jour (si l'on ne peint que des voitures). De la
même façon la capacité de l'atelier de carrosserie est
limitée à 50 camions par jour et à 50 voitures par jour.
Chaque camion produit rapporte 3000€, et chaque voiture
1000€.
Quel plan de production quotidien doit adopter Renault pour maximiser le profit de l'entreprise ?
Et si en plus, le fabriquant impose à ses employés de faire sortir de son usine au moins 30 camions et 20 voitures par jour ?
Mise en inéquation
Reprenons les exemples précédents et traduisons les en langage mathématiques.
- La question est de savoir combien de produit A et B peut-on produire au maximum. Notons simplement \( A\) le nombre de produit A et \( B\) le nombre de produit B. Les contraintes de l'énoncé se traduisent ainsi :
- \( \bullet\) Domaine :
- \( A\) et \( B\) sont des entiers positifs
- \( \bullet\) La matière première :
- 2 kg pour le produit A, 4 kg pour le produit B et le tout ne doit pas dépasser la quantité maximale de matière première soit 200 kg :
\[2A+4B\leqslant 200\]
- \( \bullet\) Temps de fabrication :
- 30 h pour le produit A, 15 h pour le produit B ; le tout ne dépassant pas 1200 h :
\[30A+15B\leqslant 1200\]
- \( \bullet\) Le bénéfice :
- de 7€, pour le A et de 6€, pour le B. Bien sur on souhaite que ce bénéfice soit maximal ; on cherche donc \( A\) et \( B\) tel que
\[7A+6B\]
soit maximal.
- On note \( c\) le nombre de camion produit quotidiennement et \( v\) le nombre de voiture.
- \( \bullet\) Domaine :
- \( c\) et \( v\) sont des entiers positifs.
- \( \bullet\) Capacité des ateliers :
- en un jour on ne peut prendre qu'un maximum de 40 camions dans l'atelier de peinture. Le temps de traitement d'un camion est de \( \dpl{\frac{1}{40}}\) de jour et par la même méthode le temps de traitement d'une voiture est \( \dpl{\frac{1}{60}}\) de jour. La contrainte sur la capacité de l'atelier de peinture s'exprime donc de la manière suivante
\[\frac{1}{40} c + \frac{1}{60} v \leqslant 1\]
En raisonnant de même, la contrainte sur l'atelier de carrosserie s'exprime par
\[\frac{1}{50} c + \frac{1}{50} v \leqslant 1\]
- \( \bullet\) Le bénéfice :
- on doit le maximiser c'est à dire trouver la valeur maximale de
\[3000c+1000v\]
- \( \bullet\) ... et si en plus :
- la condition supplémentaire se traduit simplement par
\[c\geqslant 30,\qquad v\geqslant 20\]
Avant de résoudre ces problèmes en nombres entiers, c'est à dire en satisfaisant toutes les contraintes de domaine, nous allons détailler les méthodes qui permettent de les résoudre en continue, c'est à dire dans \( \R\) .
Résolution graphique
Lorsque le problème posé fait apparaitre deux variables on peut développer une méthode de résolution (en continue) par analyse graphique. Prenons l'exemple 1. La formulation mathématique du problème a fait apparaitre 4 inéquations du plan :
\begin{eqnarray*}
A &\geqslant& 0\\
B &\geqslant& 0\\
2A+4B&\leqslant& 200\\
30A+15B&\leqslant& 1200
\end{eqnarray*}
Représentons ce domaine (\( A\) en abscisse et \( B\) en ordonnée) ; les droites dessinées correspondent aux droites d'équations \( A\longmapsto B=\dfrac{200-2A}{4}\) et
\( A\longmapsto B=\dfrac{1200-30A}{15}\)
On observe que ce domaine défini un polyèdre convexe (la partie la plus claire). En fait ça sera toujours le cas.
On rappel que le problème est de trouver \( A\) et \( B\) de sorte que le bénéfice \( 7A+6B\) soit maximal.
Imaginons que nous souhaitons un bénéfice nul (pourquoi pas ?). Cela se traduit par le fait de trouver \( A\) et \( B\) dans le domaine convexe tel que \( 7A+6B=0\) . On trace donc la droite
\( \dpl{A\longmapsto B=\frac{0-7A}{6}}\) .
On observe que cette droite touche le domaine en l'origine, c'est à dire lorsque \( A=B=0\) ; ce qui est normal : on ne produit rien, on a donc aucun bénéfice.
Cela nous amène alors à considérer la familles de droites \( \dpl{\left\{A\longmapsto B=\frac{M-7A}{6}\right\}_{M\in\R_+}}\) qui sont toutes parallèles (puisqu'elles possèdent le même coefficient directeur). Lorsque le \( M\) grandit, c'est à dire lorsque le bénéfice augmente, la droite se translate vers le haut puisque le \( M\) représente l'ordonnée à l'origine.
Par lecture graphique on observe donc que la valeur maximale de \( M\) est atteint au point d'intersection des droites \( \dpl{A\longmapsto B=\frac{200-2A}{4}}\) et
\( \dpl{A\longmapsto B=\frac{1200-30A}{15}}\) ; ceci se produit lorsque \( A=20\) donc \( B=40\) et \( M=7A+6B=380\) .
C'est la solution optimale, car si le bénéfice augmente on sort du domaine imposé par les contraintes.
En procédant de la sorte pour n'importe qu'elle type de tel problème on en déduit nécessairement que la solution est sur "coin" du polyèdre convexe.
Remarque
Lorsque l'on est face à un tel problème (linéaire et ne faisant apparaitre que deux variables) on représente le domaine et on détermine les "coins" du polyèdre.
Reprenons notre exemple :
\begin{eqnarray*}
A &\geqslant& 0\\
B &\geqslant& 0\\
2A+4B&\leqslant& 200\\
30A+15B&\leqslant& 1200\\
Max(7A+6B)&&
\end{eqnarray*}
Pour chaque "coin" on calcul la valeur de la fonction à optimiser, dans notre exemple \( 7A+6B\) et on cherche la plus grande valeur (car il s'agit d'un maximum, si c'est un minimum on va bien sur prendre le minimum).
\[
\begin{array}{c|c}
(x,y)&7A+6B\\\hline
(0,0)&0\\
(40,0)&280\\
(0,50)&300\\
(20,40)&380
\end{array}
\]
On arrive donc à la même conclusion que précédemment : il faut produire 20 produit A et 40 produit B pour obtenir un bénéfice maximum de 380€.
