管理运筹学课件第4章-整数规划与分配问题说课材料.ppt

管理运筹学课件,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管理运筹学课件第4章-整数规划与分配问题,导入案例集装箱托运计划,某厂拟用集装箱托运甲、乙两种货物，每箱的体积、质量、可获得的利润以及托运所受到的限制如表4-1所示。问怎样安排托运计划，可使利润最大？,货物,每箱体积/米,3,每箱质量/50千克,每箱利润/百元,甲,乙,3,8,4,3,5,6,托运限制,40,24,设 x1,x2表示两种货物装载数量(整数)，依题意有如下数学模型：,在实际中，许多要求变量取整的数学模型，称为整数规划。本章将讨论整数规划求解的基本思路、0-1变量的用法、分配问题及匈牙利法，以及利用Excel,Lingo,WinQSB求解的演示。,5/14/2025,2,管理运筹学课件,4.1.1 整数规划的基本概念,整数规划（,integer programming,，,IP,）是指一类要求问题中的全部或一部分变量为整数的数学规划。,在整数规划中，依决策变量的取值不同，又可进一步划分：如果所有变量都限制为整数，则称为纯整数规划（,Pure Integer Programming,，,PIP,）；如果仅一部分变量限制为整数，则称为混合整数规划（,Mixed Integer Programming,，,MIP,）；变量取二进制的整数规划则称为,0-1,规划（,Binary Integer Programming,，,BIP,）。,5/14/2025,3,管理运筹学课件,4.1.2 分枝定界法的基本思路*,【例4.1】用图解法求解整数规划,分枝定界法(Branch and Bound Method)用于求解整数规划问题，是在20世纪60年代初，由Land Doig和Dakin等人提出的。,解 (1)绘制直角坐标系，图示约束条件，图示目标函数一根基线(z=30)，使其平行移动，求得非整数最优解。该解的坐标为(72/23,88/23)，不在网格线的交叉点上，非整数解（非可行解）。,(2)对“解1”分枝定界：选取x1 进行分枝定界：在原模型的基础上，分别添加x13,x14。优化结果“解2”，X=(3,31/8)，z=38.25；“解3”，X=(4,8/3)，z=36，均为非整数（非可行解）。,(3)先对“解2”分枝定界：“解2”的坐标为(3,31/8)，分别添加 x23，x24，优化结果“解4”，X=(3,3)，z=33，为可行解；“解5”，X=(8/3,4)，z=37.33，为非可行解。,(4)再对“解3”分枝定界：“解3”的坐标，为非整数，添加x22（x2 3为非可行域），优化结果为X=(9/2,2)，z=34.5；再添加x1=4,x1 5。解得整数解X=(4,2)，z=32和非整数解X=(21/4,1)，目标值z=31.25；整数解目标值大于非整数解，取(4,2)，得“解6”。,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 x1,0 1 2 3 4 5 6 7 8 x2,(,2,9/2),z=34.5,解3(,4,8/3),解1(,72/23,88/23),解2(,3,31/8),5x1+6x2=30,解4(,3,3),z=33,解5(,8/3,4),z=37.33,解6(,4,2),z=32,(5)对“解5”分枝定界：“解5”的坐标(8/3,4)，为非整数，添加x12（x13为非可行域），优化结果为X=(2,17/4)，再添加x2=4 和x2=5。求得整数解(2,4)，目标值34；整数解(0,5)，目标值30，取(2,4)。如图“解7”。,解7(,2,4),z=34,(6)剪枝：上述有三个区域的整数解分别为“解4”X=(3,3)，z=33；“解6”X=(4,2)，z=32；“解7”X=(2,4)，z=34。相比较，目标值最大的为34，对应的最优方案。,演示：利用WinQSB,ExcelORM+规划求解,ExcelORM+Lingo求例4.1,5/14/2025,4,管理运筹学课件,4.2.1 0-1规划的概念,0-1规划是一种特殊类型的整数规划，即决策变量只取0或1。0-1规划在整数规划中占有重要地位，许多实际问题，例如指派问题、选址问题、送货问题都可归结为此类规划。求解0-1规划的常用方法是隐枚举法，对各种特殊问题还有一些特殊方法，例如求解指派问题用匈牙利方法就比较方便。,0-1规划的数学模型为：,5/14/2025,5,管理运筹学课件,4.2.2 隐枚举法简介,1.化成标准形式(1)目标函数:min,cj0(2)目标若max,目标系数改变符号,变为min;(2)若cj1)项工作任务，需要 m(n1)个人去完成，并且每个人只干一件工作，每项工作都必须有人干，通过权衡，合理分派任务，使总的消耗(或收益)达到最小(或最大)的0-1规划问题，称为分配问题(Assignment Problem，AP),导入案例,运动项目分配问题,某游泳队有四名运动员，其平时训练成绩(s/50m)如表所示。问如何安排可使总成绩最好？,人员,任务,效率矩阵cij,5/14/2025,11,管理运筹学课件,4.3.1 分配问题数学模型,5/14/2025,12,管理运筹学课件,4.3.2 匈牙利法,5/14/2025,13,管理运筹学课件,4.3.2 匈牙利法,【例4.7】用匈牙利法求引例中的最小化分配问题。,5/14/2025,14,管理运筹学课件,4.3.2 匈牙利法,【例4.8】用匈牙利法求引例中的最小化分配问题。,k=2,最优方案：,，其余=0，最优值z=34,5/14/2025,15,管理运筹学课件,案例4-4 任务分派,5/14/2025,16,管理运筹学课件,案例4-4 任务分派,（2）其中有一个人完成两项，其他每人完成一项；,（3）任务A由甲或丙完成，任务C由丙或丁完成，任务E由甲、乙或丁完成，且规定4人中丙或丁完成两项任务，其他每人完成一项。,（1）任务E必须完成，其他4项中可任选3项完成；,5/14/2025,17,管理运筹学课件,本章小结,5/14/2025,18,管理运筹学课件,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢,