地特四等申論題
108年
[林業技術] 森林經營學概要
第 三 題
三、某林業公司有五組調查人員，一組只能安排於一個林班工作，各項林班工作的表現分數如下表，今欲安排他們各執行一個林班工作，試問如何安排可求得總分數最大？（25 分）
| 組別 ＼ 林班工作 | A | B | C | D | E |
|---|---|---|---|---|---|
| 第 1 組 | 15 | 55 | 10 | 55 | 25 |
| 第 2 組 | 20 | 60 | 15 | 55 | 30 |
| 第 3 組 | 55 | 45 | 60 | 45 | 60 |
| 第 4 組 | 30 | 20 | 40 | 50 | 55 |
| 第 5 組 | 75 | 40 | 65 | 35 | 20 |
| 組別 ＼ 林班工作 | A | B | C | D | E |
|---|---|---|---|---|---|
| 第 1 組 | 15 | 55 | 10 | 55 | 25 |
| 第 2 組 | 20 | 60 | 15 | 55 | 30 |
| 第 3 組 | 55 | 45 | 60 | 45 | 60 |
| 第 4 組 | 30 | 20 | 40 | 50 | 55 |
| 第 5 組 | 75 | 40 | 65 | 35 | 20 |
📝 此題為申論題
思路引導 VIP
這是一道標準的「指派問題 (Assignment Problem)」，要求找出總分數最大的工作分配。解題關鍵在於使用「匈牙利法 (Hungarian Method)」，由於原演算法用於求解最小化問題，必須先找出矩陣中的最大值，將全矩陣減去該值轉換為「機會損失矩陣」，接著再進行列與行的簡化，最後劃線找零完成指派。
🤖
AI 詳解
AI 專屬家教
【解題關鍵】使用匈牙利法（Hungarian Method）解指派問題，求最大化需先將原矩陣轉換為機會損失矩陣。 【解答】 已知原林班工作表現分數（利潤矩陣）如下：
▼ 還有更多解析內容
匈牙利法指派問題
💡 利用匈牙利法進行最佳化資源配置，以達成最大化效益或最小成本。
🔗 匈牙利法求解最大化問題流程
- 1 轉化目標 — 最大值扣除全體元素，將最大化轉為最小化問題
- 2 行列化簡 — 依序進行列減去最小值、行減去最小值，產生零元素
- 3 畫線測試 — 用最少水平或垂直線覆蓋所有 0，判斷線數是否達標
- 4 矩陣指派 — 從單一零值的行列開始鎖定，完成一對一的最優配置
- 5 總值計算 — 將指派位置對應回原始利潤矩陣，加總得出最大分數
↓
↓
↓
↓
🔄 延伸學習：延伸學習：若矩陣非方陣（如5人派4工），須先增加虛擬行列補足為方陣後再計算。
