シンプレックスアルゴリズム

数学的最適化において、ダンツィヒのシンプレックス法（またはシンプレックス法）は線形計画法のアルゴリズムである。^{[ 1 ]}

このアルゴリズムの名前は単体の概念に由来し、 TS Motzkinによって提案されました。^{[ 2 ]}この方法では単体は実際には使用されませんが、単体錐上で動作し、追加の制約によってこれらが適切な単体になるという解釈があります。^{[ 3 ] [ 4 ] [ 5 ] [ 6 ]}問題となる単体錐は、多面体と呼ばれる幾何学的オブジェクトの角（つまり、頂点の近傍）です。この多面体の形状は、目的関数に適用される制約によって定義されます。

ジョージ・ダンツィヒは第二次世界大戦中、机上計算機を使って米陸軍航空隊の計画手法に取り組んでいた。1946年、同僚が彼に計画プロセスを機械化するよう提案し、別の仕事に就くのを思いとどまらせようとした。ダンツィヒはワシリー・レオンチェフの研究に触発されて問題を線形不等式として定式化したが、当時は目的を定式化に含めていなかった。目的がなければ、膨大な数の解が実行可能となり、そのため「最良」の実行可能な解を見つけるには、目標そのものを指定するのではなく、目標をどのように達成できるかを記述する軍事規定の「基本ルール」を使用する必要がある。ダンツィヒの核心的な洞察は、そのような基本ルールのほとんどが最大化する必要のある線形目的関数に変換できることに気づいたことだった。^{[ 7 ]}シンプレックス法の開発は漸進的で、約1年かけて行われた。^{[ 8 ]}

ダンツィヒが1947年半ばに目的関数を定式化の一部として組み込んだ後、この問題は数学的に扱いやすくなった。ダンツィヒは、教授のイェジー・ネイマンの授業で宿題と勘違いしていた未解決問題（実際には後に解決した）が、線形計画法のアルゴリズムを見つけるのに応用できることに気づいた。この問題は、 0から1の間にある連続変数の一般線形計画法に対して、ルベーグ積分の形で表現された線形制約を満たすラグランジュ乗数の存在を見つけることであった。ダンツィヒは後にこの「宿題」を博士号取得のための論文として発表した。この論文で使用された列幾何学は、ダンツィヒにシンプレックス法が非常に効率的であると確信させる洞察を与えた。^{[ 9 ]}

シンプレックス法は、標準形式の線形計画問題に対して作用する。

最大化${\textstyle \mathbf {c^{T}} \mathbf {x} }$

対象${\displaystyle A\mathbf {x} \leq \mathbf {b} }$そして${\displaystyle \mathbf {x} \geq 0}$

と${\displaystyle \mathbf {c} =(c_{1},\,\dots ,\,c_{n})}$目的関数の係数、${\displaystyle (\cdot )^{\mathrm {T} }}$はドットプレースホルダー付きの行列転置であり、${\displaystyle \mathbf {x} =(x_{1},\,\dots ,\,x_{n})}$問題の変数は、${\displaystyle A}$はp × n行列であり、${\displaystyle \mathbf {b} =(b_{1},\,\dots ,\,b_{p})}$任意の線形計画問題を標準形式に変換する簡単な手順が存在するため、この形式の線形計画問題を使用しても一般性が失われることはありません。

幾何学的に言えば、すべての値によって定義される実行可能領域は${\displaystyle \mathbf {x} }$そのため${\textstyle A\mathbf {x} \leq \mathbf {b} }$そして${\displaystyle \forall i,x_{i}\geq 0}$これは（境界を持たない場合もある）凸多面体です。この多面体の極点または頂点は、基本実行可能解（BFS）として知られています。

標準形式の線形計画問題において、目的関数が実行可能領域で最大値をとる場合、その値は（少なくとも）極点の1つで存在することが示せる。^{[ 10 ]}極点の数が有限であるため、それ自体で問題は有限計算に縮小されるが、極点の数は最小の線形計画問題を除いては扱いきれないほど大きい。^{[ 11 ]}

また、極点が目的関数の最大値でない場合、その点を含む辺が存在し、その辺上で目的関数の値が点から離れるにつれて厳密に増加することも示せる。^{[ 12 ]}辺が有限であれば、その辺は目的関数の値がより大きい別の極点に接続している。そうでなければ、辺上で目的関数は上限がなく、線形計画問題には解がない。シンプレックス法はこの洞察を応用し、多面体の辺に沿って目的関数の値がどんどん大きくなる極点へと進んでいく。これは最大値に達するか、上限のない辺を訪れるまで続く（問題に解がないと結論付ける）。多面体の頂点の数は有限であるため、アルゴリズムは常に終了する。さらに、頂点間を常に同じ方向（目的関数の方向）にジャンプするため、訪れる頂点の数は少なくなると期待される。^{[ 12 ]}

線形計画問題の解法は 2 つのステップで行われます。最初のステップ (フェーズ I) では、開始極値点を見つけます。プログラムの性質によってはこれは自明な場合もありますが、一般的には元のプログラムの修正版にシンプレックス法を適用することで解くことができます。フェーズ I の結果として考えられるのは、基本実行可能解が見つかるか、実行可能領域が空であるかのいずれかです。後者の場合、線形計画問題は実行不可能と呼ばれます。2 番目のステップ (フェーズ II) では、フェーズ I で見つかった基本実行可能解を開始点として使用してシンプレックス法を適用します。フェーズ II の結果考えられるのは、最適な基本実行可能解が得られるか、目的関数が上方に有界でない無限のエッジが得られるかのいずれかです。^{[ 13 ] [ 14 ] [ 15 ]}

線形計画問題を標準形式に変換するには、次のようにします。^{[ 16 ]}まず、下限が0以外の各変数について、その変数と下限との差を表す新しい変数を導入します。次に、元の変数を代入によって消去します。例えば、制約条件が与えられた場合、

${\displaystyle x_{1}\geq 5}$

新しい変数、$\displaystyle y_1}}$は、

${\displaystyle {\begin{aligned}y_{1}=x_{1}-5\\x_{1}=y_{1}+5\end{aligned}}}$

2番目の式は消去するために使用できます${\displaystyle x_{1}}$線形計画問題から。このようにして、すべての下限制約を非負制約に変更することができる。

第二に、残りの各不等式制約に対して、制約を等式制約に変更するために、スラック変数と呼ばれる新しい変数が導入されます。この変数は不等式の両辺の差を表し、非負であると仮定されます。たとえば、不等式

${\displaystyle {\begin{aligned}x_{2}+2x_{3}&\leq 3\\-x_{4}+3x_{5}&\geq 2\end{aligned}}}$

に置き換えられます

${\displaystyle {\begin{aligned}x_{2}+2x_{3}+s_{1}&=3\\-x_{4}+3x_{5}-s_{2}&=2\\s_{1},\,s_{2}&\geq 0\end{aligned}}}$

この形式の不等式では、代数的な操作を行うのがはるかに容易です。2番目の不等式のように≥が現れる不等式では、一部の著者は導入された変数を余剰変数。

第三に、制約のない変数を線形計画から消去します。これには2つの方法があります。1つは、その変数が現れる方程式のいずれかで変数を解き、代入によって変数を消去する方法です。もう1つは、その変数を2つの制約付き変数の差で置き換える方法です。たとえば、$\displaystyle z_{1}}$制限がない場合は、次のように記述します。

${\displaystyle {\begin{aligned}&z_{1}=z_{1}^{+}-z_{1}^{-}\\&z_{1}^{+},\,z_{1}^{-}\geq 0\end{aligned}}}$

この方程式は、$\displaystyle z_{1}}$線形計画問題から。

このプロセスが完了すると、実行可能領域は次の形式になります。

${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} ,\,\forall \ x_{i}\geq 0}$

また、ランクが${\displaystyle \mathbf {A} }$は行数です。これにより、一般性が失われることはありません。そうでなければ、システム${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$冗長な方程式があり、それを削除できるか、システムが矛盾しており、線形計画法に解がない。^{[ 17 ]}

標準形式の線形計画問題は、次の形式のタブローとして表すことができる。

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\\mathbf {0} &\mathbf {A} &\mathbf {b} \end{bmatrix}}}$

最初の行は目的関数を定義し、残りの行は制約条件を指定します。最初の列のゼロは、ベクトルと同じ次元のゼロベクトルを表します。${\displaystyle \mathbf {b} }$（著者によって正確なレイアウトに関する慣例が異なる）。列が${\displaystyle \mathbf {A} }$次数 の単位行列を含むように並べ替えることができる${\displaystyle p}$（行数${\displaystyle \mathbf {A} }$) の場合、タブローは標準形であると言われます。^{[ 18 ]}単位行列の列に対応する変数は基本変数と呼ばれ、残りの変数は非基本変数または自由変数と呼ばれます。非基本変数の値を 0 に設定すると、基本変数の値はエントリとして簡単に得られます。${\displaystyle \mathbf {b} }$そしてこの解は基本的な実行可能解です。ここでの代数的解釈は、各行で表される線形方程式の係数が次のいずれかであるということです。${\displaystyle 0}$、${\displaystyle 1}$、または他の数値。各行には${\displaystyle 1}$値を持つ列${\displaystyle 1}$、${\displaystyle p-1}$係数を含む列${\displaystyle 0}$、そして残りの列には他の係数（これらの他の変数は非基本変数を表します）が含まれます。非基本変数の値をゼロに設定することで、各行で、で表される変数の値が${\displaystyle 1}$その列は${\displaystyle b}$その行の値。

逆に、基本的な実行可能解が与えられた場合、非ゼロ変数に対応する列は非特異行列に展開できる。${\displaystyle B}$対応するタブローに逆数を掛けると、${\displaystyle B}$すると、結果として正統的な形式のタブローが得られる。^{[ 19 ]}

させて

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} _{B}^{T}&-\mathbf {c} _{D}^{T}&0\\0&I&\mathbf {D} &{\widehat {\mathbf {b} }}\end{bmatrix}}}$

正統的な形式のタブローである。${\displaystyle {\widehat {\mathbf {b} }}=B^{-1}\mathbf {b} }$目的関数から係数c T Bを除去するために、追加の行追加変換を適用できます。このプロセスはプライシングアウトと呼ばれ、正準表が得られます。 

${\displaystyle {\begin{bmatrix}1&0&-{\bar {\mathbf {c} }}_{D}^{T}&z_{B}\\0&I&\mathbf {D} &{\widehat {\mathbf {b} }}\end{bmatrix}}}$

ここで、z _Bは対応する基本実行可能解における目的関数の値です。更新された係数（相対コスト係数とも呼ばれる）は、非基本変数に関する目的関数の変化率です。^{[ 14 ]}

基本実行可能解から隣接する基本実行可能解へ移動する幾何学的操作は、ピボット操作として実装されます。まず、非基本列で非ゼロのピボット要素を選択します。この要素を含む行にその逆数を掛けてこの要素を 1 に変更し、次にその行の倍数を他の行に追加して列の他のエントリを 0 に変更します。結果として、ピボット要素がr行にある場合、その列は単位行列のr番目の列になります。この列の変数は基本変数となり、操作前の単位行列のr番目の列に対応していた変数と置き換わります。実際には、ピボット列に対応する変数が基本変数の集合に入り、入ってくる変数と呼ばれ、置き換えられる変数は基本変数の集合から出てきて、出ていく変数と呼ばれます。タブローは依然として標準形ですが、基本変数の集合が 1 つの要素だけ変更されています。^{[ 13 ] [ 14 ]}

線形計画問題が標準タブローで与えられるとする。シンプレックス法は、それぞれ改善された基本実行可能解を与える連続的なピボット操作を実行することによって進行する。各ステップにおけるピボット要素の選択は、主にそのピボットが解を改善するという要件によって決定される。

以下のセクションでは、目的関数の最大値を求めることに焦点を当てます。最小値を求める場合は、目的関数へのすべての参照を否定することでアルゴリズムを修正できます。

一般に、線形計画問題は標準形式では与えられず、シンプレックス法を開始する前に、等価な標準タブローを見つける必要があります。これは、人工変数を導入することで実現できます。単位行列の列は、これらの変数の列ベクトルとして追加されます。制約方程式の b の値が負の場合、単位行列の列を追加する前に方程式を負にします。これにより、実行可能解の集合や最適解は変更されず、スラック変数が初期実行可能解を構成することが保証されます。新しいタブローは標準形式ですが、元の問題とは等価ではありません。そこで、人工変数の合計に等しい新しい目的関数が導入され、最小値を見つけるためにシンプレックス法が適用されます。修正された線形計画問題は、フェーズ I問題と呼ばれます。^{[ 23 ]}

フェーズ I の問題に適用されるシンプレックス アルゴリズムは、新しい目的関数が非負変数の合計であるため、その値が 0 で下限が定められていることから、最小値で終了する必要があります。最小値が 0 の場合、結果として得られる正準表から人工変数を削除して、元の問題と同等の正準表を作成できます。次に、シンプレックス アルゴリズムを適用して解を見つけることができます。このステップはフェーズ IIと呼ばれます。最小値が正の場合、人工変数がすべてゼロであるフェーズ I の問題には実行可能な解がありません。これは、元の問題の実行可能領域が空であることを意味し、したがって元の問題には解がありません。^{[ 13 ] [ 14 ] [ 24 ]}

線形計画問題を解くための他のアルゴリズムについては、線形計画法の記事で説明されています。別の基底交換ピボットアルゴリズムは、交差アルゴリズムです。^{[ 41 ] [ 42 ]}線形計画法には、内点法を使用する多項式時間アルゴリズムがあります。これには、Khachiyanの楕円体アルゴリズム、Karmarkarの射影アルゴリズム、およびパス追跡アルゴリズムが含まれます。^{[ 15 ]} Big -M 法は、単相シンプレックスを使用して線形計画問題を解くための代替戦略です。Cohen ら^{[ 43 ]}は、高速行列乗算アルゴリズムを線形計画法に適用するアルゴリズムのブランチの代表例です。

線形分数計画法(LFP) は、線形計画法(LP)の一般化です。LP では目的関数は 線形関数ですが、線形分数計画法の目的関数は 2 つの線形関数の比です。言い換えれば、線形計画法は、分母が常に 1 の定数関数である分数線形計画法です。線形分数計画法は、シンプレックス法の変種^{[ 44 ] [ 45 ] [ 46 ] [ 47 ]}またはクロス法^{[ 48 ]}で解くことができます。

これらの入門書は、コンピュータサイエンスとオペレーションズリサーチを学ぶ学生向けに書かれています。

• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。『アルゴリズム入門』第2版。MIT PressおよびMcGraw-Hill、2001年。ISBN 0-262-03293-7セクション 29.3: シンプレックス法、 790 ～ 804 ページ。
• フレデリック・S・ヒリアーおよびジェラルド・J・リーバーマン：オペレーションズ・リサーチ入門、第8版。マグロウヒル。ISBN 0-07-123828-X
• Rardin, Ronald L. (1997).オペレーションズリサーチにおける最適化. Prentice Hall. p.  919. ISBN 978-0-02-398415-0。

• ジョージア工科大学のスパイロス・レベリオティスによる「線形計画法とシンプレックス法入門」 。
• グリーンバーグ、ハーベイ・J.、「クリー・ミンティ多面体はシンプレックス法の指数関数的な時間複雑性を示す」コロラド大学デンバー校（1997年）PDFダウンロード
• シンプレックス法シンプレックス法のチュートリアル（例付き）（2段階法とM法も含む）。
• Mathstoolsのシンプレックス計算機（www.mathstools.comより）
• ウィスコンシン大学ホワイトウォーター校のトーマス・マクファーランドによる、標準的な線形計画問題に対するシンプレックス法の例。
• PHPSimplex：線形計画問題を解くためのオンラインツール マラガ大学（UMA、スペイン）のダニエル・イズキエルド氏とフアン・ホセ・ルイス氏による開発
• simplex-mオンラインシンプレックスソルバー