---
lang: ja
tags: OptMech-2021, lecture
---
# 2021年度 知的システム<br>第5回：線形計画問題(4) 辞書とピボット演算
[ポータルへ戻る](https://hackmd.io/@nagae/OptMech_2021)
<div style="text-align: center">

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

# 不等式標準形から等式標準形へ
$\mathbf{A} \in \mathcal{R}^{M\times{}N}, \mathbf{c} \in \mathcal{R}^{N}, \mathbf{b} \in \mathcal{R}^{M}$ を与件とした ==**標準最小化問題**==:
$$
\min_{\mathbf{y}} \left\{\left.\mathbf{y}^{\top} \mathbf{b}
\right|
\mathbf{y}^{\top} \mathbf{A} \geq \mathbf{c}^{\top}, \mathbf{y} \geq \mathbf{0}\right\}
$$
の不等式制約を ==**等式制約**== に置き換えてみよう．これは，$N$次元の人工的な変数として ==**スラック変数**== (slack variable) $\mathbf{s} = (s_{1}, \cdots, s_{N})$ を導入し，不等式制約:
$$
\mathbf{y}^{\top} \mathbf{A} \geq \mathbf{c}^{\top}
$$
を，等式制約:
$$
\mathbf{y}^{\top} \mathbf{A} - \mathbf{s}^{\top} = \mathbf{c}^{\top}
$$
に置き換えた問題:
$$
\min_{\mathbf{y}, \color{red}{\mathbf{s}}}
\left\{\left.\mathbf{y}^{\top} \mathbf{b}
\right|
\mathbf{y}^{\top} \mathbf{A} \color{red}{- \mathbf{s}^{\top} =} \mathbf{c}^{\top}, \mathbf{y} \geq \mathbf{0}, \color{red}{\mathbf{s}\geq \mathbf{0}}\right\}
$$
を， ==**等式標準形**== と呼ぶ．

同様に，==**標準最大化問題**== :
$$
\max_{\mathbf{x}}
\left\{\left.\mathbf{c}^{\top}\mathbf{x}
\right|
\mathbf{A} \mathbf{x} \leq \mathbf{b}
, \mathbf{x} \geq \mathbf{0}\right\}
$$
に対しても，目的関数の係数に $-1$ を乗じて最小化問題とした後，==**スラック変数**== $\mathbf{r} = (r_{1}, \cdots, r_{M})$ を導入して不等式制約$\mathbf{A}\mathbf{x} \leq \mathbf{b}$を等式制約$\mathbf{A} \mathbf{x} + \mathbf{r} = \mathbf{b}$に置き換えれば，==**等式標準形**== が得られる:
$$
\min_{\mathbf{x}, \color{red}{\mathbf{r}}}
\left\{\left.-\mathbf{c}^{\top}\mathbf{x}
\right|
\mathbf{A} \mathbf{x} \color{red}{+ \mathbf{r} =} \mathbf{b}
, \mathbf{x} \geq \mathbf{0},
\color{red}{\mathbf{r}\geq\mathbf{0}}\right\}
$$

# リア充問題(主問題・双対問題)を等式標準形で表してみる
## 双対問題(上限推定問題)
### もとの問題
$$
\begin{alignat}{8}
\displaystyle
\min_{y_{1}, y_{2}, y_{3}}\quad & &8 y_{1} &+& 2 y_{2} &+& 18y_{3} &=&z\\
\text{s.t.} && y_{1} &-&2y_{2}&+&2y_{3}&\geq&1\\
&& y_{1} &+& y_{2} &+& 3 y_{3} &\geq& 2\\
&& y_{1}&,& y_{2}&,& y_{3} &\geq& 0
\end{alignat}
$$
### 等式標準形
$$
\begin{alignat}{8}
\displaystyle
\min_{y_{1}, y_{2}, y_{3}\color{red}{, s_{1}, s_{2}}} \quad& &8 y_{1} &+& 2 y_{2} &+& 18y_{3} && && &=&z\\
\text{s.t.} \quad && y_{1} &-&2y_{2}&+&2y_{3}&\color{red}{-}&\color{red}{s_{1}} &&&=&1\\
&& y_{1} &+& y_{2} &+& 3 y_{3} && &\color{red}{-} & \color{red}{s_{2}} &=& 2\\
&& y_{1}&,& y_{2}&,& y_{3} &,& \color{red}{s_{1}} &,& \color{red}{s_{2}} &\geq& 0
\end{alignat}
$$

## 主問題(リア充最大化問題)
### もとの問題
\begin{alignat}{3}
\displaystyle \max_{x_{1}, x_{2}} \quad &
& x_{1} &+& 2x_{2} &=&z\\
\text{s.t.} \quad
&&x_{1} &+& x_{2} &\leq& 8 \\
&-& 2x_{1}&+& x_{2} &\leq& 2 \\
&& 2x_{1}&+&3x_{2} &\leq& 18 \\
&& x_{1}&,&x_{2}&\geq& 0
\end{alignat}

### 等式標準形
\begin{alignat}{6}
\color{red}{\displaystyle \min_{\color{black}{x_{1}, x_{2}}, r_{1}, r_{2}, r_{3}}} \quad &
\color{red}{-}& x_{1} &\color{red}{-}& 2x_{2} && && && &=&\color{red}{-}z\\
\text{s.t.} \quad
&&x_{1} &+& x_{2} &\color{red}{+} & \color{red}{r_{1}} && && &=& 8 \\
&-& 2x_{1}&+& x_{2} &&& \color{red}{+}&\color{red}{r_{2}} && &=& 2 \\
&& 2x_{1}&+&3x_{2} &&&&& \color{red}{+}&\color{red}{r_{3}} &=& 18 \\
&& x_{1}&,&x_{2} &\color{red},& \color{red}{r_{1}}&\color{red}, &\color{red}{r_{2}}&\color{red},&\color{red}{r_{3}}&\geq& 0
\end{alignat}

# 標準最小化問題に対する辞書
==**標準最小化問題**== の ==**等式標準形**== に対して，目的関数:
$$
z = \mathbf{y}^{\top} \mathbf{b}
$$
と等式制約:
$$
\mathbf{s}^{\top} = \mathbf{y}^{\top} \mathbf{A} - \mathbf{c}^{\top}
$$
を合わせた **方程式系**
$$
\begin{bmatrix}
\mathbf{s}^{\top} & z
\end{bmatrix} =
\begin{bmatrix}
\mathbf{y}^{\top} & 1
\end{bmatrix}
\begin{bmatrix}
\mathbf{A} & \mathbf{b} \\
-\mathbf{c}^{\top} & 0
\end{bmatrix}
$$
を， 変数$\mathbf{s}$ に対する ==**辞書**== (disctionary) と呼ぶ.
:::info
**辞書** の由来は，==**説明変数**== $\mathbf{y}$ を1つ選ぶと，それに **従属** して目的関数値と ==**被説明変数**== $\mathbf{s}$ が説明される(飜訳される)ことから．
:::

==**説明変数**== $\mathbf{y}, 1$ を行, ==**被説明変数**== $\mathbf{s}, z$を列に配置した行列で ==**辞書**== の係数を表現すると便利である.
$$
\begin{array}{c|cccc|c}
& s_{1} & s_{2} & \cdots & s_{N} & z\\
\hline
y_{1} & a_{11} & a_{12} & \cdots & a_{1N} & b_{1}\\
y_{2} & a_{21} & a_{22} & \cdots & a_{2N} & b_{2} \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
y_{M} & a_{M1} & a_{M2} & \cdots & a_{MN} & b_{M}\\
\hline
1 & -c_{1} & -c_{2} & \cdots & -c_{N} & 0
\end{array}
\quad
\Leftrightarrow \quad
\begin{array}{c|c|c}
& \mathbf{s}^{\top} & z \\
\hline
\mathbf{y} & \mathbf{A} & \mathbf{b} \\
\hline
1 & -\mathbf{c}^{\top} & 0
\end{array}
$$

# 標準最大化問題に対する辞書
==**標準最大化問題**== の ==**等式標準形**== に対しても，(もとの問題の)目的関数と等式制約:
$$
\begin{align}
-\mathbf{r} &= \mathbf{A} \mathbf{x} - \mathbf{b} \\
-z &= -\mathbf{c}^{\top} \mathbf{x} - 0
\end{align}
$$
から,スラック変数 $\mathbf{r}$ に対する ==**辞書**== が得られる:
$$
\begin{bmatrix}
-\mathbf{r} \\ - z
\end{bmatrix} =
\begin{bmatrix}
\mathbf{A} & \mathbf{b}
\\
-\mathbf{c}^{\top} & 0
\end{bmatrix}
\begin{bmatrix}
\mathbf{x} \\ -1
\end{bmatrix}
$$

この辞書に対して，==**説明変数**== $\mathbf{x}, 1$を列， ==**被説明変数**== $-\mathbf{r}, -z$ を行に配置した行列で係数を表示すると， ==**標準最小化問題**== の等式標準形とほぼ同じ形の行列表現が得られる．
$$
\begin{array}{c|cccc|c}
& x_{1} & x_{2} & \cdots & x_{N} & -1\\
\hline
-r_{1} & a_{11} & a_{12} & \cdots & a_{1N} & b_{1}\\
-r_{2} & a_{21} & a_{22} & \cdots & a_{2N} & b_{2} \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
-r_{M} & a_{M1} & a_{M2} & \cdots & a_{MN} & b_{M}\\
\hline
-z & -c_{1} & -c_{2} & \cdots & -c_{N} & 0
\end{array}
\quad
\Leftrightarrow \quad
\begin{array}{c|c|c}
& \mathbf{x}^{\top} & -1 \\
\hline
-\mathbf{r} & \mathbf{A} & \mathbf{b} \\
\hline
-z & -\mathbf{c}^{\top} & 0
\end{array}
$$

# 辞書の例
## リア充度上限推定問題(標準最小化問題)
### 等式標準形
$$
\begin{alignat}{8}
\displaystyle
\min_{y_{1}, y_{2}, y_{3}} \quad& &8 y_{1} &+& 2 y_{2} &+& 18y_{3} && && &=&z\\
\text{s.t.} \quad && y_{1} &-&2y_{2}&+&2y_{3}&-&s_{1} &&&=&1\\
&& y_{1} &+& y_{2} &+& 3 y_{3} && &- & s_{2} &=& 2\\
&& y_{1}&,& y_{2}&,& y_{3} &,& s_{1} &,& s_{2} &\geq& 0
\end{alignat}
$$
### 対応する辞書
$$
\begin{array}{rrrrr}
s_{1} =& y_{1}&-2y_{2}&+2y_{3}&-1\\
s_{2} =& y_{1}&+y_{2}&+3y_{3}&-2\\
\hline
z =& 8 y_{1}&+2y_{2}&+18y_{3}&+0
\end{array}
\quad \Leftrightarrow \quad
\begin{array}{c|cc|c}
& s_{1} & s_{2} & z \\
\hline
y_{1} & 1 & 1 & 8\\
y_{2} & -2 & 1 & 2 \\
y_{3} & 2 & 3 & 18\\
\hline
1 & -1 & -2 & 0
\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}
$$

## 対応する辞書
$$
\begin{array}{rrrr}
-r_{1}=& x_{1}&+x_{2}&-8\\
-r_{2}=&-2x_{1}&+x_{2}&-2\\
-r_{3}=& 2x_{1}&+3x_{2}&-18\\
\hline
-z=&-x_{1}&-2x_{2}&-0
\end{array}\quad \Leftrightarrow\quad
\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{v} = (r_{1}, r_{2}, r_{3})$
- **説明変数**: $\mathbf{u} = (x_{1}, x_{2})$

なので，以下のように表示できる：
$$
\begin{array}{rrrr}
-r_{1}=& x_{1}&+x_{2}&-8\\
-r_{2}=&-2x_{1}&+x_{2}&-2\\
-r_{3}=& 2x_{1}&+3x_{2}&-18\\
\hline
-z=&-x_{1}&-2x_{2}&-0
\end{array}\quad \Leftrightarrow\quad
\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}
$$

ここで，**被説明変数**$r_{2}$と**説明変数**$x_{2}$を入れ替えてみよう．$r_{2}$についての式を$x_{2}$について解けば，
$$
-x_{2} = -2x_{1}+r_{2}-2
$$
を得る．これを残りの3つの式に代入して整理すれば，
$$
\begin{align}
-r_{1} &= x_{1} + (2 x_{1}-r_{2}+2)-8
\\&= 3 x_{1} - r_{2} - 6\\
-r_{3} &= 2x_{1} + 3(2x_{1}-r_{2}+2)-18
\\&= 8x_{1} - 3r_{2} -12\\
-z &= -x_{1}-2(2x_{1}-r_{2}+2)-0
\\&= -5x_{1} + 2r_{2} - 4
\end{align}
$$
が得られる．これにより，$r_{2}$と$x_{2}$を入れ替え，
- 被説明変数: $\hat{\mathbf{u}} = (r_{1}, \color{red}{x_{2}}, r_{3})$
- 説明変数:$\hat{\mathbf{v}}=(x_{1}, \color{red}{r_{2}})$

とした新たな辞書を構築できる．
$$
\begin{array}{rrrr}
-r_{1}=& 3x_{1}&-\color{red}{r_{2}}&-6\\
-\color{red}{x_{2}}=&-2x_{1}&+\color{red}{r_{2}}&-2\\
-r_{3}=& 8x_{1}&-3\color{red}{r_{2}}&-12\\
\hline
-z=&-5x_{1}&+2\color{red}{r_{2}}&-4
\end{array}\quad \Leftrightarrow\quad
\begin{array}{c|cc|c}
& x_{1} & \color{red}{r_{2}} & -1\\
\hline
-r_{1} & 3 & -1 & 6\\
-\color{red}{x_{2}} & -2 & 1 & 2 \\
-r_{3} & 8 & -3 & 12\\
\hline
-z & -5 & 2 & 4
\end{array}
$$

こうして作られた辞書に対応した**等式標準形**の線形計画問題:
$$
\begin{alignat}{7}
\displaystyle \min_{x_{1}, r_{2}, r_{1}, x_{2}, r_{3}} \quad &
-& 5x_{1} &+& 2r_{2} && && && &=&-z+4\\
\text{s.t.} \quad
&&3x_{1} &-& r_{2} &+ & r_{1} && && &=& 6 \\
&-& 2x_{1}&+& r_{2} &&& +&x_{2} && &=& 2 \\
&& 8x_{1}&-&3 r_{2} &&&&& +&r_{3} &=& 12 \\
&& x_{1}&,&r_{2} &,& r_{1}&, &x_{2}&,&r_{3}&\geq& 0
\end{alignat}
$$
は，==もとのリア充度最大化問題と **等価である**== ことに注意されたい． すなわち
- 新しい問題の**最適解** $(x_{1}^{\ast}, r_{2}^{\ast}, r_{1}^{\ast}, x_{2}^{\ast}, r_{3}^{\ast})$ は，もとのリア充問題の**最適解**に等しい．
- 上述の問題の **最適値** $z^{\ast} = 5 x_{1}^{\ast} - 2 r_{2}^{\ast} + 4$ は，もとのリア充問題の**最適値** $z^{\ast} = x_{1}^{\ast} + 2 x_{2}^{\ast}$ に等しい．

# 標準最大化問題に対するピボット演算
## 被説明変数/説明変数の入れ替え
上述の被説明変数/説明変数の入れ替えをシステマティックに表現してみよう．
**標準最大化問題**に対して，$M$次元の**被説明変数**$\mathbf{v} = (v_{1}, \cdots, v_{M})$と$N$次元の**説明変数**$\mathbf{u} = (u_{1}, \cdots, u_{N})$ からなる**辞書**:
$$
\begin{array}{rrcrcrr}
-v_{1} =& a_{11}u_{1}&+\cdots&+a_{1j}u_{j}&+\cdots&+a_{1N} u_{N}&-b_{1}\\
\vdots & \vdots & & \vdots && \vdots & \vdots\\
-v_{i} =& a_{i1}u_{1}&+\cdots&+a_{ij}u_{j}&+\cdots&+a_{iN} u_{N}&-b_{i}\\
\vdots & \vdots & & \vdots && \vdots & \vdots\\
-v_{M} =& a_{M1}u_{1}&+\cdots&+a_{Mj}u_{j}&+\cdots&+a_{MN} u_{N}&-b_{M}\\
\hline
-z=&
-c_{1} u_{1}&-\cdots& -c_{j}u_{j} &-\cdots& -c_{N} u_{N} &-\zeta
\end{array}
$$
が与えられたとする．

ここで，**被説明変数**$v_{i}$と**説明変数**$u_{j}$を入れ替えよう．ただし, $a_{ij}\ne 0$とする．この入れ替えに対応した新たな辞書は，以下のように求められる．
まず，$v_{i}$の式を$u_{j}$について解けば，
$$
\begin{align}
-u_{j} &= \frac{1}{a_{ij}}\left(a_{i1}u_{1} + \cdots + v_{i} + \cdots + a_{iN} u_{N} - b_{i}\right)\\
&= \tfrac{a_{i1}}{a_{ij}} u_{1} + \cdots + \tfrac{1}{a_{ij}} v_{i} + \cdots + \tfrac{a_{iN}}{a_{ij}} u_{N} - \tfrac{b_{i}}{a_{ij}}\\
&= \hat{a}_{i1} u_{1} + \cdots \hat{a}_{ij} v_{i} + \cdots + \hat{a}_{iN} u_{N} - \hat{b}_{i}
\end{align}
$$
ただし，
$$
\begin{align}
\hat{a}_{ih} &= \frac{a_{ih}}{a_{ij}} (h \ne j),
&
\hat{a}_{ij} &= \frac{1}{a_{ij}}
&
\hat{b}_{i} = \frac{b_{i}}{a_{ij}}
\end{align}
$$
である．

これを残りの方程式に代入すれば，新しい**被説明変数** $\hat{\mathbf{v}} = (v_{1}, \cdots, \color{red}{u_{j}}, \cdots, v_{M})$と**説明変数** $\hat{\mathbf{u}}=(u_{1}, \cdots, \color{red}{v_{i}}, \cdots, u_{N})$ に対する辞書が得られる．
この新しい辞書の任意の$v_{k} (k\ne i)$ についての式は，
$$
\begin{align}
-v_{k} &= a_{k1} u_{1} + \cdots - \frac{a_{kj}}{a_{ij}}(a_{i1}u_{1} + \cdots + v_{i} + a_{iN} u_{N} - b_{i}) \\
& \qquad + \cdots + a_{kN} u_{N} - b_{k}\\
&= \left(a_{k1}-\frac{a_{i1}a_{kj}}{a_{ij}}\right) u_{1}
+\cdots - \frac{a_{kj}}{a_{ij}} v_{i}\\
&\qquad +\cdots + \left(a_{kN}-\frac{a_{iN}a_{kj}}{a_{ij}}\right)u_{N}
-\left(b_{k} - \frac{b_{i}a_{kj}}{a_{ij}}\right)
\\
&= \hat{a}_{k1} u_{1} + \cdots + \hat{a}_{kj} v_{i} + \cdots + \hat{a}_{kN} u_{N} - \hat{b}_{k}
\end{align}
$$
と整理できる．ただし，
$$
\begin{align}
\hat{a}_{kh} &= a_{kh} - \frac{a_{ih}a_{kj}}{a_{ij}} \, (h\ne j), &
\hat{a}_{kj} &= -\frac{a_{kj}}{a_{ij}} ,&
\hat{b}_{k} &= b_{k} - \frac{b_{i}a_{kj}}{a_{ij}}
\end{align}
$$
である．

同じように，目的関数$-z$についての式は，
$$
\begin{align}
-z &= - c_{1} u_{1} - \cdots + \frac{c_{j}}{a_{ij}}\left(a_{i1}u_{1} + \cdots + v_{i} + \cdots + a_{iN} u_{N} - b_{i}\right)\\
&\qquad - \cdots - c_{N} u_{N} - \zeta
\\
&= - \left(c_{1}-\frac{a_{i1}c_{j}}{a_{ij}}\right) u_{1}
-\cdots - \frac{-c_{j}}{a_{ij}} v_{i}\\
&\qquad -\cdots - \left(c_{N}-\frac{a_{iN}c_{j}}{a_{ij}}\right)u_{N}
-\left(\zeta - \frac{b_{i}c_{j}}{a_{ij}}\right)
\\
&= - \hat{c}_{1} u_{1} - \cdots - \hat{c}_{j} v_{i} - \cdots - \hat{c}_{N} u_{N} - \hat{\zeta}
\end{align}
$$
と整理できる．ただし，
$$
\begin{align}
\hat{c}_{h} &= c_{h} - \frac{a_{ih} c_{j}}{a_{ij}} \, (h\ne j), &
\hat{c}_{j} &= -\frac{c_{j}}{a_{ij}}, &
\hat{\zeta} &= \zeta + \frac{b_{i} c_{j}}{a_{ij}}
\end{align}
$$
である．

## ピボット演算
**被説明変数**$v_{i}$と**説明変数**$u_{j}$の入れ替えに対応した新たな**辞書**:
$$
\begin{cases}
-\mathbf{v} &= \mathbf{A}\mathbf{u} - \mathbf{b} \\
-z & -\mathbf{c}^{\top} \mathbf{u} - \zeta
\end{cases}
\Rightarrow
\begin{cases}
-\hat{\mathbf{v}} &= \hat{\mathbf{A}}\hat{\mathbf{u}} - \hat{\mathbf{b}} \\
-z & -\hat{\mathbf{c}}^{\top} \hat{\mathbf{u}} - \hat{\zeta}
\end{cases}
$$
を求める手続きは，==**ピボット演算**==(pivoting, pivot operation)と呼ばれ，以下の表形式で表せる:
$$
\begin{gather}
\begin{array}{c|ccccc|c}
& u_{1} & \cdots & \color{red}{u_{j}} & \cdots & u_{N} & -1 \\
\hline
-v_{1} & a_{11} & \cdots & a_{1j} & \cdots & a_{1N} & b_{1} \\
\vdots & \vdots & & \vdots & & \vdots & \vdots\\
\color{red}{-v_{i}} & a_{i1} & \cdots & \color{red}{a_{ij}^{\ast}} & \cdots & a_{iN} & b_{i} \\
\vdots & \vdots & & \vdots & & \vdots & \vdots\\
-v_{M} & a_{M1} & \cdots & a_{Mj} & \cdots & a_{MN} & b_{M} \\
\hline
-z & -c_{1} & \cdots & -c_{j} & \cdots &- c_{N} & \zeta
\end{array}
\\
\Downarrow
\\
\begin{array}{c|ccccc|c}
& u_{1} & \cdots & \color{red}{v_{i}} & \cdots & u_{N} & -1 \\
\hline
-v_{1} & \hat{a}_{11} & \cdots & \hat{a}_{1j} & \cdots & \hat{a}_{1N} & \hat{b}_{1} \\
\vdots & \vdots & & \vdots & & \vdots & \vdots\\
\color{red}{-u_{j}} & \hat{a}_{i1} & \cdots & \color{red}{\hat{a}_{ij}^{\ast}} & \cdots & \hat{a}_{iN} & \hat{b}_{i} \\
\vdots & \vdots & & \vdots & & \vdots & \vdots\\
-v_{M} & \hat{a}_{M1} & \cdots & \hat{a}_{Mj} & \cdots & \hat{a}_{MN} & \hat{b}_{M} \\
\hline
-z & -\hat{c}_{1} & \cdots & -\hat{c}_{j} & \cdots &- \hat{c}_{N} & \hat{\zeta}
\end{array}
\end{gather}
$$

行列$\mathbf{A}$の$(i,j)$要素を ==**ピボット**==(pivot)と呼び，アスタリスク($\ast$)をつけて表す． ピボット演算の規則は一見複雑そうだが，行列の各要素を
- ピボット($p$)
- ピボットと同じ行($r$)
- ピボットと同じ列($c$)
- それ以外($q$)

に分ければ，以下のようにスッキリと記述できる:
$$
\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}
}
$$

# ピボット演算の例：リア充問題
**説明変数** $x_{2}$ と**被説明変数** $r_{2}$ を入れ替える．
$$
\begin{align}
\begin{array}{c|cc|c}
& x_{1} & \color{red}{x_{2}} & -1\\
\hline
-r_{1}& 1 & 1 & 8\\
\color{red}{-r_{2}} & -2& \color{red}{1^{\ast}} & 2\\
-r_{3}& 2 & 3 & 18\\
\hline
-z & -1 & -2& 0
\end{array}
&\Rightarrow
\begin{array}{c|cc|c}
& x_{1} & \color{red}{x_{2}} & -1\\
\hline
-r_{1}& 1-\frac{(-2)\times 1}{1} & -\frac{1}{1} & 8-\frac{2\times 1}{1}\\
\color{red}{-r_{2}} & \frac{-2}{1}& \frac{1}{1} & \frac{2}{1}\\
-r_{3}& 2-\frac{(-2)\times 3}{1} & -\frac{3}{1} & 18-\frac{2\times 3}{1}\\
\hline
-z & -1 - \frac{(-2)\times(-2)}{1}& -\frac{(-2)}{1}& 0-\frac{2\times(-2)}{1}
\end{array}
\\
&\Rightarrow
\begin{array}{c|cc|c}
& x_{1} & \color{red}{r_{2}} & -1\\
\hline
-r_{1}& 3 & -1 & 6\\
\color{red}{-x_{2}} & -2& 1 & 2\\
-r_{3}& 8 & -3 & 12\\
\hline
-z & -5 & 2& 4
\end{array}
\end{align}
$$

さらに，**説明変数** $x_{1}$ と**被説明変数** $r_{3}$ を入れ替える．
$$
\begin{align}
\begin{array}{c|cc|c}
& \color{red}{x_{1}} & r_{2} & -1\\
\hline
-r_{1}& 3 & -1 & 6\\
-x_{2} & -2& 1 & 2\\
\color{red}{-r_{3}}& \color{red}{8^{\ast}} & -3 & 12\\
\hline
-z & -5 & 2& 4
\end{array}
&\Rightarrow
\begin{array}{c|cc|c}
& \color{red}{x_{1}} & r_{2} & -1\\
\hline
-r_{1}& -\frac{3}{8} & -1-\frac{(-3)\times 3}{8} & 6-\frac{12\times 3}{8}\\
-x_{2} & -\frac{(-2)}{8}& 1-\frac{(-3)\times(-2)}{8} & 2-\frac{12\times(-2)}{8}\\
\color{red}{-r_{3}}& \frac{1}{8} & \frac{-3}{8} & \frac{12}{8}\\
\hline
-z & -\frac{(-5)}{8} & 2-\frac{(-3)\times(-5)}{8}& 4-\frac{12\times(-5)}{8}
\end{array}
\\
&\Rightarrow
\begin{array}{c|cc|c}
& \color{red}{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\\
\color{red}{-x_{1}}& \frac{1}{8} & -\frac{3}{8} & \frac{3}{2}\\
\hline
-z & \frac{5}{8} & \frac{1}{8}& \frac{23}{2}
\end{array}
\end{align}
$$

# 練習問題
リア充問題(主問題)の**等式標準形**の辞書に対して，以下の**ピボット演算** を ==順に== 行え．

1． **説明変数** $x_{1}$ と **被説明変数** $r_{1}$ を入れ替える.
2． **説明変数** $x_{2}$ と **被説明変数** $r_{3}$ を入れ替える.
3． **説明変数** $r_{1}$ と **被説明変数** $r_{2}$ を入れ替える.