管理运筹学Chapter 2.3 对偶与灵敏度分析1

线性规划,ChapterTwo：LP,第三节对偶与灵敏度分析,1.线性规划问题的对偶关系2.对偶单纯形法3.灵敏度分析4.对偶的经济解释,1.线性规划问题的对偶关系,1.1对偶问题的提出,从多个角度观察同一个问题会得出不同的看法从多个角度对一个实际问题建模会怎么样？,1.1对偶问题的提出,例2-20某企业计划生产甲、乙两种产品，该两种产品均需经A、B、C、D四种不同设备上加工，按工艺资料规定，在各种不同设备上的加工时间及设备加工能力、单位产品利润如表2-8所示。问:如何安排产品的生产计划,才能使企业获利最大?,1.1对偶问题的提出,根据题意，可以建立如下的线性规划模型：,1.1对偶问题的提出,假定另有一个企业意图收购生产企业拥有的资源，至少应付出多少代价，才能使生产企业愿意放弃生产活动，而选择出售资源呢？显然，对等量资源出售的原则是不低于生产企业自己组织生产活动所获得的利润。在获得了不低于组织生产的收入后，为了使资源出售的价格符合市场规律，具有一定的竞争力，生产企业所获得总收入应尽可能的小。,1.1对偶问题的提出,设企业所拥有的四种资源定价分别为y1，y2，y3，y4，建立的线性规划模型如下：后一个线性规划模型与原来的线性规划模型是对同一个问题，从两个角度进行的描述。如果称前者为原问题，则后者称为它的对偶问题。反之亦然。,1.1对偶问题的提出,最大生产利润模型设生产甲产品为X1件，乙产品为X2件则,资源最低售价模型设第i种资源价格为yi（i=1,2,3,4）则有,1.1对偶问题的提出,原问题,对偶问题,1.2其他形式的对偶问题,1.2其他形式的对偶问题,1.2其他形式的对偶问题,例2-22,1.2其他形式的对偶问题,则由表中原问题和对偶问题的对应关系，可以直接写出上述问题的对偶问题,习题,1.3对偶问题的性质,对称性对偶问题的对偶是原问题。弱对偶性若X是原问题的可行解，Y是对偶问题的可行解。则存在CXYb。无界性若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解,1.3对偶问题的性质,弱对偶性推论1：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。推论2：若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,1.3对偶问题的性质,最优性若X是原问题的可行解，Y是对偶问题的可行解，且有CX=Yb，则X是原问题的最优解，Y是其对偶问题的最优解。对偶定理（强对偶性）若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。,GO,1.3对偶问题的性质,兼容性互补基本解：原问题单纯形表的检验数行对应其对偶问题的一个基本解，且二者目标函数值相等。互补松弛性在线性规划规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。,GO,GO,1.3对偶问题的性质,例2-24已知线性规划问题如下，试用对偶理论分析该问题解的情况。,1.3对偶问题的性质,先求原问题的对偶问题由对偶问题的第1个约束条件，可知对偶问题无可行解；根据对偶问题的性质，可知原问题只存在无界解和无可行解两种情况。任意找到原问题的一个可行解，如X=（1，0）T，因此可以判断原问题有可行解，因此原问题解的情况应为无界解。,1.3对偶问题的性质,例2-25已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解。,1.3对偶问题的性质,解：先写出它的对偶问题,将y1*=4/5,y2*=3/5的值代入约束条件=1/53，=17/55，=7/52它们为严格不等式；由互补松弛性得x2*=x3*=x4*=0。因y1，y20；原问题的两个约束条件应取等式，故有x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原问题的最优解为X*=(1，0，0，0，1)T；z*=5,2.对偶单纯形法,2.对偶单纯形法,单纯形法与对偶单纯形法的思想对比由对偶关系的兼容性可知，单纯形法各阶段迭代表格同时给出原始、对偶问题的互补基本解。单纯形法保证原始基本解的可行性，通过迭代使得对偶基本解变为可行；对偶单纯形法保证对偶基本解的可行性，通过迭代使得原始基本解变为可行。由对偶关系的强对偶性和最优性可知，这两种不同的思维角度都可以得到最优解且目标函数值相等,2.对偶单纯形法,对偶单纯形法步骤：初始化构造含有m阶单位阵的标准形LP，b值可以为负j0且bi0，表中原问题与对偶问题均为最优解j0，引入人工变量（略）确定出基变量br=minbi，其对应变量xr为换出基的变量确定入基变量=min-j/arj|arj0，其对应的变量xs为换入基的变量获得新基，对新基检查是否bi0。如是则得两者最优解，否则循环进行。,2.对偶单纯形法,对偶单纯形法步骤：当存在br0，且所对应的行中所有分量arj0。则第r行的约束方程为因arj0（j=m+1,n）,又br0，故不可能存在xj0（j=1,n）的解，故原问题无可行解，这时对偶问题的目标函数值无界。,2.对偶单纯形法,例2-26,2.对偶单纯形法,标准化,2.对偶单纯形法,构造单位阵,2.对偶单纯形法,x1=0，x2=3/2，x3=1，maxz，=-36，即minz=36,2.对偶单纯形法,掌握了单纯形法和对偶单纯形法，我们就可以更灵活地进行单纯形迭代来求得线性规划的最优解可以从一个原始可行、对偶不可行的解出发，用单纯形法进行迭代也可以从一个原始不可行、对偶可行的解出发，用对偶单纯形法进行迭代甚至可以从一个原始不可行，对偶也不可行的解出发，先用适当的进基出基变换把解变成原始可行或对偶可行的，然后再用单纯形法或对偶单纯形法求解。但是有局限性的，它无法判断线性规划问题是否有可行解。,2.对偶单纯形法,对偶单纯形法的优势当约束条件为“”时，不必引进人工变量，使计算简化。对偶单纯形法的问题在初始单纯形表中其对偶问题应是基可行解这点，对多数线性规划问题很难实现。对偶单纯形法一般不单独使用，主要应用于灵敏度分析及整数规划中。,3.灵敏度分析,3.灵敏度分析,以前讨论线性规划问题时，假定ij，bi，cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；ij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。,3.灵敏度分析,所谓灵敏度分析，是指当线性规划问题中的参数发生变化后，引起最优解如何改变的分析，解决以下几方面的问题：线性规划问题中的各系数在什么范围内变化，不会影响已获得的最优基。如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解。当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。,3.1目标函数系数C的变化范围,目标函数系数C向量中的元素数值变化，只会影响最优解中（j=1,2,n）的值，而不会影响的值。也就是说，C中元素的变化只会影响最优解的对偶可行性而不会影响原始可行性。,3.1目标函数系数C的变化范围,Cj的变化在实际问题中反映市场环境的变化，在单纯形表中仅仅影响到检验数zj-cj的变化，所以将Cj的变化直接反映到最终单纯形表中，只可能出现下面两种情况：,3.1目标函数系数C的变化范围,例2-27求c2在什么范围内变化，原来的最优基保持不变；当c2=-3时，最优基是否变化，如果变化，求新的最优基和最优解。,3.1目标函数系数C的变化范围,最优单纯形表最优基保持不变2+C20，C2-2,3.1目标函数系数C的变化范围,当c2=-3时，已经超出保持最优基不变的范围，因此单纯形表不再是最优单纯形表。将c2=-3代入单纯形表，得到以下单纯形表：,3.1目标函数系数C的变化范围,迭代后得到最终单纯形表最优解：x1=8/3，x2=10/3，x3=0，x4=0，x5=0，minz=-46/3,3.1目标函数系数C的变化范围,例2-28在下面线性规划问题中，分析c1在什么范围内变化时，原问题的最优基不变。,3.1目标函数系数C的变化范围,原问题的最优单纯形表,令c1=c1+，得：为了表中解为最优，应有1/4+/40，1/2-/20，因此-11，即当1c13时，最优基保持不变。当c1的变化超出以上范围时，至少会使一个检验数zj-cj0，用单纯形法继续运行，就可以得到新的最优基和最优解。,3.1目标函数系数C的变化范围,作业,美佳公司计划制造I、II两种家电产品。已知各制造一件时分别占用设备A、B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如下表所示。问该公司应制造两种家电各多少件利润最大。,作业,若家电I的利润降低至1.5元/件，而家电II的利润增至2元/件时，美佳公司最优生产计划有何变化？若家电I的利润不变，则家电II的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？,3.2常数项的灵敏度分析,右边常数向量的变化只会影响最优基的原始可行性而不会影响其对偶可行性，可能出现下述两种情况：,3.2常数项的灵敏度分析,例2-29对以下线性规划问题中第一个约束右边常数b1=9进行灵敏度分析。,3.2常数项的灵敏度分析,最优单纯形表如下,3.2常数项的灵敏度分析,由于初始单纯形表中，约束矩阵中松弛变量x4，x5，x6的系数构成一个单位矩阵，因此最优单纯形表中松弛变量在约束矩阵中的系数就是最优基的逆矩阵。即,3.2常数项的灵敏度分析,当b1=b1+=9+时，最后一张单纯形表中的右边常数将成为,3.2常数项的灵敏度分析,这时，最后单纯形表中目标函数的值也将发生变化，成为：,3.2常数项的灵敏度分析,最优单纯形表变为由此可以看出，当第一个约束的右边常数b1变化时，新的单纯形表的b值列就是原来最优单纯形表的b值列加上第一个松弛变量x4在原来最优单纯形表中对应的列与的乘积。,3.2常数项的灵敏度分析,在保持原来最优基原始可行性条件下，对于b1=9+，由单纯形表约束条件的原始可行条件可以得到，当得到即-1，b1=b1+8时，原来的最优基仍为原始可行基。,3.2常数项的灵敏度分析,当b1的变化超过以上范围，例如b1=7，即=b1-b1=7-9=-2时，单纯形表成为：,3.2常数项的灵敏度分析,用对偶单纯形法继续求解得到新的最优解为：（x1,x2,x3,x4,x5,x6）=（0,0,10/3,0,11/2,1/2）maxz=40/3,作业,若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32h，分析美佳公司最优计划的变化。若设备A和设备B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。,3.3增加一个新的变量,在原单纯形表中增加一个新的变量以及新的一列，将以上系数置于原单纯形表中，构成新的单纯形表。若新变量的检验数zj-cj0，则原来的基仍为最优基，原来的基变量以及基变量的值保持不变，新的变量xj=0是非基变量。否则xj进基，用单纯形法继续运行，直至获得新的最优基和最优解。,3.3增加一个新的变量,其分析步骤为：计算计算若，原最优解不变，只需将计算得到的直接写入最终单纯形表中；若，则按单纯形法继续迭代计算找出最优,3.3增加一个新的变量,例2-30在上面的线性规划模型中，增加一个新的变量x6，它在目标函数中的系数c6=1，在约束条件中的系数向量为求新的最优基和最优解。,3.3增加一个新的变量,原问题的最优单纯形表,3.3增加一个新的变量,新的单纯形表为,3.3增加一个新的变量,使用单纯形法迭代，得到最优单纯形表:新的最优解为:(x1,x2,x3,x4,x5,x6)T=（16,0,0,0,0,10）T，maxz=42。,作业,美佳公司计划推出新型号的家电III，生产一件所需设备A、B及调试工序的时间分别为3h、4h、2h，该产品预期盈利为3元/件，试分析该种产品是否值得生产，如投产，对该公司的最优生产计划有何影响？,3.4增加一个新的约束,增加一个新的约束以后，如果原来的最优解满足新的约束，则原来的最优解仍是新问题的最优解。否则，将新增的约束直接反映到最终单纯形表中再进一步分析。,3.4增加一个新的约束,例2-31增加一个约束-x1+2x22，试分析最优解的变化。,3.4增加一个新的约束,原问题最优单纯形表为先将原问题最优解变量值代入，因有-6+20=-62,3.4增加一个新的约束,故将约束条件写成：-x1+2x2-x6=2两边同乘以-1，得到x1-2x2+x6=-2并取x6作为新的基变量，得到新的单纯形表,3.4增加一个新的约束,消去x1在第三个约束中的系数，使得基变量x1在约束条件中的系数成为单位向量：,3.4增加一个新的约束,用对偶单纯形法继续求解：新的最优解为（x1,x2,x3,x4,x5,x6）T=（10/3,0,8/3,0,22/3,0）T，maxz=28/3。如果新增加的约束是等号约束，则需要在这个约束中增加一个人工变量作为新的基变量，然后用两阶段法求得新的最优解。,作业,美佳公司，若家电I，II经调试后，还需经过一道环境试验工序。家电I每件需环境试验3h，家电II每件需2h，又环境试验工序每天生产能力为12h。试分析增加该工序后的美佳公司最优生产计划。,3.5矩阵中系数的灵敏度分析,aij的变化使线性规划的约束系数矩阵A发生变化。若变量xj在最终单纯形表中为非基变量，其分析参照本节之3.3。若变量xj在最终单纯形表中为基变量，则aij的变化将使对应的B和B-1发生变化，有可能出现原问题和对偶问题均为非可行解的情况，需引入人工变量先将原问题的解转化为可行解，再用单纯形法求解。,3.5矩阵中系数的灵敏度分析,例2-32在上面线性规划问题中，对变量x2在第一个约束中的系数a12=1进行灵敏度分析。,3.5矩阵中系数的灵敏度分析,最优单纯形表如下,3.5矩阵中系数的灵敏度分析,设a12=a12+，则即-4，a12-3时，原问题的最优基保持不变。,3.5矩阵中系数的灵敏度分析,例2-33其中x1是基变量，当x1在约束条件中的系数向量变为时求新的最优解。,3.5矩阵中系数的灵敏度分析,原问题最优单纯形表为,3.5矩阵中系数的灵敏度分析,引进一个新的变量x1，它在目标函数中的系数与x1的系数相同为2，在约束中的系数向量为，对于x1，计算它在约束矩阵中的列向量。,3.5矩阵中系数的灵敏度分析,在原最优单纯形表中增加新的变量x1：,3.5矩阵中系数的灵敏度分析,用x1替代x1，将x1的列向量变换为单位列向量，在单纯形表中删除x1及所在列：注意到此处既不适于单纯形法，也不适用于对偶单纯形法。