Calculatrice de la méthode du simplexe
Résoudre des problèmes d’optimisation à l’aide de la méthode du simplexe
La calculatrice résoudra le problème d’optimisation donné à l’aide de l’algorithme du simplexe. Elle ajoutera, si nécessaire, des variables d’écart, d’excédent et des variables artificielles. En présence de variables artificielles, la méthode du grand M ou la méthode en deux phases est utilisée pour déterminer la solution initiale. Les étapes sont disponibles.
Votre saisie
Maximiser $$$Z = 3 x_{1} + 4 x_{2}$$$, sous les contraintes $$$\begin{cases} x_{1} + 2 x_{2} \leq 8 \\ x_{1} + x_{2} \leq 6 \\ x_{2} \geq 0 \\ x_{1} \geq 0 \end{cases}$$$.
Solution
Le problème sous forme canonique peut s’écrire comme suit :
$$Z = 3 x_{1} + 4 x_{2} \to max$$$$\begin{cases} x_{1} + 2 x_{2} \leq 8 \\ x_{1} + x_{2} \leq 6 \\ x_{1}, x_{2} \geq 0 \end{cases}$$Ajoutez des variables (d’écart ou d’excédent) pour convertir toutes les inégalités en égalités :
$$Z = 3 x_{1} + 4 x_{2} \to max$$$$\begin{cases} x_{1} + 2 x_{2} + S_{1} = 8 \\ x_{1} + x_{2} + S_{2} = 6 \\ x_{1}, x_{2}, S_{1}, S_{2} \geq 0 \end{cases}$$Écrivez le tableau du simplexe :
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Solution |
| $$$Z$$$ | $$$-3$$$ | $$$-4$$$ | $$$0$$$ | $$$0$$$ | $$$0$$$ |
| $$$S_{1}$$$ | $$$1$$$ | $$$2$$$ | $$$1$$$ | $$$0$$$ | $$$8$$$ |
| $$$S_{2}$$$ | $$$1$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ | $$$6$$$ |
La variable entrante est $$$x_{2}$$$, car elle a le coefficient le plus négatif $$$-4$$$ dans la ligne Z.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Solution | Ratio |
| $$$Z$$$ | $$$-3$$$ | $$$-4$$$ | $$$0$$$ | $$$0$$$ | $$$0$$$ | |
| $$$S_{1}$$$ | $$$1$$$ | $$$2$$$ | $$$1$$$ | $$$0$$$ | $$$8$$$ | $$$\frac{8}{2} = 4$$$ |
| $$$S_{2}$$$ | $$$1$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ | $$$6$$$ | $$$\frac{6}{1} = 6$$$ |
La variable sortante est $$$S_{1}$$$, car elle a le plus petit rapport.
Divisez la ligne $$$1$$$ par $$$2$$$ : $$$R_{1} = \frac{R_{1}}{2}$$$.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Solution |
| $$$Z$$$ | $$$-3$$$ | $$$-4$$$ | $$$0$$$ | $$$0$$$ | $$$0$$$ |
| $$$x_{2}$$$ | $$$\frac{1}{2}$$$ | $$$1$$$ | $$$\frac{1}{2}$$$ | $$$0$$$ | $$$4$$$ |
| $$$S_{2}$$$ | $$$1$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ | $$$6$$$ |
Ajouter la ligne $$$2$$$ multipliée par $$$4$$$ à la ligne $$$1$$$ : $$$R_{1} = R_{1} + 4 R_{2}$$$.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Solution |
| $$$Z$$$ | $$$-1$$$ | $$$0$$$ | $$$2$$$ | $$$0$$$ | $$$16$$$ |
| $$$x_{2}$$$ | $$$\frac{1}{2}$$$ | $$$1$$$ | $$$\frac{1}{2}$$$ | $$$0$$$ | $$$4$$$ |
| $$$S_{2}$$$ | $$$1$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ | $$$6$$$ |
Soustraire la ligne $$$2$$$ à la ligne $$$3$$$: $$$R_{3} = R_{3} - R_{2}$$$.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Solution |
| $$$Z$$$ | $$$-1$$$ | $$$0$$$ | $$$2$$$ | $$$0$$$ | $$$16$$$ |
| $$$x_{2}$$$ | $$$\frac{1}{2}$$$ | $$$1$$$ | $$$\frac{1}{2}$$$ | $$$0$$$ | $$$4$$$ |
| $$$S_{2}$$$ | $$$\frac{1}{2}$$$ | $$$0$$$ | $$$- \frac{1}{2}$$$ | $$$1$$$ | $$$2$$$ |
La variable entrante est $$$x_{1}$$$, car elle a le coefficient le plus négatif $$$-1$$$ dans la ligne Z.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Solution | Ratio |
| $$$Z$$$ | $$$-1$$$ | $$$0$$$ | $$$2$$$ | $$$0$$$ | $$$16$$$ | |
| $$$x_{2}$$$ | $$$\frac{1}{2}$$$ | $$$1$$$ | $$$\frac{1}{2}$$$ | $$$0$$$ | $$$4$$$ | $$$\frac{4}{\frac{1}{2}} = 8$$$ |
| $$$S_{2}$$$ | $$$\frac{1}{2}$$$ | $$$0$$$ | $$$- \frac{1}{2}$$$ | $$$1$$$ | $$$2$$$ | $$$\frac{2}{\frac{1}{2}} = 4$$$ |
La variable sortante est $$$S_{2}$$$, car elle a le plus petit rapport.
Multipliez la ligne $$$2$$$ par $$$2$$$ : $$$R_{2} = 2 R_{2}$$$.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Solution |
| $$$Z$$$ | $$$-1$$$ | $$$0$$$ | $$$2$$$ | $$$0$$$ | $$$16$$$ |
| $$$x_{2}$$$ | $$$\frac{1}{2}$$$ | $$$1$$$ | $$$\frac{1}{2}$$$ | $$$0$$$ | $$$4$$$ |
| $$$x_{1}$$$ | $$$1$$$ | $$$0$$$ | $$$-1$$$ | $$$2$$$ | $$$4$$$ |
Ajoutez la ligne $$$3$$$ à la ligne $$$1$$$ : $$$R_{1} = R_{1} + R_{3}$$$.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Solution |
| $$$Z$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$2$$$ | $$$20$$$ |
| $$$x_{2}$$$ | $$$\frac{1}{2}$$$ | $$$1$$$ | $$$\frac{1}{2}$$$ | $$$0$$$ | $$$4$$$ |
| $$$x_{1}$$$ | $$$1$$$ | $$$0$$$ | $$$-1$$$ | $$$2$$$ | $$$4$$$ |
Soustraire $$$\frac{1}{2}$$$ fois la ligne $$$3$$$ à la ligne $$$2$$$: $$$R_{2} = R_{2} - \frac{R_{3}}{2}$$$.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Solution |
| $$$Z$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$2$$$ | $$$20$$$ |
| $$$x_{2}$$$ | $$$0$$$ | $$$1$$$ | $$$1$$$ | $$$-1$$$ | $$$2$$$ |
| $$$x_{1}$$$ | $$$1$$$ | $$$0$$$ | $$$-1$$$ | $$$2$$$ | $$$4$$$ |
Aucun des coefficients de la ligne Z n’est négatif.
L'optimum est atteint.
La solution suivante est obtenue : $$$\left(x_{1}, x_{2}, S_{1}, S_{2}\right) = \left(4, 2, 0, 0\right)$$$.
Réponse
$$$Z = 20$$$A s'obtient pour $$$\left(x_{1}, x_{2}\right) = \left(4, 2\right)$$$A.