114 專技高考高等考試 工業工程技師 作業研究 考古題詳解

核心觀念

本題考查線性規劃的圖解法、資源限制式的虛擬價格、對偶問題，以及互補剩餘定理。

圖解法先找出各限制式所界定的可行區域，再比較可行區域頂點的目標值。對偶問題中，每個原問題的「$\leq$」限制式對應一個非負對偶變數；原問題每個變數則對應一個對偶限制式。互補剩餘定理用來連結原問題與對偶問題的最佳解。

(一) 圖解法求最佳解

將三條資源限制式改寫成 $x_2$ 的上界：

另有 $x_1\geq 0,\ x_2\geq 0$，可行區域位於第一象限，並在三條限制線下方。比較可行區域的頂點：

• 原點 $(0,0)$。
• $x_1=0$ 時，最緊的上界是 $x_2\leq 10/3$，得到頂點 $(0,10/3)$。
• $x_2=0$ 時，最緊的上界是 $x_1\leq 2$，得到頂點 $(2,0)$。
• 資源 1 與資源 2 的交點：解

得 $(x_1,x_2)=(3/2,3/2)$。代入資源 3 左側得 $2(3/2)+3(3/2)=15/2\leq10$，故此交點可行。

資源 1 與資源 3 的交點不符合資源 2 限制；資源 2 與資源 3 的交點也不符合資源 1 限制，因此不屬於可行區域頂點。

逐一計算可行頂點的目標值：

因此最佳解為

在此解中，資源 1、資源 2 的限制式為緊束；資源 3 尚有 $10-\frac{15}{2}=\frac52$ 的剩餘量。

(二) 資源 3 的虛擬價格

虛擬價格是資源限制右側值增加一單位時，最佳目標值的邊際變化量；在穩定範圍內，等於該限制式對應的最佳對偶變數。

資源 3 在最佳解有正剩餘量 $\frac52$，因此依互補剩餘定理，其對應的對偶變數為 $0$。故資源 3 的虛擬價格為

在目前最佳基底維持不變的範圍內，資源 3 的可用量小幅增加不會提高最佳目標值。

(三) 寫出對偶問題

原問題是最大化問題，限制式為「$\leq$」，且 $x_1,x_2\geq0$。令 $y_1,y_2,y_3$ 分別對應資源 1、資源 2、資源 3，則 $y_1,y_2,y_3\geq0$。

對偶目標是最小化資源右側值的加權和：

核心觀念

本題考驗運輸問題的起始可行解、基本解判定，以及以運輸單形法改善解的能力。

總供給量與總需求量皆為 $48$，因此是平衡運輸問題。若有 $m$ 個起點、$n$ 個終點，運輸問題的基本可行解應有 $m+n-1$ 個基本變數；本題 $m=3,n=5$，故需 $3+5-1=7$ 個基本變數。

Vogel’s 近似法（VAM）每次計算各列、行中最低與次低成本之差作為罰數，選取罰數最大者，並在該列或行的最低成本格分配可運量。

（一）Vogel’s 近似法起始解

起始各列罰數：

• A：$9-4=5$
• B：$7-6=1$
• C：$2-2=0$

起始各行罰數：

• D：$8-2=6$
• E：$12-6=6$
• F：$5-4=1$
• G：$9-2=7$
• H：$7-5=2$

最大罰數為 G 行的 $7$。G 行最低成本為 $2$，位於 C–G，分配 $\min(30,10)=10$ 單位。此時 C 尚餘 $20$，G 的需求已滿。

刪除 G 行後，重新計算罰數。A 列罰數為 $9-4=5$、B 列為 $7-6=1$、C 列為 $5-2=3$；D 行罰數為 $8-2=6$、E 行為 $12-6=6$、F 行為 $5-4=1$、H 行為 $7-5=2$。最大罰數為 D 行的 $6$ 與 E 行的 $6$。依最低成本比較，D 行最低成本格 C–D 成本 $2$，E 行最低成本格 B–E 成本 $6$；選 D 行分配至 C–D： $\min(20,5)=5$ 單位。此時 C 尚餘 $15$，D 的需求已滿。

剩餘 A、B、C 與 E、F、H。A 列罰數為 $15-4=11$、B 列為 $7-6=1$、C 列為 $12-5=7$；E 行罰數為 $12-6=6$、F 行為 $8-4=4$、H 行為 $7-5=2$。最大罰數為 A 列的 $11$。A 列最低成本格 A–F，分配 $\min(8,9)=8$ 單位。A 供給用完，F 尚需 $1$。

剩餘 B、C 與 E、F、H。B 列罰數為 $7-6=1$、C 列為 $12-5=7$；E 行罰數為 $12-6=6$、F 行為 $8-5=3$、H 行為 $7-5=2$。最大罰數為 C 列的 $7$，其最低成本格 C–H 成本 $5$，分配 $\min(15,20)=15$ 單位。C 供給用完，H 尚需 $5$。

剩下 B 列供應 $10$，E、F、H 的需求分別為 $6,1,5$，故分配： $B\text{–}E=6,\ B\text{–}F=1,\ B\text{–}H=3$。

起始分配如下：

總運輸成本為

（二）是否為基本解

此起始解有 $7$ 個正運量變數： $AF,BE,BF,BH,CD,CG,CH$。

基本可行解所需的基本變數數目為

因此，這個起始解是基本可行解。也可將正運量格視為二分網路中的邊；這 $7$ 條邊連結全部 $8$ 個列、行節點，且無閉迴路，符合基本解條件。

（三）運輸單形法求最佳解

核心觀念

本題考驗單一服務台、顧客依 Poisson 過程到達、服務時間服從指數分布的 $M/M/1$ 排隊系統。

令：

• 到達率 $\lambda=18$ 位／小時。
• 現有服務率 $\mu=1/(3/60)=20$ 位／小時。
• 系統利用率 $\rho=\lambda/\mu$。

系統穩定的條件為 $\lambda<\mu$。$M/M/1$ 系統中，平均排隊人數為

若每位顧客等待成本為每分鐘 2 元，則每小時等待成本為 $2\times60=120$ 元／顧客小時，因此每小時總成本為

解題方法

(一) 系統利用率 $\rho$

平均服務時間為 3 分鐘，即每小時可服務

因此

現有服務人員的利用率為 $90\%$，且 $\rho<1$，所以系統穩定。

(二) 新到達顧客需要等待的機率

顧客抵達時若服務人員忙碌，就必須等待。依 Poisson 到達的 PASTA 性質，到達顧客看到系統忙碌的機率等於服務人員忙碌的比例，也就是 $\rho$。

新到達顧客需要等待的機率為 $90\%$。

(三) 每小時總期望成本

先計算平均排隊人數：

每位顧客每分鐘等待成本為 2 元，換算為每小時 120 元，因此每小時等待成本為

加上服務人員薪資：

核心觀念

本題考兩個專案管理觀念：先用要徑法（CPM）計算正常工期，再用線性規劃決定趕工幅度。網路分支在 E、F 匯合時，該作業須等所有前置作業完成，因此其最早開始時間取前置分支完成時間的最大值。

趕工成本與縮短天數呈線性關係，每縮短一天的成本斜率為：

以下依原卷掃描圖讀取趕工資料：A 的最短時間與最高成本為 2 天、1,400 美元；B 為 1 天、1,900 美元；C 為 3 天、2,800 美元；D 為 3 天、2,300 美元；E 為 4 天、2,800 美元；F 為 1 天、1,000 美元；G 為 1 天、1,000 美元。

解題方法

網路關係為 Start 分別進入 A、B；A 接 C，B 接 D；C、D 各自通往 E、F；E 接 Finish，F 經 G 接 Finish。

（一）要徑與正常完工時間

按正常作業時間計算最早開始、最早完成時間：

Finish 須等 E 與 G 均完成，因此專案正常完工時間為 $\max(14,12)=14$ 天。

各完整路徑長度為：

• A–C–E：$3+5+6=14$ 天
• B–D–E：$2+5+6=13$ 天
• A–C–F–G：$3+5+2+2=12$ 天
• B–D–F–G：$2+5+2+2=11$ 天

最長路徑為 A–C–E，故其為要徑，正常工期為 14 天。

（二）正常時間的總專案成本

將各作業正常成本相加：

（三）12 天內完成的線性規劃模式

令 $x_i$ 為作業 $i$ 的趕工天數。依原卷數據，各作業的趕工上限及每趕工一天的成本如下：

核心觀念

本題考驗設施選址的混合整數線性規劃建模，將「是否設倉」的固定成本與「出貨量」的變動成本納入同一目標式，並以二元變數表示開設決策。

題目未提供各地點的單位出貨成本，因此以 $c_A,c_B,c_C$ 分別代表 A、B、C 倉庫每單位出貨成本。

解題方法

令 $x_i$ 為地點 $i$ 的出貨量，$y_i$ 為是否在地點 $i$ 設立倉庫的二元變數：

總成本由固定設置成本與出貨成本組成，因此目標式為：

以需求量作為總出貨量下限；各倉庫未開設時出貨量為零，開設時不得超過容量：

題目表示必須滿足總需求量；若模型設定為不得超額供貨，也可將需求限制寫成 $x_A+x_B+x_C=150$。

條件轉換

• A 開設則 B 也須開設：以 $y_A\le y_B$ 表示。
• B 與 C 不可同時開設：以 $y_B+y_C\le 1$ 表示。
• C 開設時出貨量至少 40 單位：以 $x_C\ge 40y_C$ 表示。若 $y_C=0$，此限制不會要求正出貨量；