python用分枝定界法求解混合整数线性规划问题

以下是使用分枝定界法求解混合整数线性规划问题的Python代码示例：

from scipy.optimize import linprog
import math

# 最大化目标函数的系数向量
c = [-3, -2, -4]

# 不等式约束的系数矩阵
A = [[1, 1, 2],
     [2, 1, 1],
     [1, 3, 1]]

# 不等式约束的右端常数向量
b = [5, 7, 3]

# 变量的上下界
bounds = [(0, None), (0, None), (0, 1)]

# 初始的松弛线性规划问题
res = linprog(c, A_ub=A, b_ub=b, bounds=bounds, method='simplex')

# 分枝定界法的主函数
def branch_and_bound(c, A, b, bounds, res):
    # 若当前的松弛线性规划问题已经没有整数解，则返回None
    if not all((map(lambda f: f.is_integer(), res.x))):
        return None
    # 若当前的松弛线性规划问题已经取得整数解，则返回该解
    if all((map(lambda f: f.is_integer(), res.x))) and res.fun.is_integer():
        return res
    # 否则，进行分枝操作
    else:
        # 找到第一个非整数变量
        for i, x in enumerate(res.x):
            if not x.is_integer():
                break
        # 分别构造两个新的线性规划问题，一个限制x[i]的上界为整数部分，一个限制x[i]的下界为整数部分+1
        bounds1 = bounds.copy()
        bounds1[i] = (0, math.floor(res.x[i]))
        res1 = linprog(c, A_ub=A, b_ub=b, bounds=bounds1, method='simplex')
        bounds2 = bounds.copy()
        bounds2[i] = (math.ceil(res.x[i]), 1)
        res2 = linprog(c, A_ub=A, b_ub=b, bounds=bounds2, method='simplex')
        # 分别对两个新问题进行递归调用
        res1 = branch_and_bound(c, A, b, bounds1, res1)
        res2 = branch_and_bound(c, A, b, bounds2, res2)
        # 返回两个新问题的最优解
        if res1 is None:
            return res2
        elif res2 is None:
            return res1
        elif res1.fun >= res2.fun:
            return res1
        else:
            return res2

# 调用分枝定界法函数
res = branch_and_bound(c, A, b, bounds, res)

# 输出结果
print(res)

这里的例子是一个混合整数线性规划问题，其中变量x1、x2和x3均有上下界限制，且x3是一个0-1变量。首先，使用线性规划库中的linprog函数求解该问题的松弛线性规划问题。然后，定义一个分枝定界法的主函数，该函数首先判断当前的松弛线性规划问题是否已经取得整数解，若是则返回该解，否则进行分枝操作。分枝操作中，找到第一个非整数变量，构造两个新的线性规划问题，一个限制该变量的上界为其整数部分，一个限制该变量的下界为其整数部分+1。然后，对两个新问题进行递归调用，最终返回两个新问题的最优解。最后，调用分枝定界法函数，并输出结果。