線性規劃是解決最佳化問題的有效工具，本文將其應用於最短路徑和最小集合覆寫問題。針對最短路徑，我們利用距離矩陣和流量守恆約束，建立了線性規劃模型，並探討瞭如何修改目標函式和約束條件以適應不同的變體，例如最小化距離乘積和最長路徑問題。此外，我們還展示瞭如何應用最短路徑模型來提取專案管理中的關鍵任務。對於最小集合覆寫問題，我們以供應商選擇為例，說明瞭如何使用二元變數來表示供應商的選擇，並建立目標函式和約束條件以確保所有零件需求得到滿足，同時最小化所選供應商的數量或總成本。
最短路徑問題的線性規劃模型與變體
在許多實際問題中，我們經常需要找到網路中兩個節點之間的最短路徑。傳統上，Dijkstra演算法是解決這一問題的常用方法。然而，在實際建模過程中，我們往往需要考慮除最短路徑之外的其他因素，這使得線性規劃模型成為一個更具彈性的選擇。
最短路徑問題的線性規劃模型
模型構建
考慮一個具有距離矩陣 (D) 的網路，其中 (D_{ij}) 表示節點 (i) 到節點 (j) 的距離。如果兩個節點之間沒有直接連線，則 (D_{ij} = 0)。我們的目標是找到從起始節點到終止節點的最短路徑。
def solve_model(D, start=0, end=None):
if end is None:
end = len(D) - 1
# 定義模型與變數
m = Model()
x = [[m.add_var(lb=0, ub=1 if D[i][j] != 0 else 0) for j in range(len(D))] for i in range(len(D))]
# 設定起始節點的供應量與終止節點的需求量
m.add_constr(sum(x[start][j] for j in range(len(D))) - sum(x[j][start] for j in range(len(D))) == 1)
m.add_constr(sum(x[j][end] for j in range(len(D))) - sum(x[end][j] for j in range(len(D))) == -1)
# 設定其他節點的流量守恆約束
for node in range(len(D)):
if node != start and node != end:
m.add_constr(sum(x[j][node] for j in range(len(D))) == sum(x[node][j] for j in range(len(D))))
# 設定目標函式
m.objective = minimize(sum(D[i][j] * x[i][j] for i in range(len(D)) for j in range(len(D))))
# 求解模型
rc = m.optimize()
# 處理解
Path, Cost, Cumul = [], [], [0]
node = start
while node != end:
for next_node in range(len(D)):
if x[node][next_node].x > 0.9:
Path.append(next_node)
Cost.append(D[node][next_node])
Cumul.append(Cumul[-1] + Cost[-1])
node = next_node
break
return rc, m.objective_value, Path, Cost, Cumul
內容解密：
- 模型定義：首先，我們定義了一個線性規劃模型，並為每對節點建立了一個決策變數 (x_{ij})，表示是否選擇從 (i) 到 (j) 的路徑。
- 變數範圍：變數的下界設為0，上界設為1（如果 (D_{ij} \neq 0)），否則設為0，以確保沒有直接連線的節點之間不會有流量。
- 約束條件：我們設定了起始節點的供應量為1，終止節點的需求量為1，並對其他節點施加流量守恆約束，以確保路徑的連續性。
- 目標函式：目標是最小化總距離，即所有被選擇的路徑的距離總和。
- 解的處理：求解模型後，我們根據決策變數的值構建最短路徑，並計算相關的成本和累積距離。
替代演算法與變體
為何選擇線性規劃？
雖然Dijkstra演算法是一種高效的最短路徑演算法，但在實際應用中，我們往往需要在基本最短路徑問題上新增額外的約束或條件。線性規劃模型提供了更大的彈性，可以輕鬆地加入這些額外的約束。
變體
- 最小化距離乘積：如果我們想要最小化路徑上距離的乘積，可以透過對距離取對數，將問題轉化為求和的形式，從而適用於線性規劃模型。
- 最長路徑問題：理論上，最長路徑問題可能無法透過線性規劃在所有情況下求解，但對於無環有向圖，求解最長路徑是可行的。我們可以透過修改目標函式為最大化，並對距離矩陣取負值來實作。然而，這可能導致無界解，因此需要額外的約束來避免重複節點和無限迴圈。
關鍵任務提取
利用最短路徑模型，我們可以提取專案管理中的關鍵任務。具體方法是將任務的開始和結束時間視為網路中的節點，並根據任務持續時間構建距離矩陣。然後，呼叫最短路徑模型來找出最長路徑，即關鍵路徑。
def critical_tasks(D, t):
s = set([t[i] + D[i][1] for i in range(len(t))] + [t[i] for i in range(len(t))])
n, ix, start, end, times = len(s), 0, min(s), max(s), {}
for e in s:
times[e] = ix
ix += 1
M = [[0 for _ in range(n)] for _ in range(n)]
for i in range(len(t)):
M[times[t[i]]][times[t[i] + D[i][1]]] = -D[i][1]
rc, v, Path, Cost, Cumul = solve_model(M, times[start], times[end])
T = [i for i in range(len(t)) for time in Path if times[t[i] + D[i][1]] == time]
return rc, T
內容解密：
- 構建網路節點：首先，我們根據任務的開始和結束時間建立網路中的節點集合。
- 建立距離矩陣：根據任務的持續時間，建立相應的距離矩陣，用於表示任務之間的關係。
- 呼叫最短路徑模型：利用前面定義的最短路徑模型，找出網路中的最長路徑，即專案管理中的關鍵路徑。
- 提取關鍵任務：最後，根據最長路徑上的節點，提取出對應的關鍵任務。
最短路徑樹
為了找到從一個起始節點到所有其他節點的最短路徑樹，我們可以建立一個新的模型，將起始節點的供應量設為 (n-1)，並將其他每個節點的需求量設為1。這樣，我們就可以一次性地求解出到達所有其他節點的最短路徑。
經典離散模型
本章探討的問題是整數規劃（Integer Programs, IP）的經典範例。更精確的稱呼應該是離散線性規劃（Discrete Linear Programs），因為之前討論的問題都是連續線性規劃，而「連續」的反義詞正是「離散」。不過，由於「整數規劃」的稱呼已經根深蒂固，我們將繼續沿用這個術語。這些問題的特點是具有代數線性的限制條件和線性目標函式，並且要求變數只能取整數值。
為何研究經典離散模型
所有這些問題都很簡單易懂，即使它們的建模或求解並不總是那麼簡單。我們在此討論它們，是為了強調兩個重要方面：
- 首先，許多現實生活中的問題都內嵌了一個或多個這些簡單、純粹的問題。因此，對於建模者來說，識別出這些核心問題並輕鬆地對它們進行建模是非常有益的。
- 其次，為了高效地建模許多問題，需要一些技巧。瞭解這些技巧，並在不同的情況下識別出它們可以被應用的場景，是優秀建模者的標誌。
整數模型的特點
整數模型的關鍵在於要求部分或全部變數必須是整數。與前一章討論的偽整數模型不同，這些模型的結構並不保證變數的整數性質，因此需要特別的處理。
程式碼範例：最短路徑樹模型
def solve_tree_model(D, Start=None):
s, n = newSolver('Shortest paths tree problem'), len(D)
Start = 0 if Start is None else Start
G = [[s.NumVar(0, 0 if D[i][j] is None else min(n, D[i][j]), "")
for j in range(n)] for i in range(n)]
for i in range(n):
if i == Start:
s.Add(n-1 == sum(G[Start][j] for j in range(n)))
s.Add(0 == sum(G[j][Start] for j in range(n)))
else:
s.Add(sum(G[j][i] for j in range(n)) - sum(G[i][j] for j in range(n)) == 1)
s.Minimize(s.Sum(G[i][j]*(0 if D[i][j] is None else D[i][j])
for i in range(n) for j in range(n)))
rc = s.Solve()
Tree = [[i, j, D[i][j]] for i in range(n) for j in range(n) if SolVal(G[i][j]) > 0]
return rc, ObjVal(s), Tree
內容解密：
- 定義模型與變數：首先，定義了一個名為
solve_tree_model的函式，它接受距離矩陣D和起點Start作為引數。使用newSolver建立了一個新的求解器例項，並根據D的大小確定了節點數量n。預設起點為0，除非另有指定。 - 建立變數矩陣G：透過列表推導式建立了一個二維列表
G，其中每個元素都是一個由s.NumVar建立的變數，代表從節點i到節點j的流量。變數的取值範圍根據D[i][j]是否為None以及其值進行了限制。 - 新增限制條件：遍歷所有節點，對於起點，增加了兩個限制條件：出度為
n-1，入度為0。對於其他節點，增加了一個限制條件：入度與出度之差為1，確保了樹的結構。 - 最小化目標函式：使用
s.Minimize定義了目標函式，即最小化所有邊的流量與其距離的乘積之和。 - 求解模型並提取結果：呼叫
s.Solve()求解模型，並根據變數G[i][j]的值構建了最短路徑樹Tree。
全對最短路徑函式
def solve_all_pairs(D):
n = len(D)
Costs = [[None if i != j else 0 for i in range(n)] for j in range(n)]
Paths = [[None for i in range(n)] for j in range(n)]
for start in range(n):
for end in range(n):
if start != end and Costs[start][end] is None:
rc, Value, Path, Cost, Cumul = solve_model(D, start, end)
if rc == 0:
for k in range(len(Path)-1):
for l in range(k+1, len(Path)):
if Costs[Path[k]][Path[l]] is None:
Costs[Path[k]][Path[l]] = Cumul[l] - Cumul[k]
Paths[Path[k]][Path[l]] = Path[k:l+1]
return Paths, Costs
內容解密：
- 初始化成本與路徑矩陣：首先初始化了兩個二維列表
Costs和Paths，用於儲存任意兩點間的最短距離和對應路徑。 - 遍歷所有節點對：透過雙層迴圈遍歷所有節點對，並呼叫
solve_model函式求解從start到end的最短路徑。 - 更新成本與路徑矩陣：根據求解結果更新
Costs和Paths矩陣，利用最優性原理提取所有子路徑的最短距離和路徑。 - 傳回結果：最終傳回了包含所有節點對之間最短路徑資訊和距離的矩陣。
本章介紹了經典的離散模型，包括最短路徑樹模型和全對最短路徑問題，並透過具體的程式碼範例展示瞭如何使用Python進行建模和求解。這些模型在實際中有著廣泛的應用，掌握它們對於解決複雜問題具有重要意義。
整數規劃經典離散模型：最小集合覆寫問題
整數規劃是解決離散決策問題的重要工具，尤其是在需要計數或表示布林條件的情況下。本章節將探討經典的離散模型，特別著重於最小集合覆寫問題（Minimum Set Cover），並介紹其在實際應用中的變化。
為何需要整數變數？
在許多決策問題中，變數代表的是計數或布林狀態，而非連續的測量值。例如，在供應商選擇問題中，我們需要決定哪些供應商能夠提供所有必需的零件。這類別問題的核心在於整數變數的使用，尤其是二元變數（0 或 1），它們能夠表示是否選擇某個供應商或某個決策。
使用整數變數的場景包括：
- 計數物件：例如，計算供應商數量或零件數量。
- 布林決策：例如，是否與某供應商簽約。
- 指標變數：用於表示某種狀態的存在與否，例如某個連續變數是否非零。
最小集合覆寫問題
問題描述
假設 General Engine Corp. 需要選擇供應商來提供電動汽車所需的零件。不同的供應商能夠提供不同的零件，且存在部分重疊。目標是找到最小數量的供應商，以滿足所有零件需求。
模型構建
決策變數
對每個供應商 $s_i$，我們定義一個二元變數 $S_i$，其值為 1 表示選擇該供應商，為 0 則表示不選擇。這種表示方式使得我們能夠輕鬆地對供應商進行選擇。
# 定義二元變數 S_i 對應每個供應商
S = {s_i: model.binary_var() for s_i in suppliers}
內容解密：
- 這裡使用二元變數來表示是否選擇某個供應商，
model.binary_var()是建立二元變數的函式呼叫。 suppliers是一個包含所有供應商的集合，用於遍歷並為每個供應商建立對應的二元變數。- 二元變數的值限制在 0 和 1 之間，分別對應不選擇和選擇供應商的決策。
目標函式
目標是最小化所選供應商的數量。這可以透過最小化所有二元變數的總和來實作：
$$\min \sum_{i \in S} S_i$$
若考慮每個供應商的成本 $C_i$，目標函式可修改為：
$$\min \sum_{i \in S} C_i S_i$$
# 定義目標函式：最小化供應商總數或總成本
objective = model.sum(S[s_i] for s_i in suppliers)
# 或考慮成本時
objective = model.sum(C[s_i] * S[s_i] for s_i in suppliers)
model.minimize(objective)
內容解密：
model.sum()用於計算所有二元變數的總和，從而表示所選供應商的數量。- 當考慮成本時，將每個二元變數乘以對應的成本 $C_i$，然後求總和。
model.minimize()用於設定最小化目標函式。
約束條件
核心約束是確保所有必需的零件都有至少一個供應商能夠提供。對於每個零件 $p$，假設能夠提供該零件的供應商集合為 $S_p$，則約束條件為：
$$\sum_{i \in S_p} S_i \geq 1$$
# 對每個零件 p，確保至少有一個供應商被選擇
for p in parts:
suppliers_for_p = [s_i for s_i in suppliers if p in parts_supplied[s_i]]
model.add_constraint(model.sum(S[s_i] for s_i in suppliers_for_p) >= 1)
內容解密：
parts是所有零件的集合，parts_supplied[s_i]表示供應商 $s_i$ 能夠提供的零件集合。- 對每個零件 $p$，找出所有能夠提供該零件的供應商，並確保對應的二元變數總和至少為 1。
model.add_constraint()用於新增約束條件至模型中。
@startuml
skinparam backgroundColor #FEFEFE
skinparam componentStyle rectangle
title 最短路徑與集合覆蓋線性規劃模型
package "最短路徑問題" {
component [距離矩陣 D] as dist_matrix
component [決策變數 x_ij] as decision_var
component [流量守恆約束] as flow_conserve
component [目標: 最小化總距離] as obj_min
}
package "模型變體" {
component [最小化距離乘積] as min_product
component [最長路徑問題] as longest_path
component [關鍵任務提取] as critical_task
component [最短路徑樹] as path_tree
}
package "集合覆蓋問題" {
component [二元變數定義] as binary_var
component [覆蓋約束] as cover_constraint
component [目標: 最小供應商數] as min_supplier
}
package "求解流程" {
component [線性規劃模型] as lp_model
component [Python MIP 求解] as solver
component [結果分析] as result
}
dist_matrix --> decision_var
decision_var --> flow_conserve
flow_conserve --> obj_min
obj_min --> min_product
obj_min --> longest_path
longest_path --> critical_task
obj_min --> path_tree
binary_var --> cover_constraint
cover_constraint --> min_supplier
lp_model --> solver
solver --> result
note right of flow_conserve
起點供應量 = 1
終點需求量 = 1
中間節點守恆
end note
note bottom of critical_task
專案管理關鍵路徑
CPM 分析
end note
@enduml
此圖示展示了構建和求解最小集合覆寫問題的基本流程。
圖示內容解密：
- 圖表以線性流程展示，從定義二元變數開始，到結果分析結束。
- 每個節點代表模型構建和求解的一個關鍵步驟。
- 箭頭表示步驟之間的邏輯順序。