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

109 年・專技高考・高等考試・工業工程技師
試題代碼 作業研究

第 1 題25 分

Maximize

Z=12x1+5x2+3x3Z=12x_1+5x_2+3x_3

subject to

2x1+3x2+4x3≤18,2x_1+3x_2+4x_3\leq 18, 4x1+x2+2x3≤10,4x_1+x_2+2x_3\leq 10, x1≥0,x2≥0,x3≥0.x_1\geq 0,\quad x_2\geq 0,\quad x_3\geq 0.

（一）以簡捷法（Simplex Method）的表格法（tableau）求解上列線性規劃模型。（11 分）

（二）列出兩項資源的影子價格（shadow prices）。（3 分）

（三）列出最佳的基底矩陣（basis matrix）。（3 分）

（四）列出基底變數與非基底變數。（3 分）

（五）列出上列線性規劃模型的對偶模型。（5 分）

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題考查單純形表格法、影子價格、基底矩陣與線性規劃對偶。

將每個「≤\leq」限制式加入非負鬆弛變數 s1,s2s_1,s_2，可寫成等式：

2x1+3x2+4x3+s1=18,4x1+x2+2x3+s2=10.\begin{aligned} 2x_1+3x_2+4x_3+s_1&=18,\\ 4x_1+x_2+2x_3+s_2&=10. \end{aligned}

單純形法以目標列的檢定數判斷是否有可改善的非基底變數。本解採用 Cj−ZjC_j-Z_j 慣例：最大化問題若所有非基底變數的 Cj−Zj≤0C_j-Z_j\leq 0，即達最適。

解題方法：單純形表格法

初始表

初始基底為鬆弛變數 s1,s2s_1,s_2，右端值除以正的主欄係數，選出離基變數。

基底CBC_Bx1x_1x2x_2x3x_3s1s_1s2s_2RHS比值（x1x_1欄）
s1s_1023410189
s2s_2041201102.5
Cj−ZjC_j-Z_j125300

x1x_1 的檢定數最大，故 x1x_1 入基。最小比值為 10/4=2.510/4=2.5，故 s2s_2 離基；主元為 44。

第一次樞紐後

將第二列除以 44，再消去其他列的 x1x_1 係數：

基底CBC_Bx1x_1x2x_2x3x_3s1s_1s2s_2RHS比值（x2x_2欄）
s1s_1005/25/231−1/2-1/21326/526/5
x1x_11211/41/41/21/201/41/45/25/210
Cj−ZjC_j-Z_j02−3-30−3-3

x2x_2 的檢定數為 2>02>0，故 x2x_2 入基。其比值為 13/(5/2)=26/513/(5/2)=26/5 與 (5/2)/(1/4)=10(5/2)/(1/4)=10，所以 s1s_1 離基，主元為 5/25/2。

第二次樞紐後：最適表

基底CBC_Bx1x_1x2x_2x3x_3s1s_1s2s_2RHS
x2x_25016/56/52/52/5−1/5-1/526/526/5
x1x_112101/51/5−1/10-1/103/103/106/56/5
Cj−ZjC_j-Z_j00−46/9-46/9−17/18-17/18−13/6-13/6

所有非基底變數 x3,s1,s2x_3,s_1,s_2 的 Cj−ZjC_j-Z_j 均不大於 00，因此已達最適。令非基底變數為 00，得：

x1=65,x2=265,x3=0.x_1=\frac65,\qquad x_2=\frac{26}{5},\qquad x_3=0.

目標值為：

Z=12(65)+5(265)+3(0)=2025=40.4.Z=12\left(\frac65\right)+5\left(\frac{26}{5}\right)+3(0) =\frac{202}{5}=40.4.

影子價格

最適基底變數為 x1,x2x_1,x_2，其成本係數為 CB=(12,5)C_B=(12,5)。影子價格向量為：

🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 2 題15 分

依題一（四）回答下列問題：

（一）以圖解法分析其解答。（10 分）

（二）列出束縛限制式（binding constraint）與非束縛限制式。（2 分）

（三）將此非束縛限制式的右手邊值（right-hand-side value）漸增，使其也變成束縛限制式。此時的右手邊值是多少？（3 分）

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題要用圖解法分析題一（四）的線性規劃模型，並辨認最適解所在的束縛限制式。束縛限制式是在最適解處恰好等號成立的限制式；非束縛限制式則保有鬆弛量。接著調高非束縛限制式的右手邊值，找出它首次成為束縛限制式時的臨界值。

題目資訊不足

🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 3 題20 分

網路圖中有六個節點（node）AA、BB、CC、DD、EE、FF。每一對節點之間的連接弧線（link）上的數字表示兩節點間的距離，或是單位運輸成本。

原卷網路圖包含下列節點與弧線標示：

  • 節點：AA、BB、CC、DD、EE、FF
  • 弧線標示數值：44、55、66、66、88、99、1010、1111、1616、1616

（一）求出最小生成樹（Minimum spanning tree）。（10 分）

（二）說明一種最小生成樹的應用。須定義各節點及連接弧線。（10 分）

🖼️ 本題原卷含圖表。基於試題來源之版權考量，本站不轉載原卷影像； 題目文字已完整轉錄，圖表請自行參閱考選部公告之試題原檔。

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

最小生成樹（Minimum Spanning Tree, MST）是在一個連通網路中，選出連接所有節點、沒有迴路，且總弧線權重最小的樹。六個節點的生成樹必須恰有 6−1=56-1=5 條弧線。

本題可用 Kruskal 法：依權重由小到大選取弧線；若加入某條弧線會形成迴路，就略過。

解題方法

依圖中弧線權重由小到大排列：

權重弧線
4A−CA-C
5A−BA-B
6B−DB-D
6B−EB-E
8B−CB-C
9D−ED-E
10C−DC-D
11C−EC-E
16D−FD-F
16E−FE-F

依序選取：

  1. 選 A−CA-C，權重為 44。
  2. 選 A−BA-B，權重為 55。
  3. 選 B−DB-D，權重為 66。
  4. 選 B−EB-E，權重為 66。此時 A,B,C,D,EA,B,C,D,E 已連通。
  5. B−CB-C 會形成迴路 B−A−C−BB-A-C-B，略過；D−ED-E、C−DC-D、C−EC-E 也都會在已連通的節點間形成迴路，略過。
  6. FF 尚未連接，選 D−FD-F 或 E−FE-F，兩者權重皆為 1616。
🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 4 題20 分

下列的線性規劃模型有四條限制式及決策變數非零的條件：

Maximize

Z=15x1+20x2−7x3Z=15x_1+20x_2-7x_3

subject to

3x1+2x2−3x3≤24,3x_1+2x_2-3x_3\leq 24, 3x1+3x2+x3≤36,3x_1+3x_2+x_3\leq 36, 6x1+x2−5x3≤20,6x_1+x_2-5x_3\leq 20, 9x1+4x2−5x3≤20,9x_1+4x_2-5x_3\leq 20, x1≥0,x2≥0,x3≥0.x_1\geq 0,\quad x_2\geq 0,\quad x_3\geq 0.

另外有個條件：四條限制式只能選用其中兩條。寫出整數規劃模型，不需求解。（20 分）

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

這題考的是用二元變數與 Big-M 法，將「四條限制式中恰好選用兩條」轉寫為整數規劃模型。原本的三個決策變數 x1,x2,x3x_1,x_2,x_3 為非負連續變數；另設二元變數表示各限制式是否啟用。

解題方法

令 yiy_i 表示第 ii 條限制式是否選用：

yi={1,第 i 條限制式啟用,0,第 i 條限制式不啟用,i=1,2,3,4.y_i= \begin{cases} 1, & \text{第 }i\text{ 條限制式啟用},\\ 0, & \text{第 }i\text{ 條限制式不啟用}, \end{cases} \qquad i=1,2,3,4.

為了讓未選用的限制式不再限制 x1,x2,x3x_1,x_2,x_3，對每條限制式加入 Big-M 項。當 yi=1y_i=1 時，Big-M 項為零，原限制式生效；當 yi=0y_i=0 時，Big-M 項放寬限制式。

因此，整數規劃模型為：

🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 5 題20 分

阿明一個人在街上經營理髮店，容許兩位顧客排隊等候。顧客以卜瓦松過程（Poisson process）來店，平均的間隔為 15 分鐘。理髮所需的時間呈現指數分配（exponential distribution），平均為 10 分鐘。以等候模型、增減過程（birth-and-death process）來分析阿明店裡顧客的數量。

（一）顧客的數量在店中增減的情形以速率圖（rate diagram）表示之。（5 分）

（二）店裡顧客的數量以 nn 表示之，列出每個平衡方程式（balance equations）。（5 分）

（三）以 PnP_n 表示店裡顧客的數量為 nn 的平均機率，求各 PnP_n 的值。（5 分）

（四）計算店裡平均的顧客人數。（5 分）

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題是有限容量的 M/M/1/KM/M/1/K 等候模型，以 birth-and-death process（增減過程）分析店內顧客數。

  • 顧客到達服從卜瓦松過程，平均每 15 分鐘 1 位，因此到達率為 λ=115 人／分鐘.\lambda=\frac{1}{15}\text{ 人／分鐘}.
  • 理髮時間服從指數分配，平均每 10 分鐘服務 1 位，因此服務率為 μ=110 人／分鐘.\mu=\frac{1}{10}\text{ 人／分鐘}.
  • 店內最多容納 3 位顧客：1 位理髮中、2 位等候。因此狀態為 n=0,1,2,3n=0,1,2,3。當店內已有 3 位顧客時，新到顧客無法進入，故到達率在狀態 3 為 0。
  • 設 PnP_n 為穩態下店內有 nn 位顧客的機率。

（一）速率圖

令狀態 nn 表示店內顧客人數。到達使狀態增加 1，服務完成使狀態減少 1：

0⇌μλ1⇌μλ2⇌μλ30 \xrightleftharpoons[\mu]{\lambda} 1 \xrightleftharpoons[\mu]{\lambda} 2 \xrightleftharpoons[\mu]{\lambda} 3

其中各狀態的轉移率為：

  • 0→10\to1、1→21\to2、2→32\to3 的到達率均為 λ=115\lambda=\frac{1}{15}。
  • 1→01\to0、2→12\to1、3→23\to2 的服務率均為 μ=110\mu=\frac{1}{10}。
  • 狀態 3 已達容量上限，沒有 3→43\to4 的到達轉移。

（二）平衡方程式

逐一列出各狀態的流入率等於流出率：

  • 狀態 0： μP1=λP0\mu P_1=\lambda P_0
  • 狀態 1： λP0+μP2=(λ+μ)P1\lambda P_0+\mu P_2=(\lambda+\mu)P_1
  • 狀態 2： λP1+μP3=(λ+μ)P2\lambda P_1+\mu P_3=(\lambda+\mu)P_2
  • 狀態 3： λP2=μP3\lambda P_2=\mu P_3

並加上機率總和為 1 的正規化條件： P0+P1+P2+P3=1.P_0+P_1+P_2+P_3=1.

（三）各狀態機率

此 birth-and-death process 的相鄰狀態穩態關係為 λPn=μPn+1,n=0,1,2.\lambda P_n=\mu P_{n+1},\qquad n=0,1,2.

🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

其他考古題

工業工程技師《作業研究》其他年度

114113112111110