2. 整数规划选址问题建模与分支定界求解

问题设定与0-1模型构建

某区域配送网络需从6个候选点中选取若干建设配送中心，服务5个需求区。候选点有固定建设成本与容量上限，需求区有确定需求量，每个需求区只能由一个配送中心服务。目标是总成本（建设成本+运输成本）最小。

设 x_j ∈ {0,1} 表示候选点 j 是否建设，y_ij ∈ {0,1} 表示需求区 i 是否由候选点 j 服务。模型为：

min  Σ_j f_j·x_j + Σ_i Σ_j c_ij·d_i·y_ij
s.t. Σ_j y_ij = 1            ∀i        （每需求区恰好分配一次）
     Σ_i d_i·y_ij ≤ Q_j·x_j   ∀j        （容量约束，未建则不可服务）
     y_ij ≤ x_j               ∀i,j      （分配前提）
     x_j, y_ij ∈ {0,1}

教学示例参数（单位：万元、吨）：固定成本 f = [12, 10, 14, 9, 11, 13]；容量 Q = [40, 35, 45, 30, 38, 42]；需求量 d = [18, 22, 15, 25, 20]；单位运输成本 c_ij 取 1~6 的整数矩阵。以下代码用分支定界求解，并对比两种松弛策略。

分支定界实现与松弛策略对比

核心思路：对0-1变量做LP松弛得到下界；若松弛解全为整数则得到可行解；否则选一个分数变量分支（固定为0/1），用优先队列按下界排序搜索。两种松弛策略：完全LP松弛（所有0-1变量松弛为[0,1]连续）与部分松弛（仅松弛 y_ij，保留 x_j 为0-1，即先枚举建设方案再分配）。

import numpy as np
from scipy.optimize import linprog
import heapq, itertools

f = np.array([12,10,14,9,11,13], float)
Q = np.array([40,35,45,30,38,42], float)
d = np.array([18,22,15,25,20], float)
c = np.array([[2,3,1,4,5,2],
              [3,2,4,1,3,5],
              [1,4,2,3,2,1],
              [5,2,3,1,4,2],
              [2,3,5,2,1,3]], float)
m, n = c.shape                      # 5 需求区, 6 候选点
cost = c * d[:, None]               # 运输成本系数

def build_lp(free_x):
    # 变量顺序: x(6) 然后 y(30)
    nv = n + m*n
    obj = np.zeros(nv)
    obj[:n] = f
    obj[n:] = cost.ravel()
    A, b = [], []
    # 分配约束: sum_j y_ij = 1
    for i in range(m):
        row = np.zeros(nv); row[n+i*n:n+(i+1)*n] = 1
        A.append(row); b.append(1)
    # 容量约束: sum_i d_i y_ij - Q_j x_j <= 0
    for j in range(n):
        row = np.zeros(nv); row[j] = -Q[j]
        for i in range(m):
            row[n+i*n+j] = d[i]
        A.append(row); b.append(0)
    bounds = [(0,1)]*nv
    if not free_x:                  # 部分松弛: x 保持0-1
        for j in range(n):
            bounds[j] = (0,1)
    return obj, np.array(A), np.array(b), bounds

def solve_lp(free_x, fix):
    obj, A, b, bounds = build_lp(free_x)
    bounds = list(bounds)
    for idx, val in fix.items():
        bounds[idx] = (val, val)
    res = linprog(obj, A_ub=A, b_ub=b, bounds=bounds, method="highs")
    return res

def branch_and_bound(free_x=True):
    best, best_x = np.inf, None
    root = solve_lp(free_x, {})
    heap = [(root.fun, {}, root.x)]
    nodes = 0
    while heap:
        lb, fix, xsol = heapq.heappop(heap)
        if lb >= best - 1e-9:
            continue
        nodes += 1
        # 找分数变量
        frac = [(i, v) for i, v in enumerate(xsol)
                if 1e-6 < v < 1-1e-6]
        if not frac:
            if lb < best:
                best, best_x = lb, xsol
            continue
        i, _ = frac[0]
        for val in (0, 1):
            nf = dict(fix); nf[i] = val
            r = solve_lp(free_x, nf)
            if r.success and r.fun < best - 1e-9:
                heapq.heappush(heap, (r.fun, nf, r.x))
    return best, best_x, nodes

for tag, fx in [("完全LP松弛", True), ("部分松弛(x为0-1)", False)]:
    val, x, nodes = branch_and_bound(fx)
    print(f"{tag}: 最优成本={val:.2f}, 搜索节点={nodes}")
    print("  建设方案 x =", np.round(x[:n]).astype(int))

运行后应观察到：完全LP松弛的根节点下界更紧，但分支中需处理更多分数变量；部分松弛因 x 已为整数，分支维度更少，节点数通常更少但根下界偏松。两者最终最优值应一致（示例数据下预期总成本约 210~230 区间，具体以实际运行为准）。

结果判读与效率对比要点

判读要点：两策略最终最优成本应相同；若节点数差异明显，说明下界紧度与分支维度存在权衡。实际工程中可先用部分松弛快速得到可行上界，再用完全松弛收紧下界，形成混合策略。