simplex methodとは何？わかりやすく解説 Weblio辞書

シンプレックス法

概要

単体法と訳され, 1947年, ダンツィク(G.B. Dantzig) によって提案された,線形計画問題を解くための手法.理論的には有限回反復での収束性しか示されていないが,実用的には高速に最適解が得られることが知られている.また, 実用の際には, 単体法を改良した改訂単体法が良く用いられる.

詳説

　ダンツイック（G. B. Dantzig）によって提案された単体法（simplex method）（シンプレックス法）は, カーマーカー法の出現する 1984年までは線形計画問題を解くもっとも有効な解法とされていた. 単体法は問題の構造を巧妙に利用しており, いまでも, 線形計画, 整数計画, 組合せ最適化の多くの分野で使われている[2, 3, 4]. 以下, 次のような基準形と呼ばれる線形計画問題を考えることにする.

$\mbox{(P)} \quad \begin{array}{lll} & \mbox{max.} & {\displaystyle \sum_{j=1}^{n}c_j x_j} \\ & \mbox{s. t.} & {\displaystyle \sum_{j=1}^{n}a_{ij} x_j} \leq b_i \; \; (i=1,2,\ldots,m), x_1,x_2,\ldots ,x_n \geq 0. \end{array}$

ここで, $c_j \,(j=1,2,\ldots,n), \, b_i \, (i=1,2,\ldots,m),\, a_{ij} \, (i=1,2,\ldots,m, j=1,2,\ldots,n)$ は実数, $\boldsymbol{x}=(x_1,x_2,\ldots,x_m)$ は $n\,$ 個の変数からなる $n\,$ 次元ベクトルである. すべての線形計問題は, 簡単な変換によって基準形に帰着できる. 問題（P）の制約条件を満たす $\boldsymbol{x}$ を実行可能解（feasible solution）, その集まりを実行可能多面体（feasible polyhedron）と呼ぶ. 実行可能解のなかで目的関数を最大にするものを最適解（optimal solution）と呼ぶ.

　ここで, 問題（P）にスラック変数と呼ばれる非負の変数 $x_{n+i} \, (i=1,\ldots,m)$ を導入する

$\begin{array}{ll} \mbox{max.} & c_1 x_1+\cdots+ c_nx_n \\ \mbox{s. t.} & a_{i1} x_1 +\cdots+a_{in} x_n + x_{n+i} = b_i \; \; (i=1, 2, \ldots, m), \\ & x_1 \geq 0,\ldots,x_{n+m}\geq 0. \end{array}$

さらに, 目的関数を $z=c_0+\sum_{j=1}^n c_j x_j \ (c_0=0)$ と書き, 制約式左辺のスラック変数以外の項を移行すると, 上の問題は以下のようになる.

$\begin{array}{ll} \mbox{max.} & z \\ \mbox{s. t.} & x_{n+i}= b_i-a_{i1}x_{1}-\cdots-a_{in}x_{n} \quad (i=1, 2, \ldots, m), \\ & z=c_0+c_1 x_1+\cdots+c_n x_n, \\ & x_1 \geq 0,\ldots, x_{n+m} \geq 0. \end{array}$

制約式の左辺の変数を基底変数, 右辺の変数を非基底変数と呼ぶ. ここで, 非基底変数の添字を $N(1)=1,\ldots,N(n)=n$ , 基底変数の添字を $B(1)=n+1,\ldots,B(m)=n+m$ とおき, 各変数の係数の添字も対応するものにする.　非基底変数の値を任意に固定すると基底変数の値は一意に定まるが,　特に非基底変数をすべて $0\,$ に固定して得られる解を基底解（basic solution）と呼ぶ. また, 上の等式系を辞書と呼ぶ. 係数 $b_i \, (i=1,\ldots,m)$ が非負のとき, 基底解は実行可能解であるが, このような辞書を実行可能辞書と呼ぶ. 線形計画問題の実行可能な基底解は実行可能多面体の頂点に対応する [3]. 単体法は目的関数の値を最大化する実行可能な基底解を求めるものであり, 辞書を等価な辞書へと繰り返し変換することによって実現される.

単体法

入力：実行可能な辞書

ステップ１（最適性判定）

(1) $c_{N(s)}>0\,$ となる添字 $s (1\le s \le n)$ を1つ選ぶ.

(2) もし, そのような添字がなければ, 現在の基底解は最適となり, 終了する.

ステップ２（有界性判定）

(1) $\textstyle \frac{b_r}{a_{rN(s)}}=\min\{\frac{b_i}{a_{iN(s)}} : a_{iN(s)}>0, 1 \le i \le m \}$ を計算し, 行番号 $r\,$ を求める（この操作は現在の基底解から実行可能性を保ったまま非基底変数 $x_{N(s)}\,$ だけをできる限り増加させる）.

(2) そのような番号 $r\,$ がなければ（つまり, 変数 $x_{N(s)}\,$ を限りなく増加させることができる）, 問題は非有界となり, 終了する.

(3) $r\,$ が存在する場合, ステップ３へ.

ステップ３（（ $r, s\,$ ）を中心とするピボット演算を行う）

（1）辞書の $r\,$ 番目の式について $x_{N(s)}\,$ の表現式を求める.

（2）求めた $x_{N(s)}\,$ の式を辞書の他の行 ( $i\not = r\,$ ) に代入する.

（3）添字 $N(s)\,$ と $B(r)\,$ を交換し, ステップ１へ.

実行可能解をもつ問題に対して単体法が有限回で終了すれば, その問題は最適解をもつか, または非有界である. しかし, 辞書の右辺に $0\,$ の定数 $b_i\,$ を少なくとも1つ含むとき, 辞書は退化しており, 単体法は有限回で終わるとは限らない. このとき, ピボット演算を施しても, 基底解が変化しないことになり, 目的関数値も変化しない. 有限回収束を保証するための手段として, Blandのピボット選択規則 [1] が提案されており, これを用いると単体法は必ず有限回で収束する.

　先の説明で述べたように, 単体法の入力として実行可能な辞書が必要とされる. 現在の辞書が実行可能でない場合, 単体法を用いて実行可能な辞書を求めることができる. そのため, 新しい変数（人工変数） $x_a\,$ を用いて補助問題

$\begin{array}{ll} \mbox{max.} & -x_a \\ \mbox{s. t.} & x_{n+i}= b_i-a_{i1}x_{1}-\cdots-a_{in}x_{n}+x_a \; \; (i=1, 2, \ldots, m), \\ & x_1 \geq 0,\ldots, x_{n+m} \geq 0, \; x_a \geq 0, \end{array}$

を作る. 元問題が実行可能であることと補助問題の最適目的関数値が $0\,$ であることは等価なので, 補助問題を解くことにより, 元問題の実行可能解の有無を判定できる.

　一般に, 基準形の線形計画問題を解く際には, 2段階単体法と呼ばれるものを用いる. 第1段階では, 補助問題を解き, 実行可能解の有無を判定し, 実行可能解が存在する場合は実行可能辞書を求める. 第2段階では, 求めた実行可能辞書を初期の辞書として, もう一度単体法を使い, 元問題を解く.

参考文献

[1] R. G. Bland, "New finite pivot ruless for the simplex method", Mathematics of Operations Research 2（1977）, 103-107.

[2] V. Chvátal, Linear Programming, W. H. Freeman and Company, 1983.

[3] G. B. Dantzig, Linear Programming and Extensions, Princeton Univesity Press, 1963.

[4] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1988.

単体法

読み方：たんたいほう
【英】：simplex method

概要

1947年, ダンツィク(G.B. Dantzig) によって提案された,線形計画問題を解くための手法.理論的には有限回反復での収束性しか示されていないが,実用的には高速に最適解が得られることが知られている.また, 実用の際には, 単体法を改良した改訂単体法が良く用いられる.

詳説

　ダンツイック（G. B. Dantzig）によって提案された単体法（simplex method）（シンプレックス法）は, カーマーカー法の出現する 1984年までは線形計画問題を解くもっとも有効な解法とされていた. 単体法は問題の構造を巧妙に利用しており, いまでも, 線形計画, 整数計画, 組合せ最適化の多くの分野で使われている[2, 3, 4]. 以下, 次のような基準形と呼ばれる線形計画問題を考えることにする.

　ここで, 問題（P）にスラック変数と呼ばれる非負の変数 $x_{n+i} \, (i=1,\ldots,m)$ を導入する

$\begin{array}{ll} \mbox{max.} & c_1 x_1+\cdots+ c_nx_n \\ \mbox{s. t.} & a_{i1} x_1 +\cdots+a_{in} x_n + x_{n+i} = b_i \; \; (i=1, 2, \ldots, m), \\ & x_1 \geq 0,\ldots,x_{n+m}\geq 0. \end{array}$

さらに, 目的関数を $z=c_0+\sum_{j=1}^n c_j x_j \ (c_0=0)$ と書き, 制約式左辺のスラック変数以外の項を移行すると, 上の問題は以下のようになる.

単体法

入力：実行可能な辞書

ステップ１（最適性判定）

(1) $c_{N(s)}>0\,$ となる添字 $s (1\le s \le n)$ を1つ選ぶ.

(2) もし, そのような添字がなければ, 現在の基底解は最適となり, 終了する.

ステップ２（有界性判定）

(2) そのような番号 $r\,$ がなければ（つまり, 変数 $x_{N(s)}\,$ を限りなく増加させることができる）, 問題は非有界となり, 終了する.

(3) $r\,$ が存在する場合, ステップ３へ.

ステップ３（（ $r, s\,$ ）を中心とするピボット演算を行う）

（1）辞書の $r\,$ 番目の式について $x_{N(s)}\,$ の表現式を求める.

（2）求めた $x_{N(s)}\,$ の式を辞書の他の行 ( $i\not = r\,$ ) に代入する.

（3）添字 $N(s)\,$ と $B(r)\,$ を交換し, ステップ１へ.

　先の説明で述べたように, 単体法の入力として実行可能な辞書が必要とされる. 現在の辞書が実行可能でない場合, 単体法を用いて実行可能な辞書を求めることができる. そのために, 新しい変数（人工変数） $x_a\,$ を用いて補助問題

$\begin{array}{ll} \mbox{max.} & -x_a \\ \mbox{s. t.} & x_{n+i}= b_i-a_{i1}x_{1}-\cdots-a_{in}x_{n}+x_a \; \; (i=1, 2, \ldots, m), \\ & x_1 \geq 0,\ldots, x_{n+m} \geq 0, \; x_a \geq 0, \end{array}$

参考文献

[1] R. G. Bland, "New finite pivot ruless for the simplex method", Mathematics of Operations Research 2（1977）, 103-107.

[2] V. Chvátal, Linear Programming, W. H. Freeman and Company, 1983.

[3] G. B. Dantzig, Linear Programming and Extensions, Princeton Univesity Press, 1963.

[4] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1988.

「OR事典」の他の用語

非線形計画：	劣勾配勾配勾配法単体法双対定理双対性のギャップ双対性理論
線形計画：	分離問題半正定値計画半正定値計画緩和単体法双対問題双対定理同次自己双対内点法

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

シンプレックス法

(simplex method から転送)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/08/24 09:42 UTC 版)

ナビゲーションに移動検索に移動

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

この記事には複数の問題があります。改善やノートページでの議論にご協力ください。

出典がまったく示されていないか不十分です。内容に関する文献や情報源が必要です。（2015年10月）
脚注による出典や参考文献の参照が不十分です。脚注を追加してください。（2017年11月）

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

概要

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

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

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

アルゴリズム

この節の加筆が望まれています。

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

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

参考文献

William H. Press（著）、William T. Vetterling（著）、Saul A. Teukolsky（著）、Brian P. Flannery（著）、丹慶勝市（翻訳）、佐藤俊郎（翻訳）、奥村晴彦（翻訳）『ニューメリカルレシピ・イン・シー日本語版―C言語による数値計算のレシピ』技術評論社、1993年6月1日。ISBN 978-4874085608。
水野眞治, 『シンプレックス法の巡回とその回避』
松井知己, 『Bland の最小添字規則の有限性 -単体法の非巡回ピヴォット規則- 』

外部リンク

ASCII.jpデジタル用語辞典『シンプレックス法』 - コトバンク
世界大百科事典『線形計画法』 - コトバンク
ブリタニカ国際大百科事典小項目事典『ダンツィーク』 - コトバンク

アルゴリズム

ソート

比較ソート	バブルソート選択ソート挿入ソートシェルソートクイックソートマージソートヒープソートシェーカーソートコムソートノームソート図書館ソートイントロソート奇偶転置ソート
線形時間ソート	鳩の巣ソート基数ソートバケットソート
並行ソート	ソーティングネットワークバッチャー奇偶マージソートシェアソート
非効率的	ボゴソートストゥージソート
グラフ	トポロジカルソート

探索

リスト	線形探索二分探索
木・グラフ	幅優先探索最良優先探索均一コスト探索 A* 深さ優先探索反復深化深さ優先探索深さ制限探索双方向探索分枝限定法
文字列	クヌース–モリス–プラット法ボイヤー-ムーア法エイホ–コラシック法ラビン-カープ法 Bitap法

最短経路問題

最小全域木

最大フロー問題
最小カット問題

線型計画問題

順序統計量

種類

その他

カテゴリ

数理最適化 • 最適化問題 : メソッド • ヒューリスティクス

非線形(無制約)

… 関数　

勾配法

収束性（英語版）	信頼領域ウルフ条件（英語版）
準ニュートン法	BFGS法ブロイデン法 L-BFGS（英語版） DFP（英語版）対称ランク1法（英語版）
その他の求解法	ガウス・ニュートン法最急降下法レーベンバーグ・マルカート法（英語版）共役勾配法（非線形共役勾配法）切り捨てニュートン法（英語版）

… ヘッセ行列

最適化におけるニュートン法（英語版）

非線形(制約付き)

一般	バリア関数ペナルティ関数法（英語版）
微分可能	ラグランジュの未定乗数法逐次二次計画法連続線形計画（英語版）

凸最適化

凸縮小化

線型および
二次

内点法	カチヤン楕円体法カーマーカーの投影アルゴリズム
ベイズ-交換	単体法改訂シンプレックス法（英語版）十字法（英語版）レムケの主ピボット操作法（英語版）

組合せ最適化

系列範例
(Paradigms)

グラフ理論

最小全域木	ベルマン–フォード法ブルーフカ法ダイクストラ法ワーシャル–フロイド法ジョンソン法（英語版）クラスカル法
最大フロー問題	Dinic法（英語版）エドモンズ・カープフォード・ファルカーソンプッシュリラベル最大流アルゴリズム（英語版）

メタヒューリスティクス

カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）

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

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

Weblio日本語例文用例辞書

索引トップ用語の索引ランキング

「simplex method」の例文・使い方・用例・文例

「資格商法」とは文字通りには「qualification selling method」という意味であり、根拠のない資格や学位を法外な値段で売る詐欺的ビジネスである。

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。

>> 「simplex method」を含む用語の索引
simplex methodのページへのリンク


	Copyright (C) 2025 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアのシンプレックス法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
TANAKA Corpus	Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います： Creative Commons Attribution (CC-BY) 2.0 France.
京大-NICT 日英中基本文データ	この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
	Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
	Copyright © Benesse Holdings, Inc. All rights reserved.
	Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
	日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved. WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
	Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved. 「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
	This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

simplex methodとは？わかりやすく解説

シンプレックス法

概要

詳説

単体法

概要

詳説

シンプレックス法

目次

概要

アルゴリズム

参考文献

外部リンク

「simplex method」の例文・使い方・用例・文例

「simplex method」の関連用語

simplex methodとは？ わかりやすく解説

シンプレックス法

概要

詳説

単体法

概要

詳説

シンプレックス法

概要

アルゴリズム

参考文献

外部リンク

「simplex method」の例文・使い方・用例・文例

「simplex method」の関連用語

simplex methodとは？わかりやすく解説