以下为实现线性规划分支定界法的Python代码示例： ```python import scipy.optimize as opt import math import sys def branch_and_bound(c, A_ub, b_ub, bounds): # 初始松弛问题求解 result = opt.linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds) best_solution = None best_value = -sys.maxsize def recursive_branch(current_A_ub, current_b_ub, current_bounds): nonlocal best_solution, best_value current_result = opt.linprog(c, A_ub=current_A_ub, b_ub=current_b_ub, bounds=current_bounds) if current_result.success: current_value = current_result.fun current_x = current_result.x # 检查是否所有变量都是整数 all_integers = all([math.isclose(x, round(x), rel_tol=1e-9) for x in current_x]) if all_integers: if current_value < best_value: best_value = current_value best_solution = current_x else: # 选择一个非整数变量进行分支 for i, x in enumerate(current_x): if not math.isclose(x, round(x), rel_tol=1e-9): # 分支1: x <= floor(x) new_A_ub_1 = current_A_ub.copy() new_b_ub_1 = current_b_ub.copy() new_constraint_1 = [0] * len(c) new_constraint_1[i] = 1 new_A_ub_1 = new_A_ub_1.tolist() new_A_ub_1.append(new_constraint_1) new_b_ub_1 = new_b_ub_1.tolist() new_b_ub_1.append(math.floor(x)) recursive_branch(new_A_ub_1, new_b_ub_1, current_bounds) # 分支2: x >= ceil(x) new_A_ub_2 = current_A_ub.copy() new_b_ub_2 = current_b_ub.copy() new_constraint_2 = [0] * len(c) new_constraint_2[i] = -1 new_A_ub_2 = new_A_ub_2.tolist() new_A_ub_2.append(new_constraint_2) new_b_ub_2 = new_b_ub_2.tolist() new_b_ub_2.append(-math.ceil(x)) recursive_branch(new_A_ub_2, new_b_ub_2, current_bounds) break recursive_branch(A_ub, b_ub, bounds) return best_solution, best_value # 示例 c = [-1, -2] # 目标函数系数 A_ub = [[1, 1], [2, 1]] # 不等式约束系数矩阵 b_ub = [5, 8] # 不等式约束右侧常数 bounds = [(0, None), (0, None)] # 变量边界 solution, value = branch_and_bound(c, A_ub, b_ub, bounds) print("最优解:", solution) print("最优值:", -value) ``` 此代码借助`scipy.optimize.linprog`求解线性规划问题，通过递归的方式实现分支定界法。首先求解初始的松弛问题，若解中存在非整数变量，则对该变量进行分支，分别添加约束并递归求解，最终找出整数最优解。