使用Python求解整数规划问题

  摘要：当前大多使用Matlab解决运筹学中的整数规划问题，鲜有使用Python解决类似问题。本文使用Python中cvxpy库求解整数规划问题，并对问题求解过程进行总结说明。
 关键词：python；整数规划；cvxpy

0.例题

 目标函数：$\ Max \ z= 3x_1+x_2+3x_3$ Max z=3x1​+x2​+3x3​
 约束条件：$\left\{\begin{aligned} -x_1+2x_2+x_3 \leq 4 \\ 4x_2-3x_3 \leq 2 \\ x_1-3x_2+2x_3 \leq 3\\ x_1,x_2,x_3 \geq 0\\ x_1,x_2,x_3\ 均为整数 \end{aligned}\right.$⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​−x1​+2x2​+x3​≤44x2​−3x3​≤2x1​−3x2​+2x3​≤3x1​,x2​,x3​≥0x1​,x2​,x3​ 均为整数​

1.Python代码

#导入numpy
import numpy as np
#导入numpy
import cvxpy as cp

#设置目标函数中变量个数
n=3

#输入目标函数的系数
c=np.array([3,1,3])

#输入约束条件的系数矩阵（3×3）
a=np.array([[-1,2,1],[0,4,-3],[1,-3,2]])

#输入b值（3×1）
b=np.array([4,2,3])

#创建x，个数是3
x=cp.Variable(n,integer=True)

#明确目标函数（此时c是3×1，x是3×1,但python里面可以相乘）
objective=cp.Maximize(cp.sum(c*x))

#明确约束条件，其中a是3×3，x是3×1,a*x=b(b为3×1的矩阵)
constriants=[0<=x,a*x<=b]
#求解问题
prob=cp.Problem(objective,constriants)
#这里solver必须使用cp.CPLEX,否则计算不出来，而CPLEX需要pip intall CPLEX(建议使用清华镜像)
resluts=prob.solve(solver=cp.CPLEX)

#输入结果
print(prob.value)#目标函数的值
print(x.value)#各x的值

2. 结果

3.总结

 （1）本文只介绍了python解决整数规划问题中最基础的一个问题，希望能对初学者有所帮助。
 （2）CPLEX需要pip intall CPLEX，而且是在pip install cvxpy后。而pip install cvxpy你又会发现cmd报错，需要你安装Visual Studio XX。按照要求安装Visual Studio XX后，可继续安装cvxpy，安装cvxpy后再安装CPLEX。
 （3）Python当然可以解决普通线性规划问题，使用optimize.linprog()即可，不再累赘。