オペレーションズリサーチ 第 4 回¶
線形計画法 (3)〜(6)：標準形と単体法¶
日本大学生産工学部 オペレーションズリサーチ（柿本・大前）
0. この資料の使い方¶
第 3 回では、変数が 2 つの線形計画問題をグラフで解きました（図解法）。今回は、変数が何個あっても 式の変形だけで 解ける方法、単体法（シンプレックス法）を扱います。
単体法の中身は「連立 1 次方程式を何度も解き直す」ことです。使う操作は、中学・高校で習った連立方程式の加減法（式を定数倍する、式どうしを足し引きする）だけです。それを決まった手順で繰り返し、係数だけを表に書いて計算します。
目的は次の 3 点です。
- 線形計画問題を 不等式標準形・等式標準形 に直せる（スラック変数を導入できる）。
- 基底解 と実行可能領域の 頂点 の対応を説明できる。
- シンプレックスタブロー を使って、小さな線形計画問題を単体法で解ける。
題材は第 3 回と同じ生産計画問題です。第 3 回の答え（最適解 $x_1 = 35$、$x_2 = 7.5$、最適値 $z = 142.5$）を、今回はグラフを使わずに式の変形だけで求めます。第 1 回の記法（$\sum$、$\forall$）で分からないものがあれば、第 1 回資料の記法早見表に戻ってください。
章立て¶
| 章 | 内容 |
|---|---|
| 1 | 不等式標準形 |
| 2 | 等式標準形とスラック変数 |
| 3 | 基底解と頂点 |
| 4 | 単体法の考え方（式で頂点を移る） |
| 5 | シンプレックスタブロー |
| 6 | 単体法の注意点 |
| 7 | 演習 |
| 付録 | 用語早見表 |
題材（第 3 回 §2.6 の生産計画問題）¶
$$ \begin{aligned} & z = 3x_1 + 5x_2 \rightarrow \max, \\ \text{s.t.} \quad & x_1 + 7x_2 \le 140, \\ & 2x_1 + 4x_2 \le 100, \\ & 3x_1 + 2x_2 \le 120, \\ & x_1 \ge 0,\ x_2 \ge 0. \end{aligned} $$
$x_1$、$x_2$ は製品 $P_1$、$P_2$ の生産量 [kg]、3 本の制約は材料 $M_1$、$M_2$、$M_3$ の在庫です。実行可能領域の頂点は O $(0, 0)$、A $(40, 0)$、B $(35, 7.5)$、C $(14, 18)$、D $(0, 20)$ でした（第 3 回 §4.4）。
今回は標準形（最小化）にそろえるため、目的関数を $-1$ 倍した $w = -z = -3x_1 - 5x_2 \rightarrow \min$ として扱います（§1.2）。$w$ は利益 $z$ の符号を変えたもので、利益は $z = -w$ です。
1. 不等式標準形¶
1.1 標準形とは¶
線形計画問題には、最大化も最小化も、$\le$ も $\ge$ も $=$ の制約もあります。単体法は「決まった形」の問題に対する手続きなので、解く前に問題をその形にそろえます。この決まった形を 標準形 と呼びます。
この資料では 2 種類の標準形を使います。
| 名前 | 形 | 用途 |
|---|---|---|
| 不等式標準形（本章） | 最小化、制約はすべて $\le$、変数はすべて $\ge 0$ | 問題を整理する形 |
| 等式標準形（第 2 章） | 最小化、制約はすべて $=$、変数はすべて $\ge 0$ | 単体法を適用する形 |
本によって「標準形」の定義は異なります（最大化を標準とする本、$\ge$ を標準とする本があります）。互いに変換できるので、どれを標準にしても本質は同じです。この資料は、多くの教科書と同じく 最小化 を標準にします。
1.2 不等式標準形の定義¶
変数の集合を $J$、制約の集合を $I$ として（第 1 回の記法、第 3 回 §2.7）
$$ \begin{aligned} & w = \sum_{j \in J} c_j x_j \rightarrow \min, \\ \text{s.t.} \quad & \sum_{j \in J} a_{ij} x_j \le b_i, \quad \forall i \in I, \\ & x_j \ge 0, \quad \forall j \in J. \end{aligned} $$
条件は次の 3 つです。
- 目的関数は 最小化
- 制約条件はすべて $\le$（右辺 $b_i$ は定数。負でもよい）
- 変数はすべて 非負（$x_j \ge 0$）
第 3 回の生産計画問題は最大化なので、目的関数を $-1$ 倍して最小化にします（$J = \{1, 2\}$、$I = \{1, 2, 3\}$）。
$$ \begin{aligned} & w = -3x_1 - 5x_2 \rightarrow \min, \\ \text{s.t.} \quad & x_1 + 7x_2 \le 140, \\ & 2x_1 + 4x_2 \le 100, \\ & 3x_1 + 2x_2 \le 120, \\ & x_1 \ge 0,\ x_2 \ge 0. \end{aligned} $$
$w$ は利益 $z$ の符号を変えたものです。$w$ を最小にすることと利益 $z = -w$ を最大にすることは同じで、最適解（$x_1$、$x_2$ の値）は変わりません。以後、この資料ではこの形で扱います。
1.3 標準形への変換規則¶
標準形でない問題は、次の規則で書き換えます。
| 元の形 | 書き換え | 理由 |
|---|---|---|
| 最大化 $f \rightarrow \max$ | $-f \rightarrow \min$ | $f$ が最大のとき $-f$ は最小。最適値は符号を戻す |
| $\ge$ の制約 $\sum_j a_{ij} x_j \ge b_i$ | 両辺に $-1$ を掛けて $\sum_j (-a_{ij}) x_j \le -b_i$ | 負の数を掛けると不等号の向きが変わる |
| $=$ の制約 $\sum_j a_{ij} x_j = b_i$ | $\le$ と $\ge$ の 2 本に分け、$\ge$ の方はさらに $-1$ 倍する | 「$\le$ かつ $\ge$」は「$=$」と同じ |
| 符号の条件がない変数 $x_j$ | $x_j = x_j^{+} - x_j^{-}$、$x_j^{+} \ge 0$、$x_j^{-} \ge 0$ とおく | どんな実数も「非負の数の差」で書ける |
| $x_j \le 0$ の変数 | $x_j' = -x_j \ge 0$ とおく | 符号を反転 |
1.4 変換の例¶
次の問題を不等式標準形に直します。
$$ \begin{aligned} & z = 2x_1 + 3x_2 \rightarrow \max, \\ \text{s.t.} \quad & x_1 + x_2 \ge 4, \\ & x_1 + 2x_2 \le 10, \\ & x_1 - x_2 = 1, \\ & x_1 \ge 0,\ x_2 \ge 0. \end{aligned} $$
手順 1 最大化を最小化に直す。$w = -z = -2x_1 - 3x_2$ とおく。
$$ w = -2x_1 - 3x_2 \rightarrow \min $$
手順 2 $\ge$ の制約の両辺に $-1$ を掛ける。
$$ x_1 + x_2 \ge 4 \quad \Longrightarrow \quad -x_1 - x_2 \le -4 $$
$\le$ の制約 $x_1 + 2x_2 \le 10$ はそのままでよい。
手順 3 $=$ の制約を 2 本に分け、$\ge$ の方は $-1$ 倍する。
$$ x_1 - x_2 = 1 \quad \Longrightarrow \quad \begin{cases} x_1 - x_2 \le 1 \\ x_1 - x_2 \ge 1 \end{cases} \quad \Longrightarrow \quad \begin{cases} x_1 - x_2 \le 1 \\ -x_1 + x_2 \le -1 \end{cases} $$
手順 4 まとめる。
$$ \begin{aligned} & w = -2x_1 - 3x_2 \rightarrow \min, \\ \text{s.t.} \quad & -x_1 - x_2 \le -4, \\ & x_1 + 2x_2 \le 10, \\ & x_1 - x_2 \le 1, \\ & -x_1 + x_2 \le -1, \\ & x_1 \ge 0,\ x_2 \ge 0. \end{aligned} $$
元の問題の最適値は、この問題の最適値 $w^*$ の符号を変えた $z^* = -w^*$ です。最適解（$x_1$、$x_2$ の値）はそのまま同じです。
1.5 よくある間違い¶
- $\ge$ を $\le$ に直すとき、左辺だけ符号を変えて右辺を忘れる → 両辺とも $-1$ 倍します。
- 最大化を最小化に直した後、答えの符号を戻し忘れる → 最適値は $z^* = -w^*$ です。最適解は変わりません。
- 符号の条件がない変数をそのまま非負だと思う → 問題文に「$x_j \ge 0$」がなければ非負ではありません。
2. 等式標準形とスラック変数¶
2.1 不等式を等式に直す¶
単体法は連立「方程式」を解き直す手続きなので、制約条件を 等式 にします。不等式 $x_1 + 7x_2 \le 140$ に対して、右辺と左辺の差を
$$ s_1 = 140 - x_1 - 7x_2 $$
と 定義 します。$s_1$ は、材料 $M_1$ の在庫 140 kg のうち 使わずに余る量 です。この定義を移項すると
$$ x_1 + 7x_2 + s_1 = 140 $$
という等式になります。この等式は $s_1$ の定義を書き直しただけなので、$x_1, x_2$ がどんな値でも（$s_1$ をこの式で決めるかぎり）必ず成り立ちます。実行可能領域の外の点でも同じで、たとえば $(x_1, x_2) = (50, 50)$ なら $s_1 = -260$ として成り立ちます。
では、元の不等式 $x_1 + 7x_2 \le 140$ の中身はどこへ行ったのでしょうか。不等式は「余りが負でない」ことなので、$s_1 \ge 0$ と同じです。まとめると
$$ x_1 + 7x_2 \le 140 \quad \Longleftrightarrow \quad x_1 + 7x_2 + s_1 = 140,\quad s_1 \ge 0 $$
で、右側の等式は $s_1$ の定義、不等式の中身はすべて $s_1 \ge 0$ に移っています。この「等式はいつでも成り立つ。条件は非負だけ」という見方は、§3 で基底解が実行可能かどうかを判定するときに使います。
- このように、不等式の「余裕」を表すために加える変数を スラック変数（slack variable）と呼びます。slack は「ゆるみ」「余裕」という意味です。
- $\le$ の制約 1 本につき、スラック変数を 1 つ加えます。制約ごとに別の変数を使います。
生産計画問題の 3 本の制約に、それぞれ $s_1$、$s_2$、$s_3$ を加えます。
| 制約（不等式） | 等式 | スラック変数の意味 |
|---|---|---|
| $x_1 + 7x_2 \le 140$ | $x_1 + 7x_2 + s_1 = 140$ | $s_1$：材料 $M_1$ の余り [kg] |
| $2x_1 + 4x_2 \le 100$ | $2x_1 + 4x_2 + s_2 = 100$ | $s_2$：材料 $M_2$ の余り [kg] |
| $3x_1 + 2x_2 \le 120$ | $3x_1 + 2x_2 + s_3 = 120$ | $s_3$：材料 $M_3$ の余り [kg] |
2.2 等式標準形¶
スラック変数を加えると、生産計画問題は次の形になります。これを 等式標準形 と呼びます。
$$ \begin{aligned} & w = -3x_1 - 5x_2 \rightarrow \min, \\ \text{s.t.} \quad & x_1 + 7x_2 + s_1 = 140, \\ & 2x_1 + 4x_2 + s_2 = 100, \\ & 3x_1 + 2x_2 + s_3 = 120, \\ & x_1,\ x_2,\ s_1,\ s_2,\ s_3 \ge 0. \end{aligned} $$
- スラック変数の目的関数での係数は 0 です（余った材料は利益を生みません）。$w = -3x_1 - 5x_2 + 0s_1 + 0s_2 + 0s_3$ と思ってください。
- 変数は $n + m = 2 + 3 = 5$ 個、等式制約は $m = 3$ 本になります（$n$ = もとの変数の数、$m$ = 制約の数）。
- スラック変数 $s_1$、$s_2$、$s_3$ は、それぞれ 1 本の制約にだけ、係数 1 で現れます。つまり、各制約は最初から「自分のスラック変数について解けた形」になっています。これが単体法の出発点として重要です（§4.1）。
一般には、不等式標準形（§1.2）の各制約 $i \in I$ にスラック変数 $s_i \ge 0$ を加えて
$$ \sum_{j \in J} a_{ij} x_j + s_i = b_i, \quad \forall i \in I $$
と書けます。生産計画問題では制約が 3 本なので、スラック変数は $s_1$、$s_2$、$s_3$ です（添字は制約の番号です）。
2.3 スラック変数の値を読む¶
頂点 B $(x_1, x_2) = (35, 7.5)$ では、各制約の左辺は
$$ 35 + 7 \cdot 7.5 = 87.5, \qquad 2 \cdot 35 + 4 \cdot 7.5 = 100, \qquad 3 \cdot 35 + 2 \cdot 7.5 = 120 $$
なので
$$ s_1 = 140 - 87.5 = 52.5, \qquad s_2 = 100 - 100 = 0, \qquad s_3 = 120 - 120 = 0 $$
です。「材料 $M_1$ は 52.5 kg 余り、$M_2$、$M_3$ は使い切る」と読めます。スラック変数が 0 の制約は、その点で 等号が成り立っている（点がその直線の上にある）制約です。
2.4 よくある間違い¶
- スラック変数に非負条件を付け忘れる → $s_1 \ge 0$ がないと「$x_1 + 7x_2 \le 140$」に戻りません。
- 複数の制約で同じスラック変数を使い回す → 制約ごとに別の変数です。
- $\ge$ の制約にそのままスラック変数を足す → $\ge$ は先に §1.3 で $\le$ に直してから足します（$\ge$ のまま「引く」変数を使う本もあり、その場合は剰余変数と呼びます。意味は同じです）。
3. 基底解と頂点¶
3.1 式より変数が多い連立方程式¶
等式標準形の制約は、未知数 5 個（$x_1, \dots, s_3$）に対して方程式 3 本です。方程式が足りないので、解は 1 つに決まらず無数にあります。
ただし、5 個のうち 2 個の変数の値を決めてしまえば、残り 3 個は 3 本の方程式から決まります。たとえば $x_1 = 0$、$x_2 = 0$ と決めると
$$ s_1 = 140, \qquad s_2 = 100, \qquad s_3 = 120 $$
です。$x_1 = 35$、$x_2 = 7.5$ と決めると、§2.3 のとおり $s_1 = 52.5$、$s_2 = 0$、$s_3 = 0$ です。
3.2 基底解の定義¶
方程式が $m$ 本、変数が $n + m$ 個のとき、
- 変数のうち $m$ 個を選び、基底変数 と呼ぶ。残りの $n$ 個を 非基底変数 と呼ぶ。
- 非基底変数をすべて 0 とおき、連立方程式を基底変数について解いた解を 基底解 と呼ぶ。
- 基底解のうち、すべての変数が $\ge 0$ のものを 実行可能基底解 と呼ぶ。
基底変数の集合を 基底 と呼びます。
- 読み方: 「基底 $\{s_1, s_2, s_3\}$ に対する基底解」= 「$s_1, s_2, s_3$ 以外の変数（$x_1, x_2$）を 0 とおいて解いた解」
生産計画問題では $m = 3$、$n = 2$ です。基底 $\{s_1, s_2, s_3\}$ の基底解は $(x_1, x_2, s_1, s_2, s_3) = (0, 0, 140, 100, 120)$ で、すべて $\ge 0$ なので実行可能基底解です。これは頂点 O に対応します。
基底 $\{x_1, x_2, s_1\}$ なら、$s_2 = s_3 = 0$ とおいて
$$ \begin{cases} x_1 + 7x_2 + s_1 = 140 \\ 2x_1 + 4x_2 = 100 \\ 3x_1 + 2x_2 = 120 \end{cases} $$
を解きます。下の 2 本は第 3 回 §4.4 で頂点 B を求めた連立方程式で、$x_1 = 35$、$x_2 = 7.5$、したがって 1 本目から $s_1 = 52.5$ です。基底解は $(35, 7.5, 52.5, 0, 0)$ で、実行可能基底解です。頂点 B です。
3.3 基底解をすべて列挙する¶
5 個の変数から基底変数 3 個を選ぶ方法は $\binom{5}{3} = 10$ 通りです。すべての基底解を求めると次のようになります。
| 基底変数 | 0 とおく変数 | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | 実行可能？ | 頂点 |
|---|---|---|---|---|---|---|---|---|
| $s_1, s_2, s_3$ | $x_1, x_2$ | 0 | 0 | 140 | 100 | 120 | ○ | O |
| $x_1, s_1, s_2$ | $x_2, s_3$ | 40 | 0 | 100 | 20 | 0 | ○ | A |
| $x_1, x_2, s_1$ | $s_2, s_3$ | 35 | 7.5 | 52.5 | 0 | 0 | ○ | B |
| $x_1, x_2, s_3$ | $s_1, s_2$ | 14 | 18 | 0 | 0 | 42 | ○ | C |
| $x_2, s_2, s_3$ | $x_1, s_1$ | 0 | 20 | 0 | 20 | 80 | ○ | D |
| $x_1, s_2, s_3$ | $x_2, s_1$ | 140 | 0 | 0 | $-180$ | $-300$ | × | — |
| $x_1, s_1, s_3$ | $x_2, s_2$ | 50 | 0 | 90 | 0 | $-30$ | × | — |
| $x_2, s_1, s_3$ | $x_1, s_2$ | 0 | 25 | $-35$ | 0 | 70 | × | — |
| $x_2, s_1, s_2$ | $x_1, s_3$ | 0 | 60 | $-280$ | $-140$ | 0 | × | — |
| $x_1, x_2, s_2$ | $s_1, s_3$ | $\frac{560}{19}$ | $\frac{300}{19}$ | 0 | $-\frac{420}{19}$ | 0 | × | — |
実行可能基底解は 5 個で、第 3 回で求めた 5 つの頂点 O〜D と一致します。実行可能でない基底解は、直線どうしの交点ではあるが実行可能領域の 外 にある点です（第 3 回 §4.7 で「頂点ではない」とした交点がこれです）。
3.4 図で見る¶
図解法の各直線は、「ある変数が 0」という条件に対応します。
| 直線 | 条件 |
|---|---|
| $x_1 + 7x_2 = 140$ | $s_1 = 0$（材料 $M_1$ を使い切る） |
| $2x_1 + 4x_2 = 100$ | $s_2 = 0$（材料 $M_2$ を使い切る） |
| $3x_1 + 2x_2 = 120$ | $s_3 = 0$（材料 $M_3$ を使い切る） |
| 縦軸 | $x_1 = 0$ |
| 横軸 | $x_2 = 0$ |
頂点は 2 本の直線の交点、つまり「2 つの変数が 0」の点です。これが「非基底変数（2 個）を 0 とおく」ことと一致します。
実行可能領域の頂点 $\Longleftrightarrow$ 実行可能基底解
変数が 5 個になったのに図が 2 次元のままでよいのか
第 3 回 §5.2 で、変数が 3 個なら 3 次元の図になり、4 個以上は描けないと述べました。等式標準形は変数が 5 個ですが、図はいまも $x_1 x_2$ 平面のままです。これは、スラック変数が自由に動く変数ではないからです。$s_1 = 140 - x_1 - 7x_2$ のように、$s_1, s_2, s_3$ は $x_1, x_2$ を決めれば自動的に決まる従属変数です（等式制約は $s_i$ の定義式そのものです）。変数 5 個から方程式 3 本を引いた $5 - 3 = 2$ 個だけが自由に動き、それが $x_1, x_2$ です。
したがって、$s_1$ の軸はありません。「$s_1 = 0$」は原点から伸びる新しい軸ではなく、$x_1 x_2$ 平面上で $140 - x_1 - 7x_2 = 0$ となる点の集まり、つまり直線 $x_1 + 7x_2 = 140$ のことです。$s_1 = 10$ なら、それと平行な直線 $x_1 + 7x_2 = 130$ です。$s_1$ は「$x_1 x_2$ 平面の各点に、材料 $M_1$ の余りを対応させた量」と考えてください。
なぜ「すべて $\ge 0$」なら実行可能なのか
等式標準形の制約は、等式（$m$ 本）と非負条件の 2 種類です。§2.1 で見たように、等式は $s_i$ の定義を移項しただけなので、$x$ から $s$ を計算した時点で必ず満たされています。基底解も等式を解いて作った解なので同じです。残っている条件は非負条件だけなので、すべての変数が $\ge 0$ であればそれだけで実行可能です。
変数の符号は、図では「直線のどちら側にいるか」です。たとえば $s_1 = 140 - x_1 - 7x_2$ なので、直線 $x_1 + 7x_2 = 140$ の内側（原点側）では $s_1 > 0$、直線上で $s_1 = 0$、外側では $s_1 < 0$ です。$s_1 < 0$ は「材料 $M_1$ を在庫より多く使っている」という意味で、そこには行けません。$x_1 \ge 0$、$x_2 \ge 0$ も同じで、それぞれ縦軸・横軸の正の側を表します。
したがって、基底解のすべての変数が $\ge 0$ ということは、5 本の直線すべてについて正しい側（または直線上）にいる、つまり実行可能領域の中にいるということです。基底解はもともと 2 本の直線の交点なので、実行可能領域の中にある基底解は頂点です。
実行可能でない例
基底 $\{x_1, x_2, s_2\}$（$s_1 = s_3 = 0$）の基底解は、直線 $x_1 + 7x_2 = 140$ と直線 $3x_1 + 2x_2 = 120$ の交点 $(x_1, x_2) = (560/19, 300/19) \approx (29.5, 15.8)$ で、$s_2 = 100 - 2x_1 - 4x_2 = -420/19 \approx -22.1$ です。図では 2 本の直線が交わる点なので、一見すると頂点に見えます。しかし $s_2 < 0$ なので、この点は直線 $2x_1 + 4x_2 = 100$ の外側にあります。材料 $M_2$ を約 22 kg 超過する生産計画なので、実行可能ではありません。§3.3 の表で × が付いた 5 つの基底解は、どれかの変数が負、つまりどれかの直線の外側にある点です。
3.5 線形計画法の基本定理¶
第 3 回 §5.1 の「最適解は頂点のどれかにある」を、基底解の言葉で言い直すと次のようになります。
線形計画問題に最適解があるなら、実行可能基底解の中に 最適解がある。
したがって、グラフが描けなくても、実行可能基底解を調べれば最適解が見つかります。
3.6 総当たりで解いてみる¶
基本定理をそのまま使うと、次の手順で解けます。
- 基底変数の選び方（$\binom{5}{3} = 10$ 通り）をすべて書き出す。
- それぞれについて連立方程式を解き、基底解を求める（§3.3 の表）。
- 実行可能な基底解だけを残し、$w$ の値を比べる。
| 頂点 | $x_1$ | $x_2$ | $w = -3x_1 - 5x_2$ |
|---|---|---|---|
| O | 0 | 0 | 0 |
| A | 40 | 0 | $-120$ |
| B | 35 | 7.5 | $-142.5$ |
| C | 14 | 18 | $-132$ |
| D | 0 | 20 | $-100$ |
$w$ が最小なのは B なので、最適解は $x_1 = 35$、$x_2 = 7.5$、最適値 $w = -142.5$（利益 $z = 142.5$）です。第 3 回の答えと一致し、グラフは使っていません。
この方法の問題は、調べる基底解の数です。変数 $n$ 個・制約 $m$ 本の問題は、スラック変数を入れると変数が $n + m$ 個になり、基底変数の選び方は $\binom{n+m}{m}$ 通りあります。そのひとつひとつについて、$m$ 元の連立方程式を解かなければなりません。
| 変数 $n$ | 制約 $m$ | 基底変数の選び方 $\binom{n+m}{m}$ |
|---|---|---|
| 2 | 3 | 10 |
| 5 | 5 | 252 |
| 10 | 10 | 184,756 |
| 20 | 20 | 約 $1.4 \times 10^{11}$ |
| 50 | 50 | 約 $1.0 \times 10^{29}$ |
変数 50 個・制約 50 本は、現実の問題としては小さい方です。それでも基底解は $10^{29}$ 個あり、1 秒に $10^{9}$ 個調べられる計算機でも $10^{20}$ 秒（約 $3 \times 10^{12}$ 年）かかります。しかも §3.3 の表では、10 個のうち 5 個は解いてみたら実行可能ではなく、捨てることになりました。基底解の多くはこのような無駄な候補です。
そこで、実行可能基底解をすべて調べるのではなく、1 つの実行可能基底解から出発して、$w$ が良くなる隣の実行可能基底解へ移ることを繰り返す 方法を使います。これが単体法です（第 4 章）。この問題では、10 個の基底解のうち O、D、C、B の 4 個を調べるだけで最適解に着きます。
3.7 退化¶
基底解の中には、基底変数のどれかも 0 になるものがあります（3 本以上の直線が 1 点で交わる場合など）。このような基底解を 退化している といいます。生産計画問題には退化した基底解はありません。退化があるときの注意は §6.2 で触れます。
4. 単体法の考え方（式で頂点を移る）¶
単体法は、実行可能基底解（頂点）から出発し、目的関数が増える隣の頂点へ移ることを繰り返します。「隣の頂点へ移る」を式の操作で行います。この章では式の形を見ながら 1 回分の移動を丁寧に追い、第 5 章でそれを表（タブロー）にまとめます。
4.1 出発点：原点¶
等式標準形の 3 本の制約を、基底変数 $s_1, s_2, s_3$ について解いた形（左辺が基底変数だけ）に書き直します。目的関数も一緒に並べます。
$$ \begin{aligned} s_1 &= 140 - x_1 - 7x_2 \\ s_2 &= 100 - 2x_1 - 4x_2 \\ s_3 &= 120 - 3x_1 - 2x_2 \\ \hline w &= 0 - 3x_1 - 5x_2 \end{aligned} $$
この形を 辞書 と呼ぶことがあります。右辺の変数（非基底変数 $x_1$、$x_2$）を 0 とおけば、左辺の基底変数と $w$ の値が 定数項を読むだけで 分かります。
現在の基底解: $(x_1, x_2, s_1, s_2, s_3) = (0, 0, 140, 100, 120)$、$w = 0$ → 頂点 O
§2.2 で「各制約は最初から自分のスラック変数について解けた形になっている」と述べたのは、このように移項するだけで辞書になる、という意味です。
4.2 どの変数を増やすか（入る変数）¶
$w = -3x_1 - 5x_2$ なので、$x_1$ か $x_2$ を 0 から増やせば $w$ は減ります（目的は最小化なので、減らしたい）。係数が負で絶対値が大きい方が、1 単位増やしたときの減り方が大きいので、係数が最も小さい（最も負の）変数 を選びます。この規則を 最大係数規則 と呼びます（係数の絶対値が最大、という意味です）。
$x_2$ の係数 $-5$ が $x_1$ の係数 $-3$ より小さいので、$x_2$ を増やす。
これを「$x_2$ が基底に 入る」といい、$x_2$ を 入る変数 と呼びます。$x_1$ は 0 のままにします。
第 3 回 §5.3 の図の経路 O → D → C → B は、この規則で進んだものです（§4.5）。
入る変数を係数だけで決めるのは、移った先で $w$ がいくら減るかが、増やせる量（§4.3）を計算しないと分からないからです。原点 O で $x_1$ を増やすと $x_1 = 40$（頂点 A）まで増やせて、$w = -3 \times 40 = -120$ になります。$x_2$ を増やすと $x_2 = 20$（頂点 D）までで、$w = -5 \times 20 = -100$ です。1 単位あたりの減り方は $x_2$ の方が大きいのに、移った先の $w$ は $x_1$ を選んだ方が小さくなります。移った先の $w$ で選ぶには、候補の変数ごとに §4.3 の計算が要ります。変数が多い問題で毎回これを行うのは手間なので、係数だけで決めます。
係数が負の変数なら、どれを入れても最適解に着きます（§6.2 の最小添字規則は、係数の大きさでは選びません）。最大係数規則は、計算の手間が少ない選び方です。
4.3 どこまで増やせるか（出る変数）¶
$x_2$ を増やすと、基底変数 $s_1, s_2, s_3$ は辞書の式に従って減ります。どれも負になってはいけない（非負条件）ので、増やせる量に上限があります。$x_1 = 0$ のまま $x_2$ を増やすと
$$ \begin{aligned} s_1 &= 140 - 7x_2 \ge 0 \quad \Longrightarrow \quad x_2 \le 140 / 7 = 20 \\ s_2 &= 100 - 4x_2 \ge 0 \quad \Longrightarrow \quad x_2 \le 100 / 4 = 25 \\ s_3 &= 120 - 2x_2 \ge 0 \quad \Longrightarrow \quad x_2 \le 120 / 2 = 60 \end{aligned} $$
3 つの上限のうち 最小 の 20 まで増やせます。そのとき最初に 0 になるのは $s_1$ です。
$x_2 = 20$ まで増やす。$s_1$ が 0 になり、基底から 出る。
$s_1$ を 出る変数 と呼びます。「定数項 ÷ 入る変数の係数の絶対値」を比べて最小の式を選ぶ、この規則を 最小比規則 と呼びます。入る変数の係数が負でない式（増やしても減らない式）は上限がないので、比べる対象から外します。
4.4 式を書き直す（ピボット）¶
基底が $\{s_1, s_2, s_3\}$ から $\{x_2, s_2, s_3\}$ に変わりました。辞書を「左辺が新しい基底変数」の形に書き直します。使うのは連立方程式の代入法・加減法と同じ操作で、「ある式を定数倍する」「ある式に別の式の定数倍を足す（引く）」の 2 つだけです。この操作では解は変わりません。
手順 1 $s_1$ の式を $x_2$ について解く（両辺を 7 で割って整理する）。
$$ x_2 = 20 - \tfrac{1}{7} x_1 - \tfrac{1}{7} s_1 $$
手順 2 他の式の $x_2$ にこれを代入し、右辺から $x_2$ を消す。
$$ \begin{aligned} s_2 &= 100 - 2x_1 - 4\left(20 - \tfrac{1}{7} x_1 - \tfrac{1}{7} s_1\right) = 20 - \tfrac{10}{7} x_1 + \tfrac{4}{7} s_1 \\ s_3 &= 120 - 3x_1 - 2\left(20 - \tfrac{1}{7} x_1 - \tfrac{1}{7} s_1\right) = 80 - \tfrac{19}{7} x_1 + \tfrac{2}{7} s_1 \\ w &= -3x_1 - 5\left(20 - \tfrac{1}{7} x_1 - \tfrac{1}{7} s_1\right) = -100 - \tfrac{16}{7} x_1 + \tfrac{5}{7} s_1 \end{aligned} $$
手順 3 新しい辞書にまとめる。
$$ \begin{aligned} x_2 &= 20 - \tfrac{1}{7} x_1 - \tfrac{1}{7} s_1 \\ s_2 &= 20 - \tfrac{10}{7} x_1 + \tfrac{4}{7} s_1 \\ s_3 &= 80 - \tfrac{19}{7} x_1 + \tfrac{2}{7} s_1 \\ \hline w &= -100 - \tfrac{16}{7} x_1 + \tfrac{5}{7} s_1 \end{aligned} $$
現在の基底解: $(x_1, x_2, s_1, s_2, s_3) = (0, 20, 0, 20, 80)$、$w = -100$ → 頂点 D
$w$ が 0 から $-100$ に減りました（利益は 0 から 100 に増えました）。頂点 O から隣の頂点 D へ移ったことになります。この「1 つの変数について解いて、他の式に代入する」操作を ピボット と呼びます。
4.5 繰り返す¶
同じことを繰り返します。
2 回目 $w$ の式で係数が負なのは $x_1$（$-\frac{16}{7}$）だけなので、$x_1$ が入る。上限は $x_2$ の式から $20 \div \frac{1}{7} = 140$、$s_2$ の式から $20 \div \frac{10}{7} = 14$、$s_3$ の式から $80 \div \frac{19}{7} \approx 29.5$。最小は 14 で、$s_2$ が出る。$s_2$ の式を $x_1$ について解いて代入すると
$$ \begin{aligned} x_1 &= 14 + \tfrac{2}{5} s_1 - \tfrac{7}{10} s_2 \\ x_2 &= 18 - \tfrac{1}{5} s_1 + \tfrac{1}{10} s_2 \\ s_3 &= 42 - \tfrac{4}{5} s_1 + \tfrac{19}{10} s_2 \\ \hline w &= -132 - \tfrac{1}{5} s_1 + \tfrac{8}{5} s_2 \end{aligned} $$
現在の基底解: $(x_1, x_2, s_1, s_2, s_3) = (14, 18, 0, 0, 42)$、$w = -132$ → 頂点 C
3 回目 $w$ の式で係数が負なのは $s_1$（$-\frac{1}{5}$）なので、$s_1$ が入る。$x_1$ の式は $s_1$ の係数が正（増やしても減らない）なので対象外。$x_2$ の式から $18 \div \frac{1}{5} = 90$、$s_3$ の式から $42 \div \frac{4}{5} = 52.5$。最小は 52.5 で、$s_3$ が出る。
$$ \begin{aligned} x_1 &= 35 + \tfrac{1}{4} s_2 - \tfrac{1}{2} s_3 \\ x_2 &= 7.5 - \tfrac{3}{8} s_2 + \tfrac{1}{4} s_3 \\ s_1 &= 52.5 + \tfrac{19}{8} s_2 - \tfrac{5}{4} s_3 \\ \hline w &= -142.5 + \tfrac{9}{8} s_2 + \tfrac{1}{4} s_3 \end{aligned} $$
現在の基底解: $(x_1, x_2, s_1, s_2, s_3) = (35, 7.5, 52.5, 0, 0)$、$w = -142.5$ → 頂点 B
終了判定 $w = -142.5 + \frac{9}{8} s_2 + \frac{1}{4} s_3$ で、非基底変数の係数が すべて正 です。$s_2$、$s_3$ のどちらを 0 から増やしても $w$ は増えてしまうので、これ以上は改善できません。現在の基底解が最適解です。
4.6 単体法の手順（まとめ）¶
- 実行可能基底解（辞書）から始める。
- $w$ の式で、非基底変数の係数がすべて $\ge 0$ なら終了。現在の基底解が最適解。
- 負の係数のうち最小（最も負）の変数を入る変数にする。
- 各式について「定数項 ÷ 入る変数の係数の絶対値」（係数が負の式のみ）を計算し、最小の式の基底変数を出る変数にする。係数が負の式が 1 本もなければ、$w$ はいくらでも小さくできる（非有界、§6.1）。
- 辞書を書き直し（ピボット）、2 に戻る。
5. シンプレックスタブロー¶
第 4 章の計算は、変数の名前を省いて係数だけを表に書けば、ずっと楽に進められます。この表を シンプレックスタブロー（単体表）と呼びます。手計算でもプログラムでも、単体法は普通この形で行います。
5.1 表の作り方¶
等式標準形の制約 3 本と、目的関数 $w = -3x_1 - 5x_2$ を移項した式 $-3x_1 - 5x_2 - w = 0$ の、合わせて 4 本の方程式の係数を並べます。
$$ \begin{aligned} x_1 + 7x_2 + s_1 &= 140 \\ 2x_1 + 4x_2 + s_2 &= 100 \\ 3x_1 + 2x_2 + s_3 &= 120 \\ \hline -3x_1 - 5x_2 - w &= 0 \end{aligned} $$
出発点の表（基底 $\{s_1, s_2, s_3\}$、頂点 O）
| 基底 | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | 定数 |
|---|---|---|---|---|---|---|
| $s_1$ | 1 | 7 | 1 | 0 | 0 | 140 |
| $s_2$ | 2 | 4 | 0 | 1 | 0 | 100 |
| $s_3$ | 3 | 2 | 0 | 0 | 1 | 120 |
| $w$ | $-3$ | $-5$ | 0 | 0 | 0 | 0 |
- 各行が 1 本の方程式です。空欄はなく、その変数が式に出てこなければ 0 を書きます。
- 「基底」の列には、その行で解かれている基底変数（その行では係数 1、他の行では 0 の変数）を書きます。
- $w$ の列は常に同じ（最下行だけ $-1$、他は 0）なので省略しています。
- $w$ 行の係数は、最小化の目的関数 $w = -3x_1 - 5x_2$ の係数 そのまま です。第 4 章の辞書の $w$ の式と同じ数が並びます。
- $w$ 行の「定数」は、$-3x_1 - 5x_2 - w = 0$ の右辺なので、辞書の定数項の 符号を変えたもの（$-w$ の値）になります。出発点の表では $w = 0$ です。この問題では $-w$ が利益 $z$ そのものなので、利益がそのまま読めます。
5.2 表の読み方¶
| 読みたいもの | 表のどこを見るか |
|---|---|
| 基底変数の現在の値 | その行の「定数」 |
| 非基底変数の値 | 常に 0 |
| 現在の $w$ の値 | $w$ 行の「定数」の符号を変えたもの（表には $-w$ が書いてある。この問題では利益 $z$） |
| $w$ を減らせるか | $w$ 行に 負の数 があれば減らせる（辞書で係数が負、と同じこと） |
出発点の表なら、$s_1 = 140$、$s_2 = 100$、$s_3 = 120$、$x_1 = x_2 = 0$、$w = 0$ です。
5.3 表の操作（掃き出し）¶
表の各行は方程式なので、§4.4 と同じ 2 つの操作ができます。どちらも解を変えません。
| 操作 | 表では |
|---|---|
| (a) ある式の両辺を 0 でない定数で割る（掛ける） | その行の数をすべて同じ定数で割る（掛ける） |
| (b) ある式から別の式の定数倍を引く（足す） | その行の各数から、別の行の対応する数の定数倍を引く（足す） |
「ある列を、1 つの行だけ 1、他の行はすべて 0 にする」ことを、その行・列での 掃き出し と呼びます。手順は、(a) でその行の数を 1 にし、(b) で他の行の数を 0 にする、の 2 段階です。第 4 章の「$x_2$ について解いて代入する」が、表では「$x_2$ の列を掃き出す」になります。
5.4 手順（タブロー版）¶
- 入る変数: $w$ 行の負の数のうち 最も小さい（絶対値が最大の） 列を選ぶ。この列を ピボット列 と呼ぶ。負の数がなければ終了（最適）。
- 出る変数: ピボット列の成分が 正 の行について「定数 ÷ ピボット列の成分」を計算し、最小 の行を選ぶ。この行を ピボット行、ピボット行とピボット列の交わる成分を ピボット要素 と呼ぶ。正の成分がなければ非有界（§6.1）。
- 掃き出し: ピボット行をピボット要素で割って 1 にし、他の行（$w$ 行も含む）からピボット行の定数倍を引いて、ピボット列の他の成分を 0 にする（§5.3）。
- 「基底」の列で、出る変数を入る変数に書き換える。1 に戻る。
1〜4 の 1 回分（ピボット 1 回）を 1 ターンと数えます。出発点の表から 1 ターン進めた表を「1 ターン目の後の表」と呼びます。
5.5 計算例¶
1 ターン目（出発点の表 → 1 ターン目の後の表）
- $w$ 行で最小は $-5$（$x_2$ の列）→ $x_2$ が入る。
- 比: $140 / 7 = 20$、$100 / 4 = 25$、$120 / 2 = 60$ → 最小は 20、$s_1$ の行 → $s_1$ が出る。ピボット要素は 7（太字）。
- $s_1$ 行を 7 で割る。$s_2$ 行から（割った後の）$s_1$ 行の 4 倍を引く。$s_3$ 行から 2 倍を引く。$w$ 行に 5 倍を足す。
| 基底 | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | 定数 | 比 |
|---|---|---|---|---|---|---|---|
| $s_1$ | 1 | 7 | 1 | 0 | 0 | 140 | $140 / 7 = 20$ ← 最小 |
| $s_2$ | 2 | 4 | 0 | 1 | 0 | 100 | $100 / 4 = 25$ |
| $s_3$ | 3 | 2 | 0 | 0 | 1 | 120 | $120 / 2 = 60$ |
| $w$ | $-3$ | $-5$ | 0 | 0 | 0 | 0 | ↑ 最小 |
1 ターン目の後の表（基底 $\{x_2, s_2, s_3\}$、頂点 D）
| 基底 | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | 定数 |
|---|---|---|---|---|---|---|
| $x_2$ | $\frac{1}{7}$ | 1 | $\frac{1}{7}$ | 0 | 0 | 20 |
| $s_2$ | $\frac{10}{7}$ | 0 | $-\frac{4}{7}$ | 1 | 0 | 20 |
| $s_3$ | $\frac{19}{7}$ | 0 | $-\frac{2}{7}$ | 0 | 1 | 80 |
| $w$ | $-\frac{16}{7}$ | 0 | $\frac{5}{7}$ | 0 | 0 | 100 |
$w$ 行の定数が 100 になりました（$w = -100$、利益 100）。第 4 章の 2 番目の辞書と見比べてください（同じ数が並んでいます）。
2 ターン目
- $w$ 行で負は $-\frac{16}{7}$（$x_1$ の列）だけ → $x_1$ が入る。
- 比: $20 \div \frac{1}{7} = 140$、$20 \div \frac{10}{7} = 14$、$80 \div \frac{19}{7} \approx 29.5$ → 最小は 14、$s_2$ の行 → $s_2$ が出る。ピボット要素は $\frac{10}{7}$。
- $s_2$ 行を $\frac{10}{7}$ で割る（$\frac{7}{10}$ 倍する）。$x_2$ 行から $\frac{1}{7}$ 倍を引く。$s_3$ 行から $\frac{19}{7}$ 倍を引く。$w$ 行に $\frac{16}{7}$ 倍を足す。
2 ターン目の後の表（基底 $\{x_2, x_1, s_3\}$、頂点 C）
| 基底 | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | 定数 |
|---|---|---|---|---|---|---|
| $x_2$ | 0 | 1 | $\frac{1}{5}$ | $-\frac{1}{10}$ | 0 | 18 |
| $x_1$ | 1 | 0 | $-\frac{2}{5}$ | $\frac{7}{10}$ | 0 | 14 |
| $s_3$ | 0 | 0 | $\frac{4}{5}$ | $-\frac{19}{10}$ | 1 | 42 |
| $w$ | 0 | 0 | $-\frac{1}{5}$ | $\frac{8}{5}$ | 0 | 132 |
3 ターン目
- $w$ 行で負は $-\frac{1}{5}$（$s_1$ の列）→ $s_1$ が入る。
- 比: $x_2$ 行 $18 \div \frac{1}{5} = 90$、$x_1$ 行は成分が負（$-\frac{2}{5}$）なので対象外、$s_3$ 行 $42 \div \frac{4}{5} = 52.5$ → 最小は 52.5、$s_3$ の行 → $s_3$ が出る。ピボット要素は $\frac{4}{5}$。
- $s_3$ 行を $\frac{4}{5}$ で割る（$\frac{5}{4}$ 倍する）。$x_2$ 行から $\frac{1}{5}$ 倍を引く。$x_1$ 行に $\frac{2}{5}$ 倍を足す。$w$ 行に $\frac{1}{5}$ 倍を足す。
3 ターン目の後の表（最適）（基底 $\{x_2, x_1, s_1\}$、頂点 B）
| 基底 | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | 定数 |
|---|---|---|---|---|---|---|
| $x_2$ | 0 | 1 | 0 | $\frac{3}{8}$ | $-\frac{1}{4}$ | 7.5 |
| $x_1$ | 1 | 0 | 0 | $-\frac{1}{4}$ | $\frac{1}{2}$ | 35 |
| $s_1$ | 0 | 0 | 1 | $-\frac{19}{8}$ | $\frac{5}{4}$ | 52.5 |
| $w$ | 0 | 0 | 0 | $\frac{9}{8}$ | $\frac{1}{4}$ | 142.5 |
$w$ 行に負の数がない → 終了。
5.6 解の読み取り¶
3 ターン目の後の表の「基底」の列と「定数」の列を読みます。
- 基底変数: $x_2 = 7.5$、$x_1 = 35$、$s_1 = 52.5$
- 非基底変数: $s_2 = s_3 = 0$
- $w$ 行の定数 142.5 は $-w$ なので、$w = -142.5$（利益 $z = 142.5$）
最適解: $x_1 = 35$、$x_2 = 7.5$（スラック変数は $s_1 = 52.5$、$s_2 = s_3 = 0$）、最適値: $w = -142.5$（利益 $z = 142.5$ 万円）
第 3 回の図解法の答えと一致しました。$s_1 = 52.5$ は「材料 $M_1$ が 52.5 kg 余る」、$s_2 = s_3 = 0$ は「材料 $M_2$、$M_3$ は使い切る」という意味です。最適解を答えるときは、第 3 回と同じく最適解と最適値の両方を書いてください。
5.7 よくある間違い¶
- $w$ 行に元の最大化の目的関数の係数（$3$、$5$）を書く → 最小化に直した $w = -3x_1 - 5x_2$ の係数 $-3$、$-5$ です。符号を間違えると終了判定が逆になります。
- $w$ 行の定数を $w$ の値だと思う → $-w$ です（この問題では利益 $z$）。
- 比の計算に、ピボット列の成分が 0 や負の行も含めてしまう → 正の行だけで比べます。
- ピボット行をピボット要素で割る前に、他の行を掃き出す → 先にピボット要素を 1 にすると計算が簡単です。
- $w$ 行の掃き出しを忘れる → $w$ 行も他の行と同じ方程式です。必ず掃き出します。
- 分数を小数にして丸める → 分数のまま計算します（7.5、52.5 のように割り切れる場合は小数でも構いません）。
- 「基底」の列を書き換え忘れる → 1 ターン目の後の表では $s_1$ の行が $x_2$ の行になります。
6. 単体法の注意点¶
6.1 非有界¶
ピボット列に正の成分が 1 つもないと、入る変数をいくら増やしても基底変数は負になりません。つまり $w$ をいくらでも小さくできます。このとき問題は 非有界 といい、最適解はありません。
例: $w = -x_1 - x_2 \rightarrow \min$、s.t. $x_1 - x_2 \le 1$、$x_1 \ge 0$、$x_2 \ge 0$。
| 基底 | $x_1$ | $x_2$ | $s_1$ | 定数 |
|---|---|---|---|---|
| $s_1$ | 1 | $-1$ | 1 | 1 |
| $w$ | $-1$ | $-1$ | 0 | 0 |
$w$ 行は $-1$ が 2 つで同点です。同点のときは添字が小さい $x_1$ を選びます（§6.2）。$x_1$ の列で掃き出すと
| 基底 | $x_1$ | $x_2$ | $s_1$ | 定数 |
|---|---|---|---|---|
| $x_1$ | 1 | $-1$ | 1 | 1 |
| $w$ | 0 | $-2$ | 1 | 1 |
次は $x_2$ が入りますが、$x_2$ の列の成分は $-1$ だけで、正の成分がありません。$x_2$ を増やすと $x_1 = 1 + x_2$ も増えるだけで、どの変数も負にならず、$w = -1 - 2x_2$ はいくらでも小さくなります。
現実の問題で非有界になるのは、ほとんどの場合、定式化で制約を書き忘れたときです（「利益がいくらでも増やせる」ことは普通ありません）。
6.2 退化と循環¶
最小比が同点になると、次の表でどれかの基底変数の定数が 0 になります（退化、§3.7）。退化した表では、掃き出しても $w$ が減らない（定数が 0 の行で比が 0 になる）ことがあり、ごくまれに、何回か掃き出すと元の表に戻ってしまうことがあります。これを 循環 と呼びます。
循環は、入る変数と出る変数の選び方を次のように決めれば必ず避けられます（最小添字規則、Bland の規則）。
- 入る変数: $w$ 行が負の列のうち、添字が最小 の変数
- 出る変数: 比が最小の行が複数あれば、基底変数の添字が最小 の行
最小添字規則を使えば、単体法は有限回で必ず終了します。第 3 回 §5.3 の「最適解があれば、有限回の移動で到達する」は、このように循環を避けたときに成り立つことです。普段の計算は最大係数規則（§5.4）で行い、同点のときだけ添字の小さい方を選べば十分です。
6.3 原点から出発できない場合¶
§1.4 の例のように右辺に負の数があると、$x_1 = x_2 = 0$ は制約を満たしません。このとき出発点の表は実行可能基底解になっておらず、そのままでは単体法を始められません。出発点となる実行可能基底解を別の線形計画問題を解いて探す方法（2 段階単体法）がありますが、この授業では扱いません。第 5 回以降で使うソルバー（PuLP）は、この処理も自動で行います。
6.4 最大化問題¶
最大化問題は、§1.3 の規則で最小化に直してから解きます。得られた最適値の符号を変えたものが元の問題の最適値です（生産計画問題では利益 $z = -w$）。
7. 演習¶
演習問題は別紙（04_problem）にあります。解答用紙に記入して提出してください（出席確認を兼ねます）。
- 最小化／$\ge$／$=$ を含む線形計画問題を、不等式標準形に直し、さらにスラック変数を加えて等式標準形に直す（§1、§2）。
- 第 3 回の演習問題 1 を、シンプレックスタブローで解く（§5）。第 3 回で図解法で求めた答え（最適解 $x_1 = 2$、$x_2 = 6$、利益 22）と一致することを確かめる。
参考文献¶
- 福島雅夫『新版 数理計画入門』朝倉書店、2011。単体法の説明（辞書・タブロー・退化・2 段階法）と、行列・ベクトルを使った一般的な書き方はこの本の線形計画の章が詳しい。
付録：用語早見表¶
| 用語 | 意味 | 本資料の節 |
|---|---|---|
| 不等式標準形 | 最小化、制約はすべて $\le$、変数はすべて $\ge 0$ | §1.2 |
| 等式標準形 | 最小化、制約はすべて $=$、変数はすべて $\ge 0$ | §2.2 |
| スラック変数 | $\le$ を $=$ にするために加える非負の変数。制約の「余り」 | §2.1 |
| 基底変数・非基底変数 | 方程式の本数 $m$ だけ選んだ変数と、それ以外（0 とおく） | §3.2 |
| 基底解・実行可能基底解 | 非基底変数を 0 とおいた解・そのうちすべて $\ge 0$ のもの（= 頂点） | §3.2、§3.4 |
| 退化 | 基底変数のどれかも 0 になっている基底解 | §3.7 |
| 辞書 | 基底変数と $w$ を非基底変数で表した式の組 | §4.1 |
| 入る変数・出る変数 | 0 から増やす非基底変数・0 になって基底から外れる基底変数 | §4.2、§4.3 |
| 最大係数規則 | 入る変数の選び方。$w$ の係数が最も負（絶対値が最大）の変数。表では $w$ 行が最小の列 | §4.2、§5.4 |
| 最小比規則 | 出る変数の選び方。定数 ÷ ピボット列の成分が最小の行 | §4.3、§5.4 |
| ピボット・掃き出し | 入る変数について解いて他の式に代入する操作。表では列を「1 つの行だけ 1、他は 0」にする | §4.4、§5.3 |
| シンプレックスタブロー | 制約と $w$ の式の係数を並べた表。掃き出しで更新する | §5.1 |
| 終了条件 | $w$ 行に負の数がない（辞書で負の係数がない） | §4.5、§5.4 |
| 非有界 | ピボット列に正の成分がない。$w$ をいくらでも小さくできる | §6.1 |
| 循環・最小添字規則 | 退化によって表が元に戻る現象と、それを避ける選び方 | §6.2 |