---
lang: ja
tags: lecture, linear programming
---
# 線形計画問題(4) 辞書とピボット演算 - Linear Programming(4): Dictionary and Pivot Operation
[線形計画問題ポータルへ戻る | 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-Ch04</code>
</div>

# リア充問題を等式標準形で表してみる | Standard Equality Form of Mr. Adam's Happiness Problem

線形計画問題の代表的解法である単体法では，これまでの不等式標準形(標準最大化問題)ではなく，等式標準形を用いる方が便利である．これにより，**線形計画問題**は，所詮，**連立方程式**を(うまく選びながら)解く問題に帰着することが明らかになる．まずは，リア充実問題を等式標準形に直してみよう．

## リア充問題 | Original
$$\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}$$

等式標準形は**線形等式制約**と非負制約で構成される**最小化**問題なので，以下のように修正を行う：
- 最小化問題への変換
目的関数の全ての係数に$-1$を乗じる
$$
\max_{x_{1}, x_{2}} x_{1} + 2x_{2}=z \rightarrow \min_{x_{1}, x_{2}} -x_{1} - 2 x_{2} = -z
$$
- 等式制約への変換
不等式制約$x_{1} + x_{2} \leq 8$は「左辺が右辺と同じかそれより小さい」であるから，「左辺に(負ではない)何かを加えれば右辺に一致する」と等価である．
$$
x_{1} + x_{2} \leq 8 \rightarrow
\begin{cases}x_{1} + x_{2} + r_{1} = 8\\ r_{1} \geq 0
\end{cases}
$$
他の不等式についても同様に，
$$
\begin{array}{l}
-2x_{1} + x_{2} \leq 2\\
2x_{1} + 3x_{2} \leq 18
\end{array} \quad \rightarrow \quad
\begin{array}{l}
-2x_{1} + x_{2} + r_{2} = 2\\
2x_{1} + 3x_{2} + r_{3} = 18\\
r_{2}, r_{3} \geq 0
\end{array}
$$
と変換できる．

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

# 不等式標準形から等式標準形へ | From Standard Inequality Form to Standard Equality Form
上記の変換は，当然，一般的な線形計画問題にも適用できる.
$\boldsymbol{A} \in \mathcal{R}^{M\times{}N}, \boldsymbol{c} \in \mathcal{R}^{N}, \boldsymbol{b} \in \mathcal{R}^{M}$ を与件とした ==**標準最大化問題**== :
$$
\max_{\boldsymbol{x}}
\left\{\left.\boldsymbol{c}^{\top}\boldsymbol{x}
\right|
\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}
, \boldsymbol{x} \geq \boldsymbol{0}\right\}
$$
を ==**等式標準形**== に置き換えてみよう．これは， 目的関数の係数に $-1$ を乗じて最小化問題とした後，$M$ 次元の人工的な変数として ==**スラック変数**==(slack variable) $\boldsymbol{r} = (r_{1}, \cdots, r_{M})$ を導入し，不等式制約:$$\boldsymbol{A}\boldsymbol{x} \leq \boldsymbol{b}$$を等式制約:$$\boldsymbol{A} \boldsymbol{x} + \boldsymbol{r} = \boldsymbol{b}$$に置き換えれば，==**等式標準形**== が得られる:
$$
\min_{\boldsymbol{x}, \color{red}{\boldsymbol{r}}}
\left\{\left.-\boldsymbol{c}^{\top}\boldsymbol{x}
\right|
\boldsymbol{A} \boldsymbol{x} \color{red}{+ \boldsymbol{r} =} \boldsymbol{b}
, \boldsymbol{x} \geq \boldsymbol{0},
\color{red}{\boldsymbol{r}\geq\boldsymbol{0}}\right\}
$$
Suppose $\boldsymbol{A} \in \mathcal{R}^{M\times{}N}, \boldsymbol{c} \in \mathcal{R}^{N}, \boldsymbol{b} \in \mathcal{R}^{M}$ and a standard maximization problem:
$$
\max_{\boldsymbol{x}}
\left\{\left.\boldsymbol{c}^{\top}\boldsymbol{x}
\right|
\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}
, \boldsymbol{x} \geq \boldsymbol{0}\right\}.
$$
Convert it to a minimization problem by multiplying the objective by $-1$. Then let us introduce a **slack variable** $\boldsymbol{r} = (r_{1}, \cdots, r_{M})$ to convert the inequality constraint:
$$\boldsymbol{A}\boldsymbol{x} \leq \boldsymbol{b}$$to a equality:
$$\boldsymbol{A} \boldsymbol{x} + \boldsymbol{r} = \boldsymbol{b}.$$
In other words, the standard maximization problem can be reduced to the following standard equality form:
$$
\min_{\boldsymbol{x}, \color{red}{\boldsymbol{r}}}
\left\{\left.-\boldsymbol{c}^{\top}\boldsymbol{x}
\right|
\boldsymbol{A} \boldsymbol{x} \color{red}{+ \boldsymbol{r} =} \boldsymbol{b}
, \boldsymbol{x} \geq \boldsymbol{0},
\color{red}{\boldsymbol{r}\geq\boldsymbol{0}}\right\}
$$

# 辞書 | Dictionary
リア充問題の等式標準形
$$
\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}{l}
x_{1} + x_{2} + r_{1} = 8\\
-2x_{1} + x_{2} + r_{2} = 2\\
2 x_{1} + 3x_{2} + r_{3} = 18
\end{array}
$$
は，$r_{1}, r_{2}, r_{3}$を左辺に集めて
$$\begin{array}{l}
-r_{1} = x_{1} + x_{2} - 8\\
-r_{2} = -2x_{1} + x_{2} - 2\\
-r_{3} = 2 x_{1} + 3x_{2} - 18
\end{array}$$
と表せる．これに目的関数と未知変数$x_{1}, x_{2}$(および定数)の関係を書き加えれば
$$\begin{array}{l}
-r_{1} = x_{1} + x_{2} - 8\\
-r_{2} = -2x_{1} + x_{2} - 2\\
-r_{3} = 2 x_{1} + 3x_{2} - 18\\
\hline
-z=-x_{1}-2x_{2}-0
\end{array}$$
と書ける．最後の式は右辺定数が0であることを明示している．

後でも説明するように，この式は，$x_{1}, x_{2}$および定数を与えれば，$-z, -r_{1}, -r_{2}, -r_{3}$が完全に説明されることを意味している．

この式は，
$$
\begin{bmatrix}
-r_{1}\\-r_{2}\\-r_{3}
\end{bmatrix}=
\begin{bmatrix}
1 \\ -2 \\ 2
\end{bmatrix} \times x_{1} +
\begin{bmatrix}
1 \\ 1 \\ 3
\end{bmatrix} \times x_{2} +
\begin{bmatrix}
8 \\ 2 \\ 18
\end{bmatrix} \times (-1)
$$
とも書けるので，係数部分だけをまとめて下記のように書くことにしよう：
$$\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}
$$

以上の操作をまとめると
$$
\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}
$$
## 一般的な辞書 | Dictionary in General
==**等式標準形**==:
$$
\min_{\boldsymbol{x}, \boldsymbol{r}}
\left\{\left.-\boldsymbol{c}^{\top}\boldsymbol{x}
\right|
\boldsymbol{A} \boldsymbol{x} + \boldsymbol{r} = \boldsymbol{b}
, \boldsymbol{x} \geq \boldsymbol{0},
\boldsymbol{r}\geq\boldsymbol{0}\right\}
$$
に対して，目的関数:
$$
-z = - \boldsymbol{c}^{\top} \boldsymbol{x}
$$
と等式制約:
$$
-\boldsymbol{r} = \boldsymbol{A}\boldsymbol{x} - \boldsymbol{b}
$$
を合わせた **方程式系**
$$
\begin{bmatrix}
-\boldsymbol{r} \\ - z
\end{bmatrix} =
\begin{bmatrix}
\boldsymbol{A} & \boldsymbol{b}
\\
-\boldsymbol{c}^{\top} & 0
\end{bmatrix}
\begin{bmatrix}
\boldsymbol{x} \\ -1
\end{bmatrix}
$$
を，変数 $\boldsymbol{r}$ に対する ==**辞書**== (dictionary) と呼ぶ．

For a **standard equality form**:
$$
\min_{\boldsymbol{x}, \boldsymbol{r}}
\left\{\left.-\boldsymbol{c}^{\top}\boldsymbol{x}
\right|
\boldsymbol{A} \boldsymbol{x} + \boldsymbol{r} = \boldsymbol{b}
, \boldsymbol{x} \geq \boldsymbol{0},
\boldsymbol{r}\geq\boldsymbol{0}\right\},
$$
the objective function
$$
-z = - \boldsymbol{c}^{\top} \boldsymbol{x}
$$
and the equality constraint:
$$
-\boldsymbol{r} = \boldsymbol{A}\boldsymbol{x} - \boldsymbol{b}
$$
can be summarized as an equation system:
$$
\begin{bmatrix}
-\boldsymbol{r} \\ - z
\end{bmatrix} =
\begin{bmatrix}
\boldsymbol{A} & \boldsymbol{b}
\\
-\boldsymbol{c}^{\top} & 0
\end{bmatrix}
\begin{bmatrix}
\boldsymbol{x} \\ -1
\end{bmatrix}.
$$
This is referred to as the **dictionary** with respect to $r$.
:::info
**辞書** の由来は，==**説明変数**== $\boldsymbol{x}$ を1つ選ぶと，それに **従属** して目的関数値と ==**被説明変数**== $\boldsymbol{r}$ が説明される(飜訳される)ことから．
This equation system is referred to dictionary as it *translates* the **explanatory variable** $\boldsymbol{x}$ to the objective value $-z$ as well as the **explained variable** $\boldsymbol{r}$.
:::

上述したように，この辞書を，==**説明変数**== $\boldsymbol{x}$ および$-1$を**列**， ==**被説明変数**== $-\boldsymbol{r}, -z$ を**行**に配置した行列で係数を表示すると便利である．
It is useful to describe the dictionary by a matrix, which assigns the exploratory variables $\boldsymbol{x}$ and coefficient $-1$ to the columns, while the explained variables $-\boldsymbol{r}$ and $-z$ to the rows.
$$
\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}
& \boldsymbol{x}^{\top} & -1 \\
\hline
-\boldsymbol{r} & \boldsymbol{A} & \boldsymbol{b} \\
\hline
-z & -\boldsymbol{c}^{\top} & 0
\end{array}
$$

# 説明変数と被説明変数の入れ替え | Pivot
辞書の説明変数と被説明変数の関係は **相対的なもの** でしかない． 言い換えると，**方程式系を変えることなく**，説明変数と被説明変数を**入れ替えることが可能**で，それによって **異なる辞書** を構成できる．

For the dictionary, the relationship between the explanatory variable and the explained variable is merely **relative**. In other words, it is possible to pivot the explanatory and explained variables without violating the equality system, thereby obtaining other equivalent dictionaries.

たとえば，リア充度最大化問題の等式標準形に対応する辞書は，
For example, the standard form of the happiness maximization consists of
- **被説明変数 (explained variables)**: $\boldsymbol{v} = (r_{1}, r_{2}, r_{3})$
- **説明変数 (explanatory variables)**: $\boldsymbol{u} = (x_{1}, x_{2})$
なので，以下のように表示できる：
and thus its dictionary is:
$$
\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}$について解けば，
Let us pivot explained variable $r_{2}$ and explanatory variable $x_{2}$. Solving the equation with respect to $r_{2}$ for $x_{2}$, we obtain
$$
-x_{2} = -2x_{1}+r_{2}-2
$$
を得る．これを残りの3つの式に代入して整理すれば，
Substituting this to the remaining three equation, we have
$$
\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}$を入れ替え，
That is, a pivot of $r_{2}$ and $x_{2}$ obtains a new dictionary consists of
- 被説明変数 (explained): $\hat{\boldsymbol{u}} = (r_{1}, \color{red}{x_{2}}, r_{3})$
- 説明変数 (explanatory): $\hat{\boldsymbol{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}
$$

こうして作られた辞書に対応した**等式標準形**の線形計画問題:
It is noteworthy that the standard form corresponding to the new dictionary:
$$
\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}
$$
は，==もとのリア充度最大化問題と **等価である**== ことに注意されたい．すなわち，
is equivalent to the original problem. That is,
- 新しい問題の**最適解** $(x_{1}^{\ast}, r_{2}^{\ast}, r_{1}^{\ast}, x_{2}^{\ast}, r_{3}^{\ast})$ は，もとのリア充問題の**最適解**に等しい．
The optimal solution of the new problem, $(x_{1}^{\ast}, r_{2}^{\ast}, r_{1}^{\ast}, x_{2}^{\ast}, r_{3}^{\ast})$ , is equivalent to that of the original problem.
- 上述の問題の **最適値** $z^{\ast} = 5 x_{1}^{\ast} - 2 r_{2}^{\ast} + 4$ は，もとのリア充問題の**最適値** $z^{\ast} = x_{1}^{\ast} + 2 x_{2}^{\ast}$ に等しい．
The optimal value $-z^{\ast} = -5 x_{1}^{\ast} + 2 r_{2}^{\ast} - 4$ is equal to that of the original problem, $-z^{\ast} = -x_{1}^{\ast} - 2 x_{2}^{\ast}$.

# ピボット演算 | Pivot Operation
## 被説明変数/説明変数の入れ替え | Interchange of the explained and explanatory variables
上述の被説明変数/説明変数の入れ替えをシステマティックに表現してみよう．
$M$次元の**被説明変数**$\boldsymbol{v} = (v_{1}, \cdots, v_{M})$と$N$次元の**説明変数**$\boldsymbol{u} = (u_{1}, \cdots, u_{N})$ からなる**辞書**:
Suppose that a dictionary consisting $M$ explained variables (row) $\boldsymbol{v} = (v_{1}, \cdots, v_{M})$ and $N$ explanatory variable (column) $\boldsymbol{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}$について解けば，
Let us pivot explained variable $v_{i}$ and explanatory variable $u_{j}$ with assuming $a_{ij} \ne 0$. First, solve the equation with respect to $v_{i}$ for $u_{j}$, we obtain
$$
\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}
$$
ただし，
where
$$
\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{\boldsymbol{v}} = (v_{1}, \cdots, \color{red}{u_{j}}, \cdots, v_{M})$と**説明変数** $\hat{\boldsymbol{u}}=(u_{1}, \cdots, \color{red}{v_{i}}, \cdots, u_{N})$ に対する辞書が得られる．この新しい辞書の任意の$v_{k} (k\ne i)$ についての式は，
Substitute this to the remaining equations, we have another dictionary that translates the explanatory variable $\hat{\boldsymbol{u}}=(u_{1}, \cdots, \color{red}{v_{i}}, \cdots, u_{N})$ to the explained explained variable $\hat{\boldsymbol{v}} = (v_{1}, \cdots, \color{red}{u_{j}}, \cdots, v_{M})$. For this new dictionary, the equation with respect to any variable $v_{k} (k\ne i)$ is rewritten as:
$$
\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}
$$
と整理できる．ただし，
where
$$
\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$についての式は，
Similarly, the equation with respect to the objective $-z$ can be rewritten as:
$$
\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}
$$
と整理できる．ただし，
where
$$
\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}
$$
である．

## ピボット演算 | Pivot Operation
**被説明変数**$v_{i}$と**説明変数**$u_{j}$の入れ替えに対応した新たな**辞書**:
$$
\begin{cases}
-\boldsymbol{v} &= \boldsymbol{A}\boldsymbol{u} - \boldsymbol{b} \\
-z & -\boldsymbol{c}^{\top} \boldsymbol{u} - \zeta
\end{cases}
\Rightarrow
\begin{cases}
-\hat{\boldsymbol{v}} &= \hat{\boldsymbol{A}}\hat{\boldsymbol{u}} - \hat{\boldsymbol{b}} \\
-z & -\hat{\boldsymbol{c}}^{\top} \hat{\boldsymbol{u}} - \hat{\zeta}
\end{cases}
$$
を求める手続きは，==**ピボット演算**==(pivoting, pivot operation)と呼ばれ，以下の表形式で表せる:
The operation that derives a new dictionary by pivoting the explained variable $v_{i}$ and explanatory variable $u_{j}$ is referred to as the pivot operation (or, pivoting).
$$
\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}
$$

行列$\boldsymbol{A}$の$(i,j)$要素を ==**ピボット**==(pivot)と呼び，アスタリスク($\ast$)をつけて表す． ピボット演算の規則は一見複雑そうだが，行列の各要素を
The pivot operation can be summarized by categorizing each matrix element into:
- ピボット(pivot element): $p$
- ピボットと同じ行 (pivot row element): $r$
- ピボットと同じ列 (pivot column element): $c$
- それ以外 (other element): $q$

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

# ピボット演算の例：リア充問題 | Examples of The Pivot Operation
**説明変数** $x_{2}$ と**被説明変数** $r_{2}$ を入れ替える．
Pivoting explanatory column $x_{2}$ and explained row $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}{r_{2}} & -1\\
\hline
-r_{1}& 1-\frac{(-2)\times 1}{1} & -\frac{1}{1} & 8-\frac{2\times 1}{1}\\
\color{red}{-x_{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}$ を入れ替える．
Further pivoting explanatory column $x_{1}$ and explained row $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}{r_{3}} & 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}{-x_{1}}& \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}
$$