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

2.7 参数线性规划,参数aij、bi、cj在什么范围内变化时最优解不变是实际问题中常常要研究的问题，当这些参数超出这个范围时，最优解会发生怎样的变化，即为参数线性规划要研究的问题。,【例】线性规划问题,maxZ(l)=2x1+x2 5x2 15 6x1+2x2 24 x1+x2 5+l x1,x2 0,第三个约束右端不断增大，分析最优解会发生怎样的变化？,此时l 0,参数线性规划求解步骤,1、令l=0求解得最终单纯形表,2、将参数的变化反映到最终单纯形表中；因,反映到最终单纯形表中,3、让 l逐步增大，观察原问题与对偶问题解的变化，看哪一个首先出现非可行解。,15/2-(15/2)l0,x1=7/2-(1/2)l,x2=3/2+(3/2)l,Z*=17/2+(1/2)l,7/2-(1/2)l0,3/2+(3/2)l0,当0l1 表中解为最优解。此时,当 l1时，用对偶单纯形法迭代,注：不用讨论7/2-(1/2)l0的情况，因为此时，15/2-(15/2)l也是负的，且绝对值更大。因此出基项仍然是x3（第一行）。,当 l继续增大，原问题与对偶问题都保持可行解，故计算至此结束。,结论：01,x1=3,x2=3,maxZ=9,【图示】目标函数Z(l)与l的变化关系图,9,l1,Z=17/2+(1/2)l,l1,Z=9,注：问题中多个参数变化时，应使目标函数z(l)是l的线性函数。,【例】求解下述参数线性规划问题,maxZ=（2+l)x1+(1+2l)x2 5x2 15 6x1+2x2 24 x1+x2 5 x1,x2 0,【解】按参数线性规划求解问题的第一、二步，令l=0求得最优解，并将cj的变化值反映到最终单纯形表中。,反映到最终单纯形表中,当-1/5l1时，表中解为最优解。此时,当l1，变量x4的检验数为正值，用单纯形法继续迭代得,z*=7/2(2+l)+3/2(1+2l)=17/2+13l/2,-1/4+l/40,-1/2-5l/2 0,-1/5l1,当l-1/5，变量x5的检验数为正值，用单纯形法继续迭代得,当l1，原问题与对偶问题都保持可行解，故计算至此结束。,工厂的最优计划为x1=2，x2=3，z*=2(2+l)+3(1+2l)=7+8l,当l1，变量x4的检验数为正值，用单纯形法继续迭代得,当l-1/5,当 l-1/5时，变量x5的检验数为正值，用单纯形法继续迭代得,当l-1/5，变量x5的检验数为正值，用单纯形法继续迭代得,当-2l-1/5，原问题与对偶问题都保持可行解，故计算至此结束。,工厂的最优计划为x1=4，x2=0，x3=15，z*=4*(2+l)=8+4l,1/3+5/3l 0,-1/3-1/6l 0,-2l-1/5,l-2,Z(l)8+4l0没必要讨论,【图示】目标函数Z(l)与l的变化关系图,l,Z(l),1,2,l,8.5,15,22.5,目标函数z(l)是l的线性函数。,当-1/5l1时，z*=17/2+13l/2,-1,当l1，z*=7+8l,当-2l-1/5，z*=8+4l,思考题,某文教用品厂利用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每天白坯纸供应量为3万kg。如果单独生产各种产品时，每个工人每天生产原稿纸30捆，或日记本30打，或练习本30箱。书籍原材料消耗为：每捆原稿纸用白坯纸10/3kg，每打日记本用白坯纸40/3kg，每箱练习本用白坯纸80/3kg。又知每生产一捆原稿纸可盈利2元，每生产一打日记本可盈利3元，每生产一箱练习本可盈利1元。试决定：（1）在现有生产条件下工厂盈利最大的生产方案；（2）如果白坯纸的供应数量不变，当工人人数不足时，可招收临时工，临时工工资支出为每人每天40元，问该厂要不要招收临时工，招多少人？,