Exercice 2.1

On va donner la représentation du domaine délimité par les contraintes pas à pas de manière à ce que la méthode soit facile à reproduire :

les équations étant données sous forme implicite, il faut les réécrire sous forme explicite :

$$ \left. \begin{array}{l} 2 x_1+x_2\leq 18\\ 2 x_1+ 3 x_2 \leq 42\\ 3 x_1 + x_2\leq 24\\ x_1 \geq 0\\ x_2 \geq 0 \end{array}\right\}\,\, \Longleftrightarrow \,\, \left\{\begin{array}{l} x_2\leq 18 - 2 x_1 \\ x_2 \leq \left(\frac{1}{3}\right)\left(42 - 2 x_1\right)\\ x_2\leq 24 -3 x_1\\ x_1 \geq 0\\ x_2 \geq 0 \end{array}\right. $$

On commence par les tracer, avec des bornes déterminées sur le pouce. On note dans le code qui suit :

$x_1\geq 0$ est une droite verticale. Pour la représenter, il suffit d'écrire une fonction linéaire de pente très voire très très forte et de limiter sa représentation sur l'axe $x_2$ (comme tout logiciel Sagemath ne connaît dans la représentation 2D que $x$ et $y$) on réalise cela en fixant le paramètre optionnel yrange pas trop élevé. Pour une bonne représentation des droites, on épaissit le trait par l'option thickness.

Il existe plusieurs moyens de déterminer les sommets du polyèdre. Le moyen le plus efficace est le suivant :

On réécrit le système d'équations sous la forme : $\left.\begin{array}{l} 2 x_1+x_2\leq 18\\ 2 x_1+ 3 x_2 \leq 42\\ 3 x_1 + x_2\leq 24\\ x_1 \geq 0\\ x_2 \geq 0 \end{array}\right\}\,\,\Longleftrightarrow\,\, \left.\begin{array}{l} 18 - 2 x_1 - x_2\geq 0\\ 42 - 2 x_1 - 3 x_2 \geq 0\\ 24 - 3 x_1 - x_2\geq 0\\ x_1 \geq 0\\ x_2 \geq 0 \end{array}\right\}$
puis on les encode en ne retenant que leurs paramètres sous la forme suivante : $\begin{array}{c} (18,-2,-1)\\ (42,-2,-3)\\ (24,-3,-1)\\ (0,1,0)\\ (0,0,1) \end{array}$

On obtient le polyèdre avec le code suivant :

On peut maintenant lister les sommets dans un vecteur

On sélectionne les coordonnées des sommets du polyèdre de façon à pouvoir les tracer plus tard :

On a tracé le domaine, on peut rajouter le l'objectif. Clairement on a :

$z= 3 x_1 + 2 x_2 \, \, \Longleftrightarrow \,\, x_2 = \left(\frac{1}{2}\right)z - \left(\frac{3}{2}\right)x_1$

On a donc la représentation suivante

Il est clair que pour tout niveau de $z$, l'objectif se déplace parallèlement dans le plan $(x_1, x_2)$. Donc, c'est le point $SS[0]$ qui correspondent au maximum. Et donc ce maximum prend la valeur :