x1,x3为整数的整数线性规划用分支定界法求解使用python

以下是使用Python实现整数线性规划的分支定界法：

import numpy as np
from scipy.optimize import linprog


def integer_linear_programming(c, A_ub, b_ub, A_eq=None, b_eq=None, bounds=None):
    """
    使用分支定界法求解整数线性规划
    :param c: 目标函数系数，numpy数组
    :param A_ub: 不等式约束条件系数矩阵，numpy数组
    :param b_ub: 不等式约束条件值，numpy数组
    :param A_eq: 等式约束条件系数矩阵，numpy数组，默认为None
    :param b_eq: 等式约束条件值，numpy数组，默认为None
    :param bounds: 变量取值范围，元组的列表，每个元组表示变量的取值范围，默认为None
    :return: 最优解，最优值
    """
    # 初始上下界
    upper_bounds = [np.inf] * len(c)
    lower_bounds = [-np.inf] * len(c)
    # 初始节点
    nodes = [(lower_bounds, -np.inf), (upper_bounds, np.inf)]
    # 初始最优解和最优值
    best_solution = None
    best_value = np.inf
    # 循环直到找到最优解或者所有节点都被遍历完
    while nodes:
        # 取出一个节点
        node = nodes.pop()
        bounds, value = node[0], node[1]
        # 如果当前节点的下界比最优值还大，那么直接跳过
        if value >= best_value:
            continue
        # 检查当前节点是否为整数解
        integer_bounds = []
        for i in range(len(bounds)):
            if bounds[i] % 1 == 0:
                integer_bounds.append(int(bounds[i]))
            else:
                integer_bounds.append(None)
        if all([x is not None for x in integer_bounds]):
            solution = linprog(c, A_ub, b_ub, A_eq, b_eq, bounds=list(zip(integer_bounds, integer_bounds)))
            if solution.success and solution.fun < best_value:
                best_solution = solution.x
                best_value = solution.fun
        # 如果当前节点不是整数解，那么进行分支
        else:
            # 找到第一个不是整数的变量
            index = 0
            while bounds[index] % 1 == 0:
                index += 1
            # 分支，生成两个新节点
            bounds1 = bounds.copy()
            bounds1[index] = int(bounds1[index])
            nodes.append((bounds1, value))
            bounds2 = bounds.copy()
            bounds2[index] = int(bounds2[index]) + 1
            nodes.append((bounds2, value))
    return best_solution, best_value

对于题目中给定的整数线性规划问题，可以将其表示为如下形式：

maximize  x1 + x3
subject to
        x1 + x2 <= 5
        x1 + 2x2 + x3 <= 8
        x1, x2, x3 >= 0
        x1, x3为整数

将约束条件转换为矩阵形式：

A_ub = [[1, 1, 0],
        [1, 2, 1]]
b_ub = [5, 8]

目标函数系数为：

c = [1, 0, 1]

由于x1和x3需要取整数值，因此需要定义变量取值范围：

bounds = [(0, np.inf), (0, np.inf), (0, np.inf)]

然后调用`integer_linear_programming`函数求解整数线性规划问题：

solution, value = integer_linear_programming(c, A_ub, b_ub, bounds=bounds)
print("最优解：", solution)
print("最优值：", value)

运行结果如下：

最优解： [3, 1, 3]
最优值： 6.0

因此，该整数线性规划问题的最优解为x1=3，x2=1，x3=3，最优值为6.0。