# Operation Research

### Terminology
- Linear Programming 線性規劃
- Solution 給決策變數隨意值，"無論是否可行，都稱作解"
- Feasible Solution 可行解，即符合所有限制式的解
- Infeseasible Solution 不可行解，指有不符合限制式的解
- Feasible Region 可行解區域，指限制式圈起來的區域
- Optimal Solution Feasible Region 中的最優解
- Corner Point 多個限制式的交點，不論是否是 Feasible 都稱作 Corner Point
- Corner Point Feasible CPF，Corner Point，但位於 Feasible Region 內
- Slack Variable 鬆弛變數
- Decision Variables
- Object Function
- Functional Constraint
- Non Negative Constraint

### How to Formulate Problem
1. 找出 Decision Variables
2. 找出 Object Function
3. 列出所有 Constraint
4. 計算結果

### Getting Started
甚麼是線性規劃：https://www.youtube.com/watch?v=E72DWgKP_1Y&ab_channel=TomS

另一個有趣的案例，關於幻方：https://www.youtube.com/watch?v=91Ft3cLu-3o&list=PLdYmuqrR3BQZHyrD9p1NpifhWcUKNAK4R&index=4&ab_channel=Chih-huaHsu
幻方的解有很多個，但我們限制 min x1 的時候就可以得到一個唯一的最佳解

作業研究的線性規劃問題通常列出的 Functional Constraint（列數）都比變數少很多，因此矩陣是把多維壓到低維，因此有許多維度被壓縮，也就是說解有無數個，但我們要這些解之中評估"何謂最佳"，因此會使用代表 Object Function 係數的向量與 Object Variable 內積，讓其達到最大/小值（也就是解投影到 Object Vector 的投影長），在幻方的案例中，原本解有很多個，但引入了 Object Function 以後，這樣就限制最佳解只會有一個了

### Property of Linear Programming
- Feasible Region 必定是外凸（Convex）
- 如果有 Feasible Region 且 Bounded，則 Optimal Solution 必定在 Corner Point 上
- 沒有 Optimal Solution 的情況：
1. 有 Feasible Region 但沒有邊界的情況
2. 沒有 Feasible Region，無解
- 通常來說，如果有 n 個變數（Dimension），則構成一個 CPF 需要 n 個限制式
- 如果有多重的 Optimal Solution，則符合最優解的 CPF 必定有兩個
- n 個變數下，兩個 CPF 相鄰，則這兩個 CPF 必定共用 n - 1 個限制式
- n 個變數下，每個 CPF 可以延伸出兩個 Edge，一個 CPF 會有 n 個相鄰的 CPF
- 兩個相鄰的 CPF 的連線稱作 Edge
- 易錯：每個 CPF 必定需要 n 個限制式，但不代表 n 個限制式必定會有一個 CPF，例如限制式所成的 HyperPlane 都彼此平行，但大多數情況下確實 n 個限制式會產生一個 CPF
- LP 的基本假設：
- 決策變數增加一單位，則 Object Function 貢獻增加的單位也是固定的，實際狀況來說這是一個很不切實際的假設
- 可加性：生產 A 單位賺到 5 元，生產 B 單位賺到 3 元，則同時生產 A + B 則賺到 8 元
- CPF 的個數為 C(決策變數數量（等同於 Non-Negative Constraint 的數量） + #限制式數量 取 限制式數量)

### Simplex Method
幾何上的理解：透過放鬆一個 Contraint，綁定一個 Constraint 的方式從一個 CPF 移動到相鄰的 CPF，這移動的過程必定使 Object Function 的值增加，且這是一個迭代的過程，詳細步驟如下：
1. 從起始 CPF 開始（通常設為原點）
2. 檢查該 CPF 是不是最佳
3. 是：已求得最佳解
4. 否：找到更好的相鄰 CPF，並且回到步驟 2

代數方法：
對每個不等式引入 Slack Variable
- 限制式的 Slack Variable 等於 0，代表該點位於該限制式上
- 限制式的 Slack Varaible 大於 0，代表該點位於該限制式的可行解區域內
- 限制式的 Slack Variable 小於 0，代表該點位於該限制式的可行解區域外（不重要）
必須要特別注重 Slack Variable 的狀態，可行解的情況分為兩種：大於零以及等於零，分別代表綁定、不綁定某個 Constraint，最起始點我們使用原點，綁定 n 個 Contraint 分別為 $x_1\ge0, x_2\ge0,...x_n\ge0$，之後我們要把一些 Constraint 換掉，換成其他限制式，此時這些 Slack Variable 分別就代表那些各自的限制式，如果 Slack Variable 等於 0，就代表該 Slack 所對應的 Constriant 被綁定，因為能夠指明當下 CPF 是否貼著特定的 Constraint，因此 Slack Variable 又稱作 Indicate Variable，而挑選 Non Basic Variable 可以說是選擇貼近哪些 Constraint，挑選 Basic Variable 則是說選擇遠離哪些 Constraint

原理就是將一些 Free Variable（Free Variable 的數量等同於決策變數的數量）設為 0，這些被設為 0 的變數又稱作 non-basic variable，以原點為起點的初始狀態下，non-basic variable 就分別對應那些 slack variable，且 CPF 隨時必定都貼著 non-basic Variable 所代表的 Bound，其餘非 0 的變數則稱作 Basic Variable，Basic Variable 的數量等於 Functional Contraint 的數量

此外，由於 Basic Variable 的正、負、零的性質決定是否當下的 CPF 貼近某個 Constraint，因此如果你的計算過程中，如果 Basic Variable 的等號右邊常數小於 0，就必定是錯的，因為已經跑到可行解外，可能代表前面有計算錯誤

要特別注重的點是：相鄰的 CPF 的解的 Basic Variable 必定只差一個

如何決定放鬆哪個 Constraint：只要是 Object function 的變數係數為正就可以，但通常習慣上會選擇 Object function 中最大正係數的變量所對應的 Constraint

### Unbounded Constraint
如果要替換掉的變數的 Column 的係數最大值為 0，就代表 Unbounded，因為成長率無限，如果 Iteration 中決定 Leaving Variable 時，從中選出正的最小值是無限大，那麼這個最終解就是無限大

範例：
Max $x_1$
$x_1 - x_2\le 3$
$-x_1 + x_2\le 3$

### Degenerate Form
如果過程中有 Basic Variable 為 0（即 Functional Constraint 在運算過程中發現等號右邊為 0），就代表是 Degenerate Form

正常來說，CPF 綁定到的 Constraint 數量與 Non Basic Variable 的數量一樣多，也可以說與決策變數的數量一樣多，但 Degenerate Form 會使正常應該沒有綁定到的 CPF 的 Constraint 也碰到 CPF，幾何情況以下圖表示，正常來說 CPF 只應該碰到兩條線，但這情況下卻碰到了三條


### How to Determine If Problem Have Multiple Optiomal Solution
如果 Simplex 做完以後， Non-Basic Variable 在最終的 Object Function 中所對應的係數為 0，就代表有多重最佳解，因為發現即使有條 Non Basic Variable 無論怎麼變化（即該條線無論如何被移動），他與另外那些 Non-Basic Variable 所代表的 Constraint 所交的點

例如：
Max $x + y$
$x \le 1$
$y \le 1$
$x + y \le 1.5$
$x,y\ge 0$
可求得結果為 $x = 1, y = 0.5$，即下圖兩條紅線的焦點，但使用 Simplex Mthod 後，最終的 Optimal Solution 中一定有個 Non Basic Variable 所對應的係數必定不為 0，也就是如果拖動那個 Non Basic Variable 所對應的"線"，與另一條紅色線的焦點會移動，但投影到 object function 所對應的向量仍然值不會變，因為那個焦點無論如何移動，其移動軌跡永遠垂直藍線，自然不可能會影響 object function，故對應的係數為 0

若要找到另一個 Optimal Solution，就只需要取係數為 0 的那個 Column 再做一次 Simplex Iteration 即可

### Situation of Not Non Negative Constraint
如果 Non Negative Constraint 不再是 $x \ge0$，而是 $x\ge3$ 這種情況，就使用變數代換法，改成 $x - 3\ge 0$，並且以 $x' = x - 3$ 把所有 Object Function、Constraint 中的變數都換掉

如果是 $x\le 3$，就改成 $3 - x \ge 0$，並且以 $x' = 3 - x$ 把所有 Object Function、Constraint 中的變數都換掉

如果是 x 為 Free 的情況，則改成 $x = x' - x''$，代表憑空生出兩個變數，但這兩個變數都大於 0，然後同樣將算式中的 x 都替換掉

### Object Function Not Maximized
Object Function 不是話最大值的話，可轉成 Min 以後，得到結果以後再乘上負號，例如 Max Z = x1 + 2x2 + x3 可轉為 Min Z = -x1 - 2x2 - x3，假設得到 Min Z 結果為 20，則實際結果應為 -20

### Big M Method
如果 Object Function 的 Artifact Variable 不等於 0，就代表 Infeasible，但如果 Artifact Variable 能夠變成 0，就永遠不會回到非 0

要注意的是，開始做 Simplex Method 之前要先確保 Basic Variable Column 對應的 Object Function 係數為 0，也就是產生的 M 要先處理，確保 Basic Variable 對應的 Column 只有一個 1 和一堆 0

### Two Phase Method
參考影片：https://www.youtube.com/watch?v=jFWL3d6x5lA&t=896s&ab_channel=ShokoufehMirzaei

原理是先定出一個 CPF 再開始做 Simplex Method，只要將 M 的部分提取出來後並且最小化即可，做完以後必定為 0，並且能夠得出各 Slack Variable 的起始值

### Revised Simplex Method
Revised Simplex Method 就只是 Simplex Method 的矩陣形式，兩者原理完全一致

變數定義：
- $x_B$：Basic Variable 的集合
- $x_N$：Non-Basic Variable 的集合
- B：[A I] 矩陣中，Basic Variable 所對應到的 Column　所形成的矩陣
- N：[A I] 矩陣中，Non Basic Variable 所對應到的 Column　所形成的矩陣

公式推導：
1. 原矩陣如下，把 Column 分成 Basic 與 Non-Basic，我們目的是將 B 變成 I，並且 B 對應的 $c_B$ 也都保證變成 0 向量

2. 先將 B 變成 I，對應的 Row Operation 都作用在同一 Row 的其他矩陣/向量上

3. 接者將 $c_B$ 變成 0，由於 $BB^{-1}$ 為 $I$，將該 Row 都乘上 $c_B$ 後減掉最上排就能達成

4. 結論：整個矩陣乘上以下這個矩陣就是了

換個視角看，不使用 B N 分法看，而是使用 A I 的形式看：會發現　Object Function 的值為 $(c_BB^{-1})b$，前兩項一起看，正好等同於 Slack Variable 的係數值(根據做法，可能會多個負號，但該值應為正)，而 b 代表資源的量，前面那陀東西就是代表能夠影響 Z 的乘數，Shadow Price 就是這麼來的，此外有時候會用 $y$ 表示 $c_BB^{-1}$

如何決定誰是 Entering Variable, Leaving Variable：
1. 決定 Entering Variable：根據公式，Non Basic Variable 的係數等於 $C_N -C_BB^{-1}N$ 這個計算結果向量中的值，然後取正最多的係數的 Variable 作為 Entering Variable
2. 取得 Entering Variable 對應的 Column 經過 Iteration 後的結果，令為 $d = B^{-1}e$
3. 決定 Leaving Variable：$B^{-1}b$ 代表原各個 Basic Variable 對應的值，將其除以 $B^{-1}e$，得到最小的正數，對應的 Variable 就是 Leaving Variable

### 已知 B Inverse，如何求得最佳解時的整張 Table（BV 值、最佳解、NBV 的係數等）
1. 先想辦法求得 BV 有哪些，只要將 A 乘上 $B^{-1}$ 與 $B^{-1}$ 放在一起，就能找出 BV 有哪些
2. 找到 BV 以後就知道其對應的 Object Function 係數都該填 0
3. 用 Simplex Method 的公式，求出 BV 的值、NBV 的係數值以及 Z 值

例題及解答：

# Sensitive Analysis(Introduction)
### Shadow Price
通常來說，Functional Constaint 所對應的資源數量（即常數的部分）會很頻繁的改變，例如員工的數量、原物料的數量等等，因此在已經算出一個既有的 Solution 以後，我們想知道如果某個資源（不等式右邊的常數）增加了一點點（例如 1），能夠帶來怎麼樣的收入增益，這又叫做 Post Optimization Analysis，圖形上來說，就是讓該 Constraint 推離遠離原點以後，對 Optimal Solution 的影響值，常以 $y$ 表示

如果一個資源的 Shadow Price 是 10 元，這意思就是說如果提升了一單位的資源，就會增加最大收益 10 元，或是減少一單位的資源，就會減少最大收益 10 元

如果 Shadow Price 為 0，代表無論增加多少，都不會增加總效益，稱作自由財，反之稱作稀有財

### How to Get Shadow Price
某個資源的 Shadow Price 等於第 i 個 Slack Variable 在最到達最優的 Iteration 所對應的係數值(根據做法不同可能要取負號)，為何如此？詳情請見 Duality，另外，在 Standard Form 下（Max Z），Shadow Price 必定是大於等於 0，如果改為取 Min Z 時，則應該要小於等於 0

例如：
Max $x_1 + x_2$
$x_1 \le 1$
$x_2 \le 1$
$x_1 + x_2 \le 1.5$
$x_1,x_2\ge 0$
經過 Simplex Method 以後：
此時 Optimal Solution 為 1.5，各變數為 $x_1=1, x_2=0.5, x_3 = 0, x_4 = 0.5, x_5 = 0$，各對應的係數為 $c_1 = 0, c_2 =0, c_3 = 0, c_4 =0, c_5 =1$

此時如果第三條限制式的資源單位增加 0.5，變成 $x_1 + x_2 \le 2$，則該資源限制式對應的 Slack Variable $x_5$ 的係數 $c_5=1$，0.5 * 1 = 0.5，故提高一單位的 $b_3$，總收益會提高 0.5

如果增加資源數量且 Optimal CPF 的組合沒有換，那麼 Shadow Price 則就是把更新過的 Constraint 與原本就貼著的那些 Constraint 求交點，再計算新 Object Value 與舊 Object Value 的差即可

### What is Sensitive Analysis
在不改變 Optimal Solution x，但可改變 Z 的情況下，各種 Sensitive Parameter 可變動的範圍，這些 Parameter 可包含：
- Functional Constraint 的常數（資源數量）
- Object Function 的係數
- Functional Constraint 的係數
如果該參數變動，則 Optimal Solution 也會變動

針對資源數量（Functional Constraint 的常數）的 Sensitive Analysis：前面提到，增加一單位的資源能夠對 Object Function 帶來多少的改變率，其值等於 Simplex Method 求解完後，各資源所對應的 Slack Variable 的係數，而如果：
- 該資源對應的 Slack Variable 係數（即 Shadow Price）大於 0，即 Sensitive Parameter
- 該資源對應的 Slack Variable 係數（即 Shadow Price）等於 0，即 Non-Sensitive Parameter

此外還可以針對資源數量知道 b 如何變化時，BV 組合不會改變

針對 Object Function 的係數的 Sensitive Analysis：想知道不改變最佳 BV 組合的情況下，原 Object Function 的各個係數（以實際案例來說，例如商品的售出價格）各自可以怎麼變動，這使得生產資源的配置不會變（即 Optimal Solution 的組合仍不變），但是淨收益增加，圖形上來說就是 Object Function 所代表的 Vector 可以如何擺動但 CPF 仍保持不變

針對 Functional Constraint 的係數的 Sensitive Analysis：由於製程等因素，是有可能使得 Functional Constraint 的係數產生改變，因此針對 Functional Constraint 的係數的分析也是有意義的，可分析在 Optimal Solution 組合不變的情況下，Functional Constraint 的係數可以變化的範圍

### Binding Constraint and Sensitivity Parameter
指限制住最佳解的 Constraint，即最佳的 CPF 所靠到的那些 Constraint，如果某個 Constraint 不是 Binding Constraint，那麼即使該 Constraint 所對應的資源增加，也不會對 Object Function 帶來增益

Binding Constraint 對應的資源的 Shadow Price 為正，因為它原先就限制了最佳解，而如果該資源增加了就等於提高 Z 的上限，此時對應的 $b_i$ 稱作敏感參數，而 Unbinding Constraint 對應的資源的 Shadow Price 為零，因為沒有限制最佳解，即使這資源無限增加，也會被其他資源限制，故無法增加 Z 值，Shadow Price 因此為 0，此時對應的 $b_i$ 稱作不敏感參數

以上是對於 b 的 Sensitive Analysis，而對於 Object Function 的係數 c 的 Sensitivity Anaylsis，則要關注其斜率，可得知 c 的變動範圍上下限為何，但使得最佳組合 x 仍不變

最後是 $a_ij$，表達技術如何影響資源的使用效率，如何判斷 $a_ij$ 是否敏感？實際上只有當某個 Constraint 是 Binding Constraint 時，對應的 $a_ij$ 才會是敏感的，因為只有 Binding Constraint 的 $a_ij$ 改變時，才能讓 Binding Constraint 產生偏移，也才能夠讓 Z 變化

# Duality
有種情境是這樣：我們在求 LP 之前想先估計最佳解，但這該怎麼做？可先將將每個 Constraint 整體都乘上一個 $y_i$ 值，並且確保每項係數都比 Object Function 大，然後再把 Functional Constraint 等號右邊的值也乘上一個值，這個值就會是 Upper Bound，說穿了 Duality 就是找這個 $y_i$ 的組合使得等號右邊的值能夠盡可能縮小，但仍然是有效的 Upper Bound

舉例：
Max $4x_1 + x_2 + 5x_3 + 3x_4$
$x_1 - x_2 - x_3 + 3x_4 \le 1$
$5x_1 + x_2 + 3x_3 + 8x_4 \le 55$
$-x_1 + 2x_2 + 3x_3 - 5x_4 \le 3$
隨意選擇倍數 $y_i$，只要確保係數乘上倍數比 Object Function 的係數還要大即可，例如選擇讓 $y_1 = 0, y_2 = \frac{5}{3}, y_3 = 0$，即 $\frac{5}{3}(5x_1 + x_2 + 3x_3 + 8x_4) = \frac{25}{3}x_1 + \frac{5}{3}x_2 + 5x_3 + \frac{40}{3}x_4$，會發現每個係數都比 Object Function 都還要大，又因為 $\frac{5}{3}55 = \frac{275}{3}$，因此可得知 Object Function 必定比 $\frac{275}{3}$ 還要小

### Weak Daulity Property
x 向量是 Primal Form 的"任意" Feasible Solution，c 向量是 Object Function 的係數，b 向量是 Functional Constraint 等號右邊的資源數量，y 向量是 Duality Form 的"任意" Feasible Solution，則 $c^Tx\le b^Ty$，也就是說 Primal Form 的可行解套到 Object Function 的值必定小於 Dual Form 的可行解套到 Object Function 值

證明：$\sum_{j=1}^nc_jx_j \le \sum_{j=1}^n(\sum_{i=1}^m a_{ij}y_i)x_j = \sum_{i=1}^m(\sum_{j=1}^n a_{ij}x_j)y_i \le \sum_{i=1}^mb_iy_i$, m = # of column component, n = # of row component

推論：如果 Primal 是 Feasible 且 Unbounded，則 Dual Form 的解不存在

### Strong Duality Property
如果 x 是 Primal Form 的最佳解，y 是 Dual Form 的最佳解，if and only if $Z=c^Tx = y^Tb=W$

推論：如果 x 不是 Primal Form 的最佳解，y 也不是 Dual Form 的最佳解，可得知 $c^Tx \neq y^Tb$，則再結合 Weak Duality Property，可得知 x, y 都不是最佳解時 $c^Tx \lt y^Tb$，沒有等號！

### Complementary Solution Property
在 Simplex 的每個 Iteration 中找到 Primal 的一個可行解的同時，可定義出 Dual 的一個互補解 $y_c$ 使得 $cx = y_cb$（註：這裡只說 $y_c$ 是一個解，但不一定是可行解！必須要一直 Iteration 直到達到最佳，此時 $y_c$ 才會是可行解，其他狀況下則都是不可行解，這就是 Complementary "Optimal" Solution Property）

那這個 $y_c$ 的值是怎麼定義的，才能使 $y_cb = cx$ 呢？其實就是 Object Function 中 Slack Variable 的係數，例題如下：Primal Form 還沒到達最佳時，所對應的 Complmentary Solution $y_c$ 確實乘上 b 都等於 Z，且為 Infeasible 的，直到最佳解才 Feasible

例題：
- 第一個 Iteration：0 * 4 + 0 * 12 + 0 * 18 = 0
- 第二個 Iteration：0 * 4 + 5/2 * 12 + 0 * 18 = 30
- 第三個 Iteration：0 * 4 + 3/2 * 12 + 1 * 18 = 36

註：Weak Duality 中定義的 y 是指 Feasible y，這邊定理定義的 $y_c$ 是指 $c_BB^{-1}$，能夠使 $y_cb=W$，兩個定理的定義的 $y, y_c$ 意義不一樣，勿混淆

這條定理，將任意 $x$ 解定義出一個 $y_c$ 使得 $Z=cx=y_cb=W$，如果此時又正好 $x$ 到達最佳，會因為 Strong Duality($Z=cx=yb=W$ 時，對應的解且可行)使得 $Z=cx=yb=W=y_cb$，因此 $x$ 最佳時，if and only if $y_c$ 才可行，反著說 $y_c$ 可行時，也就代表 $x$ 到達最佳

而如果 $x$ 不是最佳解，但是可行的，依據 Strong Duality Property 的額外推論，可知 $x$ 非最佳時，"可行的 $y$"必定使得 $cx < yb$，但這條定理定義出的 $y_c$ 是保證 $Z=cx=y_cb=W$，顯然 $x$ 不是最佳解時對應的 $y_c$ 就是不可行的

另一種解釋方法是：根據 Simplex Method 那章，可得到每次 Iteration 後，A I 視角下，原本 $c$ 都會變成 $yA-c$(不同作法可能會是 $c-yA$)，回想 Dual Form，Functional Constraint 不就正好是 $yA\ge c$ 嗎，為每個 Functional Constraint 各自引入 Surplus $s$ 以後就是 $yA-s=c$，最後就能推得 $s=yA-c$，也就是說 Origin Variable 的係數經過 Iteration 後運算的結果，就是對應 Dual Form Surplus 的解

如果 $x$ 未達最佳解時，就代表一定會有一個 $c_BB^{-1}N-c_N$ 一定有個值是負的（也可以說 $c_N-c_BB^{-1}N$一定有個值是正的），這個負的值可能出現在 Origin Variable 或 Slack Variable 的係數之中

如果出現在 Origin Variable 之中，就代表 $yA-c$ 有值是負的，也代表有 Surplus 的值是負的，但這就代表對應的 $y$ 違反 Dual Functional Constraint，不可行
如果出現在 Slack Variable 之中，就代表 $c_BB^{-1}$ 小於 0，違反 Dual Non Negative Constraint 也不可行
因此可證明 x 未達最佳時，Complementary Solution 必定不可行

反之，如果 $x$ 達最佳解時，則 $yA-c$ 以及 $y$ 必定都大於 0，也就表示 Complementary Solution 可行，根據 Strong Duality，x 可行、y 可行的話，就代表是最佳解

### Complementary Basic Solution Property
已經知道 Primal 中一個 Iteration 的全貌，這之中包含了各 Slack Variable 的值，這個 Slack Variable 是為了把不等式小於等於少的部分補足，而對應 Dual 則有 Surplus Variable 是為了把大於等於多的部分扣除

那麼如何得到 Dual Form 的 Surplus 的值？即為 $yA-c$，也就是原本 Primal 中 Origin Variable（即不是 Slack Variable 的部分）的係數

Simplex Method 中每個 Iteration 都是一個 Basic Feasible Solution x，這之中可拆成兩個：Slack Variable 的"係數"以及 Origin Variable 的"係數"，各自對應的 Dual 的變數 $y$ 的值以及其 Surplus 的值 $c_BB^{-1}A = yA-c$

### How to get Complementary Basic Solution's Surplus Value
- Dual Origin Variables' Value：Iteration 算完以後，Slack Variable 的係數
- Surplus Variables' Value：Iteration 算完以後，Primal Origin Variable 的係數
- Primal Origin Variables's Value：Iteration 算完以後，Surplus Variable 的係數
- Slack Variables：Iteration 算完以後，Dual Origin Variable 的係數

### Complementary Slackness Property
- Primal 中的 Basic Variable 在 Dual 中必定是 Non Basic Variable
- Primal 中的 Non Basic Variable 在 Dual 中必定是 Basic Variable

推論：
- 如果 Origin Variable > 0，也就是說 Origin Variable 為 Basic 時，Origin Variable 會對應 Surplus，則 Surplus 為 Non Basic Variable，因此為 0，也就是說對應的 Constraint 是等號
- 如果 Primal 中 Constraint 是小於，則對應 Slack Variable > 0，也就是說 Slack Variable 為 Basic，Slack Variable 會對應 Dual Variable，則 Dual Variable 為 Non Basic Variable，因此為 0

### Convert From Primal Form to Dual Form
公式解：
註：轉換時 Object Function 的常數保留，並且 Min 轉 Max，Max 轉 Min，Constraint 不等式符號對應到 Variable，並且要變號，Variable 不等式符號對應到 Constraint，並且不要變號
例題：

### Slack Variable and Surplus Variable
Standard Primal Form 中多產生出的變數叫做 Slack Variable，代表"少的要補足"，用在小於等於，轉成 Dual Form 以後多產出的變數叫做 Surplus Variable，代表"多個要扣除"，兩種都是大於等於 0，但一個前面接的是正號，代表補足，一個前面接的是負號，代表扣除，兩者如果大於 0，都代表有符合 Constraint，等於 0 代表貼著 Constraint，小於 0 都代表不符合 Constraint

### Symmetry property
Primal Form 做一次 Dual 就會變成 Dual Form，Dual Form 再做一次 Dual 就變回 Primal Form

### Duality Theorem
| | Primal Optimal | Primal Infeasible | Primal Unbounded |
| ------- | -------- | -------- | -------- |
| Dual Optimal | V | | |
| Dual Infeasible ||V|V|
| Dual Unbounded ||V||

- 如果 Primal 和 Dual 其中一個是有最大可行解（Bounded），那麼另一個必定也是
- 如果 Primal 和 Dual 其中一個是 Infeasible，那麼另一個可能是 Unbounded 也可能是 Infeasible
- 如果 Primal 和 Dual 其中一個是 Unbounded，那麼另一個必定是 Infeasible

### Application of Duality
第一種應用：Simplex 的效率主要受到限制式數量影響，因此只要限制式變少，就可以加快速度，而如果恰好變數很少，那麼轉成 Dual Form 以後就變成是限制式少，那麼只需要在 Dual 求得最佳解，就可以利用 Complementary Solution Property 反向求得 $x$ 的值，正好等於 Surplus 的值

第二種應用：用於評估一個解是否是最佳解，只要找出互補解是否可行

### Economic Interpretation of Duality
符號在 Primal 中的意義：
- $x$：各生產產品的數量
- $c$：各生產產品的售出價格
- $b$：公司持有的各生產資源的總量
- $a$：矩陣 A 中的各元素代表各生產產品所需的各種生產資源數量
- $Z$：總收益

解讀 Dual's Object Function：假設手頭上有許多資源，數量為 $b_i$，並且不拿去生產，而是售出資源，售出價為 $y_i$，則總收到的租金為 $W:=\sum b_iy_i$，也就是說 W 代表資源市場能夠得到的收入，變數是資源的售出價格

解讀 Dual's Functional Constraint：假設某商品 $x_i$ 減產一單位，就代表減少了對應的收入 $c_i$，但卻能夠省下其對應的各種資源數量（對應矩陣中的 Column），但這些資源是可以售出的，那麼得到的金額為 $a\cdot y$，節省的資源數量對應 $a_i$，節省的資源價格對應 $y_i$，而甚麼時候會有減產而轉為售出資源？答案顯然就是商品 $c$ 比 $a\cdot y$ 低的時候，這就對應各個 Dual's Functional Constraint，也就是說，Dual 中的可行區域內，代表"某個 y 定價下，任意商品都不值得生產，應轉為販售資源"

另外，Dual's Object Function 商人會希望最大，但這沒有意義，因為顯然資源售出價越高越好，這樣收益就無窮大，沒有提供任何資訊，因此實際上我們想知道的問題是：怎麼樣的資源售出價格組合 $y$，會是商家"起心動念從賣商品換成賣資源"的瞬間，因為這才會是有意義的問題，商人可以在 c, b 固定為前提（常數）的情況下去觀察 y 市場的變動價格（變數），來決定以何種方式獲利，賣商品，又或是賣資源，當所有資源的價格都變很高時，就代表進入到 Dual，也就轉換了一個市場

假設賣飲料，10 元，杯子 1 元，有 10 個，原料 4 元，有 10 個，一個杯子一個原料可以產一杯飲料，那麼預估最大值 Z 就是 100，但沒想到原料價格驟變，突然原料變成 9 元，結果我直接賣原料，也能達到同樣的收入了，如果原料漲到 19 元，我把手頭上的資源都賣光，總收入就達 200 元，比原本只賣 100 元還高（c, b, A 不變）

另外，某 x 對應的 Complementary Solution，其實就是維持同樣收入的情況下，要放棄當下生產商品轉為販售資源，那麼 y 應該至少要是怎麼樣的價格，也可以說當資源在現實世界如果價格比 y 低，那就該果斷地買入該資源

### Application of Duality
第一種應用：Simplex Method 的效率嚴重受到 Constraint 數量的影響，但不太受 Variable 數量的影響，因此當 Constraint 的數量很多時就可以將 Primal 轉成 Dual，如此 Constraint 的數量與 Variable 數量的就交換了，然後求出 Dual 直到 Optima，然後利用 Complementary Slackness，y 對應的係數就能回推 Primal 的解

1. 列出 Primal
2. 轉成 Duality
3. 求解 Duality 到 Optimal
4. 利用 Duality 最佳解時對應的係數反向求 Primal 的解

第二種應用：檢查當前 Iteration 是否為最佳解，利用 Complementary Slackness 將Primal 的 Slack Variable 係數轉成 Dual y 的解，檢查是否符合所有的 Duality Constraint

# Dual Simplex
以下 Simplex 在 Primal 不好解，要用 Big M、Two Phase 求解：
Max$-8x_1-8x_2-9x_3$
$x_1 + x_2 + x_3 \le1$
$-2x_1 - 4x_2 - x_3 \le -8$
$x_1 - x_2 - x_3 \le -2$
$x_1, x_2, x_3\ge 0$
轉成 Dual Form 以後變成：
Min$y_1-8y_2-2y_3$
$y_1 - 2y_2 + y_3 \ge -8$
$y_1 - 4y_2 - y_3 \ge -8$
$y_1 - y_2 - y_3 \ge -9$
$y_1, y_2, y_3\ge 0$
再轉成 Standard Form：
Max$-y_1+8y_2+2y_3$
$-y_1 + 2y_2 - y_3 \le 8$
$-y_1 + 4y_2 + y_3 \le 8$
$-y_1 + y_2 + y_3 \le 9$
$y_1, y_2, y_3\ge 0$
這時候就不用 Big M、Two Phase 就可以找到起始解了，總之有時候 Primal 在原點不可行，可以轉成 Dual 看看原點是否可行，可行的話就用 Dual 轉成 Standard Form 以後再解，變的更簡單，實際上這就是 Dual Simplex

但要如何確定 Dual Simplex 在原點可行呢？首先必須要確保 Primal 是 Standard Form，並且 Object Function 係數都必須是"負"的，如此轉成 Dual 以後，再變一次 Standard Form 後才能保證原點就已經可行
註 1.：Standard Form 不代表一定原點可行，以上例題就是案例
註 2.：撇除 Functional Constraint 是等於以及 Free Variable 的情況下，都一定可以轉成 Standard Form

Dual Simplex 的演算法：
- 先把原式變成 Standard Form，必須要是 Max，且都是小於等於
- 檢查 Object Function 是否是 Max 並且係數都是負
- 找到 b 為負的 Row，以其對應的 Basic Variable，作為 Leaving Variable（對應轉成 Dual 以後找到 Row 0 係數為負的 Entering Variable）
- Leaving Row 與 Object Function 做 Minimal Test，取最大負(較靠近 0)的值（對應 Dual Form 的 Entering Column 與 b 做 Minimal Test，取最小正數）

其實 Dual Simplex 轉來轉去有時候很容易算錯，因此如果真的不想多記，用原本的 Primal(Standard Form) 轉成 Dual 再轉成 Standard Form 這種算法也無所謂

# Sensetive Analysis
為何需要 Sensetive Analysis：
1. 如果 b 改變會如何？
2. Basis 組合不變的情況下，b 中的單一資源的變動範圍為何？
3. 如果 c 改變會如何？
4. Basis 組合不變的情況下，c 中的單一商品價格的變動範圍為何？
5. 如果 A 改變會如何？
6. 如果多一個變數會如何（A 多一個 Column）
7. 如果多一個 Constraint 會如何（A 多一個 Row）

參考影片：https://www.youtube.com/watch?v=V27PlTwpxL0&list=PLj6E8qlqmkFufn5avTvkdFDcYA9cnuzcd&index=19&ab_channel=NYCUOCW

### Sensetive Analysis of b
問題一：如果 $b$ 改變會如何？
如果 $b$ 發生變化，變成 $\bar b$，那麼最終 $x$ 向量的值以及 $Z$ 值也必定會改變，但我們好奇的是 Basis 的組合會不會也產生變化，如果 Basis 組合沒有變化，那麼只要重新算 Z 值即可，如果發生變化，則要做 Dual Simplex 把不可行解重新修正回最佳解

先重新計算 Basic Variable 的值 $B^{-1}\bar b$，如果：
- $B^{-1}\bar b\gt 0$：代表 Basis 的組合仍然不變且為最佳組合，不需要重新求解，但為何能保證是最佳組合呢？因為 $b$ 改變不會影響 Non Basic Variable 的係數值，也就是說 $c_BB^{-1}N-c_N$ 沒有參數 $b$，當然不會改變，而先前已經保證 $c_BB^{-1}N-c_N$ 已經都大於零，那麼當然仍維持都大於零
- 如果 $B^{-1}\bar b\lt 0$：代表 BV 組合不再可行（因為有負號），要重新求解最佳解，但是要使用 Dual Simplex（此時 $c_BB^{-1}N-c_N$ 同樣仍都大於零），步驟如下：
1. 已知 BV 有哪些，把原題目的 $b$ 改成 $\bar b$，用那些 Basis + Revised Simplex 公式重建 Table
2. 此時不可行，但最後一階段的 Row 0 係數都為正，轉為 Dual 必定可行，因此可直接做 Dual Simplex

問題二：如何求得"單一資源" $b$ 的可變動範圍？讓該資源加上 delta 變成 $\bar b$，並且讓其 $B^{-1}\bar b\ge 0$，再反向求得 delta 的範圍


延伸問題：如果多個資源 $b$ 同時變動，如何確保 Basis 不變？無證明，使用 100% Rule
1. 利用問題二，求出各資源可上升、下降的變動範圍
2. 加總實際變化的百分比，如果不超過 100%，Basis 不變，但如果超過 100% 則"不一定"

### Sensetive Analysis of c
問題三：如果 $c$ 改變會如何？
$c$ 改變以後，解必定仍然可行，但可能就不再是最佳的 Basis 組合

可使用 $c_BB^{-1}N-c_N$ 檢查是否仍有最佳解：
- 如果其中元素都大於 0，代表 Optimal
- 如果有元素小於 0，代表未達 Optimal

已知 BV 有哪些，因此可以用 Basis + Revised Simplex 公式重建 Table，並且必定仍可行，接著繼續做 Iteration 直到最佳解即可

問題四：如何得到"單一價格" c 的變動範圍？
將要變化的 $c$ 改成 delta，然後計算 $c_BB^{-1}N-c_N \ge 0$，要注意的是變化的值可出現在 $c_B$ 或 $c_N$ 中


延伸問題：如果多個價格 $c$ 同時變動，如何確保不需要重做 Iteration？無證明，使用 100% Rule
1. 利用問題四，求出各價格可上升、下降的變動範圍
2. 加總實際變化的百分比，如果不超過 100%，已達最佳解，但如果超過 100% 則"不一定"

### Reduced Cost
指 Row 0 中，NBV 所對應的係數，代表的意義是若要採用 $x_j$，價格至少要增（成本至少要降）這麼多，cost 在這表示成本的意思，也就是說若要生產，至少要 Reduce 多少的 Cost

假設 $Z = 36-2/3 x_4 -x_5$，是最佳解，$x_4, x_5$ 都是 NBV，代表其對應的資源數都是 0，但如果 $x_4$ 增加 1，就會使得 $Z$ 降 $2/3$，因此若要打平，價格至少要增加 2/3 元

### Sensetive Analysis of A
問題五：如果 $A$ 改變會如何？
可能導致變成不可行，因此要先用檢查是否可行，先將 $A$ 變為 $\bar A$，這會導致 B、N 產生變化，接著用 $B^{-1}b$ 看是否都大於 0，否則不可行（$B^{-1}b$ 中與 N 無關，因此如果 A 改變導致 N 產生變化，則根本連測可行性都不需要了，因為必定可行）

若可行的話接著用 $c_BB^{-1}N-c_N \ge 0$　測是否最佳，如果 $c_BB^{-1}N-c_N$ 有一個小於 0，就代表尚未達最佳解
若不可行的話，如果 $c_BB^{-1}N-c_N \ge 0$ 就使用 Dual Simplex，如果 $c_BB^{-1}N-c_N \lt 0$，就使用 Two Phase/Big M 求解

### New Variable
問題六：如果新增變數會如何？
會增加一個 Column，但由於 Constraint 沒有增加，因此 Basis 數量也不會增加，因此新增的變數必定是 NBV，即變數值為 0，也因此即使新增後，也仍是可行解，但不一定是最佳解，因此使用 $c_BB^{-1}N-c_N \ge 0$ 繼續做到最佳解即可

### New Constraint
問題六：如果新增 Constraint 會如何？
會新增一個 Row，如果新增的 Constraint 是不等式，那同時也會增加一個 Column 以及 Basic Variable（對應 Slack Variable），同樣首先要先驗證否可行，接著判斷是否達最佳

將目前的解，代入 Constraint 檢查是否符合 Constraint，如果
- 符合 Constraint：代表可行，且"必定 Optimal"，不需要做 Optimal 的測試，這是因為 Constraint 只會讓可行區域越來越小，例如班上最高的人身高是 190 公分，如果多加個條件要是男生，結果最高的也確實是男生，那最高的身高必定依就是 190 公分，不會變成 195 公分
- 不符合 Constraint：將新的限制是加入 Final Table 中，並且轉成 Proper Form（Basic Variable 必須是 Pivot，上下都要是 0） 可得到新增的 Basic Variable 的值，然後正好可以做 Dual Simplex，直到可行

### Summary of Sensetive Analysis

# Transportation Problem
參考：管理數學 22
https://www.youtube.com/watch?v=EPczGLvFP-4&list=PLP1Ynr8cs97vbUjtYAMYmatqFwT08s3oD&index=23&ab_channel=CUSTCourses

一種 Linear Programming 的特殊形式，如下：
Min $c_{ij}x_{ij}$
$\sum_i x_{ij} = d_i$
$\sum_j x_{ij} = s_j$
$x_{ij}\ge 0$

也可以寫成表格：

寫成矩陣的形式如下，有三個貨品來源以及四個目的地，以及各地間的運輸成本：
如果把 Row 4,5,6,7 全部加起來，會變成 Row 係數全為 1，與 Row 1, 2, 3 的加總結果一樣，相減後可組出零向量，因此實際上不需要這麼多 Basis 變數，只要有 $m + n - 1$ 個 Functional Constraint 符合，剩下最後一個就會自動符合了，也因為前 $m$ 個 Row 加總的矩陣係數與後 $n$ 個 Row 加總的矩陣係數相等，使得 $\sum d_i = \sum s_i$ 兩者必須相等，否則會造成矛盾而無解

在其他 LP 問題上有多少 Functional Constraint 就會有多少 Basis，但在運輸問題中，實際上只有 $m + n - 1$ 個變數是獨立的，即 $m + n - 1$ 個 Basis 即可

- 有解的情況：由於要能組出僅當 $\sum d_i = \sum s_i$
- 有整數解的情況：不僅要有解，還要所有的 $d, s$ 都要是整數

以 Column 的方式來看，能夠影響 $c_{11}$ 的人只會有第一個 Row 以及第四個 Row，只有他們做 Row Operation 才有機會讓 $c_{11}$ 產生變化，其他 $c$ 同理，

且以上矩陣共有 m+n 個 Constraint，但實際上只有 m+n-1 個 BV，也就是只有 m+n-1 個 Constraint 是獨立的，這是因為雖然有 m+n 個 Constraint，但由於 supply 的加總等於 demand 的加總，因此只要滿足 m+n+1 個 Constraint，那麼剩下最後一個 Constraint 可以由其他 Constraint 線性組合而成，因此自然會滿足，所以有一個 Constraint 是無用的

(補)最後結果為 $c_{ij}-s_i-d_j$
通式：
對以上矩陣做 Row Operation，選出一些 BV，然後其他非 BV 對應的係數 C 必須要是 0

### Formulation of Transportation Problem
其他例題，可以利用增加 Dummy Variable 的技巧，把看起來不像是運輸問題的題目轉成運輸問題：
https://www.youtube.com/watch?v=yK7HH2QoazI&t=670s&ab_channel=NYCUOCW

### Presentation of Transportation Problem
可以以此種表格表達運輸問題，左上角代表 Cost，最右邊 Column 代表供給，最底下 Row 代表供給需求，範例：

### North-West Corner Rule
西北角法，一種解 Transportation 的方式，不保證是最佳解，而包含退化解後確實剛好有 $m+n-1$ 個值，缺點是很笨，如果成本中有 M 的話，會直接被選到，因為這個做法根本完全不會管表格中的成本項：
https://www.youtube.com/watch?v=2BnaS3bjI-c&list=PLP1Ynr8cs97vbUjtYAMYmatqFwT08s3oD&index=24&ab_channel=CUSTCourses

### Minimal Cost Method
最小成本法，西北角法的優化，改成從最小的開始，通常來說會比西北角法成本低（但也不一定），好處是會比較有意的避免選到 M，同樣不保證最佳解：
https://www.youtube.com/watch?v=at2Iqh3vJEQ&list=PL3AR9gajU1VXdA-FIgplUHk2d3VuQ2toQ&index=5&ab_channel=CUSTCourses

特例：以下案例最小成本法比西北角法還糟

### Vogel's Method
Vogel's Method 同樣不保證最佳解：
https://youtu.be/AhNemzPRXYA?si=_3Grnbt9TVGz5kyR&t=721

### 求最佳解
與 LP 一樣，要從最起始解開始，一步一步迭代得到最佳解，那麼起始解要如何決定？其實用西北角法以及 Vogel 法就可以得到起始解，只有 (m+n-1) 個為 BV，剩下都是 NBV，雖然還不是最佳解，但可以從該解開始優化迭代

# Assignment Problem
範例：https://www.youtube.com/watch?v=GXaHCBNJQzc&list=PLj6E8qlqmkFufn5avTvkdFDcYA9cnuzcd&index=27

指派問題是運輸問題的特例，例題：有 A, B, C, D 四個人，要承接四項工作，每個人對不同的工作都有不同的價格，如下圖，每條邊都有不同的權重，每個人都要分到工作，每個工作都要被分到，一個人只被分到一個工作，完全就是一對一，因此工作與人數數量要一致，可以直接用運輸問題的解法，但因為問題更小，有更好的演算法，且同樣也能畫成 Table

對應圖：

運輸問題　Table　圖：

形式如下：
Min $c_{ij}x_{ij}$
$\sum_i x_{ij} = 1$
$\sum_j x_{ij} = 1$
$x_{ij}\ge 0$
$i = j$
原本 $\sum_i x_{ij} = s_i, \sum_j x_{ij} = d_j$，現在改成 $\sum_i x_{ij} = 1, \sum_j x_{ij} = 1$，代表一個工作只被分到一個人，一個人只分到一個工作，而變數 $x_{ij}$ 必定為 0 或 1，因為如果超過 1 就不符合 Constraint，0, 1 代表是否邊是否被連上，有的話就是 1，否則為 0

指派問題是一種運輸問題，因此必定有 $m + n - 1$ 個 BV，例如四個工作分配給四個人，就會有 4+4-1，共 7 個 BV，但由於有一個工作只會分配給一個人，因此做多只有四個 1，因此 7 個 BV 中必定只有三個為 1，其他皆為 0，是 Degenerate Form

### Hungarian Method
在指派問題中的每一個 Row/Column 可以同時加/減一個常數，"Optimal Solution" 不會有任何改變，這個操作等同於就是把指派問題畫成 LP 的矩陣以後，不斷對 Row 0 做 Operation，讓 Row 0 不斷地產生 0，並且找到

https://www.youtube.com/watch?v=ipK_5LxjlSw&list=PLj6E8qlqmkFufn5avTvkdFDcYA9cnuzcd&index=27

# Network
最常見的幾個問題
- 最短路徑：從起點開始到各個地方，最短的路徑
- 最小生成樹：拉電話線，要摸到每個節點，各點間的拉線有花費，如何最小化該成本
- 最大流量問題：水管從源頭到終點，有各種路徑，問最終的最大流量
- 最小成本流問題：從至少一個工廠到至少一個倉庫，運輸許多貨物，之間有各線路，問最小的成本
名詞定義：
- Node（Vertex）
- Arc（Edge, Link, Branch）
- 有時候 Undirected Arc 會用 Link 表示
- Path：連接兩 Node 一連串有順序的 Arcs/Nodes
- Direct Path：Path 不違反方向性
- Undirect Path：Path 可違反方向性（但不見得一定要違反，Direct Path 屬於一種 Undirect Path）
- Cycle：起點與終點相同的 Path
- Connected：兩 Node 間有 Undirect Path 連接
- Tree：不含 Cycle 且連結"部分"的 Node
- Spanning Tree：不含 Cycle 且連結"所有"的 Node
- Node 的分類：
- Supply Nodes：流出大於流入
- Demand Nodes：流入大於流出
- Transhipment Nodes：流入等於流出
範例：
- A->B->C->E 是 Direct Path，B->C->A->D 是 Undirect Path

### Bellman-Ford Algorithm

### Floyd-Warshall Algorithm
找任意"兩個點之間的最短路徑"，與 Dijkstra 演算法的差異是，該算法是求解多源最短路徑
https://medium.com/@chacha0519/%E6%BC%94%E7%AE%97%E6%B3%95-floyd-warshall-668da87d91e2

### 待補充
- 最大流量只能用於 DAG

最短路徑、最小生成樹很簡單，最難的是最大流量問題：https://www.youtube.com/watch?v=K93epwBp_ZE&list=PLj6E8qlqmkFufn5avTvkdFDcYA9cnuzcd&index=28&ab_channel=NYCUOCW
37:00 開始，把有向圖變成每條邊都雙向的
如何找 Augemented Path：簡單來說就是暴力展開，從原點開始廣度/深度搜尋，只要 Residual 為正，就遞迴地到下一個節點找

### Min Cost Flow Problem
工廠會生產產品，並且將物資送到倉庫，問：從至少一個工廠（Source）到至少一個倉庫（Destination）運輸貨物，之間有各線路，並且各路線都有成本，已知各工廠產出多少產品，已知倉庫需要儲存多少產品，問如何以最小的成本將這些產出的產品送到倉庫，數學形式如下：
- Min$\sum_i\sum_j c_{ij}x_{ij}$ 最小花費成本，$x_{ij}$ 代表從 $i$ 流到 $j$ 的流量大小
- $\sum_j x_{ij} - \sum_j x_{ji} = b_i$，$\sum_j x_{ij}$ 代表流出，$\sum_j x_{ji}$ 代表流入，$b_i$ 代表淨流量，$b_i$ 如果大於 0 代表 Source，等於 0 代表 Transhipment Nodes，即路過的中間點，小於 0 代表 Destination
- $0\le x_{ij}\le u_{ij}$ 代表從 $i$ 流到 $j$ 的流量大小的 Upper Bound，表示該線路最多的極限流量

判斷是否可行且是否為整數：
- 可行解：必須要 $\sum b_i=0$ 才有可行解，代表從工廠出去的產品數到倉庫接到的產品數加總正負相抵，最後為 0
- 可行解並且為整數：必須要 $b_i, u_i$ 皆為整數，$x_{ij}$ 才會為整數解

可用 Network Simplex 解

### Bipartite Graph
在圖論中，也有與指派問題、運輸問題類似的問題，叫做二部圖，例如：把五隻狗分給五個人，雖然不是每個人都一定要分到，但最好盡可能地多，而邊中間沒有權重，權重就當成 1
二部圖也可以是有權重的，例如同樣把五隻狗盡可能分給五個人，且引入滿意度，滿意度越高越好：
當然二部圖也可以有求最小的類型，這就與指派、運輸問題相當類似了

### Review Hungarian Method

### PERT/CPM
參考影片：https://www.youtube.com/watch?v=AVEla5fLK14&list=PLj6E8qlqmkFufn5avTvkdFDcYA9cnuzcd&index=29&ab_channel=NYCUOCW
- Program Evaluation and Review Technique PERT 計畫評核術
- CPM：Critical Path Method 關鍵路徑法

使用此方法前，要先畫出 Project Network，也就是專案的時序圖，每個過程都有時間權重
從起始到結束共有六種走法，並且可得到六種走法的時間加總，其中時間最長的路徑叫做 Critical Path，代表完成該工程需要最久的時間，因此 Critical Path 的時長又稱作 Duration of Project，如果該時間變長了，那麼工程就會延期，而不是 Critical Path 的時程即使稍微延宕，也可能不會延期，如果要讓工程時間縮短，最首要的當然是先加速 Critical Path 的速度

但其中的每個流程都有壓縮的極限，例如蓋房子砌牆，雖然建好灌模的速度可以透過人力加快，但水泥要乾卻沒辦法更快，因此雖然提高付出的金錢可以加速，但到一個極限以後花錢也沒用了，圖如下（假設花費是線性）：
能加速到極限的時間就是 Crash Point，到達該點要花費的錢就是 Crash Cost，因此可計算從 Normal 加速到 Crash Point 平均單位所需要花的時間，即斜率乘上 -1，該值實務上可經過調查，得到每個階段加速需要的花費

例如一項任務：
- 正常 8 周，43 萬元
- 極限 6 周，49 萬元
- Crash Cost Per Week：(49-43)/2=三萬元

如何加速工程並且評估成本：
- 關注 Critical Path，壓縮最低 Crash Cost Per Week 的 Activity，每次壓縮一單位時間
- 更新所有 Path 的時長
有可能 Critical Path 時長被壓縮後就不再是 Critical Path，因此要更新所有 Path 的時長，但這些方法都太慢了，實際上我們可以直接轉成一個 LP 求解：
- $c_j$：Crash Cost Per Week
- $x_j$：Activity j 的壓縮單位時數
- $y_j$：Activity j 的開始時間
- $y_f$：工程結束時間

# Integer Programming
### Cutting Stock Problem
寬度為 10 的紙捲，切成 20 份寬度 5 和 100 份寬度 3 的紙捲，最少共要幾捲大紙捲

### Bin Packing Problem
參考：https://www.youtube.com/watch?v=R76aAh_li50&ab_channel=ComputationalThinking
Cutting Stock Problem 中，各種小紙捲的所需數量可以是很多個，但 Bin Packing Problem 則是限縮的，每種切法的需求數量最多只能是 1 個，例如我想要切成 1, 2, 3, 4, 5, 6 這幾種長度各 1 個

### Lower Bound
以上問題為 Integer Programming，但在求解前，我們想先知道 Lower Bound 為何

假設每個大紙捲切完以後的殘料能夠再合併成大紙捲，就能確保資源完全使用，那麼這樣的情況下最少需要 (5 / 10) * 20 + (3 / 10) * 100 = 40 捲，公式實際上為各種切法的使用率加總起來，令為 W，假設最佳整數解為 $C^*$，那麼 $W \le C^*$

### Next Fit Algorithm and First Fit Algorithm、Best Fit Algorithm
https://www.youtube.com/watch?v=qbuMPi44bVQ&ab_channel=Dr.HasanJamal

Next Fit：最多不會超過 2 * Optimal
First Fit：最多不會超過 1.7 * Optimal
Best Fit Algorithm

# Markov Chain
參考影片：https://www.youtube.com/watch?v=thoG5DDjj_A&list=PLj6E8qlqmkFvyhyY3oCLq2OBIIew52c0b&index=16

常用符號：$x_1, x_2...x_n$ 代表離散的時間點下的狀態機率分布

Markov Process 需要滿足以下性質，滿足則稱做 Markov Process：
- 狀態空間：只在有限狀態空間中變化
- 無記憶性：$P(x_{t+1} = j|x_t = i)=P(x_{t+1} = j|x_t = i_0,x_{t-1} = i_{1},...,x_{t-n} = i_{n})$ 下一次發生甚麼事件僅與當前事件有關，與更之前的狀態都無關
- 轉移矩陣的 Row 加總為 1，從狀態空間中的一點會到另一點，這機率是 100% 的

註：本章以 Row 視角看，即初始狀態 $x$ 以 Row Vector 表示，右乘轉移矩陣 $P$ 代表做一次 Transition，而非以 Column Vector 的方式（$Px$），但可自行互相轉換

Stationary Transition Probability：兩相鄰時間轉移的機率固定，不會有改變，也就是說任兩狀態 $i,j$ 之間的轉移機率都會相等，即：$P(x_{1} = j|x_0 = i)=P(x_{2} = j|x_1 = i)=P(x_{3} = j|x_2 = i)...=P(x_{n} = j|x_{n-1} = i)$

多個轉移矩陣相乘的意義：矩陣 $P^{(n)}_{ij}$ 的元素，代表經過 $n$ 輪時間從狀態 $i$ 到 $j$ 的機率，即 $P(x_{t+n} = j|x_{t} = i)$，如果只過一個時間點，會直接寫成 $P_{ij}$

Chapman–Kolmogorov Equation：$P^{(n)}_{ij}=P^{(m)}_{ik}P^{(n-m)}_{kj}$，概念類似於排列組合的加法原理，從 $i$ 到狀態 $j$，第一輪可以先分成 $k$ 種（所有狀態）路線，接著再下一輪合併回一個狀態，接著擴展到多輪，則狀態 $i$ 到 $j$ 的所有機率：$P^2_{ij}=\sum_kP^1_{ik}P^1_{kj}, P^3_{ij}=\sum_kP^1_{ik}P^2_{kj}, P^4_{ij}=\sum_kP^1_{ik}P^3_{kj}$

Steady-State Probability：矩陣每一列都相同，代表起始狀態無論為何($i$ 不論是 $1, 2, 3...$)，他們在很多輪時間後，到達任意 $j$ 狀態的機率都相同，如下圖，每個 Row 都相等

Unconditional State Probability：Unconditional 意思是，無論起始狀態為何，問時間點 $n$ 下狀態為 $j$ 的機率為多少，實際上等於每種起始狀態乘上 $P^n$ 到 $j$ 狀態機率的加總

### Classfication of State
- 如果 $P^{(n)}_{ij}\gt0$，代表一段 $n$ 時間下 $i$ 有機會到 $j$，稱作 Accessible，可用 $i\rightarrow j$ 表示
- 如果 $i$ 到 $j$, $j$ 到 $i$ 都是 Accessible，則稱作 Communicate，可用 $i\leftrightarrow j$ 表示，若兩個其中一個不滿足就不是 Communicate

我們可以對狀態空間中的每個 State 做分類，分成一到多個 Class，每一類中之 State 必須彼此為 Communicate，例如說我可以把 20 個狀態分成 4, 16 兩組 Class，這意味者 4 這組裡面彼此都 Communicate，16 組彼此間也都 Communicate
- 如果只有一個 Class，代表所有狀態空間中的狀態彼此之間都是 Communicate，稱作 Irreducible

### Transient State, Recurrent State And Absorbing State
- Transient State：一旦離開該狀態後，就"有可能"無法再回來該狀態，這就是 Transient State：
賭博的案例：假設有一塊錢，有 50% 的機率可以多贏一元，50% 的機率就賠掉一元，如果到 0 就認賠殺出，如果到 3 就收工回家，以此例來說，到狀態 2 以後，有 50% 機率因為會到 3 而有可能回不來 2，只要有可能就算！因此 State 2 為 Transient State，State 1 也是，因為可能到 0 就認賠殺出無法回到 1
- Recurrent State：指一狀態必定可以繞回來，如果不是 Transient State 則必為 Recurrent State，如果 Markov Chain 持續無限次，則 Recurrent State 必定也會經過無限次
- Absorbing State：進到該 State 以後就永遠出不去了，例如賭博的案例中的 State 0 以及 3，以 Row 來看就是只有"到自己"的那一個元素為 1，其他皆為 0
- 已知一 State 為 Absorbing State/Transient，則如果有連到該 State 也必定都是 Transient State，因此 Absobing、Transient 可以想像成有 Transient 性質的傳染性
- Recurrent State is a class property：如果一個 Class 內有一個 Recurrent State，則整個 Class 都會是 Recurrent State
- Finite State Markov Chain 必定不可能所有狀態都是 Transient State，否則走很多很多輪以後狀態會無處可去，因此如果我的狀態空間 + Markov Chain 是 Irreducible，則這些 State 必定都是 Recurrent State，不可能都是 Transient State，因為必須整體至少要有一個 Recurrent State，案例：
- Period：指一狀態回到同一個狀態只"可能"會出現在固定特定的週期，如 t,2t,3t,4t...，賭博的例子來說，從時間 0、State 2 開始，則下一次回到 State 2，只可能出現在時間 2, 4, 6, 8...，如果 t = 1，那就是沒有週期（Aperiodic）

Other Example：https://www.quora.com/What-is-the-difference-between-a-recurrent-state-and-a-transient-state-in-a-Markov-Chain

- Ergodic：指一個 State 同時是 Recurrent State、Aperiodic

### Steady-State Probability
- 如何知道會達穩態？必須是 Irreducible（即 Recurrent 且只有 1 Class）且 Ergodic（沒有週期）
- 如何求出穩態時各狀態的機率？$\lim_{n->\infty}P^{(n)}_{ij}=\pi_{j}$，也會寫成 $\pi_j$，代表到穩定態時，各狀態 $j$ 的值機率為何

### Steady-State Equation
M 個變數，M + 1 個方程式，已知有唯一解，則有個 Equation 是多餘的，但不可能是 $\sum \pi = 1$，因為如果真如此，那麼 $\pi_1= 0, \pi_2= 0, \pi_3 = 0...$ 也會是一個解，但這解顯然不合理

範例：

### Expected Average
https://youtu.be/1Y0LPgiFHkg?si=jF1h2pHExtXgphXj&t=1915

### First Passage Time
指從 State $i$ 開始 Markov，經過 $n$ 個 step 後第一次到達 State $j$ 的機率，而實際發生的時間長度則稱做 First Passage Time如果是自己到自己，即 $i$ 出發又從 $i$ 回來的時間，則稱做 Recurrent Time

範例：$x_1 = 3, x_2=2, x_3=1,x_4=0,x_5=3,x_6=1$
- 從 State 3 開始（n=1）到第一次到達 State 1（n=3）的 First Passage Time 為 2
- State 3 自己的 Recurrent Time 為 4

如果是問 n 輪下從 i 到 j First Passage 的機率，通常會用符號 $f_{ij}^{(n)}$ 表示，$f$ 代表 first，且
- $f_{ij}^{(1)} = p_{ij}^{(1)}$：第一輪就到目標狀態，都必定是第一次，因此兩者相等

(上圖彷彿就像跑一個多層的 for 迴圈，並且深度為 n 層，如果 i 不等於 j 就不繼續追下去)

$f_{ij}^{(1)}+f_{ij}^{(2)}...f_{ij}^{(\infty)}\le 1$，這行代表一直嘗試跑到無限輪，問每輪第一次碰到的機率加總，結果是不會保證等於 1，而是小於等於 1

直觀地想像，在全連通的情況下（像神經網路），想像水從 i 分支流出，只要一碰到 j 就把那些碰到 j 的水取走，接著讓剩下的水往下一輪流，如此無限輪，最後就能蒐集到所有的水

當上式小於 1 的時候，代表從 i 出發，有機會會永遠到不了 j，例如 i 到 j 中，狀態中有一個 Absorbing State，一但掉進去，就相當於流量被吸過去，永遠無法再到 j，因此小於 1

$\mu_{ij}$：從 $i$ 出發，第一次到 $j$ 所需時間 $n$ 的期望值，例如從出生到第一次吸毒所需經過的年數，如果 $f_{ij}^{(1)}+f_{ij}^{(2)}...f_{ij}^{(\infty)}\lt 1$，則 $\mu_{ij} = \infty$，因為如果中間有落到無法再到達 j 的狀態（例如 Absorbing State），則時間就被拉長到無限了，雖然機率很小，但小機率乘無限大依舊是無限大

如果是可以收斂的，則值為 $\pi_{ij}=\sum_{n=1}^\infty nf^{(n)}_{ij}$，但另一種算法為 $\pi_{ij}=1+\sum_{i\neq j}^\infty P_{ik}\mu_{kj}$，推導：


可以矩陣表示、求解 $\mu_{ij}$：

如果是算 $\mu_{ii}$，也就是自己的 Expected First Recurrent Time，則必定等於 $\frac{1}{\pi_i}$，$\pi_i$ 表示穩態時，落到 State $i$ 的機率

### Probability of Absorbing
State $k$ 是 Absorb State，問從 $i$ 第一次到 $k$ 的機率是多少，不會有第二次從 $i$ 到 $k$ 了，因為狀態會被 $k$ 吸走永遠出不去，一樣用 $f_{ik}$ 表示，因此 $f_{kk}=1$，而如果 $i$ 為 Recurrent，為了符合 Recurrent 的定義，因此 $f_{ik}$ 必定為 0

$f_{ik}=\sum_jP_{ij}f_{jk}$

### Random Walk
案例一：醉漢走路，有機率 $p_1$ 往左走一步，也有機率 $p_2$ 往右走一步，從原點開始，問第一次到左邊五步與右邊五步的機率是多少

案例二：賭博，假設有一塊錢，有 50% 的機率可以多贏一元，50% 的機率就賠掉一元，如果到 0 就認賠殺出，如果到 3 就收工回家，以此例來說，到狀態 2 以後，有 50% 機率因為會到 3 而有可能回不來 2，只要有可能就算！因此 State 2 為 Transient State，State 1 也是，因為可能到 0 就認賠殺出無法回到 1

從 State $i$ 出發，在下一 step 不是在 $i$ 就是在 $i+1$ 或 $i-1$（這時候題目的"狀態"相鄰應該要有意義）

使用 Probability of Absorbing 求到達各個 Absorbing State 的機率，即遊戲結束的機率，同樣化成矩陣的方式求解

例題：https://youtu.be/ZD43Gq2BVqA?si=a16qYvCW0X8D57Bs&t=4860

# Queuing Theory
研究不同人流下，櫃台要開多少個，如果櫃檯開太少，那麼顧客要等很久，顧客滿意度差，如果開太多，人事成本就太高，問如何取捨？

其他案例：一急診室，有一名醫生，排隊隊伍可能很長，顧客要等很久，問如果再聘一名醫生，平均顧客等候時間會縮短多少

### Queueing Theory's Basic Structure

- Input Source（顧客產生器）的屬性：
- Size：指會排隊的人數有多少，可分為有限及無限，有限反而通常比較難解，無限的會比較簡單
- 何時到達：人們以一種機率分布進來店裡，通常用指數分布
- Balking
- Queue（排隊中的顧客）的屬性：
- Queue 的容量
- Queue Displine：指如何從隊伍中找出下一位要服務的對象，通常是先排先到 FCFS，但也有例外，例如急診室，感冒的會被放很久，但命危的會先被服務
- Service Mechanism 的屬性：
- Service Facilities：一個醫院內可以有一或多組櫃台，分別負責掛號區、看診區、領藥區
- Server：醫院內有多組區域，而每個區域還可以有一到多個服務人員
- （註：大部分情況下只需要一個 Service Facilities，例如郵局、商店等，醫院是特例）
- Serice Time：服務時間，通常也是假設指數分布

### Representation of Queuing Model
通常使用 X/X/X/X/X/X 表示一個 Queuing Model，分別代表
1. Interarrival Time 的分布：顧客到達的時間"間隔"分布（註：是指到達的"間隔"分布，而不是到達的"時間點"分布），常用 M, D, Er, G 表示
2. Service Time 的分布：服務人員服務一名顧客的時間分布，常用 M, D, Er, G 表示
3. Server 的人數：通常預設為 1
4. Queue Discipline：通常預設為 FCFS
5. 內部系統上線：即隊伍的容量，通常預設為無限
6. 外部顧客上限：即商店服務的人數，通常預設為無限

註：前三項不省，後三項有時會省略

Queue Discipline 的種類：
- First Come First Service FCFS：先進先服務
- Last Come Fist Service LCFS：後進先服務
- Service in Random Order SIRO：隨機服務

時間分布的符號：
- M：Exponential Distribution
- D：Degenerate Distribution（常數時間，例如工廠產線）
- Er：Erlang Distribution
- G：General，可以是以上的任意分布

範例：

### Common Symbol
常見的名詞、符號的定義，有許多與 Markov Chain 類似的符號定義：
- State of System：在系統中，正在排隊的人數 + 正在被服務的人物
- Queue Length：正在排隊的人數
- $N(t)$：時間點 $t$ 下系統中的人數，有時候也會用 $X(t)$ 表示，因為 Queue 中的人數與 Markov State 的概念相當
- $P_n(t)$：從時間點 $t$ 下系統中剛好人數為 $N$ 的機率，$N$ 包含在排隊的與正在被服務的人數，與 Markov Chain 中的 $P_{ij}(t)$ 概念相當，但 $i$ 固定為 $0$，因此省略
- $S$：服務人員的數目
- $\lambda_N$：系統內有 $N$ 人的時候，顧客的平均到達率（可能與 $N$ 有關，例如餐廳看到排隊的一堆人就不想排了，那麼 $\lambda_N$ 就會很低，為了簡單也可以假設到達率與 $N$ 無關，這裡多個下標 $N$ 是為了一般性，如果與 $N$ 無關可單純用 $\lambda$ 即可）
- $\frac{1}{\lambda_N}$：顧客進門的 Interarrival Time 的期望值，例如 $\lambda=3$ 表示一小時平均來 $3$ 人，則等同表示平均等 $\frac{1}{3}$ 小時
- $\mu_N$：系統內有 $N$ 人的時候，"整體系統"的服務速率(整體系統的意思是指所有服務人員的服務速率總和，若每個 Server 的服務率相同，可單純用 $\mu$ 表示，當 $n\ge s$ 系統人數比服務人數多的時候，則整體服務率 $\mu_N=s\mu$)
- $\frac{1}{\mu_N}$：Service Time 的期望值
- $\rho = \frac{\lambda}{s\mu}$：到達率除以消化率（服務率），代表系統的利用率，越高越好，假設每小時來 5 人，每小時消化 6 人，長時間來看，例如 10000 小時，總共來的人數就是 50000 人，能消化的人數就是 60000 人，顯然時間一拉長只需要看平均，使用率就是 5/6，整個系統但必須小於 1，$P_n$ 才會收斂，大於 1 則無法，而 $1-/rho$ 則是空閒率，如果 $\rho$ 越高，平均顧客排隊的時間就要越久
- Transient Condition：指在初期，系統呈不穩定的狀態，例如剛開店的麥當勞可能一次先有 20 人，但服務員只有 3 個，導致剛開店就排爆了，但過了一段時間後系統就會比較平衡，則稱做 State-Steady Condition，此時 $P_n(t)$ 就不再與 $t$ 有關，有時以 $\pi_n$ 或 $P_n$ 表示，表示到達穩態
範例：

### Little's Formula and Six Major Indicators of Queuing Model
基本假設：
- $\lambda_N=\lambda$：意思是 $\lambda$ 不會受到時間影響
- $\mu_N=\mu$：意思是 $\mu$ 不會受到時間影響
- 如果 $\lambda_N\neq\lambda$，也就是各個 Lambda 都不相等的情況下，必須改為使用加權的 $\bar \lambda$，公式為$\bar \lambda=\sum_{n=0}\lambda_nP_n$

公式：
- $L$：Queue Length，系統中人數的期望值(排隊+正在被服務的)=$\sum_{n=0}^\infty nP_n$
- $W$：Waiting Time，一名顧客從開始排隊到服務結束的平均時間=$W_q+\frac{1}{\mu}$，在平均在系統中等待的時間等於平均排隊的時間加上平均服務的時間，已知平均服務的速率為 $\mu$，因此平均服務所需的時間就是 $\frac{1}{\mu}$
- $L_q$：系統中排隊的人數的期望值(不包含被服務的)=$\sum_{n=s}^\infty(n-s)P_n$
- $W_q$：一名顧客從開始排隊到開始被服務的平均時間
- $L_s$：$\frac{\lambda}{\mu}$
- $W_s$：$\frac{1}{\mu}$，$\mu$ 代表單位時間能夠服務多少人，倒數就代表一人要服務多久

衍伸：
- $L=L_q+L_s=L_q+\frac{\lambda}{\mu}=\lambda(W_q+\frac{1}{\mu})=\lambda(W_q+W_s)=\lambda W$

假設櫃台有三個服務人員，$s=3$，每個服務人員的服務率都是相同，都是一小時五人，則如果系統人數為 3 及以上時，$\mu_3 = 3\mu=15$，表示整體系統滿載運行，不論 N 再大，效率就是 15 人，表示整體系統滿載運行，如果 $N=2, \mu_2=10$

關係式的利用：如果算出 $W$，就能算出 $L$，如果有 $W$ 就能算出 $W_q$，如果算出 $W_q$ 就能算出 $L_q$

合理性的解釋：https://youtu.be/oivoejLdi5I?si=mxgq3U8DKAubI0el&t=6455

### Special Property of Exponential Distribution
- 反直覺：指數分布實際發生了結果的值，小於期望值的一半的機率達 40%
- $U=\min\{X_1 ,X_2,... X_n\}$，$X_n$ 都服從 Exp 且期望值為 $\alpha_n$，則 $U\sim Exp(\sum \alpha_n)$，例如學校的學餐阿姨等學生光顧，有三個指數分布來源：資管系、資工系、工工系，每次有客人光顧相當於做了一次 $U=\min\{X_1 ,X_2,... X_n\}$　的實驗，總體來看，這分布會服從 $U\sim Exp(\sum \alpha_n)$
- Exponential Event 發生的時間期望值為 $\alpha$，那麼問時間 $t$ 內會發生幾次會服從 Poisson Distribution $\alpha t$

### Birth and Death Process
推導：
Rate Diagram：

以下各種 Queuing Model 都是由 Birth and Death Process + Little's Formula 推導出
### Summary of M/M/1 Model
### Summary of M/M/s Model
### Summary of M/M/1/k Model
### Summary of M/M/s/k Model

### M/G/1 and M/D/1
G 代表 General，只要知道任意服務時間分布的 Mean $\frac{1}{\mu}$ 以即 Variance $\sigma^2$，且到達率、服務時間都固定為 $\lambda,\mu$ 則
- $P_0=1-\rho$，即進去就不用排隊的機率
- $L=\rho + \frac{\rho^2+\lambda^2\sigma^2}{2(1-\rho)}$
- $L_q=\frac{\rho^2+\lambda^2\sigma^2}{2(1-\rho)}$

重要的結論：只要 Variance 為 0，就會變成 M/D/1，D 代表 Degenerate，也就是服務時間為常數時間，那麼就會變成

- $L=\rho + \frac{\rho^2}{2(1-\rho)}$
- $L_q=\frac{\rho^2}{2(1-\rho)}$

由於 $\lambda$ 固定下 $W,L,W_q,L_q$ 彼此皆為正向關係，因此 $L$ 降低，其他指標也會跟著降低，因此若要讓系統的四大指標維持比較輕鬆、負擔低的狀態，除了加快員工的服務率、減少顧客的到達率外，在維持相同的服務率下降低 Variance 也能有奇效

M/G/1 有如此漂亮的解，那麼 M/G/s 呢？很可惜目前還沒有人找到很簡單、漂亮的公式

範例驗證：將 M/G/1 變成 M/M/1
服務率為 $\mu$，因此 Service Time 的變異數為 $\frac{1}{\mu^2}$，$L_q=\frac{\rho^2+\lambda^2\sigma^2}{2(1-\rho)}=\frac{\rho^2+\rho^2}{2(1-\rho)}=\frac{\rho^2}{1-\rho}=\frac{\lambda^2}{\mu(\lambda-\mu)}$，結果一致！

### Erlang Distribution
Exponential Distribution 的 I.I.D 加總的版本，等同於柏努利分布之於二項分布，幾何分布之於超幾何分布，白話來說就是"k 名顧客到達時所花的時間"，如果加總的指數分布的平均值為 $\lambda$ 代表到達的平均時間，則 Erlang Distribution 的平均所花時間當然為 $k\lambda$

而如果 Erlang Distribution 的參數為 $\lambda_{ER}, k$ 代表，$k$ 個人到達所需平均時間，則分解成 I.I.D 的各個小 Exponential Distribution 的平均值則為 $\frac{\lambda_{ER}}{k}$

### Preemptive and Non-Preemptive
Queuing Displine 除了 FCFS 外也有分等級類型的，例如醫院急診室，如果有個高緊急的單位進來的，理所當然在 Queue 中會排得比低等級的前面，這是在隊伍的情況，但如果低等級的單位正在接受服務呢？此時又可以分為 Preemptive 以即 Non-Preemptive
- Preemptive：代表可以把還沒完成的低等級單位踢開，讓高等級單位先被服務
- Non-Preemptive：必須要等低等級單位完成以後，才能讓高等級單位被服務

### Queuing Network(Jackson Network)
在一個系統中，不見得只有一個 Queuing Facility，例如醫院，有許多單位，例如櫃台、藥單、看診區等，可以只經過部分，例如我已經有藥單，只是來店裡取藥，就只經過藥單的部分

而有些系統要經過所有的單位，例如工業生產一個產品，壓平、塑模、拋光等一堆 Pipeline

範例圖：
上圖又稱作 Jackson Network
- 有多個 Facility，用 $F_i$ 表示
- Infinite Queue Capacity
- 外部到達率為 Poisson Process
- 每個 Facility 可以有多個 Server
- 每個服務人員的 Service Time 為指數分布
- 每個顧客進入 Facility 完成服務後，會到下個 Facility 或離開系統，這樣的抉擇由 $p_{ij}$ (表示哪個 Facility 到哪個 Facility) 以即 $q_i$(這個 Facility 完成後會離開系統的機率)決定，由於完成後要馬進入下一個 Facility，要馬離開，因此 $q_i+\sum_jp_{ij}=1$

Key Idea：
- 每個 Facility 都可以視為獨立的 M/M/s，其到達率等於"外部到達率+來自其他 Facility 的到達率"
- 每個 Facility 均為 M/M/s，且 rho 小於 1 的情況下，則在 steady-state 時，每個 Facility 的 output（可能為其他 Facility 之 Input）仍等同於其原本的到達率，這句話的意思是：一個櫃台到達率為一小時 20 人，那離開率(潛在的下一階段其他人的到達率)也會是一小時 20 人

# 備忘錄
非原點可行的情況如何做 Revised Simplex：做 revised simplex 之前，一定要保證起始的 Basis 組合是可行的，這對於如果原本 Basis 並不簡單，那就要 Two Phase, Big M 求得，一旦找到可行的 Basis 組合，就可以直接啟動 Revised Simplex Method

Bellman-ford 為何可以運作：Bellman ford 其實類似廣度搜尋，強制把所有能到某個點，能走的路線都走過一次，並且如果更短就 Relax，然後遍例所有 Edge V-1 次就可以停了，因為如果是有向無負環圖，則最短路徑必定長度在 V-1 內，因為從某點走到某點，即使經過所有 V 個節點，也只能經過 v-1 個邊，如果超過，就代表中間有小環，但如果小環還能夠持續遞減，這個環必定是負環，因此此算法還可以檢測是否有負環

# 未解之謎
- 為何 Markov Chain 穩態必須要符合 Recurrent、Single Class、非週期等性質，如何證明？
- 運輸問題的最佳解求法的原理究竟是甚麼？
- 為何匈牙利法是正確的？
- 為何 Ford-Fulkerson 是正確的？