运筹学对偶理论与灵敏度分析.ppt

《运筹学对偶理论与灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1第2章线性规划的对偶理论与灵敏度分析第一节线性规划的对偶理论 2一、对偶问题的提出在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关-----两个LP问题是互为对偶 3即任何一个求maxZ的LP都有一个求minW的LP。“原问题”----“LP”，“对偶问题”------“DP”。 41、原问题与对偶问题--对称形式(1)原问题中的约束条件个数等于它的对偶问题中的变量数；(2)原问题中目标函数的系数是其对偶问题中约束条件的右端项；(3)约束条件在原问题中为“≤”，则在其对偶问题中为“≥”；(4)目标函数在原问题中为求最大值，在其对偶问题中则为求最小值。二、对偶理论 5例2.2写出下述线性规划问题的对偶问题解：按照上述规则，该问题的对偶线性规划为: 6非对称形式---例如：当原问题约束条件为等式对偶问题:特点：对偶变量符号不限 7对于一般情况下线性规划问题如何写出对偶问题。对于等式约束可以把它写成两个不等式约束，对于“≥”的不等式，可以两边同乘“－1”，再根据对称形式的对偶关系写出对偶问题，然后进行适当的整理，使式中出现的所有系数与原问题中的系数相对应。归纳-----表2.2 8MaxMin约束条件数=m变量个数=m第i个约束条件“≤”“≥”“=”第i个变量≥0≤0无限制变量数=n约束条件数=n第i个变量≥0≤0无限制第i个约束条件为“≥”为“≤”为“=”第i个约束条件的右端项目标函第i个变量的系数目标函数第i个变量的系数第i个约束条件的右端项表2.2 9例2.3写出下述线性规划问题的对偶问题 10例2.4写出下述线性规划问题的对偶问题 112、对偶问题的基本定理（1）（对称性）对偶问题的对偶是原问题。（2）（弱对偶定理）若X(0)是原问题的可行解，Y(0)是对偶问题的可行解，则有CX(0)≤Y(0)b。(3）（无界性）若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。（4）（最优性定理），若X(0)、Y(0)分别是互为对偶问题的可行解，且CX(0)=Y(0)b，则X(0)、Y(0)分别是它们的最优解。（5）（强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。（6）（互补松驰性）若X*、Y*分别是原问题和对偶问题的可行解，则X*、Y*是最优解的充要条件是：Y*XS=0,YSX*=0(其中XS，YS分别是原问题和对偶问题的松驰变量向量)。 12证：设原问题是maxZ=CX；AX≤b；X≥0其对偶问题为minW=Yb；YA≥C；Y≥0又因为可得对称变换，上式的对偶问题是max（-W）=-Yb；-YA≤-C，Y≥0两边取负号，因minW＝max（-W），得到（1）（对称性）对偶问题的对偶是原问题。 13证：设原问题是若X(0)是原问题的可行解，Y(0)是对偶问题的可行解，则有CX(0)≤Y(0)b。将右乘上式，得到因为是LD的可行解，所以满足对偶问题是是LD的可行解，将左乘上式，得到是LP可行解，满足约束,即（2）（弱对偶定理） 14注意：不存在逆。当原问题（对偶问题）无可行解时，其对偶问题（原问题）或具有无界解或无可行解。若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。证：由弱对偶性CX(0)≤Y(0)b，显然得。（3）（无界性） 15证：若所以是最优解。同样证明：对于LP所有可行解X，存在可见使目标函数取值最小的可行解，既最优解。因为，所以根据性质2，LD的所有可行解Y都存在若X(0)、Y(0)分别是互为对偶问题的可行解，且CX(0)=Y(0)b，则X(0)、Y(0)分别是它们的最优解。（4）（最优性定理）， 16若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。是原问题的最优解，对应基阵B必存在即得到，其中若是对偶问题的可行解，它使因原问题的最优解是，使目标函数取值由此，得到是对偶问题的最优解。（5）（强对偶定理） 17从上述性质中，可看到原问题与对偶问题的解必然是下列三种情况之一：①原问题与对偶问题都有最优解，且CX=Yb；②一个问题具有无界解，则它的对偶问题无可行解；③两个问题均无可行解。 18若X*、Y*分别是原问题和对偶问题的可行解，则X*、Y*是最优解的充要条件是：Y*XS=0,YSX*=0(其中XS，YS分别是原问题和对偶问题的松驰变量向量)。证明：设原问题和对偶问题的标准型是原问题对偶问题（6）（互补松驰性） 19将原问题目标函数中的系数向量C用代替后，得到必有又若分别是原问题和对偶问题的最优解，则若；则故是最优解。将对偶问题的目标函数中的系数向量，用代替后，得到 20松约束:某一可行点（如X*和Y*）处的严格不等式约束（包括对变量的非负约束）紧约束:严格等式约束已知试通过求LD的最优解来求解LP的最优解。例2.5 21化简为又由于y1*=1，y2*=3,原问题的约束必为等式，即将代入约束条件，（1），（2），（5）--紧约束（3），（4）--松约束。解：对偶问题为令原问题的最优解为X*=（x1，x2，x3，x4，x5），则根据互补松弛条件，必有x3=x4=0图解--Y*=（1，3），W=11。 22无穷多解令x5=0,得到x1=1，x2=2，即X*1=（1，2，0，0，0）Z=11。再令x5=2/3，得到x1=5/3，x2=0，即X*2＝（5/3，0，0，0，2/3）Z=11。 231、影子价格----边际价格若LP的某个约束条件的右端项常数bi增加一个单位时，所引起的目标函数最优值Z*的改变量---第i个约束条件的影子价格设：B是问题LP的最优基，由前式可知，Z*=CBB-1b=Y*b=y*1b1+y*2b2+…+y*ibi+…+y*mbm当bi变为bi+1时（其余右端项不变，也不影响B），则目标函数最优值变为：Z′*=y*1b1+y*2b2+…+y*i(bi+1)+…+y*mbm所以有△Z*=Z′*－Z*=y*i三、对偶问题的经济解释——影子价格 24目标函数最优值对资源的一阶偏导数（问题中所有其它数据都保持不变）-----Z*对bi的变化率经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi就是第i个约束条件的影子价格。Z*=y*1b1+y*2b2+…+y*ibi+…+y*mbm 25问该公司如何安排生产才能使销售利润最大？表2－3生产消耗参数及产品售价甲产品乙产品每天可供量资源单位成本A2325单位5（万元/单位）B1215单位10（万元/单位）产品售价（万元）2340模型一：决策变量：甲、乙两种产品的数量两种原材料A、B的使用量模型二：决策变量：甲、乙两种产品的数量例2.6 26在最优决策下对资源的一种估价，没有最优决策就没有影子价格，----又称“最优计划价格”，“预测价格”等。定量的反映了单位资源在最优生产方案中为总收益所做出的贡献，----可称为在最优方案中投入生产的机会成本。若第i种资源的单位市场价格为mi当yi>mi时，企业愿意购进这种资源，单位纯利为yi－mi，则有利可图；yi0，说明该资源已耗尽，成为短线资源。影子价格=0，说明该资源有剩余，成为长线资源。（2）对市场资源的最优配置起着推进作用即在配置资源时，对于影子价格大的企业，资源优先供给（3）可以预测产品的价格产品的机会成本为CBB-1A-C，只有当产品价格定在机会成本之上，企业才有利可图。2、影子价格的作用 28（4）可作为同类企业经济效益评估指标之一。对于资源影子价格越大的企业，资源的利用所带来的收益就越大，经济效益就越好。通过以上讨论可知：①只有某资源对偶解大于0，该资源才有利可图，可增加此种资源量；若某资源对偶解为0，则不增加此种资源量。②直接用影子价格与市场价格相比较，进行决策，是否买入该资源。 29单纯形法在保证的前提下，使迭代到对偶单纯形法:根据对偶问题的对称性，保持对偶可行下，经过迭代，逐步实现原问题可行，以求得最优解。对偶单纯形是先保证现行解对应的对偶问题可行，即，然后从迭代到。1.单纯形法的重新解释设X*是最大化LP问题最优解的充要条件是第二节、对偶单纯形法 30（1）初始单纯形表。检查b列，若都为非负，且检验数都为非正，得到最优解，停算。若b列至少还有一个负分量，检验数保持非正，转（2）；（2）确定换出变量对应基变量为换出变量；（3）确定换入变量在单纯形表中检查所在的行的系数，若所有的，则无可行解，停止计算。若存在，计算按Θ规则，所对应的列变量的非基变量为换入变量；（4）以为主元素，按单纯形法进行换基迭代，得到新的单纯形表；重复（1）－（4）的步骤进行计算。对偶单纯形的计算步骤： 31例2.7用对偶单纯形法求解表2.4cj-9-12-15000CBxBbx1x2x3x4x5x60x4-10-2-2-11000x5-12-2-3-10100x6-14-1-1[-5]001-z’0-9-12-15000 32表2.4cj-9-12-15000CBxBbx1x2x3x4x5x60x4-10-2-2-11000x5-12-2-3-10100x6-14-1-1[-5]001-z’0-9-12-15000CBxBbx1x2x3x4x5x60x4-7.2-1.8-1.8010-0.20x5-9.2-1.8[-2.8]001-0.2-15x32.80.20.2100-0.2表2.5-z’42-6-9000-3 33cj-9-12-15000CBxBbx1x2x3x4x5x60x4-9/7[-9/14]001-9/14-1/14-12x223/79/14100-5/141/14-15x315/71/140101/14-3/14表2.6-z’501/7-3/14000-45/14-33/14cj-9-12-15000CBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9表2.7-z’72000-1/3-3-7/3 34（1）初始解非可行解，检验数都是负数时，----进行基变换，避免增加人工变量，运算简便。（2）变量较少，约束条件很多的线性规划问题，可先将其变为对偶问题，再用对偶单纯形求解，简化计算。（3）灵敏度分析。优点与用途： 35如市场条件发生变化，价值系数就会发生变化；当资源投入量发生改变时，也随着发生变化；当工艺条件发生改变时，也随着工艺的变化而变化。灵敏度分析1）系数在什么范围内变化时，最优解（基）不变；2）若系数的变化使最优解发生变化，如何最简便地求得新的最优解(值，结构）。bXBXNXsXBB-1bIB-1NB-1-Z-CBB-1b0CN-CBB-1N-CBB-1第三节、灵敏度分析 36ABC资源量甲11112乙12220利润586解：设三种产品的产量分别为x1、x2、x3，标准型为maxZ=5x1+8x2+6x3x1+x2+x3+x4=12x1+2x2+2x3+x5=20x1,x2,x3,x4,x5>0已知某企业计划生产3种产品A、B、C，其资源消耗与利润如表2.12所示问：如何安排产品产量，可获最大利润？例2.9 37表2.1558600CBXBbx1x2x3x4x55x141002-18x28011-11最优表－Z－8400-2-2-3表2.1458600CBXBbx1x2x3x4x50x412111100x52012201初始表058600最优方案为X=(4,8,0)T,目标值为84。 38Cj的灵敏度分析最优表-->表2.16②若C3=10时，σj=2>0，这时原方案已不是最优方案。原最优方案不发生改变。①σj≤0，这时对最优解方案没有影响。在例2.9中，如果改变C3，使σj=cj－CBB-1Pj1、目标函数中的价值系数（1）非基变量的价值系数 39表2.16581000XBbx1x2x3x4x55x141002-18x2801[1]-11－Z－84002-2-3表2.17581000XBbx1x2x3x4x55x141002-110x38011-11－Z－1000-200-5则最优方案调整为X=(4,0,8)T,目标值为100。 40①全部σ仍≤0，最优解方案不变，最优值变。在例2.9中，如果改变，使即单位产品A的利润在[4,8]之间变化时,最优方案不变，但最优值为。（2）、基变量的价值系数 41②为10时，原方案已不是最优方案表2.18108600CBXBbx1x2x3x4x510x141002-18x28011-1[1]－Z－10400-2-122表2.19108600XBbx1x2x3x4x510x112111100x58011-11－Z－1200-2-4-100则最优方案调整为X=(12,0,0)T,目标值为120。 42bXXBB-1bB-1A－Z-CBB-1bC-CBB-1A对偶单纯形法-新的最优方案。最优基不变---即生产产品的品种不变，但最优值会变化。影响最优解和最优值2、资源b的灵敏度分析 43即原料甲的供应量在[10，20]之间时并不影响最优方案。当时，最优方案调整为X=(16,2,0)T,目标值为96。 44表2.2058600XBbx1x2x3x4x55x1401002-18x2－10011[-1]1－Z－12000-2-2-3表2.2158600XBbx1x2x3x4x55x120122010x4100－1－11－1－Z－1000－2-40-5最优方案为X=(20,0,0)T,目标值为100。 45新产品D，单位产品消耗原材料甲---3个单位，乙---2个单位，利润10。问：投产D是否有利？（1）D利润为多少---投产产品D有利？最优方案不变。投产产品D无利。3、添加新变量的灵敏度分析 46（2）、当时，表2.225860015XBbx1x2x3x4x5x65x141002-1[4]8x28011-11-1－Z－8400-2-2-33表2.235860015XBbx1x2x3x4x5x615x611/400-1/2-1/418x291/411-1/23/40－Z－87-3/40-2-7/2-9/40生产B产品9件，生产D产品1件。目标值为87。 47假设电力供应紧张----13单位产品A、B、C每单位需电力------2、1、3个单位问该公司生产方案是否需要改变？加入松弛变量得2x1+x2+3x3＋x6＝13解：原最优解（4，8，0）T原解已不是新约束条件下的最优解以x6为基变量，将上式反映到最终单纯形表中表2.24586000XBbx1x2x3x4x5x65x141002-108x28011-1100x613213001－Z－8400-2-2-30化BI得表2.25代入电力约束条件2x1+x2+3x3134、添加新约束 48表2.25586000XBbx1x2x3x4x5x65x141002-108x28011-1100x6－3002[－3]11－Z－8400-2-2-30对偶单纯形法表2.26586000XBbx1x2x3x4x5x65x12104/30-1/32/38x29011/302/3-1/30x4100-2/31-1/3-1/3－Z－8200-10/30-11/3-2/3生产A产品1件，生产B产品9件。目标值为82。 49（1）、非基变量的工艺发生改变影响列，看检验数是大于零还是小于零。(小于零----单纯形法）2、基变量的工艺发生改变当是基变量的系数时，它的变化会使发生改变，所以最终单纯形表也要发生变化.改变(计划生产的产品工艺结构发生改变)5、技术系数 50表2.27558600XBbx1x1’x2x3x4x55x1’412002-18x280011-11－Z－840－50-2-2-3若产品A的工艺改变为对甲、乙原材料需求为----2，2，利润不变，问最优方案如何变化？表2.2858600XBbx1’x2x3x4x55x1’2100[1]-1/28x28011-11－Z－7400-23-11/2 51表2.2958600XBbx1’x2x3x4x50x421001-1/28x21011101/2－Z－80-50-20-4最优方案发生改变，这时只生产B产品10件。目标值为80。 52当是基变量的系数时，它的变化会使出现负数或检验数和基变量均不满足最优解要求。若产品A工艺改变为对甲、乙原材料的需求分别为1，3，单位产品的利润为5，问最优方案如何变化？表2.3058600XBbx1x2x3x4x55x14－1002-18x28211-11－Z－84－60-2-2-3 53表2.3158600XBBx1x2x3x4x55x1－4100－218x2160113－1－Z－10800-2-143x1-2x4+x5=-4乘以（－1）表2.3258600－MXBBx1x2x3x4x5x6－Mx64-100[2]-118x2160113－10-Z4M-1285-M0-22M-24-M+80加----人工变量x6-x1+2x4－x5+x6=4 54表2.3358600－MXBbx1x2x3x4x5x60x42-1/2001-1/21/28x2103/21101/2-3/2-Z-80-70-20-412-M生产B产品10件。目标值为80。