平成24年度 秋期 応用情報技術者試験 午前 問73
ストラテジ／ビジネスインダストリ製造業のA社では，NC工作機械を用いて，四つの仕事a〜dを行っている。各仕事間の段取り時間は表のとおりである。合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。ここで，仕事はどの順序で行ってもよく，a〜dを一度ずつ行うものとし，FROMからTOへの段取り時間で検討する。 （単位 時間） 仕事aから仕事bへ2，仕事aから仕事cへ1，仕事aから仕事dへ2 仕事bから仕事aへ1，仕事bから仕事cへ1，仕事bから仕事dへ2 仕事cから仕事aへ3，仕事cから仕事bへ2，仕事cから仕事dへ2 仕事dから仕事aへ4，仕事dから仕事bへ3，仕事dから仕事cへ2 （注：本サイトでは原問題の表を文字表記に変換しています）
出典：平成24年度 秋期 応用情報技術者試験 午前 問73
- ア4
- イ5
- ウ6
- エ7
正解：ア
解説
4つの仕事を一度ずつ行う順序（経路）のうち，段取り時間の合計が最小になるものを探すと，b→a→c→dの順（1＋1＋2＝4時間）が最小になります。他の順序ではいずれも合計が5時間以上になります。
選択肢ごとの解説
- ア正しい。b→a→c→dの順で行うと，段取り時間の合計は1＋1＋2＝4時間となり最小です。
- イ誤り。多くの順序でこの値になりますが，b→a→c→d（4時間）より小さい，より良い順序が存在します。
- ウ誤り。段取り時間の組合せを最適化せずに計算した場合に生じる値であり，最小値ではありません。
- エ誤り。段取り時間が大きい組合せを含む順序で計算した場合に生じる値であり，最小値ではありません。