- 1、本文档共100页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
一、整数规划的模型 二、分枝定界法 (二)、例题 练习:用分枝定界法求解整数规划问题 (图解法) 例2、用分枝定界法求解整数规划问题 (单纯形法) 练习:用分枝定界法求解整数规划问题 (单纯形法) 算法步骤 四、0-1 整数规划 练习:用隐枚举法求解0—1规划问题 五、指派问题 例1: 例2、 练习: 4/3 -1/3 1 0 0 4 x3 0 -5/9 2/9 0 1 0 4/3 x2 4 2/9 1/9 0 0 1 8/3 x1 11 -2/9 x5 -19/9 x4 0 0 0 -Z x3 x2 x1 b XB CB 6 0 -1 1 0 0 0 x3 0 -5/2 0 1/2 0 1 0 3 x2 4 1 0 0 0 0 1 2 x1 11 0 1 x5 -2 1/2 x4 -1 -9/2 s1 0 0 0 -Z 0 0 0 3 x5 0 x3 x2 x1 b XB CB (2 ,3) 0-1 整数规划是一种特殊形式的整数规划,这时的决策变量xi 只取两个值0或1,一般的解法为隐枚举法。 例1、求解下列0-1 规划问题 解:对于0-1 规划问题,由于每个变量只取0,1两个值,一般会用穷举法来解,即将所有的0,1 组合找出,使目标函数达到极值要求就可求得最优解。但此法太繁琐,工作量相当大。而隐枚举法就是在此基础上,通过加入一定的条件,就能较快的求得最优解。 × 2 6 ( 1, 1, 1 ) × 3 ( 1, 1, 0 ) 8 ∨ 0 2 1 1 ( 1, 0, 1 ) × 1 5 ( 0, 1, 1 ) 3 ∨ 1 1 1 0 ( 1, 0, 0 ) -2 ∨ 2 4 1 4 ( 0, 1, 0 ) 5 ∨ -1 1 0 1 ( 0, 0, 1 ) 0 ∨ 0 0 0 0 ( 0, 0, 0 ) 是∨ 否× (1) (2) (3) (4) Z 值 满足条件 约束条件 x1 . x2. x3 由上表可知,问题的最优解为 X*=( x1 =1 x2=0 x3=1 ) 由上表可知: x1 =0 x2=0 x3=1 是一个可行解,为尽快找到最优解,可将3 x1-2 x2+5 x3 ≥5 作为一个约束,凡是目标函数值小于5 的组合不必讨论,如下表。 × 4 ( 1, 1, 1 ) × 1 ( 1, 1, 0 ) 8 ∨ 8 0 2 1 1 ( 1, 0, 1 ) × 3 ( 1, 0, 0 ) × 3 ( 0, 1, 1 ) × -2 ( 0, 1, 0 ) 5 ∨ 5 -1 1 0 1 ( 0, 0, 1 ) 0 ∨ 0 0 0 0 0 ( 0, 0, 0 ) 是∨ 否× (0) (1) (2) (3) (4) Z 值 满足条件 约束条件 x1 . x2. x3 例2、求解下列0-1 规划问题 解:由于目标函数中变量x1, x2 , x4 的系数均为负数,可作如下变换: 令 x1 =1- x1′ , x2 =1- x2′, x3= x3′, x4 =1- x4′带入原题中,但需重新调整变量编号。令 x3′ = x1′, x4′ = x2′得到下式。 可以从( 1,1,1,1 )开始试算, x′(3)=( 1,1,0,1 )最优解。 ∴ x(3)=( 1,0,1,0 )是原问题的最优解,Z* =-2 例3、求解下列0-1 规划问题 令 y1=x5, y2=x4,
您可能关注的文档
- 3.日常维护及注意事项课案.ppt
- 5.3含蜡原油管道的蜡沉积及清管课案.ppt
- 3.山美版五上品社祝福您-老师.课案.ppt
- 太阳能电池选读.pptx
- 太乙穴与图片欣赏选读.pptx
- 泰国游玩攻略选读.docx
- 泰伦特中压载波选读.pptx
- 谈几何画板设计《一次函数与一元一次不等式的关系》的教学选读.docx
- 3.实施2015版药典无菌实验室改造解决方案课案.ppt
- 谈实际工作中创新的重要性选读.pptx
- 浙江省嘉兴市2024-2025学年高三上学期9月基础测试技术试卷-高中信息技术 Word版无答案.docx
- 1-1 记录个人健康数据——数据的形式与记录载体 四上信息科技.pptx
- Z20名校联盟 (浙江省名校新高考研究联盟) 2024-2025学年高三上学期第一次联考技术试卷-高中信息技术 Word版无答案.docx
- 课时1 技术的发展 技术的价值 学案 苏教版 通用技术 技术与设计1.doc
- 浙江省山水联盟2022-2023学年高三上学期8月联考通用技术试题 Word版无答案.docx
- 课时1 技术与设计的关系 设计的一般原则 学案 苏教版 通用技术 技术与设计1.doc
- 课时2 技术的性质 学案 苏教版 通用技术 技术与设计1.doc
- 浙江省金华市卓越联盟2023-2024学年高二下学期5月阶段联考(期中)技术试题-高中通用技术 Word版无答案.docx
- 课时2 技术的性质 课件(共77张ppt)苏教版 通用技术 技术与设计1.pptx
- 验收卷(一) 走进技术世界、技术世界中的设计 课件 苏教版 通用技术 技术与设计1.pptx
文档评论(0)