主题
整数线性规划
方法速览
- 主要用途 处理选址、排班或采购等含整数决策的优化。
- 必要输入 变量取值域、上下界、线性目标和线性约束。
- 适用条件 至少一项决策只能取离散整数值,业务规则可表达为线性约束。
- 典型不适用情况 保留的目标或约束含无法接受线性近似的非线性项。
- 最低限度的验证方式 检查整数性与所有约束,核对求解状态、最优界和差距。
什么时候要把变量限定为整数
选不选一个站点、排几位人员、买几台设备,都有不可分割的决策。若目标和约束对这些变量是线性的,可用整数线性规划。是非选择用
整数求解如何使用连续松弛
暂时去掉全部整数条件,保留线性约束和变量上下界,得到线性松弛。在最大化问题中,松弛可行域包含原可行域,其最优值给出上界。分支定界可对松弛解中取到非整数值的整数变量建立两个子问题,如从
购买设备的假设算例
假设预算为 4,A、B、C 的成本分别为
连续松弛可先买满价值成本比更高的 A,再用剩余 1 买半台 B,价值为
与相近方法如何选择
若允许拆分,线性规划通常更简单。0/1 选择配合少量整数容量,可以比较动态规划,先估算状态规模。存在很强组合结构时,专用的图算法或约束规划也可能合适。因模型规模太大而使用启发式时,可用松弛界或小实例比较解质量,并明确启发式结果通常没有全局最优证明。
容易埋下问题的写法
仅用上下界
第一次求解如何检查
先用几种手写方案或小实例验证每条业务规则。求解后把结果逐项代回约束,并查整数容差。读求解状态区分已证最优、时间到但有可行方案、尚未找到可行解等情形。核对输出中的数量和价值是否符合原单位。若放宽阈值就出现大跳跃,检查它是不是由整台、整箱等执行粒度导致。
把变量下标映射回方案名、人员和班次再复核。即使公式与求解都正确,导出时把甲站与乙站的变量对调,也会造成错误的执行清单。
双语言实验
同一个预算,两种可行域
沿用三种设备采购的模拟数据。尝试把每种采购方案画成一个坐标
设原整数最优值为
独立运行
Python 在终端安装依赖 python -m pip install numpy matplotlib,下载文件后运行 python mmf_integer_programming.py。MATLAB 将 mmf_integer_programming.m 放入当前文件夹,在命令窗口运行 result = mmf_integer_programming(),基础实验无需额外工具箱。两种脚本均输出数值并绘制图形。
列出两个项目所有 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。两边都调为最小化负价值,并单独标注整数变量和
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,说明整数模型的预算收益会跳变。