---
lang: ja
tags: lecture, linear programming
---
# 線形計画問題(7) 改訂単体法 - Linear Programming(7): Revised Simplex Method
[線形計画問題ポータルへ戻る | Back to LP Portal](https://hackmd.io/@nagae/LP)
<div style="text-align: center">
このページへは以下のQRコードまたはURLからアクセスできます：
You can access to this page via the following QR code or URL:
<code style="font-size:20pt">https://hackmd.io/@nagae/LP-Ch07</code>
</div>
# 改訂単体法とは | What is the Revised Simplex Method?
**単体法**の実装において**ピボット演算**によって**辞書**を更新することの問題点：
Problems with updating dictionaries by pivot operations in the simplex method:
- **辞書**全体を計算し直すのは効率が悪い :
It is inefficient to update the entire dictionary:
- **非基底変数**の選択には**目的関数の行**しか使わない;
Only the objective row is used to choose a non-basic column variable;
- **基底変数**の選択には**非基底変数の列**と **(右辺)定数**の列しか使わない.
Only the non-basic column and the RHS constants are used to choose a basic row variable.
- 反復が多くなると**計算誤差**が蓄積される．
Computational errors accumulate as the number of iterations increases.
辞書を直接更新するのではなく，**単体乗数**と**基底行列の逆行列**を改訂することでこれらの欠点を補うのが**改訂単体法**．
The **revised simplex method** improves these disadvantages by updating the **simplex multipliers** and the **inverse basic matrix** rather than the entire dictionary.
前回までで解説した**単体法**の手続きを**代数的に説明したもの**と位置付けることもできる．
It also can be recognized as an algebraic procedure of the simplex method.
# 等式標準形ふたたび | Re: Standard Equality Form
**標準最大化問題**に対する**等式標準形**は以下で構成される：
The standard equality form of the standard maximization problem consists of
- (**スラック変数**を含めた)==$N+M$次元== の非負の未知変数
$N+M$ dimensional non-negative unknown variables (including the **slack variables**);
- ==$M$本== の等式制約
$M$ equality constraints.
$$
\begin{array}{crcrrcc}
\displaystyle\min_{x_{1},\cdots,x_{N},r_{1},\cdots,r_{M}} \quad
&-c_{1} x_{1} &-\cdots &-c_{N} x_{N} &-0\cdot r_{1}&+\cdots+&0\cdot r_{M} &=& -z\\
\text{s.t.}
&a_{11} x_{1} &+\cdots&+a_{1N} x_{N}&+r_{1}&+\cdots+&0&=&b_{1}\\
&\vdots & &\vdots& &&\vdots \\
&a_{M1} x_{1} &+\cdots&+a_{MN} x_{N}&0&+\cdots+&
r_{M}&=&b_{M}\\
&x_{1},&\cdots&x_{N},& r_{1},&\cdots&r_{M}&\geq&0
\end{array}
$$
# 基底変数と辞書 | Basic Variables and Dictionary
$N+M$次元の未知変数を$M$次元の**基底変数**(被説明変数) $\boldsymbol{x}_{B}$ と $N$次元の **非基底変数** (説明変数) $\boldsymbol{x}_{N}$ に分割する．
Let decompose $N+M$ unknown variables into $M$ **basic variables** (explained variables), $\boldsymbol{x}_{B}$, and $N$ **nonbasic variables** (explanatory variables), $\boldsymbol{x}_{N}$.
この時， **等式標準形** の **等式制約** および **目的関数** は
This enables us to rewrite the **equality constraints** and the **objective function** as
$$
\begin{align}
\boldsymbol{A}_{B} \boldsymbol{x}_{B} + \boldsymbol{A}_{N} \boldsymbol{x}_{N} &= \boldsymbol{b}\\
-\boldsymbol{c}_{B}^{\top} \boldsymbol{x}_{B} - \boldsymbol{c}_{N}^{\top} \boldsymbol{x}_{N} &= -z
\end{align}
$$
と表せる． ここで，
where,
- $\boldsymbol{A}_{B} \in \mathcal{R}^{M\times M}$: **基底行列** (basis matrix)
- $\boldsymbol{A}_{N} \in \mathcal{R}^{M\times N}$: **非基底行列** (nonbasis matrix)
- $\boldsymbol{c}_{B} \in \mathcal{R}^{M}, \boldsymbol{c}_{N} \in \mathcal{R}^{N}$.
Note that the variables are basic and nonbasic, while the matrices are basis and nonbasis.
等式制約の分割：
Given the decomposition of the equality constraint
$$
\boldsymbol{A}_{B} \boldsymbol{x}_B + \boldsymbol{A}_N \boldsymbol{x}_N = \boldsymbol{b}
$$
が与えられた時，**基底行列** $\boldsymbol{A}_{B}$が**逆行列**をもてば，**基底変数**$\boldsymbol{x}_B$を**非基底変数**$\boldsymbol{x}_{N}$で「説明」できる．
if the **basis matrix** $\boldsymbol{A}_{B}$ is invertible, the **basic variable** $\boldsymbol{x}_{B}$ can be "explained" by the **nonbasic variable** $\boldsymbol{x}_{N}$:
$$
-\boldsymbol{x}_{B} = - \boldsymbol{A}_{B}^{-1}\left(
\boldsymbol{b} - \boldsymbol{A}_{N} \boldsymbol{x}_{N}
\right) = - \boldsymbol{A}_{B}^{-1} \boldsymbol{b} + \boldsymbol{A}_{B}^{-1}\boldsymbol{A}_{N}\boldsymbol{x}_{N}$$
こうして得られた**基底変数**$\boldsymbol{x}_{B}$を目的関数に代入すれば，目的関数もまた**非基底変数**$\boldsymbol{x}_{N}$で「説明」できる．
Substituting this basic variable $\boldsymbol{x}_{B}$ to the objective function, it can be explained by the nonbasic variable $\boldsymbol{x}_{N}$:
$$
\begin{align}
-z &= -\boldsymbol{c}_{B}^{\top} \boldsymbol{x}_{B} - \boldsymbol{c}_{N}^{\top} \boldsymbol{x}_{N}\\
&= -\boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1}\left(\boldsymbol{b} - \boldsymbol{A}_{N} \boldsymbol{x}_{N}\right) - \boldsymbol{c}_{N}^{\top} \boldsymbol{x}_{N}\\
&= -\boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1}\boldsymbol{b}
-\left( \boldsymbol{c}_{N}^{\top} - \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1}\boldsymbol{A}_{N} \right) \boldsymbol{x}_{N}
\end{align}
$$
以上を整理すると，**基底行列**$\boldsymbol{A}_{B}$が逆行列を持つならば，**基底変数**および**目的関数**を**非基底変数**$\boldsymbol{x}_{N}$で「説明」する**辞書**が得られる．
Accordingly, when the basis matrix $\boldsymbol{A}_{B}$ is invertible, a dictionary can be obtained that explains the basic variables and the objective function by nonbasic variables.
$$
\begin{align}
-\boldsymbol{x}_{B} &= \boldsymbol{A}_{B}^{-1} \boldsymbol{A}_{N} \boldsymbol{x}_{N} - \boldsymbol{A}_{B}^{-1} \boldsymbol{b}\\
&= \hat{\boldsymbol{A}} \boldsymbol{x}_{N} - \hat{\boldsymbol{b}}
\\
-z &=
-\left( \boldsymbol{c}_{N}^{\top} - \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1}\boldsymbol{A}_{N} \right) \boldsymbol{x}_{N}
-\boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1}\boldsymbol{b}\\
&= -\hat{\boldsymbol{c}}^{\top} \boldsymbol{x}_{N} - \hat{\zeta}
\end{align}
$$
ここで，
where
$$
\begin{align}
\hat{\boldsymbol{A}} &=\boldsymbol{A}_{B}^{-1} \boldsymbol{A}_{N}, &
\hat{\boldsymbol{b}} &=\boldsymbol{A}_{B}^{-1} \boldsymbol{b}\\
-\hat{\boldsymbol{c}}^{\top} &= \boldsymbol{c}_{N}^{\top} - \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1}\boldsymbol{A}_{N},&
\hat{\zeta} &= \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1}\boldsymbol{b}
\end{align}
$$
は，**単体法**の手続きで改訂されてきた**辞書**の係数に他ならない．
are the coefficients of dictionary.
$$
\begin{array}{c|c|c}
& \boldsymbol{x}_{N}^{\top} & -1 \\
\hline - \boldsymbol{x}_{B} & \hat{\boldsymbol{A}} & \hat{\boldsymbol{b}} \\
\hline
-z & -\hat{\boldsymbol{c}}^{\top} & \hat{\zeta}
\end{array}
\quad
\begin{array}{c|ccc|c}
& x_{N,1} & \cdots & x_{N, N} & -1\\
\hline
-x_{B, 1}& \hat{a}_{11} & \cdots & \hat{a}_{1N} & \hat{b}_{1} \\
\vdots & \vdots & \ddots & \vdots & \vdots
\\
-x_{B, M} & \hat{a}_{M1} & \cdots & \hat{a}_{MN} & \hat{b}_{M}\\
\hline
-z & -\hat{c}_{1} & \cdots & -\hat{c}_{N} & \hat{\zeta}
\end{array}
$$
# 基底行列の例 | Examples of the Basis Matrices
リア充問題の等式標準形:
The standard equality form of Mr. Adam's happiness problem:
$$
\begin{alignat}{6}
\displaystyle \min_{x_{1}, x_{2}, r_{1}, r_{2}, r_{3}} \quad &-&x_{1} &-& 2x_{2} &&&&&&&=&-z\\
\text{s.t.} \quad
&&x_{1} &+& x_{2} &+&r_{1}&&&&&=& 8 \\
&&-2x_{1}&+& x_{2} &&&+&r_{2}&&&=& 2 \\
&&2x_{1}&+&3x_{2} &&&&&+&r_{3}&=& 18 \\
&& x_{1}&,&x_{2} &, &r_{1}&,&r_{2}&,&r_{3}&\geq& 0
\end{alignat}
$$
## 基底・非基底変数を$(\boldsymbol{x}_{B}| \boldsymbol{x}_{N})=(r_{1}, r_{2}, r_{3}|x_{1}, x_{2})$とした場合 | Case with Basic/Nonbasic Variables $(\boldsymbol{x}_{B}| \boldsymbol{x}_{N})=(r_{1}, r_{2}, r_{3}|x_{1}, x_{2})$
等式制約から **基底変数**を「説明」する辞書が得られる：
The equality constraints yield the dictionary that "explains" the basic variables:
$$\begin{gather}
\underbrace{
\begin{bmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{bmatrix}}_{\boldsymbol{A}_{B}}
\begin{bmatrix}
r_{1} \\ r_{2} \\ r_{3}
\end{bmatrix}
+\underbrace{\begin{bmatrix}
1 & 1\\
-2 & 1 \\
2 & 3
\end{bmatrix}}_{\boldsymbol{A}_{N}}
\begin{bmatrix}
x_{1} \\ x_{2}
\end{bmatrix}
=\begin{bmatrix}
8 \\ 2 \\ 18
\end{bmatrix}
\\
\Downarrow\text{($\boldsymbol{A}_{B}^{-1}$を左から乗じる | multiply $\boldsymbol{A}_{B}^{-1}$ from left)}
\\
-\begin{bmatrix}
r_{1} \\ r_{2} \\ r_{3}
\end{bmatrix}=
\underbrace{
\begin{bmatrix}
1 & 1\\
-2 & 1 \\
2 & 3
\end{bmatrix}
}_{\hat{\boldsymbol{A}}}
\begin{bmatrix}
x_{1} \\ x_{2}
\end{bmatrix}
-\underbrace{\begin{bmatrix}
8 \\ 2 \\ 18
\end{bmatrix}}_{\hat{\boldsymbol{b}}}
\end{gather}
$$
これを用いれば，目的関数を「説明」する辞書も得られる：
Substituting this to the objective, the corresponding dictionary is obtained:
$$\begin{gather}
-z = \underbrace{\begin{bmatrix}
0 & 0 & 0
\end{bmatrix}}_{-\boldsymbol{c}_{B}^{\top}}
\begin{bmatrix}
r_{1} \\ r_{2} \\ r_{3}
\end{bmatrix} +
\underbrace{
\begin{bmatrix}
-1 & -2
\end{bmatrix}
}_{-\boldsymbol{c}_{N}^{\top}}
\begin{bmatrix}
x_{1} \\ x_{2}
\end{bmatrix}
\\
\Downarrow\ \text{($\boldsymbol{x}_{B}$を代入する | substitue $\boldsymbol{x}_{B}$)}
\\
-z = \underbrace{\begin{bmatrix}
-1 & -2
\end{bmatrix}
}_{-\hat{\boldsymbol{c}}^{\top}}
\begin{bmatrix}
x_{1} \\ x_{2}
\end{bmatrix}
-\underbrace{0}_{\hat{\zeta}}
\end{gather}
$$
## 基底・非基底変数を$(\boldsymbol{x}_{B}| \boldsymbol{x}_{N})=(r_{1}, x_{1}, r_{3}|r_{2}, x_{2})$と分割した場合 | Case with Basic/Nonbasic Variables $(\boldsymbol{x}_{B}| \boldsymbol{x}_{N})=(r_{1}, x_{1}, r_{3}|r_{2}, x_{2})$
基底変数を「説明」する辞書:
The dictionary that "explains" the basic variables:
$$\begin{gather}
\underbrace{
\begin{bmatrix}
1 & \color{red}{1} & 0\\
0 & \color{red}{-2} & 0\\
0 & \color{red}{2} & 1
\end{bmatrix}}_{\boldsymbol{A}_{B}}
\begin{bmatrix}
r_{1} \\ \color{red}{x_{1}} \\ r_{3}
\end{bmatrix}
+\underbrace{\begin{bmatrix}
\color{blue}{0} & 1\\
\color{blue}{1} & 1 \\
\color{blue}{0} & 3
\end{bmatrix}}_{\boldsymbol{A}_{N}}
\begin{bmatrix}
\color{blue}{r_{2}} \\ x_{2}
\end{bmatrix}
=\begin{bmatrix}
8 \\ 2 \\ 18
\end{bmatrix}
\\
\Downarrow\text{($\boldsymbol{A}_{B}^{-1}$を左から乗じる | multiply $\boldsymbol{A}_{B}^{-1}$ from left))}
\\
-\begin{bmatrix}
r_{1} \\ x_{1} \\ r_{3}
\end{bmatrix}=
\underbrace{
\begin{bmatrix}
\frac{1}{2} & \frac{3}{2} \\
-\frac{1}{2} & -\frac{1}{2} \\
1 & 4
\end{bmatrix}
}_{\hat{\boldsymbol{A}}}
\begin{bmatrix}
r_{2} \\ x_{2}
\end{bmatrix}
-\underbrace{\begin{bmatrix}
9 \\ -1 \\ 20
\end{bmatrix}}_{\hat{\boldsymbol{b}}}
\end{gather}
$$
目的関数を「説明」する辞書
The dictionary that "explains" the objective:
$$\begin{gather}
-z = \underbrace{\begin{bmatrix}
0 & \color{red}{-1} & 0
\end{bmatrix}}_{-\boldsymbol{c}_{B}^{\top}}
\begin{bmatrix}
r_{1} \\ \color{red}{x_{1}} \\ r_{3}
\end{bmatrix} +
\underbrace{
\begin{bmatrix}
\color{blue}{0} & -2
\end{bmatrix}
}_{-\boldsymbol{c}_{N}^{\top}}
\begin{bmatrix}
\color{blue}{r_{2}} \\ x_{2}
\end{bmatrix}
\\
\Downarrow \text{($\boldsymbol{x}_{B}$を代入する | substitute $\boldsymbol{x}_{B}$)}
\\
-z = \underbrace{\begin{bmatrix}
-\frac{1}{2} & -\frac{5}{2}
\end{bmatrix}
}_{-\hat{\boldsymbol{c}}^{\top}}
\begin{bmatrix}
r_{2} \\ x_{2}
\end{bmatrix}
-\underbrace{1}_{\hat{\zeta}}
\end{gather}
$$
## 基底/非基底変数を$(\boldsymbol{x}_{B}| \boldsymbol{x}_{N})=(r_{1}, x_{2}, r_{3}|x_{1}, r_{2})$とした場合 | Case with Basic/Nonbasic Variables $(\boldsymbol{x}_{B}| \boldsymbol{x}_{N})=(r_{1}, x_{2}, r_{3}|x_{1}, r_{2})$
**基底変数**を「説明」する辞書
The dictionary that "explains" the basic variables:
$$\begin{gather}
\underbrace{
\begin{bmatrix}
1 & \color{red}{1} & 0\\
0 & \color{red}{1} & 0\\
0 & \color{red}{3} & 1
\end{bmatrix}}_{\boldsymbol{A}_{B}}
\begin{bmatrix}
r_{1} \\ \color{red}{x_{2}} \\ r_{3}
\end{bmatrix}
+\underbrace{\begin{bmatrix}
1 & \color{blue}{0} \\
-2& \color{blue}{1} \\
2 & \color{blue}{0}
\end{bmatrix}}_{\boldsymbol{A}_{N}}
\begin{bmatrix}
x_{1}\\\color{blue}{r_{2}}
\end{bmatrix}
=\begin{bmatrix}
8 \\ 2 \\ 18
\end{bmatrix}
\\
\Downarrow\text{($\boldsymbol{A}_{B}^{-1}$を左から乗じる | multiply $\boldsymbol{A}_{B}^{-1}$ from left)}
\\
-\begin{bmatrix}
r_{1} \\ x_{2} \\ r_{3}
\end{bmatrix}=
\underbrace{
\begin{bmatrix}
3 & -1\\
-2 & 1\\
8 & -3
\end{bmatrix}
}_{\hat{\boldsymbol{A}}}
\begin{bmatrix}
x_{1} \\ r_{2}
\end{bmatrix}
-\underbrace{\begin{bmatrix}
6 \\ 2 \\ 12
\end{bmatrix}}_{\hat{\boldsymbol{b}}}
\end{gather}
$$
目的関数を「説明」する辞書:
The dictionary that "explains" the objective:
$$\begin{gather}
-z = \underbrace{\begin{bmatrix}
0 & \color{red}{-2} & 0
\end{bmatrix}}_{-\boldsymbol{c}_{B}^{\top}}
\begin{bmatrix}
r_{1} \\ \color{red}{x_{2}} \\ r_{3}
\end{bmatrix} +
\underbrace{
\begin{bmatrix}
-1 & \color{blue}{0}
\end{bmatrix}
}_{-\boldsymbol{c}_{N}^{\top}}
\begin{bmatrix}
x_{1} \\ \color{blue}{r_{2}}
\end{bmatrix}
\\
\Downarrow \text{($\boldsymbol{x}_{B}$を代入する | substitue $\boldsymbol{x}_{B}$)}
\\
-z = \underbrace{\begin{bmatrix}
-5 & 2
\end{bmatrix}
}_{-\hat{\boldsymbol{c}}^{\top}}
\begin{bmatrix}
x_{1} \\ r_{2}
\end{bmatrix}
-\underbrace{(-4)}_{\hat{\zeta}}
\end{gather}
$$
# 基底解と最適性条件 | Basic Solution and Optimality Condition
**改訂単体法**の**辞書**:
For a given dictionary in the revised simplex method:
$$
\begin{align}
-\boldsymbol{x}_{B} &= \boldsymbol{A}_{B}^{-1} \boldsymbol{A}_{N} \boldsymbol{x}_{N}
-\boldsymbol{A}_{B}^{-1} \boldsymbol{b} \\
-z &= \color{red}{\left(\boldsymbol{c}_{N}^{\top} - \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1} \boldsymbol{A}_{N}\right)} \boldsymbol{x}_{N} - \boldsymbol{c}_{B}^{\top}\boldsymbol{A}_{B}^{-1} \boldsymbol{b}
\end{align}
$$
に対する**基底解**は$(\boldsymbol{x}_{B} | \boldsymbol{x}_{N})= \left(\left.\boldsymbol{A}_{B}^{-1} \boldsymbol{b}\right|\boldsymbol{0}\right)$であり，その**最適性**は目的関数の係数から判別できる:
the corresponding basic solution is $(\boldsymbol{x}_{B} | \boldsymbol{x}_{N})= \left(\left.\boldsymbol{A}_{B}^{-1} \boldsymbol{b}\right|\boldsymbol{0}\right)$ and its **optimality** can be examined by using the coefficients of the objective function:
$$
-\hat{\boldsymbol{c}}^{\top} = \boldsymbol{c}_{N}^{\top} - \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1}\boldsymbol{A}_{N}
$$
- $-\hat{\boldsymbol{c}}\geq\boldsymbol{0}$ なら**基底解**が最適解
If $-\hat{\boldsymbol{c}}\geq\boldsymbol{0}$ then the current basic solution is optimal.
- $-\hat{\boldsymbol{c}}\not\geq\boldsymbol{0}$ なら$-\hat{c}_{j}<0$なる**非基底変数**$x_{N,j}$の値を0より大きくすることで，より小さな目的関数値が達成できる．
If $-\hat{\boldsymbol{c}}\not\geq\boldsymbol{0}$ then the smaller objective can be achieved by increasing a nonbasic variable $x_{N,j}$ with $-\hat{c}_{j}<0$.
# 基底解の更新と有界性の判別 | Update of Basic Variable and Boundedness Test
$-\hat{c}_{j}<0$なる**非基底変数**$x_{N,j}$を0より大きくすることで，**基底解**は
When a nonbasic variable $x_{N,j}$ with $-\hat{c}_{j}<0$ is increased, the basic variable change as
$$\begin{align}
-\boldsymbol{x}_{B} &= \hat{\boldsymbol{a}}_{j} x_{N, j} - \hat{\boldsymbol{b}}\\
\boldsymbol{x}_{B} &= \hat{\boldsymbol{b}} - \hat{\boldsymbol{a}}_{j} x_{N, j}
\end{align}$$
と変化する．ここで，
where both of the followings are $M$ dimensional column vectors:
- $\hat{\boldsymbol{a}}_{j} = \boldsymbol{A}_{B}^{-1} \boldsymbol{a}_{N,j}$. ただし，$\boldsymbol{a}_{N,j}$は$\boldsymbol{A}_{N}$の$j$番目**列**ベクトル．
$\boldsymbol{a}_{N, j}$ is $j$ th column vector of nonbasis matrix $\boldsymbol{A}_{N}$.
- $\hat{\boldsymbol{b}} = \boldsymbol{A}_{B}^{-1} \boldsymbol{b}$
はいずれも$M$次元列ベクトル．
いま，$\hat{\boldsymbol{a}}_{j}$および$\hat{\boldsymbol{b}}$ の$h$番目要素($h=1,\cdots,M$)を，それぞれ，$\hat{a}_{hj}$および$\hat{b}_{h}$と書く．基底変数の**非負制約**($\boldsymbol{x}_{B} \geq \boldsymbol{0}$)を満足するためには，$x_{N,j}$は
Let us denote $h$ th element ($h=1, \cdots, M$) of $\hat{\boldsymbol{a}}_{j}$ and $\hat{\boldsymbol{b}}$ by $\hat{a}_{hj}$ and $\hat{b}_{h}$, respectively. In order to guarantee the non-negativity of the basic variable, the nonbasic variable $x_{N,j}$ can not exceed:
$$
\alpha = \min\left\{\left.\frac{\hat{b}_{h}}{\hat{a}_{hj}}\right| h: \hat{a}_{hj}>0, h = 1, \cdots, \right\}
$$
までしか大きくできない． 定義より$x_{N,j}=\alpha$とした時にゼロとなる**基底変数**$x_{B,i}$が少なくとも一つは存在する． その中の1つを選び，**非基底変数**$x_{N,j}$と入れ替えることで，**基底**を改訂できる．
From the definition, when $x_{N,j} = \alpha$, at least one of the basic variable, $x_{B,i}$, becomes $0$. By replacing such basic variable $x_{B,i}$ and the nonbasic variable $x_{N,j}$, a new basic can be obtained.
なお，任意の$h=1, \cdots, M$について$\hat{a}_{hj}\leq 0$の場合，非負制約を満足しながら$x_{N,j}$をどこまでも増加させられる．すなわち，問題が**無界**であることが判別できる．
Note that if $\hat{a}_{h,j} \leq 0$ for any $h=1, \cdots, M$, the nonbasic variable $x_{N, j}$ can be infinite without violating the non-negativity of the basic variable (and thus the objective becomes negative infinite). This reveals that the problem is **unbounded**.
# 改訂単体法の手続き | The Procedure of Revised Simplex Method
結局のところ，**改訂単体法**とは**基底変数**$\boldsymbol{x}_{B}$およびその**基底逆行列**$\boldsymbol{A}_{B}^{-1}$を適切に改訂する方法である．その手続きは，以下のように整理できる：
The revised simplex method updates the basic variable $\boldsymbol{x}_{B}$ and the corresponding inverse basis matrix $\boldsymbol{A}_{B}^{-1}$, whose procedure can be summarized as follows:
1. **初期基底変数**$\boldsymbol{x}_{B}$を1つ選び，その**逆行列**$\boldsymbol{A}_{B}^{-1}$を計算する．
Choose an initial basic variable $\boldsymbol{x}_{B}$ and calculate the invert basis matrix $\boldsymbol{A}_{B}^{-1}$.
2. **基底解** $\hat{\boldsymbol{b}}=\boldsymbol{A}_{B}^{-1} \boldsymbol{b}$および**目的関数の係数** $-\hat{\boldsymbol{c}}^{\top} = \boldsymbol{c}_{N}^{\top} - \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1}\boldsymbol{A}_{N}$を計算し， $-\hat{c}_{k}<0$ (i.e. ==**目的関数の係数**が負==)となる **非基底変数** $k$ の中から任意の1つを選び，$j$ とする． 全ての $k$ について $-\hat{c}_{k} \geq 0$ ならば, $\hat{\boldsymbol{b}}$が**最適解**で，**最適値**は$\hat{\zeta} = \boldsymbol{c}_{B}^{\top}\boldsymbol{A}_{B}^{-1} \boldsymbol{b}$.
Calculate the basic solution $\hat{\boldsymbol{b}}=\boldsymbol{A}_{B}^{-1} \boldsymbol{b}$ and the coefficient of the objective function $-\hat{\boldsymbol{c}}^{\top} = \boldsymbol{c}_{N}^{\top} - \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1}\boldsymbol{A}_{N}$. Choose a nonbasic variable $j$ from those with negative coefficients, $\left\{k: -\hat{c}_{k}< 0\right\}$. If $-\hat{c}_{k} \geq 0$ for any $k=1, \dots, N$, the optimal solution and the optimal values are obtained by $\hat{\boldsymbol{b}}$ and $\hat{\zeta} = \boldsymbol{c}_{B}^{\top}\boldsymbol{A}_{B}^{-1} \boldsymbol{b}$, respectively. STOP.
3. $\hat{\boldsymbol{a}}_{j} = \boldsymbol{A}_{B}^{-1} \boldsymbol{a}_{N,j}$ を計算し，$\hat{a}_{hj} > 0$となる**基底変数** $x_{B,h}$ の中から ==$\hat{b}_{h}/\hat{a}_{hj}$が最小となる== (最初に0になる)ものを1つ選び $i$とする． 全ての$h$について$\hat{a}_{hj}\leq 0$ならば，その問題は**無界**である．
Calculate $\hat{\boldsymbol{a}}_{j} = \boldsymbol{A}_{B}^{-1} \boldsymbol{a}_{N,j}$ and choose a basic variable $x_{B,i}$ from candidates such that $\{h: \hat{a}_{h,j} > 0 \text{ and } \hat{b}_{h}/\hat{a}_{hj} \text{ is the smallest}\}$. If $\hat{a}_{hj} \leq 0$ for any $h$, the problem is unbounded. STOP.
4. $(i,j)$を入れ替えた**基底行列**に対して**逆行列**$\boldsymbol{A}_{B}^{-1}$を改訂する．
Update the invert basis matrix $\boldsymbol{A}_{B}^{-1}$ according to the pivot around $(i, j)$.
基底の更新のたびに逆行列 $\boldsymbol{A}_{B}^{-1}$ 全体を(Gauss の掃き出し法などで)計算するのは**極めて非効率**なので，実装上は積形式(product form)を用いる方法(e.g.[Danzig and Orchard-Hays, 1954](https://doi.org/10.2307/2001993))や LU分解を用いる方法(e.g.[Bartels and Colub, 1969](https://doi.org/10.1145/362946.362974))などが提案されている．具体的な実装方法などは [Ploskas and Samaras (2017)](https://doi.org/10.1007/978-3-319-65919-0_7)などを参照されたい．
Naïve computations of the basis inverse might request **a considerable computational burden** via straightforward Gaussian elimination. Several alternatives have been proposed, such as the Product Form methods (e.g.[Danzig and Orchard-Hays, 1954](https://doi.org/10.2307/2001993)) as well asl the LU Decomposition methods (e.g.[Bartels and Colub, 1969](https://doi.org/10.1145/362946.362974)). The readers are referred to [Ploskas and Samaras (2017)](https://doi.org/10.1007/978-3-319-65919-0_7) for more detailed implementations and their computational performance.
# 単体乗数と双対定理 | Simplex Multiplier and Duality Theorem
**改訂単体法**に登場する$\boldsymbol{\pi}^{\top} = \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1}$ は **単体乗数**(simplex multiplier)と呼ばれ，重要な役割を果たす．
In the revised simplex method, $\boldsymbol{\pi}^{\top} = \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1}$ is referred to as the **simplex multiplier** and plays an important role.
改訂単体法における基底解 $\boldsymbol{A}_{B}^{-1} \boldsymbol{b}$ の**最適性**は，
The **optimality conditions** of the basic solution $\boldsymbol{A}_{B}^{-1} \boldsymbol{b}$ in the revised simplex method are
- 基底解が許容である (the basic solution is feasible): $\boldsymbol{A}_{B}^{-1} \boldsymbol{b} \geq \boldsymbol{0}$
- 目的関数の係数 が非負である (the coefficients of the objective are non-negative): $\boldsymbol{c}_{N}^{\top} - \boldsymbol{\pi}^{\top} \boldsymbol{A}_{N} \geq \boldsymbol{0}$
であり，その時の**最適値**は$-z^{\ast}=-\boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1} \boldsymbol{b} = -\boldsymbol{\pi}^{\top} \boldsymbol{b}$であった．
and the corresponding **optimal value** is $-z^{\ast}=-\boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1} \boldsymbol{b} = -\boldsymbol{\pi}^{\top} \boldsymbol{b}$.
これより，**双対定理**の別証明を与えられる．
This gives an alternative proof of the **strong duality theorem**.
:::success
**双対定理 (Strong Dual Theorem)**
主問題が**最適解**を持つなら双対問題もまた最適解を持ち，その**最適値**は等しい．
If a primal problem has an optimal solution, its dual also has an optimal solution, and their optimal values are equivalent.
:::
以下では，等式標準形 (主問題) :
Suppose a standard equation form (as a primal problem)
$$
\begin{alignat}{4}
\displaystyle \min_{\boldsymbol{x}_{B}, \boldsymbol{x}_{N}} &
-&\boldsymbol{c}_{B}^{\top} \boldsymbol{x}_{B} &-&
\boldsymbol{c}_{N}^{\top} \boldsymbol{x}_{N} &=&-z\\
& -&\boldsymbol{A}_{B} \boldsymbol{x}_{B}&-&\boldsymbol{A}_{N} \boldsymbol{x}_{N} &=& -\boldsymbol{b} \\
&& \boldsymbol{x}_{B}&,& \boldsymbol{x}_{N} &\geq& \boldsymbol{0}
\end{alignat}
$$
とその双対問題
and its dual problem,
$$
\begin{alignat}{3}
\displaystyle \max_{\boldsymbol{y}} &-\boldsymbol{y}^{\top} \boldsymbol{b} &=& -z \\
&-\boldsymbol{y}^{\top} \boldsymbol{A}_{B} &\geq& -\boldsymbol{c}_{B}^{\top} \\
&-\boldsymbol{y}^{\top} \boldsymbol{A}_{N} &\geq& -\boldsymbol{c}_{N}^{\top}
\end{alignat}
$$
を考え，**主最適解**における**単体乗数**$\boldsymbol{\pi}$が，**双対最適解**となることを示そう．
and show that the **simplex multiplier** $\boldsymbol{\pi}$ at the primal optimal solution is the **dual optimal solution**.
まず，定義 $\boldsymbol{\pi}=\boldsymbol{c}_{B}^{\top}\boldsymbol{A}_{B}^{-1}$ および最適性条件 $\boldsymbol{c}_{N}^{\top} - \boldsymbol{\pi}^{\top} \boldsymbol{A}_{N} \geq \boldsymbol{0}$ より，
First, the definition $\boldsymbol{\pi}=\boldsymbol{c}_{B}^{\top}\boldsymbol{A}_{B}^{-1}$ and the optimality condition $\boldsymbol{c}_{N}^{\top} - \boldsymbol{\pi}^{\top} \boldsymbol{A}_{N} \geq \boldsymbol{0}$, the followings are met:
$$\begin{align}
-\boldsymbol{\pi}^{\top} \boldsymbol{A}_{B} &= - \boldsymbol{c}_{B}^{\top}\\
-\boldsymbol{\pi}^{\top} \boldsymbol{A}_{N} &\geq - \boldsymbol{c}_{N}^{\top}
\end{align}
$$
であるから，$\boldsymbol{\pi}$は**双対実行可能**. 次に，
This implies that $\boldsymbol{\pi}$ is **dual feasible**. Then, from the definition, it is obvious that
$$
-\boldsymbol{\pi}^{\top} \boldsymbol{b} = -\boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1} \boldsymbol{b} = -z^{\ast},
$$
すなわち，$\boldsymbol{\pi}$における**双対目的関数値**は**主最適値**に等しいから，**弱双対定理**より$\boldsymbol{\pi}$は**双対最適解**である．(証明終わり)．
That is, the **dual objective** at $\boldsymbol{\pi}$ is equivalent to the **primal optimal value** and thus $\boldsymbol{\pi}$ is **dual optimal** from the week duality theorem. Therefore, if a primal problem has an optimal solution, the dual has an optimal solution $\boldsymbol{\pi}$ and the both optimal values are equivalent to $-\boldsymbol{\pi}^{\top} \boldsymbol{b}$. (Q.E.D.)
# 感度解析 | Sensitivity Analyses
実際の分析では，与えられた問題の**最適解**を求めるだけでは不十分で，モデルの入力(目的関数の係数$\boldsymbol{c}$や制約条件の定数$\boldsymbol{b}$)が変化した場合に**最適解**や**最適値**がどの程度変化するかを調べる**感度分析**(sensitivity analyses)が求められることが多い．
In general, it is often not sufficient just to find the optimal solution for a given problem, but a **sensitivity analysis** is needed to examine how the optimal solution or optimal value are affected by some changes in the parameters of the model (e.g. coefficients $\boldsymbol{c}$ of the objective function and right-hand side constant $\boldsymbol{b}$).
パラメータ$\boldsymbol{c}$や$\boldsymbol{b}$の変化によって **最適基底**が変化しない場合，改訂単体法で求めた**基底行列**$\boldsymbol{A}_{B}$を用いることで，新たに問題を解き直すことなく**感度解析**が行なえる．
Such sensitivity analyses can be performed quite easy by using the **basis matrix** $\boldsymbol{A}_{B}$ if the **optimal basis** remains unchanged.
## 目的関数の係数$\boldsymbol{c}$ に対する感度 | Sensitivity w.r.t. Coefficient $\boldsymbol{c}$
目的関数の係数$\boldsymbol{c}$が$\boldsymbol{c} + \Delta \boldsymbol{c}$へと変化した場合，以下の**最適性**が満たされていれば，**最適基底**は変化せず，**最適解**もまた $\boldsymbol{x}^{\ast} = \left(\boldsymbol{x}_{B}^{\ast}\left|\boldsymbol{x}_{N}^{\ast}\right.\right) = \left(\left.\boldsymbol{A}_{B}^{-1}\boldsymbol{b}\right|\boldsymbol{0}\right)$のまま．
When the coefficient of the objective is changed from $\boldsymbol{c}$ to $\boldsymbol{c} + \Delta \boldsymbol{c}$, the **optimal basis** as well as the **optimal solution** $\boldsymbol{x}^{\ast} = \left(\boldsymbol{x}_{B}^{\ast}\left|\boldsymbol{x}_{N}^{\ast}\right.\right) = \left(\left.\boldsymbol{A}_{B}^{-1}\boldsymbol{b}\right|\boldsymbol{0}\right)$ remain unchanged if the following **optimality** is satisfied:
$$
\left(\boldsymbol{c}_{N} + \Delta \boldsymbol{c}_{N}\right)^{\top}
-\left(\boldsymbol{c}_{B} + \Delta \boldsymbol{c}_{B}\right)^{\top}
\boldsymbol{A}_{B}^{-1} \boldsymbol{A}_{N} \geq \boldsymbol{0}
$$
このとき**最適値**$z^{\ast}$の変化は，以下のように計算できる：
In this case, the change in the **optimal value** can be calculated as
$$
\begin{align}
\Delta z^{\ast} &= (\boldsymbol{c}+\Delta \boldsymbol{c})^{\top} \boldsymbol{x}^{\ast} - z^{\ast} \\
&= z^{\ast} + \Delta \boldsymbol{c}^{\top} \boldsymbol{x}^{\ast}- z^{\ast}\\
&= \Delta \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1} \boldsymbol{b}
\end{align}
$$
非基底変数についての係数の変化$\Delta \boldsymbol{c}_{N}$は最適値に影響しない点に注意されたい．
It is noteworthy that the changes in the coefficient of nonbasic variables $\Delta \boldsymbol{c}_{N}$ does not affect the optimal value.
## 右辺定数$\boldsymbol{b}$ に対する感度 | Sensitivity w.r.t. Constant $\boldsymbol{b}$
制約条件の右辺定数$\boldsymbol{b}$が$\boldsymbol{b} + \Delta \boldsymbol{b}$へと変化した場合，以下の**実行可能性**が満たされていれば，**最適基底**は変化しない．
When the constant is changed from $\boldsymbol{b}$ to $\boldsymbol{b} + \Delta \boldsymbol{b}$, the **optimal basis** remains unchanged if the following **feasibility** is satisfied:
$$
\boldsymbol{A}_{B}^{-1}(\boldsymbol{b} + \Delta \boldsymbol{b}) \geq \boldsymbol{0}
$$
このとき，**最適基底解**は
The **optimal basic solution** can be obtained as
$$
\hat{\boldsymbol{x}}_{B}^{\ast} = \boldsymbol{A}_{B}^{-1}(\boldsymbol{b} + \Delta \boldsymbol{b})
$$
となる．この新しい最適解 $\hat{\boldsymbol{x}}^{\ast} = \left(\left.\hat{\boldsymbol{x}}_{B}^{-1}\right|\boldsymbol{0}\right)$を目的関数に代入すれば，
Substituting this new optimal solution $\hat{\boldsymbol{x}}^{\ast} = \left(\left.\hat{\boldsymbol{x}}_{B}^{-1}\right|\boldsymbol{0}\right)$ to the objective function, the change in the objective value can be calculated as
$$
\begin{align}
\Delta z^{\ast} &= \boldsymbol{c}^{\top} \hat{\boldsymbol{x}}^{\ast} - z^{\ast} \\
&= \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1} (\boldsymbol{b} + \Delta \boldsymbol{b}) - \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1} \boldsymbol{b} \\
&= \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1} \Delta \boldsymbol{b} \\
&= \boldsymbol{\pi}^{\top} \Delta \boldsymbol{b}
\end{align}
$$
と求められる．ここで，$\boldsymbol{\pi}=\boldsymbol{c}_{B}^{\top}\boldsymbol{A}_{B}^{-1}$ は**最適基底**における**単体乗数**，すなわち，**双対最適解**である．
where $\boldsymbol{\pi}=\boldsymbol{c}_{B}^{\top}\boldsymbol{A}_{B}^{-1}$ is the **simplex multiplier** of the optimal basis, that is, the **dual optimal solution**.
Sign in with Wallet
Connect another wallet