Calcolatore del metodo del simplesso
Risolvi problemi di ottimizzazione usando il metodo del simplesso
Il calcolatore risolverà il problema di ottimizzazione dato usando l'algoritmo del simplesso. Se necessario, aggiungerà variabili di scarto, di eccedenza e artificiali. In presenza di variabili artificiali, per determinare la soluzione di base ammissibile iniziale si utilizza il metodo della M grande (Big M) oppure il metodo a due fasi. Sono disponibili i passaggi.
Il tuo input
Massimizza $$$Z = 3 x_{1} + 4 x_{2}$$$, soggetto a $$$\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}$$$.
Soluzione
Il problema in forma canonica può essere scritto come segue:
$$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}$$Aggiungi variabili (di scarto o di eccedenza) per trasformare tutte le disuguaglianze in uguaglianze:
$$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}$$Scrivi la tabella del simplesso:
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Soluzione |
| $$$Z$$$ | $$$-3$$$ | $$$-4$$$ | $$$0$$$ | $$$0$$$ | $$$0$$$ |
| $$$S_{1}$$$ | $$$1$$$ | $$$2$$$ | $$$1$$$ | $$$0$$$ | $$$8$$$ |
| $$$S_{2}$$$ | $$$1$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ | $$$6$$$ |
La variabile entrante è $$$x_{2}$$$, perché ha il coefficiente $$$-4$$$ più negativo nella riga Z.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Soluzione | 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 variabile uscente è $$$S_{1}$$$, perché ha il rapporto minimo.
Dividi la riga $$$1$$$ per $$$2$$$: $$$R_{1} = \frac{R_{1}}{2}$$$.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Soluzione |
| $$$Z$$$ | $$$-3$$$ | $$$-4$$$ | $$$0$$$ | $$$0$$$ | $$$0$$$ |
| $$$x_{2}$$$ | $$$\frac{1}{2}$$$ | $$$1$$$ | $$$\frac{1}{2}$$$ | $$$0$$$ | $$$4$$$ |
| $$$S_{2}$$$ | $$$1$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ | $$$6$$$ |
Aggiungi alla riga $$$1$$$ la riga $$$2$$$ moltiplicata per $$$4$$$: $$$R_{1} = R_{1} + 4 R_{2}$$$.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Soluzione |
| $$$Z$$$ | $$$-1$$$ | $$$0$$$ | $$$2$$$ | $$$0$$$ | $$$16$$$ |
| $$$x_{2}$$$ | $$$\frac{1}{2}$$$ | $$$1$$$ | $$$\frac{1}{2}$$$ | $$$0$$$ | $$$4$$$ |
| $$$S_{2}$$$ | $$$1$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ | $$$6$$$ |
Sottrai la riga $$$2$$$ dalla riga $$$3$$$: $$$R_{3} = R_{3} - R_{2}$$$.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Soluzione |
| $$$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 variabile entrante è $$$x_{1}$$$, perché ha il coefficiente $$$-1$$$ più negativo nella riga Z.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Soluzione | 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 variabile uscente è $$$S_{2}$$$, perché ha il rapporto minimo.
Moltiplica la riga $$$2$$$ per $$$2$$$: $$$R_{2} = 2 R_{2}$$$.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Soluzione |
| $$$Z$$$ | $$$-1$$$ | $$$0$$$ | $$$2$$$ | $$$0$$$ | $$$16$$$ |
| $$$x_{2}$$$ | $$$\frac{1}{2}$$$ | $$$1$$$ | $$$\frac{1}{2}$$$ | $$$0$$$ | $$$4$$$ |
| $$$x_{1}$$$ | $$$1$$$ | $$$0$$$ | $$$-1$$$ | $$$2$$$ | $$$4$$$ |
Aggiungi la riga $$$3$$$ alla riga $$$1$$$: $$$R_{1} = R_{1} + R_{3}$$$.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Soluzione |
| $$$Z$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$2$$$ | $$$20$$$ |
| $$$x_{2}$$$ | $$$\frac{1}{2}$$$ | $$$1$$$ | $$$\frac{1}{2}$$$ | $$$0$$$ | $$$4$$$ |
| $$$x_{1}$$$ | $$$1$$$ | $$$0$$$ | $$$-1$$$ | $$$2$$$ | $$$4$$$ |
Sottrai la riga $$$3$$$ moltiplicata per $$$\frac{1}{2}$$$ dalla riga $$$2$$$: $$$R_{2} = R_{2} - \frac{R_{3}}{2}$$$.
| Basic | $$$x_{1}$$$ | $$$x_{2}$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | Soluzione |
| $$$Z$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$2$$$ | $$$20$$$ |
| $$$x_{2}$$$ | $$$0$$$ | $$$1$$$ | $$$1$$$ | $$$-1$$$ | $$$2$$$ |
| $$$x_{1}$$$ | $$$1$$$ | $$$0$$$ | $$$-1$$$ | $$$2$$$ | $$$4$$$ |
Nessuno dei coefficienti della riga Z è negativo.
L'ottimo è stato raggiunto.
Si ottiene la seguente soluzione: $$$\left(x_{1}, x_{2}, S_{1}, S_{2}\right) = \left(4, 2, 0, 0\right)$$$.
Risposta
$$$Z = 20$$$A è raggiunto in $$$\left(x_{1}, x_{2}\right) = \left(4, 2\right)$$$A.