高考申論題
112年
[工業工程] 作業研究
第 一 題
📖 題組：
二、某公司已預購3台機器（分別為u、v及w），公司已規劃出4個可以放置這些機器的候選位置（A、B、C及D）。機器v因體積太大無法放置於位置C。另因機器擺在不同的位置，未來會產生的物料搬運頻率也不同，表一為各機器擺在不同的位置預期產生的搬運頻率。 (一)請建構可使總搬運頻率最小化的機器－位置擺設規劃的線性規劃模式。（8分） (二)以匈牙利法求解可使總搬運頻率最小化的機器－位置擺設規劃，並計算其總搬運頻率。（7分） 表一、指派問題相關資料 A B C D u 70 80 140 120 v 90 60 - 140 w 60 110 100 150
二、某公司已預購3台機器（分別為u、v及w），公司已規劃出4個可以放置這些機器的候選位置（A、B、C及D）。機器v因體積太大無法放置於位置C。另因機器擺在不同的位置，未來會產生的物料搬運頻率也不同，表一為各機器擺在不同的位置預期產生的搬運頻率。 (一)請建構可使總搬運頻率最小化的機器－位置擺設規劃的線性規劃模式。（8分） (二)以匈牙利法求解可使總搬運頻率最小化的機器－位置擺設規劃，並計算其總搬運頻率。（7分） 表一、指派問題相關資料 A B C D u 70 80 140 120 v 90 60 - 140 w 60 110 100 150
📝 此題為申論題，共 2 小題
小題 (一)
請建構可使總搬運頻率最小化的機器－位置擺設規劃的線性規劃模式。（8分）
思路引導 VIP
這是一道經典的「不平衡指派問題（Assignment Problem）」。看到此題應先確立決策變數為二元變數，接著分別寫出目標函數（最小化搬運頻率）、機器端限制（每台機器恰指派一位置）、位置端限制（每個位置至多放一台機器），並針對「機器v無法放位置C」加入極大值M或直接設定該變數為0。
小題 (二)
以匈牙利法求解可使總搬運頻率最小化的機器－位置擺設規劃，並計算其總搬運頻率。（7分）
思路引導 VIP
這是一道標準的不平衡指派問題，考點在於『虛擬機器』的加入與『極大值M』的處理。考生應先將3x4矩陣補齊為4x4矩陣，並將不可能的指派（機器v至位置C）設為極大成本M，再嚴格執行匈牙利法的列減法、行減法與畫線調整步驟，直至找出4個獨立的最佳指派零點。