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

核心觀念

本題考查混合整數線性規劃（Mixed Integer Linear Programming, MILP）的建模，重點是把生產決策、員工聘用決策、資源限制及邏輯條件寫成線性限制式。

生產件數及員工人數均為非負整數。服裝的單件淨利等於單件毛利減去人工成本；員工總工時則受聘用人數限制。

解題方法

令：

• $x_M,x_F,x_C$：每週生產的男裝、女裝、童裝件數。
• $n_F,n_P$：全職、兼職員工人數。

上述變數皆為非負整數。

全職員工每人每週可提供 $40\times 60=2{,}400$ 分鐘工時；兼職員工每人每週可提供 $15\times 60=900$ 分鐘工時。服裝生產所需總工時不得超過員工可提供的總工時，因此有：

每名全職員工每週人工成本為 $40\times 200=8{,}000$ 元；每名兼職員工每週人工成本為 $15\times 150=2{,}250$ 元。各類服裝的毛利扣除按生產時間計算的人工成本後，單件淨利如下：

• 男裝：$800- \frac{40}{60}\times 200=\frac{2000}{3}$ 元。
• 女裝：$1000-\frac{50}{60}\times 200=\frac{2500}{3}$ 元。
• 童裝：$900-\frac{60}{60}\times 200=700$ 元。

因此，每週總淨利可寫成服裝總毛利減員工總人工成本：

布料每週最多可取得 $10{,}000$ 平方公尺，故材料限制為：

全職員工至少僱用 100 人：

每僱用一名兼職員工，至少須僱用三名全職員工，故：

核心觀念

本題考查運輸問題的線性規劃建模，以及 Vogel 近似法（VAM）求起始可行解。令 $x_{ij}$ 表示能源供給選項 $i$ 供應需求部門 $j$ 的能源量，目標是使供應成本總和最小。

運輸表須符合供需平衡。太陽光電與再生能源的供應量上限分別為 20,000、10,000；燃氣、燃油沒有實際供應上限。為將問題整理成平衡運輸表，將燃氣與燃油各自設為 170,000 單位的可用量，並增設「虛擬需求」欄，表示未使用的供應量。170,000 足以涵蓋扣除太陽光電與再生能源後的剩餘需求，且虛擬需求的運輸成本設為 0。

解題方法

（一）起始運輸單純表

總需求為 $40,000+60,000+100,000=200,000$。供給端加上虛擬需求後，總供給為 $20,000+10,000+170,000+170,000=370,000$；虛擬需求為 $370,000-200,000=170,000$。

表中的數量單位均為「千單位」，成本單位為元／單位；「—」表示該供應路線不允許。

虛擬需求欄的分配量代表相應能源沒有投入實際供應。因燃氣與燃油無實際供應上限，表中各給 170,000 的容量只是平衡表所需的有限容量設定；虛擬需求用來記錄未用容量。

（二）Vogel 近似法起始解

VAM 每一輪計算各列、各欄最低成本與次低成本之差，選取差額最大的列或欄，再在其中成本最低的格子配置可行的最大數量。受限制路線不列入比較。

以下數量均以千單位表示。

1. 第一輪：再生能源列的成本為 $800,700,0$，罰數為 $700-0=700$，為最大。將再生能源配置到虛擬需求：$\min(10,170)=10$。再生能源用量全數留作未使用供應。

2. 第二輪：虛擬需求剩 160；燃油列可用成本為 $600,650,700,0$，罰數為 $600$，為最大。將燃油配置到虛擬需求：$\min(170,160)=160$。燃油剩 10，虛擬需求滿足。

核心觀念

本題是資源分配型動態規劃：將 5 名警察分配給 3 個分局，每個分局的月犯罪案件數取決於分配人數，目標是在警察總數恰為 5 人的條件下，使總案件數最少。各分局的案件數可以相加，因此適合用動態規劃逐一加入分局，記錄目前可用警察人數下的最小累計案件數。

令 $c_i(x)$ 表示分局 $i$ 分配 $x$ 人時的預期月犯罪案件數。題目給定：

解題方法：最佳值函數與遞迴式

令 $F_i(n)$ 為將 $n$ 名警察分配給前 $i$ 個分局後，所能達到的最少月犯罪案件數。其中 $i=1,2,3$，$n=0,1,\ldots,5$。

考慮最後加入的第 $i$ 個分局。若分配 $x$ 人給該分局，則前 $i-1$ 個分局分配 $n-x$ 人，其最小案件數為 $F_{i-1}(n-x)$。因此：

初始條件為：

等價地，也可設定 $F_0(0)=0$，且 $F_0(n)=+\infty$（$n>0$），再使用同一遞迴式逐一計算各分局。

答案為：

若題意要求將 5 人全數分配，則限制為 $x_1+x_2+x_3=5$，此時答案是 $F_3(5)$。本題各分局增加警察都會降低案件數，所以最優解會用滿 5 人，故以 $F_3(5)$ 求解。

逐階段計算

第一階段只有分局 1，依初始條件：

第二階段加入分局 2。以 $n=0,1,2$ 為例：

其餘各值同理，計算結果如下：

核心觀念

本題考的是指派問題：將 4 個工作分派給 5 位應徵者中的 4 人，使總成本最低。每人至多負責一項工作，每項工作恰由一人負責；因 $B$ 無法執行 $J_3$，該組合列為禁配。

每小時工資固定為 160 元，因此最小化總工資等同於最小化總工時：

解題方法

匈牙利法通常處理方陣指派問題。本題有 4 項工作、5 位人員，可將「不指派」視為一個虛擬工作 $J_5$，並令每人承接 $J_5$ 的成本為 0。如此得到 $5\times5$ 方陣；指派給 $J_5$ 的人即為未獲聘用者。

對於 $B$ 執行 $J_3$ 的禁配，設為足夠大的數 $M$，使該組合不會出現在最適指派中。成本矩陣如下：

匈牙利法列、行減法

先逐列減去該列最小值，再逐行減去該行最小值。得到約化矩陣：

核心觀念

本題是不確定情況下的決策分析。題目未提供各種疫情警戒情況的機率時，依指定準則評估四種方案；提供機率後，則以期望值準則比較。

各準則的定義如下：

• 大中取大（maximax）：先找出每個方案的最高淨利，再選最高者，代表採取最樂觀的評估。
• Laplace 準則：假設五種情況等機率，計算各方案的平均淨利，選平均值最高者。
• 大中取小遺憾（minimax regret）：先以每種情況下可得的最高淨利作為基準，計算各方案的遺憾值；再選「最大遺憾」最小的方案。
• 赫威茲（Hurwicz）準則：以樂觀指數 $\alpha$ 加權方案的最高淨利，並以 $1-\alpha$ 加權最低淨利，再選加權值最高者。
• 貨幣期望值（expected value）：依各情況的機率加權平均淨利，選期望淨利最高者。
• 完全資訊的期望價值（EVPI）：在完全知道將發生哪種情況時可取得的期望淨利，減去未有完全資訊時的最佳期望淨利。

（一）未提供機率時的決策準則

1. 大中取大（maximax）

各方案的最高淨利為：

因此選擇最高值 $880$，最佳方案為 $D$。

2. Laplace 準則

將五種警戒情況視為等機率，各方案淨利總和除以 $5$：

$B$ 的平均淨利最高，為 $524$ 萬元，故最佳方案為 $B$。

3. 大中取小遺憾（minimax regret）

每種情況下的最高淨利分別為：

遺憾值等於「該情況最高淨利減去該方案淨利」。各方案遺憾表如下：

各方案的最大遺憾中，$D$ 的 $100$ 萬元最低，故最佳方案為 $D$。

4. 赫威茲（Hurwicz）準則，$\alpha=0.6$

依公式

核心觀念

本題分別考查最短路徑與最小生成樹，兩者的目標不同：

• 最短路徑：找出住宅區 1 到住宅區 10 的路徑，使沿途距離總和最小。各邊距離非負，可用 Dijkstra 演算法。
• 最小生成樹：讓 10 個住宅區彼此連通，並使所有鋪設線路的總長度最小。生成樹須連通全部節點且沒有迴圈，因此包含 $10-1=9$ 條邊；可用 Kruskal 演算法。

解題方法

（一）住宅區 1 到住宅區 10 的最短路徑

以 $d(i)$ 表示目前已知從住宅區 1 到住宅區 $i$ 的最短距離。Dijkstra 演算法每次固定尚未處理節點中距離最小者，再用它更新相鄰節點的距離。

依序固定的節點為 $1,2,4,3,5,6,7,8,9,10$。更新後的最短距離如下：

例如，住宅區 6 的最短距離為

住宅區 10 可由住宅區 8 或 9 到達，經住宅區 9 的距離較短：