管理运筹学-02-5对偶原理ppt课件

1、第3节 对偶与灵敏度分析2一、 线性规划的对偶关系二、 线性规划的对偶性质三、灵敏度分析四、对偶关系的经济解释第第3节节 对偶与灵敏度分析对偶与灵敏度分析3线性规划的对偶关系线性规划的对偶关系 由于原拟用于生产每件甲产品的1个A工时和3个c工时能创造3百元利润，所以出租上述数量的各资源的盈利起码应不低于3百元。 2y1+y2+4y3 2 2140A B C D车间车间 产品产品 甲甲 乙乙单耗工时单耗工时/ /件）件）加工能力加工能力（工时（工时/ /天）天）利润利润 2 3 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12 x1 ， x2 0 第3节 对偶与灵敏度分

2、析4线性规划的对偶关系线性规划的对偶关系第3节 对偶与灵敏度分析5线性规划的对偶关系线性规划的对偶关系 min w = 8y1 + 12y2 + 36y3 y1 + 3y3 3 2y2 + 4y3 5 y1 , y2, y3 0 s.t. X*= (4,6)Tz* = 42第3节 对偶与灵敏度分析6线性规划的对偶关系线性规划的对偶关系对偶结构用矩阵表示为： max z = CX AXb X0 s.t. (原问题原问题):(对偶问题对偶问题): min w = Yb YAC Y0 s.t.记向量和矩阵为： 第3节 对偶与灵敏度分析7其他形式的对偶问题其他形式的对偶问题若模型中原问题约束条件的符号

3、与标准形式相反变变 形形对偶变量对偶变量Y令令Y=Y第3节 对偶与灵敏度分析8其他形式的对偶问题其他形式的对偶问题若模型中原问题变量的符号与标准形式相反设设X= -X对偶问题对偶问题对偶变量对偶变量Y第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

4、 +8y3 - y1 +3 y2 + 2y3 8 2 y1 - y2 + 4y3 5 y1 0 , y2 自在，自在，y3 0s.t.s.t.y1 y2y3第3节 对偶与灵敏度分析线性规划的对偶关系线性规划的对偶关系12例例2-22max z = 2y1+5y2+1y3 2 y1+3 y2 +1y3 3 1 y1 -5 y2 +1y3 2 3 y1 +1y3 -1y1 0,y2 0,s.t.解解 min = 3 x1+2 x2 -1 x3 2 x1+1 x2+3x3 2 3 x1 -5 x2 5 1 x1+1 x2+1 x3 = 1 x10, x3 0 s.t. 第3节 对偶与灵敏度分析线性规

5、划的对偶关系线性规划的对偶关系13练习练习解解 第3节 对偶与灵敏度分析线性规划的对偶关系线性规划的对偶关系14对偶问题的性质对偶问题的性质 性质性质1 对称性对称性 对偶问题的对偶是原问题。对偶问题的对偶是原问题。 第3节 对偶与灵敏度分析15性质性质2 弱对偶性弱对偶性 设设X, Y分别为原问题与对偶问题的任意分别为原问题与对偶问题的任意 可行解，则存在可行解，则存在 CX Yb 第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质16性质性质3 无界性无界性 若原问题对偶问题为无界解，则其对若原问题对偶问题为无界解，则其对偶问题原问题无可行解。偶问题原问题无可行解。原问题原问题对偶问题对

6、偶问题注：逆命题不真，原问题与对偶问题均无可行解。注：逆命题不真，原问题与对偶问题均无可行解。第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质17性质性质4 可行解是最优解时的性质可行解是最优解时的性质 设设X是原问题的可行解，是原问题的可行解，Y是对偶问题的可行解。当是对偶问题的可行解。当CX=Yb时，时，X，Y分别是原问题分别是原问题与对偶问题的最优解。与对偶问题的最优解。 第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质18性质性质5 对偶定理对偶定理 若原问题有最优解，那么对偶问题也有最若原问题有最优解，那么对偶问题也有最优解；且目标函数相等。优解；且目标函数相等。 第3节 对

7、偶与灵敏度分析对偶问题的性质对偶问题的性质19性质性质6 兼容性兼容性 该性质主要讨论原问题检验数与对偶问题解该性质主要讨论原问题检验数与对偶问题解的关系。原问题与对偶问题标准化后，具有相同的分量个数。的关系。原问题与对偶问题标准化后，具有相同的分量个数。这些分量相互之间存在着对应的关系。原问题单纯形表的检这些分量相互之间存在着对应的关系。原问题单纯形表的检验数行对应其对偶问题的一个基本解，且目标函数值相等。验数行对应其对偶问题的一个基本解，且目标函数值相等。我们把这样一对基本解称为互补基本解。我们把这样一对基本解称为互补基本解。 第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质20 :

8、max z = 3x1 +5x2 x1 8 2x2 12 3x1 + 4x2 36 x1 ， x2 0s.t.( ( P1)P1):min w=8y1+12y2+36y3 y1 +3y3 3 2y2+4y3 5 y1 , y2, y3 0s.t.( ( D1)D1): max z = 3x1 +5x2 x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 x1, x2 , x3 , x4 , x5 0s.t.( ( Ps)Ps):min w=8y1+12y2+36y3 y1 +3y3 -y4 = 3 2y2+4y3 -y5 = 5 y1 , y2 , y3 ,

9、y4 , y5 0s.t.( ( Ds)Ds)X*= (4 ,6)TY*= (0 , ,1)T *b (4 ,6 ,4, 0 ,0)T *= (0, ,1, 0 ,0)Tz*= 42 = w*第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质21 (P)的基本解 与(D)的基本解 相互对应, 且二者目标值相等。我们把这样一对基本解 与 ，称为(P)与(D)的互补基本解。 (P) 目目 标标 值值 (D) 序序号号 极极点点 基基 本本 解解 k Xk可可 行行 z = w Yk可可 行行 基基 本本 解解 k 1 O (0 ，0 ，8 ， 12 ， 36) 是是 0 否否 (0 ，0 ，0

10、，- -3 ，- -5) 2 A (8 ，0 ，0 ， 12 ， 12) 是是 24 否否 (3 ，0 ，0 ， 0 ，- -5) 3 D (0 ，6 ，8 ，0 ， 12) 是是 30 否否 (0 ， 5/2 ， 0 ，- -3 ， 0) 4 B (8 ，3 ，0 ，6 ， 0) 是是 39 否否 (- 3/4 ， 0 ， 5/4 ， 0 ， 0) 5 C (4 ，6 ，4 ，0 ， 0) 42 (0 ， 1/2 ， 1 ，0 ，0) 6 E (12 ， 0 ，- -4 ， 12 ， 0) 36 (0 , , 0 , , 1 , , 0 , , - -1) 7 G (0 ，9 ，8 ，- -

11、6 ， 0) 否否 45 是是 (0 , , 0 , , 5/4 , , 3/4 , , 0) 8 F (8 ，6 ，0 ，0 , , - 12) 12) 否否 54 是是 (3 , , 5/2 , , 0 , , 0 , , 0) 第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质22性质性质7 互补松弛性互补松弛性 设设X，Y分别为原问题和对偶问题的可分别为原问题和对偶问题的可行解，那么行解，那么YXS=0 和和 YSX=0；当且仅当，；当且仅当，X，Y为最优为最优解。解。 第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质23 由对偶问题的第由对偶问题的第1个约束条件，可知对偶问题无

12、可行解；根据对偶问题的性质，个约束条件，可知对偶问题无可行解；根据对偶问题的性质，可知原问题只存在无界解和无可行解两种情况。任意找到原问题的一个可行解，可知原问题只存在无界解和无可行解两种情况。任意找到原问题的一个可行解，如如X=（1，0T，因此可以判断原问题有可行解，因此原问题解的情况应为无界，因此可以判断原问题有可行解，因此原问题解的情况应为无界解。解。第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质24第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质25第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质26对偶单纯形法对偶单纯形法第3节 对偶与灵敏度分析27对偶单纯形法对偶单纯

13、形法第3节 对偶与灵敏度分析28对偶单纯形法对偶单纯形法（2为使迭代后表中对偶问题的解仍为可行解，令为使迭代后表中对偶问题的解仍为可行解，令称称ark为主元素，为主元素，xk为进基变量；为进基变量；（3进行矩阵行变换，得到新的基。重复以上步骤。进行矩阵行变换，得到新的基。重复以上步骤。4当所有的当所有的bi0时，当前解是最优解。时，当前解是最优解。 当存在当存在br0，且对所对应的行中所有分量，且对所对应的行中所有分量arj0。则第。则第r行的约束方程为行的约束方程为第3节 对偶与灵敏度分析29对偶单纯形法对偶单纯形法 当存在当存在br0，且对所对应的行中所有分量，且对所对应的行中所有分量ar

14、j0。则第。则第r行的约束方程为行的约束方程为 因因arj0j=m+1,n）,又又br0，故不可能存在，故不可能存在xj0j=1,n的解，故原问题无可行解，这时对偶问题的解，故原问题无可行解，这时对偶问题的目标函数值无界。的目标函数值无界。第3节 对偶与灵敏度分析 例例2-26 用对偶单纯形法求解以下问题用对偶单纯形法求解以下问题30对偶单纯形法对偶单纯形法第3节 对偶与灵敏度分析31 列出初始单纯形表列出初始单纯形表Cj -4 -12 -18 0 0第3节 对偶与灵敏度分析对偶单纯形法对偶单纯形法32Cj -4 -12 -18 0 0当前基既是原始可行基，又是对偶可行基，因而是最优基。当前基既是原始可行基，又是对偶可行基，因而是最优基。最优解为最优解为x1=0，x2=3/2，x3=1，max z，=-36，即即min z=36第3节 对偶与灵敏度分析对偶