Kalkulator metody simpleks

Kalkulator rozwiąże podany problem optymalizacyjny przy użyciu algorytmu simpleks. W razie potrzeby doda luz, nadwyżkę i zmienne sztuczne. W przypadku zmiennych sztucznych do określenia rozwiązania początkowego używana jest metoda Big M lub metoda dwufazowa. Dostępne są kroki.

Funkcja celu:

Maksymalizować?

Ograniczenia:

Oddzielone przecinkami.

Czy wszystkie zmienne są nieujemne?

Metoda sztucznego rozwiązania początkowego:

Jeśli kalkulator nie obliczył czegoś lub zidentyfikowałeś błąd, lub masz sugestię / opinię, skontaktuj się z nami.

Twój wkład

Maksymalizuj $Z = 3 x_{1} + 4 x_{2}$ , z zastrzeżeniem $\begin{cases} x_{1} + 2 x_{2} \leq 8 \\ x_{1} + x_{2} \leq 6 \\ x_{1} \geq 0 \\ x_{2} \geq 0 \end{cases}$ .

Rozwiązanie

Problem w postaci kanonicznej można zapisać następująco:

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}

Dodaj zmienne (luz lub nadwyżkę), aby przekształcić wszystkie nierówności w równości:

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}

Zapisz tablicę simpleksową:

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Rozwiązanie
$Z$	$-3$	$-4$	$0$	$0$	$0$
$S_{1}$	$1$	$2$	$1$	$0$	$8$
$S_{2}$	$1$	$1$	$0$	$1$	$6$

Zmienną wejściową jest $x_{2}$ , ponieważ ma najbardziej ujemny współczynnik $-4$ w rzędzie Z.

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Rozwiązanie	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$

Zmienną początkową jest $S_{1}$ , ponieważ ma ona najmniejszy współczynnik.

Podziel wiersz $1$ przez $2$ : $R_{1} = \frac{R_{1}}{2}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Rozwiązanie
$Z$	$-3$	$-4$	$0$	$0$	$0$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$
$S_{2}$	$1$	$1$	$0$	$1$	$6$

Dodaj wiersz $2$ pomnożony przez $4$ do wiersza $1$ : $R_{1} = R_{1} + 4 R_{2}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Rozwiązanie
$Z$	$-1$	$0$	$2$	$0$	$16$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$
$S_{2}$	$1$	$1$	$0$	$1$	$6$

Odejmij wiersz $2$ od wiersza $3$ : $R_{3} = R_{3} - R_{2}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Rozwiązanie
$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$

Zmienną wejściową jest $x_{1}$ , ponieważ ma najbardziej ujemny współczynnik $-1$ w rzędzie Z.

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Rozwiązanie	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$

Zmienną początkową jest $S_{2}$ , ponieważ ma ona najmniejszy współczynnik.

Pomnóż wiersz $2$ przez $2$ : $R_{2} = 2 R_{2}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Rozwiązanie
$Z$	$-1$	$0$	$2$	$0$	$16$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$
$x_{1}$	$1$	$0$	$-1$	$2$	$4$

Dodaj wiersz $3$ do wiersza $1$ : $R_{1} = R_{1} + R_{3}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Rozwiązanie
$Z$	$0$	$0$	$1$	$2$	$20$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$
$x_{1}$	$1$	$0$	$-1$	$2$	$4$

Odejmij wiersz $3$ pomnożony przez $\frac{1}{2}$ od wiersza $2$ : $R_{2} = R_{2} - \frac{R_{3}}{2}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Rozwiązanie
$Z$	$0$	$0$	$1$	$2$	$20$
$x_{2}$	$0$	$1$	$1$	$-1$	$2$
$x_{1}$	$1$	$0$	$-1$	$2$	$4$

Żaden ze współczynników rzędu Z nie jest ujemny.

Osiągnięto optimum.

Otrzymano następujące rozwiązanie: $\left(x_{1}, x_{2}, S_{1}, S_{2}\right) = \left(4, 2, 0, 0\right)$ .

Odpowiedź

$Z = 20$ A osiąga się na stronie $\left(x_{1}, x_{2}\right) = \left(4, 2\right)$ A.

Kalkulator metody simpleks

Rozwiązywanie problemów optymalizacyjnych przy użyciu metody simpleks

Twój wkład

Rozwiązanie

Odpowiedź