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

# 辞書の更新とリア充問題の最適解 | Update of Dictionaries to Find The Optimal Solution
リア充問題の**等式標準形**：
For the standard equality form of Mr. Adams' happiness problem,
$$
\begin{alignat}{6}
\displaystyle \min_{x_{1}, x_{2}, r_{1}, r_{2}, r_{3}} \quad -z&=-&x_{1} &-& 2x_{2} &-&0\\
\text{s.t.} \quad
-r_{1}&=&x_{1} &+& x_{2} &-& 8 \\
-r_{2}&=&2x_{1}&+& x_{2} &-& 2 \\
-r_{3}&=&2x_{1}&+&3x_{2} &-& 18 \\
&& x_{1}&,&x_{2} &,& r_{1}&, &r_{2}&,&r_{3}&\geq& 0
\end{alignat}
\qquad
\begin{array}{c|cc|c}
& x_{1} & x_{2} & -1\\
\hline
-r_{1} & 1 & 1 & 8\\
-r_{2} & -2 & 1 & 2 \\
-r_{3} & 2 & 3 & 18\\
\hline
-z & -1 & -2 & 0
\end{array}
$$
に対して，以下の2回の**ピボット演算**を行う:
perform the following two pivot operations in order:
1. **説明変数**$x_{2}$と**被説明変数**$r_{2}$を入れ替える (pivot explanatory column $x_{2}$ and explained row $r_{2}$)
2. **説明変数**$x_{1}$と**被説明変数**$r_{3}$を入れ替える (pivot explanatory column $x_{1}$ and explained row $r_{3}$)

このとき，**辞書**は下記：
Corresponding to these operations, the dictionary changes as follows:
$$
\begin{array}{c|cc|c}
& x_{1} & x_{2} & -1\\
\hline
-r_{1} & 1 & 1 & 8\\
-r_{2} & -2 & 1* & 2 \\
-r_{3} & 2 & 3 & 18\\
\hline
-z & -1 & -2 & 0
\end{array}
\rightarrow
\begin{array}{c|cc|c}
& x_{1} & r_{2} & -1\\
\hline
-r_{1} & 3 & -1 & 6\\
-x_{2} & -2 & 1 & 2 \\
-r_{3} & 8* & -3 & 12\\
\hline
-z & -5 & 2 & 4
\end{array}
\rightarrow
\begin{array}{c|cc|c}
& r_{3} & r_{2} & -1\\
\hline
-r_{1} & \frac{3}{8} & \frac{1}{8} & \frac{3}{2}\\
-x_{2} & \frac{1}{4} & \frac{1}{4} & 5 \\
-x_{1} & \frac{1}{8} & -\frac{3}{8} & \frac{3}{2}\\
\hline
-z & \frac{5}{8} & \frac{1}{8} & \frac{23}{2}
\end{array}
$$
のように変化する．最後の辞書は，**説明変数**を$\boldsymbol{u}=(r_{3}, r_{2})$，**被説明変数**を$\boldsymbol{v}=(r_{1}, x_{2}, x_{1})$としている．これに対応した**等式標準形**の線形計画問題は以下のように表される：
The last dictionary consists of the explanatory columns $\boldsymbol{u}=(r_{3}, r_{2})$ and the explained rows $\boldsymbol{v} = (r_{1}, x_{2}, x_{1})$. The corresponding standard equality form is formulated as:
$$
\begin{alignat}{6}
\displaystyle \min_{r_{3}, r_{2}, r_{1}, x_{2}, x_{1}} \quad -z&=&\tfrac{5}{8}r_{3} &+& \tfrac{1}{8}r_{2} &-&\tfrac{23}{2}\\
\text{s.t.} \quad
-r_{1}&=&\tfrac{3}{8}r_{3} &+&\tfrac{1}{8}r_{2} &-& \tfrac{3}{2} \\
-x_{2}&=&\tfrac{1}{4}r_{3}&+& \tfrac{1}{4}r_{2} &-& 5 \\
-x_{1}&=&\tfrac{1}{8}r_{3}&-&\tfrac{3}{8}r_{2} &-& \tfrac{3}{2} \\
&& r_{3}&,&r_{2} &,&r_{1}&, x_{2}, x_{1}\geq 0
\end{alignat}
$$

この問題の目的関数の最初の2項 $\tfrac{5}{8}r_{3} + \tfrac{1}{8}r_{2}$ は， $(r_{3}, r_{2})$ の ==**係数がいずれも正**== なので，$(r_{3}, r_{2})$を小さくするほど小さくなる．いま，$r_{3} = r_{2}=0$としてみよう．このとき，等式制約から，ただちに残る変数が$(r_{1}, x_{2}, x_{1}) = \left(\tfrac{3}{2}, 5, \tfrac{3}{2}\right)$と求められる．等式制約の ==**右辺定数がいずれも非負**== であるから，$(r_{3}, r_{2} | r_{1}, x_{2}, x_{1})=\left(0, 0\left| \tfrac{3}{2}, 5, \tfrac{3}{2}\right.\right)$は**実行可能**である．

Note that the coefficients of the objective function with respect to the explanatory variables, $(\frac{5}{8}, \frac{1}{8})$, are positive and thus the objective becomes smaller as $(r_{3}, r_{2})$ is decreased. When we set $r_{3}=r_{2}=0$, the remaining variables can be obtained as $(r_{1}, x_{2}, x_{1}) = \left(\tfrac{3}{2}, 5, \tfrac{3}{2}\right)$, from the equality constraints directory. Because the RHS constants of the equality constraints are positive, the solution $(r_{3}, r_{2} | r_{1}, x_{2}, x_{1})=\left(0, 0\left| \tfrac{3}{2}, 5, \tfrac{3}{2}\right.\right)$ is feasible.

$r_{2}, r_{3}$が非負である限り目的関数(の符号を反転させたもの)が$-z=-\frac{23}{2}$よりも小さくなることはないから，この解は**最適解**である．結局のところ，もとの問題の**最適解**および**最適値**は，以下のように求められる:
As long as $(r_{2}, r_{3})$ is non-negative, the objective function (with the sign reversed) can not be smaller than $-z=-\frac{23}{2}$ and thus it is optimal. Accordingly, the optimal solution and the optimal value can be obtained as:
- **最適解 (optimal solution)**: $(r_{3}, r_{2} | r_{1}, x_{2}, x_{1})=\left(0, 0 \left| \tfrac{3}{2}, 5, \tfrac{3}{2}\right.\right)$,
- **最適値 (optimal value)**: $z = \tfrac{23}{2}$.

この結果を一般化してみよう．
This can be generalized in the next section.

# 最適解が自明となる辞書 | A Dictionary with A Trivial Optimal Solution
**標準最大化問題**に対して，ある**辞書**
Suppose a standard maximization problem with given the following dictionary
$$
\begin{array}{c|c|c}
& \boldsymbol{u}^{\top} & -1 \\
\hline
-\boldsymbol{v} & \hat{\boldsymbol{A}} & \hat{\boldsymbol{b}} \\
\hline
-z & - \hat{\boldsymbol{c}}^{\top} & \hat{\zeta}
\end{array}
$$
が与えられた時， ==**$\hat{\boldsymbol{b}} \geq \hat{\boldsymbol{0}}$ かつ$-\hat{\boldsymbol{c}} \geq \boldsymbol{0}$**== ならば，$(\boldsymbol{v}|\boldsymbol{u}) = (\hat{\boldsymbol{b}}|\boldsymbol{0})$ は，対応する **等式標準形**:
and $\hat{\boldsymbol{b}} \geq \hat{\boldsymbol{0}}$ and $-\hat{\boldsymbol{c}} \geq \boldsymbol{0}$.
Then the solution $(\boldsymbol{v}|\boldsymbol{u}) = (\hat{\boldsymbol{b}}|\boldsymbol{0})$ is optimal to the corresponding standard equality form:
$$\begin{alignat}{3}
\min_{\boldsymbol{u}, \boldsymbol{v}}
&& -\hat{\boldsymbol{c}}^{\top} \boldsymbol{u} - \hat{\zeta} &= - z\\
\text{s.t.}
&& \hat{\boldsymbol{A}} \boldsymbol{u} - \hat{\boldsymbol{b}} &= - \boldsymbol{v} \\
&& \boldsymbol{u}, \boldsymbol{v} &\geq \boldsymbol{0}
\end{alignat}$$
の**最適解**であり，その**最適値**は$-z = -\hat{\zeta}$ である．
and the optimal value is $-z = -\hat{\zeta}$.

従って，ある**標準最大化**問題:
This implies that a standard maximization problem:
$$
\max_{\boldsymbol{x}} \left\{
z = \boldsymbol{c}^{\top} \boldsymbol{x} \left|
\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0}
\right.
\right\}
$$
の**最適解**を求める問題は，その**等式標準形**:
and its standard equality form:
$$
\min_{\boldsymbol{x}, \boldsymbol{r}} \left\{
-z = \boldsymbol{c}^{\top} \boldsymbol{x} \left|
\boldsymbol{A} \boldsymbol{x} - \boldsymbol{b} = - \boldsymbol{r}, \quad \boldsymbol{x}, \boldsymbol{r} \geq \boldsymbol{0}
\right.
\right\}
$$
と**等価な辞書**:
reduces to find an equivalent dictionary:
$$
\begin{align}
-\boldsymbol{v} &= \hat{\boldsymbol{A}} \boldsymbol{u}-\hat{\boldsymbol{b}} \\
-z &= - \hat{\boldsymbol{c}}^{\top} \boldsymbol{u} - \hat{\zeta}
\end{align}
$$
の中で， ==**$\hat{\boldsymbol{b}} \geq \boldsymbol{0}$ かつ $-\hat{\boldsymbol{c}} \geq \boldsymbol{0}$**== なるものを求める問題に帰着する．
such that $\hat{\boldsymbol{b}} \geq \boldsymbol{0}$ and $-\hat{\boldsymbol{c}} \geq \boldsymbol{0}$.

ここまで判ったことを整理すると，**標準最大化問題**の**等式標準形**に対して
1. **辞書**の一つは $(\boldsymbol{v}|\boldsymbol{u}) = (\boldsymbol{r}|\boldsymbol{x}), (\hat{\boldsymbol{A}}, \hat{\boldsymbol{b}}, \hat{\boldsymbol{c}}, \hat{\zeta}) = (\boldsymbol{A}, \boldsymbol{b}, \boldsymbol{c}, 0)$ で与えられる．
2. **等価な辞書**$(\hat{\boldsymbol{A}}, \hat{\boldsymbol{b}}, \hat{\boldsymbol{c}},\hat{\zeta})$は**ピボット演算**によって生成できる．
3. そうした**辞書**の中で$\hat{\boldsymbol{b}} \geq \boldsymbol{0}$かつ$-\hat{\boldsymbol{c}} \geq \boldsymbol{0}$ なるものが(たまたま)見つかれば，もとの問題の**最適解**および**最適値**は, それぞれ, $(\boldsymbol{v}^{\ast}|\boldsymbol{u}^{\ast}) = (\hat{\boldsymbol{b}}|\boldsymbol{0})$および$z^{\ast} = \hat{\zeta}$ と求められる．
The above discussion can be summarized as follows: for any standard maximization problem and its equivalent equality form,
1. A dictionary is given by $(\boldsymbol{v}|\boldsymbol{u}) = (\boldsymbol{r}|\boldsymbol{x}), (\hat{\boldsymbol{A}}, \hat{\boldsymbol{b}}, \hat{\boldsymbol{c}}, \hat{\zeta}) = (\boldsymbol{A}, \boldsymbol{b}, \boldsymbol{c}, 0)$.
2. A pivot operation obtains another equivalent dictionary $(\hat{\boldsymbol{A}}, \hat{\boldsymbol{b}}, \hat{\boldsymbol{c}}, \hat{\zeta})$.
3. When we find a dictionary with $\hat{\boldsymbol{b}} \geq \boldsymbol{0}$ and $-\hat{\boldsymbol{c}} \geq \boldsymbol{0}$ (by fortune) , the optimal solution and the optimal value of the original problem are $(\boldsymbol{v}^{\ast}|\boldsymbol{u}^{\ast}) = (\hat{\boldsymbol{b}}|\boldsymbol{0})$ and $z^{\ast} = \hat{\zeta}$, respectively.

最適解が自明となる(i.e. $\hat{\boldsymbol{b}} \geq \boldsymbol{0}$かつ$-\hat{\boldsymbol{c}} \geq \boldsymbol{0}$)辞書に必ず辿りつく方法はないだろうか? その問いに答えるのが，次に述べる**単体法**である．
Is there any systematic way to find such nice dictionary with a trivial solution (i.e. $\hat{\boldsymbol{b}} \geq \boldsymbol{0}$ and $-\hat{\boldsymbol{c}} \geq \boldsymbol{0}$)? The answer is the simplex method.

# 単体法 | Simplex Method
==**単体法 (simplex method)**== は米国の George B. Dantzig が1947 年に提案. 60年以上経過した今日でも**非常に有効な**線形計画問題の数値解法として広く利用されている. **単体法**では以下の用語が使われる:
The simplex method is introduced by George B. Danzig at 1947. It has been widely used for 60+ years as the one of quite effective solution method for the linear programming problems. In the theory of simplex method, following terms are used:
- **被説明変数** (explained variables) $\boldsymbol{v}$ → ==**基底変数**==(basic variable) $\boldsymbol{x}_B$
- **説明変数** (explanatory variables) $\boldsymbol{u}$ → ==**非基底変数**==(nonbasic variable) $\boldsymbol{x}_N$
- **説明変数**を$\boldsymbol{0}$, **被説明変数**を$\hat{\boldsymbol{b}}$ とした解 (solution with explanatory variable $\boldsymbol{0}$ and explained variable $\hat{\boldsymbol{b}}$) → ==**基底解**==(basic solution)

**単体法**の特徴は以下のように整理される:
The relevant features of the simplex method can be summarized as follows:
- **許容基底解**の1つから始め,(等式標準形の)目的関数の値が**減少**し, かつ**実行可能性**が担保されるように, **ピボット演算**によって次々と**辞書**を更新する.
Starting from a feasible basic solution, it updates the dictionary by pivot operations so that the objective function (of the standard equality form) decreases while ensuring the feasibility.
- *目的関数の**係数が負***となる非基底変数の値を0から増やすため, 目的関数値は*必ず減少*.
It increases the value of a nonbasic variable with negative coefficient from 0, and thus the objective function (of the standard equality form) surely decreases.
- **非基底変数**の増加に伴い,少なくとも1つの**基底変数**の値が減少するが, いずれかの**基底変数**が0となったところで**非基底変数**と*入れ替える*ため, **実行可能性**が担保される.
When the problem is bounded, as the nonbasic variable increases, at least one basic variable decreases, which is replaced with the nonbasic variable when it becomes 0. This enables us to ensure the feasibility.

# リア充問題で単体法の基本的動作を確認 | An Example of Simplex Method
## 初期解 | Initial Solution
リア充問題の**等式標準形**と**辞書**:
Given the standard equality form and corresponding dictionary:
$$
\begin{alignat}{6}
\displaystyle \min_{x_{1}, x_{2}, r_{1}, r_{2}, r_{3}} \quad -z&=-&x_{1} &-& 2x_{2} &-&0\\
\text{s.t.} \quad
-r_{1}&=&x_{1} &+& x_{2} &-& 8 \\
-r_{2}&=&2x_{1}&+& x_{2} &-& 2 \\
-r_{3}&=&2x_{1}&+&3x_{2} &-& 18 \\
&& x_{1}&,&x_{2} &,& r_{1}&, &r_{2}&,&r_{3}&\geq& 0
\end{alignat}
\qquad
\begin{array}{c|cc|c}
& x_{1} & x_{2} & -1\\
\hline
-r_{1} & 1 & 1 & 8\\
-r_{2} & -2 & 1 & 2 \\
-r_{3} & 2 & 3 & 18\\
\hline
-z & -1 & -2 & 0
\end{array}
$$
- **基底変数** (被説明変数) | basic variables (explained rows): $\boldsymbol{x}_{B} = (r_{1}, r_{2}, r_{3})$
- **非基底変数** (説明変数) | non-basic variable (explanatory columns): $\boldsymbol{x}_{N} = (x_{1}, x_{2})$
- **基底解** | basic solution: $(r_{1}, r_{2}, r_{3}| x_{1}, x_{2}) = (8, 2, 18|0,0)$
- 基底解での**目的関数値** | objective function at the basic solution: $-z = 0$

## 1回目の解の改訂 | 1st Update
目的関数の **非基底変数** $x_{1}, x_{2}$についての係数は$(-1, -2)$で ==いずれも負==． 従って，$x_{1}, x_{2}$を0より大きくすることで， *現在の**基底解**より小さな目的関数値を実現できる*．
The coefficients of the objective with nonbasic column variables $x_{1}, x_{2}$, $(-1, -2)$ are negative, and thus a smaller objective can be achieved by increasing $x_{1}, x_{2}$ from $0$.

例えば，**非基底変数**のうち，$x_{1}=0$のままにして，$x_{2}$を$0$から増やすことを考えよう．**等式制約**から，$x_{2}$が変化することで，**基底変数**の値は，以下のように変化する：
Suppose that the nonbasic column variable $x_{2}$ is increased while $x_{1}=0$. From the equality constraints, the basic row variables change as:
$$
\begin{align}
\begin{split}
-r_{1} &= x_{2}-8\\
-r_{2} &= x_{2}-2\\
-r_{3} &= 3x_{2}-18
\end{split}
\Leftrightarrow
\begin{split}
r_{1} &= 8 - x_{2} &(x_{2}\leq 8)\\
r_{2} &= 2 - x_{2} &(x_{2}\leq 2) \\
r_{3} &= 18-3x_{2} \quad&(x_{2}\leq 6)
\end{split}
\end{align}
$$
ただし，括弧内は，対応する基底変数が非負であるために$x_{2}$が満たすべき条件を表している．
, where the each inequality in the parentheses is the condition that $x_{2}$ must satisfy for the corresponding basic variable to be non-negative.

これより，非負制約$\boldsymbol{x}, \boldsymbol{r} \geq \boldsymbol{0}$ を担保するためには，$x_{2}$は $2$ までしか増加させられない．$x_{2}=2$まで増加させた時, **基底変数**, **非基底変数**および**目的関数**は以下のように変化する：
From the inequalities, nonbasic column variable $x_{2}$ can not be larger than $2$. When $x_{2}=2$, the basic variable, the nonbasic variable and the objective functions become

| |変更前(before)|変更後(after)|
|--|--|--|
|基底変数 (basic row variables): $(r_{1}, \color{red}{r_{2}}, r_{3})$|$(8,2,8)$|$(6,\color{red}{0}, 12)$|
|非基底変数 (nonbasic column variables): $(x_{1}, \color{red}{x_{2}})$|$(0,0)$|$(0,\color{red}{2})$|
|目的関数 (objective function): $-z$|0|$-4$|

変化後の解は，**基底変数**$r_{2}$と**非基底変数**$x_{2}$を入れ替えて得られる以下の**等価**な問題の**基底解**に他ならない．
The solution after the change is the basic solution of the following equivalent problem obtained by pivoting the basic row $r_{2}$ and nonbasic column $x_{2}$:
$$
\begin{array}{c|cc|c}
& x_{1} & x_{2} & -1\\
\hline
-r_{1} & 1 & 1 & 8\\
-r_{2} & -2 & 1* & 2 \\
-r_{3} & 2 & 3 & 18\\
\hline
-z & -1 & -2 & 0
\end{array}
\rightarrow
\begin{array}{c|cc|c}
& x_{1} & r_{2} & -1\\
\hline
-r_{1} & 3 & -1 & 6\\
-x_{2} & -2 & 1 & 2 \\
-r_{3} & 8 & -3 & 12\\
\hline
-z & -5 & 2 & 4
\end{array}
$$
$$
\begin{alignat}{6}
\displaystyle \min_{x_{1}, r_{2}, r_{1}, x_{2}, r_{3}} \quad -z&=-&5x_{1} &+& 2r_{2} &-&4\\
\text{s.t.} \quad
-r_{1}&=&3x_{1} &-& r_{2} &-& 6 \\
-x_{2}&=-&2x_{1}&+& r_{2} &-& 2 \\
-r_{3}&=&8x_{1}&-&3r_{2} &-& 12 \\
&& x_{1}&,&r_{2} &,& r_{1}&, &x_{2}&,&r_{3}&\geq& 0
\end{alignat}
$$

- **基底/非基底変数 (basic/nonbasic variables)**: $\boldsymbol{x}_{B} = (r_{1}, \color{red}{x_{2}}, r_{3}), \boldsymbol{x}_{N} = (x_{1}, \color{red}{r_{2}})$
- **基底解 (basic solution)**: $(r_{1}, x_{2}, r_{3} | x_{1}, r_{2}) = (6, 2, 12|0,0)$
- 基底解での**目的関数値** (the objective at the basic solution): $-z = -4$

## 2回目の解の改訂 | 2nd Update
新しく得られた問題の目的関数の **非基底変数** $x_{1}, r_{2}$の係数は$(-5, 2)$. ==係数が負である$x_{1}$== を0より大きくすることで，*現在の**基底解**より小さな目的関数値を実現できる*．
The coefficients of the new standard equality form with respect to the nonbasic column variables $x_{1}, r_{2}$ are $(-5, 2)$. Since the coefficient of $x_{1}$ is negative, a smaller objective can be achieved by increasing $x_1$.

$r_{2}=0$のまま**非基底変数** $x_{1}$を0から増やすと，**等式制約**から，**基底変数**の値は，以下のように変化する：
Increasing $x_{1}$ from 0 while keeping $r_{2}=0$ yields:
$$
\begin{align}
\begin{split}
-r_{1} &= 3 x_{1}-6\\
-x_{2} &= -2 x_{1}-2\\
-r_{3} &= 8 x_{1}-12
\end{split}
\Leftrightarrow
\begin{split}
r_{1} &= 6 - 3x_{1} & (x_{1} \leq 2)\\
x_{2} &= 2 + 2x_{1} & (\text{$x_{1}$に上限なし} | \text{$x_{1}$ has no upper bound})\\
r_{3} &= 12-8x_{1} \quad&(x_{1} \leq \tfrac{3}{2})
\end{split}
\end{align}
$$
ただし，括弧内は，対応する基底変数が非負であるために$x_{1}$が満たすべき条件を表している． なお，$x_{2}=2+2x_{1}$は$x_{1} \geq 0$なら常に非負であるため，$x_{1}$の ==上限を必要としない== ことに注意されたい．
Each inequality in the parentheses is the condition that $x_{1}$ must satisfy for ensuring the corresponding basic row variables to be non-negative. It is noteworthy that the basic row variable $x_{2} = 2+2 x_{2}$ is always non-negative as long as $x_{1} \geq 0$, and thus it necessitates no upper bound to $x_{1}$.

これより，非負制約を担保するためには，$x_{1}$は$\tfrac{3}{2}$までしか増加させられない．$x_{1}=\tfrac{3}{2}$まで増加させた時, **基底変数**, **非基底変数**および**目的関数** は，以下のように変化する：
According to the inequalities, $x_{1}$ can not be larger than $\frac{3}{2}$. When nonbasic column variable is increased to $x_{1}=\frac{3}{2}$, the remaining variables and the objective become:
||変更前 (before)|変更後(after)|
|--|--|--|
|基底変数 (basic row variables): $(r_{1}, x_{2}, \color{red}{r_{3}})$|$(6,2,12)$|$(\tfrac{3}{2}, 5,\color{red}{0})$|
|非基底変数 (nonbasic column variables): $(\color{red}{x_{1}}, r_{2})$|$(0,0)$|$(\color{red}{\tfrac{3}{2}}, 0)$|
|目的関数 (objective): $-z$|$-4$|$-\tfrac{23}{2}$|

変化後の解は，**基底変数**$r_{3}$と**非基底変数**$x_{1}$を入れ替えて得られる以下の**等価**な問題の**基底解**に他ならない．
This is the basic solution of the following dictionary and the corresponding standard equality form, which is obtained by pivoting basic row $r_{3}$ and nonbasic column $x_{1}$.
$$
\begin{array}{c|cc|c}
& x_{1} & r_{2} & -1\\
\hline
-r_{1} & 3 & -1 & 6\\
-x_{2} & -2 & 1 & 2 \\
-r_{3} & 8* & -3 & 12\\
\hline
-z & -5 & 2 & 4
\end{array}
\rightarrow
\begin{array}{c|cc|c}
& r_{3} & r_{2} & -1\\
\hline
-r_{1} & -\frac{3}{8} & \frac{1}{8} & \frac{3}{2} \\
-x_{2} & \frac{1}{4} & \frac{1}{4} & 5 \\
-x_{1} & \frac{1}{8} & -\frac{3}{8} & \frac{3}{2}\\
\hline
-z & \frac{5}{8} & \frac{1}{8} & \frac{23}{2}
\end{array}
$$
$$
\begin{alignat}{6}
\displaystyle \min_{r_{3}, r_{2}, r_{1}, x_{2}, x_{1}} \quad -z&=&\tfrac{5}{8}r_{3} &+& \tfrac{1}{8}r_{2} &-&\tfrac{23}{2}\\
\text{s.t.} \quad
-r_{1}&=-&\tfrac{3}{8} r_{3} &+& \tfrac{1}{8}r_{2} &-& \tfrac{3}{2} \\
-x_{2}&= &\tfrac{1}{4}r_{3}&+& \tfrac{1}{4}r_{2} &-& 5 \\
-x_{1}&=&\tfrac{1}{8} r_{3}&-&\tfrac{3}{8} r_{2} &-& \tfrac{3}{2} \\
&& r_{3}&,&r_{2} &,& r_{1}&, &x_{2}&,&x_{1}&\geq& 0
\end{alignat}
$$

- **基底/非基底変数 (basic/nonbasic variables)**: $\boldsymbol{x}_{B} = (r_{1}, x_{2}, \color{red}{x_{1}}), \boldsymbol{x}_{N} = (\color{red}{r_{3}}, r_{2})$
- **基底解 (basic solution)**: $(r_{1}, x_{2}, x_{1} | r_{3}, r_{2}) = (\tfrac{3}{2}, 5, \tfrac{3}{2}|0,0)$
- 基底解での**目的関数値** (objective at the basic solution): $-z = -\tfrac{23}{2}$

## 収束判定 | Convergence Test
新しく得られた問題の目的関数の**非基底変数**$(r_{3}, r_{2})$の係数は$(\tfrac{5}{8}, \tfrac{1}{8})$ で ==いずれも**非負**である==．このため，これらの非基底変数を0より大きくしても， ==現在の**基底解**より小さな目的関数は実現できない==． → **最適解**が求められた!!
At the above last solution, the coefficients of the objective with respect to the nonbasic column variables $(r_{3}, r_2)$, $(\frac{5}{8}, \frac{1}{8})$, is non-negative, and thus the objective function can not be smaller by increasing these nonbasic variables from $0$. That is, it's **optimal** !!.

# 単体法の手続き | Procedure of Simplex Method
**単体法**の手続きは以下のように整理できる:
The whole procedure of the simplex method can be summarized as:
1. **初期許容基底解**を1つ選び, 対応する**辞書**を構成する.
Find an initial feasible basic solution and obtain the corresponding dictionary.
2. ==$−\hat{c}_{k}$(目的関数の係数)が負となる== **辞書**の列(**非基底変数**)$k$の中から任意の1つを選び,$j$とする. 全ての列について$-\hat{c}_{k} \geq 0$ならば，いまの**基底解**が**最適解**.
Choose a nonbasic column variable with negative coefficient and let it denote by $j \in \{k: -\hat{c}_{k} < 0\}$. If there is no column with negative coefficient, i.e., $-\hat{c}_{k} \geq 0$ for all $k$, the current basic solution is **optimal**. **STOP**.
3. $\hat{a}_{h,j}>0$となる**辞書**の行(**基底変数**)$h$の中から, ==$\hat{b}_{h}/\hat{a}_{h,j}$が最小となるもの== を 1 つ選び,$i$とする. 全ての行について$\hat{a}_{h,j} ≤ 0$ならば, その問題は**無界**である.
Choose a basic row variable with $\hat{a}_{h, j}> 0$ that minimizes $\hat{b}_{h}/\hat{a}_{h,j}$ and let it denote by $i$. If $\hat{a}_{h,j} \leq 0$ for all $h$, the problem is **unbounded**. **STOP**.
4. $\hat{a}_{i,j}$を**ピボット**として**辞書**を更新する.
Update the dictionary around the pivot $\hat{a}_{i, j}$.

**初期許容基底解**の選び方:
How to choose the initial feasible basic solution:
- もとの問題の等式標準形が$\boldsymbol{b}≥\boldsymbol{0}$となる場合,原点($\boldsymbol{x}=\boldsymbol{0}$) に対応する**基底解** が**許容**であるため，これを**初期許容基底解**とできる.
If the original standard equality form has $\boldsymbol{b} \geq \boldsymbol{0}$, the corresponding basic solution $(\boldsymbol{r}|\boldsymbol{x})=(\boldsymbol{b}|\boldsymbol{0})$ is feasible and thus can be the initial solution.
- $\boldsymbol{b}\not\geq\boldsymbol{0}$の場合,もとの問題の**補助問題**を**単体法**で解くことで**初期許容基底解**を見つける(**二段階単体法**).
If $\boldsymbol{b} \not\geq \boldsymbol{0}$, the initial feasible basic solution can be obtained by solving the so-called auxiliary problem by using the simplex method. It is referred to as the Two-Phase Simplex Method.

# 巡回問題と最小添字規則 | Cycling and Smallest Subscript Rule
## 巡回 | Cycling
**単体法**が終了するときには，
When the simplex method stops, either is guaranteed that
- **最適解**が求められる
an optimal solution is found;
- **無界**であることが判明する
the problem is found to be unbounded.
のいずれかとなることが保証される．では**単体法**は必ず終了するのだろうか?
Then, does the simplex method always stop?

**単体法**では**ピボット**の列(**非基底変数**)や行(**基底変数**)の選び方に自由度があり，適当に選ぶと終了しない場合がある．例えば，以下の**標準最大化問題**:
In the simplex method, the choice of the nonbasic column and the basic row could be *arbitrary*, and inadequate choices might result an infinite loop. Consider the following standard maximization problem and its dictionary:
$$
\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}
\qquad
\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}
$$
に対して，以下のように注意深く**ピボット**を選ぶと，無限ループが生まれる．
When the pivot is chosen as follows, it loops infinitely.
$$
\begin{array}{ccc}
\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}
\\
\Uparrow & & \Downarrow
\\
\begin{array}{c|cccc|c}
& x_{3} & r_{2} & x_{1} & x_{2} & -1\\
\hline
-r_{1} & 1 & -2 & -3 & 4 & 0\\
-x_{4} & -1 & 1* & 2 & -3 & 0\\
-r_{3} & 1 & 0 & 0 & 0 & 1\\
\hline
-z & 1 & -2 & -7 & 11 & 0
\end{array}
&&
\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}
\\
\Uparrow & & \Downarrow
\\
\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}
&\Leftarrow&
\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}
\end{array}
$$

こうした現象を**巡回**(cycling)と呼ぶ．**巡回**が起こるのは，全ての**ピボット演算**が**退化**(degenerate; **ピボット演算**の前後で**基底解**が変化しない)とき． 実際，上記の巡回でも一番右の列は全く変化していない．
The above infinite loop is referred to as *cycling* and caused when every pivot operations are degenerated (i.e. the basic solution remains unchanged by pivot operations). It is easily confirmed that the right-most column is never changed in the above operations.

## 最小添字規則 | Smallest Subscript Rule
**巡回**が起きるのは, **非基底変数**(列)や**基底変数**(行)に複数の候補が存在し，選択に自由度があるとき. 従って**巡回**が起きないように行・列の選び方を**限定**すれば, **単体法**の停止性を保証できる. その最も簡単かつエレガントな規則として, 以下の**最小添字規則**(smallest subscript rule)が知られている. まず，(スラックも含めた)未知変数について，添字の小さい順に
The cycling is occurred only with arbitrary choices of the pair of nonbasic column and basic row. This implies that it is never happen if such arbitrary choices are ruled out. The most simplest rule is known as the *smallest subscript rule*, in which, the all variables (including slacks) are prioritized from the smaller subscript to the larger as

$$x_1 \succ x_2 \succ \cdots \succ x_{N} \succ r_{1} \succ r_{2} \cdots r_{M}$$
と優先順位をつけておく.そして,
Then, the following rules are applied:
- **非基底変数**(列)の候補(i.e.目的関数の係数$−\hat{c}_j$が負)が複数ある場合, その中で最も優先順位の高い (添字の小さい)ものを選ぶ;
When there are two or more candidates of the nonbasic column variables (i.e. those with $-\hat{c}_{j} < 0$), choose the one with the highest priority (i.e. the smallest subscript);
- **基底変数**(行)の候補(i.e.非基底変数を増やした時に最初に0になる)が複数ある場合, その中で最も優先順位の高い(添字が小さい)ものを選ぶ
When there are two or more candidates of the basic row variables (i.e. those first become $0$ when the nonbasic $j$ th column variable is increased), choose the one with the highest priority (i.e. the smallest subscript).

とする.

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

## 課題2 | Exercise 2
講義で紹介した**巡回**が起きる問題に対し, **最小添字規則**を適用して**単体法**が終了する(**巡回**から抜け出せる)ことを確認せよ.
Confirm that the cycling in the above example can be resolved by applying the smallest subscript rule.