对偶理论及灵敏度分析ppt培训课件

《对偶理论及灵敏度分析ppt培训课件》由会员分享，可在线阅读，更多相关《对偶理论及灵敏度分析ppt培训课件（91页珍藏版）》请在金锄头文库上搜索。

1、对偶理论及灵敏度分析,（一）基本要求 1、了解对偶问题的特点，熟悉互为对偶问题之间的关系 2、掌握对偶理论及其性质 3、掌握对偶单纯形法 4、掌握限制常数和价值系数、约束条件系数的变化对原最优解的影响 5、掌握增加新变量和增加新约束条件对原最优解的影响，并求出相应因素灵敏度的范围 6、了解影子价格的经济意义 （二）重点 1、对偶单纯形法 2、灵敏度分析 （三）难点 灵敏度分析,对偶理论对偶单纯形方法灵敏度分析,对 偶 理 论 及 灵 敏 度 分 析,对偶理 论,对偶问题概念： 任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。 对偶问题是对原问题从另一角度进行的描述，其最优解

2、与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。 对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。,问题的导出,问题的导出,假设有客户提出要求，购买工厂所拥有的工时和材料，为客户加工别的产品，由客户支付工时费和材料费。那么工厂给工时和材料制订的最低价格应是多少，才值得出售工时和材料 ?,问题的导出,出卖资源获利应不少于生产产品的获利; 约束 价格应该尽量低，这样，才能有竞争力; 目标 价格应该是非负的,问题的导出,用y1和y2分别表示工时和材料的出售价格,总利润最小 min W=3y1+9y2 保证A产品利润 y1

3、+y22 保证B产品利润 y1+4y23 保证C产品利润 y1+7y23 售价非负 y10 y20,问题的导出,问题的导出,对偶问题的定义,对称形式的对偶问题,对偶问题的定义,对称形式的对偶问题,或,对偶问题的定义,对偶问题的特点： 若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然 原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵 极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。,对偶问题的定义,非对称形式对偶问题的处理 等式约束的线性规划问题如下：（1）先将等式约束条件分解为两个不等式约束条件,对偶问题的定义,（2）按对称形式变换关系写出

4、它的对偶问题,整理得,对偶问题的定义,由此可见，yi不受正负限制。将yi代入上述 线性规划问题，得到对偶问题为；,对偶问题的定义,一般线性规划问题的对偶问题,对偶问题的定义,一般线性规划问题的对偶问题可归纳如下对应关系：,对偶问题的写出,例1标准型对偶问题,对偶问题的写出,例2,例 max =2x1+x2+3x3+x4s.t. x1+x2+x3+x452x1-x2+3x3 =-4x1 -x3+x4 1x10,x2,x4无约束,x3 0,min =5y1-4y2+y3s.t. y1+2y2+y3 2y1-y2 =1y1+3y2-y3 3y1 +y3 =1y10，y2无约束， y3 0,其对偶问题

5、为,对偶问题的写出,练习写出对偶问题,max =x1-x2+5x3-7x4s.t. x1+3x2-2x3+x4=252x1 +7x3 +2x4 -602x1 +2x2 -4x3 30x4 10-x4 5x1, x2 0, x3 ,x4无约束,练习,max =x1-x2+5x3-7x4s.t. x1+3x2-2x3+x4=252x1 +7x3+2x4 -602x1 +2x2 -4x3 30x4 10-x4 5x1, x2 0, x3 ,x4无约束,对偶问题的 基本性质,（1）对称性： 对偶问题的对偶问题是原问题。,(P),(D),对偶问题的 基本性质,（2）弱对偶性 若互为对偶的线性规划分别有可

6、行解 则其相应的目标函数值满足,对偶问题的 基本性质,（3）无界性若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。,对偶问题的 基本性质,（4） 最优性准则定理 若X和Y分别是互为对偶的线性规划的可行解 ，且使CX=Yb，则X和Y分别是相应线性规划问题的最优解,对偶问题的 基本性质,（5）对偶定理 若原问题有最优解，那么对偶问题也有最优解，且此时目标函数值相等。,证明：设 是原问题的最优解，它对应的基矩阵为B，则必定所有检验数：,令 ，则,即 是对偶问题的可行解 所以对偶问题的目标值,而 是原问题的最优解，其目标函数取值为：,由最优性准则定理知， 是对偶问题的最优解。,（6）互补

7、松驰性(松紧定理) ： 若 ，分别是(P),(D)问题的可行 解，那么 ,为最优解的充要条 件是：XS=0,YS =0(即若 Ai i=0Ai =bi 0 Pj=Cj 0PjCj = j=0),对偶问题的基本性质,XS=0,YS =0,原问题第i个约束方程是等式约束,若原问题第i个约束方程是不等式约束,例1.已知下列线性规划问题max =x1+2x2+3x3+4x4s.t. x1+2x2+2x3+3x4202x1+x2+3x3+2x420xj0, j=1,2,3,4 已知其对偶问题的最优解为y1=1.2,y2=0.2 运用对偶理论找出原问题的最优解,解其对偶问题为min =20y1+20y2s

8、.t. y1+2y212y1+y222y1+3y23 3y1+2y24y1,y20,(1.2,0.2),.,.,y1,互补松驰性(松紧定理),已知对偶问题的最优解 y1=1.2, y2=0.2,因y10,y20。所以x5=x6=0，即原问题为等式约束,互补松驰性(松紧定理),将y1=1.2,y2=0.2代入对偶问题的 约束条件，得 y30,y40,所以x1=x2=0,min =20y1+20y2s.t. y1+2y2- y3 =12y1+y2- y4=22y1+3y2- y5=3 3y1+2y2- y6=4y1,y20,互补松驰性(松紧定理),x1=x2=0x1+2x2+2x3+3x4=202

9、x1+x2+3x3+2x4=20,即 x1=x2=0，x3=4,x4=4 原问题的最优解为(0,0,4,4)T,max =x1+2x2+3x3+4x4s.t. x1+2x2+2x3+3x4202x1+x2+3x3+2x420xj0, j=1,2,3,4,互补松驰性(松紧定理),（7）原问题单纯形表的检验数行对应其对偶问题的一个基解.,对偶问题的基解,YS1为对应原问题中基变量XB的剩余变量，YS2是对应原问题中非基变量XN的剩余变量。,对偶问题的基解,例.max =x1+4x2+3x3s.t. 2x1+2x2+x34x1+2x2+2x36xj0,对偶问题为min =4y1+6y2s.t. 2y

10、1+y212y1+2y24 y1+2y23y1,y20,对偶问题的基解,对偶问题的基本解为y1=0,y2=0，ys1=-1，ys2=-4，ys3=-3,对偶问题的基解,X4 X5,由原问题的最终表可知， y1=1,y2=1(最优解)， ys1=2，ys2=0 ，ys3=0,其最终表为,对偶问题的基解,X2 X3,在单纯形法的每步迭代中，目标函数取值z=CBB-1b，和检验数CN-CBB-1N中都有乘子Y=CBB-1，那么Y的经济意义是什么?,设B是max z=CXAXb，X0的最优基， 则 z*=CBB-1b=Y*b 。 对z求偏导数，得,影子价格,变量yi*的经济意义是在其他条件不变的情况下

11、， 单位资源变化所引起的目标函数的最优值的变化。,yi*的值代表对第i种资源的估价-影子价格,这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。,影子价格,从原始问题最优表 求影子价格,当B是原问题的最优基时，Y=CBB-1就是影子价格向量。,初始表,最优表,影子价格,y1=5/3, y2=1/3即工时的影子价格为5/3，材料的影子价格为1/3。 如果目前市场

12、上材料的价格低于1/3，则企业可以购进材料来扩大生产，反之可以卖掉部分材料。如果有客户以高于5/3的价格购买工时，则可以出售一些工时。,对偶单纯形法,对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。,根据对偶问题的对称性，单纯形表的迭代过程也可以反过来进行，即保持对偶问题的解始终是基本可行解（即C-CBB-1A0），而使原问题从基本非可行解迭代到基本可行解，从而使原问题和对偶问题同时得到最优解。这种单纯形表的应用方法称之为对偶单纯形法。,对偶单纯形法的计算步骤如下：,(1) 根据线性规划问题，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最

13、优解。停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。 (2) 确定换出变量 按min(B-1b)i(B-1b)i0(B-1b)l对应的基变量xl为换出变量。,对偶单纯形法,(3)确定换入变量 在单纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有lj0，则无可行解，停止 计算。 若存在lj0 (j=1,2,，n), 计算,按规则所对应的列的非基变量xk为换入变量，这样才能保持得到的对偶问题解仍为可行解。 (4) 以lk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。重复步骤(1)(4)。,对偶单纯形法,对偶单纯形法举例,例 用对偶单纯

14、形法求解：,对偶单纯形法举例,对偶单纯形法举例,最优解为y1=5/3,y2=1/3, 最优值Z=-8,Wmin=8,对偶单纯形法在什么情况下使用 ：应用前提：有一个基，其对应的基满足: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数（非可行解）。 注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。,对偶单纯形法,例. min =3x1+4x2+5x3s.t. x1+2x2+3x352x1+2x2+x36x1,x2,x30,解 问题化为max W=-3x1-4x2-5x3s.t. -x1-2x2-3x3+x4 =-5-2x1-2x2-x3 +x5=-6x1,x2

15、,x3,x4,x50,对偶单纯形法练习,所以最优解为x1=1,x2=2,x3=0，min=11,对偶单纯形法练习,xj,对偶单纯形法的适用范围：适合于解如下形式的线性规划问题,在引入剩余变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。,对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。,灵敏度分析,在生产计划线性规划问题的一般形式中， A代表企业的技术状况， b代表企业的资源状况， C代表企业产品的市场状况在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。,