심플렉스법 계산기

계산기는 심플렉스 알고리즘을 사용하여 주어진 최적화 문제를 풉니다. 필요하면 슬랙 변수, 잉여 변수 및 인공 변수를 추가합니다. 인공 변수가 필요한 경우 초기해를 결정하기 위해 Big M 방법 또는 2단계법을 사용합니다. 풀이 단계가 제공됩니다.

사용자 입력

최대화: $$$Z = 3 x_{1} + 4 x_{2}$$$, 제약조건: $$$\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}$$$

풀이

정준형으로 표현된 문제는 다음과 같이 쓸 수 있습니다:

$$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}$$

모든 부등식을 등식으로 만들기 위해 여유변수 또는 잉여변수를 추가하십시오:

$$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}$$

심플렉스 표를 작성하시오:

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	풀이
$$$Z$$$	$$$-3$$$	$$$-4$$$	$$$0$$$	$$$0$$$	$$$0$$$
$$$S_{1}$$$	$$$1$$$	$$$2$$$	$$$1$$$	$$$0$$$	$$$8$$$
$$$S_{2}$$$	$$$1$$$	$$$1$$$	$$$0$$$	$$$1$$$	$$$6$$$

진입 변수는 $$$x_{2}$$$입니다. Z-행에서 가장 음의 계수 $$$-4$$$를 가지기 때문입니다.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	풀이	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$$$

최소 비율을 가지므로 이탈 변수는 $$$S_{1}$$$입니다.

$$$1$$$번째 행을 $$$2$$$(으)로 나눈다: $$$R_{1} = \frac{R_{1}}{2}$$$.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	풀이
$$$Z$$$	$$$-3$$$	$$$-4$$$	$$$0$$$	$$$0$$$	$$$0$$$
$$$x_{2}$$$	$$$\frac{1}{2}$$$	$$$1$$$	$$$\frac{1}{2}$$$	$$$0$$$	$$$4$$$
$$$S_{2}$$$	$$$1$$$	$$$1$$$	$$$0$$$	$$$1$$$	$$$6$$$

$$$2$$$행에 $$$4$$$를 곱한 것을 $$$1$$$행에 더한다: $$$R_{1} = R_{1} + 4 R_{2}$$$.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	풀이
$$$Z$$$	$$$-1$$$	$$$0$$$	$$$2$$$	$$$0$$$	$$$16$$$
$$$x_{2}$$$	$$$\frac{1}{2}$$$	$$$1$$$	$$$\frac{1}{2}$$$	$$$0$$$	$$$4$$$
$$$S_{2}$$$	$$$1$$$	$$$1$$$	$$$0$$$	$$$1$$$	$$$6$$$

행 $$$3$$$에서 행 $$$2$$$를 뺍니다: $$$R_{3} = R_{3} - R_{2}$$$.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	풀이
$$$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$$$

진입 변수는 $$$x_{1}$$$입니다. Z-행에서 가장 음의 계수 $$$-1$$$를 가지기 때문입니다.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	풀이	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$$$

최소 비율을 가지므로 이탈 변수는 $$$S_{2}$$$입니다.

행 $$$2$$$을(를) $$$2$$$배 합니다: $$$R_{2} = 2 R_{2}$$$.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	풀이
$$$Z$$$	$$$-1$$$	$$$0$$$	$$$2$$$	$$$0$$$	$$$16$$$
$$$x_{2}$$$	$$$\frac{1}{2}$$$	$$$1$$$	$$$\frac{1}{2}$$$	$$$0$$$	$$$4$$$
$$$x_{1}$$$	$$$1$$$	$$$0$$$	$$$-1$$$	$$$2$$$	$$$4$$$

행 $$$3$$$를 행 $$$1$$$에 더한다: $$$R_{1} = R_{1} + R_{3}$$$.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	풀이
$$$Z$$$	$$$0$$$	$$$0$$$	$$$1$$$	$$$2$$$	$$$20$$$
$$$x_{2}$$$	$$$\frac{1}{2}$$$	$$$1$$$	$$$\frac{1}{2}$$$	$$$0$$$	$$$4$$$
$$$x_{1}$$$	$$$1$$$	$$$0$$$	$$$-1$$$	$$$2$$$	$$$4$$$

행 $$$2$$$에서 행 $$$3$$$의 $$$\frac{1}{2}$$$배를 빼십시오: $$$R_{2} = R_{2} - \frac{R_{3}}{2}$$$.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	풀이
$$$Z$$$	$$$0$$$	$$$0$$$	$$$1$$$	$$$2$$$	$$$20$$$
$$$x_{2}$$$	$$$0$$$	$$$1$$$	$$$1$$$	$$$-1$$$	$$$2$$$
$$$x_{1}$$$	$$$1$$$	$$$0$$$	$$$-1$$$	$$$2$$$	$$$4$$$

Z-행의 어떠한 계수도 음수가 아닙니다.

최적해에 도달했습니다.

다음과 같은 해를 얻습니다: $$$\left(x_{1}, x_{2}, S_{1}, S_{2}\right) = \left(4, 2, 0, 0\right)$$$.

정답

$$$Z = 20$$$A는 $$$\left(x_{1}, x_{2}\right) = \left(4, 2\right)$$$A에서 달성된다.

심플렉스법 계산기

심플렉스법을 사용하여 최적화 문제를 해결하세요

사용자 입력

풀이

정답