---
lang: ja
tags: MTNS-2022, lecture, linear programming
---
# 2022年度 交通社会システム論<br>第5回：線形計画問題(4) 辞書とピボット演算<br>Dictionary and Pivot Operation
[ポータルへ戻る | Back to Portal](https://hackmd.io/@nagae/MTNS_2022)
<div style="text-align: center">

このページへは以下のQRコードまたはURLからアクセスできます：

<code style="font-size:20pt">https://hackmd.io/@nagae/MTNS_2022-Ch04</code>
</div>

# 不等式標準形から等式標準形へ | 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\}
$$

# リア充問題を等式標準形で表してみる | 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}$$

## 等式標準形 | 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}$$

# 辞書 | Dictionary
==**等式標準形**==:
$$
\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}
$$

# 辞書の例 | An Example of Dictionary
## リア充問題 | Happiness Maximization
### 等式標準形 | Standard Equality Form
$$
\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}
$$

## 対応する辞書 | Corresponding Dictionary
$$
\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}
$$

# 説明変数と被説明変数の入れ替え | 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}
$$

# 練習問題 |Exercise
リア充問題(主問題)の**等式標準形**の辞書に対して，以下の**ピボット演算** を ==順に== 行え．
For the standard equality form of the Mr. Adam's happiness maximization problem, perform the following pivot operations in order:

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