《管理运筹学》02-5对偶原理.ppt

《《管理运筹学》02-5对偶原理.ppt》由会员分享，可在线阅读，更多相关《《管理运筹学》02-5对偶原理.ppt（33页珍藏版）》请在三一办公上搜索。

1、,第 3 节,Dual Principle,DP,对偶与灵敏度分析,第3节 对偶与灵敏度分析,2,一、线性规划的对偶关系二、线性规划的对偶性质三、灵敏度分析四、对偶关系的经济解释,第3节 对偶与灵敏度分析,3,线性规划的对偶关系,对偶问题,y1 y2 y3,由于原拟用于生产每件甲产品的1个A工时和3个c工时能创造3百元利润，所以出租上述数量的各资源的盈利起码应不低于3百元。,2y1+y2+4y3 2,2y1+2y2+4y4 3,Min w=12y1+8y2+16y3+12y4,y1，y2，y3，y4 0,y3,第3节 对偶与灵敏度分析,4,原问题,对偶问题,线性规划的对偶关系,第3节 对偶与灵

2、敏度分析,5,线性规划的对偶关系,min w=8y1+12y2+36y3 y1+3y3 3 2y2+4y3 5 y1,y2,y3 0,s.t.,Y*=(0,1/2,1)T w*=42,X*=(4,6)T,z*=42,第3节 对偶与灵敏度分析,6,线性规划的对偶关系,对偶结构用矩阵表示为：,(原问题):,(对偶问题):,记向量和矩阵为：,第3节 对偶与灵敏度分析,7,其他形式的对偶问题,若模型中原问题约束条件的符号与标准形式相反,变 形,对偶变量Y,令Y=Y,第3节 对偶与灵敏度分析,8,其他形式的对偶问题,若模型中原问题变量的符号与标准形式相反,设X=-X,对偶问题,对偶变量Y,第3节 对偶与

3、灵敏度分析,9,对偶问题典式,第3节 对偶与灵敏度分析,其他形式的对偶问题,10,关系：一般对偶关系,第3节 对偶与灵敏度分析,线性规划的对偶关系,11,例2-21 max z=8 x1+5 x2-x1+2 x2 4 3 x1-x2=7 2 x1+4 x2 8 x1,x2 0,min w=4y1+7y2+8y3-y1+3 y2+2y3 8 2 y1-y2+4y3 5 y1 0,y2 自由，y3 0,s.t.,s.t.,y1 y2y3,第3节 对偶与灵敏度分析,线性规划的对偶关系,12,例2-22,max z=2y1+5y2+1y3 2 y1+3 y2+1y3 3 1 y1-5 y2+1y3 2

4、 3 y1+1y3-1,=,y1 0,y2 0,y3自由,s.t.,解,第3节 对偶与灵敏度分析,线性规划的对偶关系,13,练习,解,第3节 对偶与灵敏度分析,线性规划的对偶关系,14,对偶问题的性质,性质1 对称性 对偶问题的对偶是原问题。,第3节 对偶与灵敏度分析,15,性质2 弱对偶性 设X,Y分别为原问题与对偶问题的任意 可行解，则存在 CX Yb,第3节 对偶与灵敏度分析,对偶问题的性质,16,性质3 无界性 若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。,原问题,对偶问题,注：逆命题不真，原问题与对偶问题均无可行解。,第3节 对偶与灵敏度分析,对偶问题的性质,17,

5、性质4 可行解是最优解时的性质 设X是原问题的可行解，Y是对偶问题的可行解。当CX=Yb时，X，Y分别是原问题与对偶问题的最优解。,第3节 对偶与灵敏度分析,对偶问题的性质,18,性质5 对偶定理 若原问题有最优解，那么对偶问题也有最优解；且目标函数相等。,第3节 对偶与灵敏度分析,对偶问题的性质,19,性质6 兼容性 该性质主要讨论原问题检验数与对偶问题解的关系。原问题与对偶问题标准化后，具有相同的分量个数。这些分量相互之间存在着对应的关系。原问题单纯形表的检验数行对应其对偶问题的一个基本解，且目标函数值相等。我们把这样一对基本解称为互补基本解。,第3节 对偶与灵敏度分析,对偶问题的性质,2

6、0,X*=(4,6)T,Y*=(0,1)T,*b(4,6,4,0,0)T,*=(0,1,0,0)T,z*=42=w*,第3节 对偶与灵敏度分析,对偶问题的性质,21,(P)的基本解 与(D)的基本解 相互对应,且二者目标值相等。我们把这样一对基本解 与，称为(P)与(D)的互补基本解。,第3节 对偶与灵敏度分析,对偶问题的性质,22,性质7 互补松弛性 设X，Y分别为原问题和对偶问题的可行解，那么YXS=0 和 YSX=0；当且仅当，X，Y为最优解。,第3节 对偶与灵敏度分析,对偶问题的性质,23,由对偶问题的第1个约束条件，可知对偶问题无可行解；根据对偶问题的性质，可知原问题只存在无界解和无

7、可行解两种情况。任意找到原问题的一个可行解，如X=（1，0）T，因此可以判断原问题有可行解，因此原问题解的情况应为无界解。,第3节 对偶与灵敏度分析,对偶问题的性质,24,第3节 对偶与灵敏度分析,对偶问题的性质,25,第3节 对偶与灵敏度分析,对偶问题的性质,26,对偶单纯形法,二、对偶单纯形法基本思想：在迭代过程中保持对偶可行条件和互补松弛条件满足，并且在迭代过程中不断改进原始可行条件。当原问题和对偶问题均为可行解时，即求得了最优解。,第3节 对偶与灵敏度分析,27,对偶单纯形法,算法步骤：1线性规划的检验数行zjcj 0，但bi中存在负的分量。即该问题的对偶问题是基本可行解，原问题不是基

8、本可行解。2确定出基变量：在小于零的bi时，令出基变量br=minbi，其对应的变量xr作为出基变量。3确定进基变量：（1）为使迭代后的表中第r行基变量为非负，因而只有对应的arj0的非基变量才可以作为换入基的变量；,第3节 对偶与灵敏度分析,28,对偶单纯形法,（2）为使迭代后表中对偶问题的解仍为可行解，令称ark为主元素，xk为进基变量；（3）进行矩阵行变换，得到新的基。重复以上步骤。4当所有的bi0时，当前解是最优解。当存在br0，且对所对应的行中所有分量arj0。则第r行的约束方程为,第3节 对偶与灵敏度分析,29,对偶单纯形法,当存在br0，且对所对应的行中所有分量arj0。则第r行

9、的约束方程为 因arj0（j=m+1,n）,又br0，故不可能存在xj0（j=1,n）的解，故原问题无可行解，这时对偶问题的目标函数值无界。,第3节 对偶与灵敏度分析,例2-26 用对偶单纯形法求解以下问题,30,对偶单纯形法,第3节 对偶与灵敏度分析,31,列出初始单纯形表,Cj-4-12-18 0 0,第3节 对偶与灵敏度分析,对偶单纯形法,32,Cj-4-12-18 0 0,当前基既是原始可行基，又是对偶可行基，因而是最优基。最优解为,x1=0，x2=3/2，x3=1，max z，=-36，即min z=36,第3节 对偶与灵敏度分析,对偶单纯形法,33,练习,解,max z=-3x1-2x2,s.t.,2x1+3x2+x3=18 x1-x2 x4=2 x1+3x2 x5=10 x1,x2,x3,x4,x5 0,x1+x2+x4=2,x13x2+x5=10,第3节 对偶与灵敏度分析,对偶单纯形法,X*=(4,2)Tz*=16,