[Python] 線性規劃 Linear Programming

程式語言：Python
Package：
pulp
官方文件

功能：線性規劃求解

建立問題

pulp.LpProblem(name='NoName', sense=1)
  1. import pulp
  2.  
  3. # 求最小值
  4. minimum_problem = pulp.LpProblem("problemName", pulp.LpMinimize)
  5.  
  6. # 求最大值
  7. 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=[])
  1. import pulp
  2.  
  3. # 建立 x 變數，範圍 (-∞, ∞)，值為 continuous
  4. continous_x = pulp.LpVariable("x", lowBound=None, upBound=None, cat='Continuous')
  5.  
  6. # 建立 y 變數，範圍 [-10.5, 10.5]，值為 continuous
  7. continous_y = pulp.LpVariable("y", lowBound=-10.5, upBound=10.5, cat='Continuous')
  8.  
  9. # 建立 z 變數，範圍 [0, ∞)，值為 Integer
  10. interger_z = pulp.LpVariable("z", lowBound=0, upBound=None, cat='Integer')
  11.  
  12. # 建立 s 變數，範圍 [0, 1]，值為 Binary
  13. binary_s = pulp.LpVariable("status", lowBound=0, upBound=None, cat='Binary')
  14.  
  15. # 建立多個變數，格式為 dicts
  16. quantities = pulp.LpVariable.dicts("quantities", indexs=["shoes", "pen", "paper"])
  17. # {'shoes': quantities_shoes, 'pen': quantities_pen, 'paper': quantities_paper}
  18.  
  19. # 可用 % format，但注意需包含 indexs 的部分
  20. # 共需 len(indexStart) + 1 個 %
  21. quantities = pulp.LpVariable.dicts("quantities_%s_%s", indexs=["shoes", "pen", "paper"], lowBound=None, upBound=None, cat="Continuous", indexStart=["for"])
  22. # {'shoes': quantities_for_shoes,
  23. #  'pen': quantities_for_pen,
  24. #  'paper': quantities_for_paper}

建立數學方程式

pulp.LpAffineExpression(e=None, constant=0, name=None)
pulp.lpSum(vector) 
  1. import pulp
  2.  
  3. var = pulp.LpVariable.dicts("", ["x", "y", "z"])
  4. var = {var["x"]:1, var["y"]:2, var["z"]:3}
  5. # by 係數建立 1*x + 2*y + 3*z + 10，以下三者等效
  6. formula_1 = pulp.LpAffineExpression(var, constant=10)
  7. formula_2 = pulp.LpAffineExpression([(a,x) for a,x in var.items()], constant=10)
  8. formula_3 = pulp.lpSum([a*x for a,x in var.items()]) + 10

建立不等式

pulp.LpConstraint(e=None, sense=0, name=None, rhs=None)
  1. import pulp
  2.  
  3. var = pulp.LpVariable.dicts("", ["x", "y", "z"])
  4. # 直接寫，必須為 ==, >=, <=
  5. equation_1 = var["x"] + var["y"] == 5
  6. inequality_2 = var["x"] + var["z"] <= 10
  7. inequality_2 = var["y"] + var["z"] >= -6
  8.  
  9. formula = pulp.LpAffineExpression([(var["x"],2), (var["y"],3), (var["z"],5)], constant=10)
  10. # 可再用上面的方程式，轉為其他不等式
  11. # 可以是直覺性寫法，需為 ==, >=, <= 或是 用 LpConstraint 建立
  12. # 以下兩兩等效
  13. formula >= 1
  14. pulp.LpConstraint(formula, pulp.LpConstraintGE, rhs=1)
  15. formula == 1
  16. pulp.LpConstraint(formula, pulp.LpConstraintEQ, rhs=1)
  17. formula <= 1
  18. pulp.LpConstraint(formula, pulp.LpConstraintLE, rhs=1)

不等式彈性設計

pulp.LpConstraint.makeElasticSubProblem(*args, **kwargs)
pulp.FixedElasticSubProblem(constraint, penalty=None, proportionFreeBound=None, proportionFreeBoundList=None)
  1. import pulp
  2.  
  3. var = pulp.LpVariable.dicts("", ["x", "y", "z"])
  4. formula = pulp.LpAffineExpression([(var["x"],1), (var["y"],1), (var["z"],1)])
  5. # 可設定求解範圍
  6. # D = C(x)
  7. inequality = formula >= 100
  8. # D=(c(1−a),c(1+a)) => 90~110
  9. # penalty 為超過範圍 90~110 的處罰係數
  10. # 以下兩者皆會導致 inequality 算式改變，需注意
  11. elasticProb = pulp.FixedElasticSubProblem(inequality, penalty=1, proportionFreeBound=0.1)
  12. # elasticProb = inequality.makeElasticSubProblem(penalty=1, proportionFreeBound=0.1)
  13.  
  14. # D=(c(1−a),c(1+b)) => 90~120
  15. # penalty 為超過範圍 90~120 的處罰係數
  16. # 以下兩者皆會導致 inequality 算式改變，需注意
  17. elasticProb = pulp.FixedElasticSubProblem(inequality, penalty=1, proportionFreeBoundList = [0.1, 0.2])
  18. # elasticProb = inequality.makeElasticSubProblem(penalty=1, proportionFreeBoundList = [0.1, 0.2])
  19.  
  20. # 使用方法
  21. prob = pulp.LpProblem("problem_name")
  22. prob += var["x"]
  23. # 理論上需是 minimize，但會受到 prob 的原始設定影響
  24. # 若 prob 為 maximize，則會被轉變成 maximize，導致結果錯誤
  25. prob.extend(elasticProb)
  26. prob

範例

minimizex−ySubjectto:x≥10y≤10±10% 
  1. import pulp
  2.  
  3. x = pulp.LpVariable("x")
  4. y = pulp.LpVariable("y")
  5.  
  6. prob = pulp.LpProblem("problemName", pulp.LpMinimize)
  7.  
  8. # 加入欲求最小值的方程式，只能一個
  9. # 當加入為純方程式，不為不等式時，則視為目標方程式
  10. prob += x-y
  11. # 與下面等效
  12. # prob.setObjective(x-y)
  13.  
  14. # 加入限制條件
  15. prob += x>=10
  16. elasticProb = pulp.FixedElasticSubProblem(y<=10, penalty=1, proportionFreeBound=0.1)
  17. prob.extend(elasticProb)
  18.  
  19. print(prob)
  20. # out:
  21. # problemName:
  22. # MINIMIZE
  23. # -1*None_elastic_SubProblem_neg_penalty_var + 1*None_elastic_SubProblem_pos_penalty_var + 1*x + -1*y + 0
  24. # SUBJECT TO
  25. # _C1: x >= 10
  26.  
  27. # None_elastic_SubProblem_Constraint: None_elastic_SubProblem_free_bound
  28. #  + None_elastic_SubProblem_neg_penalty_var
  29. #  + None_elastic_SubProblem_pos_penalty_var + y <= 10
  30.  
  31. # VARIABLES
  32. # -1 <= None_elastic_SubProblem_free_bound <= 1 Continuous
  33. # -inf <= None_elastic_SubProblem_neg_penalty_var <= 0 Continuous
  34. # None_elastic_SubProblem_pos_penalty_var Continuous
  35. # x free Continuous
  36. # y free Continuous
  37.  
  38. # 求解，status 顯示求解狀態，為 int，可用 pulp.LpStatus 轉化
  39. status = prob.solve()
  40. # LpStatus key          string value    numerical value
  41. # LpStatusOptimal       “Optimal”       1
  42. # LpStatusNotSolved     “Not Solved”    0
  43. # LpStatusInfeasible    “Infeasible”    1
  44. # LpStatusUnbounded     “Unbounded”     2
  45. # LpStatusUndefined     “Undefined”     3
  46. print((status,pulp.LpStatus[status]))
  47. # out:
  48. # (1, 'Optimal')
  49.  
  50. # 求解後，會把結果放至變數中
  51. # 可用 pulp.value 得到值，變數也可直接用 varValue 得值
  52. print((x.varValue, pulp.value(y), pulp.value(prob.objective)))
  53. # out:
  54. # (10.0, 11.0, -1.0)
  55.  
  56. # 可直接更改變數值，再得到更改後的最小值
  57. x.varValue = 100
  58. print((x.varValue, y.varValue, pulp.value(prob.objective)))
  59. # out:
  60. # (100, 11.0, 89.0)

參考

Introduction to Linear Programming with Python and PuLP
Linear Programming in Python: A Straight Forward Tutorial

留言

張貼留言