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

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

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

作業	所要日数	先行作業
$A$	$3$	なし
$B$	$4$	なし
$C$	$2$	$A$
$D$	$2$	$A$
$E$	$3$	$B, C$

プロジェクトは時刻 $0$ に始まり、すべての作業が終わった時点で完了する。各作業は、先行作業がすべて終わればすぐに始められる。また、同時に進められる作業の数に制限はないものとする。

このプロジェクトの最短完了時刻（日）と、作業 $D$ の全余裕（日）を、この順に組で求めよ。

この問題で使うもの

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

ヒント

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

ヒント 1

PERT の手順を使います。前から最早開始時刻を、後ろから最遅開始時刻を求め、その差で全余裕を求めます。

ヒント 2

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

ヒント 3

最早開始時刻は $A : 0, B : 0, C : 3, D : 3, E : max (4, 5) = 5$ です。 $E$ の最早終了時刻から最短完了時刻がわかります。後続作業のない $D$ の最遅終了時刻は最短完了時刻と同じです。

答えと解説

答えを見る

(8, 3)

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

解説を読む

PERT の手順に従い、まず前から最早開始時刻を、次に後ろから最遅開始時刻を求めます。

1. 最早開始時刻 $E S$ と最早終了時刻 $E F$ （前から計算）

先行作業がない作業は $E S = 0$ です。先行作業がある作業は、先行作業の $E F$ のうち最大のものが $E S$ になります。また $E F = E S + 所要日数$ です。

$A$ : $E S = 0$ , $E F = 0 + 3 = 3$
$B$ : $E S = 0$ , $E F = 0 + 4 = 4$
$C$ : 先行作業は $A$ なので $E S = 3$ , $E F = 3 + 2 = 5$
$D$ : 先行作業は $A$ なので $E S = 3$ , $E F = 3 + 2 = 5$
$E$ : 先行作業は $B, C$ なので $E S = max (4, 5) = 5$ , $E F = 5 + 3 = 8$

プロジェクトの最短完了時刻は、すべての作業の $E F$ の最大値なので
$T = max (3, 4, 5, 5, 8) = 8 日$
です。

2. 最遅終了時刻 $L F$ と最遅開始時刻 $L S$ （後ろから計算）

後続作業がない作業（ $D$ と $E$ ）は $L F = T = 8$ です。後続作業がある作業は、後続作業の $L S$ のうち最小のものが $L F$ になります。また $L S = L F - 所要日数$ です。

$E$ : $L F = 8$ , $L S = 8 - 3 = 5$
$D$ : $L F = 8$ , $L S = 8 - 2 = 6$
$C$ : 後続作業は $E$ なので $L F = 5$ , $L S = 5 - 2 = 3$
$B$ : 後続作業は $E$ なので $L F = 5$ , $L S = 5 - 4 = 1$
$A$ : 後続作業は $C, D$ なので $L F = min (3, 6) = 3$ , $L S = 3 - 3 = 0$

3. 全余裕 $T F = L S - E S$

$A$ : $0 - 0 = 0$
$B$ : $1 - 0 = 1$
$C$ : $3 - 3 = 0$
$D$ : $6 - 3 = 3$
$E$ : $5 - 5 = 0$

全余裕が $0$ の作業 $A, C, E$ をつないだ $A \to C \to E$ がクリティカルパスで、その所要日数の合計 $3 + 2 + 3 = 8$ は最短完了時刻と一致します。作業 $D$ の全余裕は $3$ 日で、 $D$ は最大 $3$ 日遅れてもプロジェクト全体の完了は遅れません。

よって答えは $(8, 3)$ です。

別解

前進計算（最早時刻）：A は 0〜3、B は 0〜4、C は A の後で 3〜5、D は A の後で 3〜5。E は B と C の両方が終わってから始めるので、max(4,5)=5 から 8 まで。よって最短完了時刻は max(E の終了 8, D の終了 5)=8 日。

後退計算（最遅時刻）：完了時刻を 8 とする。E の最遅終了は 8、最遅開始は 5。D は後続がないので最遅終了は 8、最遅開始は 6。C の最遅終了は E の最遅開始 5 なので、最遅開始は 3。

作業 D の全余裕＝最遅開始−最早開始=6−3=3 日。

検算：D は 3 日目に始めて 5 日目に終わる。完了時刻 8 を延ばさずに最大 3 日遅らせられる（終了が 8 になる）ので、全余裕は 3 日で正しい。

答え：(8, 3)

この問題の確認

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

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

確認の方法について

間違いを報告する

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