🙄

【OR】線形計画法の第一歩：タブローによるシンプレックス解法

2024/06/24に公開

 はじめにこの記事では、初学者向けに線形計画法の解法の一つである「タブローを利用したシンプレックス法」について解説します。

 対象読者とりあえずシンプレックス法による線形計画問題を解けるようになりたい方

 シンプレックス法とは？
 シンプレックス法の概要シンプレックス法は、線形計画法において最適解を求めるための代表的な手法の一つです。線形計画法の特徴として、最適解は実行可能領域の端点（頂点）に存在することが知られています。シンプレックス法は、この特性を利用して実行可能領域の端点を巡りながら最適解を探索するアルゴリズムです。


この図は、シンプレックス法がどのようにして実行可能領域の頂点を巡りながら最適解を探索するかを示しています。赤い矢印は、シンプレックス法の各ステップでの移動を表しています。

 シンプレックス法の基本概念
 制約条件と目的関数
目的関数: 最大化・最小化したい量を表す線形関数

制約条件: 利用可能なリソースやその他の制限を表す一連の線形等式や不等式
具体例：製品生産の最適化問題

原材料AとBがあり、原材料Aは 4\text{kg}、原材料Bは 3\text{kg} の在庫があります。

製品Aを作るのに原材料AとBをそれぞれ 1\text{kg} 必要とし、製品Bを作るのに原材料Aを 1\text{kg} 利用します。

また、製品Aが1単位あたり3万円、製品Bが1単位あたり2万円の利益を生み出すことができます。
これらを目的関数と制約条件にて整理します：

x: 製品Aの生産量（単位）

y: 製品Bの生産量（単位）

z: 総利益（万円）
目的関数：

z = 3x + 2y
制約条件：

\begin{aligned}
x + y &\le 4 \quad \text{（原材料Aの制約）} \\
x &\le 3 \quad \text{（原材料Bの制約）} \\
x, y &\ge 0 \quad \text{（非負制約）}
\end{aligned}
このような制約条件下で x と y をそれぞれ何個生産すれば利益を最大化することができるかを求めていきます。

 標準形線形計画問題を形式的に記述するためには、標準形に変換する必要があります。標準形は次のように構成されます。
目的関数の最大化または最小化
等式制約条件
非負の変数条件
具体例

上記の例の問題を標準形に変換します。

スラック変数（後ほど説明）を導入し、不等式から等式に変換します。
目的関数：

z = 3x + 2y
制約条件（等式）：

\begin{aligned}
x + y + s_1 &= 4 \quad \text{（原材料Aの制約）} \\
x + s_2 &= 3 \quad \text{（原材料Bの制約）}
\end{aligned}
非負制約：

x, y, s_1, s_2 \ge 0

 スラック変数不等式制約条件式から等式制約条件式に変換するために導入される、非負な補助変数のことです。

 辞書（シンプレックス辞書）目的：

シンプレックス法の各ステップで、現在地点での解を管理するために使用する表現方法です。

構成：

基底変数と非基底変数に分けて表現された目的関数と制約条件で構成されます。
具体例

標準形で挙げた例を利用し、スラック変数を左辺に残して移項します。
目的関数：

z = 3x + 2y
制約条件：

\begin{aligned}
s_1 &= 4 - x - y \quad \text{（原材料Aの制約）} \\
s_2 &= 3 - x \quad \quad \quad \text{（原材料Bの制約）}
\end{aligned}
※ 元の式が x + y + s_1 = 4 なので、移項するとマイナスになる点に注意してください。
非負制約：

x, y \ge 0

 初期辞書何も操作されていない初期状態の辞書を初期辞書と呼びます。

 基底変数と非基底変数辞書表現をした際に左辺にある変数を基底変数、右辺にある変数を非基底変数と呼びます。

 基底解辞書表現において、非基底変数を全て0にして得られる解を基底解と呼びます。

具体例：

(x, y, s_1, s_2) = (0, 0, 4, 3)

 ピボット操作辞書の基底解から別の基底解を探すために行う操作のことです。

最適解に向かって解を入れ替えながら探索していきます。

 タブロー (Tableau)シンプレックス法を適用する際に用いる計算表であり、線形計画問題の各ステップを効率的に計算するための表です。

 タブローを使ったシンプレックス法の手順
 1. 初期タブローの作成初期辞書から表に値を入れ込んでいきます。

Basis: 基底変数を表します。

CB: 基底変数に対応する目的関数の係数を示します。（初期段階のスラック変数は利益に寄与しないため0となります）

B: 基底変数の値（定数項）を表します。

Z_j: 現在の基底変数に基づいて目的関数の係数の合計を示しています。
Z_j = \sum(CB_i \times a_{ij})


C_j - Z_j: この行の値を見て、どの変数を基底に加えるべきか（ピボット列）、どの変数を除外すべきか（ピボット行）を判断します。

 2. ピボット操作
 ピボット要素を決定する① ピボット列の選択

C_j - Z_j の行で非負数（正の数）かつ一番大きい値を選択します。

例: 今回の目的関数は z = 3x + 2y なので、C_j - Z_j = (3, 2) となります。このうち値が大きい 3の列（xの列） をピボット列として選択します。
選択した列をピボット列と言います。
② ピボット行の選択

ピボット列の各値に対してB列の各値の比率を計算します。この比率が最小の非負数を持つ行をピボット行として選択します。

例: ピボット列（x列）の値が (1, 1) であり、B列の値が (4, 3) の場合、比率は以下のようになります。

s_1行: 4 / 1 = 4

s_2行: 3 / 1 = 3

この中で最小の値を持つ s_2 の行 をピボット行として選択します。
選択された行をピボット行と言います。
③ ピボット要素の確定

ピボット行とピボット列の交差点の要素をピボット要素として操作を行います。

 変数の入れ替えと計算基底変数の置き換え

ピボット行の基底変数（s_2）をピボット列の変数（x）に入れ替え、対応する目的関数の係数（CB）も更新します。

掃き出し法による計算（単位列化）

ピボット要素を1にする: ピボット行全体をピボット要素で割ります（今回は元々1なのでそのまま）。

ピボット列の他の要素を0にする: ピボット行以外の行に対して、行列基本変形を行いピボット列の値を0にします。

 3. 判定と繰り返し最適解を得るには C_j - Z_j の行がすべて 0以下 である必要があります。

まだ正の値（yの列など）が残っている場合は、次のピボット操作を行います。手順は基本的に一緒です。
2回目のピボット操作後:

この段階で、C_j - Z_j の行がすべて0以下になっているため、ピボット操作を終了します。

表のB列（基底変数の値）を見ると、x = 3, y = 1 となっており、その時の目的関数値 Z（最大利益）は 11 であることがわかりました。

 グラフによる確認

グラフでも示されているように、x = 3, y = 1 の時に最大値11が得られることが確認できます。

 最後にこの記事を通じて、シンプレックス法の基本概念とその適用方法について理解を深めることができたでしょうか。私自身も学習中ですが、上記の方法で手順を整理することができました。
今回の解説では、具体的な例を通じてシンプレックス法の手順を一歩一歩説明しました。初めて学ぶ方でも、この記事を参考にすれば実際の問題を解く足がかりになるはずです。さらに理解を深めるためには、実際に手を動かして問題を解いてみてください。
シンプレックス法に関する疑問や質問があれば、ぜひコメント欄で共有してください。また、誤りがあればご指摘いただけると幸いです。
最後まで読んでいただき、ありがとうございました！