版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
设纯整数规划松弛问题的最优解设xi不为整数，4/8/2025将分离成一个整数与一个非负真分数之和：则有等式两边都为整数并且有4/8/2025加入松弛变量si得此式称为以xi行为源行（来源行）的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。将Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。则4/8/2025例如，x1行：移项：令加入松弛变量s1得同理，对于x2行有：4/8/2025如果在对偶单纯形法中原切割方程的松弛变量仍为基变量，则此松弛变量所在列化为单位向量后就可以去掉该行该列，再切割。【例】已知整数规划【解】不考虑整数约束，松弛问题的最优表如下4/8/2025cj3200bCBXBx1x2x3x42x2011/2－1/25/23x110－1/43/413/4λj00－1/4－5/4最优表最优解X=(－1/2，3/4，0，0)T，x1、x2不满足整数要求，选择x2行进行分割：得到Gomory约束添加到最优表中，得4/8/2025cj32000bCBXBx1x2x3x4x52x2011/2－1/205/23x110－1/43/4013/40x500－1/2－1/21－1/2λj00－1/4－5/402x2010－1½23x11001－1/27/20x30011－21λj000－1－1/2x1行：Gomory约束添加到最优表中，得4/8/2025cj320000bCBXBx1x2x3x4x5x62x2010－1½023x11001－1/407/30x30011－1010x60000－1/21－1/2λj000－1－1/202x2010－10213x110010－140x300110－430x600001－21λj000－10－14/8/2025得到整数最优解：X＝(4，1)，Z＝14注1：Gomory约束可写为注2：Gomory约束只是割去线性规划可行域的一部分，保留了全部整数解。用图解法表示：4/8/202513/4,5/2松弛问题第一次切割4,1第二次切割x1+x2≤54/8/2025作业：教材P134T5.30—1规划指派问题Exit1.领会
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 25年公司级安全培训考试试题及答案原创题
- 《劳动法与社会保障法》课件上编-第一章
- 网架钢结构企业ESG实践与创新战略研究报告
- 缆索起重机企业县域市场拓展与下沉战略研究报告
- 西部会展企业县域市场拓展与下沉战略研究报告
- 弹跳试验台企业ESG实践与创新战略研究报告
- 农林牧渔机械企业县域市场拓展与下沉战略研究报告
- 立式加工中心企业ESG实践与创新战略研究报告
- 弹簧夹头企业县域市场拓展与下沉战略研究报告
- 2025年合同能源管理项目合作计划书
- JTG D70-2-2014 公路隧道设计规范 第二册 交通工程与附属设施
- 有机超市创业计划书
- T-CARM 002-2023 康复医院建设标准
- 车展安保方案
- 生态安全的主要内容
- 人工智能行业的智能客服技术人员培训
- 《血管活性药物静脉输注》标准解读护理课件
- 《IPV4地址简介》课件
- 天然气管道风险评估模型
- 血液透析发生失衡综合症的原因及预防
- 儿童滑膜炎护理查房
评论
0/150
提交评论