最佳化技術在解決複雜排程問題中扮演著至關重要的角色。本文探討瞭如何利用 Google OR-Tools 函式庫處理約束條件、指標變數以及 Maximax 和 Minimin 問題。文章首先介紹瞭如何重新定義約束條件，並使用 bounds_on_box 函式計算線性函式的邊界。接著，reify_force 和 reify_raise 函式被用於強制執行約束條件並將其與指標變數關聯。文章進一步探討了指標變數在約束條件滿足性判斷中的應用，並以 Maximax 問題為例展示瞭如何建構數學模型。此外，文章還詳細說明瞭教職員排班問題的解決方案，包括資料表設計、數學模型建立以及 Python 程式碼實作。最後，文章討論了工作人員排班模型的擴充套件，例如加入資格限制和強制排班要求，並提供程式碼範例說明如何將最佳化解轉換為使用者友善的資訊。最後，文章簡要介紹了體育賽程安排問題的建模思路，並總結了最佳化技術在排程問題中的應用價值。
高階技術：約束條件的重新定義與指標變數的應用
在處理複雜的最佳化問題時，常常需要對約束條件進行重新定義，並使用指標變數來表示某些條件是否被滿足。本文將探討如何使用 Google 的 OR-Tools 函式庫來實作這些技術。
約束條件的重新定義
在最佳化問題中，約束條件通常以線性或非線性的形式出現。為了能夠在求解過程中有效地處理這些約束條件，我們需要將它們轉換為適當的形式。
線性約束條件的邊界計算
首先，我們需要計算線性約束條件在給定變數範圍內的上下界。Listing 7-10 提供了一個函式 bounds_on_box，用於計算線性函式在給定範圍內的上下界。
from ortools.linear_solver import pywraplp
def bounds_on_box(a, x, b):
Bounds, n = [None, None], len(a)
s = pywraplp.Solver('Box', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
xx = [s.NumVar(x[i].Lb(), x[i].Ub(), "") for i in range(n)]
S = s.Sum([-b] + [a[i] * xx[i] for i in range(n)])
s.Maximize(S)
rc = s.Solve()
Bounds[1] = None if rc != 0 else s.Objective().Value()
s.Minimize(S)
s.Solve()
Bounds[0] = None if rc != 0 else s.Objective().Value()
return Bounds
約束條件的重新定義與強制執行
接下來，我們需要將約束條件重新定義，並使用指標變數來控制其是否被強制執行。Listing 7-11 提供了函式 reify_force，用於重新定義約束條件並強制執行。
def reify_force(s, a, x, b, delta=None, rel='<=', bnds=None):
n = len(a)
if delta is None:
delta = s.IntVar(0, 1, "")
if bnds is None:
bnds = bounds_on_box(a, x, b)
if rel in ['<=', '==']:
s.Add(sum(a[i] * x[i] for i in range(n)) <= b + bnds[1] * (1 - delta))
if rel in ['>=', '==']:
s.Add(sum(a[i] * x[i] for i in range(n)) >= b + bnds[0] * (1 - delta))
return delta
指標變數的應用
指標變數可以用來表示某些條件是否被滿足。在本文中，我們將探討如何使用指標變數來表示約束條件是否被滿足。
約束條件的滿足與指標變數
Listing 7-12 提供了函式 reify_raise，用於將約束條件的滿足與指標變數聯絡起來。
def reify_raise(s, a, x, b, delta=None, rel='<=', bnds=None, eps=1):
n = len(a)
if delta is None:
delta = s.IntVar(0, 1, "")
if bnds is None:
bnds = bounds_on_box(a, x, b)
if rel == '<=':
s.Add(sum(a[i] * x[i] for i in range(n)) >= b + bnds[0] * delta + eps * (1 - delta))
if rel == '>=':
s.Add(sum(a[i] * x[i] for i in range(n)) <= b + bnds[1] * delta - eps * (1 - delta))
elif rel == '==':
gm = [s.IntVar(0, 1, "") for _ in range(2)]
s.Add(sum(a[i] * x[i] for i in range(n)) >= b + bnds[0] * gm[0] + eps * (1 - gm[0]))
s.Add(sum(a[i] * x[i] for i in range(n)) <= b + bnds[1] * gm[1] - eps * (1 - gm[1]))
s.Add(gm[0] + gm[1] - 1 == delta)
return delta
Maximax 和 Minimin 問題的解決
最後，本文將探討如何使用上述技術來解決 Maximax 和 Minimin 問題。這些問題涉及在多個選項中選擇最佳結果。
Maximax 問題的建模
Maximax 問題可以透過引入新的變數和約束條件來建模。首先，我們需要將每個仿射函式轉換為等式約束。然後，我們使用 reify_raise 函式將這些等式約束轉換為指標變數。最後，我們將目標函式設定為最大化這些指標變數中的最大值。
def reify(s, a, x, b, d=None, rel='<=', bs=None, eps=1):
return reify_raise(s, a, x, b, reify_force(s, a, x, b, d, rel, bs), rel, bs, eps)
範例：解決 Maximax 問題
考慮以下 Maximax 問題：
max max (2x - 3y + 12)
subject to x ∈ [-2, 5], y ∈ [2, 3]
我們可以使用上述技術來解決這個問題。首先，我們定義變數和約束條件。然後，我們使用 reify 函式將約束條件轉換為指標變數。最後，我們將目標函式設定為最大化指標變數。
進階排程技術：教職員排班問題
教職員排班問題牽涉到多重複雜的需求和限制條件，是一個極具挑戰性的最佳化問題。以下將探討一個具體的變體問題：如何將教師分配到課程班級，同時滿足教師的偏好和各種硬性限制條件。
問題描述
假設學校已經安排好課程的上課時間，例如 MOR142 第 1 節課在週一、週三、週五的 9:00-10:00 上課，而第 2 節課則在週二、週四的 9:00-10:30 上課。每個課程班級需要一位教師授課。我們有一群教師，部分是全職，部分是兼職，每位教師都有授課時數的限制。此外，教師們對於某些課程、日期或時間有個人偏好或厭惡。
數學建模與限制條件
硬性限制條件：
- 每個課程班級必須分配到一位教師。
- 每位教師的授課時數不能超過其上限。
- 任何教師不能同時教授兩個或以上在同一時間段上課的課程班級。
教師偏好：
- 教師對於某些課程有偏好或厭惡。
- 教師對於某些特定的上課日期或時間有偏好或厭惡。
- 教師對於某些特定的課程組合有偏好或厭惡，例如不希望連續上課。
解決方案
資料表準備
首先，需要準備幾張資料表來描述問題的各個導向：
課程班級表（如 Table 7-8 所示）：列出所有課程班級的 ID、所屬課程 ID 和上課時間。
教師偏好表（如 Table 7-9 所示）：列出每位教師的 ID、授課時數範圍、對各個課程的偏好值、對某些特定課程集合的偏好值，以及對某些特定課程配對的偏好值。
數學模型
這個問題可以建模為一個包含整數變數的最佳化問題。目標函式旨在最大化教師的整體滿意度，同時滿足所有硬性限制條件。
def staff_scheduling(sectors, instructors, preferences):
# 建立 solver
s = Solver()
# 定義決策變數
x = {}
for i in instructors:
for j in sectors:
x[(i, j)] = s.IntVar(0, 1, f"x_{i}_{j}")
# 硬性限制條件
for j in sectors:
s.Add(s.Sum(x[(i, j)] for i in instructors) == 1) # 每個課程班級恰好分配一位教師
for i in instructors:
s.Add(s.Sum(x[(i, j)] * get_sector_credits(j) for j in sectors) <= get_instructor_max_credits(i)) # 教師授課時數不超過上限
# 加入教師偏好相關限制和目標函式
objective = []
for i in instructors:
for j in sectors:
objective.append(x[(i, j)] * get_instructor_preference(i, j))
s.Maximize(s.Sum(objective))
# 求解
status = s.Solve()
if status == pywraplp.Solver.OPTIMAL:
print("Optimal solution found.")
# 輸出結果
for i in instructors:
for j in sectors:
if x[(i, j)].solution_value() > 0:
print(f"Instructor {i} is assigned to sector {j}")
else:
print("No optimal solution found.")
# 輔助函式：取得課程班級的學分
def get_sector_credits(sector_id):
# 從資料表中查詢或計算課程班級的學分
pass
# 輔助函式：取得教師的最大授課學分
def get_instructor_max_credits(instructor_id):
# 從資料表中查詢教師的最大授課學分
pass
# 輔助函式：取得教師對某個課程班級的偏好值
def get_instructor_preference(instructor_id, sector_id):
# 從資料表中查詢或計算教師對課程班級的偏好值
pass
內容解密：
- 建立 solver：使用適當的最佳化軟體函式庫（如 Google OR-Tools）建立一個整數規劃 solver。
- 定義決策變數：
x[(i, j)]表示是否將教師i分配到課程班級j，其值為 0 或 1。 - 硬性限制條件：確保每個課程班級恰好有一位教師，以及每位教師的授課時數不超過其上限。
- 目標函式：最大化教師對所分配課程班級的整體偏好值。
- 求解與輸出結果：使用 solver 求解該整數規劃問題，並輸出最優分配方案。
工作人員排班模型最佳化
在複雜的工作人員排班問題中，如何有效地分配課程給不同的講師，同時滿足多種限制條件和偏好，是一個具有挑戰性的最佳化問題。本章節將探討如何利用數學建模和最佳化技術來解決這一問題。
7.3.1 建立模型
7.3.1.1 決策變數
首先，我們需要定義決策變數。在這個問題中，我們需要決定將哪個講師分配給哪個課程。因此，決策變數可以定義為一個二元變數 $x_{i,j}$，其中 $i$ 代表講師，$j$ 代表課程。如果 $x_{i,j} = 1$，則表示講師 $i$ 被分配到課程 $j$。
x = [[s.IntVar(0, 1, "") for _ in range(nbS)] for _ in range(nbI)]
內容解密：
這段程式碼定義了一個二維陣列 x，用於表示講師和課程之間的分配關係。其中 nbI 代表講師的數量，nbS 代表課程的數量。s.IntVar(0, 1, "") 用於建立一個二元整數變數，代表是否將某個講師分配給某個課程。
7.3.1.2 約束條件
接下來，我們需要定義約束條件。主要的約束條件包括：
- 每個課程最多隻能分配給一個講師。
- 每個講師分配的課程數量必須在一定的範圍內。
- 每個講師在同一時間內最多隻能上一個課程。
for j in range(nbS):
k_out_of_n(s, 1, [x[i][j] for i in range(nbI)], '<=')
for i in range(nbI):
s.Add(sum(x[i][j] for j in range(nbS)) >= I[i][1][0])
s.Add(sum(x[i][j] for j in range(nbS)) <= I[i][1][1])
for t in range(nbT):
k_out_of_n(s, 1, [x[i][j] for j in range(nbS) if S[j][2] == t], '<=')
內容解密：
- 第一個迴圈確保每個課程最多被分配給一個講師。
- 第二個迴圈確保每個講師分配的課程數量在允許的範圍內。
- 第三個迴圈確保每個講師在同一時間內最多上一個課程。
7.3.1.3 目標函式
目標函式旨在最大化所有講師的偏好權重。偏好權重分為三類別：課程偏好、集合偏好和配對偏好。
WC = sum(x[i][j] * I[i][2][c] for i in range(nbI) for j in range(nbS) for c in range(nbC) if S[j][1] == c)
WR = sum(I[i][3][r] * sum(x[i][j] for j in R[r][1]) for r in range(nbSets) for i in range(nbI))
WP = sum(z[i][p][k] * I[i][4][p] for i in range(nbI) for p in range(nbPairs) for k in range(len(P[p][1])) if I[i][4][p] != 0)
s.Maximize(WC + WR + WP)
內容解密：
WC代表課程偏好的總權重。WR代表集合偏好的總權重。WP代表配對偏好的總權重。- 最終的目標函式是最大化這三類別偏好權重的總和。
7.3.1.4 可執行模型
完整的模型實作如 Listing 7-15 所示。
def solve_model(S, I, R, P):
# ...（省略部分程式碼）
return rc, SolVal(x), xs, ObjVal(s)
內容解密：
這個函式接收四個引數：S（課程資料）、I（講師資料）、R（偏好集合資料）和 P（偏好配對資料）。它傳回求解結果，包括是否成功求解、變數的值、額外的求解資訊和目標函式的值。
進階技術：工作人員排班與體育賽程安排
工作人員排班的最佳化模型變化
在前述的工作人員排班模型基礎上，可以進行多種變化和擴充套件，以滿足不同的實際需求。
加入資格限制
在典型的學術部門中，並非所有教師都具備教授所有課程的資格。我們可以為每個教師-課程配對新增一個「合格」布林變數，用於限制某些特定的排班安排。具體實施方法是將相應的決策變數設為零，從而避免不符合資格的教師被安排教授特定課程。
強制特定教師群體的排班要求
部門可能有政策要求某些教師（如終身教授）每學期必須教授一門低年級課程，無論他們的個人偏好如何。這類別需求可以透過「k-out-of-n」型別的約束來實作。
確保特定課程的教授資格
對於某些具有大量分組的課程，部門可能希望至少有一位終身教授負責其中一個分組，而其他分組則可以由兼職教師負責。這同樣可以透過適當設定的「k-out-of-n」約束來實作。
最佳化解的呈現
在求解最佳化模型後，我們可以透過特定的程式碼（清單7-16）將結果轉換為對使用者有意義的資訊。這段程式碼會生成一個列表，按照教師索引排序，包含每位教師被分配的課程分組，以及參與該分配的三個權重值（如表7-12所示）。這些資訊對於使用者理解最佳化模型的運作以及驗證結果非常有幫助。
def ss_ret(x, z, nbI, nbSets, nbS, nbPairs, I, S, R, P):
xs = []
for i in range(nbI):
xs.append([i, [[j, (I[i][2][S[j][1]],
sum(I[i][3][r] for r in range(nbSets) if j in R[r][1]),
sum(SolVal(z[i][p][k]) * I[i][4][p] / 2
for p in range(nbPairs) for k in range(len(P[p][1]))
if j in P[p][1][k]))] for j in range(nbS) if SolVal(x[i][j]) > 0]])
return xs
內容解密：
- 函式定義：
ss_ret函式接收多個引數，包括決策變數x和z，以及與問題相關的多個陣列和引數，用於處理和傳回最佳化解。 - 迴圈處理：函式透過迴圈遍歷每位教師，並提取出與該教師相關的排班資訊，包括所教授的分組和相關權重。
- 權重計算：對於每個分組，計算三個權重值：課程偏好權重、集合偏好權重和配對偏好權重。其中，配對偏好權重需要考慮相關的分組配對，並將權重值均分至相關分組。
- 結果傳回：最終傳回一個結構化的列表，包含每位教師的排班詳情和相關權重資訊，便於進一步分析和驗證。
體育賽程安排
體育賽程安排是一個複雜的最佳化問題，涉及多個引數和約束條件。我們需要根據聯賽的需求，生成一個賽程表，規定每支球隊在每個星期與哪些對手進行比賽。
問題定義
給定一個聯賽，其中包含多個分割槽，每個分割槽有多支球隊。我們需要確定每支球隊在整個賽季中與同分區和其他分割槽球隊的比賽次數，以及每週最多比賽場次等引數。
模型建立
- 決策變數：使用一個三維二元變數
x_{i,j,w}來表示第i支球隊和第j支球隊是否在第w週進行比賽。 - 約束條件：
- 同分區球隊間的比賽次數約束。
- 不同分割槽球隊間的比賽次數約束。
- 每週每支球隊最多比賽場次的約束。
內容解密：
- 三維二元變數：
x_{i,j,w}用於表示球隊間的比賽安排，其中i和j是球隊索引，w是週索引。 - 約束條件建立：透過數學公式表達不同型別的約束條件，例如同分割槽和不同分割槽之間的比賽次數，以及每週的比賽場次限制。
- 最佳化目標：雖然文中未明確提及，但體育賽程安排的最佳化目標通常包括公平性、觀眾吸引力、球隊休息時間等。
結語
工作人員排班和體育賽程安排都是複雜的最佳化問題，需要根據具體情況建立合適的模型和約束條件。透過運用最佳化技術，可以有效地解決這些問題，並獲得令人滿意的結果。這些技術不僅適用於特定領域，也具有廣泛的應用前景。
