[Exercice 4.24]

Une entreprise fabrique deux produits en quantités $x_1$ pour le premier et $x_2$ pour le second. Ces deux produits sont obtenus par le passage dans deux processus opérés par deux départements distincts dont la main d'œuvre permet un temps opératoire disponible de 2110 heures pour le premier département et de 1900 pour le second. Bien que les conditions technologiques soient identiques dans les deux départements, les temps de production unitaires sont distincts. On a le tableau suivant (en heure par unités produites) :

Tables

Produit	Département ①	Département ②
$x_1$	1	4
$x_2$	3	2

La demande est telle que l'entreprise doit produire au plus 200 unités du produit $x_1$ et au moins 300 du produit $x_2$ sachant que leurs prix de vente est de 4 pour le produit $x_1$ et de 3 pour le produit $x_2$.

Construire le programme.
Construire le domaine de faisabilité associé à ce problème :

Tracer les contraintes.
Obtenir les sommets et les placer.
Rajouter l'objectif
Déterminer le maximum du profit par déduction.

Déterminer l'optimum en évaluant l'objectif sur chaque sommet en déterminant le sommet qui donne la valeur la plus élevée de l'objectif.
Pourquoi ne peut-on pas appliquer la méthode du simplexe canonique sur cet exemple ?
Déterminer l'optimum par élimination de Fourier-Motzkin. Hint : il suffit de rajouter l'objectif comme une inégalité $z\leq \ldots$ et de conserver $z$ jusqu'à la fin de la procédure d'élimination. Alors, la valeur du membre de droite donne le maximum de $z$. Il suffit alors de remonter pour obtenir $x_1$ et $x_2$.
Déterminer la solution par la méthode du simplex.

On commence par construire le programme :

\[ \begin{array}{c} \max z = 4x_1+ 3x_2\\ \text{sous les contraintes}\\ x_1 + 3 x_2 \leq 2110\\ 4 x_1 + 2 x_2 \leq 1900\\ x_1 \leq 200\\ x_2 \geq 300\\ x_1 \geq 0\\ x_2 \geq 0 \end{array} \]

cl0

On utilise cette liste pour définir un polygone (polyèdre sur le plan) et obtenir ses sommets.

cl0

Le fait que l'on puisse tracer un polygone à partir des inégalités est la preuve qu'il existe des solutions au système d'équations donné. On peut maintenant placer l'objectif :

cl0

On peut aussi évaluer la fonction objectif sur tous les sommets

cl0

On ne peut appliquer la méthode directe du simplex sur ce problème parce qu'il n'est pas possible de le mettre sous forme standard avec tous les éléments du vecteur $\boldsymbol{b}$ positifs.

On peut en revanche appliquer directement la méthode de Fourier-Motzkin. Pour ce faire, on commence par réécrire le programme comme suit : :

\[ \begin{array}{c} z \leq 4x_1+ 3x_2\\ x_1 + 3 x_2 \leq 2110\\ 4 x_1 + 2 x_2 \leq 1900\\ x_1 \leq 200\\ x_2 \geq 300\\ x_1 \geq 0\\ x_2 \geq 0 \end{array} \]

cl0

On peut trouver la valeur recherchée à l'œil nu ou opérer comme suit. On restreint la liste aux lignes où l'opérateur associé à $z$ est $==$. Puis on recherche la ligne qui donne le $z$ maximal. Pour la première part de l'opération, le mieux est de définir une fonction :

cl0

Pour finir on peut trouver la solution en appelant la méthode du simplex interactive disponible dans Sagemath.

Exercice 4.24 : Production par processus

Énoncé