地特三等申論題
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
本題為非平衡指派問題（機器 3 台，位置 4 個）。因此第一步必須「引入虛擬機器」（M4），其到各位置的頻率均為 0，使矩陣轉為 $4 \times 4$ 方陣。此外，M2 無法擺在 L3，屬於禁忌指派（Prohibited Assignment），須在此格設一個極大值 $M$。之後便能套用匈牙利法的標準步驟（列減、行減、畫線覆蓋、調整矩陣）求出最適解。
小題 (二)
㈡若表一內的數值代表機器被分配在各候選位置的利潤，請以匈牙利法進行這三台機器的安裝位置指派，以使總利潤為最大。（5 分）
思路引導 VIP
本題將問題從「極小化（頻率）」轉變為「極大化（利潤）」。使用匈牙利法處理極大化問題時，第一步必須將其轉換為極小化問題，一般做法是利用一個足夠大（或矩陣中最大）的數值減去矩陣中的所有數值（禁忌指派 $-M$ 除外）。另外，虛擬機器（M4）的實際利潤均為 0，所以其對應列轉換前的利潤值為 0，這在極小化矩陣中需要格外注意。