Python实现线性规划的计算

线性规划的目标函数既可以是求最大值，也可以是求最小值，约束条件可以是小于等于也可以是大于等于，但为了方便起见，MATLAB和python都规定线性规划标准型为： z = m i n f T x , s . t . = { A ⋅ x ≤ b , A e q ⋅ x = b e q , l b ≤ x ≤ u b z=min m f^Tm x,\ s.t.= egin{cases} m{A} cdot m x lem b,\ Aeq cdot m x=beq ,\ lble m x le ub end{cases} z=min fTx,s.t.=⎩⎪⎨⎪⎧A⋅x≤b,Aeq⋅x=beq,lb≤x≤ub

转换为标准型的方法

目标函数 m a x → m i n max ightarrow min max→min 若目标函数 z 1 = m a x f 1 T x , z_1=max m f_1^Tm x, z1=max f1Tx,则可以通过加负号来实现变成 z 2 = m i n − f 1 T x z_2=min -m f_1^Tm x z2=min −f1Tx 约束条件：大于等于 → ightarrow →小于等于 A ⋅ x ≥ b ⇒ − A ⋅ x ≤ − b m{A} cdot m x ge m bquadmRightarrow -m{A} cdot m x le m {-b} A⋅x≥b⇒−A⋅x≤−b

官方示例及代码（不用第三方库）

z = m i n − x 0 + 4 x 1 s . t . = { − 3 x 0 + x 1 ≤ 6 , − x 0 − 2 x 1 ≥ − 4 , x 1 ≥ − 3 z=min -x_0+4x_1\ s.t.= egin{cases} -3x_0 + x_1 leq 6,\ -x_0 - 2x_1 geq -4,\ x_1 geq -3 end{cases} z=min−x0+4x1s.t.=⎩⎪⎨⎪⎧−3x0+x1≤6,−x0−2x1≥−4,x1≥−3 与MATLAB中 l i n p r o g ( c , A , b , A e q , b e q , l b , u b ) linprog(c,A,b,Aeq,beq,lb,ub) linprog(c,A,b,Aeq,beq,lb,ub) 求解函数类似，python中可以调用scipy库中的optimize.linprog()函数

The problem is not presented in the form accepted by `linprog`. This is
easily remedied by converting the "greater than" inequality
constraint to a "less than" inequality constraint by
multiplying both sides by a factor of :math:`-1`. Note also that the last
constraint is really the simple bound :math:`-3 leq x_1 leq infty`.
Finally, since there are no bounds on :math:`x_0`, we must explicitly
specify the bounds :math:`-infty leq x_0 leq infty`, as the
default is for variables to be non-negative. After collecting coeffecients
into arrays and tuples, the input for this problem is:

>>> c = [-1, 4]
>>> A = [[-3, 1], [1, 2]]
>>> b = [6, 4]
>>> x0_bounds = (None, None)
>>> x1_bounds = (-3, None)
>>> from scipy.optimize import linprog
>>> res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds])

Note that the default method for `linprog` is interior-point, which is
approximate by nature.

>>> print(res)
     con: array([], dtype=float64)
     fun: -21.99999984082494 # may vary
 message: Optimization terminated successfully.
     nit: 6 # may vary
   slack: array([3.89999997e+01, 8.46872439e-08] # may vary
  status: 0
 success: True
       x: array([ 9.99999989, -2.99999999]) # may vary

If you need greater accuracy, try revised simplex.

>>> res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds], method=revised simplex)
>>> print(res)

运行结果：

con: array([], dtype=float64)
     fun: -22.0 # may vary
 message: Optimization terminated successfully.
     nit: 1 # may vary
   slack: array([39.,  0.]) # may vary
  status: 0
 success: True
       x: array([10., -3.]) # may vary

使用pulp库求解（推荐，功能更强大）

from pulp import *

# 1. 建立问题
prob = LpProblem("Problem", LpMinimize)

# 2. 建立变量
x1 = LpVariable("x1")
x2 = LpVariable("x2", -3)

# 3. 设置目标函数 z
prob += -x1 + 4*x2, 

# 4. 施加约束
prob += -3*x1 + x2 <= 6.0, "constraint1"
prob += -x1 - 2*x2 >= -4, "constraint2"

# 5. 求解
prob.solve()

# 6. 打印求解状态
print("Status:", LpStatus[prob.status])

# 8. 打印最优解的目标函数值
print("z= ", value(prob.objective))

# 7. 打印出每个变量的最优值
for v in prob.variables():
    print(v.name, "=", v.varValue)

运行结果：

Status: Optimal
x1 = 10.0
x2 = -3.0
z=  -22.0

小结

就以上代码来看，scipy.optimize.linprog()会比较简便，但是pulp库的代码适用性更强，没有 ≥ ge ≥或 ≤ le ≤的限制，同时目标函数还支持直接设为最大优化。 具体参数设置可以参照或者

注释