高考申論題
114年
[工業工程] 作業研究
第 一 題
📖 題組：
某公司新購 M1, M2, M3 三台機器，候選的機器安裝位置有 L1, L2, L3, L4，其中 M2 機器因某些因素無法擺放在 L3 的位置。表一為三台機器分別擺在四個候選位置的物料搬運頻率。 表一（候選位置 L1, L2, L3, L4）： M1: 21, 23, 20, 22 M2: 30, 25, -, 23 M3: 26, 24, 27, 20 （註：- 表示無法擺放）
某公司新購 M1, M2, M3 三台機器，候選的機器安裝位置有 L1, L2, L3, L4，其中 M2 機器因某些因素無法擺放在 L3 的位置。表一為三台機器分別擺在四個候選位置的物料搬運頻率。 表一（候選位置 L1, L2, L3, L4）： M1: 21, 23, 20, 22 M2: 30, 25, -, 23 M3: 26, 24, 27, 20 （註：- 表示無法擺放）
📝 此題為申論題，共 2 小題
小題 (一)
請以匈牙利法（Hungarian method）進行這三台機器的安裝位置指派，以使總物料搬運頻率為最小。（10 分）
思路引導 VIP
看到此題，應立即辨識為「不平衡指派問題」及「禁制指派（限制條件）」。先補上虛擬機器（Dummy Machine）使矩陣平衡為 4×4，並將無法安裝的位置成本設為極大值 M。接著嚴格執行匈牙利法（列減、行減、畫線檢驗、矩陣調整）直到最少直線數等於矩陣階數為止。
小題 (二)
若表一內的數值代表機器被分配在各候選位置的利潤，請以匈牙利法進行這三台機器的安裝位置指派，以使總利潤為最大。（5 分）
思路引導 VIP
此題為極大化指派問題，核心考點在於「矩陣轉換」與「不平衡處理」。看到題目應直覺聯想：1. 加入虛擬機器（M4）使供需平衡（形成方陣）；2. 找出矩陣最大值，將「利潤矩陣」轉換為求極小值的「機會損失矩陣」；3. 將禁止指派的儲存格設為極大值（M）。完成前置轉換後，即可標準化執行匈牙利法。
匈牙利法指派問題
💡 利用矩陣運算尋找一對一任務分配的最優解，含極大化與極小化處理。
🔗 匈牙利法運算流程
- 1 前處理 — 補虛擬列/行成方陣，並處理禁止指派位置。
- 2 目標轉換 — 若求極大化，須以最大值減去各項轉為極小化。
- 3 列行歸零 — 各列/行減去該列/行最小值，產生零元素。
- 4 最少線覆蓋 — 用最少直線覆蓋所有 0，若線數等於階數即得解。
- 5 矩陣調整 — 若線數不足，找出未覆蓋區最小值進行加減調整。
↓
↓
↓
↓
🔄 延伸學習：延伸學習：當存在多個獨立零元素組合時，代表該問題具備多組最佳解。
