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

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

第 1 題40 分

The industrial ship-scheduling problem is concerned with determining appropriate schedules (that is, sailing courses 航線) for a fleet of cargo ships so that they can transport cargoes from one port to the other. The following describes details about this classical O.R. problem.

There are a number of ports with each containing cargo to be transported. Each cargo has a specific port to which it must be transported (called the destination port). At any port, the destination port for one cargo may or may not be the same as the other cargoes' destination ports.

There are cargo ships docked (停泊) at some of the ports (note that it is "some," not "all"). Each ship has a number of candidate schedules that it can choose. These schedules are a list of ports that the corresponding ship will visit one after another according to the given sequence. For example, a schedule like this {Taipei, Kaohsiung, Hong Kong, Manila, Ho Chi Minh City, Singapore} indicates that the corresponding cargo ship is currently docked at the port of Taipei and after departure it will visit Kaohsiung, Hong Kong, Manila, Ho Chi Minh City and Singapore in sequence.

Each cargo ship will choose one of the candidate schedules to sail. Each schedule requires the ship to spend a specific amount of money (for fuels and other sailing-related costs).

Situations for cargoes to be transported to their destination ports:

  1. When a cargo ship leaves its docking port, it may or may not carry all the cargoes waiting to be transported at that port. In other words, the ship can leave some of the cargoes behind and let those cargoes be picked up by other ships (as they will sail to that port because it is in their schedules).
  2. There may be ports that only have cargoes, that is, there are no cargo ships docking at those ports. In such cases, those cargoes can only be transported by ships sailing to those ports from some other ports.

For simplicity, loading capacity and time issues are ignored. That is, we will not consider the maximum number of cargoes that each ship can carry as well as the time at which each cargo must be delivered to its destination port.

The following symbols are defined so we can use to develop a mathematical optimization model for the above industrial ship-scheduling problem.

Parameters:
VV the set of cargo ships to be scheduled (indexed by vv)
RvR_v the set of candidate schedules that ship vv can choose (with rr representing any specific schedule, i.e., r∈Rvr \in R_v)
cvrc_{vr} the fixed total costs for cargo ship vv to choose schedule rr (r∈Rvr \in R_v)
NN the set of cargoes (indexed by ii)
aivra_{ivr} a constant that equals 1 if scheduler for cargo ship vv can provide service to cargo ii and 0 otherwise; that is, "aivr=1a_{ivr} = 1" is equivalent to saying that "if ship vv chooses schedule r∈Rvr \in R_v, it can transport cargo ii to ii's destination port"

Decision variables:
xvrx_{vr} a binary decision variable which equals 1 if ship vv chooses schedule rr to sail and 0 otherwise; that is, xvrx_{vr} equals 1 or 0, ∀v∈V,r∈Rv\forall v \in V, r \in R_v.

Please use the above symbols only to develop a linear optimization model for the industrial ship-scheduling problem (注意!模型必需是線性的,而且只能使用上面所定義過的符號). The goal is to determine a specific schedule for every cargo ship and also ensure a successful service for every cargo (that is, every cargo will be transported to its destination port by one and only one of the cargo ships); the objective of the model is to minimize the total sailing costs for all cargo ships. Please show the objective function and every constraint of the model as completely as possible.

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

這一題的完整詳解

核心觀念

這題是以 0–1 變數選擇航線的「集合涵蓋」型線性規劃。每艘船必須從自己的候選航線中選出一條；每批貨物都必須有船運送。參數 aivra_{ivr} 表示「船 vv 選擇航線 rr 時，能把貨物 ii 運到目的港」，所以用它可以計算：在選定的航線組合下，有幾艘船有能力運送貨物 ii。

解題方法

以 xvrx_{vr} 表示船 vv 是否選擇航線 rr。總成本是所有被選航線固定成本的加總，目標為最小化：

min⁡∑v∈V∑r∈Rvcvrxvr\min \sum_{v\in V}\sum_{r\in R_v} c_{vr}x_{vr}

每艘船恰好選一條航線：

∑r∈Rvxvr=1∀v∈V\sum_{r\in R_v}x_{vr}=1 \qquad \forall v\in V

每批貨物至少有一艘被選的船能運送它：

∑v∈V∑r∈Rvaivrxvr≥1∀i∈N\sum_{v\in V}\sum_{r\in R_v}a_{ivr}x_{vr}\ge 1 \qquad \forall i\in N

航線選擇變數為二元變數：

xvr∈{0,1}∀v∈V, r∈Rvx_{vr}\in\{0,1\} \qquad \forall v\in V,\ r\in R_v

解題技巧

🔒

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

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

免費註冊

第 2 題30 分

Solve the following linear programming model using the simplex method.
Note: You will get zero points if you use any other solution method.

Maximize x1+2x2+3x3x_1 + 2x_2 + 3x_3
Subject to
x1≤4x_1 \le 4
x2≤4x_2 \le 4
x1+x2≤6x_1 + x_2 \le 6
−x1+2x3≤4-x_1 + 2x_3 \le 4
x1,x2,x3≥0x_1, x_2, x_3 \ge 0

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

這一題的完整詳解

核心觀念

本題考查以 單純形法（Simplex Method） 求解最大化線性規劃問題。

標準作法如下：

  1. 將每個「≤\le」限制式加入鬆弛變數，使其成為等式。
  2. 以鬆弛變數作為初始基底變數。
  3. 由目標列中最大的 Cj−ZjC_j-Z_j 選入基底變數。
  4. 以最小正比值
    RHS主元欄正係數\frac{\text{RHS}}{\text{主元欄正係數}}
    決定離開基底的變數。
  5. 進行樞紐運算，直到所有 Cj−Zj≤0C_j-Z_j\le 0，即達到最大值。

由於所有限制式右端值皆非負，加入鬆弛變數後即可直接建立可行的初始基底，不需要人工變數。

解題方法

原問題為

max⁡Z=x1+2x2+3x3\max Z=x_1+2x_2+3x_3

限制式為

x1+s1=4,x2+s2=4,x1+x2+s3=6,−x1+2x3+s4=4,\begin{aligned} x_1+s_1&=4,\\ x_2+s_2&=4,\\ x_1+x_2+s_3&=6,\\ -x_1+2x_3+s_4&=4, \end{aligned}

其中

x1,x2,x3,s1,s2,s3,s4≥0.x_1,x_2,x_3,s_1,s_2,s_3,s_4\ge 0.

各變數的目標係數為

Cj=(1,2,3,0,0,0,0).C_j=(1,2,3,0,0,0,0).

第一次單純形表

初始基底為 s1,s2,s3,s4s_1,s_2,s_3,s_4：

基底CBRHSx1x2x3s1s2s3s4s1041001000s2040100100s3061100010s404−10200011230000\begin{array}{c|c|c|rrrrrrr} \text{基底}&C_B&\text{RHS}&x_1&x_2&x_3&s_1&s_2&s_3&s_4\\ \hline s_1&0&4&1&0&0&1&0&0&0\\ s_2&0&4&0&1&0&0&1&0&0\\ s_3&0&6&1&1&0&0&0&1&0\\ s_4&0&4&-1&0&2&0&0&0&1\\ \hline &&&1&2&3&0&0&0&0 \end{array}

初始目標列為

Cj−Zj=(1,2,3,0,0,0,0).C_j-Z_j=(1,2,3,0,0,0,0).

最大正值為 33，因此選擇 x3x_3 進入基底。

x3x_3 欄只有第 4 列係數為正，因此離開基底的變數為 s4s_4。主元為 22，比值為

42=2.\frac{4}{2}=2.

將第 4 列除以 22，使主元變成 11：

−12x1+x3+12s4=2.-\frac12x_1+x_3+\frac12s_4=2.

第二次單純形表

此時基底為 s1,s2,s3,x3s_1,s_2,s_3,x_3：

基底CBRHSx1x2x3s1s2s3s4s1041001000s2040100100s3061100010x332−120100012Zj6−320300032Cj−Zj5220000−32\begin{array}{c|c|c|rrrrrrr} \text{基底}&C_B&\text{RHS}&x_1&x_2&x_3&s_1&s_2&s_3&s_4\\ \hline s_1&0&4&1&0&0&1&0&0&0\\ s_2&0&4&0&1&0&0&1&0&0\\ s_3&0&6&1&1&0&0&0&1&0\\ x_3&3&2&-\frac12&0&1&0&0&0&\frac12\\ \hline Z_j&&6&-\frac32&0&3&0&0&0&\frac32\\ C_j-Z_j&&&\frac52&2&0&0&0&0&-\frac32 \end{array}

最大正值為

52,\frac52,

因此選擇 x1x_1 進入基底。

對 x1x_1 欄進行最小正比值檢定：

s1 列：41=4,s3 列：61=6.\begin{aligned} s_1\text{ 列：}&\quad \frac{4}{1}=4,\\ s_3\text{ 列：}&\quad \frac{6}{1}=6. \end{aligned}

第 4 列的 x1x_1 係數為負，不列入比值檢定。因此最小正比值為 44，由 s1s_1 離開基底。

主元為第 1 列的 11。樞紐運算後：

🔒

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

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

免費註冊

第 3 題30 分

"Convex sets” (凸集合) are the foundation on which our knowledge about mathematical programming and optimization has been developed. The following is a way to define convex sets.
We can choose any two points from a convex set, draw a line segment to connect them and this line segment will entirely be contained in the set (我們可自一個凸集合中選任何兩點來構成一線段,該線段上沒有任何一點是落在該凸集合之外).
The above definition is illustrated by the following two figures: The shaded area in the left figure is a convex set and the shaded area in the right figure is NOT (because part of the line segment connecting (x1,y1)(x_1,y_1) and (x2,y2)(x_2,y_2) in the right figure is clearly not in the shaded area).

🖼️【此處有附圖，請對照原卷】
(圖示：左邊為凸集合，右邊為非凸集合)

In the following figure, the shaded area is the intersection (交集) of x≥0,y≥0x \ge 0, y \ge 0 and x≥yx \ge y.
This shaded area looks that it is a convex set. However, to be 100% certain, we can only use the definition to check (or to test). So please do so. That is, please use the above definition for convex sets to check/test whether the shaded area is a convex set or not. Note that your answer must be given for the general case, that is, based on any two points selected from the shaded area.

🖼️【此處有附圖，請對照原卷】
(圖示：包含 x≥0,y≥0,x≥yx \ge 0, y \ge 0, x \ge y 的交集區域)

🖼️ 本題含圖表，以下為原卷對應頁面：
原卷第 3 頁原卷第 4 頁

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

這一題的完整詳解

核心觀念

本題考查作業研究與數學規劃中最基本的幾何與分析概念：凸集合（Convex Set）的數學嚴格定義與證明。

  1. 凸集合的定義：
    設集合 S⊆RnS \subseteq \mathbb{R}^n，若對任意兩點 u,v∈S\mathbf{u}, \mathbf{v} \in S 以及任意實數 λ∈[0,1]\lambda \in [0, 1]，連接此兩點的線段上所有點： w=λu+(1−λ)v\mathbf{w} = \lambda \mathbf{u} + (1 - \lambda)\mathbf{v} 均滿足 w∈S\mathbf{w} \in S，則稱 SS 為凸集合。
  2. 線性不等式與半空間（Half-spaces）：
    本題區域為三個半空間的交集： S={(x,y)∈R2∣x≥0,  y≥0,  x−y≥0}S = \{(x, y) \in \mathbb{R}^2 \mid x \ge 0,\; y \ge 0,\; x - y \ge 0\} 題目要求依題目所給的幾何與代數定義，自該區域任選兩點進行一般性（general case）的嚴格代數檢驗與證明。

解題方法

要證明集合 SS 為凸集合，必須遵循嚴謹的分析步驟：

  1. 設定一般化的任意兩點：
    任取兩點 P1=(x1,y1)∈SP_1 = (x_1, y_1) \in S 與 P2=(x2,y2)∈SP_2 = (x_2, y_2) \in S。
    由定義可知，P1P_1 與 P2P_2 的座標均滿足題目給定的三條約束條件：
    • 對 P1P_1：x1≥0x_1 \ge 0、y1≥0y_1 \ge 0 且 x1≥y1x_1 \ge y_1
    • 對 P2P_2：x2≥0x_2 \ge 0、y2≥0y_2 \ge 0 且 x2≥y2x_2 \ge y_2
  2. 表示線段上的任意點：
    任取純量 λ∈[0,1]\lambda \in [0, 1]，連接 P1P_1 與 P2P_2 之線段上的任意點 Pλ=(xλ,yλ)P_\lambda = (x_\lambda, y_\lambda) 可表示為兩點的凸組合（Convex Combination）： xλ=λx1+(1−λ)x2x_\lambda = \lambda x_1 + (1 - \lambda)x_2 yλ=λy1+(1−λ)y2y_\lambda = \lambda y_1 + (1 - \lambda)y_2
  3. 逐一檢驗 PλP_\lambda 是否仍滿足集合的三大條件：
    • 條件一（xλ≥0x_\lambda \ge 0）：
      因為 x1≥0x_1 \ge 0、x2≥0x_2 \ge 0，且 λ≥0\lambda \ge 0、1−λ≥01 - \lambda \ge 0，所以兩項非負數相加必非負： xλ=λx1+(1−λ)x2≥0x_\lambda = \lambda x_1 + (1 - \lambda)x_2 \ge 0
    • 條件二（yλ≥0y_\lambda \ge 0）：
🔒

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

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

免費註冊

其他考古題

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

114 年113 年112 年111 年108 年

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

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