---
lang: ja
tags: MTNS-2022, lecture, linear programming
---
# 2022年度 交通社会システム論<br>第6回 練習問題 解答例<br>Report #2 Answer
[ポータルへ戻る](https://hackmd.io/@nagae/MTNS_2022)
<div style="text-align: center">

このページへは以下のQRコードまたはURLからアクセスできます：

<code style="font-size:20pt">https://hackmd.io/@nagae/MTNS_2022-Ch05-answer</code>
</div>

## 課題1 | Exercise 1
以下の問題を**単体法**で解け．
Solve the following problem by using the simplex method.
$$
\begin{alignat}{6}
\displaystyle \max_{x_{1}, x_{2}, x_{3}} \quad &x_{1} &+&x_{2}&+&2x_{3}&=&z\\
\text{s.t.} \quad
& &&x_{2}&+&2x_{3}&\leq&3\\
-&x_{1}&&&+&3x_{3}&\leq&2\\
&2x_{1}&+&x_{2}&+&x_{3}&\leq&1\\
& x_{1}&,&x_{2} &,& x_{3}&\geq& 0
\end{alignat}
$$

$$
\begin{align}
\begin{array}{c|ccc|c}
& x_{1} & x_{2} & x_{3} & -1\\
\hline
-r_{1} & 0 & 1 & 2 & 3\\
-r_{2} & -1 & 0 & 3 & 2\\
-r_{3} & 2 & 1* & 1 & 1\\
\hline
-z& -1 & -1 & -2 & 0\\
\end{array}
&\Rightarrow
\begin{array}{c|ccc|c}
& x_{1} & r_{3} & x_{3} & -1\\
\hline
-r_{1} & -2 & -1 & 1 & 2\\
-r_{2} & -1 & 0 & 3* & 2\\
-x_{2} & 2 & 1 & 1 & 1 \\
\hline
-z & 1 & 1 & -1 & 1
\end{array}\\
&\Rightarrow
\begin{array}{c|ccc|c}
& x_{1} & r_{3} & r_{2} & -1\\
\hline
-r_{1} &-\frac{5}{3} & -1 & -\frac{1}{3} & \frac{4}{3}\\
-x_{3} &-\frac{1}{3} & 0 & \frac{1}{3} & \frac{2}{3}\\
-x_{2} &\frac{7}{3} & 1 & -\frac{1}{3} & \frac{1}{3}\\
\hline
-z & \frac{2}{3} & 1 & \frac{1}{3} & \frac{5}{3}
\end{array}
\end{align}
$$
最適解は$(r_{1}^{\ast}, x_{3}^{\ast}, x_{2}^{\ast}|x_{1}^{\ast}, r_{3}^{\ast}, r_{2}^{\ast}) = (\frac{4}{3}, \frac{2}{3}, \frac{1}{3}|0, 0, 0)$，すなわち$x_{1}^{\ast}=0,x_{2}^{\ast}=\frac{1}{3},x_{3}^{\ast}=\frac{2}{3}$で最適値は$z^{\ast}=\frac{5}{3}$.
The optimal solution is $(r_{1}^{\ast}, x_{3}^{\ast}, x_{2}^{\ast}|x_{1}^{\ast}, r_{3}^{\ast}, r_{2}^{\ast}) = (\frac{4}{3}, \frac{2}{3}, \frac{1}{3}|0, 0, 0)$， or equivalently, $x_{1}^{\ast}=0,x_{2}^{\ast}=\frac{1}{3},x_{3}^{\ast}=\frac{2}{3}$ and the optimal value is $z^{\ast}=\frac{5}{3}$.

### 別の解軌跡 | Another Solution Path
$$
\begin{align}
\begin{array}{c|ccc|c}
& x_{1} & x_{2} & x_{3} & -1\\
\hline
-r_{1} & 0 & 1 & 2 & 3\\
-r_{2} & -1 & 0 & 3* & 2\\
-r_{3} & 2 & 1 & 1 & 1\\
\hline
-z& -1 & -1 & -2 & 0\\
\end{array}
&\Rightarrow
\begin{array}{c|ccc|c}
& x_{1} & x_{2} & r_{2} & -1\\
\hline
-r_{1} & \frac{2}{3} & 1 & -\frac{2}{3} & \frac{5}{3}\\
-x_{3} & -\frac{1}{3} & 0 & \frac{1}{3} & \frac{2}{3}\\
-r_{3} & \frac{7}{3}* & 1 & -\frac{1}{3} & \frac{1}{3}\\
\hline
-z& -\frac{5}{3} & -1 & \frac{2}{3} & \frac{4}{3}\\
\end{array}\\
&\Rightarrow
\begin{array}{c|ccc|c}
& r_{3} & x_{2} & r_{2} & -1\\
\hline
-r_{1} & -\frac{2}{7} & \frac{5}{7} & -\frac{4}{7} & \frac{11}{7}\\
-x_{3} & \frac{1}{7} & \frac{1}{7} & \frac{2}{7} & \frac{5}{7}\\
-x_{1} & \frac{3}{7} & \frac{3}{7}* & -\frac{1}{7} & \frac{1}{7} \\
\hline
-z & \frac{5}{7} & -\frac{2}{7} & \frac{3}{7} & \frac{11}{7}
\end{array}\\
&\Rightarrow
\begin{array}{c|ccc|c}
& r_{3} & x_{1} & r_{2} & -1\\
\hline
-r_{1} &-1 & -\frac{5}{3} & -\frac{1}{3} & \frac{4}{3}\\
-x_{3} & 0 &-\frac{1}{3} & \frac{1}{3} & \frac{2}{3}\\
-x_{2} &1 &\frac{7}{3} & -\frac{1}{3} & \frac{1}{3}\\
\hline
-z & 1 &\frac{2}{3} & \frac{1}{3} & \frac{5}{3}
\end{array}
\end{align}
$$

## 課題2 | Exercise 2
講義で紹介した**巡回**が起きる問題：
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}$.