---
lang: ja
tags: OptMech-2021, lecture
---
# 2021年度 知的システム<br>第8回：線形計画問題(7) 改訂単体法
[ポータルへ戻る](https://hackmd.io/@nagae/OptMech_2021)
<div style="text-align: center">

このページへは以下のQRコードまたはURLからアクセスできます：
<code style="font-size:20pt">https://hackmd.io/@nagae/OptMech_2021-Ch07</code>
</div>

# 改訂単体法とは
**単体法**の実装において**ピボット演算**によって**辞書**を更新することの問題点：
- **辞書**全体を計算し直すのは効率が悪い
- **非基底変数**の選択には**目的関数の行**しか使わない
- **基底変数**の選択には**非基底変数の列**と **(右辺)定数**の列しか使わない
- 反復が多くなると**計算誤差**が蓄積する

これらの欠点を補うのが**改訂単体法**．
- **基底変数**と**非基底変数**の分割に応じて，**等式標準形**の**等式制約**と**目的関数**を分割し，**連立方程式の解**として**辞書**を再定義する．
- 各反復で**辞書**を直接更新するのではなく**連立方程式の解**を特徴づける**基底行列**の**逆行列**(**基底逆行列**)を更新する．

前回までで解説した**単体法**の手続きを代数的に説明したものと位置付けることもできる．

# 等式標準形ふたたび
**標準最大化問題**に対する**等式標準形**は
- (**スラック変数**を含めた)==$N+M$次元== の非負の未知変数
- ==$M$本== の等式制約

で構成される．
$$
\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}
$$

# 基底変数と辞書
$N+M$次元の未知変数を$M$次元の**基底変数**(被説明変数) $\mathbf{x}_{B}$ と $N$次元の **非基底変数** (説明変数) $\mathbf{x}_{N}$ に分割する．

この時， **等式標準形** の **等式制約** および **目的関数** は
$$
\begin{align}
\mathbf{A}_{B} \mathbf{x}_{B} + \mathbf{A}_{N} \mathbf{x}_{N} &= \mathbf{b}\\
-\mathbf{c}_{B}^{\top} \mathbf{x}_{B} - \mathbf{c}_{N}^{\top} \mathbf{x}_{N} &= -z
\end{align}
$$
と表せる． ここで，
- $\mathbf{A}_{B} \in \mathcal{R}^{M\times M}$: **基底行列** (basis matrix)
- $\mathbf{A}_{N} \in \mathcal{R}^{M\times N}$: **非基底行列** (nonbasis matrix)
- $\mathbf{c}_{B} \in \mathcal{R}^{M}, \mathbf{c}_{N} \in \mathcal{R}^{N}$.

等式制約の分割：
$$
\mathbf{A}_{B} \mathbf{x}_B + \mathbf{A}_N \mathbf{x}_N = \mathbf{b}
$$
が与えられた時，**基底行列** $\mathbf{A}_{B}$が**逆行列**をもてば，**基底変数**$\mathbf{x}_B$を**非基底変数**$\mathbf{x}_{N}$で「説明」できる．
$$
-\mathbf{x}_{B} = - \mathbf{A}_{B}^{-1}\left(
\mathbf{b} - \mathbf{A}_{N} \mathbf{x}_{N}
\right) = - \mathbf{A}_{B}^{-1} \mathbf{b} + \mathbf{A}_{B}^{-1}\mathbf{A}_{N}\mathbf{x}_{N}$$
こうして得られた**基底変数**$\mathbf{x}_{B}$を目的関数に代入すれば，目的関数もまた**非基底変数**$\mathbf{x}_{N}$で「説明」できる．
$$
\begin{align}
-z &= -\mathbf{c}_{B}^{\top} \mathbf{x}_{B} - \mathbf{c}_{N}^{\top} \mathbf{x}_{N}\\
&= -\mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1}\left(\mathbf{b} - \mathbf{A}_{N} \mathbf{x}_{N}\right) - \mathbf{c}_{N}^{\top} \mathbf{x}_{N}\\
&= -\mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1}\mathbf{b}
-\left( \mathbf{c}_{N}^{\top} - \mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1}\mathbf{A}_{N} \right) \mathbf{x}_{N}
\end{align}
$$

以上を整理すると，**基底行列**$\mathbf{A}_{B}$が逆行列を持つならば，**基底変数**および**目的関数**を**非基底変数**$\mathbf{x}_{N}$で「説明」する**辞書**が得られる．
$$
\begin{align}
-\mathbf{x}_{B} &= \mathbf{A}_{B}^{-1} \mathbf{A}_{N} \mathbf{x}_{N} - \mathbf{A}_{B}^{-1} \mathbf{b}\\
&= \hat{\mathbf{A}} \mathbf{x}_{N} - \hat{\mathbf{b}}
\\
-z &=
-\left( \mathbf{c}_{N}^{\top} - \mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1}\mathbf{A}_{N} \right) \mathbf{x}_{N}
-\mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1}\mathbf{b}\\
&= -\hat{\mathbf{c}}^{\top} \mathbf{x}_{N} - \hat{\zeta}
\end{align}
$$
ここで，
$$
\begin{align}
\hat{\mathbf{A}} &=\mathbf{A}_{B}^{-1} \mathbf{A}_{N}, &
\hat{\mathbf{b}} &=\mathbf{A}_{B}^{-1} \mathbf{b}\\
-\hat{\mathbf{c}}^{\top} &= \mathbf{c}_{N}^{\top} - \mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1}\mathbf{A}_{N},&
\hat{\zeta} &= \mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1}\mathbf{b}
\end{align}
$$
は，**単体法**の手続きで改訂されてきた**辞書**の係数に他ならない．

$$
\begin{array}{c|c|c}
& \mathbf{x}_{N}^{\top} & -1 \\
\hline - \mathbf{x}_{B} & \hat{\mathbf{A}} & \hat{\mathbf{b}} \\
\hline
-z & -\hat{\mathbf{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}
$$

# リア充問題の例
等式標準形:
$$
\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}
$$

## 変数を$(\mathbf{x}_{B}| \mathbf{x}_{N})=(r_{1}, r_{2}, r_{3}|x_{1}, x_{2})$と分割した場合
等式制約 → **基底変数**を「説明」する辞書
$$\begin{gather}
\underbrace{
\begin{bmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{bmatrix}}_{\mathbf{A}_{B}}
\begin{bmatrix}
r_{1} \\ r_{2} \\ r_{3}
\end{bmatrix}
+\underbrace{\begin{bmatrix}
1 & 1\\
-2 & 1 \\
2 & 3
\end{bmatrix}}_{\mathbf{A}_{N}}
\begin{bmatrix}
x_{1} \\ x_{2}
\end{bmatrix}
=\begin{bmatrix}
8 \\ 2 \\ 18
\end{bmatrix}
\\
\Downarrow\text{($\mathbf{A}_{B}^{-1}$を左から乗じる)}
\\
-\begin{bmatrix}
r_{1} \\ r_{2} \\ r_{3}
\end{bmatrix}=
\underbrace{
\begin{bmatrix}
1 & 1\\
-2 & 1 \\
2 & 3
\end{bmatrix}
}_{\hat{\mathbf{A}}}
\begin{bmatrix}
x_{1} \\ x_{2}
\end{bmatrix}
-\underbrace{\begin{bmatrix}
8 \\ 2 \\ 18
\end{bmatrix}}_{\hat{\mathbf{b}}}
\end{gather}
$$

目的関数を「説明」する辞書
$$\begin{gather}
-z = \underbrace{\begin{bmatrix}
0 & 0 & 0
\end{bmatrix}}_{-\mathbf{c}_{B}^{\top}}
\begin{bmatrix}
r_{1} \\ r_{2} \\ r_{3}
\end{bmatrix} +
\underbrace{
\begin{bmatrix}
-1 & -2
\end{bmatrix}
}_{-\mathbf{c}_{N}^{\top}}
\begin{bmatrix}
x_{1} \\ x_{2}
\end{bmatrix}
\\
\Downarrow\ \text{($\mathbf{x}_{B}$を代入する)}
\\
-z = \underbrace{\begin{bmatrix}
-1 & -2
\end{bmatrix}
}_{-\hat{\mathbf{c}}^{\top}}
\begin{bmatrix}
x_{1} \\ x_{2}
\end{bmatrix}
-\underbrace{0}_{\hat{\zeta}}
\end{gather}
$$

## 変数を$(\mathbf{x}_{B}| \mathbf{x}_{N})=(r_{1}, x_{1}, r_{3}|r_{2}, x_{2})$と分割した場合
**基底変数**を「説明」する辞書
$$\begin{gather}
\underbrace{
\begin{bmatrix}
1 & \color{red}{1} & 0\\
0 & \color{red}{-2} & 0\\
0 & \color{red}{2} & 1
\end{bmatrix}}_{\mathbf{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}}_{\mathbf{A}_{N}}
\begin{bmatrix}
\color{blue}{r_{2}} \\ x_{2}
\end{bmatrix}
=\begin{bmatrix}
8 \\ 2 \\ 18
\end{bmatrix}
\\
\Downarrow\text{($\mathbf{A}_{B}^{-1}$を左から乗じる)}
\\
-\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{\mathbf{A}}}
\begin{bmatrix}
r_{2} \\ x_{2}
\end{bmatrix}
-\underbrace{\begin{bmatrix}
9 \\ -1 \\ 20
\end{bmatrix}}_{\hat{\mathbf{b}}}
\end{gather}
$$

目的関数を「説明」する辞書
$$\begin{gather}
-z = \underbrace{\begin{bmatrix}
0 & \color{red}{-1} & 0
\end{bmatrix}}_{-\mathbf{c}_{B}^{\top}}
\begin{bmatrix}
r_{1} \\ \color{red}{x_{1}} \\ r_{3}
\end{bmatrix} +
\underbrace{
\begin{bmatrix}
\color{blue}{0} & -2
\end{bmatrix}
}_{-\mathbf{c}_{N}^{\top}}
\begin{bmatrix}
\color{blue}{r_{2}} \\ x_{2}
\end{bmatrix}
\\
\Downarrow \text{($\mathbf{x}_{B}$を代入する)}
\\
-z = \underbrace{\begin{bmatrix}
-\frac{1}{2} & -\frac{5}{2}
\end{bmatrix}
}_{-\hat{\mathbf{c}}^{\top}}
\begin{bmatrix}
r_{2} \\ x_{2}
\end{bmatrix}
-\underbrace{1}_{\hat{\zeta}}
\end{gather}
$$

## 変数を$(\mathbf{x}_{B}| \mathbf{x}_{N})=(r_{1}, x_{2}, r_{3}|x_{1}, r_{2})$と分割した場合
**基底変数**を「説明」する辞書
$$\begin{gather}
\underbrace{
\begin{bmatrix}
1 & \color{red}{1} & 0\\
0 & \color{red}{1} & 0\\
0 & \color{red}{3} & 1
\end{bmatrix}}_{\mathbf{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}}_{\mathbf{A}_{N}}
\begin{bmatrix}
x_{1}\\\color{blue}{r_{2}}
\end{bmatrix}
=\begin{bmatrix}
8 \\ 2 \\ 18
\end{bmatrix}
\\
\Downarrow\text{($\mathbf{A}_{B}^{-1}$を左から乗じる)}
\\
-\begin{bmatrix}
r_{1} \\ x_{2} \\ r_{3}
\end{bmatrix}=
\underbrace{
\begin{bmatrix}
3 & -1\\
-2 & 1\\
8 & -3
\end{bmatrix}
}_{\hat{\mathbf{A}}}
\begin{bmatrix}
x_{1} \\ r_{2}
\end{bmatrix}
-\underbrace{\begin{bmatrix}
6 \\ 2 \\ 12
\end{bmatrix}}_{\hat{\mathbf{b}}}
\end{gather}
$$

目的関数を「説明」する辞書
$$\begin{gather}
-z = \underbrace{\begin{bmatrix}
0 & \color{red}{-2} & 0
\end{bmatrix}}_{-\mathbf{c}_{B}^{\top}}
\begin{bmatrix}
r_{1} \\ \color{red}{x_{2}} \\ r_{3}
\end{bmatrix} +
\underbrace{
\begin{bmatrix}
-1 & \color{blue}{0}
\end{bmatrix}
}_{-\mathbf{c}_{N}^{\top}}
\begin{bmatrix}
x_{1} \\ \color{blue}{r_{2}}
\end{bmatrix}
\\
\Downarrow \text{($\mathbf{x}_{B}$を代入する)}
\\
-z = \underbrace{\begin{bmatrix}
-5 & 2
\end{bmatrix}
}_{-\hat{\mathbf{c}}^{\top}}
\begin{bmatrix}
x_{1} \\ r_{2}
\end{bmatrix}
-\underbrace{(-4)}_{\hat{\zeta}}
\end{gather}
$$

# 基底解と最適性条件
**改訂単体法**の**辞書**:
$$
\begin{align}
-\mathbf{x}_{B} &= \mathbf{A}_{B}^{-1} \mathbf{A}_{N} \mathbf{x}_{N}
-\mathbf{A}_{B}^{-1} \mathbf{b} \\
-z &= \left(\mathbf{c}_{N}^{\top} - \mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1} \mathbf{A}_{N}\right) \mathbf{x}_{N} - \mathbf{c}_{B}^{\top}\mathbf{A}_{B}^{-1} \mathbf{b}
\end{align}
$$
に対する**基底解**は$(\mathbf{x}_{B} | \mathbf{x}_{N})= \left(\left.\mathbf{A}_{B}^{-1} \mathbf{b}\right|\mathbf{0}\right)$であり，
その**最適性**は目的関数の係数(**相対費用係数**と呼ばれる):
$$
-\hat{\mathbf{c}}^{\top} = \mathbf{c}_{N}^{\top} - \mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1}\mathbf{A}_{N}
$$
から判別できる:
- $-\hat{\mathbf{c}}\geq\mathbf{0}$ なら**基底解**が最適解
- $-\hat{\mathbf{c}}\not\geq\mathbf{0}$ なら$-\hat{c}_{j}<0$なる**非基底変数**$x_{N,j}$の値を0より大きくすることで，より小さな目的関数値が達成できる．

# 基底解の更新と有界性の判別
$\hat{c}_{j}<0$なる**非基底変数**$x_{N,j}$を0より大きくすることで，**基底解**は
$$
-\mathbf{x}_{B} = \hat{\mathbf{a}}_{j} x_{N, j} - \hat{\mathbf{b}}
$$
と変化する．ここで，
- $\hat{\mathbf{a}}_{j} = \mathbf{A}_{B}^{-1} \mathbf{a}_{N,j}$. ただし，$\mathbf{a}_{N,j}$は$\mathbf{A}_{N}$の$j$番目**列**ベクトル．
- $\hat{\mathbf{b}} = \mathbf{A}_{B}^{-1} \mathbf{b}$

はいずれも$M$次元列ベクトル．

いま，$\hat{\mathbf{a}}_{j}$および$\hat{\mathbf{b}}$ の$h$番目要素($h=1,\cdots,M$)を，それぞれ，$\hat{a}_{hj}$および$\hat{b}_{h}$と書く．
基底変数の**非負制約**($\mathbf{x}_{B} \geq \mathbf{0}$)を満足するためには，
$x_{N,j}$は
$$
\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}$と入れ替えることで，**基底**を改訂できる．

なお，任意の$h$について$\hat{a}_{hj}\leq 0$の場合，非負制約を満足しながら$x_{N,j}$をどこまでも増加させられる．すなわち，問題が**無界**であることが判別できる．

# 改訂単体法の手続き
結局のところ，**改訂単体法**とは**基底行列**$\mathbf{A}_{B}$およびその**逆行列**$\mathbf{A}_{B}^{-1}$を適切に改訂する方法である．その手続きは，以下のように整理できる：
1. **初期許容基底行列**$\mathbf{A}_{B}$を1つ選び，その**逆行列**$\mathbf{A}_{B}^{-1}$を計算する．
2. **基底解**$\hat{\mathbf{b}}=\mathbf{A}_{B}^{-1} \mathbf{b}$および**相対費用係数**$-\hat{\mathbf{c}}^{\top} = \mathbf{c}_{N}^{\top} - \mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1}\mathbf{A}_{N}$を計算し， ==$-\hat{c}_{k}$ (**目的関数の係数**)が負となる== **非基底変数** $k$ の中から任意の1つを選び，$j$とする． 全ての $k$ について $-\hat{c}_{k} \geq 0$ ならば, $\hat{\mathbf{b}}$が**最適解**で，**最適値**は$\hat{\zeta} = \mathbf{c}_{B}^{\top}\mathbf{A}_{B}^{-1} \mathbf{b}$.
3. $\hat{\mathbf{a}}_{j} = \mathbf{A}_{B}^{-1} \mathbf{a}_{N,j}$ を計算し，$\hat{a}_{hj} > 0$となる**基底変数** $x_{B,h}$ の中から ==$\hat{b}_{h}/\hat{a}_{hj}$が最小となる== (最初に0になる)ものを1つ選び $i$とする． 全ての$h$について$a_{hj}\leq0$ならば，その問題は**無界**である．
4. $(i,j)$を入れ替えた**基底行列**に対して**逆行列**$\mathbf{A}_{B}^{-1}$を改訂する．

## 基底逆行列$\mathbf{A}_{B}^{-1}$の更新方法
**改訂単体法**で**基底**が更新される度に$\mathbf{A}_{B}^{-1}$全体を(Gaussの掃き出し法などで)計算するのは極めて非効率．そのため，実装上は
- **積形式**(product form)を用いる方法
- **LU分解**を用いる方法

などが提案されている(本講義では詳しくは紹介しない)．

# 単体乗数と双対定理
**改訂単体法**に登場する$\mathbf{\pi}^{\top} = \mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1}$ は **単体乗数**(simplex multiplier)と呼ばれる．

**改訂単体法**における**基底解** $\mathbf{A}_{B}^{-1} \mathbf{b}$ の最適性は，
- **基底解** が許容である: $\mathbf{A}_{B}^{-1} \mathbf{b} \geq \mathbf{0}$
- **相対費用係数** が非負である: $\mathbf{c}_{N}^{\top} - \mathbf{\pi}^{\top} \mathbf{A}_{N} \geq \mathbf{0}$

であり，その時の**最適値**は$-z^{\ast}=-\mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1} \mathbf{b} = -\mathbf{\pi}^{\top} \mathbf{b}$であった． これより，**双対定理**の別証明を与えられる．

以下では，**等式標準形**:
$$
\begin{alignat}{4}
\displaystyle \min_{\mathbf{x}_{B}, \mathbf{x}_{N}} &
-&\mathbf{c}_{B}^{\top} \mathbf{x}_{B} &-&
\mathbf{c}_{N}^{\top} \mathbf{x}_{N} &=&-z\\
& -&\mathbf{A} \mathbf{x}_{B}&-&\mathbf{A}_{N} \mathbf{x}_{N} &=& -\mathbf{b} \\
&& \mathbf{x}_{B}&,& \mathbf{x}_{N} &\geq& \mathbf{0}
\end{alignat}
$$
とその**双対問題**
$$
\begin{alignat}{3}
\displaystyle \max_{\mathbf{y}} &-\mathbf{y}^{\top} \mathbf{b} &=& -z \\
&-\mathbf{y}^{\top} \mathbf{A}_{B} &\geq& -\mathbf{c}_{B}^{\top} \\
&-\mathbf{y}^{\top} \mathbf{A}_{N} &\geq& -\mathbf{c}_{N}^{\top}
\end{alignat}
$$
を考え，**等式標準形**の**最適解**における**単体乗数**$\mathbf{\pi}$が，**双対最適解**となることを示そう．

まず，$\mathbf{\pi}$の定義($\mathbf{\pi}=\mathbf{c}_{B}^{\top}\mathbf{A}_{B}^{-1}$)および**最適性条件**($\mathbf{c}_{N}^{\top} - \mathbf{\pi}^{\top} \mathbf{A}_{N} \geq \mathbf{0}$)より，
$$\begin{align}
-\mathbf{\pi}^{\top} \mathbf{A}_{B} &= - \mathbf{c}_{B}^{\top}\\
-\mathbf{\pi}^{\top} \mathbf{A}_{N} &\geq - \mathbf{c}_{N}^{\top}
\end{align}
$$
であるから，$\mathbf{\pi}$は**双対実行可能**. さらに，
$$
-\boldsymbol{\pi}^{\top} \mathbf{b} = -\mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1} \mathbf{b} = -z^{\ast},
$$
すなわち，$\boldsymbol{\pi}$における**双対目的関数値**は**最適値**に等しいから，**弱双対定理**より$\boldsymbol{\pi}$は**双対最適解**である．
従って，**主問題**が**最適解**を持つなら**双対問題**もまた**最適解**を持ち，その**最適値**は等しい．

# 感度解析
実際の分析では，与えられた問題の**最適解**を求めるだけでは不十分で，モデルの入力(目的関数の係数$\mathbf{c}$や制約条件の定数$\mathbf{b}$)が変化した場合に**最適解**や**最適値**がどの程度変化するかを調べる**感度分析**(sensitivity analyses)が求められることが多い．このとき，パラメータ$\mathbf{c}$や$\mathbf{b}$の変化によって **基底**が変化しない場合，**改訂単体法**で求めた**基底行列**$\mathbf{A}_{B}$を用いることで，新たに問題を解き直すことなく**感度解析**が行なえる．

## 目的関数の係数$\mathbf{c}$が変化した場合
目的関数の係数$\mathbf{c}$が$\mathbf{c} + \Delta \mathbf{c}$へと変化した場合，**最適性**
$$
\left(\mathbf{c}_{N} + \Delta \mathbf{c}_{N}\right)^{\top}
-\left(\mathbf{c}_{B} + \Delta \mathbf{c}_{B}\right)^{\top}
\mathbf{A}_{B}^{-1} \mathbf{A}_{N} \geq \mathbf{0}
$$
が満たされていれば，**最適基底**は変化しない．このとき，**最適解**は $\mathbf{x}^{\ast} = \left(\mathbf{x}_{B}^{\ast}\left|\mathbf{x}_{N}^{\ast}\right.\right) = \left(\left.\mathbf{A}_{B}^{-1}\mathbf{b}\right|\mathbf{0}\right)$のままなので，**最適値**$z^{\ast}$の変化は，
$$
\begin{align}
\Delta z^{\ast} &= (\mathbf{c}+\Delta \mathbf{c})^{\top} \mathbf{x}^{\ast} - z^{\ast} \\
&= z^{\ast} + \Delta \mathbf{c}^{\top} \mathbf{x}^{\ast}- z^{\ast}\\
&= \Delta \mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1} \mathbf{b}
\end{align}
$$
と計算できる．なお，**非基底変数**についての係数の変化$\Delta \mathbf{c}_{N}$は**最適値**に影響しない点に注意されたい．

## 右辺定数$\mathbf{b}$が変化した場合
制約条件の右辺定数$\mathbf{b}$が$\mathbf{b} + \Delta \mathbf{b}$へと変化した場合，**許容性**:
$$
\mathbf{A}_{B}^{-1}(\mathbf{b} + \Delta \mathbf{b}) \geq \mathbf{0}
$$
が満たされていれば，**最適基底**は変化しない．このとき，**最適基底解**は
$$
\hat{\mathbf{x}}_{B}^{\ast} = \mathbf{A}_{B}^{-1}(\mathbf{b} + \Delta \mathbf{b})
$$
となる．この新しい最適解$\hat{\mathbf{x}}^{\ast} = \left(\left.\hat{\mathbf{x}}_{B}^{-1}\right|\mathbf{0}\right)$を目的関数に代入すれば，
$$
\begin{align}
\Delta z^{\ast} &= \mathbf{c}^{\top} \hat{\mathbf{x}}^{\ast} - z^{\ast} \\
&= \mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1} (\mathbf{b} + \Delta \mathbf{b}) - \mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1} \mathbf{b} \\
&= \mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1} \Delta \mathbf{b} \\
&= \boldsymbol{\pi}^{\top} \Delta \mathbf{b}
\end{align}
$$
と求められる．ここで，$\mathbf{\pi}$は**最適基底**における**単体乗数**，すなわち，**双対最適解**であることに注意されたい．