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

核心觀念

本題考線性規劃的產品組合問題，並用單純法求最適解。每種產品的單位利潤作為目標函數係數；各部門每週可用工時則形成產能限制。第三小題考的是影子價格：在最適基底不變的範圍內，某部門增加一小時產能，最適利潤增加多少。

（一）建立線性規劃模式

令 $x_1$、$x_2$ 分別為每週生產的 $P1$、$P2$ 數量。

每單位 $P1$、$P2$ 的利潤分別為 60 元、50 元，因此目標為最大化每週總利潤：

依各部門的工時需求與每週產能，限制式為：

（二）單純法求最佳解

將三個產能限制分別加入鬆弛變數 $s_1,s_2,s_3$，轉為等式：

初始基底為 $s_1,s_2,s_3$。依單純法進行換基，最適基底為 $x_1,x_2,s_1$；其解可由 $K2$、$K3$ 兩個限制同時緊束求得：

由第二式得 $x_2=100-x_1$，代入第一式：

此時 $K1$ 使用工時為：

所以 $s_1=500-420=80$；而 $K2$、$K3$ 皆恰好用滿。目標值為：

為確認該解為最大值，可由最適基底求得對偶價格。令 $y_1,y_2,y_3$ 分別代表 $K1,K2,K3$ 的影子價格。由於 $s_1>0$，互補條件給出 $y_1=0$；

核心觀念

本題考的是指派問題與匈牙利法。每台機器指派至一個位置，每個位置至多安裝一台機器；未被選用的位置可留空。三台機器要指派到四個位置，因此加入一列「虛擬機器」，代表未使用的位置，其成本或利潤設為 $0$，將問題轉成 $4\times4$ 方陣。

匈牙利法適用於方形指派矩陣。最小化問題以列、欄減去各自最小值進行歸零化，再以零元素找出互不共用列、欄的指派；最大化問題則先轉成最小化問題。

題目中 $M2$ 不可放在 $L3$，以禁止指派值處理。此處在最小化題可設為足夠大的 $K$；在最大化題轉換為成本後，同樣設為 $K$。

解題方法

（一）最小化物料搬運頻率

原始矩陣加入虛擬機器 $M4$，並以 $K$ 表示禁止的 $M2\to L3$：

先做列減法，各列最小值依序為 $20,23,20,0$，得到：

再做欄減法。四欄最小值皆為 $0$，矩陣不變。選取互不共用列與欄的零元素，可得一組完整指派：

• $M1\to L3$，原頻率 $20$
• $M2\to L2$，原頻率 $25$
• $M3\to L4$，原頻率 $20$
• $M4\to L1$，代表 $L1$ 留空

總物料搬運頻率為：

（二）最大化利潤

核心觀念

本題是最小生成樹問題。生成樹須連通所有結點，且不形成迴路；若有 $n$ 個結點，生成樹恰有 $n-1$ 條邊。本圖有 8 個結點，因此需選出 7 條邊，使總距離最短。

解題方法

採用 Kruskal 法：依邊長由小到大檢視，每次選取不會形成迴路的最短邊，直到所有結點連通。

核心觀念

本題屬於「不確定情況下的決策」，各種景氣狀態的發生機率未知，因此依題目指定的決策準則比較方案。

令樂觀指數為 $\alpha$，則 Hurwicz 準則對每個方案計算：

其中 $0\leq \alpha\leq 1$；$\alpha$ 越大，越重視最高收益。各準則皆選擇計算值最高的方案。

解題方法與計算

（一）Laplace 準則

景氣狀態的機率未知時，Laplace 準則假設三種狀態等可能，計算各方案的平均收益：

• $A$：$\dfrac{120+70-40}{3}=50$
• $B$：$\dfrac{80+90+5}{3}=\dfrac{175}{3}\approx58.33$
• $C$：$\dfrac{90+100-10}{3}=60$
• $D$：$\dfrac{60+55+50}{3}=55$

最高平均收益為 $60$ 億元，故選 $C$。

（二）小中取大（maximin）準則

先找各方案在最不利景氣下的最低收益，再選擇最低收益最高的方案：

最高的最低收益為 $50$ 億元，故選 $D$。

（三）Hurwicz 準則，$\alpha=0.4$

各方案的最高與最低收益如下，代入 $H_i(0.4)=0.4(\text{最高收益})+0.6(\text{最低收益})$：

• $A$：最高 $120$、最低 $-40$，$H_A=0.4(120)+0.6(-40)=24$
• $B$：最高 $90$、最低 $5$，$H_B=0.4(90)+0.6(5)=39$
• $C$：最高 $100$、最低 $-10$，$H_C=0.4(100)+0.6(-10)=34$
• $D$：最高 $60$、最低 $50$，$H_D=0.4(60)+0.6(50)=54$

最高 Hurwicz 值為 $54$ 億元，故選 $D$。

（四）各方案適用的樂觀指數範圍

核心觀念

本題考馬可夫鏈（Markov chain）的穩定狀態，以及如何用穩定狀態計算長期市場占有率與年銷售額。令 $X_n$ 表示消費者第 $n$ 次購買的品牌；題目給定的下一次購買機率只與本次品牌有關，因此符合一階馬可夫鏈。

若穩定狀態機率向量為 $\boldsymbol{\pi}=(\pi_A,\pi_B,\pi_C)$，則須滿足：

其中 $P$ 為移轉機率矩陣。

（一）一階移轉機率矩陣

列代表本次購買品牌，欄代表下一次購買品牌，故：

每一列總和皆為 $1$，符合移轉機率矩陣的性質。

（二）穩定狀態機率

依 $\boldsymbol{\pi}P=\boldsymbol{\pi}$，可得：

整理前兩式：

由第一式得 $\pi_C=4\pi_A-3\pi_B$。代入第二式：