数理計画モデル分析と基礎的定式化技法
大山 達雄…………………l…測＝l州Illl……………lt…ll…………‖‖‖＝＝‖‖‖＝‖‖＝‖‖‖‖‖‖＝‖‖‖‖＝‖‖‖＝＝‖‖＝川Ill…‖‖川Illl…lll‖‖‖＝‖‖‖＝川Illltllll……llll…lllll‖仙州l……lllll…l…l……11…ll……lll………t…llll州Illll……

1．数理計画モデル分析

され、入力データが用意されると、次はモデルの解を求めるという操作が必要となる。この操システムはいくつかの構成要素からなり、そ作は一般にモデルを解くと呼ばれるが、より具れらがお互いに相互関係を有し、何らかの目的体的には、数式の形で表された最適化問題の最のために機能しているものであるといえる。与
えられたシステムに対して、解決すべき何らか適解を求める場合、コンピュータによって数学モデルで表された変数の変動の様子を模擬的にの問題が提起されたとしよう。現実のシステム調べる場合、などいくつかの異なる場合が考えそのものではそれぞれのシステムの状況も異なられる。数学モデルが現実のシステムを厳密なとそれらの相互関係を、たとえば数式を用いて意味で正確に表しているとは限らない以上、われわれはモデルの妥当性、適合性、整合性を何らかの方法でチェックする必要もあるし、またモデルの解が得られたとしても、入力データの数学的に表現した数学モデルを構築し、その中変動によってモデルの解がどのように変化するでモデルの解を得ることによってシステムの処かといった解の安定性、信頼性の分析、いわゆ理、操作を考える。われわれの対象とするシス

る感度分析と呼ばれるモデルのフィードバック

テムにおいて、たとえば弄り益を最大にする、費用を最小にする、効率を最大にする、というよ操作を綿密に実施する必要がある。数理計画モデルの構築から始まってモデルの最適解を求め、うに何らかの評価基準を最適にしようという一その結果を分析するまでの一連の換作が数理計

種の目的を有する数学モデルは最適化モデル、画モデル分析である。システムに対する問題提起から、モデル分析によって何らかの解を得、るし、またシステム自体の構成要素間の相互関係もわれわれにとって分析、処理が困難な場合がほとんどである。そこでシステムの構成要素

あるいはより一般的に数理計画モデルと呼ばれる。数学モデルが現実のシステムをもう一つの別な形に表現したものである以上、モデルの構それをシステムに対する解決策として意思決定築に際しては、システムの構造、特性ができるのようになる。

をするまでの操作を模式的に図示すると、図1だけ正確かつ厳密に表現されることが必要である。システムに関する多くのデータも何らかの形で考慮されなければならない。たとえばエネ

意 思 決 定ルギーシステムにおけるエネルギー変換効率、原燃料としての原油、石炭、天然ガスなどの燃料単価、将来需要などはすべて対応する数学モデルの中で何らかの形で用いられる数値であって、これらが数学モデルのための入力データとなる。システムに対応する数学モデルが構築

おおやま たっお
政策研究大学院大学政策研究科

モ デ ル 分 析

〒338浦和市下大久保2551998年2月号

図1© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（5）71望。基礎的定式低級法

くと諾二叫封二且6となるが、図2のように卑えられ藍区分線形関数に嘉沌㍍引は、∬＝＝柑のときの封の健を軸＝且4であるので、正しく得モデルを構築する場合の定式甘藍技法として、等、非常各こ多≪のものが提案きれ、実施きれてられない・。すなわち上の定式耳』におu、て、次の終M瑚が満たきれねばならな矩、。

し・∴二 ∴、 ・ニ・ ・＞；盲￣∴F：：：）‥ゴニ指．・

線形計画恥非線形計画、動的計画の各種普デル∴∴ご・・、 −．・一ノ・・∵二∴ン隼・∴．′、・・∴予

べなW・が㌔定式甘藍の基本事項である線形性と非∴．．．、−・ご ∴ ・・．：．−・‥：・モ∵−∴㍉●．

腹掛軋静態性と勧健性、特殊な種類の制約に『附芳≠ 考れぞれの例を紹介することをこする。

巨．・ ．∴ ÷．・∴：・、、
そこで払胤型整数変数g見，g慧∈《の調を用いて≠モデルの変数に関連するものとじて㌔任意の非以 1Fのような定式化を行なう。

′．．一．＼

のりー′しノ′．︑＼＼盲ノ？ぷ

凱湖諾 ∈≡ 老勒銅

非線形関数の線形脂

5− こ ・＿ ミ、・−●こニ、こヽl∵ノ・二‥．一二′、・・、∴′岬lヽ∴．・，＼こ● 、．・ ご こ∴すとるガ披≠動的問題を静的閻魔に変換する方激︒毯

翫旬≦．勘≦諸式耳旺昏こ関連するものたじて≠論理制約を定式朋雲＼⊥＝．．′

線形関数を線形イ臨すもる方法、をむ／てモデルの定式（4）仙（7）の下で臥以下が成立サる。

．・．．．、∴ ．ノ∴・ナ．∴与、・・く ・二．−肪胤型整数変数叡欄障るとも非常に広範囲の定式化が可能となる。‰、ま図2のよ】うな区分線

・＿・・：：・−′

形関数が卑えられ放とじよう。区間ダニか項（鮎）g且＝胤，g2＝乾）のとき、諾且＝3，の≦諾2≦6，、、 ・ ‡− −・：、●二・丁∴．・．・こi
ご ．、− ・、・・ご 一二、、、・∴ノ∴

区間盈芝分割ずると凱図望首こ示す諾とぞの関数！．こ、・、 ．．・・・・、、・ ．

J・ご−〕、・．．一三．、．．・●
こ。 ． ／．1−‡ト．‥．．・・、・・＼、・●のよ莞・殻こ衷サみことができる。
勘招酢瑚帖翫 掴
二∴・、・。．、−、：、．・1、・●、

一一・．・〃て・−JnU︺ル

、∴

J：‥

囲3

一般に図3のような非線形関数を、犯偶の区間分割に塞く区分線形関数によって近似的に表してみよう。それノぞれの区間或 ∈ Ⅳ ＝こ）93

老乳，2∋…ヲ陀卦の幅を恥 をの区間内の折線の勾配をβ豆とすると、変数謹と封の間の関数野＝瑠3

邸（諾）は次のように表すことができる。

図2

しかも／なが紅蜘姉妹㈹で与えられる定式化にお射で∴新心い凌数町諾慧，∬3の値を任意に定、・1、ざ、 ‥一ニーご●∵ご・「二 ′．．ご．∴・い ・・．∴ −、、 ・、∴こ￣人−！−㌧∵．−−、−−ミ‥ ．・㌧ノ㍉

悶（6）、 十′●．て、・∴‥●、−ご＼とニ、底∈Ⅳ・」、、・© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

豆∈．Ⅳ

オペレ、−ションズuリサーチ

・：、・・i0≦諾豆≦βゎ 五∈Ⅳ

ここで仇1型整数変数（勾＝∈Ⅳ）を用いると、（8）−（10）の表現は次のように書くことができる。

3：℃1＋2￡2一風悠3≦27（15）領域β3−4諾1＋3こだ2−属悠3≦15q溝≦諾塩≦β豆筍＿1宜∈Ⅳ （11）Zo＝1，Z崖∈（0，1），宜∈Ⅳー諾1＋5諾2＋∬z3≧25（10）

gl＋g2＋z3≦2，Zl，Z2，g3∈（0，1）（16）（12）

以上から、任意の非線形関数は、m個の区間に分割した区分線形関数として、兜−1個の♭1型整数変数を用いて近似的に表すことができ上の定式化において、Zl＝0ならば（諾1，諾2）∈ぶ1を表し、Z2＝0ならば（ご1，諾2）∈g2を表し、そしてz3＝0ならば（諾1，諾2）∈鞄を表すゝしたがって（16）が満たされているということは、♭
1型整数変数zl，Z2，Z3のうち少なくとも一つが0となれば、それはすべてが1とはならないこる。つまりどのような非線形関数に対しても、区間分割を細かくすると、与えられた非線形関数を高精度で近似できることになる。とを意味するので、点（諾1，諾2）は領域gl，鞄，β3のうちのいずれかの中にあることになる。

論理制約の定式化

より一般的に、多変数関数薫（諾1，…，諾れ），五∈〟＝‡1，…，m）を用いて、m本の制約条件がいま諾1ロヱ2平面上に図4に示すような3つの領域β1，範，鞄がぶ1＝（（ご1，諾2）l3諾1＋5諾2≦
15，諾1≧0，諾2≧0〉，戟＝（（ヱ1，諾2）！諾2≦4，馳1＋諾2≧19，ヱ1一諾2≦5），鞄＝（（諾1，諾2）

次のように与えられているとする。
薫（諾1，…，ヱ兜）≦あ宜 宜∈〟（17）l一諾1＋5諾2≧25，馳1＋2：若2≦27，一触1＋3ニだ2≦

このとき m本の制約条件のうちの少なくとも15〉のように与えられているとする。

た本を満たさなければならない という論理制

約は、ひ1型整数変数（z豆‡宜∈財）を用いて∬2

弟（諾1，…，諾柁）叫∬（1一之宜）≦わ度五∈財（18）∑z豆≧ゐ（19）宜∈凡才

易∈（0，1），宜∈〟；∬：大きな数 （20）のように定式化できる。
上に示した論理制約条件は、たとえば製造工場などの生産システムにおいて、品質管理に図4関する何種類かの検査項目が満たされなければならないという生産方式を決定する場合などにも適用できる。

このとき点（諾1，諾2）は領域β1，戟，鞄のうちの少なくとも一つの中になければならないとする。

このような論理制約はひ1型整数変数zl，勿，g3と大きな数∬を用いて以下のように表すことが動的問題の静的問題への変換できる。
3こだ1＋5諾2一属悠1≦15
領域ぶ1

諾1＋ggl≧0（13）諾2＋厨 zl≧0
諾2−」打z2≦4領域戟弛1＋諾2＋属悠2≧19（14）諾1一言2−∬z2≦5

1998年2 月号

ネットワークフロー最適化問題のうち、次のような動的フロー最適化問題を考えてみよう。
図5に示すようなネットワーークⅣ＝（Vg）の頂点集合、枝集合をそれぞれⅤ＝‡1，2，3，4），且＝（（宜，ブ）一宜∈竹ゴ∈Ⅴ）として、枝（宜，ブ）上の数値（c豆メ，α豆J）はそれぞれc勿：枝（五，ゴ）の単位時間当たり容量、叫‥枝（五，ブ）上の移動所要© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（7）丁3

時間を表す。総所要時間郡内にソ山ス温からシ

ここで新たなネットワーク抑甘巨＝㈹甘粕
瑚抑膵慨のようにじて作成する。新たな頂点集合≠礁集合はそれぞれ明利い＝紬津川

ンク4へのプ田匝の畳を最大にサると矩、う動的−．・‥・二・ニ ーー￣∴ ∴．薄紅−ナ・テ∴ご．、＿． ．●、．・・、■、：・■、−．−−．．．

・‥・・・ ′∴ ∫・ 、・・−‥∴

軋横断鶴緑木冊粛の容盈を筍ガとする。
・∴ノ‥て・一、・￣・∴・・√．′ こ・1・・∴■∴二￣−−：、動的ア悶b鵬最適耳比問題は新たなネッ匹汐一夕ーニ ′ −、こ∴∴∴‥＼、、ミ￣ −・∴Jさ．、−・
腑町軌雄二曙胤ブ…，耶からシンク頂点宜（陀，盟）9、∴〕‡∴′‥∴′、：∴−・．一二∴・・を求める多り山沸教シンク型静的フ闇偏最適イ奴−−・・ご、 、 ■・ ∴こ、ノ、・・・．−・‥‥．ニ1・．‥て≠総所要暗闇班ニアの場僚の鼎過勤的ブロー∴∴・ご、ニ‡．・こ荘∴ゾ、ン・−：・∴ご−−ご：・．、ニ∴＼●三」●、∴、
図6のプ田−ほも時刻⑬にソース且から頂点2，3晶こをれぞれ3333を』′て時刻且に同様に頂点2，3亀こそれぞれ3，認のプ田山を流した場合の時刻．′∴∴‥・1こ−：、∴1．．．・・−・・．∴∴・‥ −：．王・＼、．．・・・．・・・・・・‥∴．・・・：・・．、；∴・こ‡さ．ノ、：・、．

ずる閲願となる。も〆たがってこの場合の最適プ・． こ−：・、．●．∴∴∴●■ニ ー ・−・．、・ ′・二・∴∴右 ・●・・‥：・ニー・ニ・・∴∴・．

穏最芝おける且つの実行可能ア四♭鵬を表す。

‥ 、−− ●、 ・・．：・ヰ∴− べ∴‡：、∴■、
数理計画モデル分析において、最適解自体が非常に塵要な意味を持つことは当然である。
蕊たモデルで得られた最適解を現実のシステムに対サる 最適な 意思決定として実施に移すと糾う操作がそれほど容易でない場合があることも事実である。つまりわれわれの得た最適解が：こ三富．≡二つ

数学モデルとじての最適化問題に対する最適解て

23

≡i5

フ■

図7晋堵（8）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ0リサーチ

である以上、それがいかに厳密に得られたものであったとしても、現実のシステムに適用する場合には、何らかの修正、補正が必要である。
モデル分析においては、モデルの解を得るということだけを目的とすべきではなく、モデルを結、結合すればよいかという処理方法の開発なども必要となるであろう。このようなことが可能となれば、実際に解ける問題の範囲がかなり拡大することは事実である。
数理計画手法の適用という観点からしてあ十分に換作、駆使することによって、モデルから得られる情報を現実のシステムと関連させ、さらに詳細な分析を加えることが重要である。
そのためにもわれわれの構築する数学モデルまり多くの分析がこれまでには行われていない
分野は大きく3つに分かれるようである。第1は非常に自然に近いとされる天然資源、環境などに関する分野である。自然現象の非線形性には、単にできるだけ厳密、詳細にというのではなく、むしろある程度単純であっても、システ伴う複雑さがOR手法に基づくモデル分析を非ムとの十分な整合性がとれているという条件のたモデル分析がそれほど普及していない現在で常に困難にしているといえる。非線形性を扱っ下で、十分な操作性を有することが必要である。

は、この分野における分析が一般的に普及する数学モデルの構造が決定された後には、モデルにはもう少しの時間が必要であろう。第2は逆を解くのに必要とされる、できるだけ信頼度の高い入力データを準備しなければならない。このようなデータ収集作業には、やはりシステムに全く人間の行動、組織そのものあるいはそれある。人間行動が古くから 平均人 として統計自体を綿密に多方面から分析する作業が必要と的にしか捉えられなく、人間の価値観、感情、なる。モデルの構築、データの収集作業に際してシステムを詳細に観察、把握すると、これまで気づかなかったシステムの新たな側面が見出意思、行動自体にあまり関心が向けられなかったことにもよるのであろう。第3は第1と第2の中間ともいうべき、あるいはこれらが混合しされることもある。モデル分析は、時として、た分野ともいうべき災害、危機管理といった分数学モデルを解いて最適解を得ることに相当する程度に重要な情報、知見をわれわれに与えて野である。地震、台風、大雨等の自然災害、天災に突然見舞われる場合、あるいはテロ、爆弾、くれる場合があるということは非常に興味深い事故といった突発的な緊急事態にどのように対ことである。

応すればよいかという問題である。こういったに近いとされる行政、組織、政治などの分野で分野に数理計画手法の適用の将来性があるよう

4．数理計画モデル分析の課題と将来展望な気がする。これからもより多くの人々によって、より広範に、より積極的に、数理計画モデ
数理計画モデル分析の実施に当たっては、たとえば古典的、代表的な数理計画問題としての施設配置問題の場合のように、変数、制約条件の数がそれぞれ何千、何万にも及ぶ巨大規模のモデルのため、データ入手可能性と信頼性、そして最適解を求める方法に関する問題点が存在することがある。今後はこのような問題に対してもメインフレームコンピュータによらて解くというのではなく、より動的に、そしていろいろな状況に応じて、あるいは対話型としてパソコンレベルで容易に解けることが必要である。

ただ単に現実の状況を忠実にモデル化するというのではなく、たとえば問題の多階層化ある
いは分割化といった工夫、さらには階層化、分ルが新たな理論と手法の開発を待つつ、新たな応用分野に適用されることを期待したい。
参考文献

川Fbrd，L・R・and D・R・Fuikerson（1962）．
Flowsin Networks，Princeton University
Press，USA・【2】Bradley，S．P．，A・C．Haxand
T且・Magn弧ti（1977）．A揮おed肋娩emα孟夏cαg
Prp9rummin9，Addison−Wbsley，Reading，MA，716p．【3】大山達雄，1993．「最適化モデル分析」，日科技連出版，372p．仁句大山達雄，1995．
数理計画モデル分析の概要と実際 ，数理計画モデルの応用一橋築と解法と分析−，第2回ORセミナーテキスト，日本OR学会，ppふ13．

割化の後にそれらをどのようにして整合的に連1998年2 月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（9）75