0-1整数规划解法.ppt

  1. 1、本文档共34页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
指派问题与匈牙利法 用匈牙利法求出最优指派方案为: 即甲-B,乙-D,丙-E,丁-A, 任务C放弃。 最少时间为105。 求职应注意的礼仪 求职时最礼貌的修饰是淡妆 面试时最关键的神情是郑重 无论站还是坐,不能摇动和抖动 对话时目光不能游弋不定 要控制小动作 不要为掩饰紧张情绪而散淡 最优雅的礼仪修养是体现自然 以一种修养面对两种结果 必须首先学会面对的一种结果----被拒绝 仍然感谢这次机会,因为被拒绝是面试后的两种结果之一。 被拒绝是招聘单位对我们综合考虑的结果,因为我们最关心的是自己什么地方与用人要求不一致,而不仅仅是面试中的表现。 不要欺骗自己,说“我本来就不想去”等等。 认真考虑是否有必要再做努力。 必须学会欣然面对的一种结果----被接纳 以具体的形式感谢招聘单位的接纳,如邮件、短信 考虑怎样使自己的知识能力更适应工作需要 把走进工作岗位当作职业生涯的重要的第一步,认真思考如何为以后的发展开好头。 Thank you 解0-1型整数规划最容易想到的方法,和一般整数线性规划的情形一样,就是穷举法,即检查变量取值为0或1的每一种组合,比较目标函数值以求得最优解, 这就需要检查变量取值的2n个组合。 对于变量个数n较大(例如n>10),这几乎是不可能的。 而隐枚举法就是在此基础上改进的,通过加入一定的条件,就能较快的求得最优解。 只检查变量取值的组合的一部分,就能求到问题的最优解,这样的方法称为隐枚举法(implicit enumeration),分枝定界法也是一种隐枚举法。其解题关键是寻找可行解,产生过滤条件。 过滤条件:是满足目标函数值优于计算过的可行解目标函数值的约束条件。 下面举例说明求解0-1型整数规划的隐枚举法 例4.6 : 目标函数 max z=3x1-2x2+5x3 约束条件: x1+2x2-x3≤2 (1) x1+4x2+x3≤4 (2) x1+x2≤3 (3) 4x2+x3≤6 (4) x1,x2,x3=0或1 (5) 解题时先通过试探的方法找一个可行解,容易看出(x1,x2,x3)=(1,0,0),满足(1)~(4)条件,算出相应的目标函数值z=3。 我们在求最优解时,对于极大化问题,当然希望z≥3,于是增加一个约束条件: 3x1-2x2+5x3≥3 ◎ 称为过滤的条件(filtering constraint)。这样,原问题的 线性约束条件就变成5个。 用全部枚举的方法,3个变量共有23=8个解,原来4个约束条 件,共需32次运算。 现在增加了过滤条件◎,如按下述方法进行,就可减少运算 次数。将5个约束条件按◎~(4)顺序排好。 对每个解,依次代入约束条件左侧,求出数值,看是否适合 不等式条件,如某一条件不适合,同行以下各条件就不必再 检查,因而就减少了运算次数。 在计算过程中,若遇到z值已超过条件◎右边的值,应改变条件◎,使右边值为迄今为止最大者, 然后继续作。 例如,当检查点(0,0,1)时,因z=5(>3), 所以改进过滤条件,用3x1-2x2+5x3≥5 ◎′代替◎,继续进行。 这种对过滤条件的改进,更可以减少计算量。 再改进过滤条件,用3x1-2x2+5x3≥8◎″代替◎′,再继续进行。 至此,z值已不能改进,即得到最优解,解答如前,但计算已简化。 本例计算过程实际只作16次运算。 即求得最优解(x1,x2,x3)=(1,0,1), max z=8 注意: 一般常重新排列xi的顺序使目标函数中xi的系数是递增(不减)的,在上例中, 改写 z=3x1-2x2+5x3=-2x2+3x1+5x3 因为-2,3,5是递增的,变量(x2,x1,x3)也按下述顺序取值:(0,0,0), (0,0,1),(0,1,0),(0,1,1),…, 这样,最优解容易比较早的发现。 再结合过滤条件的改进,更可使计算简化 步骤: (1)、用试探法,求出一个可行解,以它的目标值作为当前最好值Z0 (2)、增加过滤条件Z? Z0 (3)、将xi 按ci由小?大排列。最小化问题反之。 maxZ = 3x1 -2x2+5x3 x1 +2x2 - x3? 2 (1) x1 +4x2 +x3? 4 (2) x1 + x2 ? 3 (3) 4x2+x3? 6 (4) x1 , x2 , x3为0或1 解:1.观察得解(x1 , x2 , x3 )=(1 ,0 ,0) ,Z0 =

文档评论(0)

xx88606 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档