1、第三章第三章 整数规划整数规划 一般整数规划问题一般整数规划问题 整数规划的解法整数规划的解法 01规划规划 指派问题指派问题 物流资源分配问题物流资源分配问题知识目标知识目标 掌握整数规划的基本形式；掌握分枝定界法计算过程；理解割平面法；掌握01规划的标准形式；了解01变量的应用；掌握01规划的匈牙利解法。技能目标技能目标 能够结合实际情况建立整数规划模型，并可利用分枝 定界法求解；能够应用01规划建模并求解，安排人员工作。第一节 一般整数规划问题 什么是整数规划问题？整数规划的一般形式：max z（或min z）=1njjjc x 112(,)1,2,.01,2,nijjijjna xbi
2、ms txjnxxx 取整数 第二节 整数规划的解法 割平面法 分枝定界法例3-5 12121212maxz129452028,0 xxxxxxx x割平面法 基本思想：求原问题对应松弛问题最优解，如果不是原问题的可行解，则通过引入线性约束条件（即割平面），使松弛问题的可行域逐步缩小（即切掉一部分），每次切割掉的是松弛问题的非整数解的一部分，但不切掉任何整数解，直到最后使目标函数达到最优的整数解成为可行域的一个顶点时，即为原问题的最优解。其本质是利用线性规划的求解方法逐步缩小可行域，最后找到整数规划的最优解。例3-6 2121212max 326320,0zxxxxxx x且为整数234113
3、442xxx234111(0)(0)1442xxx 2341111244xxx 341110244xx341111442xxs jjjczjjjcz412222333xss 2121212max 326320,0zxxxxxx x且为整数割平面法的求解步骤 步骤1：求解原问题的松弛问题，得最优解，若满足整数约束，则即为最优解，否则进入下一步；步骤2：分解其中一个非整分量，构造一个新的线性约束条件，加入原松弛问题中，形成新的线性规划；步骤3：求解新线性规划问题，得，若为整数则为原问题的最优解，否则进入步骤2。按某非整分量构造的约束条件需满足以下两个条件：（1）当前最优解不满足该约束，即使得该最优
4、解不会再出现在松弛问题可行解中；（2）所有整数可行解均满足该约束，即新增约束条件后，仍保留了原松弛问题的所有整数解。分枝定界法 基本思想：求原问题的对应的松弛问题，其最优解若不是原问题的可行解，则通过附加线性不等式约束（整型），将松弛问题分枝变为若干子问题，即对每一个非整变量附加两个互相排斥（不交叉）的整型约束，即得两个子问题，继续求解定界，重复下去，直到得到最优解为止。例3-7 用分枝定界法求解：12121212max43410.238,0zxxxxstxxx x且均为整数011 6(,)5 5x 0625z 12121212max43410.238,0zxxxxstxxx x且均为整数01
5、1 6(,)5 5x 0625z 分枝定界法求解步骤步骤1：求解原问题的松弛问题（用LP表示），得最优解，若满足整数约束，则即为最优解，否则进入下步。步骤2：分枝。任选的一个不为整的分量，设为（其中为整数部分，为小数部分），据此得两个约束条件，这样就将LP的可行域分割成两个不相交的子集。将这两个约束分别加入LP得两个新问题，即两个分枝LP1和LP2。步骤3：定界。设LP的最优值为，则它是IP最优值的上界，任取IP的一个可行解，对应目标值记为，它是的下界（初次下界可以取“”），即有：分枝定界法求解步骤步骤4：解每一分枝，并根据不同情况采取以下步骤：（1）若无可行解，则将该分枝剪掉，不再考虑。（2
6、）若是整数解且其最优值，则该分枝的解就是原整数规划问题的最优解，结束。（3）若是整数解，但最优值，则取为新的下界，该枝关闭。（4）若是非整数解且，则该分枝中不包含原问题的最优解，该枝关闭。（5）若是非整数解，且又是平行各分枝中的最大目标函数值，则取为新的上界，同时将该枝视为新的LP，回到步骤2。步骤5：各分枝均已查清，对应最优目标值的解即是原问题的最优解。第三节 01规划 如果整数规划问题中的所有决策变量仅限于取0或者1两个值，则称此问题为01整数规划，简称01规划，其变量称为01变量。如果整数规划问题中的部分决策变量为01变量，则称为01混合整数规划。01规划规划的求解 列举法 隐枚举法隐枚
7、举法1231231231223123(0)(1)(2)(3)(4)max32522 44 3 46,01zxxxxxxxxxxxxxx x x或第四节 指派问题 指派问题的标准形式 价值系数,1,2,ijci jn 效率矩阵 决策变量 指派问题求解匈牙利法k定理定理1 设指派问题的效率矩阵为 ，若将该矩阵的某一行（或某一列）的各个元素都减去同一常数 （可正可负），得到新的效率矩阵 ，则以 为效率矩阵的新的指派问题与原指派问题的最优解相同。但其最优解比原最优值减少 。ijn nCck()ijn nCcCk例3-12 61012961081476781296101417971215784C3118
8、1773232154234C 31181773232154234C 1311806621210105412341301180066201210105041234061012961081476781296101417971215784C非标准形式的指派问题 最大化指派问题 人数和工作数不等 某事一定不能由某人来做 一个人可做几件事 第五节 物流资源分配问题本章小结 本章在线性规划的基础上，结合物流问题实际，提出了决策变量部分或者全部限制为整数时的一般线性整数规划问题，通过与相应的线性规划进行比较，说明了整数规划问题需要探求新的求解方法，接着重点阐述了求解整数规划问题的两类基本方法：割平面法与分枝
9、定界法。作为整数规划的特例，专门讨论了决策变量仅取0、1两个值时相应整数规划及其求解方法。最后介绍了整数规划在物流资源分配中的应用。本章重点和难点是求解一般整数规划的分枝定界法、割平面法原理与具体计算方法；标准指派问题及其匈牙利解法；整数规划在物流领域中的有效运用。案例分析（1）现代配送中心规划时考虑的因素、目标和约束条件的限制主要有哪些？（2）案例中建模的过程及模型的含义？（3）整数规划可以应用在哪些实际问题中？实训设计 某企业分配甲、乙、丙、丁四个人去完成五项任务。经测算得每人完成各项任务时间如表3-13所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。
