---
lang: ja
tags: MTNS-2022, lecture, linear programming
---
# 2022年度 交通社会システム論<br>第7回：線形計画問題(6) 二段階単体法<br>Two-Phase Simplex Method
[ポータルへ戻る | 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</code>
</div>

# 二段階単体法 | Two-Phase Simplex Method
**標準最大化問題**の**等式標準形**およびその**辞書**:
In order to apply the simplex method for a given standard equality form and its equivalent dictionary,
$$
\begin{array}{crcrrcc}
\displaystyle\min_{\boldsymbol{x}, \boldsymbol{r}} \quad
&-c_{1} x_{1} &-\cdots &-c_{N} x_{N} &-0&=& -z\\
\text{s.t.}
&a_{11} x_{1} &+\cdots&+a_{1N} x_{N}&-b_{1}&=&-r_{1}\\
&\vdots & &\vdots& &&\vdots \\
&a_{M1} x_{1} &+\cdots&+a_{MN} x_{N}&-b_{M}&=&-r_{M}\\
&x_{1},&\cdots&x_{N}& &\geq&0\\
&r_{1},&\cdots&r_{M}&&\geq&0
\end{array}
\qquad
\begin{array}{c|ccc|c}
& x_{1} & \cdots & x_{N} & -1\\
\hline
-r_{1} & a_{11} & \cdots & a_{1N} & b_{1} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
-r_{M} & a_{M1} & \cdots & a_{MN} & b_{M} \\
\hline
-z & -c_{1} & \cdots & -c_{N} & 0
\end{array}
$$
に対して**単体法**を適用するためには，**許容基底解**を初期解として与える必要がある．
a feasible basic solution must be given as an initial solution.

- 任意の $j=1,\cdots,M$ について $b_{j} \geq 0$ の場合： <br>In case with $b_{j} \geq 0 \quad \forall j = 1, \cdots, M$:
自明な**許容基底解** $(\boldsymbol{r}|\boldsymbol{x}) = (\boldsymbol{b}|\boldsymbol{0})$ が存在する．
There is a trivial feasible solution $(\boldsymbol{r} | \boldsymbol{x})=(\boldsymbol{b}|\boldsymbol{0})$.
- $b_{j} < 0$ なる行が存在する場合：
In case with there exists $b_{j} < 0$ for some $j = 1, \cdots, M$.
自明な**許容解**が存在しない → **2段階単体法**を適用：**補助問題**を**単体法**で解くことで**許容基底解**を探索(第1段階)．**許容解**が見つかれば，それを初期解として再度**単体法**を用いてもとの問題の**最適解**を求める(第2段階)．
There is no trivial feasible solutions and the two-phase simplex method is applied: A feasible basic solution might be found by solving an auxiliary problem (Phase-I). If it is found, we can use it as an initial solution and apply the simplex method to solve the optimal problem (Phase-II).

# 二段階単体法で用いる補助問題 | An Auxiliary Problem for Finding Feasible Solution
もとの問題：
For a given original problem:
$$
\begin{align}
\min_{\boldsymbol{x}, \boldsymbol{r}} \quad & -\boldsymbol{c}^{\top} \boldsymbol{x} = -z\\
\text{s.t.} \quad& \boldsymbol{A} \boldsymbol{x} + \boldsymbol{r} = \boldsymbol{b} \\
& \boldsymbol{x}, \boldsymbol{r} \geq \boldsymbol{0}
\end{align}
$$
に対して，以下の**補助問題**(auxiliary problem)を考える:
suppose the following auxiliary problem:
$$
\begin{align}
\min_{\boldsymbol{x}, \boldsymbol{r}, \color{red}{x_{a}}} \quad & \color{red}{x_{a}} = z_{a}\\
\text{s.t.} \quad& \boldsymbol{A} \boldsymbol{x} + \boldsymbol{r} \color{red}{-\boldsymbol{1} x_{a}}= \boldsymbol{b} \\
& \boldsymbol{x}, \boldsymbol{r}\color{red}{, x_{a}} \geq \boldsymbol{0}
\end{align}
$$
ここで，$\boldsymbol{1}$は全ての要素が1の$M$次元列ベクトル, $x_{a}$は**1次元(スカラ)の人工変数** (artifitial variable)．
where $\boldsymbol{1}$ is an $M$-dimensional column vector with all elements $1$ and $x_{a}$ is an artificial scalar variable.

**もとの問題**と**補助問題**との間には，以下の関係がある：
The relationship between the original and the auxiliary problems can be summarized as:
- **補助問題**は常に**実行可能**. $x_{a}$ を大きくすることで, 任意の$\boldsymbol{A}, \boldsymbol{b}$に対して**補助問題**の**許容解**を求められる．
The auxiliary problem is always feasible and one of its feasible solutions for any $\boldsymbol{A}$ and $\boldsymbol{b}$ can be obtained by increasing $x_{a}$.
- もとの問題が**実行可能**であり，かつその時にのみ, **補助問題**の**最適値**が0となる．
The optimal value of the auxiliary problem becomes $0$ if and only if the original problem is feasible.

# 補助問題の初期許容基底解 | An Initial Feasible Basic Solution for the Auxiliary Problem
補助問題の**辞書**は以下のように表される:
The dictionary of the auxiliary problem is denoted by:
$$
\begin{array}{c|cccc|c}
& x_{1} & \cdots & x_{N} & x_{a} & -1 \\
\hline
-r_{1} & a_{11} & \cdots & a_{1N} & -1 & b_{1}\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
-r_{M} & a_{M1} & \cdots & a_{MN} & -1 & b_{M}\\
\hline
z_{a} & 0 & \cdots & 0 & 1 & 0
\end{array}
$$
いま，$b_{i}$が最小となる行を $h = \displaystyle\arg\min_{i=1, \cdots, M}\left\{b_{i}\right\}$ とし，**人工変数**$x_{a}$に対応する列を$k=N+1$とすると，$(h, k)$を**ピボット**とすることで，**補助問題**の**初期許容解**が得られる．
Let $h = \displaystyle\arg\min_{i=1, \cdots, M}\left\{b_{i}\right\}$ be the row with minimum $b_{i}$ and $k=N+1$ be the column corresponding to the artificial variable $x_{a}$. Then the initial feasible solution of the auxiliary problem can be obtained by pivoting the dictionary around $(h, k)$.

**ピボット演算**の規則：
According to the pivot operation rule:
$$
\boxed{
\begin{array}{cc}
p & r\\
c & q
\end{array}
} \Rightarrow
\boxed{
\begin{array}{cc}
1/p & r/p\\
-c/p & q-(rc/p)
\end{array}
}
$$
より，ピボット行$h$, ピボット列$k$および最終列(右辺定数)の要素は，以下のように変化する：
the pivot row $h$, the pivot column $k$ and the right-most column constants become:
$$
\begin{array}{c|cc}
& x_{a} & -1\\
\hline
r_{h} & -1* & b_{h} \\
r_i & -1 & b_{i}
\end{array}
\Rightarrow
\begin{array}{c|cc}
& \color{red}{r_{h}} & -1\\
\hline
\color{red}{x_{a}} & -1 & -b_{h} \\
i & -1 & b_{i} - b_{h}
\end{array}
$$

ここで，$b_{i}$の中で最小のものが$b_{h}$であるため，$b_{h}<0$かつ$b_{i}-b_{h} \geq 0$となる．この**ピボット演算**後の**基底解**は，
Here $b_{h}$ the minimum amongst $b_{i}$ and it is satisfied that $b_{h} <0$ and $b_{i} - b_{h} \geq 0$. The basic solution after this pivot operation becomes
$$\begin{align}
r_{i} &= b_{i} - b_{h} \quad (i\ne h),&
x_{a} &= - b_{h}
\end{align}
$$
であり，いずれも非負であるため**実行可能**である． 従って，これを**初期許容基底解**とした**単体法**によって**補助問題**を解くことができる．
which is feasible as every element is non-negative. Use this as the initial feasible basic solution for the simplex method, we can solve the auxiliary problem.

# 二段階単体法の例 | An Example of Two-Phase Simplex Method
**例題**：
Example:
$$
\begin{alignat}{3}
\max_{x_{1}, x_{2}} && 3x_{1} &+&2x_{2}&=&z\\
\text{s.t.} && 2x_{1} &-& x_{2}&\leq& -1\\
&-&x_{1} &+&2x_{2} &\leq& 4\\
&-&x_{1} &-&x_{2} &\leq& -2\\
&&x_{1}&,&x_{2}&\geq&0
\end{alignat}
$$

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

### 第1段階 | Phase-I
**人工変数**$x_{a}$を導入して**補助問題**を作成:
Formulate the auxiliary problem by introducing an artificial scalar $x_{a}$:
$$
\begin{alignat}{5}
\min_{x_{1}, x_{2}, r_{1}, r_{2}, r_{3}, x_{a}} && &&&&x_{a}&-&0&=&z_{a}\\
\text{s.t.} && 2x_{1} &-& x_{2}&-&x_{a}&-&(-1)&=& -r_{1}\\
&-&x_{1} &+&2x_{2}&-&x_{a}&-&4 &=& -r_{2}\\
&-&x_{1} &-&x_{2}&-&x_{a}&-&(-2)&=& -r_{3}\\
&&x_{1}&,&x_{2}&,&x_{a}&,&r_{1},&r_{2},&r_{3}\geq0
\end{alignat}
\qquad
\begin{array}{c|ccc|c}
&x_{1}&x_{2}&x_{a}&-1\\
\hline
-r_{1}&2&-1&-1&-1\\
-r_{2}&-1&2&-1&4\\
-r_{3}&-1&-1&-1&-2\\
\hline
\color{orange}{-z} &\color{orange}{-3} &\color{orange}{-2}&\color{orange}{0}&\color{orange}{0}\\
z_{a} & 0 & 0 & 1& 0
\end{array}
$$
**辞書**を構成する際，あとで便利なので，**もとの問題**の目的関数の行(上の例でオレンジ色で表されている行)を加えておくとよい．
When building the dictionary, it is nice to add the row of the original objective function (the rows in orange in the example above) for later convenience.

右辺定数$b_{i}$が最小の行$h$と人工変数の列$k$を入れ替える**ピボット演算**を行なえば，**補助問題**の**初期許容基底解**が得られる．
By a pivot operation that switches the row with minimum $b_{i}$ and the column of the artificial variable $x_{a}$, the initial feasible solution for the auxiliary problem:
$$
\begin{array}{c|ccc|c}
& x_{1} & x_{2} & x_{a} & -1\\
\hline
-r_{1} & 2 & -1 & -1 & -1\\
-r_{2} & -1 & 2 & -1 & 4\\
-r_{3} & -1 & -1 & -1* & -2\\
\hline
-z & -3 & -2 & 0 & 0 \\
z_{a} & 0 & 0 & 1 & 0
\end{array}
\Rightarrow
\begin{array}{c|ccc|c}
& x_{1} & x_{2} & r_{3} & -1\\
\hline
-r_{1} & 3 & 0 & -1 & 1\\
-r_{2} & 0 & 3 & -1 & 6\\
-x_{a} & 1 & 1 & -1* & 2\\
\hline
-z & -3 & -2 & 0 & 0 \\
z_{a} & -1 & -1 & -1 & -2
\end{array}
$$

$(r_{1}, r_{2}, x_{a}) = (1, 6, 2)$を**初期許容基底解**として**補助問題**に対して**単体法**を適用(第1段階):
Let $(r_{1}, r_{2}, x_{a}) = (1, 6, 2)$ be the initial feasible basic solution and apply the simplex method to the auxiliary problem (Phase-I):
$$
\begin{array}{c|ccc|c}
& x_{1} & x_{2} & r_{3} & -1\\
\hline
-r_{1} & 3* & 0 & -1 & 1\\
-r_{2} & 0 & 3 & -1 & 6\\
-x_{a} & 1 & 1 & -1 & 2\\
\hline
-z & -3 & -2 & 0 & 0 \\
z_{a} & -1 & -1 & -1 & -2
\end{array}
\Rightarrow
\begin{array}{c|ccc|c}
& r_{1} & x_{2} & r_{3} & -1\\
\hline
-x_{1} & \tfrac{1}{3} & 0 & -\tfrac{1}{3} & \tfrac{1}{3}\\
-r_{2} & 0 & 3 & -1 & 6\\
-x_{a} & -\tfrac{1}{3} & 1* & -\tfrac{2}{3} & \tfrac{5}{3}\\
\hline
-z & 1 & -2 & -1 & 1 \\
z_{a} & \tfrac{1}{3} & -1 & \tfrac{2}{3} & -\tfrac{5}{3}
\end{array}
\Rightarrow
\begin{array}{c|ccc|c}
& r_{1} & x_{a} & r_{3} & -1\\
\hline
-x_{1} & \tfrac{1}{3} & 0 & -\tfrac{1}{3} & \tfrac{1}{3}\\
-r_{2} & 1 & -3 & 1 &1\\
-x_{2} & -\tfrac{1}{3} & 1 & -\tfrac{2}{3} & \tfrac{5}{3}\\
\hline
-z & \tfrac{1}{3} & 2 & -\tfrac{7}{3} & \tfrac{13}{3} \\
z_{a} & 0 & 1 & 0 & 0
\end{array}
$$

**補助問題**の**基底変数**の入れ替えにともなって，**もとの問題**の係数や定数も変化することに注意．
Note that the coefficients and the RHS constants of the original problem change as the basic variables of the auxiliary problem are pivoted.

**補助問題**の**最適値**(i.e. **最適解**における**人工変数**$x_{a}$の値)が
Since the optimal value (i.e. the value of artificial variable $x_{a}$ at the optimal) is $$z_{a}^{\ast} = x_{a}^{\ast} = 0
$$なので，**もとの問題**は**実行可能**で，その**許容基底解**の1つが**補助問題**の**最適解**$(x_{1}, r_{2}, x_{2}) = \left(\tfrac{1}{3}, 1, \tfrac{5}{3}\right)$として求められた．
the original problem is feasible and one feasible basic solution can be obtained as the optimal solution of the auxiliary problem, $(x_{1}, r_{2}, x_{2}) = \left(\tfrac{1}{3}, 1, \tfrac{5}{3}\right)$.

### 第2段階 | Phase-II
次に，これを**初期解**として**もとの問題**に**単体法**を適用する．**補助問題**の最適解に対応する**辞書**から
In the Phase-II, let this be the initial solution and apply the simplex method to the original problem. By removing
- 目的関数$z_{a}$に対応する行 | the row of the auxiliary objective $z_{a}$
- 人工変数$x_{a}$に対応する列 | the column of the artificial variable $x_{a}$

を取り除けば，$(x_{1}, r_{2}, x_{2})$を**基底変数**とする**辞書**が得られる:
from the optimal dictionary of the auxiliary problem, we have the dictionary with basic variable $(x_{1}, r_{2}, x_{2})$:
$$
\begin{array}{c|cc|c}
& r_{1} & r_{3} & -1\\
\hline
-x_{1} & \tfrac{1}{3} & -\tfrac{1}{3} & \tfrac{1}{3}\\
-r_{2} & 1 & 1 &1\\
-x_{2} & -\tfrac{1}{3} & -\tfrac{2}{3} & \tfrac{5}{3}\\
\hline
-z & \tfrac{1}{3} & -\tfrac{7}{3} & \tfrac{13}{3} \\
\end{array}
$$

これを初期解として**単体法**を適用すれば，
Let this be the initial solution and apply the simplex method
$$
\begin{array}{c|cc|c}
& r_{1} & r_{3} & -1\\
\hline
-x_{1} & \tfrac{1}{3} & -\tfrac{1}{3} & \tfrac{1}{3}\\
-r_{2} & 1 & 1* &1\\
-x_{2} & -\tfrac{1}{3} & -\tfrac{2}{3} & \tfrac{5}{3}\\
\hline
-z & \tfrac{1}{3} & -\tfrac{7}{3} & \tfrac{13}{3} \\
\end{array}
\Rightarrow
\begin{array}{c|cc|c}
& r_{1} & r_{2} & -1\\
\hline
-x_{1} & \tfrac{2}{3} & \tfrac{1}{3} & \tfrac{2}{3}\\
-r_{3} & 1 & 1 &1\\
-x_{2} & \tfrac{1}{3} & \tfrac{2}{3} & \tfrac{7}{3}\\
\hline
-z & \tfrac{7}{3} & \tfrac{7}{3} & \tfrac{20}{3} \\
\end{array}
$$
より，**もとの問題**の**最適解**は$(x_{1}^{\ast}, r_{3}^{\ast}, x_{2}^{\ast} | r_{1}^{\ast}, r_{2}^{\ast}) = \left(\left.\tfrac{2}{3}, 1, \tfrac{7}{3} \right| 0, 0\right)$で，**最適値**は$z^{\ast} = \tfrac{20}{3}$ と求められる．
we can obtain the **optimal solution** and the **optimal value** of the original problem as $(x_{1}^{\ast}, r_{3}^{\ast}, x_{2}^{\ast} | r_{1}^{\ast}, r_{2}^{\ast}) = \left(\left.\tfrac{2}{3}, 1, \tfrac{7}{3} \right| 0, 0\right)$ and $z^{\ast} = \frac{20}{3}$, respectively.

# 二段階単体法の手続き | Procedure of the Two-Phase Simplex Method
1. **等式標準形**および**初期辞書**を構築．
Derive the standard equality form and its dictionary.
2. $\boldsymbol{b} \geq \boldsymbol{0}$ なら，$(\boldsymbol{r}|\boldsymbol{x}) = (\boldsymbol{b}|\boldsymbol{0})$ が **もとの問題** の**初期許容基底解**．
If $\boldsymbol{b} > \boldsymbol{0}$ then $(\boldsymbol{r}|\boldsymbol{x}) = (\boldsymbol{b}|\boldsymbol{0})$ is the initial feasible basic solution to the original problem.
3. $\boldsymbol{b} \not\geq \boldsymbol{0}$ なら， **補助問題**に対して**単体法**を実行(==第1段階==):
If $\boldsymbol{b} \not \geq \boldsymbol{0}$, apply the simplex method to the auxiliary problem (Phase-I):
3.1 $b_{i}$が最小となる行$h$と人工変数$x_{a}$の列を入れ替える**ピボット演算**により, **補助問題**に対する**許容基底解**が得られる．これを初期解として**単体法**を適用すれば，**補助問題**の**最適解**が求められる．
Pivot the row with the smallest $b_{i}$ and the column of the artificial variable $x_{a}$ and obtain the feasible basic solution. Let this be the initial solution and apply the simplex method, we can obtain the optimal solution to the auxiliary problem.
3.2 **補助問題**の**最適値**が正ならば，$\boldsymbol{A x}+\boldsymbol{r}=\boldsymbol{b}$かつ$\boldsymbol{x}, \boldsymbol{r} \geq \boldsymbol{0}$を満たす解$(\boldsymbol{x}, \boldsymbol{r})$は存在しない(i.e. **もとの問題**は**不能**)．
If the optimal value of the auxiliary problem is positive, there is no solution $(\boldsymbol{x}, \boldsymbol{r})$ that satisfies $\boldsymbol{A x}+\boldsymbol{r}=\boldsymbol{b}$ and $\boldsymbol{x}, \boldsymbol{r} \geq \boldsymbol{0}$. That is the original problem is **infeasible**. STOP.
3.3 **補助問題**の**最適値**が0ならば，$x_{a}^{\ast} = 0$. このとき，**補助問題**の**最適解**$(\boldsymbol{x}_{B} | \boldsymbol{x}_{N}) = (\hat{\boldsymbol{b}}|\boldsymbol{0})$は**もとの問題**の**許容基底解**
If the optimal value of the auxiliary problem is $0$, then the optimal solution $(\boldsymbol{x}_{B} | \boldsymbol{x}_{N}) = (\hat{\boldsymbol{b}}|\boldsymbol{0})$, where $x_{a}^{\ast} = 0$, is the feasible basic solution to the original problem.
4. **もとの問題**の許容基底解が求められたなら，それを初期解として**単体法**を実行(==第2段階==)．
Let the feasible solution to the original problem as the initial solution and apply the simplex method (Phase-II).

# 基本定理の(構成的)証明 | A Constructive Proof of the Fundamental Theorem
**二段階単体法**の手続きの特徴：
The relevant features of the two-phase simplex method are:
1. ==**第1段階**== (**補助問題**を解く)では，以下のいずれか一方が実現：
In Phase-I (solve the auxiliary problem), either one of the following is realized:
- **もとの問題**が**不能**であると判定される;
It is found that the original problem is **infeasible**;
- **もとの問題**の**許容基底解**の1つが見つかる.
It is found the one feasible basic solution to the original problem.
2. ==**第2段階**== (**もとの問題**を解く)では，以下のいずれか一方が実現:
In Phase-II (solve the original problem), either one of the following is realized:
- **もとの問題**が**無界**である(制約条件を満たしながら目的関数値をどこまでも小さくできる)と判定される;
It is found that the original problem is **unbounded**;
- **もとの問題**の**最適解**が見つかる．
**The optimal solution** to the original problem is obtained.

従って，**二段階単体法**によって，どんな**線形計画問題**も
This implies that by the two-phase simplex method, any linear programming problem can be classified as one of the following:
- **不能**(**許容解**を持たない);
**Infeasible** (no feasible solution exist);
- **無界**(**許容解**はあるが目的関数がどこまでも大きくできるため**最適解**を持たない);
**Unbounded** (the objective can be infinite without violating feasibility and thus no optimal solutions exist)
- **最適解**をもつ.
**The optimal solutions** exist.

に分類される．

これは，線形計画問題の**基本定理**の構成的証明を与える：
This gives a constructive proof of the fundamental theorem of the linear programming problem.

## 基本定理 | Fundamental Theorem
:::success
**実行可能** で **有界** な線形計画問題は **最適解** を持つ.
If a linear programming problem is **feasible** and **bounded**, it has an **optimal solution**.
:::

# 練習問題 | 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}
$$