---
lang: ja
tags: OptMech-2021, lecture
---
# 2021年度 知的システム<br>第6回：線形計画問題(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</code>
</div>

# 辞書の更新とリア充問題の最適解
リア充問題の**等式標準形**：
$$
\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回の**ピボット演算**を行う:
1. **説明変数**$x_{2}$と**被説明変数**$r_{2}$を入れ替える
2. **説明変数**$x_{1}$と**被説明変数**$r_{3}$を入れ替える

このとき，**辞書**は下記：
$$
\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}
$$
のように変化する．最後の辞書は，**説明変数**を$\mathbf{u}=(r_{3}, r_{2})$，**被説明変数**を$\mathbf{v}=(r_{1}, x_{2}, x_{1})$としている．これに対応した**等式標準形**の線形計画問題は以下のように表される：
$$
\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)$は**実行可能**である．

$r_{2}, r_{3}$が非負である限り目的関数が$-z=-\frac{23}{2}$よりも小さくなることはないから，この解は**最適解**である．結局のところ，もとの問題の**最適解**および**最適値**は，以下のように求められる:
- **最適解**: $(r_{3}, r_{2} | r_{1}, x_{2}, x_{1})=\left(0, 0 \left| \tfrac{3}{2}, 5, \tfrac{3}{2}\right.\right)$,
- **最適値**: $z = \tfrac{23}{2}$.

この結果を一般化してみよう．

# 辞書の更新と標準最大化問題の最適解
**標準最大化問題**に対して，ある**辞書**
$$
\begin{array}{c|c|c}
& \mathbf{u}^{\top} & -1 \\
\hline
-\mathbf{v} & \hat{\mathbf{A}} & \hat{\mathbf{b}} \\
\hline
-z & - \hat{\mathbf{c}}^{\top} & \hat{\zeta}
\end{array}
$$
が与えられた時， ==**$\hat{\mathbf{b}} \geq \hat{\mathbf{0}}$ かつ$-\hat{\mathbf{c}} \geq \mathbf{0}$**== ならば，$(\mathbf{v}|\mathbf{u}) = (\hat{\mathbf{b}}|\mathbf{0})$ は，対応する **等式標準形**:
\begin{alignat}{3}
\min_{\mathbf{u}, \mathbf{v}}
&& -\hat{\mathbf{c}}^{\top} \mathbf{u} - \hat{\zeta} &= - z\\
\text{s.t.}
&& \hat{\mathbf{A}} \mathbf{u} - \hat{\mathbf{b}} &= - \mathbf{v} \\
&& \mathbf{u}, \mathbf{v} &\geq \mathbf{0}
\end{alignat}
の**最適解**であり，その**最適値**は$-z = -\hat{\zeta}$ である．

従って，ある**標準最大化**問題:
$$
\max_{\mathbf{x}} \left\{
z = \mathbf{c}^{\top} \mathbf{x} \left|
\mathbf{A} \mathbf{x} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0}
\right.
\right\}
$$
の**最適解**を求める問題は，その**等式標準形**:
$$
\min_{\mathbf{x}, \mathbf{r}} \left\{
-z = \mathbf{c}^{\top} \mathbf{x} \left|
\mathbf{A} \mathbf{x} - \mathbf{b} = - \mathbf{r}, \quad \mathbf{x}, \mathbf{r} \geq \mathbf{0}
\right.
\right\}
$$
と**等価な辞書**:
$$
\begin{align}
-\mathbf{v} &= \hat{\mathbf{A}} \mathbf{u}-\hat{\mathbf{b}} \\
-z &= - \hat{\mathbf{c}}^{\top} \mathbf{u} - \hat{\zeta}
\end{align}
$$
の中で， ==**$\hat{\mathbf{b}} \geq \mathbf{0}$ かつ $-\hat{\mathbf{c}} \geq \mathbf{0}$**== なるものを求める問題に帰着する．

ここまで判ったことを整理すると，**標準最大化問題**の**等式標準形**に対して
1. **辞書**の一つは $(\mathbf{v}|\mathbf{u}) = (\mathbf{r}|\mathbf{x}), (\hat{\mathbf{A}}, \hat{\mathbf{b}}, \hat{\mathbf{c}}) = (\mathbf{A}, \mathbf{b}, \mathbf{c})$ で与えられる．
2. **等価な辞書**$(\hat{\mathbf{A}}, \hat{\mathbf{b}}, \hat{\mathbf{c}})$は**ピボット演算**によって生成できる．
3. そうした**辞書**の中で$\hat{\mathbf{b}} \geq \mathbf{0}$かつ$-\hat{\mathbf{c}} \geq \mathbf{0}$ なるものが(たまたま)見つかれば，もとの問題の**最適解**および**最適値**は, それぞれ, $(\mathbf{v}^{\ast}|\mathbf{u}^{\ast}) = (\hat{\mathbf{b}}|\mathbf{0})$および$z^{\ast} = \hat{\zeta}$ と求められる．

最適解が自明となる(i.e. $\hat{\mathbf{b}} \geq \mathbf{0}$かつ$-\hat{\mathbf{c}} \geq \mathbf{0}$)辞書に必ず辿りつく方法はないだろうか? その問いに答えるのが，次に述べる**単体法**である．

# 単体法
==**単体法 (simplex method)**== は米国の George B. Dantzig が1947 年に提案. 60年以上経過した今日でも**非常に有効な**線形計画問題の数値解法として広く利用されている. **単体法**では以下の用語が使われる:
- **被説明変数**$\mathbf{v}$ → ==**基底変数**==(basic variable) $\mathbf{x}_B$
- **説明変数**$\mathbf{u}$ → ==**非基底変数**==(nonbasic variable) $\mathbf{x}_N$
- **説明変数**を$\mathbf{0}$, **被説明変数**を$\hat{\mathbf{b}}$ とした解 → ==**基底解**==(basic solution)

**単体法**の特徴は以下のように整理される:
- **許容基底解**の1つから始め,(等式標準形の)目的関数の値が**減少**し, かつ**実行可能性**が担保されるように, **ピボット演算**によって次々と**辞書**を更新する.
- *目的関数の**係数が負***となる非基底変数の値を0から増やすため, 目的関数値は*必ず減少*
- **非基底変数**の増加に伴い,少なくとも1つの**基底変数**の値が減少するが, いずれかの**基底変数**が0となったところで**非基底変数**と*入れ替える*ため, **実行可能性**が担保される.

# リア充問題で単体法の基本的動作を確認
## 初期解
リア充問題の**等式標準形**と**辞書**:
$$
\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}
$$
- **基底変数** (被説明変数): $\mathbf{x}_{B} = (r_{1}, r_{2}, r_{3})$
- **非基底変数** (説明変数): $\mathbf{x}_{N} = (x_{1}, x_{2})$
- **基底解** : $(r_{1}, r_{2}, r_{3}| x_{1}, x_{2}) = (8, 2, 18|0,0)$
- 基底解での**目的関数値**: $-z = 0$

## 1回目の解の改訂
目的関数の **非基底変数** $x_{1}, x_{2}$についての係数は$(-1, -2)$で ==いずれも負==． 従って，$x_{1}, x_{2}$を0より大きくすることで， *現在の**基底解**より小さな目的関数値を実現できる*．

例えば，**非基底変数**のうち，$x_{1}=0$のままにして，$x_{2}$を0から増やすことを考えよう．**等式制約**から，$x_{2}$が変化することで，**基底変数**の値は，以下のように変化する：
$$
\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}$が満たすべき条件を表している．

これより，非負制約$\mathbf{x}, \mathbf{r} \geq \mathbf{0}$ を担保するためには，$x_{2}$は2までしか増加させられない．$x_{2}=2$まで増加させた時, **基底変数**, **非基底変数**および**目的関数**は以下のように変化する：
||変更前|変更後|
|--|--|--|
|基底変数$(r_{1}, \color{red}{r_{2}}, r_{3})$|$(8,2,8)$|$(6,\color{red}{0}, 12)$|
|非基底変数$(x_{1}, \color{red}{x_{2}})$|$(0,0)$|$(0,\color{red}{2})$|
|目的関数 $-z$|0|$-4$|

変化後の解は，**基底変数**$r_{2}$と**非基底変数**$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}
$$

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

## 2回目の解の改訂
新しく得られた問題の目的関数の **非基底変数** $x_{1}, r_{2}$の係数は$(-5, 2)$. ==係数が負である$x_{1}$== を0より大きくすることで，*現在の**基底解**より小さな目的関数値を実現できる*．

$r_{2}=0$のまま**非基底変数** $x_{1}$を0から増やすと，**等式制約**から，**基底変数**の値は，以下のように変化する：
$$
\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}$に上限なし})\\
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}$の ==上限を必要としない== ことに注意されたい．

これより，非負制約を担保するためには，$x_{1}$は$\tfrac{3}{2}$までしか増加させられない．$x_{1}=\tfrac{3}{2}$まで増加させた時, **基底変数**, **非基底変数**および**目的関数** は，以下のように変化する：
||変更前|変更後|
|--|--|--|
|基底変数$(r_{1}, x_{2}, \color{red}{r_{3}})$|$(6,2,12)$|$(\tfrac{3}{2}, 5,\color{red}{0})$|
|非基底変数$(\color{red}{x_{1}}, r_{2})$|$(0,0)$|$(\color{red}{\tfrac{3}{2}}, 0)$|
|目的関数 $-z$|$-4$|$-\tfrac{23}{2}$|

変化後の解は，**基底変数**$r_{3}$と**非基底変数**$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}
$$

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

## 収束判定
新しく得られた問題の目的関数の**非基底変数**$(r_{3}, r_{2})$の係数は$(\tfrac{5}{8}, \tfrac{1}{8})$ で ==いずれも**非負**である==．このため，これらの非基底変数を0より大きくしても， ==現在の**基底解**より小さな目的関数は実現できない==． → **最適解**が求められた!!

# 単体法の手続き
**単体法**の手続きは以下のように整理できる:
1. **初期許容基底解**を1つ選び, 対応する**辞書**を構成する.
2. ==$−\hat{c}_{k}$(目的関数の係数)が負となる== **辞書**の列(**非基底変数**)$k$の中から任意の1つを選び,$j$とする. 全ての列について$-\hat{c}_{k} \geq 0$ならば，いまの**基底解**が**最適解**.
3. $\hat{a}_{h,j}>0$となる**辞書**の行(**基底変数**)$h$の中から, ==$\hat{b}_{h}/\hat{a}_{h,j}$が最小となるもの== を 1 つ選び,$i$とする. 全ての行について$\hat{a}_{h,j} ≤ 0$ならば, その問題は**無界**である.
4. $\hat{a}_{i,j}$を**ピボット**として**辞書**を更新する.

**初期許容基底解**の選び方:
- もとの問題の等式標準形が$\mathbf{b}≥\mathbf{0}$となる場合,原点($\mathbf{x}=\mathbf{0}$) に対応する**基底解 **が**許容**であるため，これを**初期許容基底解**とできる.
- $\mathbf{b}\not\geq\mathbf{0}$の場合,もとの問題の**補助問題**を**単体法**で解くことで**初期許容基底解**を見つける(**二段階単体法**).

# 巡回問題と最小添字規則
## 巡回
**単体法**が終了するときには，
- **最適解**が求められる
- **無界**であることが判明する

のいずれかとなることが保証される．では**単体法**は必ず終了するのだろうか?

**単体法**では**ピボット**の列(**非基底変数**)や行(**基底変数**)の選び方に自由度があり，適当に選ぶと終了しない場合がある．例えば，以下の**標準最大化問題**:
$$
\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}
$$
に対して，以下のように注意深く**ピボット**を選ぶと，無限ループが生まれる．
$$
\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; **ピボット演算**の前後で**基底解**が変化しない)とき． 実際，上記の巡回でも一番右の列は全く変化していない．

## 最小添字規則
**巡回**が起きるのは, **非基底変数**(列)や**基底変数**(行)に複数の候補が存在し，選択に自由度があるとき. 従って**巡回 が**起きないように行・列の選び方を**限定**すれば, **単体法**の停止性を保証できる. その最も簡単かつエレガントな規則として, 以下の**最小添字規則**(smallest subscript rule)が知られている. まず，(スラックも含めた)未知変数について，添字の小さい順に
$$x_1 \succ x_2 \succ \cdots \succ x_{N} \succ r_{1} \succ r_{2} \cdots r_{M}$$
と優先順位をつけておく.そして，
- **非基底変数**(列)の候補(i.e.目的関数の係数$−\hat{c}_j$が負)が複数ある場合, その中で最も優先順位の高い (添字の小さい)ものを選ぶ
- **基底変数**(行)の候補(i.e.非基底変数を増やした時に最初に0になる)が複数ある場合, その中で最も優先順位の高い(添字が
小さい)ものを選ぶ

とする.

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

## 課題2
講義で紹介した**巡回**が起きる問題に対し, **最小添字規則**を適用して**単体法**が終了する(**巡回**から抜け出せる)ことを確認せよ.