112 年 國立中央大學工業管理研究所碩士班《作業研究》

📄 試題原卷　免費註冊後即可對照原始考卷 PDF免費註冊

第 1 題

Consider a queueing model for which there is unlimited service, i.e., an infinite number of servers available. A self-service type situation is one example of such a model. Interarrival time is exponentially distributed with rate λ\lambda and service time is exponentially distributed with rate μ\mu. Let the state be the number of customers in the system. One could use the general birth and death processes to analyze this model. Let the state be the number of customers in the system.

(a) (5 points) Draw a rate transition diagram for this model and determine λn\lambda_n and μn\mu_n for state nn.
(b) (10 points) Let pnp_n be the steady-state probability of nn customers in the system. Show that pn=λnn!μnp0p_n = \frac{\lambda^n}{n!\mu^n} p_0, n=1,2,...n = 1,2,...
(c) (10 points) Show that pn=(λ/μ)ne−λ/μn!p_n = \frac{(\lambda/\mu)^n e^{-\lambda/\mu}}{n!}, n=0,1,…n = 0, 1, \dots

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

這一題的完整詳解

此題為一個具備無限多服務器的排隊模型（M/M/∞ 模型）的穩態分析。題目要求繪製其狀態轉移圖，並推導穩態機率公式。

核心觀念：一般化出生-死亡過程 (General Birth and Death Process)、穩態機率。

(a) 狀態轉移圖與 λn,μn\lambda_n, \mu_n 的決定

此模型為一出生-死亡過程，其中：

  • 狀態 nn 代表系統中有 nn 位顧客。
  • 顧客到達服從指數分佈，率為 λ\lambda。因此，從狀態 nn 到 n+1n+1 的出生率 λn=λ\lambda_n = \lambda 對於所有 n≥0n \ge 0。
  • 顧客服務時間服從指數分佈，率為 μ\mu。由於有無限多個服務器，每位到達的顧客都能立即獲得服務。因此，當系統中有 nn 位顧客時，會有 nn 位顧客正在接受服務。每位正在服務的顧客以率 μ\mu 完成服務離開系統。所以，從狀態 nn 到 n−1n-1 的死亡率 μn=nμ\mu_n = n\mu 對於所有 n≥1n \ge 1。

狀態轉移圖:
狀態 0: 系統中無顧客。
狀態 1: 系統中有一位顧客。
狀態 n: 系統中有 n 位顧客。

  • 從狀態 nn 到 n+1n+1 的轉移（到達）：率為 λn=λ\lambda_n = \lambda。
  • 從狀態 nn 到 n−1n-1 的轉移（離開）：率為 μn=nμ\mu_n = n\mu。
      λ       λ       λ             λ
0 ----> 1 ----> 2 ----> 3 ----> ... ----> n ----> ...
|       ^       ^       ^             ^
|       | 1μ    | 2μ    | 3μ          | nμ
|       |       |       |             |
<-------<-------<-------<-------------<

決定 λn\lambda_n 和 μn\mu_n:

  • 對於任意狀態 n≥0n \ge 0，λn=λ\lambda_n = \lambda (顧客到達率)。
  • 對於任意狀態 n≥1n \ge 1，μn=nμ\mu_n = n\mu (顧客離開率)。

(b) 證明 pn=λnn!μnp0p_n = \frac{\lambda^n}{n!\mu^n} p_0, n=1,2,...n = 1,2,...

根據一般化出生-死亡過程的穩態條件，我們有：
λnpn=μn+1pn+1\lambda_n p_n = \mu_{n+1} p_{n+1} 對於所有 n≥0n \ge 0。

代入我們在 (a) 中得到的 λn\lambda_n 和 μn\mu_n：
λpn=(n+1)μpn+1\lambda p_n = (n+1)\mu p_{n+1}

我們可以重新整理這個方程式來表示 pn+1p_{n+1}：
pn+1=λ(n+1)μpnp_{n+1} = \frac{\lambda}{(n+1)\mu} p_n

現在，我們從 p1p_1 開始，逐步推導 pnp_n：
對於 n=1n=1: p1=λ1μp0=λμp0p_1 = \frac{\lambda}{1\mu} p_0 = \frac{\lambda}{\mu} p_0

🔒

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

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

免費註冊

第 2 題

Let P=[1/21/21/32/3]P = \begin{bmatrix} 1/2 & 1/2 \\ 1/3 & 2/3 \end{bmatrix} be a transition probability matrix of a discrete time Markov chain. The eigenvalues of PP are λ0=1,λ1=1/6\lambda_0 = 1, \lambda_1 = 1/6. Apply Sylvester's formula to get the followings.

(a) (10 points) Determine Z0Z_0 and Z1Z_1.
(b) (15 points) Determine the analytical solution of PnP^n.

Hint: (Sylvester's formula) Let PP be a square matrix of order s+1s+1. Let λ0,λ1,…,λs\lambda_0, \lambda_1, \dots, \lambda_s be the eigenvalues of PP, and assume they are distinct. Then
Pn=∑k=0sλknZkP^n = \sum_{k=0}^{s} \lambda_k^n Z_k
where matrix ZkZ_k is given by
Zk=∏r=0,r≠ksP−λrIs+1λk−λrZ_k = \prod_{r=0, r \neq k}^{s} \frac{P - \lambda_r I_{s+1}}{\lambda_k - \lambda_r}
Is+1I_{s+1} is the identity matrix of order s+1s+1.

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

這一題的完整詳解

核心觀念

本題考察具有相異特徵值之矩陣的 Sylvester 公式：

Pn=∑k=0sλknZkP^n=\sum_{k=0}^{s}\lambda_k^n Z_k

其中 ZkZ_k 為對應於特徵值 λk\lambda_k 的投影矩陣。當矩陣只有兩個相異特徵值 λ0=1\lambda_0=1 與 λ1=16\lambda_1=\frac16 時，

Pn=1nZ0+(16)nZ1=Z0+(16)nZ1.P^n=1^nZ_0+\left(\frac16\right)^nZ_1 =Z_0+\left(\frac16\right)^nZ_1.

兩個投影矩陣分別為

Z0=P−λ1Iλ0−λ1,Z1=P−λ0Iλ1−λ0.Z_0=\frac{P-\lambda_1I}{\lambda_0-\lambda_1}, \qquad Z_1=\frac{P-\lambda_0I}{\lambda_1-\lambda_0}.

解題方法

已知

P=[12121323],λ0=1,λ1=16.P= \begin{bmatrix} \frac12 & \frac12\\[2mm] \frac13 & \frac23 \end{bmatrix}, \qquad \lambda_0=1,\quad \lambda_1=\frac16.

（a）求 Z0Z_0 與 Z1Z_1

求 Z0Z_0

Z0=P−16I1−16=P−16I56.Z_0=\frac{P-\frac16I}{1-\frac16} =\frac{P-\frac16I}{\frac56}.

先計算分子：

P−16I=[12−16121323−16]=[13121312].P-\frac16I = \begin{bmatrix} \frac12-\frac16 & \frac12\\[2mm] \frac13 & \frac23-\frac16 \end{bmatrix} = \begin{bmatrix} \frac13 & \frac12\\[2mm] \frac13 & \frac12 \end{bmatrix}.

因此

Z0=65[13121312]=[25352535].Z_0 = \frac65 \begin{bmatrix} \frac13 & \frac12\\[2mm] \frac13 & \frac12 \end{bmatrix} = \begin{bmatrix} \frac25 & \frac35\\[2mm] \frac25 & \frac35 \end{bmatrix}.

求 Z1Z_1

Z1=P−I16−1=P−I−56.Z_1=\frac{P-I}{\frac16-1} =\frac{P-I}{-\frac56}.

先計算：

P−I=[−121213−13].P-I = \begin{bmatrix} -\frac12 & \frac12\\[2mm] \frac13 & -\frac13 \end{bmatrix}.

所以

Z1=−65[−121213−13]=[35−35−2525].Z_1 = -\frac65 \begin{bmatrix} -\frac12 & \frac12\\[2mm] \frac13 & -\frac13 \end{bmatrix} = \begin{bmatrix} \frac35 & -\frac35\\[2mm] -\frac25 & \frac25 \end{bmatrix}.

（b）求 PnP^n 的解析解

根據 Sylvester 公式：

Pn=1nZ0+(16)nZ1.P^n=1^nZ_0+\left(\frac16\right)^nZ_1.

代入 Z0Z_0 與 Z1Z_1：

Pn=[25352535]+(16)n[35−35−2525].P^n = \begin{bmatrix} \frac25 & \frac35\\[2mm] \frac25 & \frac35 \end{bmatrix} + \left(\frac16\right)^n \begin{bmatrix} \frac35 & -\frac35\\[2mm] -\frac25 & \frac25 \end{bmatrix}.

逐項合併後得到：

🔒

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

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

免費註冊

第 3 題15 分

Consider the following linear programming problem (P) where A is the coefficient matrix, x is the decision variable vector, and c is the cost vector. The dual problem of (P), which is denoted as (D), is also formulated in the following.

(P): Minimize cTxc^T x
subject to Ax≥bAx \ge b
x≥0x \ge 0

(D): Maximize wTbw^T b
subject to wTA≤cTw^T A \le c^T
w≥0w \ge 0

Suppose that x0x_0 is a feasible solution for (P), that is, Ax0≥bAx_0 \ge b, and w0w_0 is a feasible solution for (D), that is, w0TA≤cTw_0^T A \le c^T. Please compare w0Tbw_0^T b (that is, the objective function value of (D)) and cTx0c^T x_0 (that is, the objective function value of (P)) and determine: Do they have the same value? Or, is one larger than or equal to the other? Or, is one strictly larger than the other? You must provide convincing reasons to back up your answer (答案必須有明確的理由).

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

這一題的完整詳解

核心觀念

本題考的是線性規劃的弱對偶定理：對偶問題的任一可行解，其目標值不會大於原問題任一可行解的目標值。

解題方法

由原問題可行性，Ax0≥bAx_0\ge b；又因為 w0≥0w_0\ge 0，左乘 w0Tw_0^T 後不等號方向不變：

w0TAx0≥w0Tbw_0^T Ax_0\ge w_0^T b

由對偶問題可行性，w0TA≤cTw_0^T A\le c^T；又因為 x0≥0x_0\ge 0，右乘 x0x_0 後不等號方向不變：

w0TAx0≤cTx0w_0^T Ax_0\le c^T x_0

合併兩式可得：

w0Tb≤w0TAx0≤cTx0w_0^T b\le w_0^T Ax_0\le c^T x_0
🔒

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

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

免費註冊

第 4 題15 分

Please solve the following linear programming problem and report the optimal solution. Show your calculation process in detail (答案必須有詳細的計算過程).

Minimize 6x1+9x2+15x3+6x4+9x56x_1 + 9x_2 + 15x_3 + 6x_4 + 9x_5
subject to
4x1−4x2+6x3+2x4+2x5≥64x_1 - 4x_2 + 6x_3 + 2x_4 + 2x_5 \ge 6
3x1+3x2+6x3+3x4+9x5≥123x_1 + 3x_2 + 6x_3 + 3x_4 + 9x_5 \ge 12
x1,x2,x3,x4,x5≥0x_1, x_2, x_3, x_4, x_5 \ge 0

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

這一題的完整詳解

核心觀念

本題是標準的線性規劃問題：

  • 目標：最小化總成本。
  • 限制式為「至少達到」的 ≥\ge 型態。
  • 所有變數皆滿足 xj≥0x_j\ge 0。

適合使用：

  1. 對偶問題（Dual Problem）
  2. 弱對偶定理
  3. 互補鬆弛定理（Complementary Slackness）

原問題為：

min⁡Z=6x1+9x2+15x3+6x4+9x5s.t.4x1−4x2+6x3+2x4+2x5≥63x1+3x2+6x3+3x4+9x5≥12x1,x2,x3,x4,x5≥0\begin{aligned} \min\quad Z={}&6x_1+9x_2+15x_3+6x_4+9x_5\\ \text{s.t.}\quad &4x_1-4x_2+6x_3+2x_4+2x_5\ge 6\\ &3x_1+3x_2+6x_3+3x_4+9x_5\ge 12\\ &x_1,x_2,x_3,x_4,x_5\ge 0 \end{aligned}

解題方法：建立對偶問題

對於「最小化、限制式為 ≥\ge、變數非負」的線性規劃，其對偶為「最大化、限制式為 ≤\le、對偶變數非負」。

令兩個對偶變數分別為 y1,y2y_1,y_2，則對偶問題為：

max⁡W=6y1+12y2s.t.4y1+3y2≤6(x1)−4y1+3y2≤9(x2)6y1+6y2≤15(x3)2y1+3y2≤6(x4)2y1+9y2≤9(x5)y1,y2≥0\begin{aligned} \max\quad W={}&6y_1+12y_2\\ \text{s.t.}\quad &4y_1+3y_2\le 6 \qquad (x_1)\\ &-4y_1+3y_2\le 9 \qquad (x_2)\\ &6y_1+6y_2\le 15 \qquad (x_3)\\ &2y_1+3y_2\le 6 \qquad (x_4)\\ &2y_1+9y_2\le 9 \qquad (x_5)\\ &y_1,y_2\ge 0 \end{aligned}

求解對偶問題

觀察對偶目標函數：

W=6y1+12y2W=6y_1+12y_2

其中 y1,y2y_1,y_2 的係數皆為正，因此希望在可行範圍內盡量提高 y1,y2y_1,y_2。

考慮第 1 個與第 5 個對偶限制式：

4y1+3y2≤64y_1+3y_2\le 6 2y1+9y2≤92y_1+9y_2\le 9

將兩式相加，可得：

6y1+12y2≤156y_1+12y_2\le 15

而左側正是對偶目標函數 WW，因此任何對偶可行解都必須滿足：

W≤15W\le 15

若能找到一組可行解使 W=15W=15，即可證明對偶最佳值為 1515。

令上述兩個限制式同時取等號：

{4y1+3y2=62y1+9y2=9\begin{cases} 4y_1+3y_2=6\\ 2y_1+9y_2=9 \end{cases}

第一式乘以 11，兩式相減：

(4y1+3y2)−(2y1+9y2)=6−9(4y_1+3y_2)-(2y_1+9y_2)=6-9 2y1−6y2=−32y_1-6y_2=-3

整理得：

y1=3y2−32y_1=3y_2-\frac{3}{2}

代入第一式：

4(3y2−32)+3y2=64\left(3y_2-\frac{3}{2}\right)+3y_2=6 12y2−6+3y2=612y_2-6+3y_2=6 15y2=1215y_2=12 y2=45y_2=\frac45

因此：

y1=3(45)−32=125−1510=910y_1=3\left(\frac45\right)-\frac32 =\frac{12}{5}-\frac{15}{10} =\frac{9}{10}

故對偶候選解為：

(y1,y2)=(910,45)(y_1,y_2)=\left(\frac9{10},\frac45\right)

檢查其他對偶限制式

代入 y1=910y_1=\frac9{10}、y2=45y_2=\frac45：

−4y1+3y2=−4(910)+3(45)=−65≤9-4y_1+3y_2 =-4\left(\frac9{10}\right)+3\left(\frac45\right) =-\frac65\le 9
🔒

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

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

免費註冊

第 5 題20 分

John is a manager in charge of running a department of 20 Python programmers. Currently, he has a total of 15 projects that he can choose for his programmers. After some thinking, he came up with the following "incidence matrix" indicating the best composition for each project team. For example, John considers that project 1 is best to be handled by programmers 1, 3, and 20.

programmerproject 1project 2project 3...project 15
1110...0
2001...1
3100...0
..................
20110...1

As required by company policies, John must ensure that "no one in his department is left behind;" that is, every programmer must have at least one project to work on. Because the company must pay certain money to programmers doing each project, naturally they asked John to choose some of the projects so that as little money is paid as possible (while at the same time ensuring that no one is left behind).

Let aija_{ij} denote the numeric value indicating whether programmer ii can work on project jj or not. For example, for project 1, we have a1,1=1,a2,1=0,a3,1=1a_{1,1}=1, a_{2,1}=0, a_{3,1}=1, and a20,1=1a_{20,1}=1. Let cjc_j be the total costs that the company will have to pay to those programmers doing project jj. Moreover, let XjX_j be the decision as to whether John should choose project jj or not. To be precise, XjX_j is a binary decision variable such that " Xj=1X_j=1 " indicates that John should choose project jj and " Xj=0X_j=0 " indicates otherwise.

Please formulate the above situation as a binary linear programming model. Note: you are NOT allowed to define any more decision variable, parameters, symbols, etc. (不可自行定義任何新的決策變數、參數、或符號).

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

這一題的完整詳解

此題要求將一個專案分配問題，以二元整數規劃 (Binary Integer Programming, BIP) 的形式建立模型。問題的目標是最小化總成本，同時確保所有程式設計師都有至少一個專案負責。

核心觀念：二元整數規劃、指派問題、成本最小化、資源限制。

模型建立步驟：

  1. 定義決策變數：
    題目已經給定了決策變數：

    • XjX_j: 專案 jj 是否被選擇。
      Xj=1X_j = 1 若選擇專案 jj，否則 Xj=0X_j = 0。
      j=1,2,…,15j = 1, 2, \dots, 15 (共 15 個專案)。
      這些變數是二元的，表示只能選擇或不選擇一個專案。

  2. 定義參數：
    題目也給定了一些參數：

    • aija_{ij}: 指標矩陣，表示程式設計師 ii 是否能執行專案 jj。
      aij=1a_{ij} = 1 若程式設計師 ii 能執行專案 jj，否則 aij=0a_{ij} = 0。
      i=1,2,…,20i = 1, 2, \dots, 20 (共 20 位程式設計師)。
      j=1,2,…,15j = 1, 2, \dots, 15 (共 15 個專案)。
    • cjc_j: 執行專案 jj 的總成本。
    • 總程式設計師數量：20 人。
    • 總專案數量：15 個。

    重要限制： 題目明確要求「不可自行定義任何新的決策變數、參數、或符號」。這意味著我們必須利用 aija_{ij} 和 cjc_j 來表達所有條件。

  3. 建立目標函數：
    目標是最小化總成本。總成本取決於選擇了哪些專案。如果選擇專案 jj (Xj=1X_j=1)，則會產生成本 cjc_j。
    因此，目標函數是：
    Minimize Z=∑j=115cjXjZ = \sum_{j=1}^{15} c_j X_j

  4. 建立約束條件：

    • 約束 1：確保所有程式設計師都有專案可做。
      公司政策要求「沒有人被落下」，即每位程式設計師至少要負責一個專案。
      一位程式設計師 ii 能夠負責專案 jj 的前提是：
      a) 程式設計師 ii 能夠執行專案 jj (aij=1a_{ij}=1)。
      b) 專案 jj 被選擇執行 (Xj=1X_j=1)。

      對於每一個程式設計師 ii (i=1,…,20i = 1, \dots, 20)，他/她所能負責的專案集合為 Ji={j∣aij=1}J_i = \{ j \mid a_{ij} = 1 \}。
      程式設計師 ii 能夠被分配到的專案，必須是 JiJ_i 中的某個專案 jj，且該專案 jj 被選擇 (Xj=1X_j=1)。
      我們需要確保對於每一個 ii，至少有一個 j∈Jij \in J_i 使得 Xj=1X_j=1。

      數學表達式：對於每個程式設計師 ii，必須滿足：
      ∑j=115aijXj≥1\sum_{j=1}^{15} a_{ij} X_j \ge 1
      這裡的 aija_{ij} 是參數，如果程式設計師 ii 不能做專案 jj (aij=0a_{ij}=0)，則該項不會被計入總和。如果 aij=1a_{ij}=1，則表示如果專案 jj 被選擇 (Xj=1X_j=1)，這個專案就可能分配給程式設計師 ii。

🔒

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

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

免費註冊

其他考古題

中央大學《作業研究》其他年度

115 年114 年113 年111 年108 年

其他學校的企管與商學考古題

臺灣大學156清華大學31成功大學102政治大學187中正大學36中山大學158臺北大學69高雄大學38宜蘭大學31嘉義大學26臺南大學22屏東大學21暨南國際大學17中央警察大學14臺北護理健康大學14臺灣海洋大學9聯合大學4臺北商業大學2