下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、.例4-7 用对偶单纯形法求解线性规划问题. Min z =5x1+3x s.t. -2 x1 + 3x6 3 x1 - 6 x4 Xj0(j=1,2)解: 将问题转化为 Max z = -5 x1 - 3 x s.t. 2 x1 - 3x+ x3 = -6 -3 x1 + 6 x+ x4-4 Xj0(j=1,2,3,4)其中,x3 ,x4 为松弛变量,可以作为初始基变量,单纯形表见表4-17. 表4-17 例4-7单纯形表Cj-6-3-40CBXBbX1X2X3X4迭代0次0X4-62-3100X5-4-36010-5-300CBXBbX1X2X3X4迭代1次-3X42-2/31-1/300
2、X3-1610216-70-10在表4-17中,b=-160,而y0,故该问题无可行解.注意: 对偶单纯形法仍是求解原问题,它是适用于当原问题无可行基,且所有检验数均为负的情况.若原问题既无可行基,而检验数中又有小于0的情况.只能用人工变量法求解.在计算机求解时,只有人工变量法,没有对偶单纯形法.3.对偶问题的最优解由对偶理论可知,在原问题和对偶问题的最优解之间存在着密切的关系,可以根据这些关系,从求解原问题的最优单纯形表中,得到对偶问题的最优解.(1) 设原问题(p)为 Min z=CX s.t. 则标准型(LP)为 Max z=CX s.t. 其对偶线性规划(D)为 Max z=bTY s
3、.t. 用对偶单纯形法求解(LP),得最优基B和最优单纯形表T(B)。对于(LP)来说,当j=n+i时,有Pj=-ei,cj=0从而,在最优单纯形表T(B)中,对于检验数,有(n+1,n+2n+m)=(cn+1,cn+2,cn+m)-CBB-1(Pn+1,Pn+2,Pn+m)=- CBB-1 (-I)于是,Y*=(n+1,n+2n+m)T 。可见,在(LP)的最优单纯形表中,剩余变量对应的检验数就是对偶问题的最优解。同时,在最优单纯形表T(B)中,由于剩余变量对应的系数所以 B-1 =(-y n+1,-y n+2-yn+m) 例4-8 求下列线性规划问题的对偶问题的最优解。 Min z =6x
4、1+8x s.t. x1 + 2x20 3 x1 + 2x50 Xj0(j=1,2)解: 将问题转化为 Max z =-6x1-8x s.t. -x1 2x + x3=20 -3 x1 - 2x+ x4 =50 Xj0(j=1,2,3,4)用对偶单纯形法求解如表 表4-18 例4-8单纯形表Cj-6-800CBXBbX1X2X3X4迭代0次-8X45/201-3/41/4-6X515101/2-1/2-1100031在引入松弛变量化为标准型之后,约束等式两侧同乘-1,能够立即得到检验数全部非正的原规划基本解,可以直接建立初始对偶单纯形表进行求解,非常方便。 对于有些线性规划模型,如果在开始求解时不能很快使所有检验数非正,最好还是采用单纯形法求解。因为,这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看,可以说,对偶单纯形法是单纯形法的一个补充。除此之外,在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法,可以简化计算。例4-9:求解线性规划问题: Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0 标准化:Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年03月山东枣庄滕州市校园招考聘用中小学教师20人笔试历年典型题及考点剖析附带答案含详解
- 2024年03月安徽合肥市瑶海区新任教师招考聘用40人笔试历年典型题及考点剖析附带答案含详解
- 2024年03月国家文物局考古研究中心招考聘用出站博士后笔试历年典型题及考点剖析附带答案含详解
- 2024年03月四川省广元市朝天区2024年上半年面向社会公开考试招考41名事业单位工作人员笔试历年典型题及考点剖析附带答案含详解
- 2024年03月四川凉山宁南县事业单位招考聘用13人笔试历年典型题及考点剖析附带答案含详解
- 2024年03月云南西双版纳景洪市人力资源和社会保障局急需紧缺人才校园招考聘用笔试历年典型题及考点剖析附带答案含详解
- 2024年03月中新天津生态城教育系统教职人员(在职)招考聘用143人笔试历年典型题及考点剖析附带答案含详解
- 2024年03月中国农业银行陕西省分行春季招考聘用316人笔试历年典型题及考点剖析附带答案含详解
- 生产过程控制程序
- 英语专升本单选500题
- 六年级下学期小升初模拟考试英语试卷共七套
- 关于PPP政策有关问题的解读
- 互联网供应链金融创新模式研究以中企云链为例
- 2024燃气发电企业安全生产标准化实施规范
- 智能手环营销方案
- 2024年山东高速集团总部部分业务技术岗位内部选聘9人公开引进高层次人才和急需紧缺人才笔试参考题库(共500题)答案详解版
- 2024年广西南宁市中考物理适应性试卷
- 施工总承包管理方案
- 三角形的面积市公开课特等奖市赛课微课一等奖课件
- JB-T 8168-2023 脉冲电容器及直流电容器
- 幼儿园儿童体检结果反馈单.doc
评论
0/150
提交评论