しんぷれっくすほうとは? わかりやすく解説

Weblio 辞書 > 学問 > 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最適性判定

(1) c_{N(s)}>0\,となる添字s (1\le s \le n)1つ選ぶ.
(2) もし, そのような添字なければ, 現在の基底解最適となり, 終了する.


ステップ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\,存在する場合, ステップ3へ.


ステップ3((r, s\,)を中心とするピボット演算を行う)

(1)辞書r\,番目の式についてx_{N(s)}\,表現式を求める.
(2)求めたx_{N(s)}\,の式を辞書の他の行 (i\not = r\,) に代入する.
(3)添字N(s)\,B(r)\,交換し, ステップ1へ.


実行可能解をもつ問題に対して単体法有限回で終了すれば, その問題最適解をもつか, または非有界である. しかし, 辞書右辺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 21977), 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事典」の他の用語
線形計画:  NP困難  アフィン変換法  カーマーカー法  シンプレックス法  ポテンシャル関数  中心パス  主双対内点法



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

辞書ショートカット

すべての辞書の索引

「しんぷれっくすほう」の関連用語

しんぷれっくすほうのお隣キーワード
検索ランキング

   

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



しんぷれっくすほうのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.

©2025 GRAS Group, Inc.RSS