問題定義

制約条件のもとで、負でない変数の線形多項式で表現される目的関数を最大化 or 最小化する

目的関数：

\[\displaystyle z = \sum_{j=1}^N c_j x_j\] \[max \left( z \right) \mbox{ or } min \left( z \right)\]

制約条件：

\[\begin{cases} \displaystyle \sum_{j=1}^N a_{ij} x_j \lesseqqgtr b_i, & i = 1, ..., M \\ x_j \ge 0, & j = 1, ..., N \end{cases}\]

問題の例

• 以下の条件で、売上を最大にするには製品A, Bをそれぞれいくつ作れば良いか？
  • ある工場で部品1, 2, 3の在庫がそれぞれ18000, 21000, 21000個
  • 製品A, Bそれぞれの販売単価、および作るのに必要な部品の個数は下表の通り

	部品1	部品2	部品3	単価
製品A	1	2	3	20000
製品B	3	3	1	10000

\[z = 20000x_1 + 10000x_2\] \[max \left( z \right)\] \[\begin{cases} x_1 + 3x_2 \le 18000 \\ 2x_1 + 3x_2 \le 21000 \\ 3x_1 + x_2 \le 21000 \\ x_1, x_2 \ge 0 \end{cases}\]

このケースであれば、変数が2つしかないためグラフを利用して解ける。

→ \(x_1 = 6000, x_2 = 3000\) で \(z\) の最大値150,000,000

重要な前提

上述の例のように、制約及び目的関数が全て線形多項式のみからなるの最大化・最小化問題においては、

• 実行可能領域は凸性を持つ：領域内の任意の2点を結んだ線分も同じ領域に含まれる
  • 2次元なら凸多角形、3次元なら凸多面体
• 解を与えるのは実行可能領域の境界のどこかになる：2次元空間であれば境界の線分あるいは頂点
  • 線分の場合は、線分上のどの点でも同じ値となるため、実質的には頂点に限定して求めて良い

【NOTE】領域の凸性が重要な理由

• シンプレックス法では、目的関数が大きくなる方向へ 順番に領域の境界を辿っていく
• 下図のように領域が凸性を持たない場合、真の最適解へ向かうには目的関数を小さくする方向の移動が必要になり、局所最適解で探索が止まってしまう可能性がある

解法：シンプレックス法 (Simplex method)

基本思想

1. 最初に（最適解とは限らないが）実現可能な境界上の解を1つ見つける
2. その解からスタートして、境界に沿っていずれかの変数を増減させ、より目的関数を最大化 or 最小化する次の頂点（解）を見つける
3. どの変数を増減させても目的関数が増加しない状態になったら終了

処理の流れ

ここでは一般的な解法について記述。次節で具体的な問題を解く。

1. 標準形への変換

• 以下のような問題に落とし込みたい
  • 目的関数の最大化問題
  • 多項式の制約は全て上限制約を課す不等式
  • 変数 \(x_i\) は全て非負

\[max \left( z \right)\] \[\begin{cases} \displaystyle \sum_{j=1}^N a_{ij} x_j \le b_i, & i = 1, ..., M \\ x_j \ge 0, & j = 1, ..., N \end{cases}\]

最小化問題であるとき

符号を反転させ、\(z' = -z\) の最大化問題として扱う。

下限制約を課す不等式があるとき

下限制約を課す不等式

\[\displaystyle \sum_{j=1}^N a_{ij} x_j \ge b_i\]

は上限制約を課す不等式

\[\displaystyle \sum_{j=1}^N \left( -a_{ij} x_j \right) \le -b_i\]

に変換する。

等式の制約があるとき

\[\displaystyle \sum_{j=1}^N a_{ij} x_j = b_i\]

は、

\[\begin{cases} \displaystyle \sum_{j=1}^N a_{ij} x_j \ge b_i \\ \displaystyle \sum_{j=1}^N a_{ij} x_j \le b_i \end{cases}\]

に分解する。

変数の値として負の数も許容されるとき

特定の変数 \(x_i\) に非負条件がない場合、

\[\begin{cases} x_i = x_{i_1} - x_{i_2} \\ x_{i_1}, x_{i_2} \ge 0 \end{cases}\]

のように定義し、\(x_i\) を \(x_{i_1} - x_{i_2}\) に置き換えて処理を行う（変数は1つ増えることになる）。

2. スラック形への変換

• 非負条件以外の不等式制約を等式制約に変換したい

\[\displaystyle \sum_{j=1}^N a_{ij} x_j \le b_i\] \[\Longleftrightarrow \begin{cases} \displaystyle \sum_{j=1}^N a_{ij} x_j + s_i = b_i, & i = 1, ..., M \\ s_i \ge 0 \end{cases}\]

\(s_i\) は不等式の余裕（= slack）を埋める変数であり、スラック変数 と呼ばれる。

スラック変数は元々の不等式の変数と同様に扱い、\(s_i = x_{N+i}\) と置く。

スラック形：

\[\begin{cases} \displaystyle z = \sum_{j=1}^N c_j x_j \\ \displaystyle x_{N+i} = b_i - \sum_{j=1}^N a_{ij} x_j, & i = 1, ..., M \\ x_1, ..., x_{N+M} \ge 0 \end{cases}\]

• 基底変数と非基底変数
  • 左辺の変数 M 個の変数は、それぞれ1つの方程式にしか現れない：基底変数
  • 右辺の変数 N 個の変数は、複数の方程式にまたがって現れる：非基底変数
• 方程式を変形し、左辺の基底変数を右辺の非基底変数いずれかと入れ替えて別のスラック形にできる

【NOTE】スラック形の何が嬉しいのか？

• 方程式を見れば明らかなように、右辺の \(x_j\) を全てゼロとおくと、\(x_{N+i} = b_i\) と決まる。つまり、連立方程式の「明らかな解」が1つ求まる
  • 変数の値が決まれば、そのときの \(z\) の値も1つ定まる（上の式の場合は \(z=0\)）
  • ただし、\(b_i \lt 0\) の場合は \(x_{N+i}\) が負になって解の条件を満たさないため、別の方法で解を1つ見つける必要がある（次節）
• 「明らかな解」のときの \(z\) の値が大きくなるよう、うまく別のスラック形に変換していくのがシンプレックス法

3. 実現可能な基底解を1つ求める

• スラック形は M 個の連立方程式であり、変数の数（M+N）は M より大きいため、無限個の解を持つ
• 探索の開始地点として、条件を満たす領域境界の 実現可能基底解 を1つ求めたい

標準形において \(b_i\) が全てゼロ以上の場合

• スラック形で非基底変数を全てゼロと置くと、残る基底変数の値もすべて決まり、「明らかな解」が1つ求まる
  • 最初のスラック形では、非基底変数は全て元々の不等式が持っていた変数なので、この解はグラフで言うと原点
  • 更に、全ての \(x_i \ge 0\) なので、原点は領域境界上の頂点の1つ
• グラフ原点に対応する実現可能基底解：

\[(x_1, ..., x_N) = (0, ..., 0), (x_{N+1}, ..., x_{N+M}) = (b_1, ..., b_M)\]

標準形において負の \(b_i\) が存在する場合

• \(x_1, ..., x_N = 0\) とおくと、負の \(b_i\) に対して \(x_{N+i} = b_i \lt 0\) となってしまう（非負条件を満たさない）
• よって同じ方法は使えない

まず実現可能な解が存在するかどうかから調べる必要がある。

\(b_i \lt 0\) な方程式だけに新たなスラック変数 \(t_i\) を追加した、以下の連立方程式を考える。

\[\begin{cases} x_{N+i} = \begin{cases} \displaystyle b_i - \sum_{j=1}^N a_{ij} x_j, & \mbox{if } b_i \ge 0 \\ \displaystyle b_i - \sum_{j=1}^N a_{ij} x_j + t_i, & \mbox{if } b_i \lt 0 \end{cases} \\ x_i, t_i \ge 0 \end{cases}\]

元の方程式が実現可能な解を持つならば、余計なスラック変数 \(t_i\) がなくても等式が成立するはず。

→ この方程式において全ての \(t_i\) がゼロとなるような解が存在すれば、元の問題も実現可能な解を持つ。

つまり、この方程式の条件下で

\[\displaystyle z^{\prime} = - \sum_i t_i\]

の最大化問題を解けば良い（補助問題と呼ぶ）。

• 最適値がゼロ（\(max(z^{\prime}) = 0\)）の場合：補助問題の最適解を、元の問題の初期実行可能基底解として良い
• 最適値が負（\(max(z^{\prime}) \lt 0\)）の場合：元の問題は実行不可能（解なし）

【NOTE】補助問題自体の「明らかな解」は？

• \(b_i \ge 0\) の方程式では元のスラック変数 \(x_{N+i}\) を基底変数とみなして \(x_1, ..., x_N = 0\)
• \(b_i \lt 0\) のときは新しく追加したスラック変数 \(t_i\) を基底変数とみなして \(x_1, ..., x_N = 0\), \(x_{N+i} = 0\)

とすれば、基底変数もゼロ以上の値に決まり、「明らかな解」が得られる。よって補助問題はシンプレックス法で解ける。

4. 非基底変数を調整して目的関数を最大化

目的関数を最大化する流れを以下に示す。

1. 目的関数 \(z = \sum_{j=1}^N c_j x_j\) において、\(c_k \gt 0\) であるような非基底変数 \(x_k\) を1つ選ぶ
   • 係数 \(c_j\) が正ということは、他の非基底変数を固定して \(x_k\) を増やすと、\(z\) が増加する
   • 条件を満たす \(x_k\) が存在しなければ処理終了。この時点の非基底変数をゼロと置いて得られる「明らかな解」が最適解
     • （理由）負の係数しか存在しない = どの非基底変数を増やしても目的関数は減少
2. 各基底変数が非負条件を破らない範囲の上限まで \(x_k\) を増加させる
   • \(x_k\) を増やしていくと、いずれかの方程式において、基底変数が負になってしまう
   • 一番早く限界を迎える方程式と、その方程式に存在する基底変数 \(x_l\) を見つけることで、\(x_k\) を増やせる上限がわかる
3. \(x_l\) を非基底変数、\(x_k\) を基底変数にし、問題を新たなスラック形に変形（基底の交換）
4. 1に戻る

【NOTE】有界 / 非有界

実行可能領域が常に閉じているとは限らない。
下図のように、ステップ2においていくらでも目的関数を大きくできるケースがある。
→この場合、目的関数は発散し、最大値は存在しない（「非有界である」 という）。

「領域が無限に広い → 最大値が存在しない」は誤り。

【NOTE】最小添字規則

1. ステップ1において、係数 \(c_k \gt 0\) な非基底変数 \(x_k\)（= ピボット列）を選ぶ際、候補が複数あれば、添え字 \(k\) が最も小さい \(x_k\) を選択する
2. ステップ2において、一番すぐに限界を迎える基底変数 \(x_l\)（= ピボット行）を選ぶ際、同時に限界を迎えるものが複数あれば、候補の中で添え字 \(l\) が最も小さい \(x_l\) を選択する

これにより、同じパスを無限に巡回探索することを防ぐことができる。

例題と解法

原点が実行可能解、かつ領域が有界

\[\begin{cases} -x & + 2y & \le 8 \\ x & + y & \le 7 \\ 3x & + y & \le 15 \\ \end{cases}\] \[x, y \ge 0\]

maximize \(z = x + 2y\)

解き方

【スラック形への変換】

条件式にスラック変数 \(s_i \ge 0\) を加えて等式に変換。

\[\begin{cases} -x & + 2y & + s_1 & & & = 8 \\ x & + y & & + s_2 & & = 7 \\ 3x & + y & & & + s_3 & = 15 \\ \end{cases}\]

目的関数の定義 \(z = x + 2y\) を変形したものを加え、

\[\begin{cases} & -x & + 2y & + s_1 & & & = 8 & \qquad & \text{(A)} \\ & x & + y & & + s_2 & & = 7 & & \text{(B)} \\ & 3x & + y & & & + s_3 & = 15 & & \text{(C)} \\ z & -x & - 2y & & & & = 0 & & \text{(Z)} \\ \end{cases}\]

これは

• 非基底変数：\(x, y\)
• 基底変数：\(s_1, s_2, s_3\)

のスラック形で、\(z\) が非基底変数 \(x, y\) のみで表現されている。

連立方程式 (A), (B), (C) は、明らかな解 \((x, y) = (0, 0), (s_1, s_2, s_3) = (8, 7, 15)\) を持つ。

このとき、

\[z = x + 2y = 0\]

この解が探索の開始地点。

【\(z\) が大きくなるように基底変数を交換】

前述の明らかな解では、非基底変数が全てゼロ。

ここから非基底変数 \(x, y\) を増やしてもっと \(z\) を大きくできないか考える。

\(z = x + 2y\) と \(x, y \ge 0\) より、係数が正である \(x, y\) のどちらを増やしても \(z\) が増加する。

→ 係数の大きい \(y\) を選び（最大係数規則）、基底変数 \(s_1, s_2, s_3\) の非負条件が破れない範囲で 増やすことにする。 （追記：本当は巡回のリスクを回避するため最小添字規則を採用した方が安全）

連立方程式 (A), (B), (C) において残りの非基底変数 \(x \ (= 0)\) を固定し、\(y\) を0から少しずつ増やしていったとき、4を少し超えた \(y=4 + \delta \ (0 \lt \delta \ll 1)\) で (A) の非負条件が破れる（\(s_1 \ge 0\) が保てなくなる）：

\[-0 + 2 \times (4 + \delta) + s_1 = 8 \Leftrightarrow s_1 + 2\delta = 0\]

よって、\(y\) は4まで増やせる。

(A) 以外の式 (B), (C), (Z) の \(y\) の係数をゼロにするように掃き出し計算を行うと、

\[\begin{cases} & -\dfrac{1}{2}x & + y & + \dfrac{1}{2}s_1 & & & = 4 & \qquad & \text{(A')} \\ & \dfrac{3}{2}x & & - \dfrac{1}{2}s_1 & + s_2 & & = 3 & \qquad & \text{(B')} \\ & \dfrac{7}{2}x & & - \dfrac{1}{2}s_1 & & + s_3 & = 11 & \qquad & \text{(C')} \\ z & -2x & & + s_1 & & & = 8 & \qquad & \text{(Z')} \\ \end{cases}\]

これは、

• 非基底変数：\(x, s_1\)
• 基底変数：\(y, s_2, s_3\)

に入れ替わったことを意味する（= 別のスラック形への変換）。

新しい方程式を見れば、明らかな解として \((x, s_1) = (0, 0), (y, s_2, s_3) = (4, 3, 11)\) が見つかる。

このとき \(z = 8\)。

【NOTE】

基底変数の入れ替えの後も、「明らかな解」において「非基底変数が全てゼロ」という性質が保たれていることが重要。

【基底交換の繰り返し】

前ステップ最後に得られた明らかな解をスタートとして、同様の処理を繰り返す。

\(z = 8 + 2x - s_1\) と \(x, s_1 \ge 0\) より、係数が正である \(x\) を増やせば \(z\) が増加する。

\(s_1 \ (= 0)\) を固定して \(x\) をゼロから増やしていったとき、\(x = 2 + \delta\) で (B’) の非負条件が破れる：

\[\dfrac{3}{2} \times (2 + \delta) - \dfrac{1}{2} \times 0 + s_2 = 3 \Leftrightarrow \dfrac{3}{2} \delta + s_2 = 0\]

よって、\(x\) は2まで増やせる。

(B’) 以外の式 (A’), (C’), (Z’) の \(x\) の係数をゼロにするように掃き出し計算を行うと、

\[\begin{cases} & & + y & + \dfrac{1}{3}s_1 & + \dfrac{1}{2}s_2 & & = 5 & \qquad & \text{(A'')} \\ & x & & - \dfrac{1}{3}s_1 & + \dfrac{2}{3}s_2 & & = 2 & \qquad & \text{(B'')} \\ & & & - \dfrac{2}{3}s_1 & + 9s_2 & + s_3 & = 4 & \qquad & \text{(C'')} \\ z & & & + \dfrac{1}{3}s_1 & + \dfrac{4}{3}s_2 & & = 12 & \qquad & \text{(Z'')} \\ \end{cases}\]

これが新しいスラック形。

• 非基底変数：\(s_1, s_2\)
• 基底変数：\(x, y, s_3\)

明らかな解：\((s_1, s_2) = (0, 0), (x, y, s_3) = (2, 5, 4)\)

このとき \(z = 12\)

【値の収束】

\(z = 12 - \dfrac{1}{3}s_1 - \dfrac{4}{3}s_2\) と \(s_1, s_2 \ge 0\) より、\(s_1, s_2\) を増やしても \(z\) は12以上にならない（収束）。

よって、\((x, y) = 2, 5\) のとき \(z\) は最大値12を取る。

原点が実行可能解、かつ領域が非有界

\[\begin{cases} -x & + y & \le 1 \\ x & + 3y & \le 9 \\ \end{cases}\] \[x, y \ge 0\]

maximize \(z = x + 2y\)

解き方

【スラック形への変換】

前問と同様に、

\[\begin{cases} & -x & + y & + s_1 & & = 1 & \qquad & \text{(A)} \\ & -x & + 3y & & + s_2 & = 9 & \qquad & \text{(B)} \\ z & -x & - 2y & & & = 0 & \qquad & \text{(Z)} \\ \end{cases}\]

• 変数
  • 非基底変数：\(x, y\)
  • 基底変数：\(s_1, s_2\)
• 明らかな解
  • \[(x, y) = (0, 0), (s_1, s_2) = (1, 9)\]
  • このとき \(z = 0\)

【基底交換の繰り返し】

こちらも前問と同様。

変換1回目：

1. \(z = x + 2y\) の係数を見ると \(x, y\) どちらを増やしても \(z\) は増える
2. \(x \ (= 0)\) を固定し、係数の大きい \(y\) をゼロから増やしていく（最大係数規則）（追記：本当は巡回リスクを回避するため最小添字規則を採用した方が安全）
3. \(y = 1 + \delta\) で (A) より \(s_1\) の非負条件が破れる（\(y\) は1まで増やせる）
4. (A) 以外の \(y\) の係数をゼロにする掃き出しを行って別のスラック形に変換：

\[\begin{cases} & -x & + y & + s_1 & & = 1 & \qquad & \text{(A')} \\ & 2x & & - 3s_1 & + s_2 & = 6 & \qquad & \text{(B')} \\ z & -3x & & + 2s_1 & & = 2 & \qquad & \text{(Z')} \\ \end{cases}\]

• 変数
  • 非基底変数：\(x, s_1\)
  • 基底変数：\(y, s_2\)
• 明らかな解
  • \[(x, s_1) = (0, 0), (y, s_2) = (1, 6)\]
  • このとき \(z = 2\)

変換2回目：

1. \(z = 3x - 2s_1\) の係数を見ると \(x\) を増やせば \(z\) は増える
2. \(s_1 \ (= 0)\) を固定し、\(x\) をゼロから増やしていく
3. \(x = 3 + \delta\) で (B’) より \(s_2\) の非負条件が破れる（\(x\) は3まで増やせる）
4. (B) 以外の \(x\) の係数をゼロにする掃き出しを行って別のスラック形に変換：

\[\begin{cases} & & + y & - \dfrac{1}{2}s_1 & + \dfrac{1}{2}s_2 & = 4 & \qquad & \text{(A')} \\ & x & & - \dfrac{3}{2}s_1 & + \dfrac{1}{2}s_2 & = 3 & \qquad & \text{(B')} \\ z & & & - \dfrac{5}{2}s_1 & + \dfrac{3}{2}s_2 & = 11 & \qquad & \text{(Z')} \\ \end{cases}\]

• 変数
  • 非基底変数：\(s_1, s_2\)
  • 基底変数：\(x, y\)
• 明らかな解
  • \[(s_1, s_2) = (0, 0), (x, y) = (3, 4)\]
  • このとき \(z = 11\)

変換3回目：

1. \(z = 11 + \dfrac{5}{2}s_1 - \dfrac{3}{2}s_2\) の係数を見ると \(s_1\) を増やせば \(z\) は増える
2. \(s_2 \ (= 0)\) を固定し、\(s_1\) をゼロから増やしていく
3. \(s_1\) をどれだけ増やしても (A’), (B’) の左辺は小さくなる一方で、\(x, y\) の非負条件は破れない（\(s_1\) はいくらでも増やせる）

【値の発散】

\(s_1\) をいくらでも増やせるので、\(z\) の最大値は無限大に発散する。

原点が実行可能解でない

\[\begin{cases} x & + 4y & \le 22 \\ 2x & + y & \le 9 \\ x & - 2y & \le -4 \\ \end{cases}\] \[x, y \ge 0\]

maximize \(z = x + 2y\)

解き方

【スラック形への変換】

条件式にスラック変数 \(s_i \ge 0\) を加えて等式に変換。

\[\begin{cases} x & + 4y & + s_1 & & & = 22 \\ 2x & + y & & + s_2 & & = 9 \\ x & - 2y & & & + s_3 & = -4 \\ \end{cases}\]

第3式の右辺に負の値があるので、前2問のように \((x, y) = (0, 0)\) とすると \(s_3 = -4 \lt 0\) となり、非負条件が破れて実行可能解にならない。

→ 別の方法で実行可能解を見つける必要がある。

【補助問題を解く】

実行可能解を1つ見つけるため、スラック変数 \(t_i \ge 0\) を加えて次の補助問題を解く。

\[\begin{cases} x & + 4y & + s_1 & & & & = 22 \\ 2x & + y & & + s_2 & & & = 9 \\ x & - 2y & & & + s_3 & - t_1 & = -4 \\ \end{cases}\]

maximize \(z' = \displaystyle \sum_i (-t_i) = - t_1\)

【NOTE】

この補助問題の解が \(max(z') = 0\)、つまり \(t_1 = 0\) であれば、余計なスラック変数 \(t_1\) を加えなくても元の問題の条件を満たすような \(x, y, s_1, s_2, s_3\) が存在する ということになる（これを最初の実行可能解として使う）。

逆に、\(max(z') \lt 0\) は元の問題の条件を満たす解が存在しないことを意味する（解なし）。

右辺を正にするため第3式の符号を反転させ、\(z'\) の定義式の変形 \(z' + t_1 = 0\) を加える。

\[\begin{cases} & x & + 4y & + s_1 & & & & = 22 \\ & 2x & + y & & + s_2 & & & = 9 \\ & -x & + 2y & & & - s_3 & + t_1 & = 4 \\ z' & & & & & & + t_1 & = 0 \\ \end{cases}\]

• 変数
  • 非基底変数：\(x, y, s_3\)
  • 基底変数：\(s_1, s_2, t_1\)
• 明らかな解
  • \[(x, y, s_3) = (0, 0, 0), (s_1, s_2, t_1) = (22, 9, 4)\]
  • このとき \(z' = -4\)

【NOTE】

これまで解いてきた問題では、目的関数は常に非基底変数のみで表現されており、「非基底変数が全てゼロ」を満たす解からスタートして目的関数の値を増やしてきた。

しかし、この補助問題の初期状態においては、\(z' = - t_1\) であり基底変数が表式に含まれる。

そのため、「非基底変数をゼロから増やして目的関数を増加させる」というアプローチが使えない。

これまでと同様のアプローチを適用できるようにするため、\(z\) の式から \(t_1\) を掃き出しで排除する。

\[\begin{cases} & x & + 4y & + s_1 & & & & = 22 \\ & 2x & + y & & + s_2 & & & = 9 \\ & -x & + 2y & & & - s_3 & + t_1 & = 4 \\ z' & +x & - 2y & & & + s_3 & & = -4 \\ \end{cases}\]

これで今までのシンプレックス法と同じ状態（目的関数が非基底変数のみで表現される）にできた。

ここからはこれまでと同様に解ける。

1. \(z = -4 -x +2y -s_3\) の係数を見ると \(y\) を増やせば \(z'\) は増える
2. \(x, s_3 \ (= 0)\) を固定し、\(y\) をゼロから増やしていく
3. \(y = 2 + \delta\) で第3式より \(t_1\) の非負条件が破れる（\(y\) は2まで増やせる）
4. 第3式以外の \(y\) の係数をゼロにする掃き出しを行って別のスラック形に変換：

\[\begin{cases} & 3x & & + s_1 & & 2s_3 & - 2t_1 & = 14 \\ & \dfrac{5}{2}x & & & + s_2 & + \dfrac{1}{2}s_3 & - \dfrac{1}{2}t_1 & = 7 \\ & -\dfrac{1}{2}x & + y & & & - \dfrac{1}{2}s_3 & + \dfrac{1}{2}t_1 & = 2 \\ z' & & & & & & + t_1 & = 0 \\ \end{cases}\]

• 変数
  • 非基底変数：\(x, s_3, t_1\)
  • 基底変数：\(y, s_1, s_2\)
• 明らかな解
  • \[(x, s_3, t_1) = (0, 0, 0), (y, s_1, s_2) = (2, 14, 7)\]
  • このとき \(z' = 0\)

\(z' = -t_1\), \(t_1 \ge 0\) より、\(t_1\) をゼロから大きくしても \(z'\) は増加しない（収束）

\(max(z') = 0\) より、元の問題は実行可能解 \((x, y, s_1, s_2, s_3) = (0, 2, 14, 7, 0)\) を持つ。

【元の問題を解く】

実行可能解が1つ得られたので、元の問題の方程式を補助問題の最終結果の方程式に置き換える。

\[\begin{cases} & 3x & & + s_1 & & 2s_3 & = 14 \\ & \dfrac{5}{2}x & & & + s_2 & + \dfrac{1}{2}s_3 & = 7 \\ & -\dfrac{1}{2}x & + y & & & - \dfrac{1}{2}s_3 & = 2 \\ z & -x & - 2y & & & & = 0 \\ \end{cases}\]

• 変数
  • 非基底変数：\(x, s_3\)
  • 基底変数：\(y, s_2, s_3\)
• 明らかな解
  • \[(x, s_3) = (0, 0), (y, s_1, s_2) = (2, 14, 7)\]
  • このとき \(z = x + 2y = 4\)

ここで、\(z\) の表式には非基底変数と基底変数が混在している。

補助問題の最初の手順と同様に、掃き出しにより非基底変数だけの表式に直しておく。

\[\begin{cases} & 3x & & + s_1 & & 2s_3 & = 14 \\ & \dfrac{5}{2}x & & & + s_2 & + \dfrac{1}{2}s_3 & = 7 \\ & -\dfrac{1}{2}x & + y & & & - \dfrac{1}{2}s_3 & = 2 \\ z & -2x & & & & - s_3 & = 4 \\ \end{cases}\]

これで今までのシンプレックス法と同じ状態（目的関数が非基底変数のみで表現される）にできた。

あとは同じように解くだけ。

\(x\) を限界まで増やす変形：

\[\begin{cases} & & & s_1 & - \dfrac{6}{5}s_2 & + \dfrac{7}{5}s_3 & = \dfrac{28}{5} \\ & x & & & + \dfrac{2}{5}s_2 & + \dfrac{1}{5}s_3 & = \dfrac{14}{5} \\ & & y & & + \dfrac{1}{5}s_2 & - \dfrac{2}{5}s_3 & = \dfrac{17}{5} \\ z & & & & + \dfrac{4}{5}s_2 & - \dfrac{3}{5}s_3 & = \dfrac{48}{5} \\ \end{cases}\]

• 変数
  • 非基底変数：\(s_2, s_3\)
  • 基底変数：\(x, y, s_1\)
• 明らかな解
  • \[(s_2, s_3) = (0, 0), (x, y, s_1) = (\dfrac{14}{5}, \dfrac{17}{5}, \dfrac{28}{5})\]
  • このとき \(z = \dfrac{48}{5}\)

\(s_3\) を限界まで増やす変形：

\[\begin{cases} & & & \dfrac{5}{7}s_1 & - \dfrac{6}{7}s_2 & + s_3 & = 4 \\ & x & & - \dfrac{1}{7}s_1 & + \dfrac{4}{7}s_2 & & = 2 \\ & & y & + \dfrac{2}{7}s_1 & - \dfrac{1}{7}s_2 & & = 5 \\ z & & & + \dfrac{3}{7}s_1 & + \dfrac{2}{7}s_2 & & = 12 \\ \end{cases}\]

• 変数
  • 非基底変数：\(s_1, s_2\)
  • 基底変数：\(x, y, s_3\)
• 明らかな解
  • \[(s_1, s_2) = (0, 0), (x, y, s_3) = (2, 5, 4)\]
  • このとき \(z = 12\)

【値の収束】

\(z = 12 - \dfrac{3}{7}s_1 - \dfrac{2}{7}s_2\) と \(s_1, s_2 \ge 0\) より、\(s_1, s_2\) を増やしても \(z\) は12以上にならない（収束）。

よって、\((x, y) = 2, 5\) のとき \(z\) は最大値12を取る。