生産管理論 2001年度中間試験問題

解答上の注意

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

問題1

文教工芸では，高級アンティーク家具修繕を行っている．家具の修繕には「分解作業」，「補修作業」，「組立・仕上作業」の3つの工程があり，それらに順に実施し，修繕作業を終える．各工程には専門の職人が一人ずつしかおらず，ひとつの工程で同時に２つ以上の修繕依頼品を扱うこはできない．

さて，休み明けに早速4点の依頼が届いた．作業見積もりを行った結果，各依頼家具の修繕に必要な各工程での必要日数は以下の表の通りとなった．

以下の問いに答えよ．

問題2

ある工場では，毎日1kgの産業廃棄物が排出される．この産業廃棄物は，工場内の特殊保管庫で一時的に保管され，工場からの依頼に応じて専門処理業者により一括処理される．専門業者は工場からの依頼があると， すぐに処理作業を行い，依頼された量の産業廃棄物をすべて工場外に搬出する．

この産業廃棄物の保管や処理に要する費用は以下のようにまとめられる．なお，1ヶ月は30日，1年間は360日で換算する．

以下の問いに答えよ．

問題3

（問題3と問題4のどちらか一方を選択し解答しなさい）

各枝に正の重みが与えられたグラフがある．このグラフ上の全点を張る木の中で，枝の重みの総和が最小なものを「最小木」とよぶ．この最小木は「クラスカル法」と名づけられている以下のアルゴリズムで求められることが知られている．

次の問いに答えよ．

(1)	図1で与えられたグラフの最小木を求めなさい．答えは，グラフを図示し，最小木を構成する枝を太線にすることで示しなさい．	図1 グラフ
(2)	与えられたグラフの点数がn個，枝数がm本である時，最小木を求める問題の入力サイズを求めよ．
(3)	クラスカル法をできる限り効率よく実行したい．どのような点に工夫を加えると効率よく実行できるか．工夫を加えるべき箇所を挙げ，その方法を説明せよ．
(4)	上記で提案した工夫を加えた上でクラスカル法を実行した際の，クラスカル法の最悪計算量を評価せよ．ただし，評価結果は漸近計算量で表現せよ．
(5)	n=1,000,000(点数が百万),m=3,000,000(枝数が三百万)のサイズのグラフ上で最小木をクラスカル法で求める．1秒に1億回演算可能なコンピュータを用いて導出を試みた場合，おおよそどの程度の時間で最小木を導くか求めなさい．なお，必要ならlog102=0.3010とみなし利用してよい．

問題4

図2のような距離関係にある4つの場所を順に回って，出発した地点に帰ってきたい．

以下の問いに答えよ．

(1)	家から出発し，家→競技場→学校→公園→家と順に回って，家に戻ってきたとする．移動に要した総距離を求めよ．	図2 4つの場所間の距離
(2)	家から出発し，3つの場所を順に回り，家に帰ってくる方法は何通りあるか．
(3)	家から出発し，3つの場所を順に回り，家に帰ってくるルートのうち，総移動距離を最小にするルートを求めよ．その際，どのようにそのルートを導出したのかの過程と，そのルートが最短である 根拠を必ず明記せよ．
(4)	順に回ってきたい場所の数が家を含めてnヶ所の時，(3)で用いた方法の最悪計算量を評価せよ．
(5)	小問(3)で用いた方法で最短のルートを導出する．n=16のとき，1秒間に1億回の演算が可能なコンピューターを用いて計算を行った場合，おおよそどの程度の時間で最短ルートを導くのかもとめなさい． 必要ならば，16!=20922789888000，15!=1307674368000として，利用してよい．

配点と講評