コラム・特集

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

IEハンドブック
第14部 インダストリアル・エンジニアリングの最適化

第2章 線形計画法

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

シンプレックス・アルゴリ ズムは,1947年 G.B.Danzigによって開発されたLP問題を解くための逐次解法である。シンプレックス・アルゴリズムの理論や,各種の計算法の改良については,次の代表的な教科書に詳しく書かれている(Dantzig,Murty,Phillips他, Gass,Hadley)。この章ではシンプレックス法の基本的原理を簡単に述べよう。

例題14.2.2 次のLP問題を考える。

目的関数:Z=40×1+36×2→最小化
制約条件:
x1く 8
x2く10
5×1+3×2>45
x1>0, x2>0

ここでは,すべての制約条件を満足し,目的関数に最小値を与えるような変数x1,x2の値を決めることが問題 となる。この問題を解く第1ステップとして,非負でしかも制約条件を満たすようなx1,x2のすべての可能な値を考えてみよう。たとえば,x1=8,×2=10という解は正であるし,すべての制約を満足している。このような解は「許容解」とよばれている。またすべての許容解の集合を「許容領域」とよぶ。LPの解は,許容領域 内で最良許容解を見つけることに他ならない。最良許容解はLP問題の「最適解」とよばれる。例題では最適解は,目的関数40×1+36×2を最小化する許容解である。最適解を取ったときの目的関数の値は,LP問題の「最適値」とよばれる。

グラフ上に許容領域を示すために,すべての制約を描き入れると,この制約条件式を満足するx1,x2の領域がわかる。非負制約は2つの許容値が第一象限内に存在することを表わしている。

制約条件5×1+3×2≧ 45は, x1,x2のどの許容解も直線5×1+3κ2=45より上に存在することを示している(図表14.2.2を参照のこと)。同じようにして,x1≦ 8,x2≦ 10を書き入れることができる。許容領域は,図表14.2.2に示すようにABCで囲まれた影をつけた部分で与えられる。この領域の中に無数の許容点が存在するのは明らかである。この問題の目的は,Zが最小値を取るような許容点を見つけることである。許容点A,B,Cは許容領域の「端点」とよばれる。

初めからZをある値に固定すると,Z=40×1+36×2 で与えられる目的関数は直線になる。Zを じょじょに変 化させていくと,その直線はもとの直線に平行に移動していく。最適解を求めるには,まず,許容領域内の1点,または複数個の点を通るようにZの値を適当に決めて,目的関数の直線を引く。最初のZは600で描かれている。この直線を原点に近づけていくと,Zの値はだんだん小さくなる(図表14.2.2)。このような直線40×1+36×2 =Zの平行移動は,許容領域ABC内の少なくとも1点が含まれている限り続けられ,最後には最小点に達する。

明らかにx1=8,×2=16の端点Aにおいて最小値に達している。この点がZの最小値377.60を 実現する最良許容点である。

したがってx1=8,×2=16がこの線形計画問題の最適解であり,Z=37760が最適値である。

この例では許容領域の端点の1つ (すなわちA点)が最適解となっている。一般的にいうと,すべてのLP問題において次の性質が成立する.もし,あるLP問題に最適解が存在しいるならば,許容領域内の端点のうち少なくとも1点が常に最適解になり得る。

このことは,シンプレックス法によりLP問題を解く上での基本的な性質である LP問題の許容領域が無限の点を含むとしても,許容領域内の有限個の端点だけを吟味することによって,最適解を決定することができる。LP用語では端点の許容解は「許容基底解として知られている。そこで一般のLP問題を解くためのシンプレックス法とは,次々に異なった許容基底解を見つけ出し, 吟味する手順であるといってよい。2変数だけの問題であればグラフ上で簡単に許容領域を表わし,許容基底解である端点を確認きる。実際にはLP問題には,何百もの制約条件があり,何千もの変数が含まれているので, 許容基底解を算出する代数的な手順が必要となるわけである。シンプレックス法では許容基底解を算出するのに, 古典的なガウスージョルダンの消去法を用いている。ガウスージョルダンの消去法はベクトルー行列演算の繰り返しであり,コンピュータを用いれば簡単に計算できる。

シンプレックス法の一般的な手順は次のようになる。

1.初めに初期許容基底解を決める。
2.よりよい目的関数値を持つ別の許容基底解を見つけることができれば,初期解を更新する。この手順によって,目的関数値が現在得られている目的関数値より悪い許容基底解は,すべて実質的には考慮しないで済むことになる。このことがすべての許容基 底解を調べるという幼稚な方法に比べて,この計算手順をより効率のよいものにしていることになる。
3.目的関数の値を改善することにより,さらによい 許容基底解を探索し続ける。もしある特定の許容基底解から,もうそれ以上更新することができなくなった場合には,それが最適解となリシンプレックス法は終わる。

シンプレックス法計算の効率
シンプレックス法の計算の効率は,(1)最適解に到達するまでの繰り返し回数(許容基底解の数)と,(2)問題を解くための総計算時間,によって決まる。問題中の制約条件式や,決定変数の数に関連させた計算効率の研究には,多くの努力がはらわれてきた。

多くの実際問題を解いてみた経験によると,制約条件 式数がm本,変数の数がn個である一般の線形計画問題での繰り返し回数は,mから3mの間であり,その平均値は2mとなっている。繰り返し回数の実際の上限は, 2(m+n)である(場合によっては,いくつかの問題では,この限界を超えることがある)。

計算時間はおおよそ問題の制約式の数の3乗 (m3) に比例して変わることが分かっている。たとえば,問題Aには問題Bの2倍の制約式があるとすれば,Aに要する計算時間はBの8倍程度になる。

シンプレックス法の計算効率は,変数の数よりも制約式の数に,より敏感であるということに注意しておこう。そこで一般的にLP問題の定式化にあたっては,冗長な制約式を避けることにより,制約条件式数をできるだけ少なくすることを奨める。

Cutlerと Wolfeの研究によって,シンプレックス法による計算の特性がまとめられている。そこでは30変種のシンプレックス・アルゴリズムを用いて,9個のLP問題を解いた計算結果が示されている。その集計の中には,変種ごとの効率の比較や,LPの計算機コードの効率に関する重要な特徴などが示されている。

シンプレックス法の多くの変種に関する研究について は,読者はBarnesと Grispを参照するとよい。

 本コラムは絶版となっている「IEハンドブック(サルベンティ編・日本能率協会訳・1986)」をアーカイブとして掲載するものです。このハンドブックの各章は多くの事例と理論を通して生産性向上に対するアイデアを提供するべく専門家によって執筆されています。基盤をなしているIEの考え方・原則はインダストリアル・エンジニアリングにかかわるすべてのひとに有用でしょう。

関連記事一覧

2019ものづくり公開セミナーガイド

B2Bデジタルマーケティングセミナー

ものづくり人材育成ソリューション

マーケティング分野オンラインセミナー