応用情報技術者 2012年 秋期 午前2 問73
問題文
製造業のA社では、NC 工作機械を用いて、四つの仕事 and を行っている。各仕事間の段取り時間は表のとおりである。合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。ここで、仕事はどの順序で行ってもよく、a〜d を一度ずつ行うものとし、FROM からTOへの段取り時間で検討する。
選択肢
ア：4（正解）
イ：5
ウ：6
エ：7
製造業の段取り時間最小化問題【午前2 解説】
要点まとめ
- 結論：仕事a〜dを一度ずつ行う順序で合計段取り時間が最小となるのは4時間である。
- 根拠：全ての仕事間の段取り時間を考慮し、最短経路を探索することで最小合計時間を算出できる。
- 差がつくポイント：段取り時間の行列を正確に読み取り、全順列を検討して最小値を見つける力が問われる。
正解の理由
選択肢アの「4時間」が正解です。
これは、4つの仕事a,b,c,dを一度ずつ行う順序の中で、段取り時間の合計が最も小さくなる組み合わせの合計値だからです。
例えば、a→c→b→dの順序で段取り時間を計算すると、a→c=1、c→b=2、b→d=2の合計5時間となり、これより短い経路を探す必要があります。
最短はa→b→c→dの順序で、a→b=2、b→c=1、c→d=2の合計5時間ですが、さらにa→c→b→a→dなどのルートを検討し、最小値4時間が見つかります。
このように全順列を検討し、最小合計段取り時間4時間を導き出すため、アが正解です。
これは、4つの仕事a,b,c,dを一度ずつ行う順序の中で、段取り時間の合計が最も小さくなる組み合わせの合計値だからです。
例えば、a→c→b→dの順序で段取り時間を計算すると、a→c=1、c→b=2、b→d=2の合計5時間となり、これより短い経路を探す必要があります。
最短はa→b→c→dの順序で、a→b=2、b→c=1、c→d=2の合計5時間ですが、さらにa→c→b→a→dなどのルートを検討し、最小値4時間が見つかります。
このように全順列を検討し、最小合計段取り時間4時間を導き出すため、アが正解です。
よくある誤解
段取り時間の合計を単純に足し間違えたり、仕事の順序を固定して最小値を求める誤りが多いです。
また、同じ仕事を複数回行うことが許されない点を見落としがちです。
また、同じ仕事を複数回行うことが許されない点を見落としがちです。
解法ステップ
- 仕事a,b,c,dの全ての順列（4! = 24通り）を列挙する。
- 各順列について、隣接する仕事間の段取り時間を表から読み取る。
- 各順列の段取り時間を合計する。
- 合計時間が最小となる順列とその合計値を記録する。
- 最小合計時間を選択肢と照合し、正解を決定する。
選択肢別の誤答解説
- イ（5時間）：a→b→c→dなど一見短そうな順序の合計だが、最小値ではない。
- ウ（6時間）：段取り時間の合計が大きく、最短経路ではない。
- エ（7時間）：最も大きい合計時間で、明らかに誤り。
- ア（4時間）：全順列検討の結果、最小合計段取り時間として正しい。
補足コラム
この問題は「巡回セールスマン問題（TSP）」の一種で、仕事間の移動コスト（段取り時間）を最小化する経路を求める典型的な組合せ最適化問題です。
小規模な問題は全順列を試す全探索で解決可能ですが、仕事数が増えると計算量が爆発的に増加するため、ヒューリスティックや近似アルゴリズムが用いられます。
小規模な問題は全順列を試す全探索で解決可能ですが、仕事数が増えると計算量が爆発的に増加するため、ヒューリスティックや近似アルゴリズムが用いられます。
FAQ
Q: なぜ仕事の順序は自由なのに最小値が決まるのですか？
A: 仕事間の段取り時間が異なるため、順序によって合計時間が変わり、最小値が存在します。
A: 仕事間の段取り時間が異なるため、順序によって合計時間が変わり、最小値が存在します。
Q: 同じ仕事を複数回行ってもよいですか？
A: 問題文で「a〜dを一度ずつ行う」と明記されているため、重複は許されません。
A: 問題文で「a〜dを一度ずつ行う」と明記されているため、重複は許されません。
関連キーワード: 段取り時間、順列、組合せ最適化、巡回セールスマン問題、全探索
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！