物流运筹学——整数规划ppt课件

1、第三章第三章 整数规划整数规划 普通整数规划问题普通整数规划问题 整数规划的解法整数规划的解法 01规划规划 指派问题指派问题 物流资源分配问题物流资源分配问题知识目的知识目的掌握整数规划的根本方式；掌握整数规划的根本方式；掌握分枝定界法计算过程；掌握分枝定界法计算过程；了解割平面法；了解割平面法；掌握掌握01规划的规范方式；规划的规范方式；了解了解01变量的运用；变量的运用；掌握掌握01规划的匈牙利解法。规划的匈牙利解法。技艺目的技艺目的可以结合实践情况建立整数规划模型，并可利用分可以结合实践情况建立整数规划模型，并可利用分枝枝 定界法求解；定界法求解；可以运用可以运用01规划建模并求解，安

2、排人员任务。规划建模并求解，安排人员任务。第一节 普通整数规划问题 什么是整数规划问题？ 整数规划的普通方式：max z（ 或min z） =1njjjc x 112( , )1,2,. .01,2,nijjijjna xbims txjnxxx 取整数 第二节 整数规划的解法 割平面法 分枝定界法例3-5 12121212maxz129452028,0 xxxxxxx x割平面法 根本思想：求原问题对应松弛问题最优解，假设不是原问题的可行解，那么经过引入线性约束条件即割平面，使松弛问题的可行域逐渐减少即切掉一部分，每次切割掉的是松弛问题的非整数解的一部分，但不切掉任何整数解，直到最后使目的函

3、数到达最优的整数解成为可行域的一个顶点时，即为原问题的最优解。其本质是利用线性规划的求解方法逐渐减少可行域，最后找到整数规划的最优解。 例3-6 2121212max 326320,0zxxxxxx x且为整数234113442xxx234111(0)(0)1442xxx 2341111244xxx 341110244xx341111442xxs jjjczjjjcz412222333xss 2121212max 326320,0zxxxxxx x且为整数割平面法的求解步骤 步骤1：求解原问题的松弛问题，得最优解，假设满足整数约束，那么即为最优解，否那么进入下一步；步骤2：分解其中一个非整分量

4、，构造一个新的线性约束条件，参与原松弛问题中，构成新的线性规划；步骤3：求解新线性规划问题，得，假设为整数那么为原问题的最优解，否那么进入步骤2。按某非整分量构造的约束条件需满足以下两个条件：1当前最优解不满足该约束，即使得该最优解不会再出如今松弛问题可行解中；2一切整数可行解均满足该约束，即新增约束条件后，仍保管了原松弛问题的一切整数解。分枝定界法 根本思想：求原问题的对应的松弛问题，其最优解假设不是原问题的可行解，那么经过附加线性不等式约束整型，将松弛问题分枝变为假设干子问题，即对每一个非整变量附加两个相互排斥不交叉的整型约束，即得两个子问题，继续求解定界，反复下去，直到得到最优解为止。例

5、3-7 用分枝定界法求解：12121212max43410. . 238,0zxxxxstxxx x且均为整数011 6(, )5 5x 0625z 12121212max43410. . 238,0zxxxxstxxx x且均为整数011 6(, )5 5x 0625z 分枝定界法求解步骤步骤1：求解原问题的松弛问题用LP表示，得最优解，假设满足整数约束，那么即为最优解，否那么进入下步。步骤2：分枝。任选的一个不为整的分量，设为其中为整数部分，为小数部分，据此得两个约束条件，这样就将LP的可行域分割成两个不相交的子集。将这两个约束分别参与LP得两个新问题，即两个分枝LP1和LP2。步骤3：定

6、界。设LP的最优值为，那么它是IP最优值的上界，任取IP的一个可行解，对应目的值记为，它是的下界初次下界可以取“，即有：分枝定界法求解步骤步骤4：解每一分枝，并根据不同情况采取以下步骤：1假设无可行解，那么将该分枝剪掉，不再思索。2假设是整数解且其最优值，那么该分枝的解就是原整数规划问题的最优解，终了。3假设是整数解，但最优值，那么取为新的下界，该枝封锁。4假设是非整数解且，那么该分枝中不包含原问题的最优解，该枝封锁。5假设是非整数解，且又是平行各分枝中的最大目的函数值，那么取为新的上界，同时将该枝视为新的LP，回到步骤2。步骤5：各分枝均已查清，对应最优目的值的解即是原问题的最优解。第三节

7、01规划 假设整数规划问题中的一切决策变量仅限于取0或者1两个值，那么称此问题为01整数规划，简称01规划，其变量称为01变量。假设整数规划问题中的部分决策变量为01变量，那么称为01混合整数规划。 01规划的求解规划的求解 列举法 隐枚举法隐枚举法1231231231223123(0)(1)(2)(3) (4) max32522 44 3 46 ,01zxxxxxxxxxxxxxx x x或第四节 指派问题 指派问题的规范方式 价值系数 ,1,2,ijci jn 效率矩阵 决策变量 指派问题求解匈牙利法k定理定理1 设指派问题的效率矩阵为设指派问题的效率矩阵为 ，假设将该矩阵的某一，假设将该

8、矩阵的某一行行或某一列的各个元素都减去同一常数或某一列的各个元素都减去同一常数 可正可负，得到可正可负，得到新的效率矩阵新的效率矩阵 ，那么以，那么以 为效率矩阵的新的指派问题为效率矩阵的新的指派问题与原指派问题的最优解一样。但其最优解比原最优值减少与原指派问题的最优解一样。但其最优解比原最优值减少 。 ijn nCck()ijn nCcCk例3-12 61012961081476781296101417971215784C31181773232154234C 31181773232154234C 131180662121010541234130118006620121010504123406

9、1012961081476781296101417971215784C非规范方式的指派问题 最大化指派问题 人数和任务数不等 某事一定不能由某人来做 一个人可做几件事 第五节 物流资源分配问题本章小结 本章在线性规划的根底上，结合物流问题实践，提出了决策变量部分或者全部限制为整数时的普通线性整数规划问题，经过与相应的线性规划进展比较，阐明了整数规划问题需求探求新的求解方法，接着重点论述了求解整数规划问题的两类根本方法：割平面法与分枝定界法。作为整数规划的特例，专门讨论了决策变量仅取0、1两个值时相应整数规划及其求解方法。最后引见了整数规划在物流资源分配中的运用。 本章重点和难点是求解普通整数规划的分枝定界法、割平面法原理与详细计算方法；规范指派问题及其匈牙利解法；整数规划在物流领域中的有效运用。 案例分析1现代配送中心规划时思索的要素、目的和约束条件的限制主