管理运筹学教学课件ppt整数规划.pptx
《管理运筹学教学课件ppt整数规划.pptx》由会员分享,可在线阅读,更多相关《管理运筹学教学课件ppt整数规划.pptx(57页珍藏版)》请在三一文库上搜索。
1、版权归工商管理系刘艳老师所有1 第六章 整数规划 IP(Integer programming) 本 章 要 求 n理解整数规划的含义 n掌握分枝定界法的思想和方法 n掌握0-1变量的含义和用法 n掌握指派问题的算法 n微机求解 版权归工商管理系刘艳老师所有2 6.1 整数规划问题的提出 n决策问题中经常有整数要求,如人数、件 数、机器台数、货物箱数如何解决? 四舍五入不行,枚举法太慢 n问题分类:纯整数规划、混合整数规划、 0-1整数规划 n专门方法:分枝定界法、割平面法、隐枚 举法、匈牙利法 版权归工商管理系刘艳老师所有3 问题举例 n某集装箱运输公司,箱型标准体积24m3,重量 13T,
2、现有两种货物可以装运,甲货物体积5m3 、重量2T、每件利润2000元;乙货物体积4m3 、重量5T、每件利润1000元,如何装运获利最 多? n建模:maxZ=2000x1+1000x2 s.t 5x1+4x224.5 2x1+5x2 14 x1,x2 0且为整数 n解此LP问题,得:X1=4.9,X2=0 n显然不是可行解 版权归工商管理系刘艳老师所有4 整数规划图解法 图解法的启示 nA(4.9,0)点是LP问题的可 行解,不是IP问题的可行解 ,B(4,1)才是IP的最优解 n纯整数规划的可行解就是可 行域中的整数点 n非整数点不是可行解,对于 求解没有意义,故切割掉可 行域中的非可行
3、解,不妨碍 整数规划问题的优化 nIP问题的最优解不优于LP问 题的最优解 1 2 3 4 5 6 7 2 3 1 B A x1 x2 版权归工商管理系刘艳老师所有 5 6.2 分枝定界法 n分枝定界法是20世纪60年代初由land doig 和dakin等人 提出的。其基本思想是根据某种策略将原问题的可行域 分解为越来越小的子域,并检查某个子域内整数解的情 况,直到找到最优的整数解或证明整数解不存在。 n思路:切割可行域,去掉非整数点。一次分枝变成两个 可行域,分别求最优解 n例1. maxZ=2000x1+1000x2 5x1+4x224 .5 2x1+5x2 14 x1 , x2 0且为
4、整数 解:先不考虑整数要求,解相应的LP问题,得 : x1=4.9 x2=0 Z=9800 不是可行解 Z=9600是IP问题的上界,记为:Z=9800 版权归工商管理系刘艳老师所有6 nX1=4.8不符合要求,切掉45之间的可行域, 可行域变成两块,即原有约束条件再分别附加 约束条件x1 4和x1 5 n原问题分解为两个 maxZ=2000x1+1000x2 maxZ=2000x1+1000x2 5x1+4x224.5 5x1+4x224.5 2x1+5x2 14 ( IP1 ) 2x1+5x2 14 (IP2) x1 4 x1 5 x1,x2 0且为整数 x1,x2 0且为整数 版权归工商
5、管理系刘艳老师所有7 n不考虑整数要求,解相应LP问题。 解IP1得:x1=4 ,x2=1 z=9000 解IP2得:无可行解 此时可以断定IP问题的下界为9000,记为 Z=9000 由于目前的分枝末梢最大值是9000,故IP问 题的上界便是9000。由于Z=Z,此时已得IP问 题的最优解,即x1=4,x2=1,Z=9000 版权归工商管理系刘艳老师所有 8 分枝定界法的解题步骤 n1、不考虑整数约束,解相应LP问题; n2、检查是否符合整数要求,是,则得最 优解,完毕。否则,转下步; n3、任取一个非整数变量xi=bi,构造两 个新的约束条件:xibi,xibi+1, 分别加入到上一个LP
6、问题,形成两个新 的分枝问题; n4、不考虑整数要求,解分枝问题。若整 数解的Z值所有分枝末梢的Z值,则得最 优解。否则, 取Z值最大的非整数解, 继续分解,Go to 3。 版权归工商管理系刘艳老师所有9 (课本P161例题2讲解) nMaxz=40x1+90x2 S.t 9x1+7x256 7x1+20x2 70 x1,x20; 且为整数 版权归工商管理系刘艳老师所有 10 Z=0, Z=356 Z=0, Z=349 Z=340, Z=349 Z* = Z= Z =340 LP0 X1=4.81,X2=1.82 Z=356 LP1 X1=4.00,X2=2.10 Z=349 LP1 X1=
7、5.00,X2=1.57 Z=341 X1 4X1 5 LP2 X1=4.00 X2=2.00 Z=340 LP2 X1=1.42 X2=3.00 Z=327 X2 2X2 3 LP2 X1=5.44, X2=1.0 Z=308 LP2 无可行解 X2 1X2 2 版权归工商管理系刘艳老师所有 11 6.3 01规划问题 n某些特殊问题,只做是非选择,故变量设置简化 为0或1,1代表选择,0代表不选择。 n在许多决策问题中,往往存在多种决策方案中选 一个方案的情况,这时,可以在问题中加入以下 约束: xj=1 或 xj1 公式表示从n个决策中必须选中一个;公式则 表示从n个决策中可以选一个,也
8、可以不选。如果 需要从n个决策中选择K个,则可将上两式的右边 值改为K。 nn j=1 j=1 版权归工商管理系刘艳老师所有12 n课本例5: 600万元投资5个项目,求利润 最大的方案? 项目 投资额 项目收益约束条件 中选1项 之中选1项 选必先选 210160 300210 15060 13080 260180 版权归工商管理系刘艳老师所有 13 n例5 n 0 当项目未被选中 建模:设xj= 1 当项目被选中 max Z=160x1+210x2+60x3+80x4+180x5 210x1+300x2+150x3+130x4+260x5 600 x1+x2+x3=1 x3+x4=1 x5
9、 x1 xj=0或1 j=1,2,5 版权归工商管理系刘艳老师所有 14 求解:01规划的隐枚举法 n解例5: max Z=160x1+210x2+60x3+80x4+180x5 210x1+300x2+150x3+130x4+260x5 600 x1+x2+x3=1 x3+x4=1 x5 x1 xj=0或1 j=1,2,5 增加过滤条件: 160x1+210x2+60x3+80x4+180x5 240 版权归工商管理系刘艳老师所有15 用隐枚举法解例5: (x1,x2,x3,x4,x5) Z值 (1,0,0,1,0) 240 (1,1,1,1,1) X (1,1,1,1,0) X (1,1,
10、1,0,1) X (1,1,1,0,0) X (1,1,0,1,1) X (1,1,0,1,0) X (1,1,0,0,1) X (1,1,0,0,0) X (1,0,1,1,1) X (1,0,1,1,0) X (1,0,0,1,1) 420 版权归工商管理系刘艳老师所有16 6.4 指派问题(Assignment Problem) n在生活中经常会遇到这样的问题,某单位 需完成n项任务,恰好有n个人可以承担这 些任务。由于每个人的专长不同,各人完 成任务不同(或所费时间)、效率也不 同。于是产生应指派哪个人去完成哪项任 务,使完成n项任务的总效率最高(或所需 总时间最小)。这类问题称为指派
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 管理 运筹学 教学 课件 ppt 整数 规划
链接地址:https://www.31doc.com/p-3849868.html