オペレーションズ・リサーチの問題

難易度 1教科書の例題レベル大学数学オペレーションズ・リサーチ

あるプロジェクトは作業 $A, B, C, D, E$ の $5$ つからなる。各作業の所要時間（単位は時間）と先行作業（その作業を始める前にすべて終わっていなければならない作業）は次のとおりである。

作業	所要時間	先行作業
$A$	$3$	なし
$B$	$5$	なし
$C$	$2$	$A$
$D$	$4$	$A, B$
$E$	$3$	$C, D$

プロジェクトは時刻 $0$ に開始する。どの作業も、先行作業がすべて終わればすぐに始められ、同時に進められる作業の数に制限はないものとする。プロジェクトの最短完了時刻（時間）と、作業 $C$ の全余裕（時間）を、この順に組で答えよ。

この問題で使うもの

PERT の最早・最遅開始時刻とクリティカルパス（説明と入口の問題）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

PERT の計算を使います。前から最早開始時刻を、後ろから最遅開始時刻を求め、その差として全余裕を出します。

ヒント 2

最早開始時刻は「先行作業の最早終了時刻の最大値」、最遅終了時刻は「後続作業の最遅開始時刻の最小値」です。全余裕 $=$ 最遅開始時刻 $-$ 最早開始時刻です。

ヒント 3

最早開始時刻は $A : 0, B : 0, C : 3, D : 5, E : 9$ となります。 $E$ の最早終了時刻がプロジェクトの完了時刻です。次に、完了時刻から逆算して $C$ の最遅開始時刻を求めましょう。

答えと解説

答えを見る

(12, 4)

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

手順 1：最早開始時刻（ES）を前から順に求める。

先行作業のない作業の最早開始時刻は $0$ である。先行作業がある作業の最早開始時刻は、先行作業の「最早開始時刻 $+$ 所要時間」（最早終了時刻）のうち最大のものである。

$A$ ： $E S_{A} = 0$ （最早終了 $0 + 3 = 3$ ）
$B$ ： $E S_{B} = 0$ （最早終了 $0 + 5 = 5$ ）
$C$ ：先行作業は $A$ だけなので $E S_{C} = 3$ （最早終了 $3 + 2 = 5$ ）
$D$ ：先行作業は $A, B$ なので $E S_{D} = max (3, 5) = 5$ （最早終了 $5 + 4 = 9$ ）
$E$ ：先行作業は $C, D$ なので $E S_{E} = max (5, 9) = 9$ （最早終了 $9 + 3 = 12$ ）

最後の作業 $E$ の最早終了時刻が $12$ なので、プロジェクトの最短完了時刻は $12$ 時間である。

手順 2：最遅開始時刻（LS）を後ろから順に求める。

プロジェクトを時刻 $12$ に終えるとして、後続作業のない作業の最遅終了時刻を $12$ とする。ある作業の最遅終了時刻は、その作業を先行作業にもつ作業（後続作業）の最遅開始時刻のうち最小のものであり、最遅開始時刻 $=$ 最遅終了時刻 $-$ 所要時間である。

$E$ ：最遅終了 $12$ 、 $L S_{E} = 12 - 3 = 9$
$D$ ：後続作業は $E$ なので最遅終了 $9$ 、 $L S_{D} = 9 - 4 = 5$
$C$ ：後続作業は $E$ なので最遅終了 $9$ 、 $L S_{C} = 9 - 2 = 7$
$B$ ：後続作業は $D$ なので最遅終了 $5$ 、 $L S_{B} = 5 - 5 = 0$
$A$ ：後続作業は $C, D$ なので最遅終了 $min (7, 5) = 5$ 、 $L S_{A} = 5 - 3 = 2$

手順 3：全余裕を求める。

全余裕 $= L S - E S$ である。

作業	$E S$	$L S$	全余裕
$A$	$0$	$2$	$2$
$B$	$0$	$0$	$0$
$C$	$3$	$7$	$4$
$D$	$5$	$5$	$0$
$E$	$9$	$9$	$0$

よって作業 $C$ の全余裕は $7 - 3 = 4$ 時間である。なお、全余裕が $0$ の作業 $B \to D \to E$ がクリティカルパスであり、その所要時間の合計 $5 + 4 + 3 = 12$ は最短完了時刻と一致する。

答えは $(12, 4)$ である。

別解

前進計算（最早開始時刻 ES、最早完了時刻 EF）を行う。
$A$ : ES=0, EF=3。
$B$ : ES=0, EF=5。
$C$ : 先行 $A$ なので ES=3, EF=5。
$D$ : 先行 $A, B$ なので ES=max(3,5)=5, EF=9。
$E$ : 先行 $C, D$ なので ES=max(5,9)=9, EF=12。
よって最短完了時刻は $12$ 。

後退計算（最遅完了時刻 LF、最遅開始時刻 LS）を行う。
$E$ : LF=12, LS=9。
$C$ : 後続は $E$ なので LF=9, LS=7。
$D$ : LF=9, LS=5。

$C$ の全余裕 = LS−ES = 7−3 = 4（または LF−EF = 9−5 = 4）。

検算：クリティカルパスは $B \to D \to E$ で 5+4+3=12。 $A \to C \to E$ は 3+2+3=8 なので、12−8=4 の余裕があり、 $C$ の全余裕 4 と一致する。

したがって答えは $(12, 4)$ 。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる