欢迎来到天天文库
浏览记录
ID:56816428
大小:908.00 KB
页数:13页
时间:2020-06-30
《运筹学基础对偶线性规划3.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、§2.7参数线性规划参数aij、bi、cj在什么范围内变化时最优解不变是实际问题中常常要研究的问题,当这些参数超出这个范围时,最优解会发生怎样的变化,即为参数线性规划要研究的问题。【例】线性规划问题maxZ(l)=2x1+x25x2≤156x1+2x2≤24x1+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≤156x1+2x2≤24x1+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没必要讨论
此文档下载收益归作者所有