1、什么是線性規劃
線性規劃（Linear programming），在線性等式或不等式約束條件下求解線性目標函式的極值問題，常用于解決資源分配、生產調度和混合問題，例如：
max fx = 2*x1 + 3*x2 - 5*x3
s.t. x1 + 3*x2 + x3 <= 12
2*x1 - 5*x2 + x3 >= 10
x1 + x2 + x3 = 7
x1, x2, x3 >=0
線性規劃問題的建模和求解，通常按照以下步驟進行：
（1）問題定義，確定決策變數、目標函式和約束條件；
（2）模型構建，由問題描述建立數學方程，并轉化為標準形式的數學模型；
（3）模型求解，用標準模型的優化演算法對模型求解，得到優化結果；
2、PuLP 庫求解線性規劃
PuLP是一個開源的第三方工具包，可以求解線性規劃、整數規劃、混合整數規劃問題，
下面以該題為例講解 PuLP 求解線性規劃問題的步驟：
（0）匯入 PuLP庫函式
import pulp
（1）定義一個規劃問題
MyProbLP = pulp.LpProblem("LPProbDemo1", sense=pulp.LpMaximize) # 定義問題名稱
pulp.LpProblem 是定義問題的建構式，
"LPProbDemo1"是用戶定義的問題名（用于輸出資訊），
引數 sense 用來指定求最小值/最大值問題，可選引數值：LpMinimize、LpMaximize ，
（2）定義決策變數
x1 = pulp.LpVariable('x1', lowBound=0, upBound=7, cat='Continuous') # 定義決策變數
x2 = pulp.LpVariable('x2', lowBound=0, upBound=7, cat='Continuous') # 定義決策變數
x3 = pulp.LpVariable('x3', lowBound=0, upBound=7, cat='Continuous') # 定義決策變數
pulp.LpVariable 是定義決策變數的函式，
'x1' 是用戶定義的變數名，
引數 lowBound、upBound 用來設定決策變數的下界、上界；可以不定義下界/上界，默認的下界/上界是負無窮/正無窮，本例中 x1,x2,x3 的取值區間為 [0,7]，
引數 cat 用來設定變數型別，可選引數值：'Continuous' 表示連續變數（默認值）、' Integer ' 表示離散變數（用于整數規劃問題）、' Binary ' 表示0/1變數（用于0/1規劃問題），
（3）添加目標函式
MyProbLP += 2*x1 + 3*x2 - 5*x3 # 設定目標函式
添加目標函式使用 "問題名 += 目標函式式" 格式，
（4）添加約束條件
MyProbLP += (2*x1 - 5*x2 + x3 >= 10) # 不等式約束
MyProbLP += (x1 + 3*x2 + x3 <= 12) # 不等式約束
MyProbLP += (x1 + x2 + x3 == 7) # 等式約束
添加約束條件使用 "問題名 += 約束條件運算式" 格式，
約束條件可以是等式約束或不等式約束，不等式約束可以是 小于等于 或 大于等于，分別使用關鍵字">="、"<="和"=="，
（5）求解
MyProbLP.solve()
print("Status:", pulp.LpStatus[MyProbLP.status]) # 輸出求解狀態
for v in MyProbLP.variables():
print(v.name, "=", v.varValue) # 輸出每個變數的最優值
print("F(x) = ", pulp.value(MyProbLP.objective)) #輸出最優解的目標函式值
solve() 是求解函式，PuLP默認采用 CBC 求解器來求解優化問題，也可以呼叫其它的優化器來求解，如：GLPK，COIN CLP/CBC，CPLEX，和GUROBI，但需要另外安裝，
3、Python程式和運行結果
完整的程式代碼如下：
import pulp
MyProbLP = pulp.LpProblem("LPProbDemo1", sense=pulp.LpMaximize) # 定義問題名稱
x1 = pulp.LpVariable('x1', lowBound=0, upBound=7, cat='Continuous') # 定義決策變數
x2 = pulp.LpVariable('x2', lowBound=0, upBound=7, cat='Continuous') # 定義決策變數
x3 = pulp.LpVariable('x3', lowBound=0, upBound=7, cat='Continuous') # 定義決策變數
MyProbLP += 2*x1 + 3*x2 - 5*x3 # 設定目標函式
MyProbLP += (2*x1 - 5*x2 + x3 >= 10) # 不等式約束
MyProbLP += (x1 + 3*x2 + x3 <= 12) # 不等式約束
MyProbLP += (x1 + x2 + x3 == 7) # 等式約束
MyProbLP.solve()
print("Status:", pulp.LpStatus[MyProbLP.status]) # 輸出求解狀態
for v in MyProbLP.variables():
print(v.name, "=", v.varValue) # 輸出每個變數的最優值
print("F(x) = ", pulp.value(MyProbLP.objective)) #輸出最優解的目標函式值
程式運行結果如下：
Welcome to the CBC MILP Solver
Version: 2.9.0
Build Date: Feb 12 2015
Status: Optimal
x1 = 6.4285714
x2 = 0.57142857
x3 = 0.0
F(x) = 14.57142851
著作權說明：
原創作品
Copyright 2021 YouCans, XUPT
Crated：2021-04-28
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/281129.html
標籤：其他
上一篇：Django模板引擎