108 地方特考三等 工業工程 作業研究 考古題詳解

核心觀念

本題考曼哈頓距離的線性化。兩點 $(x_1,y_1)$、$(x_2,y_2)$ 間的曼哈頓距離為

絕對值不是線性式，因此以非負輔助變數表示各座標差的絕對值，再用線性限制式確保其不小於該差值及其相反數。

解題方法

設第四個分行的座標為 $(x,y)$，並令 $u_i$、$v_i$ 分別表示新分行與第 $i$ 個既有分行在 $x$、$y$ 座標上的絕對差。如此一來，三段曼哈頓距離之和可寫成 $\sum_{i=1}^3(u_i+v_i)$。

三個既有分行座標依序為 $(4,3)$、$(0,-3)$、$(-2,1)$，因此線性規劃模式如下：

核心觀念

本題考「人員排班的線性規劃模型建構」。關鍵是將每種班別設為決策變數，按各班別涵蓋的時段列出人力需求限制，再以時薪乘上工時建立總成本目標式。

全職班每班 8 小時；兼職班每班 4 小時。由於全職職員的時薪較高，目標是選擇符合各時段需求及全職、兼職比例限制的班表，使總薪資最低。

解題方法

令：

• $x_1,x_2,x_3$：分別為三種全職班的人數，依序為上午 6 點至下午 2 點、上午 10 點至下午 6 點、下午 2 點至晚上 10 點。
• $y_1,y_2,y_3,y_4$：分別為四個 4 小時時段的兼職人數，依序為上午 6 點至上午 10 點、上午 10 點至下午 2 點、下午 2 點至下午 6 點、下午 6 點至晚上 10 點。

全職職員每人每日成本為 $200\times 8=1{,}600$ 元；兼職職員每人每日成本為 $150\times 4=600$ 元。因此總成本最小化目標式為：

依各時段的班別涵蓋情形，列出需求限制：

• 上午 6 點至上午 10 點：只有全職班 $x_1$ 與兼職班 $y_1$ 覆蓋，需求至少 8 人。
• 上午 10 點至下午 2 點：全職班 $x_1,x_2$ 與兼職班 $y_2$ 覆蓋，需求至少 16 人。
• 下午 2 點至下午 6 點：全職班 $x_2,x_3$ 與兼職班 $y_3$ 覆蓋，需求至少 20 人。
• 下午 6 點至晚上 10 點：只有全職班 $x_3$ 與兼職班 $y_4$ 覆蓋，需求至少 12 人。

故人力需求限制為：

核心觀念

本題考查資源配置的動態規劃。四位銷售員是有限資源，三個學區是必須服務的對象；各學區的銷售量取決於分配到該區的銷售員人數。目標是在每區至少分配一人、總人數恰為四人的條件下，使總銷售量最大。

令 $f_i(n)$ 表示分配 $n$ 位銷售員至學區 $i$ 時的預估銷售量。令 $F_k(n)$ 表示將 $n$ 位銷售員分配到前 $k$ 個學區時可達成的最大總銷售量。

解題方法

採用逐區遞推。每個學區至少分配一人，因此前 $k$ 區至少需要 $k$ 人；每次遞推時，枚舉分配給目前學區的人數，並將剩餘人數配置到前面的學區。

初始條件為：

遞推式為：

其中 $x$ 是分配給第 $k$ 個學區的人數，限制 $x\ge 1$；剩餘 $n-x$ 人必須足以讓前 $k-1$ 區各至少有一人。

第一階段：只配置學區一

第二階段：配置學區一、二

以下列出各總人數下，分配給學區二的人數與最大銷售量：

核心觀念

本題考馬可夫鏈（Markov chain）的 $n$ 步轉移機率。林先生每週選擇的清運點，只與本週所在的清運點有關；從一週到下一週的轉移機率由題目表格給定。

令狀態依序為清運點一、二、三，轉移機率矩陣為

矩陣中第 $i$ 列、第 $j$ 欄的數值，代表目前在清運點 $i$，下一週轉移到清運點 $j$ 的機率。$P^n$ 的第 $i$ 列、第 $j$ 欄則表示從狀態 $i$ 出發，經過 $n$ 週到達狀態 $j$ 的機率。

解題方法

本週一晚上在清運點二，未來第四個週一晚上是經過四次每週轉移，因此所求為四步轉移機率 $(P^4)_{22}$。

先計算兩步轉移矩陣：