コラム・特集

2.6 コンピュータによるLPの解法

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

第2章 線形計画法

2.6 コンピュータによるLPの解法

多くの実際問題をLPで定式化してみると,何千もの決定変数や何百もの制約条件式になってしまう。これらの膨大な計算にはコンピュータの利用が必要になる。シンプレックス法は繰り返し手順であるから,どんな問題に対しても機械的に適用することができる。したがって, シンプレックス法はコンピュータでの取り扱いに適しているといえる。

シンプレックス法は1947年に開発されたのだが,1951年までにはまだ公式に発表されていなかった。したがって,コンピュータによるLP問題の解は1952年までは現われなかった。

第1世代のコンピュータを使用した最初の成功例は, 1952年代の初期の(米国)規格標準局によるものである。

第1世代のコンピュータは真空管式で,現在のような大きいメモリーは持っていなかった。それらの計算機では100変数,50制約式を超えないような,小規模LP間題が解けただけであったし,また計算速度も遅かった。

たとえば10×20のLP問題を解くのに15分もかかった(現在ではこの規模の問題は1,2秒で解ける!)。このため LPの主要産業への広範な応用は,コンピュータ技術の発展を待たなければならなかった。LPの発展とその応用は,ほとんどコンピュータの発展に歩調を合わせて成し遂げられてきたといってもよい。

1950年代後半には第2世代のコンピュータが登場した。真空管に変わリトランジスタが使用され,コンピュータはより高速に作動するようになった。データの格納は磁気ディスクで行われるようになった。コンピュータによって2,000から3,000個の変数,300から400本の制約式を持つ程度の中規模のLP問題が解けるようになった。 この時期にはLPの産業界への応用も多く見られたが, 大規模な産業上の問題を解くには,なお第3世代コンピュータの登場を待たねばならなかった。

第3世代のコンピュータは1960年代に登場した。それには集積回路が用いられ,大きな磁気コアメモリーが使用されて,マルチプログラミングや,タイムシェアリングが可能になった。これらの特色によって計算速度は飛躍的に増え,何千もの制約式や無制限に近い決定変数を含む大規模LP問題も解けるようになった。これにより軍事,工業,商業,農業,教育,環境などのさまさまな分野で,LPが素晴らしい成功を収めることになった。

コンピュータ・コード
多くのコンピュータ製造業者や,主要コンピュータ・システムに対するLPソフトウエアを専門的に販売している私企業によって,商用LPコンピュータ・コードが提供されている。提供者の能力に応じて,これらのコードの複雑さや,使用の簡便さ,費用等が変わってくる。

大規模なLP問題を解く必要に迫まられて,複雑で高級なLPコンピュータ・コードの開発が促進された。それらは「数理計画システム」と呼ばれている(たとえば I BMのMPSX-370や Control Data Corporationの APEXⅢ ,Management Science System社のMPS―Ⅲなど)。これらのコードは精巧なデータ取扱い機能と, 解を解析する手段とをもっており,8,000~16,000個の制約条件式をもち,変数の数には制限が無いような大きな問題を解くことができる。50,000本の制約条件式をもつLP問題をMPS―Ⅲで解くのに成功している。

5,000本以上の制約条件式を含むLP問題は,いかなる基準から考えても明らかに大型問題であり,これがうまく解けるかどうかは,問題の構造や問題のもつ特性に依存してくる。LP問題の実用的な規模は,制約条件式が500~1,500本,変数の数が数千個程度のものである。この程度の問題ならば,どの高級LP計算システムでも, そう無理なく解くことができる。これらの高級LPシス テムは,通常のレンタル料金に加えて,システム使用料を加算すれば使用することができる。もし利用者が頻繁 にLP問題を解く必要があるならば,LPのソフトウエアを別に購入すれば費用の面で有利になる。また,たまに使用するのであれば,信頼のおけるコンピュータ・サ ービス会社に依頼するのもよいし,あるいは,借出し用のLPソフトウエアを備えた計算センターに接続する , リモートジョブ端末を借り入れるのもよい。最近のLPコードの性能や,そのデータ管理機能に関するすぐれた研究が,Orchard Haysにより発表されている。また Whitellは,数理計画システムでの計算アルゴリズムについての現況報告をしている。商用コンピュータ・コー ド はすべて,LP問題を解く基本的な方法としてシンプ レックス・アルゴリズムと,その変化形を使用している。 最近になって,ソ連の数学者Khachianによって, 新しいアルゴリズムが開発され多大な興味が注がれている。Khachianのアルゴリズムは,理論的には重要な新しい展開となったものの,計算機で取り扱える見通しは難しそうである(Dantzig参照)

LPソフトウエアで重要ないくつかの特色
さまさまなコンピュータ製造業者や,コンピュータ・サービス機関から提供されている,すべてのLPソフトウエアの特色について,論議することは実際的ではなかろう。ここではすべての高級なLP計算システムに共通する,重要な特色のいくつかを簡単に述べよう。さらに詳細については ,読者はBradley他を参照するとよい。

入カデーター
ほとんどすべてのコンピュータ・コードで,使用者は以下のデータを準備しなければならない。

1.「使用者が見分け易いようにつけた決定変数,制約条件式,目的関数の名前」―たとえば,活動をx1, x2, x3と定める代わりに,PROD1,PROD2, PROD3,と名付けると便利であろう。
2.「制約条件式の係数,目的関数の係数,制約条件式の右辺の値 (RHS)」―― この場合,非ゼロの係数だけを入れればよい実際には制約行列に,たくさんのゼロ要素を含んでいるものが多い。
3.「 制約関係の性質」一 利用者は制約条件式を等式や不等式に指定する(=,≦または≧)。
4.「変数の限界」一変数は通常は利用者が特に指定しなければ,非負で上界は有限ではない。
5.「多重LP計算」― 利用者は,あらかじめ複数個の目的関数や,RHSベクトルを入力できる。そこで適当な目的関数とRHSベクトルを指定することにより,いろいろな組み合わせでの繰り返しLP計算が可能となる。これは入カデータに応じた,LP解の感度分析に有効な方法である。

マトリックス・ジェネレーター
大規模のLP問題に対する入カデータの作成には,マトリックス・ジェネレーターを使用すると便利である。これは一般には,個々の利用者によって開発された専用のプログラムである。このプログラムにより,原データはコンピュータ・コードが要求するLPデータ・フォーマットに変換される。利用者はまた,目的関数の係数や 右辺の定数,制約条件式の係数の値を算出するために, 表データヘの算術計算をすることができる。またマトリ ックス・ジェネレーターは,ある種の矛盾のチェックにより,入カデータの誤りを見つけることもできる。一般にマトリックス・ジェネレーターでは,利用者は情報が収集されたままの形で,最小限の情報量を指定するだけでよい大きなLP問題を解く場合には,特殊な形で大量のデータをまとめねばならないから,マトリックス・ジェネレーターは無くてはならないものである。データ の取扱いと更新,マトリックスの生成で,LPモデルの解を得るための総費用のうち90%を費やすことさえある。市販の高級なLPソフトウエアは,LPパッケージの一部分として,汎用性のあるマトリックス・ジェネレーターを備えている。もちろんLPモデルが入カパラメー夕の変更だけで,定常的に繰返し計算されるような場合には,個々の利用者が,そのための特殊なマトリックス・ジェネレーターを開 発することもある。

使用者による選択指定
商品化されているほとんどのコードは,LP解の精度を向上するために,次のような選択指定項目を備えている。

1.「スケーリング」― LP計算での丸め誤差の集積や数値的な不安定性を減少させるために,利用者の選択指定として,入カデータの自動スケーリングを使用できる。LPで定式化したときに,係数の大きさが幅広く変わるような場合には,自動スケーリングの選択指定を利用すべきである。
2.「許容限界」― 許容限界によって利用者はLP解に望む精度の程度を指定することができる。例えば, どのくらい小さい数となったら,もうゼロとして取 り扱ってもよいかの許容限界を指定できる。
3.「誤差」― シンプレックス法では一般形でLP問題を解くから(ここではすべての制約条件式が等式として表わされている),LP解によって制約条件式を満足させるときに,どの程度の誤差まで許容できるかを与えておく必要がある。たとえば制約条件式の右辺と左辺間の誤差が1×10~7程度までは許すという具合である。

出力機能
LPソフトウエアの標準的な最月小限の出力は,通常, 次のようなものである。

1.「最適解の変数名とその値」
2.「 目的関数の最適値」
3.「 制約資源のシャドウプライス」―制約条件式のシャドウプライスとは,その右辺の値を1単位増加させたときの,目的関数の最適値の正味変化量である。制約された資源の増加が,目的関数値に対しては正の影響を与えるか,負の影響を与えるかに従って,シャドウプライスは正あるいは負の値を取る シャドウプライスは限界費用,限界利益と解釈することができる。
4.「決定変数の機会費用」―機会費用の意味は,シャドウプライスのもつ意味と似ているが,列すなわち決定変数の,目的関数に対する影響を表わしている。

標準的な出力に加えて,すべての主要なLPソフトウ エアは,選択によって次のような出力を出すことができる。

1.「入カデータに対する入力確認」――利用者は入力データの要約も完全な情報も要求できる。これはデバッグに利用できる。
2.「感度分析」― これはLPの最適化後に入カパラメータに関する,解の解析を行うことである。基本的には目的関数の係数や右辺の定数の変化に関して , 最適値がどの程度敏感であるかを分析する。感度分析については次の節でもっと詳しく述べる。

レポートライター
レポートライターは標準的な出力を,利用者向きの出力形式に変換するための専用プログラムである。マトリ ックス・ジェネレーターに似ているが,こちらは出力の 際に使用される。これらの利用者向きの出力は,LPモデルに詳しくない現場の人にも理解できるようになっている。大部分の高級LPコードは,汎用のレポートライ ターを利用者に提供している。

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

関連記事一覧

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

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

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

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