トップ > 最適化とは

最適化とは

汎用数理計画法パッケージ「Numerical Optimizer」は、“データ”と“やり方(ルール)”がわかっていながら、 解決策が導き出せない現実の問題に対し、最適解を提供するツールです。 最適化ソリューションは様々な分野で広く利用されています。 数理計画法と呼ばれる様々な解法(アルゴリズム)を駆使して現実の 問題を解決するというアプローチです。

最適化のイメージ(ナップサック問題を例として)

ここではより具体的なイメージを持っていただくために数理計画の世界の中では 有名な "ナップサック問題" を例として紹介します。

ナップサック問題概要

容量(重量)制限のある袋にものを詰め込みます。 袋は無限にものを入れることが出来ませんので、どれを入れるかが重要になります。 最終的に入れることができたものの価値が高ければ嬉しいということです。しばしば 泥棒に例えられる有名な問題です。

ナップサック問題イメージ

問題の整理

ここでは袋の重量制限を 10 kg としてものの価値と重さは以下のように考えます。 参考に単位重量あたりの価値(価値/重量)も出してみました。

ナップサック問題 データ

この問題を最適化問題として定式する必要があるのですが、Numerical Optimizer ではモデリング言語 SIMPLE が それをサポートします.ナップサック問題の定式化の記述はこちらを ご覧ください。

答えを求める

この問題を最適化問題として解くと最適解は「 B と D を詰め込む(合計 90 )」と なります。ちなみに単位重量あたりの価値が大きいものから順に詰めていくという方法 (貪欲法)で行うと答えは「 A と E を詰め込む(合計 87)」と最適解になりません。

現実の問題はこの例のように簡単ではなく、評価(例では価値)が複数であったり、ルール (例では重量制限のみ)が単純ではありません。

汎用数理計画パッケージ Numerical Optimizer の "汎用" とは

最適化をする際には、

という二段階の手順が必要になります。汎用数理計画法パッケージ Numerical Optimizer は後者の 「求解」を担当します。 当然「モデル化」部分に対してもモデリング言語 SIMPLE が強力にサポートします。

つるかめ算を例にして

最適化問題ではありませんが、分かりやすくつるかめ算を例にして汎用数理計画法パッケージを用いる イメージを説明したいと思います。

(問題) つる(足 2 本)とかめ(足 4 本)が合計で 10 匹います。足の合計は 30 本です。 つるとかめはそれぞれ何匹でしょうか?

つるかめ算に特化した "汎用的でない" 解法

まず、つる 0 羽・かめ 10 匹を初期値として考えます。この状態では足の合計が 40 本 です。ここから 10 本足を減らせばよく、かめを 1 匹減らしてつるを 1 羽増やすことに より足の合計は 2 本減りますから 10 ÷ 2 = 5 となり、答えは つる 5 羽かめ 5 匹となります。
この解法(アルゴリズム)をプログラミングし、システム化したとします。そのときに いくつか "もったいない" 点があります。それは という点です。特化した解法ではソリューションとしての応用分野に幅を出すことが 難しくなります。

汎用的な解法

問題をモデル化(定式化)します。

   つるを X 、かめを Y とおく。
    X + Y = 10
    2X + 4Y = 30

この連立一次方程式を解けば答えが求まります。 これをシステム化する際にはつるかめ算用の解法(アルゴリズム)の構築ではなく 連立一次方程式を解くプログラムを書けばよいということになります。
これは いたるところで用いられるものですので、プログラムすることなく既存のツールを 引っ張り出して即座にシステム化できるでしょう。

汎用数理計画法パッケージ Numerical Optimizer も同様で、数理計画問題として「定式化」された 問題を解く汎用的な解法(アルゴリズム)が詰まっていますので、幅広い分野で応用 されているのです。

最適化イメージ