線性連續模型在專案與資源最佳化中的應用

線性連續模型是解決最佳化問題的有效工具，尤其適用於專案管理和資源分配等領域。透過建立數學模型，可以清晰地描述專案任務之間的依賴關係、資源限制以及目標函式，進而利用線性規劃演算法求解最佳方案。例如，在專案排程中，可以將任務的開始時間和持續時間作為變數，並設定前置任務的約束條件，以最小化專案的總完成時間。同樣地，在油品混合問題中，可以將不同油品的混合比例作為變數，並設定硬度和成本的約束條件，以找到成本最低的混合方案。更進一步，多階段模型可以模擬現實生活中複雜的決策過程，例如在肥皂製造過程中，需要考慮不同油脂的價格波動、儲存成本以及生產需求，並制定多階段的採購和生產計劃，以最小化總成本。

專案管理與資源最佳化：線性連續模型的應用

專案管理是最佳化領域中的一個重要應用，尤其是在涉及多項任務、複雜依賴關係和有限資源的情況下。線性連續模型為專案管理提供了一種強大的工具，能夠幫助專案經理在滿足前置任務、資源限制等條件下，最小化專案的總完成時間。

專案管理的線性模型構建

在專案管理中，每項任務都有兩個基本屬性：持續時間和前置任務。為了最小化專案的總完成時間，我們需要決定每項任務的開始時間，同時滿足前置任務的限制。假設我們有一組任務 $T$，每項任務 $i$ 的開始時間為 $t_i$，持續時間為 $D_i$，前置任務集合為 $T_i$。我們的目標是最小化專案的總完成時間。

數學模型

1. 決策變數：每項任務 $i$ 的開始時間 $t_i$。
2. 目標函式：最小化專案的總完成時間 $t$，其中 $t \geq t_i + D_i$ 對所有任務 $i$ 成立。
3. 限制條件：
   • 前置任務限制：$t_j + D_j \leq t_i$，對所有 $j \in T_i$。
   • 非負限制：$0 \leq t_i$，對所有任務 $i$。

程式碼實作

def solve_model(D):
    s = newSolver('Project management')
    n = len(D)
    max_time = sum(D[i][1] for i in range(n))
    t = [s.NumVar(0, max_time, 't[%i]' % i) for i in range(n)]
    Total = s.NumVar(0, max_time, 'Total')
    for i in range(n):
        s.Add(t[i] + D[i][1] <= Total)
        for j in D[i][2]:
            s.Add(t[j] + D[j][1] <= t[i])
    s.Minimize(Total)
    rc = s.Solve()
    return rc, SolVal(Total), SolVal(t)

內容解密：

1. newSolver('Project management')：建立一個新的求解器例項，用於解決專案管理問題。
2. max_time = sum(D[i][1] for i in range(n))：計算所有任務持續時間的總和，作為專案總完成時間的上界。
3. t = [s.NumVar(0, max_time, 't[%i]' % i) for i in range(n)]：為每項任務定義一個數值變數，表示其開始時間，範圍在 0 到 max_time 之間。
4. s.Add(t[i] + D[i][1] <= Total)：新增約束條件，確保專案總完成時間 Total 不小於任何任務的結束時間。
5. s.Add(t[j] + D[j][1] <= t[i])：新增前置任務約束，確保任務 $i$ 的開始時間不早於其前置任務 $j$ 的結束時間。
6. s.Minimize(Total)：設定目標函式，最小化專案總完成時間 Total。

混合問題的最佳化

在混合問題中，我們需要將多種原料按照一定的比例混合，以滿足特定的品質要求。例如，在油品混合問題中，不同來源的油品具有不同的硬度和成本，我們需要確定最佳的混合比例，以最小化成本同時滿足硬度要求。

數學模型

假設有 $n$ 種原料，每種原料的成本為 $c_i$，硬度為 $h_i$，混合比例為 $x_i$。目標是最小化總成本 $\sum_{i=1}^{n} c_i x_i$，同時滿足混合後的硬度要求 $H_{min} \leq \sum_{i=1}^{n} h_i x_i \leq H_{max}$。

程式碼實作與解析

# 假設相關資料已給定
def blending_problem(c, h, H_min, H_max):
    # 定義求解器並建立變數
    s = newSolver('Blending Problem')
    n = len(c)
    x = [s.NumVar(0, 1, 'x[%i]' % i) for i in range(n)]
    
    # 新增約束條件
    s.Add(s.Sum(x) == 1)  # 混合比例總和為1
    s.Add(s.Sum(h[i] * x[i] for i in range(n)) >= H_min)  # 硬度下限
    s.Add(s.Sum(h[i] * x[i] for i in range(n)) <= H_max)  # 硬度上限
    
    # 最小化成本
    s.Minimize(s.Sum(c[i] * x[i] for i in range(n)))
    rc = s.Solve()
    return rc, SolVal(x)

內容解密：

1. s.Add(s.Sum(x) == 1)：確保混合比例的總和為 1，表示完全混合。
2. s.Add(s.Sum(h[i] * x[i] for i in range(n)) >= H_min) 和 s.Add(s.Sum(h[i] * x[i] for i in range(n)) <= H_max)：新增硬度約束，確保混合後的硬度在指定範圍內。
3. s.Minimize(s.Sum(c[i] * x[i] for i in range(n)))：最小化混合後的總成本。

多階段模型的應用與技術解析

在現實生活中，決策往往受到多階段影響，前一階段的決定會對後續階段產生重要作用。這種多階段模型在許多實際情況中都有體現，例如倉函式倉管理中，本月的庫存狀況會直接影響下月的採購決策。

2.4 多階段模型的技術核心

多階段模型的建立需要特別注意不同階段之間的連續性和邏輯銜接。以一個綜合性的肥皂製造與混合問題為例，我們將展示如何結合多種技術來解決實際問題。

2.4.1 問題例項：肥皂製造的多階段規劃

肥皂的生產涉及多種不同來源的油脂混合，這些油脂具有不同的脂肪酸成分。我們需要根據肥皂的目標屬性，調整不同油脂的比例，以滿足特定的脂肪酸含量範圍。

表 2-10：不同油脂的脂肪酸含量

表 2-11：目標脂肪酸含量範圍

在這個問題中，我們面臨以下挑戰：

1. 不同油脂的價格在不同月份有所不同（見表2-12）。
2. 可以選擇即期購買或期貨購買來取得油脂。
3. 可以儲存最多1000噸的油脂，但需要支付每噸每月5美元的儲存成本。
4. 每月需要滿足5000噸肥皂的需求。

表2-12：計劃期間內各月份的油價（美元/噸）

多階段模型建立與關鍵技術

在構建多階段模型時，我們需要考慮以下關鍵要素：

1. 變數定義：定義每個階段的決策變數，例如每個月份採購的油脂數量、儲存的油脂數量以及混合生產的肥皂數量。

# 定義變數
oil_purchase = {}
oil_storage = {}
soap_production = {}

for month in range(5):  
    for oil in oils:
        oil_purchase[(month, oil)] = model.continuous_var(name=f"oil_purchase_{month}_{oil}")
        oil_storage[(month, oil)] = model.continuous_var(name=f"oil_storage_{month}_{oil}")
    soap_production[month] = model.continuous_var(name=f"soap_production_{month}")

#### 內容解說：

這段程式碼定義了三個主要變數：

• oil_purchase[(month, oil)]：在特定月份採購特定油脂的數量。
• oil_storage[(month, oil)]：在特定月份儲存特定油脂的數量。
• soap_production[month]：在特定月份生產的肥皂數量。 這些變數用於後續的約束條件和目標函式設定。

2. 約束條件：設定不同階段之間的連續性約束，例如儲存量平衡、生產需求滿足等。

# 設定約束條件
for month in range(5):
    for oil in oils:
        # 油脂儲存平衡約束
        model.add_constraint(oil_storage[(month, oil)] >= 0)
        if month > 0:
            model.add_constraint(oil_storage[(month, oil)] == oil_storage[(month-1, oil)] + oil_purchase[(month, oil)] - soap_production[month] * oil_usage[oil])
    
    # 肥皂生產需求約束
    model.add_constraint(soap_production[month] >= demand)

#### 內容解說：

這段程式碼建立了兩個主要約束條件：

• 油脂儲存平衡約束：確保每個月份的油脂儲存量不會為負，並且儲存量等於前一月的儲存量加上當月採購量減去當月用於生產肥皂的油脂量。
• 肥皂生產需求約束：確保每個月份的肥皂生產量滿足需求量。

3. 目標函式：最小化總成本，包括採購成本、儲存成本等。

# 設定目標函式
total_cost = model.sum(oil_purchase[(month, oil)] * oil_price[(month, oil)] for month in range(5) for oil in oils) + \
             model.sum(oil_storage[(month, oil)] * storage_cost for month in range(5) for oil in oils)
model.minimize(total_cost)

#### 內容解說：

這段程式碼定義了目標函式，旨在最小化總成本。總成本包括兩個部分：

• 採購成本：所有月份中所有油脂的採購成本總和。
• 儲存成本：所有月份中所有儲存油脂的成本總和。

油品混合最佳化問題：線性連續模型例項

在規劃期初，我們擁有一定數量的油品存貨，如表2-13所示。我們的目標是決定如何在每個月的成本最小化的前提下，對這些油品進行精煉和混合。

2.4.2 模型構建

2.4.2.1 決策變數

問題的核心是「如何在每個月的成本最小化的前提下混合各種油品？」這意味著我們需要確定在每個月的最終混合過程中，使用了多少數量的每一種油品。這只是一個開始，但顯然還不夠。因為我們可以從購買的油品和庫存中的油品進行混合，所以我們需要區分這兩個數量。此外，我們可能會決定購買並儲存某些油品（因為價格即將上漲），因此我們還需要知道可以儲存多少數量。這表明對於每一種油品（O = {0, 1, 2, …, n_o} 是油品的集合）和每個月（M = {0, 1, 2, …, n_m} 是月份的集合），至少有三個決策變數。

| 油品 | 持有量 |
|
---
---
|
---
-
---
-|
| o0   | 15     |
| o1   | 52     |
| o2   | 193    |
| o3   | 152    |
| o4   | 70     |
| o5   | 141    |
| o6   | 43     |
| o7   | 25     |
| o8   | 89     |

定義決策變數如下：

• x_{i,j} ≥ 0：表示在第 j 月購買的第 i 種油品的噸數
• y_{i,j} ≥ 0：表示在第 j 月混合到肥皂中的第 i 種油品的噸數
• z_{i,j} ≥ 0：表示在第 j 月初持有的第 i 種油品的噸數

#### 內容解密：

這些變數分別代表了購買、混合和儲存的數量。它們對於描述問題的動態變化至關重要。

2.4.2.2 約束條件

首先，我們需要指定每個油品在每個月份（除了最後一個月）的庫存變化情況。因此，我們有： z_{i,j} + x_{i,j} - y_{i,j} = z_{i,j+1}，對於所有 i ∈ O 和 j ∈ M \ {n_m}

# 示例程式碼：庫存平衡約束
for i in range(n_o):
    for j in range(n_m - 1):
        model.add_constraint(z[i, j] + x[i, j] - y[i, j] == z[i, j + 1])

#### 內容解密：

這個約束確保了每個月的庫存量等於上個月的庫存量加上本月購買量再減去本月混合使用的量。這樣可以確保庫存量的連續性和正確性。

此外，我們還有總儲存量的上下限約束： C_min ≤ Σz_{i,j} ≤ C_max，對於所有 j ∈ M

# 示例程式碼：總儲存量約束
for j in range(n_m):
    model.add_constraint(sum(z[i, j] for i in range(n_o)) >= C_min)
    model.add_constraint(sum(z[i, j] for i in range(n_o)) <= C_max)

#### 內容解密：

這個約束確保了每個月總儲存量都在允許的範圍內，避免了儲存量過大或過小。

接下來是混合比例的約束： l_k * t_j ≤ Σy_{i,j} * p_{i,k} ≤ u_k * t_j，對於所有 k ∈ A 和 j ∈ M

# 示例程式碼：混合比例約束
for j in range(n_m):
    t_j = sum(y[i, j] for i in range(n_o))
    for k in range(n_a):
        model.add_constraint(sum(y[i, j] * p[i, k] for i in range(n_o)) >= l[k] * t_j)
        model.add_constraint(sum(y[i, j] * p[i, k] for i in range(n_o)) <= u[k] * t_j)

#### 內容解密：

這個約束確保了混合後的產品中各種脂肪酸的含量比例在目標範圍內。這對於保證產品品質至關重要。

最後是滿足需求的約束： t_j ≥ D_j，對於所有 j ∈ M

# 示例程式碼：滿足需求約束
for j in range(n_m):
    t_j = sum(y[i, j] for i in range(n_o))
    model.add_constraint(t_j >= D[j])

#### 內容解密：

這個約束確保了每個月生產的肥皂數量滿足當月的需求。

2.4.2.3 目標函式

我們的目標是最小化總成本，包括購買油品的成本和儲存油品的成本。 最小化 Σx_{i,j} * P_{i,j} + Σz_{i,j} * SC

# 示例程式碼：目標函式
model.set_objective('min', sum(x[i, j] * P[i, j] for i in range(n_o) for j in range(n_m)) + sum(z[i, j] * SC for i in range(n_o) for j in range(n_m)))

#### 內容解密：

這個目標函式綜合考慮了購買成本和儲存成本，能夠幫助我們找到最佳化的解決方案。