公務員試験について

質問

この問題なぜ解答が21日になるのかわかりません。また、問題の解き方も教えてください。

問題
10人でa-f の作業を行うことになった。 各作業の作業人数、作業時間、作業開始の条件が 次の表の通りであるとき 作業開始からa-f のすべての作業を終了するまでの最少日数はどれか。 ただし 各 作業は 常に表に示す作業人数で行うものとし、 一つの作業は開始すると終了するまで 中断できないものとする。

解説
作業期間、作業開始の条件 、一度に作業できる 人数が10人までであることを 考慮して、 日数についての 線分図を 書く。 図より 全体の 作業が終了する 最小日数は 21日となる。

回答No.4

staratras

No.3です。少し補足（蛇足？）です。

この問題では、「一つの作業は開始すると終了するまで 中断できないものとする」いう条件がありますが、仮にこの制約がなかったとすればどうなるか考えてみました。

それが下の図の下段で、Cの作業を中断することによって19日間ですべての作業を終えることができます。この場合もカギを握っているのは「Cの作業をいつやるか」ということです。

回答No.3

staratras

この問題では「Cの作業をいつやるか」が最大のポイントです。

甲の作業が終了していないと乙が開始できないなど、他の作業は、別の作業と関連付けられているのに対し、Cだけはそうした条件・制約が一切ないからです。

そこでまずCを考えずに、ほかの作業を順序立てて並べてみると下の上段の表のようになります。ここで1日の作業人数の合計に着目すると、7日目から10日目まで6人しか働いていないことに気付きます。これはAで6人働いているため、Bが終わってもEを始めるには人数が足りないためですが、4人がまだ働けます。

そこで4人でできるCの作業を7日目以降14日目までやることにしたのが中段の表です。22日かかります。これを上段と比較してみると11日目から13日目にかけては働いている人数が8人→7人に減少していることがわかり、この部分を改善すれば日数を短縮できるのではないかとわかります。

このためにA終了後にD（3人で5日）ではなくE（5人で6日）の作業を開始することに変更したのが下段の表です。21日で終了します。これが最少日数です。

回答No.2

paranoia23

いったん、人数の制約をとっぱらった状態で考えると解けると思います。

無限に人がいたとして、
Ａのルートと、Ｂのルートと、Ｃのルートをパラレルにこなしても、
Ａのルートの「最短１８日の壁」
は越えられないと考えます。

　　　　　　１０日　　５日
　　　　◆◆◆Ａ◆◆◆Ｄ◆◆◆◆
　　　　◆　　　　　　　　　　◆　　　３日
　　　　◆　　　　　　　　　　◆◆◆◆Ｆ◆◆◆◆終了
　　　　◆　　　　　　　　　　|　　　 |
開始◆◆◆－－Ｂ－－－Ｅ－－－　　　 |
　　　　|　　６日　　 ６日　　　　　　|
　　　　|　　　　　　　　　　　　　　 |
　　　　|　　　　　　　　　　　　　　 |
　　　　－－－Ｃ－－－－－－－－－－－
　　　　　　 ７日

なので、最初にＡを着手しそうだというのは辿り着くと思います。

そうすると、
【案１】Ａを進めてる間、空いてる人にはＢ－Ｅを進めて貰うプランなのか？
【案２】Ａを進めてる間、空いてる人にはＣを進めて貰うプランなのか？
　　　　（案２は、ＢのあとにＣを進めることと等価です。
　　　　　１３日目の状況が変わりません。）

という部分を考えることになり、

以下の図のどちらかになります。

【案１：１０日経過後】

　　　　　　　　　　　　残５日
　　　　◆◆◆Ａ完了－－－Ｄ－－
　　　　◆　　　　　　　　　　 |　　残３日
　　　　◆　　　　　　　　　　 －－－Ｆ－－－－終了
　　　　◆　　　　　　　　　　 |　　　|
開始◆◆◆◆◆Ｂ完了－－－Ｅ－－　　 |
　　　　|　　　　　　　 残６日　　　　|
　　　　|　　　　　　　　　　　　　　 |
　　　　|　　　　　　　　　　　　　　 |
　　　　－－－Ｃ－－－－－－－－－－－
　　　　　　　残７日

　　　※人数の関係で、Ｅの開始は、待たされてしまう。

【案２：１０日経過後】

　　　　　　　　　　　　残５日
　　　　◆◆◆Ａ完了－－－Ｄ－－
　　　　◆　　　　　　　　　　　｜　　残３日
　　　　◆　　　　　　　　　　　 －－－Ｆ－－－－終了
　　　　◆　残３日　　　残６日　｜　　 ◆
開始◆◆◆－－Ｂ－－－－－Ｅ－－－　　 ◆
　　　　◆　（消化３日）　　　　　　　 ◆
　　　　◆　　　　　　　　　　　　　　 ◆
　　　　◆　　　　　　　　　　　　　　 ◆
　　　　◆◆◆Ｃ完了◆◆◆◆◆◆◆◆◆◆

では、案１と案２では、どっちが得でしょうか？

****************************************************

上の図に対して、
「きりがよい状況まで時計を進める」ということをすると、
「単純なモデル」として捉えることができると思います。

【案１：１６日経過後】

　　　　　　　　　　　　残５日
　　　　◆◆◆Ａ完了－－－Ｄ－－
　　　　◆　　　　　　　　　　　|　　残３日
　　　　◆　　　　　　　　　　　－－－Ｆ－－－－終了
　　　　◆　　　　　　　　　　　|　　 |
開始◆◆◆　（※中央のルートは完了）　 |
　　　　|　　　　　　　　　　　　　　 |
　　　　|　　　　　　　　　　　　　　 |
　　　　|　　　　　　　　　　　　　　 |
　　　　－－－Ｃ－－－－－－－－－－－
　　　　　　　残７日

　　⇒　時間がかかる方は８日なので、１６＋８＝計２４日

【案２：１３日経過後】

　　　　　　　　　　　　残２日（３日消化）
　　　　◆◆◆Ａ完了－－－Ｄ－－
　　　　◆　　　　　　　　　　　 |　残３日
　　　　◆　　　　　　　　　　　 －－Ｆ－－－－終了
　　　　◆　　　　　　　　　　　 |
開始◆◆◆◆◆Ｂ完了－－－Ｅ－－－
　　　　　　　　　　　　残６日

　　　　　（※下のルートは完了）
　　　　　（※Ｂ・Ｃの順でも、Ｃ・Ｂの順でも状況は同じ）

　　⇒　時間がかかる方は９日なので、１３＋９＝計２２日

となり、２２日が答えです。
（※本の解答は誤っているかと思われます。）
.

回答No.1

山田 太郎（@f_a_007）

まず、A、C作業班始動。C終了後にF作業開始。

A(6)・・・+10日
C(4)・・・+00日
F(3)・・・+00日

【10日目の現状】

・1人仕事なし
・残りの作業は

B（3人）・・・6日
D（3人）・・・5日
E（5人）・・・6日

そこで10日目にB作業開始し、翌日にE作業スタート。

B(6)・・・・・+05日
E(3)・・・・・+01日

【16日目の現状】

・残りの作業は

D（3人）・・・+05日

よって《最短作業日＝21日》となる。