民國115年 高考三級 工業工程 作業研究考古題

民國115年 高考三級 工業工程 作業研究收錄考選部官方試題，共 4 題可線上瀏覽，考選部未公告本科目答案。

官方資料

題目與答案

第1題

以大M 法（Big M Method）求解以下線性規劃問題。（30 分） Maximize 2 +2 +3 Subject to , , Z x x x x x x x x x x x x x x x

參考解答（AI 生成，非官方）

  • 一、題意與模式標準化。本題為求極大化之線性規劃，目標函數係數為 2、2、3，即 Max Z = 2x1 + 2x2 + 3x3；限制式之係數與右端值在題面排版中脫漏，無法完整辨識。就方法論而言，大 M 法（Big M Method）適用於含「大於等於」或「等於」限制式之問題：先將不等式化為等式，小於等於者加入寬鬆變數（slack variable），大於等於者減去剩餘變數（surplus variable），再對缺乏單位向量之限制式加入人工變數（artificial variable），並在目標函數中給予極大懲罰係數 M（求極大時為 −M）。
  • 二、初始單純形表之建構。改寫後之目標函數可表示為 Max Z = 2x1 + 2x2 + 3x3 − M a1 − M a2，移項後以 Z − 2x1 − 2x2 − 3x3 + M a1 + M a2 = 0 表示。據此建立初始單純形表（simplex tableau）：各列對應一條限制式，各行對應各變數（含寬鬆、剩餘、人工變數）及右端常數欄；初期基變數（basic variable）由寬鬆變數與人工變數組成，其在表中之係數行恰構成單位矩陣。表格下方另列 Z_j 列與 C_j − Z_j（即 reduced cost，簡化成本）列，作為迭代判別依據。
  • 三、迭代規則與比值檢定。求極大化問題時，選 C_j − Z_j 最大正值（或 Z_j − C_j 最負）之非基變數為進入變數（entering variable）；再以各列右端值除以該行正係數，取最小比值者所在列之基變數為離去變數（leaving variable），比值相同可任取，或依 Bland 法則以避免循環（cycling）；樞紐元素（pivot element）所在列先除以樞紐值使其為 1，再以列運算使該行其餘元素歸零，完成一次迭代。
  • 四、最優性判定與可行性檢核。當所有 C_j − Z_j ≤ 0 時達最優；若此時人工變數仍為正值基變數，表示原問題無可行解（infeasible）；若某非基變數之 C_j − Z_j > 0 而其係數行全為非正，則問題為無界（unbounded）。因 M 為充分大之正數，最優解中人工變數必被逐出基底而為零，否則該解不具可行性。最後應將最優表之 x1、x2、x3 值代回原目標函數求 Z，並逐條驗證是否滿足原始限制式。
  • 五、資料缺漏之處理與作答建議。由於題面限制式之係數與右端常數未能完整辨識，僅憑 Max Z = 2x1 + 2x2 + 3x3 無法建立唯一之初始表，亦無法算出唯一最優解與 Z 值，故本題資料缺漏，無法得出唯一數值。考生宜先依題意逐條抄錄限制式，明確標示所加之寬鬆、剩餘與人工變數，再逐表列出並註記樞紐行、樞紐列與比值，最後以「所有 C_j − Z_j ≤ 0 且人工變數均為零」作結，以取得方法分數。

第2題

某太空中心計畫將一顆探測器送入預定軌道，只有3 個火箭發射窗口可 供使用，而每個發射窗口至多可以發射5 枚火箭。每枚火箭成功將探測 器送入預定軌道的機率為3/4，失敗機率為1/4。若某一發射窗口被啟用， 則需支付固定的發射準備費用200 萬元。此外，每發射一枚火箭需額外 支付100 萬元的發射成本。只要有任意一枚火箭成功將探測器送入預定 軌道，任務即宣告成功，後續發射窗口將不再使用。若三個發射窗口全 部結束後，仍未能成功將探測器送入預定軌道，則此次太空任務失敗， 並造成800 萬元的任務損失。請利用動態規劃決定在各發射窗口中應發 射多少枚火箭？使太空中心的總期望成本最小。（25 分）

參考解答（AI 生成，非官方）

  • 一、問題結構與決策變數。三個發射窗口依序使用，屬多階段序貫決策（sequential decision）問題，宜以倒推式動態規劃（backward dynamic programming）求解。令 n_i 為第 i 個窗口發射之火箭數（i = 1, 2, 3，n_i ∈ {0, 1, …, 5}）；因啟用窗口須付 200 萬元固定準備費，n_i = 0 即等同不啟用。單枚失敗機率 q = 1/4，n 枚全數失敗機率為 (1/4)^n，任務成功機率為 1 − (1/4)^n。成本單位均為萬元。
  • 二、遞迴關係。令 V(m) 表示「尚餘 m 個窗口可用且任務尚未成功」時，自該階段起算之最小期望總成本，則邊界條件 V(0) = 800（三窗口全數失敗之任務損失）。對 m ≥ 1：V(m) = min over n = 1…5 of { 200 + 100n + (1/4)^n × V(m−1) }，另可比較「不啟用本窗口」之選項 0 + V(m−1)。由於 200 + 100n 恆為正且 V(m−1) 有限，啟用並發射至少一枚必優於放棄，故最適解中每個被使用之窗口至少發射一枚。
  • 三、逆推計算。V(1) = min{300 + 0.25×800 = 500，400 + 0.0625×800 = 450，500 + 0.015625×800 = 512.5，603.125，700.78} = 450（n = 2）。V(2) = min{300 + 0.25×450 = 412.5，400 + 0.0625×450 = 428.125，507.03，601.76，700.44} = 412.5（n = 1）。V(3) = min{300 + 0.25×412.5 = 403.125，400 + 0.0625×412.5 = 425.78，506.45，601.61，700.40} = 403.125（n = 1）。
  • 四、最適策略與期望成本。最適策略為：第一窗口發射 1 枚；若失敗（機率 1/4），第二窗口發射 1 枚；若再失敗（機率 1/4），第三窗口發射 2 枚；若三窗口共 4 枚全數失敗（機率 (1/4)^4 = 1/256），任務失敗並損失 800 萬元。總期望成本 = 300 + 0.25 × [300 + 0.25 × (400 + 0.0625 × 800)] = 300 + 0.25 × 412.5 = 403.125 萬元。
  • 五、結果驗算與詮釋。以策略分解驗算：固定準備費與發射成本之期望值為 300 + 0.25×300 + 0.0625×400 = 400 萬元，失敗損失期望值為 (1/256)×800 = 3.125 萬元，合計 403.125 萬元，與遞迴結果一致。由於單枚發射成本（100 萬元）相對失敗損失（800 萬元）偏低，前期宜「少量試射、保留窗口」，末段因無退路而加重發射量，呈現剩餘階段愈少、最適發射量愈多之動態規劃典型特徵。

第3題

某校園有兩個共享單車停放點：東門與西門。一位學生每天早上從校園 離開。他從東門出發的機率為2/3，從西門出發的機率為1/3。若出發的 停放點有共享單車，他就騎一輛單車；若該停放點沒有共享單車，他只 能步行。當他返回校園時，他從東門進入的機率為1/3，從西門進入的機 率為2/3，並將共享單車停放在進入的停放點。假設校園共有兩輛共享單 車，長期而言，該學生必須步行的比例是多少？（25 分）

參考解答（AI 生成，非官方）

  • 一、狀態定義與轉移機制。以每天早上出發前「東門停放點之單車數」為狀態，記為 i ∈ {0, 1, 2}，西門則有 2 − i 輛。學生自東門出發機率 2/3、自西門出發 1/3；返回時自東門進入機率 1/3、自西門進入機率 2/3，並將所騎單車停放於進入之停放點。若出發點無車則步行，且無車可停放，狀態維持不變。此為有限狀態、齊次之馬可夫鏈（Markov chain），其轉移機率不隨時間改變。
  • 二、轉移機率之推導。狀態 0：自東門出發（2/3）必步行，留於 0；自西門出發（1/3）可取車，返回停東門（1/3）至狀態 1、停西門（2/3）回狀態 0。故 P00 = 2/3 + 2/9 = 8/9，P01 = 1/9。狀態 1：自東門取車後停東門（2/9）留 1、停西門（4/9）至 0；自西門取車後停東門（1/9）至 2、停西門（2/9）留 1。故 P10 = 4/9，P11 = 4/9，P12 = 1/9。狀態 2：自東門取車停東門（2/9）留 2、停西門（4/9）至 1；自西門無車步行（1/3）留 2。故 P21 = 4/9，P22 = 5/9。
  • 三、平穩分布之求解。令 π = (π0, π1, π2) 滿足 π = πP 且 π0 + π1 + π2 = 1。由 π0 = (8/9)π0 + (4/9)π1 得 π0 = 4π1；由 π2 = (1/9)π1 + (5/9)π2 得 π2 = π1/4；配合正規化 4π1 + π1 + π1/4 = 1，解得 π1 = 4/21，故 π0 = 16/21、π2 = 1/21。代回第二式檢驗：(16 + 16 + 4)/189 = 36/189 = 4/21，與 π1 相符，驗算無誤。
  • 四、步行比例之計算。步行僅發生於「自東門出發且東門無車」或「自西門出發且西門無車」兩種情形，故長期步行比例為 (2/3)π0 + (1/3)π2 = (2/3)(16/21) + (1/3)(1/21) = 32/63 + 1/63 = 33/63 = 11/21，約為 0.5238，即約 52.38% 的早晨必須步行。
  • 五、結果詮釋與政策意涵。因返回時停於西門之機率（2/3）高於東門（1/3），單車長期滯留西門，使東門無車（狀態 0）之機率偏高達 16/21，故步行比例超過五成。若欲降低步行率，可於夜間將單車由西門調度回東門，或於東門增設停車樁、提供歸還誘因，此即共享運具系統之再平衡（rebalancing）策略。

第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 組可行組合，或依動態規劃逆推求解」，以確保模式建構部分之配分。