《运筹学对偶理论与灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《运筹学对偶理论与灵敏度分析.ppt（54页珍藏版）》请在三一办公上搜索。
1、第2章 线性规划的对偶理论与灵敏度分析,一、对偶问题的提出,在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关-两个LP问题是互为对偶,即任何一个求maxZ的LP都有一个求minW的LP。“原问题”-“LP”，“对偶问题”-“DP”。,1、原问题与对偶问题-对称形式,(1)原问题中的约束条件个数等于它的对偶问题中的变量数；(2)原问题中目标函数的系数是其对偶问题中约束条件的右端项；(3)约束条件在原问题中为“”，则在其对偶问题中为“”；(4)目标函数在原问题中为求最大值，在其对偶问题中则为求最小值。,二、对偶理论,例2.2 写出下述线性规划问题的对偶
2、问题,解：按照上述规则，该问题的对偶线性规划为:,非对称形式-例如：当原问题约束条件为等式,对偶问题:,特点：对偶变量符号不限,对于一般情况下线性规划问题如何写出对偶问题。对于等式约束可以把它写成两个不等式约束，对于“”的不等式，可以两边同乘“1”，再根据对称形式的对偶关系写出对偶问题，然后进行适当的整理，使式中出现的所有系数与原问题中的系数相对应。,归纳-表2.2,表2.2,例2.3 写出下述线性规划问题的对偶问题,例2.4 写出下述线性规划问题的对偶问题,2、对偶问题的基本定理,（1）（对称性）对偶问题的对偶是原问题。（2）（弱对偶定理）若X(0)是原问题的可行解，Y(0)是对偶问题的可行
3、解，则有C X(0)Y(0)b。(3）（无界性）若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。（4）（最优性定理），若X(0)、Y(0)分别是互为对偶问题的可行解，且C X(0)=Y(0)b，则X(0)、Y(0)分别是它们的最优解。（5）（强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。（6）（互补松驰性）若X*、Y*分别是原问题和对偶问题的可行解，则X*、Y*是最优解的充要条件是：Y*XS=0,YSX*=0(其中XS，YS分别是原问题和对偶问题的松驰变量向量)。,证：设原问题是max Z=C X；AXb；X 0其对偶问题为min W=Y
4、b；YA C；Y 0,又因为,可得,对称变换，上式的对偶问题是,max（-W）=-Y b；-YA-C，Y 0,两边取负号，因min W max（-W），得到,（1）（对称性）对偶问题的对偶是原问题。,证：设原问题是,若X(0)是原问题的可行解，Y(0)是对偶问题的可行解，则有C X(0)Y(0)b。,将 右乘上式，得到,因为 是LD的可行解，所以满足,对偶问题是,是LD的可行解，将 左乘上式，得到,是LP可行解，满足约束,即,（2）（弱对偶定理）,注意：不存在逆。当原问题（对偶问题）无可行解时，其对偶问题（原问题）或具有无界解或无可行解。,若原问题（对偶问题）为无界解，则其对偶问题（原问题）无
5、可行解。,证：由弱对偶性C X(0)Y(0)b，显然得。,（3）（无界性）,证：若,所以 是最优解。,同样证明：对于LP所有可行解X，存在,可见 使目标函数取值最小的可行解，既最优解。,因为，所以,根据性质2，LD的所有可行解Y都存在,若X(0)、Y(0)分别是互为对偶问题的可行解，且C X(0)=Y(0)b，则X(0)、Y(0)分别是它们的最优解。,（4）（最优性定理），,若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。,是原问题的最优解，对应基阵B必存在,即得到，其中,由此，得到,是对偶问题的最优解。,（5）（强对偶定理）,从上述性质中，可看到原问题与对偶问题的解
6、必然是下列三种情况之一：原问题与对偶问题都有最优解，且CX=Yb；一个问题具有无界解，则它的对偶问题无可行解；两个问题均无可行解。,若X*、Y*分别是原问题和对偶问题的可行解，则X*、Y*是最优解的充要条件是：Y*XS=0,YSX*=0(其中XS，YS分别是原问题和对偶问题的松驰变量向量)。,证明：设原问题和对偶问题的标准型是 原问题 对偶问题,（6）（互补松驰性）,将原问题目标函数中的系数向量C用 代替后，得到,必有,又若 分别是原问题和对偶问题的最优解，则,若；则 故 是最优解。,将对偶问题的目标函数中的系数向量，用 代替后，得到,松约束:某一可行点（如X*和Y*）处的严格不等式约束（包
7、括对变量的非负约束）紧约束:严格等式约束,已知试通过求LD的最优解来求解LP的最优解。,例2.5,化简为,又由于y1*=1，y2*=3,原问题的约束必为等式，即,将代入约束条件，（1），（2），（5）-紧约束（3），（4）-松约束。,解：对偶问题为,令原问题的最优解为X*=（x1，x2，x3，x4，x5），则根据互补松弛条件，必有x3=x4=0,图解-Y*=（1，3），W=11。,无穷多解令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。,1、影子价格-边际价格若LP的某
8、个约束条件的右端项常数bi增加一个单位时，所引起的目标函数最优值Z*的改变量-第i个约束条件的影子价格,设：B是问题LP的最优基，由前式可知，Z*=CB B-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,三、对偶问题的经济解释影子价格,目标函数最优值对资源的一阶偏导数（问题中所有其它数据都保持不变）-Z*对bi的变化率,经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi就是
9、第 i 个约束条件的影子价格。,Z*=y*1b1+y*2b2+y*ibi+y*mbm,问该公司如何安排生产才能使销售利润最大？表23生产消耗参数及产品售价,模型一：决策变量：甲、乙两种产品的数量两种原材料A、B的使用量,模型二：决策变量：甲、乙两种产品的数量,例2.6,在最优决策下对资源的一种估价，没有最优决策就没有影子价格，-又称“最优计划价格”，“预测价格”等。定量的反映了单位资源在最优生产方案中为总收益所做出的贡献，-可称为在最优方案中投入生产的机会成本。若第i 种资源的单位市场价格为mi当yi mi时，企业愿意购进这种资源，单位纯利为yimi，则有利可图；yi mi，则企业有偿转让这种
10、资源，可获单位纯利miyi，否则，企业无利可图，甚至亏损。,（1）指出企业挖潜革新的途径影子价格0，说明该资源已耗尽，成为短线资源。影子价格=0，说明该资源有剩余，成为长线资源。（2）对市场资源的最优配置起着推进作用即在配置资源时，对于影子价格大的企业，资源优先供给（3）可以预测产品的价格产品的机会成本为CBB-1A-C，只有当产品价格定在机会成本之上，企业才有利可图。,2、影子价格的作用,（4）可作为同类企业经济效益评估指标之一。对于资源影子价格越大的企业，资源的利用所带来的收益就越大，经济效益就越好。通过以上讨论可知：只有某资源对偶解大于0，该资源才有利可图，可增加此种资源量；若某资源对偶
11、解为0，则不增加此种资源量。直接用影子价格与市场价格相比较，进行决策，是否买入该资源。,1.单纯形法的重新解释设X*是最大化LP问题最优解的充要条件是,第二节、对偶单纯形法,（1）初始单纯形表。检查b列，若都为非负，且检验数都为非正，得到最优解，停算。若b列至少还有一个负分量，检验数保持非正，转（2）；,（2）确定换出变量 对应基变量为换出变量；,（3）确定换入变量在单纯形表中检查所在的行的系数，若所有的，则无可行解，停止计算。若存在，计算,按规则，所对应的列变量的非基变量为换入变量；,（4）以 为主元素，按单纯形法进行换基迭代，得到新的单纯形表；重复（1）（4）的步骤进行计算。,对偶单纯形的
12、计算步骤：,例2.7 用对偶单纯形法求解,（1）初始解非可行解，检验数都是负数时，-进行基变换，避免增加人工变量，运算简便。（2）变量较少，约束条件很多的线性规划问题，可先将其变为对偶问题，再用对偶单纯形求解，简化计算。（3）灵敏度分析。,优点与用途：,如市场条件发生变化，价值系数就会发生变化；当资源投入量发生改变时，也随着发生变化；当工艺条件发生改变时，也随着工艺的变化而变化。,灵敏度分析1）系数在什么范围内变化时，最优解（基）不变；2）若系数的变化使最优解发生变化，如何最简便地求得新的最优解(值，结构）。,第三节、灵敏度分析,解：设三种产品的产量分别为x1、x2、x3，标准型为 max Z
13、=5x1+8x2+6x3x1+x2+x3+x4=12x1+2x2+2x3+x5=20 x1,x2,x3,x4,x50,已知某企业计划生产3种产品A、B、C，其资源消耗与利润如表2.12所示,问：如何安排产品产量，可获最大利润？,例2.9,最优方案为 X=(4,8,0)T,目标值为84。,Cj的灵敏度分析,最优表-表2.16,若C3=10时，j=20，这时原方案已不是最优方案。,原最优方案不发生改变。,j0，这时对最优解方案没有影响。在例2.9中，如果改变 C3，使,j=cj CBB-1 Pj,1、目标函数中的价值系数（1）非基变量的价值系数,则最优方案调整为 X=(4,0,8)T,目标值为10
14、0。,即单位产品A的利润在4,8之间变化时,最优方案不变，但最优值为。,（2）、基变量的价值系数,为10时，原方案已不是最优方案,则最优方案调整为 X=(12,0,0)T,目标值为120。,对偶单纯形法-新的最优方案。,最优基不变-即生产产品的品种不变，但最优值会变化。,影响最优解和最优值,2、资源b的灵敏度分析,即原料甲的供应量在10，20之间时并不影响最优方案。,当 时，最优方案调整为 X=(16,2,0)T,目标值为96。,最优方案为 X=(20,0,0)T,目标值为100。,新产品D，单位产品消耗原材料甲-3个单位，乙-2个单位，利润10。问：投产D是否有利？,（1）D利润为多少-投产
15、产品D有利？,最优方案不变。投产产品D无利。,3、添加新变量的灵敏度分析,（2）、当 时，,生产B产品9件，生产D产品1件。目标值为87。,假设电力供应紧张-13单位产品A、B、C每单位需电力-2、1、3个单位问该公司生产方案是否需要改变？,加入松弛变量得 2x1+x2+3x3x613,解：原最优解（4，8，0）T,原解已不是新约束条件下的最优解,以x6为基变量，将上式反映到最终单纯形表中,化 BI 得表2.25,代入电力约束条件 2x1+x2+3x313,4、添加新约束,对偶单纯形法,生产A产品1件，生产B产品9件。目标值为82。,（1）、非基变量的工艺发生改变影响 列，看检验数是大于零还是
16、小于零。(小于零-单纯形法）,2、基变量的工艺发生改变当 是基变量 的系数时，它的变化会使发生改变，所以最终单纯形表 也要发生变化.,改变(计划生产的产品工艺结构发生改变),5、技术系数,若产品A的工艺改变为对甲、乙原材料需求为-2，2，利润不变，问最优方案如何变化？,最优方案发生改变，这时只生产B产品10件。目标值为80。,当 是基变量 的系数时，它的变化会使 出现负数或检验数和基变量均不满足最优解要求。,若产品A工艺改变为对甲、乙原材料的需求分别为1，3，单位产品的利润为5，问最优方案如何变化？,x1-2 x4+x5=-4 乘以（1）,加-人工变量x6-x1+2 x4x5+x6=4,生产B产品10件。目标值为80。,
