民國115年 高考三級 工業工程 作業研究
第4題
某消防局將配置8 輛消防車到4 個地區，每個地區必須配置1 至4 輛消 防車，且每輛消防車只能配置到一個地區。配置不同數量的消防車到各 地區時，預估可增加的成功…
題目
某消防局將配置8 輛消防車到4 個地區，每個地區必須配置1 至4 輛消 防車，且每輛消防車只能配置到一個地區。配置不同數量的消防車到各 地區時，預估可增加的成功救災件數如下表： 消防車數量 地區 16 14 18 30 27 32 41 37 43 49 46 51 建構一個整數規劃模型，以決定8 輛消防車於4 個地區之配置方式，使 成功救災總件數的增加量最大。（20 分）
參考解答（AI 生成，非官方）
- 一、決策變數與參數。令 x_ij 為 0-1 變數，x_ij = 1 表示配置 i 輛消防車至第 j 個地區（i = 1, 2, 3, 4；j = 1, 2, 3, 4），否則為 0；令 r_ij 為對應之預估增加救災件數，依題表前三地區依序為 16、30、41、49；14、27、37、46；18、32、43、51。此為典型之資源分配（resource allocation）問題，以整數規劃（integer programming）建模最為直接。
- 二、目標函數。Max Z = 雙重加總（j = 1 至 4，i = 1 至 4）r_ij × x_ij，即四個地區因配置消防車而增加之成功救災件數總和為最大。由於每地區僅能選定一種配置量，目標式實為各地區被選方案效益之和。
- 三、限制式。(1) 每地區恰選一種配置量：對所有 j，i = 1 至 4 加總 x_ij = 1；(2) 消防車總數為 8：對所有 j、i 加總 i × x_ij = 8；(3) 每地區配置 1 至 4 輛，已由 i 之取值範圍及第 (1) 式隱含；(4) 0-1 整數限制：x_ij ∈ {0, 1}。三類限制式共同構成完整之整數規劃模型。
- 四、求解方法。可以動態規劃求解：令 f_k(n) 為將 n 輛車分配予前 k 個地區之最大增加件數，遞迴式 f_k(n) = max over i = 1…4 of { r_ik + f_(k−1)(n − i) }，邊界 f_0(0) = 0，f_k(n) = −∞（當 n < k 或 n > 4k），答案為 f_4(8)；亦可採分支界限法（branch and bound）或整數規劃套裝軟體求解。就前三地區觀察，配置 1 至 4 輛之邊際效益分別為 18、14、11、8，呈遞減，符合邊際報酬遞減法則。
- 五、資料缺漏之說明。題面表格僅呈現三個地區之數據，第四地區之效益欄位在排版中脫漏，致總量限制 i × x_ij 加總等於 8 下之最適配置無法唯一決定，故本題資料缺漏，無法得出唯一數值。考生作答時應完整寫出變數定義、目標式與三類限制式，並註明「若補足第四地區數據，可列舉滿足每區 1 至 4 輛且總和為 8 之 31 組可行組合，或依動態規劃逆推求解」，以確保模式建構部分之配分。
AI 依官方試題文字產生的參考解答，非考選部公告答案，內容僅供備考參考。