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

Weblio 辞書 > 学問 > OR事典 > simplex methodの意味・解説 
OR事典
索引トップ 用語の索引 ランキング カテゴリー
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会

シンプレックス法

読み方：しんぷれっくすほう
【英】：simplex method

概要

単体法と訳され, 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]. 以下, 次のような基準形と呼ばれる線形計画問題を考えることにする.


\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.

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

Weblio日本語例文用例辞書
索引トップ 用語の索引 ランキング
辞典・百科事典の検索サービス - Weblio辞書辞典・百科事典の検索サービス - Weblio辞書

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

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

英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

カテゴリ一覧

全て

＋ ビジネス

＋ 業界用語

＋ コンピュータ

＋ 電車

＋ 自動車・バイク

＋ 船

＋ 工学

＋ 建築・不動産

＋ 学問

＋ 文化

＋ 生活

＋ ヘルスケア

＋ 趣味

＋ スポーツ

＋ 生物

＋ 食品

＋ 人名

＋ 方言

＋ 辞書・百科事典

すべての辞書の索引

あいうえお
かきくけこ
さしすせそ
たちつてと
なにぬねの
はひふへほ
まみむめも
やゆよ
らりるれろ
わをん
がぎぐげご
ざじずぜぞ
だぢづでど
ばびぶべぼ
ぱぴぷぺぽ
ＡＢＣＤＥ
ＦＧＨＩＪ
ＫＬＭＮＯ
ＰＱＲＳＴ
ＵＶＷＸＹ
Ｚ
１２３４５
６７８９０
記号

Weblioのサービス

「simplex method」の関連用語

1
シンプレックス法
OR事典
14% |||||

2
単体法
OR事典
14% |||||

3
線形計画
OR事典
10% |||||

4
受賞論文
ウィキペディア小見出し辞書
4% |||||

5
ゲーデル賞
百科事典
4% |||||

6
衝突判定
百科事典
2% |||||

7
トランスフェクション
百科事典
2% |||||

8
上田実 (医学研究者)
百科事典
2% |||||

9
アカウキクサ属
百科事典
2% |||||

simplex methodのお隣キーワード

TSP多面体

U字型生産ライン

VR

VaR

simple leaf

simple life

simplex method

simplified language

Ε-近似アルゴリズム

かんばん方式

たたみ込み

たたみ込み法

アウトソーシング

検索ランキング

   

 英語⇒日本語
日本語⇒英語		    


simplex methodのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
TANAKA Corpus
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います：
 Creative Commons Attribution (CC-BY) 2.0 France.
京大-NICT 日英中基本文データ
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
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.
日本語WordNet日本語WordNet
日本語ワードネット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.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
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.

©2025 GRAS Group, Inc.RSS