☞ 全方位學習筆記：關鍵路徑分析 (Critical Path Analysis, D1)

歡迎來到關鍵路徑分析！

你好！如果你正在研讀決策數學 1 (Decision Mathematics 1)，關鍵路徑分析 (CPA) 絕對是其中最實用且有趣的課題之一。別擔心，即使圖論 (Graph Theory) 初看起來有點抽象，CPA 本質上是一個能讓你高效規劃和管理項目的強大工具。

我們將學習什麼？ 我們會學會如何將複雜的項目（例如蓋房子或產品發布）建立成網絡模型。隨後，我們會利用簡單的算術計算出完成整個項目的最短時間，並識別出那些絕對不能延誤的重要任務。這段最短時間即稱為關鍵路徑 (Critical Path)。

---

第一部分：建立項目模型 – 活動網絡 (Activity Networks)

1.1 活動、工期與優先次序

在動手畫圖之前，我們需要先理解項目的基本組成要素。

  • 活動 (Activity)： 需要進行的特定任務（例如：「打地基」）。活動需要時間來完成。
  • 工期 (Duration)： 完成該活動所需的時間（以小時、天或週為單位）。
  • 優先次序 (Precedence) 或依賴關係 (Dependency)： 在新活動開始之前必須完成哪些活動。這是構建網絡的核心資訊。

例子： 如果活動 B 要求必須先完成活動 A，我們稱 A 為 B 的緊前活動 (Immediate Predecessor)。

1.2 繪製活動網絡 (AOA)

在決策數學中，我們通常使用箭線圖法 (Activity on Arc, AOA)。

  • 箭線 (Arcs / Arrows)： 代表活動本身。活動名稱及其工期會標註在箭頭上。
  • 節點 (Nodes / Vertices)： 代表事件 (Events)——即某一組活動已完成，且新活動可以開始的時間點。

方向規則： 箭頭必須始終從較早的事件（節點）指向較晚的事件。

繪製網絡的逐步指南
  1. 從單一節點（節點 1）開始，代表項目的起點。
  2. 對於所有沒有緊前活動的項目，從節點 1 畫出相應的箭頭。
  3. 繼續添加節點和箭頭，確保只有在所有緊前活動都到達前置節點後，下一個活動才能開始。
  4. 以單一的最終節點作為網絡的結束。

⚠ 檢查站： 將節點想像成火車站，將活動想像成火車旅程。你只能在上一班火車順利抵達後，才能離開車站！

1.3 核心概念：虛擬活動 (Dummy Activities)

這通常是最棘手的部分，但對於畫出正確的網絡至關重要。虛擬活動 (Dummy Activity) 是一種概念上的活動，其耗時為零（工期 = 0）。它以虛線箭頭表示。

我們何時必須使用虛擬活動？

為了確保網絡準確反映依賴關係，我們主要出於以下兩個原因使用虛擬活動：

  1. 唯一性規則 (Uniqueness Rule) 衝突： 如果兩個或多個活動擁有完全相同的起點節點和終點節點。（這在 AOA 中是不允許的，因為這樣無法區分這些活動。）
  2. 複雜依賴規則（「重疊」規則）： 這是最常見的原因。觀察以下依賴關係：
    • 活動 C 僅依賴於 A。
    • 活動 D 依賴於 A 和 B。
    如果 A 和 B 在同一個節點結束，D 可以開始，但 C 絕對不能依賴於 B。此時需要一個虛擬活動，在不引入不必要依賴的情況下，正確地連結所需的緊前活動。

💡 虛擬活動記憶法： 虛擬活動就像數學上的必要設定，而非真實任務。它們讓我們遵守規則：一個活動 = 一條獨一無二的箭線。

第一部分重點總結： 一個繪製精良的網絡會正確地顯示所有任務（箭線）和依賴關係，並在必要時使用節點和零工期的虛線箭頭（虛擬活動）。

---

第二部分：關鍵路徑演算法

網絡繪製完成後，我們開始計算時間。我們會在每個節點填入兩個重要的時間點：最早開始時間 (Earliest Start Time, EST) 和最遲開始時間 (Latest Start Time, LST)。

我們在每個節點使用標準的方框記號，通常格式如下：
\[\n \begin{array}{|c|c|}\n \hline\n \text{EST} & \text{節點編號} \\\n \hline\n \text{LST} & \\\n \hline\n \end{array}\n \]

2.1 前向傳遞 (Forward Pass) —— 計算 EST

任意節點的最早開始時間 (EST) 是該事件可能實現的最早時刻。計算方法是從起點節點向終點節點前向掃描網絡。

前向傳遞步驟
  1. 起始節點： 第一個節點（節點 1）的 EST 始終為 0。
  2. 計算： 對於任何後續節點，找出其緊前節點的 EST，並加上相連活動（箭線）的工期。 $$ \text{EST}_{\text{下一節點}} = \text{EST}_{\text{當前節點}} + \text{工期} $$
  3. 最大值規則 (Maximum Rule)： 如果一個節點有多個輸入活動（箭線），你必須計算通往該節點的每一條路徑的到達時間。該節點的 EST 取這些到達時間中的最大值。這確保了在進入下一階段前，所有緊前活動都已完全完成。

💭 比喻： 想像同時進行幾場賽跑。整個項目必須等最慢的選手（最大時間）衝過終點線後，才能開始下一輪活動。

最終結果： 最終節點的 EST 即為整個項目的最短完成時間。

2.2 後向傳遞 (Backward Pass) —— 計算 LST

任意節點的最遲開始時間 (LST) 是在不延誤項目總最短完成時間的前提下，該事件可能發生的最遲時刻。計算方法是從終點節點向起點節點後向掃描網絡。

後向傳遞步驟
  1. 終止節點： 最終節點的 LST 設定為與其 EST 相等（即項目的最短完成時間）。
  2. 計算： 對於任何節點，找出後續節點的 LST，並減去相連活動（箭線）的工期。 $$ \text{LST}_{\text{當前節點}} = \text{LST}_{\text{下一節點}} - \text{工期} $$
  3. 最小值規則 (Minimum Rule)： 如果一個節點有多個輸出活動（箭線），你必須計算每一條輸出路徑所需的開始時間。該節點的 LST 取這些時間中的最小值。這確保了我們不會延誤任何後續任務。

⚠ 常見錯誤警示： 同學們常會混淆規則！

  • 前向傳遞 (EST)： 往回看，選最大值 (Maximum)。
  • 後向傳遞 (LST)： 往前看，選最小值 (Minimum)。

第二部分重點總結： 前向傳遞找到絕對最短時間 (EST)，後向傳遞找到在不超過該最短時間的前提下，最遲可能完成的時間線 (LST)。

---

第三部分：浮動時間與識別關鍵路徑

CPA 最重要的成果就是識別哪些任務是關鍵的（關鍵路徑），哪些具有一定的靈活性（浮動時間）。

3.1 計算總浮動時間 (Total Float)

總浮動時間 (Total Float)（通常簡稱為「浮動時間」）是指在不影響項目整體最短完成時間的情況下，一個活動可以被推遲的時間量。它代表了該特定任務的「閒置時間」。

計算活動 $X$ 的總浮動時間，假設其從節點 $i$（起點）運行到節點 $j$（終點），工期為 $D$：

$$ \text{Total Float} = \text{LST}_j - \text{EST}_i - D $$

其中：

  • \( \text{LST}_j \)：終點節點的最遲開始時間。
  • \( \text{EST}_i \)：起點節點的最早開始時間。
  • \( D \)：活動工期。

例子： 如果活動 A 的 EST 為 5，LST 為 15，工期為 8，則浮動時間為 \( 15 - 5 - 8 = 2 \)。這意味著活動 A 可以延誤 2 個時間單位而不會拖慢整個項目。

3.2 定義關鍵路徑

關鍵路徑 (Critical Path) 是指那些總浮動時間為零 (Float = 0) 的活動序列。

  • 這些活動是「瓶頸」。如果任何關鍵活動被延誤，整個項目將會被延誤相同的時間。
  • 在網絡圖中，關鍵路徑通常用雙線標記，或通過繪製連接關鍵節點的實線來表示。

如何識別關鍵節點： 若一個節點的 EST 等於其 LST，則該節點為關鍵節點。 $$ \text{EST} = \text{LST} $$ 關鍵路徑即是連接這些關鍵節點的路線。

🗄 檢查站： 將關鍵路徑想像成網絡中最長、最慢的路線。由於它是最長的，它決定了總時間。在非關鍵活動上省下的時間對項目進度沒有幫助，但若在關鍵活動上損失了時間，整個時間表就崩潰了！

3.3 最短完成時間

最短完成時間 (Minimum Completion Time) 就是最終節點的 EST。在所有任務都高效執行的假設下，這是完成該項目的最短可能時間。

🧩 速查箱：CPA 核心術語

EST： 任務最早可開始的時間（前向傳遞，選最大值）。
LST： 任務最遲必須開始的時間（後向傳遞，選最小值）。
Float： 閒置時間（終點 LST - 起點 EST - 工期）。
關鍵路徑： 浮動時間為零的活動（不可延誤）。

---

第四部分：進階概念與常見陷阱

4.1 資源分配與限制（簡述）

雖然基本的 CPA 確定了最短時間，但在現實生活中，我們常面臨資源限制（例如：只有兩名建築工人，或只有一台機器）。

如果兩個非關鍵活動被安排在同時進行，但兩者都需要同一個有限資源，其中一個就必須延遲。這種延遲會消耗其浮動時間。我們必須始終確保活動的總浮動時間永遠不會被超過，否則項目的最短時間將會增加。

4.2 考試時須避免的常見錯誤

  1. 忘記虛擬活動： 務必仔細檢查你的優先次序表。如果違反了唯一性或複雜依賴規則，你「必須」插入一個虛擬活動（工期 = 0）。
  2. 混淆最小值/最大值規則： 記住規則！EST = 輸入時間的最大值。LST = 輸出時間的最小值。
  3. 浮動時間計算錯誤： 確保正確使用了節點時間：終點節點的 LST 減去起點節點的 EST，再減去工期。
  4. 未標記關鍵路徑： 在考試中，如果題目要求識別關鍵路徑，除了標示最短時間外，必須在網絡圖上用雙線標記，或明確列出關鍵節點/活動。

🎉 你一定做得到！ CPA 是有規律可循的。一旦你掌握了前向和後向傳遞，剩下的就是熟能生巧。多練習繪製網絡，直到放置節點和虛擬活動變成你的直覺。

最終重點： CPA 將複雜的任務清單轉化為一個強有力的時間表，清晰地突顯出那些需要最嚴密監控的活動，以確保項目如期完成。