运筹学基础对偶线性规划3.ppt

运筹学基础对偶线性规划3.ppt

ID:56816428

大小:908.00 KB

页数:13页

时间:2020-06-30

运筹学基础对偶线性规划3.ppt_第1页
运筹学基础对偶线性规划3.ppt_第2页
运筹学基础对偶线性规划3.ppt_第3页
运筹学基础对偶线性规划3.ppt_第4页
运筹学基础对偶线性规划3.ppt_第5页
资源描述:

《运筹学基础对偶线性规划3.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、§2.7参数线性规划参数aij、bi、cj在什么范围内变化时最优解不变是实际问题中常常要研究的问题,当这些参数超出这个范围时,最优解会发生怎样的变化,即为参数线性规划要研究的问题。【例】线性规划问题maxZ(l)=2x1+x25x2≤156x1+2x2≤24x1+x2≤5+lx1,x2≥0第三个约束右端不断增大,分析最优解会发生怎样的变化?此时l≥0参数线性规划求解步骤1、令l=0求解得最终单纯形表2、将参数的变化反映到最终单纯形表中;因反映到最终单纯形表中Cj比值CBXBb检验数jx1x2x3x4x52100015/2-(15/2)l0015/4-15/27/2-

2、(1/2)l1001/4-1/23/2+(3/2)l010-1/43/2x3x1x2021-17/2-(1/2)l000-1/4-1/23、让l逐步增大,观察原问题与对偶问题解的变化,看哪一个首先出现非可行解。15/2-(15/2)l≥0x1=7/2-(1/2)lx2=3/2+(3/2)lZ*=17/2+(1/2)l7/2-(1/2)l≥03/2+(3/2)l≥0当0≤l≤1表中解为最优解。此时Cj比值CBXBb检验数jx1x2x3x4x52100015/2-(15/2)l0015/4-15/27/2-(1/2)l1001/4-1/23/2+(3/2)l010-1/43/

3、2x3x1x2021-17/2-(1/2)l000-1/4-1/2当l>1时,用对偶单纯形法迭代注:不用讨论7/2-(1/2)l≤0的情况,因为此时,15/2-(15/2)l也是负的,且绝对值更大。因此出基项仍然是x3(第一行)。Cj比值CBXBb检验数jx1x2x3x4x521000-1+l00-2/15-1/61310-1/151/603011/500x5x1x2021-900-1/15-1/30当l继续增大,原问题与对偶问题都保持可行解,故计算至此结束。结论:01,

4、x1=3,x2=3,maxZ=9【图示】目标函数Z(l)与l的变化关系图lZ(l)12l8.51522.59l≤1,Z=17/2+(1/2)ll>1,Z=9注:问题中多个参数变化时,应使目标函数z(l)是l的线性函数。【例】求解下述参数线性规划问题maxZ=(2+l)x1+(1+2l)x25x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0【解】按参数线性规划求解问题的第一、二步,令l=0求得最优解,并将cj的变化值反映到最终单纯形表中。反映到最终单纯形表中Cj比值CBXBb检验数jx1x2x3x4x52+l1+2l00015/20015/4-15/27/2

5、1001/4-1/23/2010-1/43/2x3x1x202+l1+2l-17/2l2l0-1/4-1/2当-1/5≤l≤1时,表中解为最优解。此时当l>1,变量x4的检验数为正值,用单纯形法继续迭代得z*=7/2(2+l)+3/2(1+2l)=17/2+13l/2-17/2-13l/2000-1/4+l/4-1/2-5l/2-1/4+l/4≤0-1/2-5l/2≤0-1/5≤l≤1当l<-1/5,变量x5的检验数为正值,用单纯形法继续迭代得Cj比值CBXBb检验数jx1x2x3x4x52+l1+2l0006004/51-6210-1/5013011/500x4x1x2

6、02+l1+2l-7-8l001/5-1/5l0-2-l当l>1,原问题与对偶问题都保持可行解,故计算至此结束。工厂的最优计划为x1=2,x2=3,z*=2(2+l)+3(1+2l)=7+8l当l≥1,变量x4的检验数为正值,用单纯形法继续迭代得当l<-1/5Cj比值CBXBb检验数jx1x2x3x4x52+l1+2l00015/20015/4-15/27/21001/4-1/23/2010-1/43/2x3x1x202+l1+2l-17/2l2l0-1/4-1/2当l<-1/5时,变量x5的检验数为正值,用单纯形法继续迭代得-17/2-13l/2000-1/4+l/4-

7、1/2-5l/2当l<-1/5,变量x5的检验数为正值,用单纯形法继续迭代得Cj比值CBXBb检验数jx1x2x3x4x52+l1+2l0001505100411/301/60102/30-1/61x3x1x502+l0-8-4l01/3+5/3l0-1/3-1/6l0当-2≤l<-1/5,原问题与对偶问题都保持可行解,故计算至此结束。工厂的最优计划为x1=4,x2=0,x3=15,z*=4*(2+l)=8+4l1/3+5/3l≤0-1/3-1/6l≤0-2≤l≤-1/5l<-2,Z(l)=8+4l<0没必要讨论

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

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

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