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

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

あるプロジェクトは作業 $A, B, C, D, E, F, G$ の $7$ つからなる。各作業の所要日数には、楽観値 $a$ 、最可能値 $m$ 、悲観値 $b$ の $3$ つの見積もりが与えられている。先行作業とは、その作業を始める前にすべて終わっていなければならない作業のことである。

作業	先行作業	$a$	$m$	$b$
$A$	なし	$2$	$4$	$6$
$B$	なし	$3$	$5$	$13$
$C$	$A$	$1$	$3$	$5$
$D$	$A$	$4$	$6$	$14$
$E$	$B, C$	$2$	$5$	$8$
$F$	$D, E$	$3$	$4$	$11$
$G$	$E$	$1$	$2$	$9$

PERT の手法に従い、各作業の所要日数の期待値 $t_{e}$ と分散 $σ^{2}$ を
$t_{e} = \frac{a + 4 m + b}{6}, σ^{2} = (\frac{b - a}{6})^{2}$
で定める。各作業の所要日数を $t_{e}$ として最早開始時刻を計算し、プロジェクトの完了時刻（期待値） $T$ とクリティカルパスを求める。さらに、クリティカルパス上の作業の所要日数は互いに独立であるとして、クリティカルパス上の作業の分散の和 $V$ を求める。

$T$ と $V$ をこの順に組 $(T, V)$ で答えよ。なお、プロジェクトは時刻 $0$ に開始し、先行作業がすべて終わればその作業はすぐに開始できるものとする。

この問題で使うもの

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

ヒント

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

ヒント 1

まず各作業の期待所要日数 $t_{e}$ を公式で計算し、それを所要日数とみなして最早開始時刻を前から順に求めましょう。

ヒント 2

作業の最早開始時刻は先行作業の最早終了時刻の最大値です。完了時刻を求めたら、後ろから最遅時刻を計算し、余裕が $0$ の作業をつなげるとクリティカルパスになります。

ヒント 3

$t_{e}$ は $A : 4, B : 6, C : 3, D : 7, E : 5, F : 5, G : 3$ です。 $E$ の最早開始時刻は $max (6, 7) = 7$ 、 $F$ の最早開始時刻は $max (11, 12) = 12$ になります。

答えと解説

答えを見る

(17, \frac{11}{3})

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

解説を読む

1. 期待所要日数と分散

$t_{e} = \frac{a + 4 m + b}{6}$ 、 $σ^{2} = (\frac{b - a}{6})^{2}$ を計算する。

$A$ : $t_{e} = \frac{2 + 16 + 6}{6} = 4$ 、 $σ^{2} = (\frac{4}{6})^{2} = \frac{4}{9}$
$B$ : $t_{e} = \frac{3 + 20 + 13}{6} = 6$ 、 $σ^{2} = (\frac{10}{6})^{2} = \frac{25}{9}$
$C$ : $t_{e} = \frac{1 + 12 + 5}{6} = 3$ 、 $σ^{2} = \frac{4}{9}$
$D$ : $t_{e} = \frac{4 + 24 + 14}{6} = 7$ 、 $σ^{2} = \frac{25}{9}$
$E$ : $t_{e} = \frac{2 + 20 + 8}{6} = 5$ 、 $σ^{2} = (\frac{6}{6})^{2} = 1$
$F$ : $t_{e} = \frac{3 + 16 + 11}{6} = 5$ 、 $σ^{2} = (\frac{8}{6})^{2} = \frac{16}{9}$
$G$ : $t_{e} = \frac{1 + 8 + 9}{6} = 3$ 、 $σ^{2} = \frac{16}{9}$

2. 最早開始時刻 (ES) と最早終了時刻 (EF)

各作業の ES は先行作業の EF の最大値（先行作業がなければ $0$ ）であり、EF $=$ ES $+ t_{e}$ である。

$A$ : ES $= 0$ , EF $= 4$
$B$ : ES $= 0$ , EF $= 6$
$C$ : ES $= 4$ , EF $= 7$
$D$ : ES $= 4$ , EF $= 11$
$E$ : ES $= max (6, 7) = 7$ , EF $= 12$
$F$ : ES $= max (11, 12) = 12$ , EF $= 17$
$G$ : ES $= 12$ , EF $= 15$

よって $T = max (17, 15) = 17$ である。

3. クリティカルパス

最遅終了時刻 (LF) と最遅開始時刻 (LS $=$ LF $- t_{e}$ ) を後ろから計算する。

$F$ : LF $= 17$ , LS $= 12$
$G$ : LF $= 17$ , LS $= 14$
$E$ : LF $= min (12, 14) = 12$ , LS $= 7$
$D$ : LF $= 12$ , LS $= 5$
$C$ : LF $= 7$ , LS $= 4$
$B$ : LF $= 7$ , LS $= 1$
$A$ : LF $= min (4, 5) = 4$ , LS $= 0$

余裕（LS $-$ ES）が $0$ の作業は $A, C, E, F$ である。したがってクリティカルパスは $A \to C \to E \to F$ （ $4 + 3 + 5 + 5 = 17$ ）となる。

確認のため、ほかの経路の長さを求めると次のとおりで、いずれも $17$ より短い。よってクリティカルパスはこの $1$ 本だけである。

$A \to D \to F$ : $16$
$B \to E \to F$ : $16$
$A \to C \to E \to G$ : $15$
$B \to E \to G$ : $14$

4. 分散の和

クリティカルパス上の作業の所要日数は独立なので、その和の分散は各分散の和である。
$V = \frac{4}{9} + \frac{4}{9} + 1 + \frac{16}{9} = \frac{4 + 4 + 9 + 16}{9} = \frac{33}{9} = \frac{11}{3}$

よって $(T, V) = (17, \frac{11}{3})$ である。

別解

各作業の期待値と分散を計算する。
A: t=(2+16+6)/6=4, σ²=(4/6)²=4/9
B: t=(3+20+13)/6=6, σ²=(10/6)²=25/9
C: t=(1+12+5)/6=3, σ²=(4/6)²=4/9
D: t=(4+24+14)/6=7, σ²=(10/6)²=25/9
E: t=(2+20+8)/6=5, σ²=1
F: t=(3+16+11)/6=5, σ²=(8/6)²=16/9
G: t=(1+8+9)/6=3, σ²=(8/6)²=16/9

最早開始・終了時刻:
A: 0〜4、B: 0〜6
C: 4〜7（先行 A）
D: 4〜11（先行 A）
E: 先行 B(6), C(7) より開始 7、終了 12
F: 先行 D(11), E(12) より開始 12、終了 17
G: 先行 E より開始 12、終了 15

完了時刻は T=max(17,15)=17。
クリティカルパスは F の開始を決める E を通り、E の開始を決める C を通り、C の先行は A。よって A→C→E→F で 4+3+5+5=17。他の経路を確認する。A→D→F は 4+7+5=16、B→E→F は 6+5+5=16、A→C→E→G は 15。したがって A→C→E→F が唯一のクリティカルパス。

分散の和 V = 4/9 + 4/9 + 1 + 16/9 = 24/9 + 1 = 8/3 + 1 = 11/3。

検算: 4/9+4/9+9/9+16/9=33/9=11/3。

答え: (T,V)=(17, 11/3)

この問題の確認

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

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

確認の方法について

間違いを報告する

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