---
lang: ja
tags: OptMech-2021, lecture
---
# 2022年度 交通社会システム<br>Report #3 解答例
[ポータルへ戻る | Back to Portal](https://hackmd.io/@nagae/MTNS_2022)
<div style="text-align: center">

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

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

## 課題 | Exercise
次の問題を**二段階単体法**で解け：
Solve the following problem by using the two-phase simplex method.
$$
\begin{alignat}{4}
\max_{x_{1}, x_{2}, x_{3}} \quad & & 3x_{1} &+&4 x_{2} &+& 5 x_{3} &=&z\\
\text{s.t.} \quad
&& x_{1} &+&2x_{2}&+&2x_{3}&\leq&1\\
&-&3x_{1} &&&+&x_{3}&\leq&-1\\
&-&2x_{1} &-&x_{2}&&&\leq&-1\\
&&x_{1}&,&x_{2}&,&x_{3}&\geq&0
\end{alignat}
$$

等式標準形と初期辞書:
The standard equality form and the corresponding dictionary.
$$
\begin{alignat}{5}
\min_{x_{1}, x_{2}, x_{3}, r_{1}, r_{2}, r_{3}} \quad &-&3x_{1} &-&4 x_{2} &-& 5 x_{3} &-&0&=&-z\\
\text{s.t.} \quad
&& x_{1} &+&2x_{2}&+&2x_{3}&-&1&=&-r_{1}\\
&-&3x_{1} &&&+&x_{3}&-&(-1)&=&-r_{2}\\
&-&2x_{1} &-&x_{2}&&&-&(-1)&=&-r_{3}\\
&&x_{1}&,&x_{2}&,&x_{3},&&r_{1}, r_{2}, r_{3}&\geq&0
\end{alignat}
\qquad
\begin{array}{c|ccc|c}
& x_{1}& x_{2}& x_{3}& -1 \\
\hline
-r_{1} & 1& 2& 2& 1\\
-r_{2} & -3& 0& 1& -1\\
-r_{3} & -2& -1& 0& -1\\
\hline
-z & -3& -4& -5& 0\\
\end{array}
$$

補助問題の初期辞書：
The initial dictionary for the auxiliary problem:
\begin{array}{c|cccc|c}
& x_{1}& x_{2}& x_{3}& x_{a}& -1 \\
\hline
-r_{1} & 1& 2& 2& -1& 1\\
-r_{2} & -3& 0& 1& -1*& -1\\
-r_{3} & -2& -1& 0& -1& -1\\
\hline
-z & -3& -4& -5& 0& 0\\
z_{a} & 0& 0& 0& 1& 0\\
\end{array}

$x_{a}$の列(第4列)と，右辺定数が最小となる行($r_{2}$の行:第2行)がピボット．
The $x_{a}$ column (4th column) and $r_{2}$ row (2nd row) with the smallest RHS constant should be pivotted.

## 第1段階 | Phase-I
### 初期解 | Initial Solution
$x_{a}$と$r_{2}$を入れ替えることで，右辺定数がいずれも非負となる． これを第1段階の初期辞書とする．
By pivoting $x_{a}$ and $r_{2}$, we can obtain a dictionary with non-negative RHS constants, which can be used as an initial dictionary.
$$
\begin{array}{c|cccc|c}
& x_{1}& x_{2}& x_{3}& r_{2}& -1 \\
\hline
-r_{1} & 4& 2& 1& -1& 2\\
-x_{a} & 3& 0& -1& -1& 1\\
-r_{3} & 1*& -1& -1& -1& 0\\
\hline
-z & -3& -4& -5& 0& 0\\
z_{a} & -3& 0& 1& 1& -1\\
\end{array}
$$
$z_{a}$の係数が負となる$x_{1}$の列と，$x_{1}$を増やした時に最初に0となる$r_{3}$がピボット．
Choose $x_{1}$ column with negative coefficient of $z_{a}$ and $r_{3}$ row that becomes $0$ at first.
### 第1回 | 1st Iteration
$x_{1}$と$r_{3}$を入れ替える．
Pivot $x_{1}$ and $r_{3}$.
\begin{array}{c|cccc|c}
& r_{3}& x_{2}& x_{3}& r_{2}& -1 \\
\hline
-r_{1} & -4& 6*& 5& 3& 2\\
-x_{a} & -3& 3& 2& 2& 1\\
-x_{1} & 1& -1& -1& -1& 0\\
\hline
-z & 3& -7& -8& -3& 0\\
z_{a} & 3& -3& -2& -2& -1\\
\end{array}
$z_{a}$の係数が負となる$x_{2}$の列と，$x_{2}$を増やした時に最初に0となる$r_{1}$の行がピボット．
Choose $x_{2}$ column with negative coefficient of $z_{a}$ and $r_{1}$ row that becomes $0$ at first.
### 第2回 | 2nd Iteration
$x_{2}$と$r_{1}$を入れ替える．
Pivot $x_{2}$ and $r_{1}$.
\begin{array}{c|cccc|c}
& r_{3}& r_{1}& x_{3}& r_{2}& -1 \\
\hline
-x_{2} & -2/3& 1/6& 5/6& 1/2& 1/3\\
-x_{a} & -1& -1/2& -1/2& 1/2*& 0\\
-x_{1} & 1/3& 1/6& -1/6& -1/2& 1/3\\
\hline
-z & -5/3& 7/6& -13/6& 1/2& 7/3\\
z_{a} & 1& 1/2& 1/2& -1/2& 0\\
\end{array}
$z_{a}$の係数が負となる$r_{2}$の列と, $r_{2}$を増やした時に最初に0となる$x_{a}$の行がピボット．
Choose $r_{2}$ column with negative coefficient of $z_{a}$ and $x_{a}$ row that becomes $0$ at first.
### 第3回 | 3rd Iteration
$r_{2}$と$x_{a}$を入れ替える．
Pivot $r_{2}$ and $x_{a}$.
$$
\begin{array}{c|cccc|c}
& r_{3}& r_{1}& x_{3}& x_{a}& -1 \\
\hline
-x_{2} & 1/3& 2/3& 4/3& -1& 1/3\\
-r_{2} & -2& -1& -1& 2& 0\\
-x_{1} & -2/3& -1/3& -2/3& 1& 1/3\\
\hline
-z & -2/3& 5/3& -5/3& -1& 7/3\\
z_{a} & 0& 0& 0& 1& 0\\
\end{array}
$$
$z_{a}$の係数はいずれも非負であるため， 対応する基底解$(x_{2}, r_{2}, x_{1})=(1/3, 0, 1/3)$が第1段階の最適解であり，その最適値が0であることから，もとの問題は許容である．
This is optimal for the auxiliary problem as no negative $z_{a}$ coefficients. The original problem is feasible as the optimal value of auxiliary problem is $0$ and the corresponding basic solution $(x_{2}, r_{2}, x_{1})=(1/3, 0, 1/3)$ is a feasible solution to the original problem.

## 第2段階
### 初期解
第1段階の最適辞書から$x_{a}$の列と$z_{a}$の行を取り除いたものが第2段階の初期辞書となる．
$$
\begin{array}{c|ccc|c}
& r_{3}& r_{1}& x_{3}& -1 \\
\hline
-x_{2} & 1/3& 2/3& 4/3*& 1/3\\
-r_{2} & -2& -1& -1& 0\\
-x_{1} & -2/3& -1/3& -2/3& 1/3\\
\hline
-z & -2/3& 5/3& -5/3& 7/3\\
\end{array}
$$
$-z$の係数が負である$x_{3}$の列と， $x_{3}$を増やした時に最初に0となる$x_{2}$の行がピボット．

### 第1回
$x_{3}$と$x_{2}$を入れ替える:
\begin{array}{c|ccc|c}
& r_{3}& r_{1}& x_{2}& -1 \\
\hline
-x_{3} & 1/4*& 1/2& 3/4& 1/4\\
-r_{2} & -7/4& -1/2& 3/4& 1/4\\
-x_{1} & -1/2& 0& 1/2& 1/2\\
\hline
-z & -1/4& 5/2& 5/4& 11/4\\
\end{array}
$-z$の係数が負である$r_{3}$の列と， $r_{3}$を増やした時に最初に0となる$x_{3}$の行がピボット．

### 第2回
\begin{array}{c|ccc|c}
& x_{3}& r_{1}& x_{2}& -1 \\
\hline
-r_{3} & 4& 2& 3& 1\\
-r_{2} & 7& 3& 6& 2\\
-x_{1} & 2& 1& 2& 1\\
\hline
-z & 1& 3& 2& 3
\end{array}
$-z$ の係数はいずれも非負であるため，対応する基底解$(r_{3}, r_{2}, x_{1})=(1, 2, 1)$，すなわち$(x_{1}^{\ast}, x_{2}^{\ast}, x_{3}^{\ast})=(1, 0, 0)$が最適解であり，そのときの最適値は3.