Skip to content

整数线性规划 ​

方法速览 ​

  • 主要用途 处理选址、排班或采购等含整数决策的优化。
  • 必要输入 变量取值域、上下界、线性目标和线性约束。
  • 适用条件 至少一项决策只能取离散整数值,业务规则可表达为线性约束。
  • 典型不适用情况 保留的目标或约束含无法接受线性近似的非线性项。
  • 最低限度的验证方式 检查整数性与所有约束,核对求解状态、最优界和差距。

什么时候要把变量限定为整数 ​

选不选一个站点、排几位人员、买几台设备,都有不可分割的决策。若目标和约束对这些变量是线性的,可用整数线性规划。是非选择用 0/1 变量,数量用非负整数。还有能够连续分配的运量或工时,就构成混合整数线性规划。先确认单位,若整箱入库而可以拆箱配送,采购与配送变量的取值域应分别建模。

整数求解如何使用连续松弛 ​

暂时去掉全部整数条件,保留线性约束和变量上下界,得到线性松弛。在最大化问题中,松弛可行域包含原可行域,其最优值给出上界。分支定界可对松弛解中取到非整数值的整数变量建立两个子问题,如从 x=2.4 分成 x≤2 和 x≥3。不可行的分支或其上界无法超过已找到整数解时可跳过。求解器通常还会加入切平面等方法。允许中途停止时,记录整数可行解、界以及相应的最优性差距。SciPy 文档的混合整数线性规划与最优性差距

购买设备的假设算例 ​

假设预算为 4,A、B、C 的成本分别为 3,2,2,对应价值 7,4,4,每类最多买一台。模型为

max 7a+4b+4c,3a+2b+2c≤4,a,b,c∈{0,1}.

连续松弛可先买满价值成本比更高的 A,再用剩余 1 买半台 B,价值为 9。把 B 向上取整超预算,向下取整只得到价值 7。整数可行的组合为不买、单买任一台或合买 B 和 C。合买成本 4、价值 8,故为整数最优。这里可直接枚举,稍大的例子就要让求解器给界。

与相近方法如何选择 ​

若允许拆分,线性规划通常更简单。0/1 选择配合少量整数容量,可以比较动态规划,先估算状态规模。存在很强组合结构时,专用的图算法或约束规划也可能合适。因模型规模太大而使用启发式时,可用松弛界或小实例比较解质量,并明确启发式结果通常没有全局最优证明。

容易埋下问题的写法 ​

仅用上下界 0≤a≤1 仍会允许小数,必须声明为二进制。逻辑限制如“选 A 就必须选 B”,可写为 a≤b。以大常数表达开关时,常数过小会误删方案,过大则会使松弛变弱或产生数值困难,应从变量上界推导。表示人数和班次时要核对每人能否同时出现在多个班次。

第一次求解如何检查 ​

先用几种手写方案或小实例验证每条业务规则。求解后把结果逐项代回约束,并查整数容差。读求解状态区分已证最优、时间到但有可行方案、尚未找到可行解等情形。核对输出中的数量和价值是否符合原单位。若放宽阈值就出现大跳跃,检查它是不是由整台、整箱等执行粒度导致。

把变量下标映射回方案名、人员和班次再复核。即使公式与求解都正确,导出时把甲站与乙站的变量对调,也会造成错误的执行清单。

双语言实验 ​

同一个预算,两种可行域 ​

沿用三种设备采购的模拟数据。尝试把每种采购方案画成一个坐标 (支出,价值)。预算竖线左侧以及竖线上的点可行,最靠上的整数点是购买 B 和 C。连续松弛允许购买部分设备,因此可沿着 A 的单位价值 7/3 先投入 3,再把余下 1 用于 B 或 C,得到价值 9。其理由是若低单位价值的设备占了预算,同时高单位价值设备仍能继续购买,就可将一小段预算转向后者并提高价值。这条交换推理依赖于仅有一道预算约束和可分割数量。

设原整数最优值为 z⋆,则整数可行方案给出下界,松弛给出上界,故 8≤z⋆≤9。上下界之差为 1。对这个小例子,枚举已检查所有 23=8 个组合,因而知道 z⋆=8。更大的实例用分支定界一类工具,按当前最好整数解和当前全局界报告剩余差距,松弛初界常会在求解过程中收紧。

独立运行 ​

Python 在终端安装依赖 python -m pip install numpy matplotlib,下载文件后运行 python mmf_integer_programming.py。MATLAB 将 mmf_integer_programming.m 放入当前文件夹,在命令窗口运行 result = mmf_integer_programming(),基础实验无需额外工具箱。两种脚本均输出数值并绘制图形。

下载 Python 源码 · 下载 MATLAB 源码

列出两个项目所有 0/1 决策,先过预算再比收益。预算 5 时选第二项,收益 5,恰好用完预算。完整实践进一步比较连续松弛。

最简版依赖 Python:无第三方依赖。MATLAB:基础功能,无需额外工具箱。

在源码所在目录运行 python mmf_min_integer_programming.py

py
import json
from itertools import product

costs = [3, 5]
values = [4, 5]
budget = 5
# 穷举每项选或不选的二进制向量,只对可行组合比较收益。
feasible = []
for choice in product((0, 1), repeat=len(costs)):
    cost = sum(flag * amount for flag, amount in zip(choice, costs))
    if cost <= budget:
        value = sum(flag * amount for flag, amount in zip(choice, values))
        feasible.append((value, cost, choice))
value, cost, choice = max(feasible, key=lambda row: row[0])
assert choice == (0, 1) and cost == budget and value == 5
result = {"choice": list(choice), "cost": cost, "value": value, "feasible_count": len(feasible)}
print("LAB_RESULT " + json.dumps(result, ensure_ascii=False))
下载当前源码

Python 用 itertools.product 生成二元组合,MATLAB 通过基础函数 ndgrid 展平得到组合矩阵。图中若多个组合坐标重合,只显示一个位置,因此不能由点的个数判断枚举是否完整。两种语言的 x、cost、value、relaxed_value、absolute_gap 应对应 [0,1,1]、4、8、9、1。

用标准求解器复核 ​

Python 可选安装 scipy,MATLAB 的 intlinprog 需要 Optimization Toolbox。两边都调为最小化负价值,并单独标注整数变量和 [0,1] 上下界。对于更大的模型,复算整数约束、预算、目标和求解状态。 SciPy milp · MathWorks intlinprog

python
from scipy.optimize import Bounds, LinearConstraint, milp

fit = milp([-7, -4, -4], integrality=[1, 1, 1],
           bounds=Bounds([0, 0, 0], [1, 1, 1]),
           constraints=LinearConstraint([[3, 2, 2]], 0, 4))
assert fit.success, fit.message
print(fit.x, -fit.fun)
matlab
[x, fval, flag] = intlinprog([-7; -4; -4], 1:3, [3 2 2], 4, ...
    [], [], zeros(3, 1), ones(3, 1));
assert(flag == 1);
disp([x.' -fval])
参数练习与参考结论

将预算从 4 提高到 5,整数最优值变为 11。A+B 和 A+C 并列,枚举顺序不同可能选出不同方案,比较时应核对支出同为 5、价值同为 11。此外,预算从 4 提高到 4.5 时整数最优仍是 8,说明整数模型的预算收益会跳变。

关联文章 ​

MathModel FAQ · 数学建模知识库