下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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-2030全球与中国海上船舶涂装服务市场现状及未来发展趋势
- 关注一汽集团发布阩旗技术“SIGHT(洞见)531”发展战略
- 2024年南乐县《高等数学(一)》(专升本)考前冲刺试题含解析
- 2024年云南省红河哈尼族彝族自治州金平苗族瑶族傣族自治县《高等数学(一)》(专升本)考前冲刺预测试卷含解析
- 宽带账号安全威胁及防范方法
- 职业道德教育的主体性分析
- 电梯维修施工合同范本
- 人才委托聘用协议书
- 区域经销协议
- 就业合同范本2011
- GB/T 43902-2024绿色制造制造企业绿色供应链管理实施指南
- 2024年山东高速集团总部部分业务技术岗位内部选聘9人公开引进高层次人才和急需紧缺人才笔试参考题库(共500题)答案详解版
- HYT 081-2005 红树林生态监测技术规程
- 设计创意生活智慧树知到期末考试答案2024年
- 压疮指南解读
- 《杜绝校园暴力共建和谐校园》主题班会课件(共23张)
- 我的动物朋友.ppt
- 带状疱疹中医治疗课件
- 第四章 船舶稳性.ppt
- 20世纪英国文学
- 陕西水利工程常用表格.doc
评论
0/150
提交评论