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

難易度 4大学院入試の標準レベル大学数学オペレーションズ・リサーチ

あるプロジェクトは作業 $A, B, C, D, E, F$ の $6$ つからなる。各作業の通常の所要日数、先行作業（その作業を始める前にすべて終わっていなければならない作業）、および短縮のデータは次のとおりである。

作業	通常の所要日数	先行作業	1 日短縮あたりの追加費用（万円）	短縮できる最大日数
$A$	$4$	なし	$5$	$1$
$B$	$6$	なし	$2$	$2$
$C$	$5$	$A$	$3$	$2$
$D$	$3$	$A$	$4$	$1$
$E$	$4$	$B, D$	$6$	$2$
$F$	$3$	$C, E$	$10$	$1$

各作業は、先行作業がすべて終わればすぐに始められ、同時に進められる作業の数に制限はない。各作業の所要日数は $1$ 日単位で、表の「短縮できる最大日数」まで短縮でき、追加費用は短縮した日数に比例する。

プロジェクト全体の所要日数（すべての作業が終わるまでの日数）を $11$ 日以下にするために必要な追加費用の合計の最小値は何万円か。

この問題で使うもの

PERT の最早・最遅開始時刻とクリティカルパス（説明と入口の問題）
プロジェクトの工期短縮（クラッシング）（説明と入口の問題）

ヒント

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

ヒント 1

まず通常の所要日数で最早開始時刻を計算し、クリティカルパスとプロジェクト所要日数を求める。次に、開始から終了までのすべての経路を書き出す。

ヒント 2

所要日数を $11$ 日以下にする条件は「すべての経路の長さが $11$ 以下」である。各作業の短縮日数を変数にすると、経路ごとの不等式を条件とする費用最小化（線形計画）になる。複数の経路に共通な作業を短縮すると効率がよいことに注意する。

ヒント 3

経路は $A \to C \to F$ （ $12$ ）、 $A \to D \to E \to F$ （ $14$ ）、 $B \to E \to F$ （ $13$ ）で、それぞれ $1, 3, 2$ 日以上の短縮が必要。最小性は、3 つの不等式に適当な正の重みを掛けて足し、費用の式と係数を比べることで示せる。

答えと解説

答えを見る

17

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

解説を読む

通常時の最早開始時刻とクリティカルパス. 最早開始時刻を $E S$ 、最早終了時刻を $E F$ とする。
- $A$ : $E S = 0, E F = 4$
- $B$ : $E S = 0, E F = 6$
- $C$ : $E S = 4, E F = 9$
- $D$ : $E S = 4, E F = 7$
- $E$ : $E S = max (6, 7) = 7, E F = 11$
- $F$ : $E S = max (9, 11) = 11, E F = 14$

よって通常のプロジェクト所要日数は $14$ 日で、クリティカルパスは $A \to D \to E \to F$ である。

経路の列挙. 開始から終了までの経路は次の $3$ 本で、長さは
- $P_{1} : A \to C \to F$ … $4 + 5 + 3 = 12$
- $P_{2} : A \to D \to E \to F$ … $4 + 3 + 4 + 3 = 14$
- $P_{3} : B \to E \to F$ … $6 + 4 + 3 = 13$

である。所要日数はこれらの最大値なので、 $11$ 日以下にするには各経路を $11$ 日以下にすればよい。各作業の短縮日数を $a, b, c, d, e, f$ （ $0 \leq a \leq 1, 0 \leq b \leq 2, 0 \leq c \leq 2, 0 \leq d \leq 1, 0 \leq e \leq 2, 0 \leq f \leq 1$ の整数）とすると、条件は
$(1) a + c + f \geq 1, (2) a + d + e + f \geq 3, (3) b + e + f \geq 2$
で、最小化する費用は $Z = 5 a + 2 b + 3 c + 4 d + 6 e + 10 f$ である。

実行可能な案. $a = 1, d = 1, e = 1, b = 1$ （他は $0$ ）とすると、 $(1)$ : $1 \geq 1$ 、 $(2)$ : $1 + 1 + 1 = 3 \geq 3$ 、 $(3)$ : $1 + 1 = 2 \geq 2$ を満たし、 $Z = 5 + 4 + 6 + 2 = 17$ 万円である。このとき各経路の長さは $P_{1} = 11, P_{2} = 11, P_{3} = 11$ となり、所要日数は $11$ 日になる。（ $a = 1, e = 2$ でも $Z = 17$ となる。）

下界. 条件 $(1), (2), (3)$ にそれぞれ $1, 4, 2$ を掛けて加えると
$1 \cdot (a + c + f) + 4 (a + d + e + f) + 2 (b + e + f) = 5 a + 2 b + c + 4 d + 6 e + 7 f \geq 1 + 12 + 4 = 17.$
一方 $a, \dots, f \geq 0$ なので
$Z = 5 a + 2 b + 3 c + 4 d + 6 e + 10 f \geq 5 a + 2 b + c + 4 d + 6 e + 7 f \geq 17.$
これは線形計画法の双対問題の実行可能解（各経路に重み $1, 4, 2$ ）による下界にあたる。

したがって、追加費用の最小値は $17$ 万円である。

別解

作業の道（経路）と通常の所要日数:\n- $P_{1}$ : $A \to C \to F$ = $4 + 5 + 3 = 12$ \n- $P_{2}$ : $A \to D \to E \to F$ = $4 + 3 + 4 + 3 = 14$ \n- $P_{3}$ : $B \to E \to F$ = $6 + 4 + 3 = 13$ \n\n11 日以下にするには、 $P_{1}$ を 1 日以上、 $P_{2}$ を 3 日以上、 $P_{3}$ を 2 日以上短縮する必要がある。作業 $X$ の短縮日数を $x_{X}$ として\n $x_{A} + x_{C} + x_{F} \geq 1, x_{A} + x_{D} + x_{E} + x_{F} \geq 3, x_{B} + x_{E} + x_{F} \geq 2$ 、上限 $x_{A} \leq 1, x_{B} \leq 2, x_{C} \leq 2, x_{D} \leq 1, x_{E} \leq 2, x_{F} \leq 1$ 、費用 $5 x_{A} + 2 x_{B} + 3 x_{C} + 4 x_{D} + 6 x_{E} + 10 x_{F}$ を最小化。\n\n $P_{2}$ の 3 日は $A, D, E, F$ から短縮する。費用の安い順に $D$ (4), $A$ (5), $E$ (6), $F$ (10) なので $P_{2}$ だけで最低 $4 + 5 + 6 = 15$ 万円。\n\n- $x_{A} = x_{D} = x_{E} = 1$ (15 万円): $P_{1}$ は $A$ で 1 日短縮されて OK。 $P_{3}$ は $E$ で 1 日のみなので $B$ を 1 日（2 万円）追加して合計 17 万円。（ $P_{3}$ は 2 日短縮が必要で $B$ 2 日は 4 万円より、 $E$ を 1 日短縮したうえ $B$ 1 日の方が安い。）\n- $x_{A} = 1, x_{E} = 2$ (17 万円): $P_{2}$ : 3 日、 $P_{3}$ : 2 日、 $P_{1}$ : 1 日、すべて OK で 17 万円。\n- $x_{D} = 1, x_{E} = 2$ (16 万円) では $P_{1}$ が短縮されず、 $C$ を 1 日（3 万円）足して 19 万円。\n- $F$ を使う案は $F$ だけで 10 万円かかり、 $D, A$ との組み合わせで $19$ 万円以上。\n\n以上より最小は 17 万円。検算: $x_{A} = x_{B} = x_{D} = x_{E} = 1$ のとき $P_{1} = 12 - 1 = 11$ 、 $P_{2} = 14 - 3 = 11$ 、 $P_{3} = 13 - 2 = 11$ 、費用 $5 + 2 + 4 + 6 = 17$ 。 $P_{2}$ の下限 15 に、 $P_{3}$ を満たすための追加（ $E$ の短縮が 1 日以下なら $B$ を足す）で最低 2 万円必要で、15 万円の組は $P_{3}$ が不足するため 17 が最小。

この問題の確認

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

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

確認の方法について

間違いを報告する

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