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