トップページ | ひとつ上のページ | 目次ページ | このサイトについて | ENGLISH

数理計画法

数理計画法（Mathematical Programming）は、数理モデル（”現実”を式で表したもの）の、 最適解を求めるための方法です。 最適解というのは、利益の問題なら、利益が最大の状態ですし、 輸送の問題なら、最短ルートや最小コストのことです。

名前が「計画法」となっているので 実験計画法 との関係が気になりますが、 実験計画法は、「実験”を”計画する方法」で、 数理計画法は、「数理”で”計画する方法」と考えれば良いようです。

さて、数理モデルで最適解を探す作業は、数理計画法以外の分野でもしていることです。 例えば、 実験計画法 で最適条件を見つけたり、 品質工学 で安定した品質の条件を決めたり、 リスク解析 でリスクを最小にする方法を考えたり、 回帰分析 で予測式を見つける作業です。 そう考えると、数理計画法とは何かがわからなくなってきますが、 筆者は数理計画法を下記のように考えています。

• 最適解（最大値・最小値）を求めることが目的になっている （他の分野では、モデルの「性質」を調べることが目的になっていたりします）
• 最適解を求める「方法」を研究対象にしている
• 数理計画法が扱う数理モデルは、 オペレーションズ・リサーチ が発祥になっている （数理モデルなら、どんなものでも扱うわけではないです。）

オペレーションズ・リサーチから出発した数理計画法は、 理論が深められて、応用の広い基礎理論になりつつあるようです。 数理モデルの「最適解は求まるのか否か」という深遠な研究もあります。 おそらく、このサイトで取り上げたいろいろな手法と無関係ではないです。

数理計画法の扱う「問題」

数理計画法が扱う数理モデルは、○○問題と言われています。 これらの解法の研究が、数理計画法の使命になっています。 解法の筆頭が、線形計画法です。 また、これらの問題を眺めると、数理計画法が何をしようとしているかが見えます。

• 生産計画問題 - 利益を最大にするための材料と品種の組合せを見つける
• 輸送問題 - 輸送費用を最小にするルートを見つける
• 施設配置問題 - 輸送費用を最小にする倉庫の配置を見つける
• ナップザック問題 - 重量制限の中で、もっとも価値が高い詰め込み方を見つける
• 巡回セールスマン問題 - すべてのポイントを回る最短ルートを見つける

線形計画法

問題が、いくつかの不等式で表されていると、 不等式によって、解を得られる範囲に制約ができています。

線形計画法は、その不等式が 線形 の式で表されている時に、 その制約の中での最適値を求める方法です。

参考文献

「Python言語によるビジネスアナリティクス実務家のための最適化・統計解析・機械学習」　久保幹雄　他　著　近代科学社　2016
グラフ、統計解析、機械学習、ネットワーク分析、最適化、Excelとの連携、といった事をするのに使うツールが、 Pythonではモジュールとしてまとまっているそうです。 この本は、モジュールの使い方事典のような内容です。
Pythonの本としては珍しく、動的計画法など、数理計画法関係にもかなりのページを割いています。

「メタヒューリスティクスの数理」久保幹雄 ・J.P.ペドロソ　著　共立出版　2009
数理計画法の解法にメタヒューリスティクスを使います。 「メタ」とは、各手法の集合という意味です。 この本は、手法集であり、手引書です。

「数理計画入門」 福島雅夫 著 朝倉書店 1996
具体例を通して理解を深めることを目指した本

「数理計画法」 加藤直樹 著 コロナ社 2008
数学の本です。各手法と問題の関係が、すっきりと整理されています。

「数理計画法の基礎」 坂和正敏 著 森北出版

「グラフ・ネットワークアルゴリズムの基礎」　浅野孝夫　著　近代科学社　2017
経路の探索問題のアルゴリズムを解説。

順路 次は 遺伝的アルゴリズム