這是筆者學習使用PULP庫進行線性規(guī)劃問題求解的學習筆記，水平有限，錯誤在所難免，請方家不吝指正。

PULP庫簡介

PULP是用Python寫的一個線性規(guī)劃(Linear Programming, LP)問題求解庫。它的主要作用是將優(yōu)化問題描述為數(shù)學模型，生成MPS或者LP文件，然后調用LP求解器，如CBC、GLPK、CPLEX、Gurobi等來進行求解。

PULP庫安裝

作為python的庫，PULP的安裝非常簡單了，打開command window，輸入以下指令，等待安裝完成即可：

pip install pulp

優(yōu)化問題的求解步驟

通常來說，優(yōu)化問題的求解可以分為以下五個步驟：

• 獲取問題描述
• 數(shù)學劍魔
• 求解數(shù)學模型
• 后續(xù)分析
• 根據(jù)最優(yōu)解，提出實施方案

下面逐一進行詳述：

獲取問題描述

這一步的目的是獲得嚴格無歧義的對問題的描述。在這一步中，需要反復和業(yè)務方進行探討，確保模型和實際業(yè)務嚴密貼合。需要注意模型和數(shù)據(jù)是緊密聯(lián)系的，有時哪怕你提出的模型很好，但是業(yè)務方無法提供可用的數(shù)據(jù)，那你也不可能憑空對模型進行求解。因此必須要確認好對方的需求和可用的數(shù)據(jù)，才能保證模型求解之后作出的決策可以落地。

數(shù)學建模

在這一步中，我們需要從問題的描述里抽象出幾個關鍵因素：決策變量、約束和目標函數(shù)。這一步又可以分解為四個步驟：

• 找到?jīng)Q策變量，也就是我們需要改變以在滿足約束范圍內找到最優(yōu)目標函數(shù)的變量，特別需要注意其單位；
• 用決策變量表示目標函數(shù)，大多數(shù)情況下目標函數(shù)是問題在給定決策變量范圍內的總成本或者總利潤；
• 用決策變量表示約束，這些約束可能是在問題描述中顯式提出的，也可能是一些隱式的約束，例如說我們不可能給一項工作分配負數(shù)時間，在運輸時不能運輸0.8臺車等；
• 確定求解問題所需的數(shù)據(jù)。為了在數(shù)學上求解模型，我們需要數(shù)據(jù)的支持，比如經(jīng)過某條路徑所需的時間、某個變量的具體上界數(shù)字等。

求解數(shù)學模型

在這一步中我們要找到模型的全局最優(yōu)或者近似全局最優(yōu)以幫助我們作出決策。在規(guī)模合理的線性優(yōu)化中，我們通?？梢越柚蠼馄髦幸呀?jīng)實施好的改進單純形法、內點法等來幫助我們得到全局最優(yōu)。但是如果是非線性問題或者問題規(guī)模很大，那么在較短時間內可能無法求出精確解，這時候通常我們會借助啟發(fā)式算法，在給定時間內收斂到一個質量較高的近似全局最優(yōu)(注意在通常情況下，啟發(fā)式算法是不能保證每次都收斂到全局最優(yōu)附近的)。

后續(xù)分析

為了幫助作出最后的決策，通常在跑通求解之后，需要對模型進行進一步的分析：哪些變量的改變對結果影響最大，收緊或者放松約束對結果的影響等等。這些分析可以幫助我們檢驗模型的魯棒性，并且為作出決策提供支持。

此外，需要考慮最優(yōu)解代表的決策是否符合邏輯，或者是否符合業(yè)務方的需求。

根據(jù)最優(yōu)解，提出實施方案

在這一步中，我們需要將用數(shù)學語言表述的最優(yōu)解轉化為簡潔可行的實施方案，進行展示和反饋。這一步中，讓業(yè)務方理解在優(yōu)化過程中發(fā)現(xiàn)的關鍵因素，以及讓他們明白具體在操作中如何實施是非常重要的，否則可能面臨著一個數(shù)學上非常優(yōu)秀的解在業(yè)務上無法落地的結局。

也可以考慮一些將來的工作，如監(jiān)測優(yōu)化方案實施后業(yè)務數(shù)據(jù)的變化、進一步分析數(shù)學模型，為業(yè)務方尋找新的價值等。

在PULP中求解簡單線性規(guī)劃問題

下面用官方文檔上的一個例子解釋以下用PULP求解線性問題的基本步驟：

問題描述

制造商想要用雞肉和牛肉兩種材料來混合出貓糧。在滿足貓糧所需要的蛋白質、脂肪、纖維、鹽等營養(yǎng)成分的前提下，盡可能降低成本。營養(yǎng)成分約束如下：

每克貓糧中，蛋白質大于8%，脂肪大于6%，纖維小于2%，鹽分小于0.4%。

每克雞肉的成本是0.013元，牛肉的成本是0.008元。而每克的這兩種肉含有的營養(yǎng)成分如下表(單位：克)：

制造商想要知道最優(yōu)的混合比例如何。

數(shù)學模型

確定決策變量

此問題中，決策變量就是雞肉和牛肉的比例，可以用兩個變量表示：

目標函數(shù)

這里的優(yōu)化目標就是最小化成本，因此目標函數(shù)為：

約束

此問題的約束來自兩方面：隱式的約束在于兩個比例之和必須為1，顯式的約束在于各營養(yǎng)成分之和必須要大于要求。

PULP求解

函數(shù)介紹

在PULP中可以通過LpProblem建立優(yōu)化問題，其函數(shù)原型如下：

pulp.LpProblem(name='NoName', sense=LpMinimize)

其函數(shù)的參數(shù)為name：在lp文件中寫入的問題名稱；sense：最大或者最小，可為LpMinimize\LpMaximize二者之一。

對于優(yōu)化變量，可以通過LpVariable函數(shù)給出，其函數(shù)原型如下：

pulp.LpVariable(name, lowBound=None, upBound=None, cat='Continuous', e=None)

其函數(shù)參數(shù)為name：變量名；lowBound變量下界；upBound變量上界；cat變量類型，可以為LpInteger\LpBinary\LpContinuous三者之一；e指明變量是否在目標函數(shù)和約束中存在，主要用來實現(xiàn)列生成算法。

完整代碼如下：

from pulp import *

# 1. 建立問題
prob = LpProblem("Bleding Problem", LpMinimize)

# 2. 建立變量
x1 = LpVariable("ChickenPercent", 0, None, LpInteger)
x2 = LpVariable("BeefPercent", 0)

# 3. 設置目標函數(shù)
prob += 0.013*x1 + 0.008*x2, "Total Cost of Ingredients per can"

# 4. 施加約束
prob += x1 + x2 == 100, "PercentagesSum"
prob += 0.100*x1 + 0.200*x2 >= 8.0, "ProteinRequirement"
prob += 0.080*x1 + 0.100*x2 >= 6.0, "FatRequirement"
prob += 0.001*x1 + 0.005*x2 <= 2.0, "FibreRequirement"
prob += 0.002*x2 + 0.005*x2 <= 0.4, "SaltRequirement"

# 5. 求解
prob.solve()

# 6. 打印求解狀態(tài)
print("Status:", LpStatus[prob.status])

# 7. 打印出每個變量的最優(yōu)值
for v in prob.variables():
    print(v.name, "=", v.varValue)

# 8. 打印最優(yōu)解的目標函數(shù)值
print("Total Cost of Ingredients per can = ", value(prob.objective))

求解結果如下：

Status: Optimal
BeefPercent = 57.0
ChickenPercent = 43.0
Total Cost of Ingredients per can =  1.015

參考鏈接

Pulp官方文檔