程式語言：Python
- Package：
- pulp
官方文件
功能：線性規劃求解
建立問題
pulp.LpProblem(name='NoName', sense=1)
import pulp
# 求最小值
minimum_problem = pulp.LpProblem("problemName", pulp.LpMinimize)
# 求最大值
maximum_problem = pulp.LpProblem("problemName", pulp.LpMaximize)
建立變數
pulp.LpVariable(name, lowBound=None, upBound=None, cat='Continuous', e=None)
pulp.LpVariable.dicts(name, indexs, lowBound=None, upBound=None, cat='Continuous', indexStart=[])
import pulp
# 建立 x 變數，範圍 (-∞, ∞)，值為 continuous
continous_x = pulp.LpVariable("x", lowBound=None, upBound=None, cat='Continuous')
# 建立 y 變數，範圍 [-10.5, 10.5]，值為 continuous
continous_y = pulp.LpVariable("y", lowBound=-10.5, upBound=10.5, cat='Continuous')
# 建立 z 變數，範圍 [0, ∞)，值為 Integer
interger_z = pulp.LpVariable("z", lowBound=0, upBound=None, cat='Integer')
# 建立 s 變數，範圍 [0, 1]，值為 Binary
binary_s = pulp.LpVariable("status", lowBound=0, upBound=None, cat='Binary')
# 建立多個變數，格式為 dicts
quantities = pulp.LpVariable.dicts("quantities", indexs=["shoes", "pen", "paper"])
# {'shoes': quantities_shoes, 'pen': quantities_pen, 'paper': quantities_paper}
# 可用 % format，但注意需包含 indexs 的部分
# 共需 len(indexStart) + 1 個 %
quantities = pulp.LpVariable.dicts("quantities_%s_%s", indexs=["shoes", "pen", "paper"], lowBound=None, upBound=None, cat="Continuous", indexStart=["for"])
# {'shoes': quantities_for_shoes,
# 'pen': quantities_for_pen,
# 'paper': quantities_for_paper}
建立數學方程式
pulp.LpAffineExpression(e=None, constant=0, name=None)
pulp.lpSum(vector)
import pulp
var = pulp.LpVariable.dicts("", ["x", "y", "z"])
var = {var["x"]:1, var["y"]:2, var["z"]:3}
# by 係數建立 1*x + 2*y + 3*z + 10，以下三者等效
formula_1 = pulp.LpAffineExpression(var, constant=10)
formula_2 = pulp.LpAffineExpression([(a,x) for a,x in var.items()], constant=10)
formula_3 = pulp.lpSum([a*x for a,x in var.items()]) + 10
建立不等式
pulp.LpConstraint(e=None, sense=0, name=None, rhs=None)
import pulp
var = pulp.LpVariable.dicts("", ["x", "y", "z"])
# 直接寫，必須為 ==, >=, <=
equation_1 = var["x"] + var["y"] == 5
inequality_2 = var["x"] + var["z"] <= 10
inequality_2 = var["y"] + var["z"] >= -6
formula = pulp.LpAffineExpression([(var["x"],2), (var["y"],3), (var["z"],5)], constant=10)
# 可再用上面的方程式，轉為其他不等式
# 可以是直覺性寫法，需為 ==, >=, <= 或是 用 LpConstraint 建立
# 以下兩兩等效
formula >= 1
pulp.LpConstraint(formula, pulp.LpConstraintGE, rhs=1)
formula == 1
pulp.LpConstraint(formula, pulp.LpConstraintEQ, rhs=1)
formula <= 1
pulp.LpConstraint(formula, pulp.LpConstraintLE, rhs=1)
不等式彈性設計
pulp.LpConstraint.makeElasticSubProblem(*args, **kwargs)
pulp.FixedElasticSubProblem(constraint, penalty=None, proportionFreeBound=None, proportionFreeBoundList=None)
import pulp
var = pulp.LpVariable.dicts("", ["x", "y", "z"])
formula = pulp.LpAffineExpression([(var["x"],1), (var["y"],1), (var["z"],1)])
# 可設定求解範圍
# D = C(x)
inequality = formula >= 100
# D=(c(1−a),c(1+a)) => 90~110
# penalty 為超過範圍 90~110 的處罰係數
# 以下兩者皆會導致 inequality 算式改變，需注意
elasticProb = pulp.FixedElasticSubProblem(inequality, penalty=1, proportionFreeBound=0.1)
# elasticProb = inequality.makeElasticSubProblem(penalty=1, proportionFreeBound=0.1)
# D=(c(1−a),c(1+b)) => 90~120
# penalty 為超過範圍 90~120 的處罰係數
# 以下兩者皆會導致 inequality 算式改變，需注意
elasticProb = pulp.FixedElasticSubProblem(inequality, penalty=1, proportionFreeBoundList = [0.1, 0.2])
# elasticProb = inequality.makeElasticSubProblem(penalty=1, proportionFreeBoundList = [0.1, 0.2])
# 使用方法
prob = pulp.LpProblem("problem_name")
prob += var["x"]
# 理論上需是 minimize，但會受到 prob 的原始設定影響
# 若 prob 為 maximize，則會被轉變成 maximize，導致結果錯誤
prob.extend(elasticProb)
prob
範例
$$
minimize\\
x-y \\
Subject to: \\
x\geq 10\\
y\leq 10\pm 10\%\\
$$
import pulp
x = pulp.LpVariable("x")
y = pulp.LpVariable("y")
prob = pulp.LpProblem("problemName", pulp.LpMinimize)
# 加入欲求最小值的方程式，只能一個
# 當加入為純方程式，不為不等式時，則視為目標方程式
prob += x-y
# 與下面等效
# prob.setObjective(x-y)
# 加入限制條件
prob += x>=10
elasticProb = pulp.FixedElasticSubProblem(y<=10, penalty=1, proportionFreeBound=0.1)
prob.extend(elasticProb)
print(prob)
# out:
# problemName:
# MINIMIZE
# -1*None_elastic_SubProblem_neg_penalty_var + 1*None_elastic_SubProblem_pos_penalty_var + 1*x + -1*y + 0
# SUBJECT TO
# _C1: x >= 10
# None_elastic_SubProblem_Constraint: None_elastic_SubProblem_free_bound
# + None_elastic_SubProblem_neg_penalty_var
# + None_elastic_SubProblem_pos_penalty_var + y <= 10
# VARIABLES
# -1 <= None_elastic_SubProblem_free_bound <= 1 Continuous
# -inf <= None_elastic_SubProblem_neg_penalty_var <= 0 Continuous
# None_elastic_SubProblem_pos_penalty_var Continuous
# x free Continuous
# y free Continuous
# 求解，status 顯示求解狀態，為 int，可用 pulp.LpStatus 轉化
status = prob.solve()
# LpStatus key string value numerical value
# LpStatusOptimal “Optimal” 1
# LpStatusNotSolved “Not Solved” 0
# LpStatusInfeasible “Infeasible” 1
# LpStatusUnbounded “Unbounded” 2
# LpStatusUndefined “Undefined” 3
print((status,pulp.LpStatus[status]))
# out:
# (1, 'Optimal')
# 求解後，會把結果放至變數中
# 可用 pulp.value 得到值，變數也可直接用 varValue 得值
print((x.varValue, pulp.value(y), pulp.value(prob.objective)))
# out:
# (10.0, 11.0, -1.0)
# 可直接更改變數值，再得到更改後的最小值
x.varValue = 100
print((x.varValue, y.varValue, pulp.value(prob.objective)))
# out:
# (100, 11.0, 89.0)
參考
Introduction to Linear Programming with Python and PuLP
Linear Programming in Python: A Straight Forward Tutorial
留言
張貼留言