Excelのソルバーのアルゴリズムに関する質問

Excelのソルバーのヘルプの機能のコピぺです。


Microsoft Excel のソルバー ツールでは、テキサス州オースティンのテキサス大学の Leon Lasdon 氏とクリーヴランド州立大学の Allan Waren 氏が開発した
GRG2 (Generalized Reduced Gradient) 非線形最適化コードが使用されています。

線形問題と整数問題では、Frontline Systems, Inc. の John Watson 氏と Dan Fylstra 氏が実装した、束縛変数を用いたシンプレックス法と分枝限定法が使用
されています。ソルバーが使用する内部解決プロセスの詳細については、以下の連絡先にお問い合わせください。

調べてみたのですが、非線形用と線形用と整数用の３種類があるということなのですか？
そしれぞれぞれのアルゴリズムが異なるということなのでしょうか？
それと最後の内部解決プロセスというのはいきなり出てきているのですが、
シンプレックス法と分枝限定法とどういう関係にあるのでしょうか？
よろしくお願い致します。

No.1 ベストアンサー 回答者： gef00675 回答日時： 2008/12/12 13:48

エクセルのことはよく知りませんが、一般論をいうと、

目的関数および制約条件のすべてが一次式で表されるような最適化問題を線形計画問題といい、それ以外を非線形計画問題といいます。

非線形計画法を解くためのアルゴリズムには、準ニュートン法や共役傾斜法などがあり、線形計画法を解くためのアルゴリズムがシンプレックス法です。

非線形計画問題を解くアルゴリズムは一般的な数式に適用できますから、もちろん線形計画問題にも適用できます。しかし、計算のコストを考えると、線形計画問題については専用のアルゴリズムを使うほうがよいです。たとえばニュートン法をパソコンに実装するとき、使える変数や制約条件の数は数100個程度が限度ですが、シンプレックス法では数万個でもOKです。

整数計画問題とは変数のとる値が整数に限定された最適化問題のことであって、整数だけという制約の下で、解の集合を絞っていくアルゴリズムが分枝限定法です。線形・非線形のどちらの場合にも適用されます。

アルゴリズムの詳細は下記URLをご覧ください。
http://ja.wikipedia.org/wiki/ニュートン法,
http://ja.wikipedia.org/wiki/シンプレックス法,
http://ja.wikipedia.org/wiki/分枝限定法

No.2 回答者： chie65536 回答日時： 2008/12/12 14:32

＞それと最後の内部解決プロセスというのはいきなり出てきているのですが、

＞シンプレックス法と分枝限定法とどういう関係にあるのでしょうか？
何の関係もありません。

「ソルバーが使用する内部解決プロセス」とは「ソルバーが内部で使用している、問題解決の為の、プログラムやらアルゴリズムやらインターフェースやら色々」と言う意味です。

噛み砕いて言えば「ソルバーに組み込んだプログラムの中身は、マイクロソフトでは判らん。なので以下の連絡先に連絡しろ」って事が書いてあるだけです。