高考申論題
107年
[工業工程] 作業研究
第 一 題
📖 題組：
考慮以下之最大流量問題，其中源點（source）為節點 A，匯流（sink）為節點 F，各項有向弧旁之數字為該弧之容量（capacity）。 （圖中包含節點 A, B, C, D, E, F 與對應弧容量：A->B: 9, A->C: 7, B->D: 7, B->E: 3, C->D: 6, C->E: 8, D->F: 2, E->F: 5） (一)將此問題轉換成最小成本流量問題。（10 分） (二)以網路單形法（network simplex method）求解小題(一)所得之最小成本流量問題。（10 分）
考慮以下之最大流量問題，其中源點（source）為節點 A，匯流（sink）為節點 F，各項有向弧旁之數字為該弧之容量（capacity）。 （圖中包含節點 A, B, C, D, E, F 與對應弧容量：A->B: 9, A->C: 7, B->D: 7, B->E: 3, C->D: 6, C->E: 8, D->F: 2, E->F: 5） (一)將此問題轉換成最小成本流量問題。（10 分） (二)以網路單形法（network simplex method）求解小題(一)所得之最小成本流量問題。（10 分）
📝 此題為申論題，共 2 小題
小題 (一)
將此問題轉換成最小成本流量問題。
思路引導 VIP
看到最大流量轉最小成本流量問題，應直覺想到建立「循環網路（Circulation Network）」。核心技巧是從匯流點（Sink）到源點（Source）建構一條「虛擬返回弧」，將所有節點的外部供需量設為 0，並將該返回弧成本設為負值，藉由最小化成本來達到最大化流量的目的。
小題 (二)
以網路單形法（network simplex method）求解小題(一)所得之最小成本流量問題。
思路引導 VIP
本題測驗將最大流問題等價轉換為最小成本流量問題（MCFP）的技巧，關鍵在於加入一條從匯點至源點的虛擬弧以最大化流量。在網路單形法求解過程中，需精確掌握節點對偶變數（Node potentials）與縮減成本（Reduced costs）的計算，依序疊代至所有非基底弧符合最佳性條件為止。