运筹学基础对偶线性规划

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

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

2、/4-15/27/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-

3、1/23/2+(3/2)l010-1/43/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继续增大，原问题与对偶问题都保持可行解，故计算至此结束。结论：0

4、2=3/2+(3/2)l,maxZ=17/2+(1/2)ll>1,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比值CBXB

5、b检验数jx1x2x3x4x52+l1+2l00015/20015/4-15/27/21001/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检验

6、数jx1x2x3x4x52+l1+2l0006004/51-6210-1/5013011/500x4x1x202+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/2

7、l2l0-1/4-1/2当l＜-1/5时，变量x5的检验数为正值，用单纯形法继续迭代得-17/2-13l/2000-1/4+l/4-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+

8、5/3l≤0-1/3-1/6l≤0-2≤l≤-1/5l＜-2,Z(l)＝8+4l<0没必要讨论