---
lang: ja
tags: OptMech-2021, lecture
---
# 2021年度 知的システム<br>第5回 練習問題 解答例
[ポータルへ戻る](https://hackmd.io/@nagae/OptMech_2021)
<div style="text-align: center">

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

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

## 課題1
以下の問題を**単体法**で解け．
$$
\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}, x_{3}, x_{2}|x_{1}, r_{3}, r_{2}) = (\frac{4}{3}, \frac{2}{3}, \frac{1}{3}|0, 0, 0)$，すなわち$x_{1}=0,x_{2}=\frac{1}{3},x_{3}=\frac{2}{3}$で最適値は$z=\frac{5}{3}$.

### 別解法(その1)
$$
\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
講義で紹介した**巡回**が起きる問題：
$$
\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}
$$に対し, **最小添字規則**を適用して**単体法**が終了する(**巡回**から抜け出せる)ことを確認せよ.

$$
\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{最小添字規則を適用}
&\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}=\frac{1}{2}, x_{3}=1, x_{2}=x_{4} =0$で最適値は$z=\frac{5}{2}$.