2001年度オペレーションズ・リサーチ期末試験問題

オペレーションズ・リサーチ 2001年度期末試験問題

解答上の注意

問題1から問題3の3つの問題があります．解答用紙への記入はどのような順番でもかまいませんが，どの問題についての解答なのかは明記してください．
解答用紙には，解答だけではなく必要かつ十分な解の導出過程を採点者にわかりやすいように記述すること.
問題用紙は4枚あります．最後の1枚はメモ用の白紙です．問題用紙のホチキスははずしてもかまいません．
解答用紙は5枚綴じになっています．解答用紙のホチキスははずさないでください．裏面を使用してもかまいません．解答用紙が不足したら手を挙げて要求してください．

問題1

右の図1で示したネットワークに関して，次の問に答えよ．
	図1：有向グラフ

（1）	図1で示したネットワークの基になる有向グラフを隣接行列，接続行列，リスト表現で各々示せ．（グラフ構造のみを表現すればよく，各枝に付されたデータを表現する必要はない．）
（2）	点v₁を根として幅優先探索を行ったときの探索木を図示せよ．
（3）	点v₁を根とし，各点に後行順（後順）で番号付けをせよ．
（4）	図1で示したネットワークの基になる有向グラフを強連結成分分解し，その構造をHasse図で示せ．
（5）	図1で示されたネットワークの各枝に付された数字は各枝の長さを示しているとする．点v₁を根とした最短路木と，各点までの最短距離を求めよ．
（6）	図1で示した有向グラフの枝の向きを無視した無向グラフを考える．各枝に付された数字は各枝の重さを示しているとしたとき，ネットワークの最小木とその重さを求めよ．

問題2

文教石油はある油田で原油を産出し，精製工場Aまたは精製工場Bのどちらか一方で簡単な精製を行い，精製後に港にある貯蔵タンクに保存している．安全対策上，産出した原油の貯蔵タンク以外での保管は禁止されている．工場，精製工場A，精製工場B，貯蔵タンクの位置関係とパイプラインの敷設状況は図2に示した通りである．油田の埋蔵量は潤沢で設備も整っており大量の原油を産出することが可能である．また，港にある貯蔵タンクは十分な量が貯蔵できる能力を持っている．

パイプラインにはポンプの関係で1方向にしか原油を流すことはできない．また，パイプラインは「精製前原油専用」と｢精製後原油専用｣の2種類が存在し，精製前原油が精製後原油専用のパイプラインを通過することは許されていない．図2の各施設間の矢線は敷設してある2種類のパイプラインと原油を流せる方向を示している．

精製工場Aから精製工場Bへのパイプラインは2本あり，1本は精製前原油専用のパイプラインでもう1本は精製後原油専用のパイプラインである．精製は1回のみ行えばよいので，精製工場Aで精製済みの原油は精製工場Bで再度精製する必要はない．

図2：文教石油の設備とパイプラインの敷設状況

各パイプラインには1時間当りに流すことができる通過可能量（容量）と1キロリットル当り流すのに必要な送量費用が定まっている．それらをまとめたのが以下の表1である．また，精製工場にも単位時間に精製可能な処理能力と1キロリットル当り精製するのに必要なコストが求まっており，表2のようにまとめられている．

表1：パイプライン関連データ

パイプライン	通過原油	通過可能量（キロリットル/時間）	送量費用（万ドル/キロリットル）
油田⇒精製工場A	精製前原油	30	3
油田⇒精製工場B	精製前原油	40	6
精製工場A⇒精製工場B	精製前原油	20	1
精製工場A⇒精製工場B	精製後原油	10	2
精製工場A⇒貯蔵タンク	精製後原油	40	7
精製工場B⇒貯蔵タンク	精製後原油	30	4

表2：精製工場の処理能力と処理費用

精製工場	精製処理可能量（キロリットル/時間）	精製費用（万ドル/キロリットル）
精製工場A	40	4
精製工場B	30	2

精製前と生成後の原油の量に変化は無いと仮定する．以下の問いに答えよ．

(1)	産出規制があり現在の油田からの産出量は1時間当り50キロリットルに定められている．50キロリットルの原油を油田から貯蔵タンクに精製し送るのに最もコストがかからないプランを提案せよ．
(2)	産出規制が近々解除される見込みである．産出規制が無かったとしたら，現在の設備で油田から産出し精製し貯蔵タンクに送ることができる1時間あたりの原油の産出量は最大何キロリットルか．
(3)	産出規制解除をにらみ，増産計画を練ることになった．予算の関係上，6本あるパイプラインと2つの精製工場の合計8つの設備のなかで1つのみ強化が可能である．どの設備を強化すべきか適切な理由を沿えて提案せよ．

問題3

2001年にオペレーションズ･リサーチ学会から発刊された「OR辞典2000」によると，オペレーションズ･リサーチとは『現象を抽象化した数理モデルを構築し,　モデル分析に基づいて種々の問題,　とりわけ意思決定問題の解決を支援する方法論や技法の総称.』と記述してある．

以下の問に答えよ．

（1）	数理モデルを構築する際に気をつけなくてはならない点を簡潔に述べよ．
（2）	オペレーションズ･リサーチを用いて問題を解決する際の「モデル分析」にはどのような方法があるか．いくつかの例を挙げよ．
（3）	モデル分析の結果が必ずしも意思決定問題を解決する最良案ではないことがある．なぜそのようなことが起こるのか．理由を述べよ．

作成：	根本俊男(文教大学情報学部経営情報学科) e-mail: nemoto@shonan.bunkyo.ac.jp
実施：	2001年7月10日