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

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

あるプロジェクトは作業 $1$ から作業 $8$ までの $8$ つの作業からなる。各作業の所要日数と先行作業（その作業を始める前にすべて終わっていなければならない作業）は次のとおりである。

作業	所要日数	先行作業
$1$	$3$	なし
$2$	$5$	なし
$3$	$4$	$1$
$4$	$2$	$1$
$5$	$6$	$2, 4$
$6$	$3$	$3$
$7$	$4$	$5, 6$
$8$	$2$	$3$

各作業は、先行作業がすべて終わればすぐに始めることができ、同時に進められる作業の数に制限はない。プロジェクトは時刻 $0$ に始まり、すべての作業が終わった時点で完了する。プロジェクトの完了時刻を最も早い値にしたとき、全余裕（最遅開始時刻と最早開始時刻の差）が $0$ である作業の番号の集合を求めよ。

この問題で使うもの

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

ヒント

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

ヒント 1

まず前進計算で各作業の最早開始時刻とプロジェクトの最早完了時刻を求め、次に後退計算で最遅開始時刻を求めます。

ヒント 2

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

ヒント 3

前進計算すると $E S_{5} = 5$ , $E S_{7} = 11$ で、最早完了時刻は $15$ 日になります。ここから後退計算で各作業の最遅開始時刻を求めましょう。

答えと解説

答えを見る

{1, 2, 4, 5, 7}

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

解説を読む

作業 $i$ の所要日数を $d_{i}$ 、最早開始時刻を $E S_{i}$ 、最早終了時刻を $E F_{i} = E S_{i} + d_{i}$ とする。

前進計算（最早開始時刻）

先行作業がない作業は $E S = 0$ 、それ以外は先行作業の $E F$ の最大値が $E S$ になる。

作業 $1$ ： $E S_{1} = 0$ , $E F_{1} = 3$
作業 $2$ ： $E S_{2} = 0$ , $E F_{2} = 5$
作業 $3$ ： $E S_{3} = E F_{1} = 3$ , $E F_{3} = 7$
作業 $4$ ： $E S_{4} = E F_{1} = 3$ , $E F_{4} = 5$
作業 $5$ ： $E S_{5} = max (E F_{2}, E F_{4}) = max (5, 5) = 5$ , $E F_{5} = 11$
作業 $6$ ： $E S_{6} = E F_{3} = 7$ , $E F_{6} = 10$
作業 $7$ ： $E S_{7} = max (E F_{5}, E F_{6}) = max (11, 10) = 11$ , $E F_{7} = 15$
作業 $8$ ： $E S_{8} = E F_{3} = 7$ , $E F_{8} = 9$

プロジェクトの最早完了時刻は $max (E F_{7}, E F_{8}) = max (15, 9) = 15$ 日である。

後退計算（最遅開始時刻）

最遅終了時刻を $L F_{i}$ 、最遅開始時刻を $L S_{i} = L F_{i} - d_{i}$ とする。後続作業がない作業（作業 $7$ , $8$ ）は $L F = 15$ 、それ以外は後続作業の $L S$ の最小値が $L F$ になる。

作業 $7$ ： $L F_{7} = 15$ , $L S_{7} = 11$
作業 $8$ ： $L F_{8} = 15$ , $L S_{8} = 13$
作業 $6$ ： $L F_{6} = L S_{7} = 11$ , $L S_{6} = 8$
作業 $5$ ： $L F_{5} = L S_{7} = 11$ , $L S_{5} = 5$
作業 $3$ ： $L F_{3} = min (L S_{6}, L S_{8}) = min (8, 13) = 8$ , $L S_{3} = 4$
作業 $4$ ： $L F_{4} = L S_{5} = 5$ , $L S_{4} = 3$
作業 $2$ ： $L F_{2} = L S_{5} = 5$ , $L S_{2} = 0$
作業 $1$ ： $L F_{1} = min (L S_{3}, L S_{4}) = min (4, 3) = 3$ , $L S_{1} = 0$

全余裕

全余裕 $T F_{i} = L S_{i} - E S_{i}$ は
$T F_{1} = 0, T F_{2} = 0, T F_{3} = 1, T F_{4} = 0, T F_{5} = 0, T F_{6} = 1, T F_{7} = 0, T F_{8} = 6.$

よって全余裕が $0$ の作業は $1, 2, 4, 5, 7$ である。実際、経路 $1 \to 4 \to 5 \to 7$ （ $3 + 2 + 6 + 4 = 15$ ）と経路 $2 \to 5 \to 7$ （ $5 + 6 + 4 = 15$ ）がともに長さ $15$ のクリティカルパスになっており、その上の作業が求める集合 ${1, 2, 4, 5, 7}$ に一致する。

別解

前進計算（最早開始 ES、最早終了 EF）：
作業1: ES=0, EF=3。作業2: ES=0, EF=5。作業3: ES=3, EF=7。作業4: ES=3, EF=5。作業5: ES=max(5,5)=5, EF=11。作業6: ES=7, EF=10。作業7: ES=max(11,10)=11, EF=15。作業8: ES=7, EF=9。
完了時刻は max(EF) = 15。

後退計算（最遅終了 LF、最遅開始 LS）：
作業7: LF=15, LS=11。作業8: LF=15, LS=13。作業6: LF=11, LS=8。作業5: LF=11, LS=5。作業3: LF=min(LS6=8, LS8=13)=8, LS=4。作業4: LF=5, LS=3。作業2: LF=5, LS=0。作業1: LF=min(LS3=4, LS4=3)=3, LS=0。

全余裕 = LS − ES：作業1: 0, 作業2: 0, 作業3: 4−3=1, 作業4: 0, 作業5: 0, 作業6: 8−7=1, 作業7: 0, 作業8: 13−7=6。

全余裕が 0 の作業は 1, 2, 4, 5, 7。
検算：経路 2→5→7 は 5+6+4=15、経路 1→4→5→7 は 3+2+6+4=15 でどちらも 15 に等しく、他の経路 1→3→6→7 は 3+4+3+4=14、1→3→8 は 9 で 15 未満。よってクリティカルな作業は 1, 2, 4, 5, 7。

この問題の確認

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

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

確認の方法について

間違いを報告する

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

作業	所要日数	先行作業
$A$	$4$	なし
$B$	$6$	なし
$C$	$3$	$A$
$D$	$5$	$A$
$E$	$7$	$B, C$
$F$	$4$	$B$
$G$	$6$	$D, E$
$H$	$5$	$D, F$
$I$	$3$	$G, H$