114 年 國立成功大學工業與資訊管理學系研究所甲組《作業研究》
第 1 題
- Consider the following linear programming:
min
s.t.
(P)
(a) [10%] Formulate the dual problem corresponding to (P).
(b) [5%] For the network shown below, apply the primal-dual method as outlined in the slides to determine the flow pattern that achieves the maximum flow from the source (node 1) to the sink (node 4). The arc capacity from node to node is represented by the number at the center of the arc connecting these nodes.
🖼️【此處有附圖,請對照原卷】
Now the initial flow is given by
| Node | Node | Flow from Node to Node |
|---|---|---|
| 1 | 2 | 1 |
| 1 | 3 | 2 |
| 2 | 4 | 3 |
| 3 | 4 | 1 |
| Determine the maximum flow, starting from the given initial flow. | ||
| (c) [10%] Find the optimal value for (P). (Hint: Consider the relation between the problems in (a) and (b).) | ||
| (d) [5%] Find an optimal solution for (P). |
登入後即可作答並保存紀錄。
核心觀念
本題結合三個重點:
- 線性規劃的對偶問題建立。
- 最大流問題的殘餘網路與增廣路徑。
- 強對偶定理:原問題與對偶問題的最佳值相等。
原問題 是
(a) 對偶問題
令前五條等式限制式的對偶變數為 ,第六條等式限制式的對偶變數為 。由於原問題的限制式皆為等式,因此
皆為自由變數。
原問題右側常數只有第六條為 ,所以對偶目標函數為
逐一對應原問題變數,可得:
因此對偶問題為
其中 可視為網路各弧的流量, 為由節點 至節點 的總流量。
(b) 最大流問題
由圖可讀得網路弧及容量為:
題目文字所列的初始流量中, 的流量若為 ,會超過該弧容量 ,因此不可能是可行流。以下依原圖容量及可行流條件,採用可行初始流作增廣分析。
第一次增廣
在殘餘網路中,取路徑
其剩餘容量為
第 2 題
- Consider the following linear programming:
max
s.t.
.
(P)
where can be assigned any positive or negative values. After apply the simplex method with , the final tableau is
| Basic Vars | Z | | | | | | RHS |
|---|---|---|---|---|---|---|---|
| Z | 1 | 0 | 0 | 0 | | | |
| | 0 | 1 | 0 | 0 | | | |
| | 0 | 0 | 1 | 0 | | | |
| | 0 | 0 | 0 | 1 | | | |
(a) [10%] Determine and such that over the range the above basic solution will remain optimal. Find the objective value (as a function of ), and then find the best choice within this range.
____, ____, ____, ____
(b) [5%] Given that within the range of values found in (a), identify the shadow prices and (as a function of ) for the two resources.
____, ____
(c) [5%] Given , additional constraint is added to the problem (P). Determine the optimal solution of (P).
____
登入後即可作答並保存紀錄。
核心觀念
本題考查:
- 目標函數係數變動時的敏感度分析。
- 利用最終單純形表判斷目前基底是否仍然最適。
- 影子價格與鬆弛變數欄位的關係。
- 新增限制式後的可行性判斷。
最終表中,非基底變數為 ,其目標列為
在本題表格的記號下,最大化問題維持最適的條件是目標列中非基底變數的係數皆不大於 。
(a) 係數變動範圍、目標值與最佳
1. 基底解
由最終表令非基底變數 ,得到
因此在這段敏感度分析中,基底解固定不變。
2. 目標函數值
原目標函數為
代入基底解:
依題目所給最終表的目標列,常數項為 ,因此敏感度分析下的目標值寫成
其中 造成的目標列變化如下。
3. 更新目標列
由最終表, 欄在三個基底變數列中的係數分別為
目標函數係數的變化量為
因此, 欄目標列係數的變化量為
原係數為 ,故更新後為
同理, 欄目標列係數的變化量為
因此
4. 判斷 的範圍
要維持目前基底最適,必須滿足
以及
第 3 題
- Please express the following statements with linear constraints using binary variables.
(a) (5%) or .
(b) (5%) can be values 0, 5, 9, or 12.
(c) (5%) If , then ; otherwise .
登入後即可作答並保存紀錄。
這題考驗將邏輯敘述轉換為線性約束(包含二元變數)的能力。二元變數(binary variables)通常用來表示「是」或「否」的選擇,或是在多個選項中選擇一個。
(a) or
這個敘述是一個「或」的關係,表示兩個條件中至少有一個必須成立。為了處理這種「或」的邏輯,我們引入一個二元變數 。
令 表示第一個條件成立 ()。
令 表示第二個條件成立 ()。
為了讓 控制哪個條件成立,我們引入一個足夠大的常數 。
-
處理第一個條件 ():
我們希望當 時,這個條件必須滿足。當 時,這個條件可以不滿足。
可以寫成:。
當 時, (必須滿足)。
當 時, (通常 M 夠大,此約束變得鬆弛)。 -
處理第二個條件 ():
我們希望當 時,這個條件必須滿足。當 時,這個條件可以不滿足。
可以寫成:。
當 時, (必須滿足)。
當 時, (通常 M 夠大,此約束變得鬆弛)。
綜合以上,我們得到以下線性約束:
選擇 M 的方法:
M 必須足夠大,以確保在另一種情況下約束是鬆弛的。
對於第一個約束,。當 時,我們希望約束不起作用。假設 的合理範圍是有限的,M 必須大於 的最大可能值。
對於第二個約束,。當 時,我們希望約束不起作用。M 必須大於 的最大可能值。
通常,M 可以設為一個非常大的正數。
另一種常見的處理方式是:
引入二元變數 。
令 表示第一個條件成立,否則 。
令 表示第二個條件成立,否則 。
我們需要 (表示「或」的關係)。
-
條件 1:。
當 時,必須滿足。當 時,可以不滿足。
當 時,。
當 時,。 -
條件 2:。
當 時,必須滿足。當 時,可以不滿足。
當 時,。
當 時,。
綜合:
如果我們回到第一種方法,使用單一的二元變數 。
令 表示條件 1 成立, 表示條件 2 成立。
【答案】
令 為一個二元變數 ()。
其中 是一個足夠大的正數。
(b) can be values 0, 5, 9, or 12.
這個敘述表示 的值必須是這四個離散值之一。為了表示這種「多選一」的關係,我們引入多個二元變數,每個變數對應一個選項。
令 為四個二元變數,其中 表示 ,否則 。
第 4 題
- There are two types of customers. Type 1 and 2 customers arrive in accordance with independent Poisson processes with respective rate and . There are two servers. A type 1 arrival will enter service with server 1 if that server is free; if server 1 is busy and server 2 is free, then the type 1 arrival will enter service with server 2. If both servers are busy, then the type 1 arrival will go away. A type 2 customer can only be served by server 2; if server 2 is free when a type 2 customer arrives, then the customer enters service with that server. If server 2 is busy when a type 2 arrives, then that customer goes away. Once a customer is served by either server, he departs the system. Service times at server are exponential with rate , . Suppose we want to find the average number of customers in the system.
(a) (5%) Define states.
(b) (5%) Give the balance equations. Do not attempt to solve them.
In terms of the long-run probabilities, what is
(c) (5%) the average number of customers in the system?
(d) (5%) the average time a customer spends in the system.
登入後即可作答並保存紀錄。
作業研究 – 失敗排隊系統 (Loss System) 參考詳解
1. 核心觀念
- Poisson 到達:兩類客戶的到達是獨立的 Poisson 流,參數分別為 (類別 1)與 (類別 2)。
- 指數服務時間:伺服器 的服務時間服從指數分布,速率為 。
- 無排隊、失敗系統:若到達時所有可用伺服器皆忙碌,客戶直接離開(loss),因此系統只能有 0、1、2 個客戶同時在系統中。
- 馬可夫過程(CTMC):系統狀態變化僅受目前佔用情形影響,符合連續時間馬可夫鏈的條件。
- 穩態平衡方程:以長期機率 ( 為伺服器 1 是否佔用, 為伺服器 2 是否佔用)寫出進出流平衡。
- Little 定理:平均系統人數 與有效到達率 、平均逗留時間 之關係 。
2. 解題方法
(a) 定義狀態
伺服器 、 各有「閒」(0) /「忙」(1) 兩種情形,故系統的狀態集合為
其中 代表伺服器 1 為 、伺服器 2 為 ()。
對應的長期機率記為 。
(b) 平衡方程(不求解)
| 狀態 | 可能的 離開 事件 | 可能的 進入 事件 |
|---|---|---|
| 類別 1 到達 →;類別 2 到達 → | 伺服器 1 完工 ←;伺服器 2 完工 ← | |
| 服務完成 →;類別 1、2 到達均導入伺服器 2,分別以 → | 類別 1 到達 ← | |
| 服務完成 →;類別 1 到達導入伺服器 1,→ | 類別 2 到達 ← | |
| 服務完成 →;服務完成 → | 由 以 、由 以 進入 |
寫成 全局平衡方程(每個狀態的流入=流出):
第 5 題15 分
- (15%) Consider a population of individuals each of whom possesses two genes which can be either type A or type a. Suppose that in outward appearance type A is dominant and type a is recessive. (That is, an individual will have only the outward characteristics of the recessive gene if its pair is aa.) Suppose that the population has stabilized, and the percentages of individuals having respective gene pairs AA, aa, and Aa are p, q, and r. Call an individual dominant or recessive depending on the outward characteristics it exhibits. Let denote the probability that an offspring of two dominant parents will be recessive; and let denote the probability that the offspring of one dominant and one recessive parent will be recessive. Compute and to show that .
登入後即可作答並保存紀錄。
核心觀念
- 基因型 (genotype) 與表現型 (phenotype) 的關係:A 為顯性,a 為隱性,只有 aa 才表現為隱性外觀。
- 穩定族群中基因型頻率:,且 。
- 條件機率:給定父母的外觀(顯性或隱性)時,必須先求其基因型的條件分布。
- Mendelian 遺傳規則:兩基因對的交配結果可用表格或機率公式直接寫出。
解題方法
- 求顯性父母的基因型條件機率
- 顯性 × 顯性()
- 只有兩者皆為 時,子代才有機會得到 aa。
- 的子代基因型分布為 。
- 因此