用对偶单纯形法求解线性规划问题

用对偶单纯形法求解线性规划问题

ID:6775686

大小:85.00 KB

页数:4页

时间:2018-01-25

用对偶单纯形法求解线性规划问题_第1页
用对偶单纯形法求解线性规划问题_第2页
用对偶单纯形法求解线性规划问题_第3页
用对偶单纯形法求解线性规划问题_第4页
资源描述:

《用对偶单纯形法求解线性规划问题》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、例4-7用对偶单纯形法求解线性规划问题.Minz=5x1+3xs.t.-2x1+3x≥63x1-6x≥4Xj≥0(j=1,2)解:将问题转化为Maxz=-5x1-3xs.t.2x1-3x+x3=-6-3x1+6x+x4≥-4Xj≥0(j=1,2,3,4)其中,x3,x4为松弛变量,可以作为初始基变量,单纯形表见表4-17.表4-17例4-7单纯形表Cj-6-3-40CBXBbX1X2X3X4迭代0次0X4-62[-3]100X5-4-36010-5-300CBXBbX1X2X3X4迭代1次-3X42-2/31-1/300X3-1610216-70-10在表4-

2、17中,b=-16<0,而y≥0,故该问题无可行解.注意:对偶单纯形法仍是求解原问题,它是适用于当原问题无可行基,且所有检验数均为负的情况.若原问题既无可行基,而检验数中又有小于0的情况.只能用人工变量法求解.在计算机求解时,只有人工变量法,没有对偶单纯形法.3.对偶问题的最优解由对偶理论可知,在原问题和对偶问题的最优解之间存在着密切的关系,可以根据这些关系,从求解原问题的最优单纯形表中,得到对偶问题的最优解.(1)设原问题(p)为Minz=CXs.t.则标准型(LP)为Maxz=CXs.t.其对偶线性规划(D)为Maxz=bTYs.t.用对偶单纯形法求解(L

3、P),得最优基B和最优单纯形表T(B)。对于(LP)来说,当j=n+i时,有Pj=-ei,cj=0从而,在最优单纯形表T(B)中,对于检验数,有(σn+1,σn+2…σn+m)=(cn+1,cn+2…,cn+m)-CBB-1(Pn+1,Pn+2…,Pn+m)=-CBB-1(-I)于是,Y*=(σn+1,σn+2…σn+m)T。可见,在(LP)的最优单纯形表中,剩余变量对应的检验数就是对偶问题的最优解。同时,在最优单纯形表T(B)中,由于剩余变量对应的系数所以B-1=(-yn+1,-yn+2…-yn+m)例4-7求下列线性规划问题的对偶问题的最优解。Minz=6

4、x1+8xs.t.x1+2x≥203x1+2x≥50Xj≥0(j=1,2)解:将问题转化为Maxz=-6x1-8xs.t.-x1—2x+x3=20-3x1-2x+x4=50Xj≥0(j=1,2,3,4)用对偶单纯形法求解如表表4-18例4-8单纯形表Cj-6-800CBXBbX1X2X3X4迭代0次-8X45/201-3/41/4-6X515101/2-1/2-1100031在引入松弛变量化为标准型之后,约束等式两侧同乘-1,能够立即得到检验数全部非正的原规划基本解,可以直接建立初始对偶单纯形表进行求解,非常方便。对于有些线性规划模型,如果在开始求解时不能很快

5、使所有检验数非正,最好还是采用单纯形法求解。因为,这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看,可以说,对偶单纯形法是单纯形法的一个补充。除此之外,在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法,可以简化计算。例4-9:求解线性规划问题:Minf=2x1+3x2+4x3S.t.x1+2x2+x3≥32x1-x2+x3≥4x1,x2,x3≥0标准化:Maxz=-2x1-3x2-4x3s.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥0表格对偶单纯形法Cj-6-800CBXBbX1X2X

6、3X4迭代0次-8X45/201-3/41/4-6X515101/2-1/2-1100031

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。