オペレーションズ・リサーチ 前期期末試験

平成9年7月1日実施

　

解答上の注意：解答の導出が明らかでない問題に関しては，解答のみでなく，解答の導出過程もわかりやすく記述すること．解答用紙のホチキスははずさないこと．

問題1 以下の問いに答えなさい．
  1. 図１で与えられたネットワークにおいて，頂点①からの他のすべての頂点に至る最短距離および最短路木を求めなさい．

    図1（各枝の数字が各枝の長さを示す）
  2. 図2で与えられたネットワークにおいて，頂点①から頂点④への流量100の最小費用流を求めなさい．

    図2 （枝の容量，    一単位当たりの費用）
問題2 図3のネットワークで表現される道路網において，重要物資の①から⑫への移動を計画している．各枝（道路）に付された数字はその道路の危険度を示している．重要物資の移動なので時間・距離といった尺度ではなく，なるべく経路上の危険度の最大値が小さい経路を通って①から⑫までの移動計画を立てたい．

　

  1. どのような移動計画を作れば良いか．導出方法を説明した上で移動計画を示せ．
  2. （１）で用いた導出方法が要求に合う移動経路を導いている根拠を簡潔に示せ．

問題3

文教工業の工場（図4の頂点①）から排出され川に至る汚水処理網がある（図4参照）．頂点②，③，④，⑤は汚水のある段階の処理施設を示し，枝は汚水（中間処理済の水）を誘導する水路を示す．各汚水処理施設には設備の関係で単位時間当たりの処理量には限度がある．また，誘導水路にも単位時間当たりに流すことができる容量がある．

　

  1. この汚水処理網が単位時間当たりに処理できる汚水の最大量を求めよ．
  2. この汚水処理網の処置施設・誘導水路を改良し能力を高めることによって単位時間当たりにより多くの汚水を処理できるようにしたい．どの処理施設・誘導水路を改良すれば良いか理由と共に提案せよ．