オペレーションズ・リサーチの問題
あるプロジェクトは作業 の つからなる。各作業の通常の所要日数、先行作業（その作業を始める前にすべて終わっていなければならない作業）、短縮できる最大日数、 日短縮するごとにかかる追加費用は次の表のとおりである。
| 作業 | 通常の所要日数 | 先行作業 | 短縮できる最大日数 | 日あたりの短縮費用（万円） |
|---|---|---|---|---|
| なし | ||||
| なし | ||||
短縮は 日単位で行い、短縮費用は短縮した日数に比例するものとする。プロジェクト全体の完了までの日数を 日にするために必要な追加費用の最小値は何万円か。
この問題で使うもの
- プロジェクトの工期短縮（クラッシング）（説明と入口の問題）
この問題を解けるようになるまで（2 技能）
読み込み中…
右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
一覧で見る（前提が先）
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
まず PERT で通常の工期とすべての経路の長さを求めましょう。工期を 日にするには、すべての経路を 日以下にする必要があります。
ヒント 2
経路は と の 本で、どちらも 日です。共通の作業 の短縮日数 が か かで場合分けすると、残りは各経路ごとに別々に最小費用を考えられます。短縮できる最大日数に注意しましょう。
ヒント 3
のとき、経路 は で合わせて 日、経路 は で合わせて 日短縮する必要があります。経路 は を 日短縮するのが最も安く 万円です。経路 は が 日までしか短縮できないことから費用の下限を考えましょう。
答えと解説
答えを見る
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
手順 1：通常の工期と経路を求める。
最早開始時刻を順に計算する。 は 日目に開始できる。 は の終了後なので 日目、 は の終了後なので 日目に開始できる。 は と の両方が終わってから始まるので
より 日目に開始でき、プロジェクトは 日で完了する。
始点から終点までの経路は
- 経路 ：（ 日）
- 経路 ：（ 日）
の 本だけで、どちらも 日である。工期はこの 本の長さの大きい方なので、工期を 日にするには、両方の経路の長さをそれぞれ 日以下にしなければならない。
手順 2：問題を式で表す。
作業 の短縮日数をそれぞれ （ 以上の整数）とし、 とする。条件は
で、追加費用は
である。 は経路 だけ、 は経路 だけに含まれるので、 を決めれば「 を満たす の最小化」と「 を満たす の最小化」を別々に考えればよい。 は か なので場合分けする。
手順 3： の場合。
経路 ： が必要。 日あたりの費用は が 万円で の 万円より安く、 は 日まで短縮できるので、 のとき最小で 万円。実際、 のとき なので、経路 の費用は 万円以上である。
経路 ： が必要。安い （ 万円）は 日までしか短縮できないので 、よって 。このとき
なので経路 の費用は 万円以上で、 のとき 万円となり等号が成り立つ。
よって のときの最小費用は 万円。
手順 4： の場合。
の費用が 万円かかる。経路 は が必要で、 より最小 万円（）。経路 は が必要で、 より最小 万円（）。
よって のときの最小費用は 万円。
手順 5：結論。
より、最小費用は のときの 万円である。このとき所要日数は で、経路 は 日、経路 は 日となり、工期はちょうど 日になっている。
以上より、追加費用の最小値は
である。
別解
通常の所要日数での経路の長さは、 が 日、 が 日で、どちらも 日（ともに最長経路）である。したがって 日にするには、両方の経路をそれぞれ 日以上短縮する必要がある。
作業 の短縮日数を とすると、条件は次のとおり。
-
-
-
費用は を最小化する。
を使わない場合：
- 経路 側は、費用 の を 日短縮するのが最安で、費用は 。
- 経路 側は、 を 日（費用 ）、 を 日（費用 ）短縮するのが最安で、費用は 。
- 合計は 万円。
を 日使う場合：
- の費用は 。
- 残りは各経路であと 日ずつ必要で、 に 、 に かかる。
- 合計は 万円。
を使うより使わない方が安いので、最小は 万円。
検算： とすると、 は 日、 は 日となり、条件を満たす。費用は 万円。