数学模型1-4整数规划.pdf

1 4 整数规划 整数线性规划模型 线性规划问题除满足 约束条件外 还要求某些变量只取整数 值 混合整数规划模型 线性规划问题中只限 定部分变量为整数 说明 不只是一个简单的限制 使得优化 问题求解比普通线性规划问题变得困难得 多 例1 集装箱运货 货物体积 米3 箱 重量 百公斤 箱 利润 千元 箱 甲5 2 20 乙4 5 10 装运限制24 13 如何装箱以获取最大的利润 设X1 X2 为甲 乙两货物各托运箱数 5X1 4X2 24 2X1 5X2 13 X1 X2 0 X1 X2为整数 maxZ 20 X1 10 X2 例2 投资模型 某公司预投资向四个项目投资15百万 每 个项目需要的投资额度与三年净现值如下表 项目A B C D 投资额 百万 8 6 5 4 净现值NPV 百万 12 8 7 6 如何投资才能使得总的净现值最大 和以前LP模型不同的是 没有投资半个项目 的说法 只有投与不同某个项目的区别 设 Xi i 1 2 3 4 代表是否投资项目A B C D Max Z 12 X1 8X2 7 X3 6X4 8 X1 6X2 5 X3 4X4 15 X1 X2 X3 X4为0或1 例3 选址问题 A1 A3 B2 B4 B3B1A2 Ai 可建仓库地点 容量 ai 投资费用bi 建2个 Bj 商店 需求dj j 1 4 Cij 仓库 i 到商店 j 的单位 运费 问 选择适当地点建仓库 在满足商店需 求条件下 总费用最小 解 设Xi i 1 2 3 为是否在 Ai 建仓库 yij i 1 2 3 j 1 4 由 i仓库向 j商店运货量 y11 y21 d1 y12 y22 y32 d2 y23 y33 d3 y14 y24 y34 d4 x1 x2 x3 2 y11 y12 y14 a1x1 y21 y22 y23 y24 a2x2 y32 y33 y34 a3x3 xi 为0 1 yij 0 混合整数规划 四舍五入法 考虑去掉整数约束的一般线性规划问题问 题 通过舍入此规划问题的解以得到整数解 这样得到的的解可能根本不是整数规划问 题的解 9 例子 对应的一般LP问题的解为 四舍五入后 但真正的整数解为 变量重要性排序 对于例2 还有一种简单的考虑 计算回报 率 投资回报率大的 可望得到最大的NPV 一个极端的例子 相应的线性规划的可行域无界 而此时的 整数规划的可行域为空集 分支定界法分支定界法 割平面法割平面法 整数规划常用解法 分支定界法 基本思路 maxZ CTX AX b X 0 A maxZ CTX AX b X 0 X为整数 B B 为 A 的松弛问题 C D B Xj i 1 B Xj i X Xj i 1 i maxZ 40X1 90X2 9X1 7X2 56 7X1 20X2 70 X1 X2 0 X1 X2为整数 例 解 先解 1 的松弛问题 X 4 809 1 817 Z 355 890 上界Z 选X1分枝 问题 2 1 X1 4 问题 3 1 X1 5 选 2 继续分枝 问题 4 2 X2 2 问题 5 2 X2 3 解为 X1 4 X2 2 1 Z 349 0 解为 X1 5 X2 1 571 Z 341 39 1 4 809 1 817 S0 0 355 890 2 4 2 1 S0 0 349 0 3 5 1 571 S0 0 341 39 4 4 2 S0 0 340 5 1 428 3 340 327 12 6 5 444 1 340 307 76 7 无解无解 X1 4 X1 5 X2 2X2 1 X2 2X2 3 分支定界法步骤 1 A 先解 A 的松弛问题 B 2 B 无可行解 A 无可行解 B 最优解符合 A 要求 停 B 最优解不符合 A 要求 转 3 3 估整数解S0 作下界 4 选 B 解中不符合整数条件的分量Xj Xj bj 分支 作 B 的后续问题 C D C B 加约束Xj bj D B 加约束Xj bj 1 5 解 C D 剪支条件 C D 无可行解 C D 对应的目标值S S0 C D 对应的目标值Sc S0 且解为整数解 令Sc S0 且解为非整数解 令 C D 取代 B 返回 4 6 全部支剪完 停 优点 1 任何模型均可用 2 思路简单 灵活 3 速度快 4 适合上机 分支变量选择原则 按目标函数系数 选系数绝对值最大者变 量先分 对目标值升降影响最大 选与整数值相差最大的非整数变量先分 支 按使用者经验 对各整数变量排定重要性 的优先顺序 分支节点选择 深探法 后进先出法 最后打开的节点最先选 尽快找到整数解 整 数解质量可能不高 广探法 选目标函数当前最大值节点 找到的整数解质 量高 但速度慢 25 例子 0 1背包问题 旅行外出 有一个体积为35个单位的背 包 有七种商品 如何装包 所携带商品 价值最高 26 0 1背包问题 松弛问题 B 为 同于 A 约束 目标 0 Xj 1 j 1 7 A 变量排序 单位重量价值大的先放 重量价值价 重 1 3 12 4 2 4 12 3 3 3 9 3 4 3 15 5 5 15 90 6 6 13 26 2 7 16 112 7 0 S 0 X7 X5 X4 1 X1 1 3 Z 221 9 S 217 X1 X4 X7 1 X5 13 5 Z 217 10 S 217 X1 X7 X5 1 X2 1 4 Z 217 5 S 214 X3 X7 X5 1 X4 1 3 Z 216 6 S 214 X7 X5 X4 1 X6 1 13 Z 219 1 X1 X7 X5 1 X4 1 3 Z 219 7 S 214 X6 X7 1 X5 6 15 Z 174 8 S 214 X7 X5 X4 1 Z 217 2 S 0 X7