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

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

对偶理论及灵敏度分析DualTheoryandSensitivityAnalysis对偶理论DualTheory影子价格Shadowprice对偶单纯形法DualSimplexMethod灵敏度分析SensitivityAnalysis参数线性规划ParameterLP 1对偶理论对偶问题的提出原问题与对偶问题的数学模型原问题与对偶问题的对应关系对偶问题的基本性质影子价格对偶单纯形法 对偶问题的提出例1：某厂利用现有资源(设备A、设备B、调试工序)生产两种产品(产品Ⅰ、产品Ⅱ)，有关数据如下表。问如何安排生产，使厂家利润最大？产品Ⅰ产品Ⅱ资源限量设备A0515设备B6224调试工序115单位利润21 分析：设产品Ⅰ的产量为x1，产品Ⅱ的产量为x2；又设利润为z。则该问题的线性规划数学模型为：maxz=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0 换一种思路：厂家的资源只出让而不自己生产，该如何解决？设备A出让单价为y1，设备B出让单价为y2，调试工序出让单价为y3。收购收购代价最小厂家出让所得应不低于用同等数量的资源自己生产的利润。 厂家接受的条件：利润需要保证，即6y2+y3≥25y1+2y2+y3≥1收购方接受的条件：收购成本最低，即minw=15y1+24y2+5y3于是得到一个线性规划模型minw=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1,y2,y3≥0 原问题与对偶问题的数学模型原问题maxz=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0对偶问题minw=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1,y2,y3≥0互为对偶问题厂家收购 原问题及其对偶问题的最终单纯形表-zx1x2x3x4x5bmax1000-0.25-0.5-8.5x30011.25-7.57.5x11000.25-0.53.5x2010-0.251.51.5-wy1y2y3y4y5y6y7bmin17.5003.5M-3.51.5M-1.5-8.5y2-1.2510-0.250.250.25-0.250.25y37.5010.5-0.5-1.51.50.5 尝试求解上述两个线性规划问题，你会发现目标函数值一致两个问题的解都出现在单纯形法表格中其他规律结论原问题与其对偶问题实质上一样两个问题互为对方的另一种表达形式 原问题与对偶问题的对应关系原问题对偶问题对称数学模型maxz=CXAX≤bX≥0minf=bTYATY≥CTY≥0目标函数取值maxzminf变量X=(x1,x2,…,xn)TY=(y1,y2,…,ym)T目标函数系数C=(c1,…,cn)bT=(b1,…,bn)常数b=(b1,…,bn)TCT=(c1,…,cn)T约束条件系数A=(aij)m×nAT=(aij)n×m变量-约束变量(n,≥0,≤0,任意)约束(n,≥,≤,=)约束-变量约束(m,≤,≥,=)变量(m,≥0,≤0,任意) 例2：将下述线性规划作为原问题，请转换为对偶问题maxz=5x1+3x2+2x3+4x45x1+x2+x3+8x4≤82x1+4x2+3x3+2x4=10x1≥0,x2≥0,x3任意,x4任意 解法1：将原问题写成对称形式的线性规划问题。得到maxz=5x1+3x2+2(x3’-x3’’)+4(x4’-x4’’)5x1+x2+(x3’-x3’’)+8(x4’-x4’’)≤82x1+4x2+3(x3’-x3’’)+2(x4’-x4’’)≤10-2x1-4x2-3(x3’-x3’’)-2(x4’-x4’’)≤-10x1≥0,x2≥0,x3’≥0,x3’’≥0,x4’≥0,x4’’≥0 设对偶问题变量y1,y2’,y2’’≥0，直接转换，得minf=8y1+10y2’-10y2’’5y1+2y2’-2y2’’≥5y1+4y2’-4y2’’≥3y1+3y2’-3y2’’≥2-y1-3y2’+3y2’’≥-28y1+2y2’-2y2’’≥4-8y1-2y2’+2y2’’≥-4y1,y2’,y2’’≥0 令y2=y2’-y2’’(即y2取值任意)，合并第3、4个约束条件和第5、6个约束条件，得到原问题的对偶问题minf=8y1+10y25y1+2y2≥5y1+4y2≥3y1+3y2=28y1+2y2=4y1≥0,y2任意 解法2：也可以根据原问题与对偶问题的对应关系，直接得到对偶问题：minf=8y1+10y25y1+2y2≥5y1+4y2≥3y1+3y2=28y1+2y2=4y1≥0,y2任意 对偶问题的基本性质对称性：对偶问题的对偶是原问题(对称定理)。证明：设原问题为maxz=CX,AX≤b,X≥0；则其对偶问题为minf=bTY,ATY≥CT,Y≥0。把对偶问题看作原问题，得到线性规划模型为max–f=-bTY,-ATY≤-CT,Y≥0。将上述问题转换为对偶问题，得到min–z=-(CT)TX,-(AT)TX≥-(bT)T,X≥0，即maxz=CX,AX≤b,X≥0。所以对偶问题的对偶即为原问题。 弱对偶性：若X是原问题的可行解，Y是其对偶问题的可行解，则恒有CX≤bTY。证明：因为X为原问题的可行解，故AX≤b，且X≥0；因为Y为对偶问题的可行解，故ATY≥CT，且Y≥0。由上述可得CX=XTCT≤XTATY=YTAX≤YTb=bTY。 原问题对偶问题CX*=bTY*CX≤bTY 从弱对偶性可得到以下重要结论：(1)极大化问题(原问题)的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。(2)极小化问题(对偶问题)的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。(3)若原问题可行，但其目标函数值无界，则对偶问题无可行解。(4)若对偶问题可行，但其目标函数值无界，则原问题无可行解。(5)若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。(6)对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。 最优性：若X是原问题的可行解，Y是其对偶问题的可行解，且有CX=bTY，则X是原问题的最优解，Y是其对偶问题的最优解。证明：根据弱对偶性及已知条件，对于对偶问题任意可行解Y*都有bTY*≥CX=bTY，故Y为对偶问题的最优解。根据弱对偶性及已知条件，对于原问题的任意可行解X*都有CX*≤bTY=CX，故X为原问题的最优解。 强对偶性：若原问题及其对偶问题都有可行解，则两者都有最优解，且最优解的目标函数值相等(对偶定理)。证明：根据弱对偶性可知，由于原问题与对偶问题都有可行解，故原问题目标函数有上界且对偶问题目标函数有下界，所以两者都有最优解。同时，原问题的影子价格即为对偶问题的一个可行解，这个可行解的目标函数即为原问题的目标函数值，且为最优。 互补松弛性：在线性规划问题的最优解中，有以下结论成立：(1)若yi>0，则Σaijxj=bi；(2)若Σaijxj0时，ai1xi1+ai2xi2+…+ainxin=bi，这表明生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。 (5)从影子价格的含义上再来考察单纯形表的计算。检验数σj=cj-CBB-1Pj=cj-Σaijyi，式中cj代表第j种产品的产值，Σaijyi是生产该种产品所消耗各种资源的影子价格的总和，即产品的隐含成本。当产品产值大于隐含成本，表明生产该项产品有利，可在计划中安排；否则，用这些资源来生产别的产品更为有利(准确地说，出售更有利)，就不在生产计划中安排。这就是检验数的经济意义。 (6)一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。 3对偶单纯形法对偶单纯形法的基本思路对偶单纯形法的计算步骤对偶单纯形法的应用举例 对偶单纯形法的基本思路当一个线性规划的约束条件中包含“≥”约束时，为了获得初始可行基，必须用大M法，略嫌麻烦。若减去一个剩余变量，认定为基变量，则成为系数为-1的基变量，其基本解不可行。但是，若基本解满足最优性检验，也就是说其对偶问题所对应的解可行，那么通过迭代，可以使得原问题的解逐渐变得可行，也就得到了原问题的最优解。这就是对偶单纯形法的原理。优点是不需要添加人工变量。 单纯形法的基本思路对偶问题的可行解对偶问题最优解判断对偶单纯形法基本思路最优解判断σj=cj-zj≤0原问题基可行解xB=B-1b≥0 对偶单纯形法的计算步骤第一步：给出一组满足最优检验的基本解第二步：若当前解可行，则得最优解第三步：确定出基变量。选择负数基本解中最小值所对应的变量作为出基变量。即当min{bi’|bi’<0}=br’时第r行对应变量为出基变量第四步：确定入基变量。若第r行都大于等于0则无可行解，停止计算；否则计算θ=min{λj/arj|arj<0,λj<0}=λs/ars，即选择xs为入基变量第五步：以ars为主元素进行消元，转第二步 对偶单纯形法的应用举例例3：已知线性规划问题及其对偶问题maxz=7x1+5x22x1+2x2≤20x1+3x2≤154x1+x2≤322x1+3x2≤21x1,x2≥0minw=20y1+15y2+32y3+21y42y1+y2+4y3+2y4≥72y1+3y2+y3+3y4≥5y1,y2,y3,y4≥0试用对偶单纯形法求解对偶问题 BVwy1y2y3y4y5y6b1-20-15-32-21000y5-2-1-4-210-7y6-2-3-1-301-51015810.5————1-4-70-5-8056y30.50.2510.5-0.2501.75y6-1.5-2.750-2.5-0.251-3.252.66672.5455——232——1-1-1.500-7.5-262.5y30.2-0.310-0.30.21.1y40.61.1010.1-0.41.3 对偶单纯形法的优点：不需要人工变量；当变量多于约束时，用对偶单纯形法可减少迭代次数；在灵敏度分析中，有时需要用对偶单纯形法处理简化。对偶单纯形法缺点：在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。因此，对偶单纯形法一般不单独使用。 练习用对偶单纯形法求解线性规划问题：minw=2x1+3x2+4x3x1+2x2+x3≥32x1-x2+3x3≥4x1,x2,x3≥0 4灵敏度问题及其图解分析灵敏度问题灵敏度分析——图解法灵敏度分析——对偶理论分析 灵敏度问题线性规划问题中，aij,cj,bi都是常数，但这些系数是估计值和预测值。市场的变化→cj值变化；工艺的变化→aij值变化；资源的变化→bj值变化。这样，自然就出现了如下的问题：当这些系数中的一个或多个发生变化时，原最优解会怎样变化？当这些系数在什么范围内变化时，原最优解仍保持不变？若最优解发生变化，如何用最简单的方法找到现行的最优解？ 研究内容研究线性规划中，aij,bi,cj的变化对最优解的影响。研究方法图解法对偶理论分析仅适用于含2个变量的线性规划问题在单纯形表中进行分析 灵敏度分析——图解法例4：用图解法求解下列线性规划模型maxz=34x1+40x24x1+6x2≤482x1+2x2≤182x1+x2≤16x1,x2≥0 x218—16—14—12—10—8—6—4—2—0|||||||||24681012141618x14x1+6x2≤482x1+2x2≤182x1+x2≤16ABCDE(8,0)B(0,6.8)最优解(3,6) 18—16—14—12—10—8—6—4—2—0|||||||||24681012141618x14x1+6x2≤482x1+2x2≤182x1+x2≤16ABCDEx2=(z/40)-(34/40)x1 18—16—14—12—10—8—6—4—2—0|||||||||24681012141618x14x1+6x2≤482x1+2x2≤182x1+x2≤16ABCDE新的最优解若c1增加c2不变x2=(z/c2)-(c1/c2)x1 18—16—14—12—10—8—6—4—2—0|||||||||24681012141618x14x1+6x2≤482x1+2x2≤182x1+x2≤16ABCDE新的最优解若c1减少c2不变x2=(z/c2)-(c1/c2)x1 18—16—14—12—10—8—6—4—2—0|||||||||24681012141618x14x1+6x2≤48斜率=-2/32x1+2x2≤18斜率=-12x1+x2≤16ABCDE最优解不变的范围(设c1固定c2变动)-1≤-34/c2≤-2/334≤c2≤51 灵敏度分析——对偶理论分析分析cj的变化分析bi的变化分析aij的变化增加一个变量xj的分析增加一个约束条件的分析 研究内容研究线性规划中，aij,bi,cj的变化对最优解的影响。常用公式检验数σNT=cNT-cBTB-1N；σj=cj-cBTB-1pj基本解z=cBTB-1b+cNTxN=cBTB-1b (1)非基本变量系数ck的灵敏度分析系数：原来ck变化后ck’=ck+Δck检验数：原来σk=ck-cBTB-1pk改变后σk’=ck’-cBTB-1pk=σk+Δck为了保持最优解不变，必须σk’≤0，即Δck≤-σkck’=ck+Δck≤ck-σk (2)基本变量系数cl的灵敏度分析系数：原来cl变化后cl’=cl+Δcl检验数：原来σj=cj-cBTB-1pj(j≠l)改变后σj’=cj-(cBT+ΔcT)B-1pj=σj-Δclalj’为了保持最优解不变，必须σj’≤0，即max{σj/alj’|alj’>0}≤Δcl≤min{σj/alj’|alj’<0} (3)右端常数项br的灵敏度分析常数项：原来br变化后br’=br+Δbr基本解：原来xB=B-1b改变后xB’=B-1b’=B-1b+B-1(0,…,Δbr,…,0)T=(b1’,…,bm’)T+Δbr(β1r,…,βmr)T为了保持最优基不变，必须xB’≥0，即bi’+Δbrβir≥0，i=1,2,…,m，亦即max{-bi’/βir|βir>0}≤Δbr≤min{-bi’/βir|βir<0} (4)约束条件中系数aij的灵敏度分析(非基变量)约束条件系数：原来aij变化后aij’=aij+Δaij检验数：原来σj=cj-cBTB-1pj=cj-yTpj改变后σj’=cj-yTpi’=σj-yiΔaij为了保持最优解不变，必须σj’≤0，即当yi>0时，Δaij≥σj/yi当yi<0时，Δaij≤σj/yi (5)增加新的变量略(6)增加新的约束条件略 例5：某家电厂家利用现有资源生产两种产品，有关数据如下表。产品Ⅰ产品Ⅱ资源限量设备A(台时)0515设备B(台时)6224调试工序(小时)115单位利润(元/台)21 试问问题1：如何安排生产，使厂家获利最多？问题2：当c1=1.5时，最优生产计划有何变化？问题3：当c2=2时，最优生产计划有何变化？问题4：求原最优解不变时c2的范围。问题5：b1和b2分别如何改变，原计划不变？问题6：为保持最优解不变，a11=0的变化范围。问题7：增加一个变量，最优解的改变。问题8：增加一个约束条件，最优解的变化。 解：(1)设x1表示产品Ⅰ的产量，x2表示产品Ⅱ的产量，z为厂家利润，则得到线性规划模型maxz=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0解之，得到最优解x=(3.5,1.5)T最优值z=8.5 (2)c1=1.5时，得到线性规划模型maxz=1.5x1+x25x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0解之，得到最优解x=(3.5,1.5)T最优值z=6.75结论：最优解不变，最优值减少 (3)c2=2时，得到线性规划模型maxz=2x1+2x25x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0解之，得到最优解x=(3.5,1.5)T最优值z=10结论：最优解不变，最优值增加 (4)c2的变化范围原问题的最终单纯形表中alj’和σj见表，计算σj/alj’也在下表中结论：-1/3≤Δc2≤1，或2/3≤c2’≤2Itemx1x2x3x4x5σj000-0.25-0.5a2j’010-0.251.5σj/a2j’--0--1-1/3 (5)略(6)略(7)略(8)略 灵敏度分析的步骤将参数的改变计算反映到最终单纯形表上；检查原问题是否仍为可行解；检查对偶问题是否仍为可行解；按下表所列情况得出结论和决定继续计算的步骤。 练习某厂计划生产甲、乙、丙三种产品，这三种产品单位利润及生产产品所需材料、劳动力如下表：单位产品甲乙丙可使用资源量劳动力1/31/31/31材料1/34/37/33利润(元)231 (1)确定最优的生产方案；(2)当c3增大至多少时，丙产品安排生产；(3)增加3个劳动力，最优解是否改变？(4)劳动力在哪个范围内变化，对利润值的改变有利；(5)增加新的产品丁，需1个劳动力，1个单位原料，利润3元。确定最优的生产方案。(6)添加新约束：x1+2x2+x3≤10，最优解是否改变？ 5参数线性规划概念模型步骤举例目标函数的系数含有参数的线性规划问题约束条件右端的常数项含有参数的线性规划问题 参数线性规划的概念当参数cj或bi沿某一方向连续变动时，目标函数值z将随cj或bi的变动而呈线性变动，z是这个变动参数的线性函数，因而称为参数线性规划。 参数线性规划的模型(1)目标函数的系数含有参数的LP模型设C：价值不变向量；C*：资源变动向量；λ：参数，则有模型maxz(λ)=(C+λC*)XAX=bX≥0(2)约束条件右端的常数项含有参数的LP模型设b：资源不变向量；b*：资源变动向量；λ：参数，则有模型maxz=CXAX=b+λb*X≥0 参数线性规划的分析步骤(1)令λ=0求解得最终单纯形表(2)将λC*或λb*项反映到最终单纯形表中去(3)λ值增大或减小，观察原问题或对偶问题确定现有解(基)允许的λ的变动范围当λ的变动超出这个范围时，用单纯形法或对偶单纯形法求新的解(4)重复第(3)步，直到λ值继续增大或减小时，表中的解(基)不再出现变化时为止 参数线性规划应用举例例6：目标函数的系数含有参数的线性规划问题。分析λ值变化时，下述参数线性规划问题最优解的变化。maxz(λ)=(2+λ)x1+(1+2λ)x25x1≤156x1+2x2≤24x1+x2≤5x1,x2≥0 解：(1)先令λ=0求得最优解，见下表。BV-zx1x2x3x4x5bθ121000x350100153x462010244x51100155101-0.400-6x1100.2003-x402-1.21063x501-0.20122100-0.20-1-8x1100.2003x400-0.81-22x201-0.2012 (2)然后将λ反映在最终单纯形表中，见下表BV-zx1x2x3x4x5b12+λ1+2λ0000x350100153x462010244x51100155101+2λ-0.4-0.2λ00-6-3λx1100.2003-x402-1.21063x501-0.20122100-0.2+0.2λ0-1-2λ-8-7λx1100.2003x400-0.81-22x201-0.2012 (3)为保持原问题解不变，则-0.2+0.2λ≤0，且-1-2λ≤0，即-1/2≤λ≤1。解不变，值变z=8+7λ(4)增加λ，即λ≥1。继续。解变，值变z=5+10λBV-zx1x2x3x4x5bθ100-0.2+0.2λ0-1-2λ-8-7λx1100.200315x400-0.81-22-x201-0.2012-11-λ000-1-2λ-5-10λx35010015x44001-214x2110015 (5)减少λ，即-2≤λ≤-1/2。继续。解变，值变z=6+3λ。见下表。(6)减少λ，即λ≤-2。初始单纯形表即达最优z=0BV-zx1x2x3x4x5bθ12+λ1+2λ0000x350100153x462010244x51100155101+2λ-0.4-0.2λ00-6-3λx1100.2003x402-1.2106x501-0.2012 xzλ(0,5,15,14,0)T5+10λ[1,∞)(3,2,0,2,0)T8+7λ[-0.5,1](3,0,0,6,2)T6+3λ[-2,-0.5](0,0,15,24,5)T0(-∞,-2]-2-1/2-1124.51525λz(λ)0 例7：目标函数的右端的常数项含有参数的线性规划问题。分析λ值变化时，下述参数线性规划问题最优解的变化。maxz(λ)=2x1+x2x1+x2≤10+2λ2x1+4x2≤24-λ3x1+x2≤18+λx1,x2≥0 (1)先令λ=0求得最优解，然后将λ反映在最终单纯形表中，见下表：-zx1x2x3x4x5bθ1000-0.1-0.6-13.2x3001-0.2-0.21.6x20100.3-0.23.6x1100-0.10.44.8-zx1x2x3x4x5bθ1000-0.1-0.6-13.2-0.5λx3001-0.2-0.21.6+2λx20100.3-0.23.6-0.5λx1100-0.10.44.8+0.5λ (2)为保持基不变，必须1.6+2λ≥0，3.6-0.5λ≥0，4.8+0.5λ≥0，即-0.8≤λ≤7.2，且z=13.2+0.5λ(3)当λ＜-5时，x1+x2≤10+2λ不成立，无解(4)当λ＞24时，2x1+4x2≤24-λ不成立，无解(5)当7.2≤λ≤24时，x1=12-0.5λ，x2=0，x3=-2+2.5λ，x4=0，x5=-18+2.5λ；z=24-λ(6)当-5≤λ≤-0.8时，x1=4-0.5λ，x2=6+2.5λ，x3=0，x4=-8-10λ，x5=0；z=14+1.5λ 前述(5)和(6)的计算结果-zx1x2x3x4x5bλ10θ10-30-10-241-14x30-11-0.50-22.523x11200.5012-0.57x50-50-1.51-182.57-zx1x2x3x4x5bλ-1θ100-0.50-0.5-14-1.5-12.5x2011.50-0.562.53.5x400-511-8-102x110-0.500.54-0.54.5 结论：λ∈[-5,-0.8]，z=14+1.5λλ∈[-0.8,7.2]，z=13.2+0.5λλ∈[7.2,24]，z=24-λλ∈(-∞,-5)∪(24,+∞)，z=无解6.516.8λz(λ)0-57.224-20-10102012.8