---
lang: ja
tags: MTNS_2023, lecture
---
# 最小添字規則による巡回の回避
講義で紹介した**巡回**が起きる問題：
Confirm that the **cycling** in the following example:
$$
\begin{alignat}{6}
\displaystyle
\max_{x_{1}, x_{2}, x_{3}, x_{4}} \quad
&&3x_{1} &-&5x_{2}&+&x_{3}&-&2x_{4}&=&z\\
\text{s.t.} \quad
&& x_{1}&-&2x_{2}&-&x_{3}&+&2x_{4}&\leq&0\\
&&2x_{1}&-&3x_{2}&-&x_{3}&+&x_{4}&\leq&0\\
&& & & & & x_{3} & & &\leq&1\\
&& x_{1}&,&x_{2}&,&x_{3}&,&x_{4} &\geq&0
\end{alignat}
$$に対し, **最小添字規則**を適用して**単体法**が終了する(**巡回**から抜け出せる)ことを確認せよ.
can be resolved by applying the **smallest subscript rule**.

$$
\begin{align}
\begin{array}{c|cccc|c}
& x_{1} & x_{2} & x_{3} & x_{4} & -1\\
\hline
-r_{1} & 1* & -2 & -1 & 2 & 0\\
-r_{2} & 2 & -3 & -1 & 1 & 0\\
-r_{3} & 0 & 0 & 1 & 0 & 1\\
\hline
-z & -3 & 5 & -1 & 2 & 0
\end{array}&\Rightarrow
\begin{array}{c|cccc|c}
& r_{1} & x_{2} & x_{3} & x_{4} & -1\\
\hline
-x_{1} & 1 & -2 & -1 & 2 & 0\\
-r_{2} & -2 & 1* & 1 & -3 & 0\\
-r_{3} & 0 & 0 & 1 & 0 & 1\\
\hline
-z & 3 & -1 & -4 & 8 & 0
\end{array}\\
&\Rightarrow
\begin{array}{c|cccc|c}
& r_{1} & r_{2} & x_{3} & x_{4} & -1\\
\hline
-x_{1} & -3 & 2 & 1* & -4 & 0\\
-x_{2} & -2 & 1 & 1 & -3 & 0\\
-r_{3} & 0 & 0 & 1 & 0 & 1\\
\hline
-z & 1 & 1 & -3 & 5 & 0
\end{array}\\
&\Rightarrow
\begin{array}{c|cccc|c}
& r_{1} & r_{2} & x_{1} & x_{4} & -1\\
\hline
-x_{3} & -3 & 2 & 1 & -4 & 0\\
-x_{2} & 1 & -1 & -1 & 1* & 0\\
-r_{3} & 3 & -2 & -1 & 4 & 1\\
\hline
-z & -8 & 7 & 3 & -7 & 0
\end{array}\\
\text{最小添字規則を適用 | Apply the smallest subscript rule}
&\Rightarrow
\begin{array}{c|cccc|c}
& r_{1} & r_{2} & x_{1} & x_{2} & -1\\
\hline
-x_{3} & 1 & -2 & -3 & 4 & 0\\
-x_{4} & 1 & -1 & -1 & 1 & 0\\
-r_{3} & -1 & 2 & 3* & -4 & 1\\
\hline
-z & -1 & 0 & -4 & 7 & 0
\end{array}\\
&\Rightarrow
\begin{array}{c|cccc|c}
& r_{1} & r_{2} & r_{3} & x_{2} & -1\\
\hline
-x_{3} & 0 & 0 & 1 & 0 & 1\\
-x_{4} & \frac{2}{3}* & -\frac{1}{3} & \frac{1}{3} & -\frac{1}{3} & \frac{1}{3}\\
-x_{1} & -\frac{1}{3} & \frac{2}{3} & \frac{1}{3} & -\frac{4}{3} & \frac{1}{3}\\
\hline
-z & -\frac{7}{3} & \frac{8}{3} & \frac{4}{3} & \frac{5}{3} & \frac{4}{3}
\end{array}\\
&\Rightarrow
\begin{array}{c|cccc|c}
& x_{4} & r_{2} & r_{3} & x_{2} & -1\\
\hline
-x_{3} & 0 & 0 & 1 & 0 & 1\\
-r_{1} & \frac{3}{2} & -\frac{1}{2} & \frac{1}{2} & -\frac{1}{2} & \frac{1}{2}\\
-x_{1} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & -\frac{3}{2} & \frac{1}{2}\\
\hline
-z & \frac{7}{2} & \frac{3}{2} & \frac{5}{2} & \frac{1}{2} & \frac{5}{2}
\end{array}
\end{align}
$$
これより，最適解は$x_{1}^{\ast}=\frac{1}{2}, x_{3}^{\ast}=1, x_{2}^{\ast}=x_{4} =0$で最適値は$z^{\ast}=\frac{5}{2}$.
It therefore finds that the optimal solution $x_{1}^{\ast}=\frac{1}{2}, x_{3}^{\ast}=1, x_{2}^{\ast}=x_{4} =0$ and the optimal value $z^{\ast}=\frac{5}{2}$.