地特三等申論題
113年
[工業工程] 作業研究
第 三 題
三、以網路單形法（Network Simplex Method）求解下圖中之最小成本流量問題（Minimum Cost Flow Problem）。圖中淨流量顯示於節點旁，單位流量成本則顯示於節線旁。（A, D）與（B, D）之流量上限分別為 20 與 15。（25 分）
[圖形說明：節點 A[30], B[20], C[0], D[0], E[-50]。弧與成本：(A,C)=5, (A,B)=2, (A,D)=3, (B,D)=7, (B,C)=4, (C,D)=1, (C,E)=8, (D,E)=6。]
📝 此題為申論題
思路引導 VIP
看到這題首先應建構一組初始生成樹（基本可行解），接著利用網路單形法計算「節點位勢」與「縮減成本」來尋找入基變數。特別注意本題帶有「流量上限（Upper Bound）」，當流量達到上限時會發生退化現象（Bound Swap，換基但樹結構不變），直到所有處於下限/上限的非基本弧均符合最佳性條件即可求得最小成本。
🤖
AI 詳解
AI 專屬家教
【解題關鍵】有容量上限的網路單形法需尋找初始生成樹，透過「節點位勢」與「縮減成本」檢驗最佳性，並留意入基流量受上限限制所引發的「狀態切換（Bound Swap）」。 【解答】 計算：Step 1→2→3 逐步推導
▼ 還有更多解析內容