地特三等申論題
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
將最大流量問題轉換為最小成本流量問題的標準作法，是引入一條從匯流點（Sink, F）回到源點（Source, A）的「虛擬回流弧」。透過設定該虛擬弧的單位成本為 -1（原網路弧成本皆為 0），並將所有節點的供需量設為 0，便可藉由最小化總成本來達成最大化流量的目的。
小題 (二)
以網路單形法（network simplex method）求解小題(一)所得之最小成本流量問題。
思路引導 VIP
看到此題，首先回想「最大流量轉最小成本流量」的技巧：加入一條從匯流點 (F) 回到源點 (A) 的虛擬弧，容量無限、成本為負值（如 -1），其餘原網路弧成本皆設為 0。接著應用網路單形法（Network Simplex Method），選定一組初始基底（生成樹），透過計算節點位勢與縮減成本，反覆尋找可改善目標函數的非基底弧加入基底，並沿循環推進流量，直到所有非基底弧均符合最佳性條件為止。