运筹学06整数规划PPT学习教案

1、会计学1 运筹学运筹学06整数规划整数规划 第2页 一、问题的提出 第1页/共39页 第3页 例1 工作分配问题 甲甲乙乙丙丙丁丁 译成英文译成英文21097 译成日文译成日文154148 译成德文译成德文13141611 译成俄文译成俄文415139 甲乙丙丁四人翻译把专利说明书译成四种文字，所需 翻译时间如下表。怎样分配最省时？ 第2页/共39页 第4页 工作分配问题数学模型 第3页/共39页 第5页 例2 急救中心选址问题 某市有八个区，救护车从一个区至另一个区的车程用时 如下表所示（单位：分钟）。若要求救护车在8分钟内 必须赶到，应建几个救护中心？建于何处？ 2345678 18911

2、1314815 2101213111714 37781210 487109 581416 6107 712 1127 212 33456 43456 53456 634568 717 868 急救中心设在k 区，救护车在8分钟内能赶到的区： 第4页/共39页 第6页 急救中心选址问题数学模型 第5页/共39页 第7页 1、一般整数规划 2、0-1 整数规划 第6页/共39页 第8页 第7页/共39页 第9页 三、带逻辑变量的数学规划问题 1、m个约束只有k个起作用 ), 2 , 1(, 1 mibxa n j ijij kmyyy miyMbxa m i n j ijij 21 1 ), 2

3、, 1(, 不不起起作作用用约约束束 起起作作用用约约束束 i i yi 1 0 第8页/共39页 第10页 r n j jij bbbbxa, 21 1 0 或或 1 , 21 11 r r i ii n j jij yyy ybxa i i i b b y 约约束束值值 约约束束值值 0 1 2、右端项有多种选择 第9页/共39页 第11页 3),4(, 1, 4 2121 xxxx则则否否则则则则若若 1 3 4 1 4 21 22 21 12 11 yy Myx Myx Myx Myx 2 , 1 1 0 i i i yi 不不起起作作用用约约束束 起起作作用用约约束束 3、带条件约束

4、或分段约束 第10页/共39页 第12页 0 0 0, )( j jjjj jj x xxcK xC 若若 若若 nj y Myx yKxcz j jj n j jjjj , 2 , 1 1 , 0 0 min 1 增增加加约约束束： ni x x y i i i ,2, 1 01 00 4、价格系数分段定价 n j jj xCz 1 )(min 有先期投入 第11页/共39页 第13页 整数规划 松弛问题 ILP的可行解包含在LP的可行解中 ILP的最优值小于或等于LP的最优值 第12页/共39页 第14页 第13页/共39页 第15页 第14页/共39页 第16页 例1 工作分配问题 甲甲

5、乙乙丙丙丁丁 译成英文译成英文21097 译成日文译成日文154148 译成德文译成德文13141611 译成俄文译成俄文415139 甲乙丙丁四人翻译把专利说明书译成四种文字，所需 翻译时间如下表。怎样分配最省时？ 第15页/共39页 第17页 工作分配问题 员工员工1员工员工2。员工员工m 工作工作1 a11a12A1m 工作工作2 A21a22A2m 。 工作工作m am1am2amm m 个人完成 m 项任务，每项任务由一人完成， 每人分担一项任务。怎样分派才能效率最高，或用 时最少 ？ 工作效率（或工时）矩阵 第16页/共39页 第18页 工作分配问题数学模型 第17页/共39页 第

6、19页 定理1 设原效率矩阵 A =a ij 每行减去常数ui ，每列减去常数vj 新的效率矩阵 B =bij , 则A与的最优解相同。 定理2 若A的元素可分成 0 与非0，则 盖住0的最小直线数 = 不同行、不同列的0的最大个数。 第18页/共39页 第20页 算法原理 设A的元素0，且有一组不同行不同列的0， 则分配问题有一组最优解。 令：与0对应的xij =1，其余xij =0， 就是一个最优解。 此时：z = 0 达到最优。 0875 110104 2350 01105 第19页/共39页 第21页 21097 154148 13141611 415139 2 4 11 4 0875

7、 110104 2350 01195 1、先对行造0。 每行最小值 行位势 第20页/共39页 第22页 0875 110104 2350 01195 2、再对列造0 每列最小值 列位势 0050 0825 11054 2300 01145 第21页/共39页 第23页 3、加括号，画直线； (0)825 11(0)54 23(0)0 01145 第22页/共39页 第24页 4、再用位势法造0 (0)825 11(0)54 23(0)0 01145 未划掉数字中的最小值 2 2 2 0 2 0803 11032 4500 01123 -2-200 第23页/共39页 第25页 5、返回3 0

8、8(0)3 11(0)32 450(0) (0)1123 第24页/共39页 第26页 最后，每行每列都有0，得到最优解 。 08(0)3 11(0)32 450(0) (0)1123 甲 俄语 乙 日语 丙 英语 丁 德语 英英 日日 德德 俄俄 甲甲乙乙丙丙丁丁 z = 4+4+9+11 = 28(小时) 第25页/共39页 第27页 NB 1 I bBcB 1 N 0 bB 1 Zbx rr rrr bxb 第26页/共39页 第28页 为整数xx bAx ts xc , 0 . . min 为整数xx bx bAx ts xc rr , 0 . . min 为整数xx bx bAx ts xc rr , 0 . . min 第27页/共39页 第29页 1 ,0 . min x bAx ts xc 1 ,0 1. min x x bAx ts xc r 1 ,0 0. min x x bAx ts xc r 第28页/共39页 第30页 第29页/共39页 第31页 第30页/共39页 第32页 选一分支写出并求解 放松问题，同时从分 支集中删除该分支 判 定是否 为整数 解 初始分支为可行解 集，初始界为无穷大 判 定是否 分支集 空 是停止 当前最