如何用Python实现整数线性规划问题求解？

本文共计718个文字，预计阅读时间需要3分钟。

使用cvxpy求解问题，比如我们求解这样一个问题：首先，我们需要配置基本环境，首先记得按顺序安装以下模块：pip install numpy，pip install mkl，pip install cvxopt，pip install scs，pip install ecos，pip install osqp。

cvxpy求解

比如我们求解这样的一个问题：

我们需要配置基本的环境，首先记得按顺序安装模块：

pip install numpy
pip install mkl
pip install cvxopt
pip install scs
pip install ecos
pip install osqp
再：
pip install cvxpy

完整代码如下：

# coding=gbk
"""
作者：川川
@时间 : 2022/1/30 0:35
群：428335755
"""

import cvxpy as cp
from numpy import array

c = array([40, 90]) # 定义目标向量
a = array([[9, 7], [-7, -20]]) # 定义约束矩阵
b = array([56, -70]) # 定义约束条件的右边向量
x = cp.Variable(2, integer=True) # 定义两个整数决策变量
obj = cp.Minimize(c * x) # 构造目标函数
cons = [a * x <= b, x >= 0] # 构造约束条件
prob = cp.Problem(obj, cons) # 构建问题模型
prob.solve(solver='GLPK_MI', verbose=True) # 求解问题
print("最优值为:", prob.value)
print("最优解为：\n", x.value)

运行结果如下：

由于注释很详细，我就没啥好说的了，如果你有不懂，可以评论区留言，或者加我联系方式问我。

scipy求解

模块安装：

pip install scipy

首先要转化为标准的式：

求解标准式代码如下：

from scipy import optimize
import numpy as np

# 求解函数
res = optimize.linprog(c, A, b, Aeq, beq, LB, UB, X0, OPTIONS)
# 目标函数最小值
print(res.fun)
# 最优解
print(res.x)

标准形式是<=，如果是>=，则在两边加上符号-。
举个例子如下：

求解代码为：

from scipy import optimize
import numpy as np

# 确定c,A,b,Aeq,beq
c = np.array([2, 3, -5])
A = np.array([[-2, 5, -1], [1, 3, 1]])
B = np.array([-10, 12])
Aeq = np.array([[1, 1, 1]])
Beq = np.array([7])
# 求解
res = optimize.linprog(-c, A, B, Aeq, Beq)
print(res)

运行如下：

解释一些结果：

• fun是目标函数最小值
• x是最优解，即上面的x1,x2,x3的最优解

推荐一本好书

《机器学习线性代数基础：Python语言描述》的优势：本书以机器学习涉及的线性代数核心知识为重点，进行新的尝试和突破：从坐标与变换、空间与映射、近似与拟合、相似与特征、降维与压缩这5个维度，环环相扣地展开线性代数与机器学习算法紧密结合的核心内容。