管理运筹学-整数规划1..ppt

分枝定界法割平面法的原理0 1整数规划建模指派问题求解 第七章整数规划 1整数规划问题的提出 问如何选择甲 乙两种货物的托运数量 使获得的利润最大 例1某厂拟用集装箱托运甲乙两种货物 每箱的体积 重量 可获利润以及托运所受限制如表 整数规划有纯整数规划 混合整数规划与0 1整数规划等类型 我们只研究线性整数规划 一般模型为 去掉整数约束条件 就是线性规划问题 其中Z为整数集合 n1 n IP比LP更难求解 一般不能 枚举 不能 四舍五入 如例1 不考虑整数条件 最优解为x 4 8 0 T z 96 四舍五入得x 5 0 T 不是可行解x 4 0 T 不是最优解 而最优解是x 4 1 T z 90 2分枝定界法 BranchandBoundMethod 原问题A 松弛问题B 分枝定界法的基本思想 xk xk 和xk xk 1 设A有一可行解 其目标函数值是Z的一个下界 定界 从解B0开始 若其最优解符合整数条件则得到A的解 否则取此解不满足整数条件的分量 在B0问题中分别加入约束条件 从而得到B0的两个子问题B1和B2 分枝 分别解B1和B2 根据它们解的情况 或增大 定界 或继续分枝 或终止分枝 重复分枝定界过程 直至不能增大 不能分枝为止 其中 xk 为xk的整数部分 如xk 3 5 xk 3 xk 1 5 xk 2 与原问题约束共同构成B1 构成B2 B0的最优解为x1 4 81 x2 1 82 z0 356 不是A的可行解 由x1 4 81产生两个约束条件x1 4 x1 5 注意 这样分枝并没有减少A的可行解 但增加了可能符合整数条件的顶点 1 再将B1分枝 在B1中分别加x2 2 x2 3得到 A的可行解 z3 更新 340 得到新的界 由于z4 知B4的可行域内不可能含有比 4 2 T更优的解 故B4不再分枝 回到B2 由于z2 不排除B2的可行域中有比 4 2 T更好的整数解的可能 故要继续分枝 在B2中分别加约束条件 x2 1 x2 2 得到问题B5和B6 z 340 z 割平面法 先求解松弛问题B0 然后构造一个割平面 线性约束 切除可行域中一块 其中不含A的可行解 切除的结果使整数解可能成为顶点 Q1 Q2 1 1 R Q1 R Q2 1 1 Q3 切割前 切割后 系数为整数 注意 x1 x2为整数 x3 x4也为整数 当系数和常数项不为整数时 先将不等式变形 然后再加松弛变量 如何构造割平面 最终表为 整数 正真分数 即 正数 不大于bi的整数 决策变量仅取为0或1的整数规划问题 x i是0 1变量的表示 xi 0或1或xi 0 xi 1 xi Z 40 1整数规划 4 1典型的0 1整数规划问题 1 相互排斥的计划 例4 某公司拟在市东 西 南三区建立门市部 拟议中有7个位置 点 Ai i 1 2 7 可供选择 规定在东区 由A1 A2 A3三个点中至多选两个 在西区 由A4 A5两个点中至少选一个 在南区 由A6 A7两个店中至少选一个 如选用Ai点 设备投资估计为bi元 每年可获利润估计为ci元 但投资总额不能超过B元 问选择哪几个点可使年利润最大 解题时先引入0 1变量xi i 1 2 7 令 投资总额不超过B A1 A2 A3三个点中至多选两个 A4 A5两个点中至少选一个 A6 A7两个店中至少选一个 收益最大 2 相互排斥的约束条件 二者择一 如例1中体积约束 车运5x1 4x2 24船运7x1 3x2 45 引入0 1变量y 令体积约束为 5x1 4x2 24 yM7x1 3x2 45 1 y My 0或1其中M为充分大的数 这m个约束条件变为m 1个约束条件和m个变量 第i个约束条件起作用 第i个约束条件不起作用 有m个互相排斥的约束条件 i 1 m 多者择一 引入m个0 1变量yi 3 关于固定费用的问题 例5某工厂为了生产某种产品 有几种不同的生产方式可供选择 如选定的生产方式投资成本高 选购自动化程度高的设备 由于产量大 因而分配到每件产品的变动成本就减低 反之 如选定的生产方式投资低 将来分配到每件产品的变动成本可能增加 所以必须全面考虑 今设有三种方式可供选择 令xj表示采用第j种方式时的产量 cj表示采用第j种方式时每件产品的变动成本 kj表示采用第j种方式时的固定成本 采用各种生产方式的成本分别为 引入0 1变量yj 令 当采用第j种生产方式 即xj 0时不采用第j种生产方式 即xj 0时 于是目标为 MinZ k1y1 c1x1 k2y2 c2x2 k3