《第02章对偶问题与灵敏度分析》由会员分享，可在线阅读，更多相关《第02章对偶问题与灵敏度分析（142页珍藏版）》请在金锄头文库上搜索。
1、,计算机学院 陈丰 ,运筹学,力学中有对偶，数学规划论中也有对偶。20世纪50年代，运筹学界发现每个线性规划问题都有一个相对应的“影像”，称之为LP问题的对偶问题（Dual Programming，DP）。它们都是研究同一对象，出于同一目的，但研究的角度不同，它们密切联系又有区别，相辅相成，互为对偶。,第2章 线性规划的对偶理论与灵敏度分析,提 纲,1 线性规划的对偶问题2 对偶问题的基本性质3 影子价格4 对偶单纯形法5 灵敏度分析,学习目标：1 掌握原问题与其对偶问题的对应关系2 能熟练准确地写出一般形式的线性规划的对偶问题,1 线性规划的对偶问题,1 线性规划的对偶问题,1.1 对偶问题
2、的提出,在第1章例1中讨论了工厂生产计划模型及其解法，该问题站在工厂管理者的角度追求利润最大。我们记为LP1：,（LP1）,现从另一角度来讨论这个问题。假定该厂的决策者决定不生产产品、，而将其所有资源出租或外售。这时工厂的决策者就要考虑给各种资源如何定价的问题。,设分别用y1、y2和y3表示单位时间（h）设备A、设备B和调试工序的出让价格。则该厂的决策者进行定价决策时，将作如下比较： 若用6h设备B和1h调试工序可生产一件产品，利润为2元，那么将生产每件产品的设备台时和调试工序出租和出让的所有收入应不低于生产一件产品的利润，这就有 6y2y32,同理将生产一件产品的设备台时和调试工序出租和出让
3、的所有收入应不低于生产一件产品的利润，这就有 5y12y2y31,将工厂所有设备台时和调试工序都出租和出让，其总的收入为 w15y124y25y3从工厂的决策者来看当然w愈大愈好，但从接受者来看他的支付愈少愈好，所以工厂的决策者只能在满足所有产品的利润条件下，使其总收入尽可能地小，他才能实现其意愿，为此可得到如下的线性规划问题：,（LP2）,我们称这个线性规划问题为例1线性规划问题（这里称为原问题）的对偶问题。联系：都 是关于工厂的模型并且使用相同的数据，目的都是为了提高工厂的效益。区别：模型反映的角度不同，前者为充分利用资源问题，后者为资源恰当估价问题。,（LP1）,任何线性规划问题都有对偶
4、问题，而且都有相应的意义。,1 线性规划的对偶问题,1.2 对称形式下对偶问题的一般形式,定义：满足下列条件的线性规划问题称为具有对称形式： 变量均具有非负约束 约束条件当目标函数求极大时取“”号，当目标函数 求极小时均取“”号。,LP1具有对称形式,（LP2）,（LP1）,目标函数,n,m,C,b,决策变量,（LP2）,（LP1）,下面是对称形式下线性规划原问题的一般形式：,用yi(i=1,.,m)代表第i种资源的估价，则其对偶问题的一般形式为,矩阵表示,AT,C,b,min,A,b,C,max,原问题,对偶问题,对称形式下线性规划的原问题与对偶问题的对应关系：,P43 例1 写出下述线性规
5、划问题的对偶问题（即第1章 例1）,y1y2y3,y1 y2 y3,y1，y2 ，y3 0,1 线性规划的对偶问题,并非所有线性规划问题具有对称形式，故下面讨论一般情况下线性规划问题如何写出其对偶问题。,1.3 非对称形式的原-对偶问题关系,无论对称或非对称的线性规划问题在写出其对偶问题时，下表的对应关系都适用。,由于前面四个对应关系与对称形式下的对应关系一致，故我们只需讨论约束类型与变量类型之间的对应关系:,约束条件,约束条件,变量,变量,P64 2.1(b) 写出下述线性规划问题的对偶问题,max z 5x16x23x3,x12x22x3 = 5x15x2 x3 3 4x17x23x3 8
6、x1无约束，x2 0 ，x3 0,y1y2y3,563,=,0,0,无约束,P44 例3 写出下述线性规划问题的对偶问题,min z 7x14x24x3,4x12x26x3243x16x24x315 5x1 3x330 x10, x2无约束, x30,y1y2y3,学习目标：1 掌握单纯形法的矩阵描述，它是灵敏度分析的基础2 理解对偶问题的基本性质,2 对偶问题的基本性质,本节的讨论先假定原问题及对偶问题为对称形式线性规划问题（结论同样适用于非对称形式），原问题为：,2 对偶问题的基本性质,其对偶问题为：,（2.9）,（2.10）,2 对偶问题的基本性质,例4 用单纯形法求解,列出初始单纯形表
7、, , ,(1/2),1,1,单纯行法的迭代过程实际上是对增广矩阵进行的初等行变换。,A1,A2,A3,A4,矩阵的初等变换不只是可用语言表述，而且可用矩阵的乘法运算来表示。为此要引入初等矩阵的概念。,初等矩阵：将单位矩阵作一次初等（行/列）变换所得的矩阵称为初等矩阵。 以非0常数 c 乘以矩阵的某一行（列） Ei ( c ) 将矩阵的某一行（列）乘以常数 c 并加到另一行（列）Eij(c) 将矩阵的某两行（列）对换位置 Eij,复习初等变换和初等矩阵,由线性代数可知，对矩阵进行的初等行变换，相当于用相应的初等矩阵左乘矩阵。,(1/2),A1,A2, , ,(1/2),1,1,单纯行法的迭代过
8、程实际上是对增广矩阵进行的初等行变换。,A1,A2,A3,A4,A4, , ,(1/2),1,1,A1,A2,A3,E1(1/2),E12(1),E21(1),E1(1/2)A1=A2,E12(1)A2=A3,E21(1)A3=A4,即 E1(1/2)E12(1)E21(1)A1=A4,令 D=E1(1/2)E12(1)E21(1)，则有 DA1=A4,对于矩阵A，如果存在一个矩阵B，使得 AB = BA = I（单位矩阵） 成立，则称A是可逆矩阵，并称B是A的逆矩阵。记作 A-1，即A-1 = B。当然，也可称A是B的逆矩阵。,复习逆矩阵的概念,A1,A4,即 DA1=A4,即用 D=E3E
9、2E1左乘,现A4中基变量为x1和x3，P1和P3构成单位矩阵，如下,A4,互换下第2列与第3列的位置,A4,类似，A1中也互换第2列与第3列的位置，有,A1,A1,A4,即 DA1=A4,即用 D=E3E2E1左乘,下面将A4进行分块处理,b,B,N,S,同理，将A1进行分块处理,有 DA1=A4,b,B,N,S,有,Db=bDB=BDN=NDS=S,由于 B =I则有 DB=I因此 D = B-1即 D是基B的逆矩阵,由于 S =I DS=S因此 D = S= B-1,B-1,即 D( )=( ),b,B,N,S,Db=bDB=BDN=NDS=S,B-1,即 DA1=A4,证实,结论：单纯
10、行法的迭代过程相当于用B-1（基B的逆矩阵）左乘增广矩阵。,线性规划问题（2.9）的矩阵表达式加上松驰变量 Xs 后为：,（2.11）,上式中： Xs为松弛变量，Xs=（xn+1，xn+2，xn+m） I为mm单位矩阵,2.1 单纯形法计算的矩阵描述 P29,单纯形法计算时，总选取为初始基，对应基变量Xs初始单纯形表可表示成如下形式（表1）,（2.11）,设迭代若干步后, 基变量变为XB，XB在初始单纯形表中的系数矩阵为B。,将B在初始单纯形表中单独列出，而A中去掉B的若干列后剩下的列组成N。于是其初始单纯形表可表示成如下形式（表2）。,当迭代若干步后，基变量为XB时，该步的单纯形表中由XB系
11、数组成的矩阵B转变为单位矩阵。,初始单纯形表,中间(最终)单纯形表,单纯行法的迭代计算实际上是对增广矩阵进行的初等行变换，由线性代数可知，这就相当于用有限多个初等矩阵E1，E2，Ek依次左乘增广矩阵。,EkE2E1,b,B,N,I,初等行变换的结果使初始单纯形表中的B变成了单位矩阵I，这表明 EkE2E1BI，故EkE2E1B-1（基B的逆矩阵）,EkE2E1,b,B,N,I,因此，单纯行法的迭代过程相当于用B-1（基B的逆矩阵）左乘增广矩阵。,结论：单纯行法的迭代过程相当于用B-1（基B的逆矩阵）左乘增广矩阵。,几个结论,（1）对应初始单纯形表中的单位矩阵，迭代后的单纯形表中为B-1。,I,
12、B-1,j,j,0 0 0 -1/4 -1/2,15/2,7/2,3/2,第1章中的例1,则,（2）初始单纯形表中基变量 Xs = b ，迭代后的单纯形表中为 XB = B-1b,（3）初始单纯形表中约束系数矩阵为（A, I）=（B, N, I）， 迭代后的表中的约束系数矩阵为（B-1A, B-1I） =（B-1B, B-1N, B-1I） =（I, B-1N, B-1）,（4）若初始单纯形表中变量 xj 的系数向量为Pj， 迭代后为Pj，则有 Pj=B-1Pj。,P38 1.8 已知某线性规划问题的初始单纯形表（见表1.17）和用单纯形法迭代后得到的表（见表1.18），试求括弧中未知数al的
13、值。,表1.17,表1.18,表1.17,表1.18,当基变量变为XB=（x1, x5）T时，XB在初始单纯形表中的系数矩阵为B = (P1, P5 ) =,表1.17,表1.18,已知，单纯形法的迭代过程相当于用B-1左乘增广矩阵。即,表1.17,表1.18,f=3b/2=g，b/2-1=h c/2=2 c=4 c/2+3=i i=5d/2=-1 d=-2 d/2+e=1 e=2,单纯形表的格式：,表1.17,表1.18,b/2=g，b/2-1=h g=1 h=0 b=2 a、j、k、l ?,2 = -1( 2a+05 )即 -7 = -12a， a=3,（5）用单纯形法求解线性规划问题时，迭代的每一步在得到原问题（2.9）的一个基可行解的同时，其检验数的相反数是其对偶问题（2.10）的一个基解（不一定是基可行解，因为有可能有负数存在）。 P47 第6个性质当B为最优基时，其检验数的相反数是其对偶问题（2.10）的一个基可行解（同时也是其对偶问题的最优解），且此时两个问题的目标函数值相等。,
