1. Énoncé du problème : Maximiser $Z = 3x_1 + 2x_2$ sous les contraintes : $$6x_1 + 2x_2 \leq 24$$ $$10x_1 + 3x_2 \leq 30$$ $$x_1, x_2 \geq 0$$ 2. Formule et méthode : Le problème est une programmation linéaire. La méthode du simplexe consiste à transformer les inégalités en égalités en ajoutant des variables d'écart (slack variables) et à optimiser la fonction objectif. 3. Ajout des variables d'écart : $$6x_1 + 2x_2 + s_1 = 24$$ $$10x_1 + 3x_2 + s_2 = 30$$ avec $s_1, s_2 \geq 0$. 4. Tableau initial du simplexe : Variables de base : $s_1, s_2$ | Base | $x_1$ | $x_2$ | $s_1$ | $s_2$ | RHS | |-------|-------|-------|-------|-------|-----| | $s_1$ | 6 | 2 | 1 | 0 | 24 | | $s_2$ | 10 | 3 | 0 | 1 | 30 | | $Z$ | -3 | -2 | 0 | 0 | 0 | 5. Choix de la variable entrante : La variable avec le coefficient négatif le plus grand en $Z$ est $x_1$ (coefficient -3). 6. Calcul du ratio pour la variable sortante : $$\frac{24}{6} = 4$$ $$\frac{30}{10} = 3$$ Le plus petit ratio est 3, donc $s_2$ sort. 7. Pivot sur la ligne $s_2$, colonne $x_1$ : Divisons la ligne $s_2$ par 10 : $$\frac{1}{10} \times (10x_1 + 3x_2 + s_2 = 30) \Rightarrow x_1 + \frac{3}{10}x_2 + \frac{1}{10}s_2 = 3$$ 8. Mise à jour de la ligne $s_1$ : Soustrayons $6 \times$ la nouvelle ligne $s_2$ de la ligne $s_1$ : $$6x_1 + 2x_2 + s_1 = 24$$ $$- 6 \times (x_1 + \frac{3}{10}x_2 + \frac{1}{10}s_2 = 3)$$ $$\Rightarrow 6x_1 + 2x_2 + s_1 - 6x_1 - \frac{18}{10}x_2 - \frac{6}{10}s_2 = 24 - 18$$ $$\Rightarrow 0x_1 + (2 - 1.8)x_2 + s_1 - 0.6s_2 = 6$$ $$\Rightarrow 0x_1 + 0.2x_2 + s_1 - 0.6s_2 = 6$$ 9. Mise à jour de la ligne $Z$ : Ajoutons $3 \times$ la nouvelle ligne $s_2$ à la ligne $Z$ : $$-3x_1 - 2x_2 = 0$$ $$+ 3 \times (x_1 + \frac{3}{10}x_2 + \frac{1}{10}s_2 = 3)$$ $$\Rightarrow -3x_1 - 2x_2 + 3x_1 + \frac{9}{10}x_2 + \frac{3}{10}s_2 = 9$$ $$\Rightarrow 0x_1 + (-2 + 0.9)x_2 + 0.3s_2 = 9$$ $$\Rightarrow 0x_1 - 1.1x_2 + 0.3s_2 = 9$$ 10. Nouveau tableau : | Base | $x_1$ | $x_2$ | $s_1$ | $s_2$ | RHS | |-------|-------|-------|-------|-------|-----| | $s_1$ | 0 | 0.2 | 1 | -0.6 | 6 | | $x_1$ | 1 | 0.3 | 0 | 0.1 | 3 | | $Z$ | 0 | -1.1 | 0 | 0.3 | 9 | 11. Nouvelle variable entrante : Le coefficient négatif le plus grand dans $Z$ est $x_2$ avec -1.1. 12. Calcul du ratio pour la variable sortante : Pour $s_1$ : $\frac{6}{0.2} = 30$ Pour $x_1$ : $\frac{3}{0.3} = 10$ Le plus petit ratio est 10, donc $x_1$ sort. 13. Pivot sur la ligne $x_1$, colonne $x_2$ : Divisons la ligne $x_1$ par 0.3 : $$\frac{1}{0.3} \times (x_1 + 0.3x_2 + 0.1s_2 = 3) \Rightarrow \frac{1}{0.3}x_1 + x_2 + \frac{1}{3}s_2 = 10$$ Mais $x_1$ est la variable de base, on veut isoler $x_2$ : $$x_2 = 10 - \frac{1}{0.3}x_1 - \frac{1}{3}s_2$$ Cependant, pour le simplexe, on pivote pour que $x_2$ soit dans la base, donc on exprime $x_1$ en fonction de $x_2$ : $$x_1 = 3 - 0.3x_2 - 0.1s_2$$ On divise la ligne $x_1$ par 0.3 pour que le pivot soit 1 : $$x_1 = 3 - 0.3x_2 - 0.1s_2$$ On inverse pour $x_2$ : $$x_2 = \frac{1}{0.3}x_1 - \frac{10}{0.3} + \frac{1}{3}s_2$$ Mais pour le simplexe, on fait : Nouvelle ligne $x_2$ = (ancienne ligne $x_1$) divisé par 0.3 : $$x_2 + \frac{1}{3}s_2 + \frac{1}{0.3}x_1 = 10$$ Pour simplifier, on fait pivot sur $x_2$ dans la ligne $x_1$ : $$x_1 = 3 - 0.3x_2 - 0.1s_2$$ Donc on remplace $x_1$ dans les autres lignes. 14. Mise à jour de la ligne $s_1$ : $$0.2x_2 + s_1 - 0.6s_2 = 6$$ Remplaçons $x_2$ par $\frac{1}{0.3}(x_1 - 3 + 0.1s_2)$ : $$0.2 \times \frac{1}{0.3}(x_1 - 3 + 0.1s_2) + s_1 - 0.6s_2 = 6$$ $$\Rightarrow \frac{0.2}{0.3}x_1 - \frac{0.2}{0.3} \times 3 + \frac{0.2}{0.3} \times 0.1s_2 + s_1 - 0.6s_2 = 6$$ $$\Rightarrow \frac{2}{3}x_1 - 2 + \frac{2}{30}s_2 + s_1 - 0.6s_2 = 6$$ $$\Rightarrow \frac{2}{3}x_1 + s_1 + \left(\frac{2}{30} - 0.6\right)s_2 = 8$$ $$\Rightarrow \frac{2}{3}x_1 + s_1 - 0.5333s_2 = 8$$ 15. Mise à jour de la ligne $Z$ : $$-1.1x_2 + 0.3s_2 = 9$$ Remplaçons $x_2$ par $\frac{1}{0.3}(x_1 - 3 + 0.1s_2)$ : $$-1.1 \times \frac{1}{0.3}(x_1 - 3 + 0.1s_2) + 0.3s_2 = 9$$ $$\Rightarrow -3.6667x_1 + 11 - 0.3667s_2 + 0.3s_2 = 9$$ $$\Rightarrow -3.6667x_1 + 11 - 0.0667s_2 = 9$$ $$\Rightarrow -3.6667x_1 - 0.0667s_2 = -2$$ 16. Comme il n'y a plus de coefficient négatif dans $Z$ pour les variables hors base, la solution optimale est atteinte. 17. Solution optimale : Variables de base : $x_2$ et $s_1$ $$x_1 = 0$$ $$x_2 = 10$$ $$Z = 3(0) + 2(10) = 20$$ **Réponse finale :** $$x_1 = 0, x_2 = 10, Z_{max} = 20$$