基本情報技術者平成20年秋期 午前問76

午前問76

A社の営業員がA社から出発して,取引先のB社,C社,D社を1回ずつ訪問してA社に戻りたい。各社間(FromからTo)の所要時間を表のとおりとするとき,最短の巡回時間は何分か。
76.gif/image-size:276×139

分類

ストラテジ系 » 企業活動 » OR・IE

正解

解説

訪問はA社を出発して3社を巡った後にA社に戻るので、訪問先を○,△,□とすれば訪問ルートは[A→○→△→□→A]と表せます。そして、○→△→□に入る3社の訪問順には次の6通りがあります。
  • B→C→D
  • B→D→C
  • C→B→D
  • C→D→B
  • D→B→C
  • D→C→B
上記の訪問順すべてについて所要時間を計算します。
  • [A→B→C→D→A] 20+50+30+40=140(分)
    76_1.gif/image-size:276×127
  • [A→B→D→C→A] 20+25+30+35=110(分)
    76_2.gif/image-size:276×127
  • [A→C→B→D→A] 35+50+25+40=150(分)
    76_3.gif/image-size:276×127
  • [A→C→D→B→A] 35+30+25+20=110(分)
    76_4.gif/image-size:276×127
  • [A→D→B→C→A] 40+25+50+35=150(分)
    76_5.gif/image-size:276×127
  • [A→D→C→B→A] 40+30+50+20=140(分)
    76_6.gif/image-size:276×127
したがって所要時間が最短となるのはルート[A→B→D→C→A]および[A→C→D→B→A]で110分になります。
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop