📑 Table of Contents▼
曖昧さ回避 この項目では、線型計画問題を解くアルゴリズムについて説明しています。非線型最適化問題のNelderとMeadによる滑降シンプレックス法 (downhill simplex method)については「ネルダー–ミード法」をご覧ください。

シンプレックス法（シンプレックスほう、単体法、たんたいほう、英語: simplex method）は、1947年にジョージ・ダンツィーク（ダンツィク）が提案した、線型計画問題を解くアルゴリズムの中で最も広く使用されている方法である。線型計画法の1つ。

シンプレックス法は、実行可能解（超多面体の頂点）の1つから出発して目的関数の値をなるべく大きく（小さく）するようなところに移動させていく動作を繰り返して最適解を見つけ出す方法である。各ステップで必ず目的関数の値は改善される。

このアルゴリズムは、実用上は高速であり、変数の数・条件式の数の大きな方のオーダーの回数だけ反復を繰り返せばほとんど常に最適解に達する。このことは、1982年に スティーヴン・スメイル (Stephen Smale) が証明した。シンプレックス法は、用いるピボット規則により性能が左右される。有限回のピボットで終了することが保証されている規則として、Blandの提案した最小添字規則が知られている[1]。ダンツィクの提案したピボット規則は問題の規模にたいして指数時間かかる問題例があることが知られている。現在のところ、線型計画問題を多項式時間で解くピボット規則の存在性は未解決問題である。

単体法という名前は、ダンツィクが提案した特殊な図解法においては、アルゴリズムの進行に従って単体が下に落ちていくように見えることに由来する。

アルゴリズム

編集

一般的な流れは以下のとおりである。

  1. 線型計画問題を制限標準型に変形する。
    1. スラック変数を加え、標準型に変形する。制約条件のうち、不等式を含む物がなくなり、全て等式となる。
    2. 人工変数を加え、制限標準型に変形する。等式化された問題の目的関数を とおく。 を最大化（最小化）する線型計画問題にする。
  2. ここまで行った作業を基にシンプレックス表（Simplex Tableau、線型計画問題の係数を表にまとめたもの）を作成する。
  3. 式の数だけ基底変数を定める。目的関数 は必ず基底変数に選ばなければならない。
  4. 初期の基底変数から得られた連立方程式の解が最適かどうかを調べる。最適とみなすことができた場合は終了。終了しなかった場合は以下の作業をおこなう。
  5. 基底変数と非基底変数の組合せを変更する。
    1. 新たに基底変数にできそうな変数を非基底変数の中から選ぶ。複数存在する場合は、最も効果の高い変数を基底に選ぶ（ピボット列の決定）
    2. 基底から追い出す変数を決める。増加限界（定数項の値から新たに基底に入れる変数の係数を割ったもの）によって変数を決めることが多い。（ピボット行の決定）
    3. 新しい基底変数での連立方程式を解く。具体的にはピボットを中心に掃き出し法などで新たな実行可能解を求める。実行後は4.に戻り、同様の処理を繰り返す。

掛谷宗一とシンプレックス法

編集

掛谷宗一はダンツィークよりも早くこのアルゴリズムを発見していたようである[2]。掛谷が1913年から翌1914年にかけて出版した積分方程式に関する研究にはこの方法が用いられていた。この結果により掛谷は1928年に日本帝国学士院恩賜賞を授かった。

河田龍夫は次のエピソードを残している[2][3]。

1944年、軍の威信をかけて開設された統計数理研究所の草案を作るときのことであった。河田は掛谷の自宅に通い、掛谷とともに構想を練り、文部省に出す文書を作成していた。

あるとき掛谷は配給制度について語った。

人によって物の価値は異なる。無類の酒好きである掛谷にとって酒の価値は大きいが、砂糖はそれほどでもない。東京都全体で配給すべき、酒、砂糖、味噌、煙草等の量が定まっている。各人にとっての価値を適当に仮定して、全員の総価値を最大にするには、どう配分するべきか？

河田によれば、掛谷はこの問題から線形計画の問題を定式化し、そして凸体（英語版）の方法で解いた。掛谷はこの方法の名人で、掛谷の解法は今でいうシンプレックス法であった、と河田は書いている。

脚注

編集
[脚注の使い方]
  1. ^ 今野浩 1987, pp. 39–42.
  2. ^ a b ヴァンソン・ボレリ、ジャン-リュック・リュリエール 著、庵原謙治、庵原優子 訳『微積分のこころに触れる旅 : 掛谷の問題に導かれて』日本評論社、2019年、157-158頁。ISBN 978-4-535-78896-1。 
  3. ^ 佐々木 重夫『東北大学数学教室の歴史』東北大学数学教室同窓会、1984年、119頁。NDLJP:12112946。 

参考文献

編集
  • 今野浩『線形計画法』日科技連、1987年3月1日。ISBN 978-4817150141。 
  • William H. Press（著）、William T. Vetterling（著）、Saul A. Teukolsky（著）、Brian P. Flannery（著）、丹慶 勝市（翻訳）、佐藤 俊郎（翻訳）、奥村 晴彦（翻訳）『ニューメリカルレシピ・イン・シー 日本語版―C言語による数値計算のレシピ』技術評論社、1993年6月1日。ISBN 978-4874085608。 
  • 水野眞治 (2013年2月23日). “シンプレックス法の巡回とその回避” (pdf). 学習・研究用テキスト 線形計画法 (3A). 2024年11月22日時点のオリジナルよりアーカイブ。2025年3月4日閲覧。

外部リンク

編集
スタブアイコン

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

スタブアイコン

この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。

📚 Artikel Terkait di Wikipedia

ネルダー–ミード法

ネルダー–ミード法（ネルダー–ミードほう、英: Nelder–Mead method）や滑降シンプレックス法（英: downhill simplex method）やアメーバ法（英: amoeba method）は、最適化問題のアルゴリズム。導関数は不要。1965年に John A. Nelder

チミジンキナーゼ

235–72. (1990). PMID 1707295.  ^ a b c d “Sequence Analysis of Herpes Simplex Virus 1 Thymidine Kinase and DNA Polymerase Genes from over 300 Clinical

ゲーデル賞

A.; Teng, Shang-Hua (2004), “Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time”, J. ACM 51 (3): 385–463, arXiv:math/0212413

衝突判定

polyhedral objects. Early work by Ming C. Lin used a variation on the simplex algorithm from linear programming. The Gilbert-Johnson-Keerthi distance

トランスフェクション

thymidine kinase to thymidine kinase-deficient human cells by purified herpes simplex viral DNA”. Proc Natl Acad Sci USA 74 (4): 1590–4. (1977). doi:10.1073/pnas

ソラレン

psoralen-treated DNA by genetic recombination in human cells infected with herpes simplex virus”. Cancer Res. 41 (12 Pt 1): 5033-8. (1981). PMID 6272987.  ^ “Psoralens

十文字法

また単体法も多面体の探索に平均でD回の反復かかるBorgwardt (1987): Borgwardt, Karl-Heinz (1987). The simplex method: A probabilistic analysis. Algorithms and Combinatorics (Study and Research

改訂単体法

改訂単体法（かいていたんたいほう、改訂シンプレックス法、英: Revised simplex method）とは、数理最適化に関するアルゴリズムの一種である。1954年にジョージ・ダンツィーグ・ウィリアム・オーチャード・ヘイズ（ドイツ語版）によって考案された線形計画問題を解くための解法であり、同じく