機械学習に意思決定論? ②

機械学習に意思決定論? ②

<<前の記事に戻る

 

前回は、1980年代に最盛期を迎えた意思決定論のサーベィを通して、AIにおける意思決定論の俯瞰を行いました。今回は、決定問題(不確実性が伴わない情報下での意思決定論)における手法の概論を行います。

決定理論には、生産管理やORの分野で有名な線形計画法(LP:Linear Programing)と実数計画法(IP:Integer Programing)、さらにネットワーク理論とその活用であるPERTやクリティカル・パスなどがあります。さらに広く解釈すると、ガントチャートなどのスケジューリング手法もその一部であると言えます。

これらの理論を知るためには、一般的な教科書や大学の講義を受ければ済みます。ただしこれらの理論は、1970~80年代に渡り膨大な研究論文によりその理論の正しさが数学的に証明されてきた分野であり、この理論的背景から全てを理解するためには大学院2年間分の時間が必要です。

理論が正しいことを前提に利用するだけであるなら、基本的なフォーミュラとフォーミュラの解法手法を知るだけで十分ですが、実は解法手法を理解し実施するだけでも大学の15コマを使った講義を受けなければならない時代もありました。この解法手法は、シンプレックス法と呼ばれるもので、フォーミュラをベーシック・タブロー(マトリックス表示した数字のテーブル)に落とし、ベーシスと呼ばれる評価軸を置き換える作業を繰り返す解法になります。

LPの解法:シンプレックス法

 

図1:LPのフォーミュラ、概念図、ベーシック・タブロー
図1:LPのフォーミュラ、概念図、ベーシック・タブロー

上記のLPフォーミュラは、教科書で練習のために作られた以下のような問題に対するものです。

LPの解法:ドレッシング製造工場

あるサラダ・ドレッシング製造会社が、イタリアンとフレンチの2種類のサラダ・ドレッシングを製造し納品しているとしよう。この2種類のドレッシングを作るためには、サラダ・オイル、ビネガー、塩、香辛料、野菜などの原材料が使われているとしよう。このような原材料のうち、この2種類のドレッシングを区別するために重要なものは、サラダ・オイルとビネガーの割合である。

それぞれドレッシングにおける原材料の使用量と、それぞれの原材料最大在庫量は以下の図に示す通りである。 

ここで、問題を簡略化するために、生産したそれぞれのドレッシングは、全て納品できるものとする。さて、この会社が利益を最大化するためには、それぞれのドレッシングを何本ずつ生産すべきであろうか?

図2: LP問題の例
図2: LP問題の例
図3:LPの一般的フォーミュラ
図3:LPの一般的フォーミュラ

この問題を解くためには、図1の中の連立方程式を利益最大化するように解けば良いだけですので、中学の算数程度の知識があれば誰でも計算することができます。
しかしこの問題は、教科書用にシンプル化されたものであり、実際の製造現場では何十種類もの原材料で何十種類もの製品を作る組み合わせを考慮する必要があります。事実、40年前の家電製造メーカでも、500種類の原材料(中間生産物を含む)から200種類の電気製品を作っていました。このように多くの材料と製品の組み合わせによるLPを解くとなれば、最低でも500本からなる連立方程式を解くことになります。もはや、人力で解法することは意味のないことですので、コンピュータに解かせることが必要となります。

 

LPの解法:シンプレックス法

 

このコンピュータによる処理のために、ベーシック・タブローによる解法が必要であり、同時にベーシック・タブローの数学的な正当性が証明さる必要がありました。1980年代には、これらの理論構築が完了し、PCによる解法のためのソフトウェアLINDOなどが開発され、現在に至っています。現在のLINDOの利用者の仕事は、基本的なフォーミュレーションができることと、分析結果の判断(デュアル・ソリューションの解釈)と感度分析だけが重要であり、どれだけ煩雑なフォーミュレーションであってもその解法に煩わされる必要は無くなります。従って、図3に一般的なフォーミュレーションを記載しておきます。

気をつけなくてはならない事は、LPの結果が必ずしも実数値ではない点です。また、求めた結果が小数点であらわされている場合、単純に数字を丸めて実数にすれば最適性を保たれることにもなりません。そこで、実務面を考慮して編み出された手法がIPです。IPのフォーミュレーションは、基本的にLPと同じですが、実数で求めたい変数をInteger(実数)と指定しLINDOで計算させれば良いだけです。さらに、このIPの延長上の特殊ケースとしてネットワーク理論の解法が位置づけられています。IPとネットワークの基本的な相違は、ネットワーク内の変数が全てダミー変数(それぞれの変数が結果として0か1が付与される変数)であることです。7

住宅建築問題

また、図5のネットワークをIPで表したのが下図6です。

 

 

ケース:住宅建築問題:整数計画法(IP)

図6: ネットワークのIPフォーミュレーション
図6: ネットワークのIPフォーミュレーション

このフォーミュラを使って最適解を求めると、クリティカル・パスと呼ばれる最短完了日数を求めることができます。また、同時にEST(最短作業開始日)とLCT(最遅作業完了日)を求め、このESTとLCTの差から各工程のスラック(猶予日数)を割り出すことができます。従ってこの現場を監督する者にとって、全工程を最短の日数で完了させるために、日数を厳格に管理しなければならないクリティカル・パス上の工程と作業に余裕のあるスラックがある工程の管理を分けて行い、より効果的な管理ができるようにするための手法です。

図7: EST&LCTとクリティカル・パス

 

続きを読む>>