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