Kalkulator metody simpleks

Rozwiązywanie problemów optymalizacyjnych przy użyciu 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.

Oddzielone przecinkami.

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=3x1+4x2Z = 3 x_{1} + 4 x_{2}, z zastrzeżeniem {x1+2x28x1+x26x10x20\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=3x1+4x2maxZ = 3 x_{1} + 4 x_{2} \to max{x1+2x28x1+x26x1,x20\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=3x1+4x2maxZ = 3 x_{1} + 4 x_{2} \to max{x1+2x2+S1=8x1+x2+S2=6x1,x2,S1,S20\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ą:

Basicx1x_{1}x2x_{2}S1S_{1}S2S_{2}Rozwiązanie
ZZ3-34-4000000
S1S_{1}1122110088
S2S_{2}1111001166

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

Basicx1x_{1}x2x_{2}S1S_{1}S2S_{2}RozwiązanieRatio
ZZ3-34-4000000
S1S_{1}112211008882=4\frac{8}{2} = 4
S2S_{2}111100116661=6\frac{6}{1} = 6

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

Podziel wiersz 11 przez 22: R1=R12R_{1} = \frac{R_{1}}{2}.

Basicx1x_{1}x2x_{2}S1S_{1}S2S_{2}Rozwiązanie
ZZ3-34-4000000
x2x_{2}12\frac{1}{2}1112\frac{1}{2}0044
S2S_{2}1111001166

Dodaj wiersz 22 pomnożony przez 44 do wiersza 11: R1=R1+4R2R_{1} = R_{1} + 4 R_{2}.

Basicx1x_{1}x2x_{2}S1S_{1}S2S_{2}Rozwiązanie
ZZ1-10022001616
x2x_{2}12\frac{1}{2}1112\frac{1}{2}0044
S2S_{2}1111001166

Odejmij wiersz 22 od wiersza 33: R3=R3R2R_{3} = R_{3} - R_{2}.

Basicx1x_{1}x2x_{2}S1S_{1}S2S_{2}Rozwiązanie
ZZ1-10022001616
x2x_{2}12\frac{1}{2}1112\frac{1}{2}0044
S2S_{2}12\frac{1}{2}0012- \frac{1}{2}1122

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

Basicx1x_{1}x2x_{2}S1S_{1}S2S_{2}RozwiązanieRatio
ZZ1-10022001616
x2x_{2}12\frac{1}{2}1112\frac{1}{2}0044412=8\frac{4}{\frac{1}{2}} = 8
S2S_{2}12\frac{1}{2}0012- \frac{1}{2}1122212=4\frac{2}{\frac{1}{2}} = 4

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

Pomnóż wiersz 22 przez 22: R2=2R2R_{2} = 2 R_{2}.

Basicx1x_{1}x2x_{2}S1S_{1}S2S_{2}Rozwiązanie
ZZ1-10022001616
x2x_{2}12\frac{1}{2}1112\frac{1}{2}0044
x1x_{1}11001-12244

Dodaj wiersz 33 do wiersza 11: R1=R1+R3R_{1} = R_{1} + R_{3}.

Basicx1x_{1}x2x_{2}S1S_{1}S2S_{2}Rozwiązanie
ZZ000011222020
x2x_{2}12\frac{1}{2}1112\frac{1}{2}0044
x1x_{1}11001-12244

Odejmij wiersz 33 pomnożony przez 12\frac{1}{2} od wiersza 22: R2=R2R32R_{2} = R_{2} - \frac{R_{3}}{2}.

Basicx1x_{1}x2x_{2}S1S_{1}S2S_{2}Rozwiązanie
ZZ000011222020
x2x_{2}0011111-122
x1x_{1}11001-12244

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

Osiągnięto optimum.

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

Odpowiedź

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