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

113 年・地方特考・三等・工業工程
試題代碼 作業研究

第 一 題25 分

以大 MM 法（Big-M Method）求解以下線性規劃問題。（25 分）

Maximize

Z=x1+2x2Z=x_1+2x_2

Subject to

x1+x2=7x_1+x_2=7 4x1+x2≥44x_1+x_2\geq 4 x1,x2≥0x_1,x_2\geq 0

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

這一題的完整詳解

核心觀念

本題考大 MM 法處理含等式與「大於等於」限制式的線性規劃問題：

  • 等式限制式沒有鬆弛變數可直接形成初始基底，須加入人工變數。
  • 「大於等於」限制式須減去剩餘變數，再加入人工變數以建立初始基底。
  • 最大化問題中，人工變數以大幅負係數 −M-M 加入目標函數；其中 MM 為足夠大的正數。若原問題有可行解，最適解中人工變數應為零。

解題方法

先將限制式改寫成等式，並加入人工變數：

x1+x2+a1=7x_1+x_2+a_1=7 4x1+x2−s2+a2=44x_1+x_2-s_2+a_2=4

其中 a1,a2≥0a_1,a_2\geq 0 為人工變數，s2≥0s_2\geq 0 為剩餘變數。大 MM 法的目標函數為

max⁡Z=x1+2x2−Ma1−Ma2.\max Z=x_1+2x_2-Ma_1-Ma_2.

初始基底取 a1,a2a_1,a_2。由於兩個人工變數在目標函數中的係數均為 −M-M，先將目標列消去基底變數，得到

Z=(1+5M)x1+(2+2M)x2−Ms2−11M.Z=(1+5M)x_1+(2+2M)x_2-Ms_2-11M.

接著進行單形法迭代。因 x2x_2 的目標列係數 2+2M2+2M 為正，令 x2x_2 進入基底。依最小比值法，第一列比值為 77，第二列比值為 44，故 a2a_2 離開基底。樞紐後第二列為

4x1+x2−s2+a2=4.4x_1+x_2-s_2+a_2=4.

再由第一列消去 x2x_2，可得

−3x1+s2+a1−a2=3.-3x_1+s_2+a_1-a_2=3.

此時 x1x_1 的目標列係數仍為正，令 x1x_1 進入基底。第二列的比值為 11，故 s2s_2 離開基底。樞紐後整理為

x1+14x2−14s2+14a2=1,x_1+\frac14x_2-\frac14s_2+\frac14a_2=1, −134x2+14s2+a1+34a2=0.-\frac{13}{4}x_2+\frac14s_2+a_1+\frac34a_2=0.

令非基底變數 x2=s2=0x_2=s_2=0，可得

x1=1,a1=a2=0.x_1=1,\qquad a_1=a_2=0.
🔒

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

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

免費註冊

第 二 題25 分

考慮下表中之運輸問題。

單位運輸成本如下表，列為來源，欄為目的地：

來源\目的地DEF供應量A$4$6$910B$6$7$65C$5$4$1010需求量12414\begin{array}{c|ccc|c} \text{來源}\backslash\text{目的地} & D & E & F & \text{供應量}\\ \hline A & \$4 & \$6 & \$9 & 10\\ B & \$6 & \$7 & \$6 & 5\\ C & \$5 & \$4 & \$10 & 10\\ \hline \text{需求量} & 12 & 4 & 14 & \end{array}

（一）應用西北角法（Northwest Corner Method）找出一個初始可行基解（Initial Basic Feasible Solution）。（10 分）

（二）由小題（一）所得之初始可行基解開始，應用運輸單形法（Transportation Simplex Method）求出最佳解。（15 分）

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

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

這一題的完整詳解

核心觀念

本題考查運輸問題的：

  1. 供需平衡與虛擬來源（Dummy Source）。
  2. 西北角法求初始可行基解。
  3. 運輸單形法（Transportation Simplex Method）改善基解。
  4. MODI 位勢法判斷最佳性。

運輸問題最小化時，對非基變數計算相對成本：

Δij=cij−ui−vj\Delta_{ij}=c_{ij}-u_i-v_j

其中 ui,vju_i,v_j 為位勢。若所有非基變數皆滿足：

Δij≥0\Delta_{ij}\geq 0

則目前解為最佳解；若有 Δij<0\Delta_{ij}<0，則選擇負值最大的非基變數進入基底。

（一）西北角法求初始可行基解

原表供應量為：

10+5+10=2510+5+10=25

需求量為：

12+4+14=3012+4+14=30

需求量大於供應量 55，因此需增加一個虛擬來源 XX，供應量為 55，各運輸成本設為 00。

西北角法分配

  1. A→DA\to D：
min⁡(10,12)=10\min(10,12)=10

A 用完，D 尚需 22。

  1. B→DB\to D：
min⁡(5,2)=2\min(5,2)=2

D 滿足，B 尚餘 33。

  1. B→EB\to E：
min⁡(3,4)=3\min(3,4)=3

B 用完，E 尚需 11。

  1. C→EC\to E：
min⁡(10,1)=1\min(10,1)=1

E 滿足，C 尚餘 99。

  1. C→FC\to F：
min⁡(9,14)=9\min(9,14)=9

C 用完，F 尚需 55。

  1. X→FX\to F：
min⁡(5,5)=5\min(5,5)=5

F 滿足。

初始可行基解如下：

來源\目的地DEF供應量A100010B2305C01910X0055需求量12414\begin{array}{c|ccc|c} \text{來源}\backslash\text{目的地} & D & E & F & \text{供應量}\\ \hline A & 10 & 0 & 0 & 10\\ B & 2 & 3 & 0 & 5\\ C & 0 & 1 & 9 & 10\\ X & 0 & 0 & 5 & 5\\ \hline \text{需求量} & 12 & 4 & 14 & \end{array}

初始運輸成本為：

Z0=10(4)+2(6)+3(7)+1(4)+9(10)+5(0)Z_0=10(4)+2(6)+3(7)+1(4)+9(10)+5(0) Z0=167Z_0=167

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

第一次改善

目前基底為：

AD, BD, BE, CE, CF, XFAD,\ BD,\ BE,\ CE,\ CF,\ XF

令 uA=0u_A=0，由基底成本關係 cij=ui+vjc_{ij}=u_i+v_j 得：

vD=4,uB=2,vE=5,uC=−1,vF=11,uX=−11.\begin{aligned} v_D&=4,\\ u_B&=2,\\ v_E&=5,\\ u_C&=-1,\\ v_F&=11,\\ u_X&=-11. \end{aligned}

計算非基變數的相對成本：

DEFA−1−2B−−−7C2−−X76−\begin{array}{c|ccc} & D & E & F\\ \hline A & - & 1 & -2\\ B & - & - & -7\\ C & 2 & - & -\\ X & 7 & 6 & - \end{array}

最負者為：

ΔBF=−7\Delta_{BF}=-7

故令 BFBF 進入基底。其閉迴路為：

BF(+)→BE(−)→CE(+)→CF(−)BF(+)\rightarrow BE(-)\rightarrow CE(+)\rightarrow CF(-)

可調整量為負號位置的最小配置量：

θ=min⁡(3,9)=3\theta=\min(3,9)=3

調整後：

xBF=0+3=3,xBE=3−3=0,xCE=1+3=4,xCF=9−3=6.\begin{aligned} x_{BF}&=0+3=3,\\ x_{BE}&=3-3=0,\\ x_{CE}&=1+3=4,\\ x_{CF}&=9-3=6. \end{aligned}

此時成本為：

Z1=167−7(3)=146Z_1=167-7(3)=146

第二次改善

新的基底為：

🔒

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

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

免費註冊

第 三 題25 分

以網路單形法（Network Simplex Method）求解下圖中之最小成本流量問題（Minimum Cost Flow Problem）。圖中淨流量顯示於節點旁，單位流量成本則顯示於節線旁。(A,D)(A,D) 與 (B,D)(B,D) 之流量上限分別為 2020 與 1515。（25 分）

🖼️【此處有附圖，請對照原卷】

圖中資料如下：

節點淨流量：

A:30,B:20,C:0,D:0,E:−50A:30,\quad B:20,\quad C:0,\quad D:0,\quad E:-50

有向節線及單位流量成本：

A→C:5A\to C:5 A→B:2A\to B:2 A→D:3A\to D:3 B→C:4B\to C:4 B→D:7B\to D:7 C→D:1C\to D:1 C→E:8C\to E:8 D→E:6D\to E:6

其中：

0≤xAD≤20,0≤xBD≤150\leq x_{AD}\leq 20,\qquad 0\leq x_{BD}\leq 15
🖼️ 本題原卷含圖表。基於試題來源之版權考量，本站不轉載原卷影像； 題目文字已完整轉錄，圖表請自行參閱考選部公告之試題原檔。

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

這一題的完整詳解

核心觀念

本題是最小成本流量問題：

  • 節點淨流量為正：供給節點。
  • 節點淨流量為負：需求節點。
  • 每條節線的成本為單位流量成本。
  • 所有流量須滿足節點流量平衡。
  • (A,D)(A,D)、(B,D)(B,D) 具有容量上限。

設各節線流量為 xijx_{ij}，目標函數為

min⁡Z=5xAC+2xAB+3xAD+4xBC+7xBD+xCD+8xCE+6xDE.\min Z= 5x_{AC}+2x_{AB}+3x_{AD}+4x_{BC} +7x_{BD}+x_{CD}+8x_{CE}+6x_{DE}.

流量平衡式為

xAC+xAB+xAD=30,x_{AC}+x_{AB}+x_{AD}=30, xBC+xBD−xAB=20,x_{BC}+x_{BD}-x_{AB}=20, xCD+xCE−xAC−xBC=0,x_{CD}+x_{CE}-x_{AC}-x_{BC}=0, xDE−xAD−xBD−xCD=0,x_{DE}-x_{AD}-x_{BD}-x_{CD}=0, xCE+xDE=50.x_{CE}+x_{DE}=50.

且

0≤xAD≤20,0≤xBD≤15,0\leq x_{AD}\leq20,\qquad 0\leq x_{BD}\leq15,

其餘流量皆須滿足非負限制。

解題方法：網路單形法

選取下列四條節線作為基底樹：

(A,C), (B,C), (C,D), (D,E).(A,C),\ (B,C),\ (C,D),\ (D,E).

令非基底節線 (A,B)(A,B)、(B,D)(B,D)、(C,E)(C,E) 的流量為 00，並令 (A,D)(A,D) 達到其上限：

xAD=20.x_{AD}=20.

由節點 AA 的流量平衡：

xAC+20=30⇒xAC=10.x_{AC}+20=30 \quad\Rightarrow\quad x_{AC}=10.

由節點 BB 的流量平衡：

xBC=20.x_{BC}=20.

由節點 CC 的流量平衡：

xCD=xAC+xBC=10+20=30.x_{CD}=x_{AC}+x_{BC}=10+20=30.

由節點 DD 的流量平衡：

xDE=xAD+xCD=20+30=50.x_{DE}=x_{AD}+x_{CD}=20+30=50.

因此得到流量解：

xAC=10,xAB=0,xAD=20,\boxed{ x_{AC}=10,\quad x_{AB}=0,\quad x_{AD}=20, } xBC=20,xBD=0,xCD=30,\boxed{ x_{BC}=20,\quad x_{BD}=0,\quad x_{CD}=30, } xCE=0,xDE=50.\boxed{ x_{CE}=0,\quad x_{DE}=50. }

網路單形法最適性檢定

令節點勢能為 πi\pi_i，簡化成本定義為

cˉij=cij−πi+πj.\bar c_{ij}=c_{ij}-\pi_i+\pi_j.

對基底樹上的節線，令簡化成本為 00。取

πE=0.\pi_E=0.

由 (D,E)(D,E)：

🔒

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

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

免費註冊

第 四 題25 分

考慮以下之天氣模型。某城市明天的天氣，取決於今天與昨天的天氣。

如果今天與昨天都是下雨，則明天下雨的機率是 0.70.7。

如果今天下雨而昨天沒下雨，則明天下雨的機率是 0.60.6。

如果今天沒下雨而昨天下雨，則明天下雨的機率是 0.40.4。

如果今天與昨天都沒下雨，則明天下雨的機率是 0.30.3。

長期下來，該城市是雨天的時間比例為何？（25 分）

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

這一題的完整詳解

核心觀念

題目描述的是二階馬可夫鏈：明天的天氣不只取決於今天，也取決於昨天。將狀態改寫為「最近兩天的天氣組合」，就能轉成一階馬可夫鏈，再求其穩態分布。

令 RR 表示下雨、NN 表示沒下雨；以「昨天、今天」的順序表示狀態，狀態空間為 RR、RN、NR、NNRR、RN、NR、NN。長期穩態分布中各狀態的機率，便代表長期下雨與不下雨的時間比例。

解題方法

依題目給定的明天下雨機率，轉移如下：

  • RRRR：明天下雨機率 0.70.7，故轉至 RRRR 的機率為 0.70.7，轉至 RNRN 的機率為 0.30.3。
  • RNRN：明天下雨機率 0.60.6，故轉至 NRNR 的機率為 0.60.6，轉至 NNNN 的機率為 0.40.4。
  • NRNR：明天下雨機率 0.40.4，故轉至 RRRR 的機率為 0.40.4，轉至 RNRN 的機率為 0.60.6。
  • NNNN：明天下雨機率 0.30.3，故轉至 NRNR 的機率為 0.30.3，轉至 NNNN 的機率為 0.70.7。

因此，依狀態順序 RR、RN、NR、NNRR、RN、NR、NN，轉移矩陣為

P=(0.70.300000.60.40.40.600000.30.7).P= \begin{pmatrix} 0.7&0.3&0&0\\ 0&0&0.6&0.4\\ 0.4&0.6&0&0\\ 0&0&0.3&0.7 \end{pmatrix}.

設穩態分布為 π=(a,b,c,d)\boldsymbol{\pi}=(a,b,c,d)，滿足 πP=π\boldsymbol{\pi}P=\boldsymbol{\pi}，且 a+b+c+d=1a+b+c+d=1。由各狀態的平衡方程：

🔒

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

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

免費註冊

其他考古題

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

111110