python scipy计算0-1整数规划最优解算例

在Python中，Scipy库提供了解决优化问题的功能，包括线性、二次和整数规划等。对于0-1整数规划（Integer Linear Programming, ILP），可以利用`scipy.optimize.linprog`函数配合`scipy.sparse`处理稀疏矩阵。下面是一个简单的0-1整数规划求解示例，假设我们要最大化目标函数 `c * x`，其中 `x` 是一个长度为n的一维数组，每个元素表示一个决策变量，只能取0或1。

from scipy.optimize import linprog
import numpy as np

# 定义目标系数 c 和约束条件 A_ub（大于等于零的约束）、A_eq（等于零的约束）
c = np.array([1, 2])  # 目标函数的系数
A_ub = [[-1, -1], [1, 1]]  # 约束条件的上界部分，每一行对应一个约束
b_ub = [0, 4]  # 上界的值

# 对于0-1约束，我们通常会添加额外的变量和约束
n_vars = len(c)  # 决策变量的数量
x_bounds = [(0, 1)] * n_vars  # 每个变量的下界（0）和上界（1）

# 如果有等式约束（如A_eq和b_eq），可以像下面这样添加
# A_eq = ...  # 等于零的约束系数
# b_eq = ...  # 等于零的约束值

# 使用linprog求解
res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=x_bounds)

# res是一个字典，包含结果信息
print("最优解：", res.x)
print("最优值：", res.fun)

#