- 1、本文档共68页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
1.整数规划的数学模型2.分枝定界法3.割平面法4.0-1型整数规.ppt
1.整数规划的数学模型 2.分枝定界法 3.割平面法 4.0-1型整数规划 5.指派问题 整数规划的数学模型 max(min)(c1 x1+ c2 x2 +…+ cn xn ) a11 x1+ a12 x2 +…+ a1n xn ? (=,?) b1 a21 x1+ a22 x2 +…+ a2n xn ? (=,?) b2 ……... am1 x1+ am2 x2 +…+ amn xn ? (=,?) bm x1~n ? 0 且取整数 纯整数规划: 所有变量都有取整约束 混合整数规划: 只有部分变量有取整约束 分枝定界法 1.分枝定界法的基本思路 2.第65页例5-1 3.练习题 分枝定界法的基本思路 ? 分枝定界法的基本思路 第65页例5-1 max z = 40x1 + 90x2 9x1 + 7x2 ? 56 7x1 +20x2 ? 70 x1,x2 ? 0且取整 ? 用分枝定界法解例5-1 1.求解相应的线性规划L0 max z = 40x1 + 90x2 9x1 + 7x2 ? 56 7x1 +20x2 ? 70 x1,x2 ? 0 用分枝定界法解例5-1 x2 5 9x1+7x2=56 4 3 2 7x1+20x2=70 1 0 1 2 3 4 5 6 7 8 9 10 x1 L0 : x* = (4.81, 1.82), Z* =356 ? 用分枝定界法解例5-1 2.将L0分解为L1和L2 L1 :max z = 40x1 + 90x2 9x1 + 7x2 ? 56 7x1 +20x2 ? 70 x1 ? 4 x1,x2 ? 0 用分枝定界法解例5-1 3.分解L1形成L3、L4,其中: L3 = {L1, x2?2} L4 = {L1, x2?3} L3 : X* = (4, 2), Z* = 340 L4 : X* = (1.42, 3), Z* = 327 (1)取下界min=340(L3); (2)舍弃L4 用分枝定界法解例5-1 4.分解L2形成L5、L6,其中: L5 = {L2, x2?1} L6 = {L2, x2?2} L5 : X* = (5.44, 1), Z* = 308 L6 : 无可行解 (1)舍弃L5、L6; (2)得最优解X* = (4, 2), Z* = 340。 ? 例5-1求解过程示意图 练习题 max z = 2x1 + 5x2 + 4x3 x1 + x2 + x3 ? 12 x1 + 2x2 ? 15 4x1 + 5x3 ? 26 x1~3 ? 0且取整 求解练习题 首先求解线性规划L0 : max z = 2x1 + 5x2 + 4x3 x1 + x2 + x3 + x 4 = 12 x1 + 2x2 + x5 = 15 4x1 +5x3 + x6 = 26 x1~6 ? 0 求解练习题 ? 求解练习题 ? 求解练习题 ? 求解练习题 ? 求解练习题 割平面法 1.割平面法的基本思路 2.例 3.练习题 割平面法的基本思路 同分枝定界法一样,割平面法也是一种利用连续模型求解非连续问题的常用方法。割平面法的基本思路是:当得到的解不满足取整约束时,就设法在问题上增加一个约束条件,把包含这个非整数解的一部分可行域从原来的可行域中割除,但不割掉任何一个整数可行解。这个新增加的约束条件就称为割平面。 例 max z = x1 + x2 - x1 + x2 ? 1 3x1 + x2 ? 4 x1,x2 ? 0且取整 ? 用割平面法解例 1.求解相应的线性规划L0 max z = x1 + x2 - x1 + x2 ? 1 3x1 + x2 ? 4 x1,x2 ? 0 ? 用割平面法解例 非整数解,为建立割平面,首先考虑非整
您可能关注的文档
- 1.Manpower市场实习生地点上海本科2个月.PDF
- 1.暑期国际实习生项目-ITIntern适合专业计算机类.PDF
- 2014年沧州银行股份有限公司次级债券跟踪评级报告.PDF
- 2017年度报告公告编号2.PDF
- 2017年度物流企业营商环境调查报告.PDF
- 2018年高考温馨提示.doc
- 30轻症中暑用刮痧.doc
- AA30空气辅助式喷枪.PDF
- ADUCM360361常见问题解答.PDF
- AFOLU项目项目表格1.0版.PDF
- 2024年中国钽材市场调查研究报告.docx
- 2024年中国不锈钢清洗车市场调查研究报告.docx
- 2024年中国分类垃圾箱市场调查研究报告.docx
- 2024年中国水气电磁阀市场调查研究报告.docx
- 2024年中国绿藻片市场调查研究报告.docx
- 2010-2023历年初中毕业升学考试(青海西宁卷)数学(带解析).docx
- 2010-2023历年福建厦门高一下学期质量检测地理卷.docx
- 2010-2023历年初中数学单元提优测试卷公式法(带解析).docx
- 2010-2023历年初中毕业升学考试(山东德州卷)化学(带解析).docx
- 2010-2023历年初中毕业升学考试(四川省泸州卷)化学(带解析).docx
最近下载
- 宜兴市各级文物保护单位一览表.docx
- 国学《千字文》之《渠荷的历》个人原创课件公开课课件.pptx VIP
- 老旧小区改造工程项目可行性研究报告.docx VIP
- 《GB∕T 45003-2024职业健康安全管理 工作中的心理健康安全:管理社会心理风险 指南》解读和应用指导材料(2024A0-雷泽佳).docx VIP
- 妙事多音乐--张老师 -培训讲解.ppt
- 基础化学高职高专第五版高琳第十章氧化还原平衡.pptx
- 在线网课学习课堂《英语视听说(西京学院 )》单元测试考核答案.docx
- 电子商务平台商家入驻协议书模板.doc
- 北京四中2023学年度上学期初中九年级期中考试物理试卷.docx
- 自然教育研学方案.pptx
文档评论(0)