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

1、一、 线性规划的对偶关系二、 线性规划的对偶性质三、灵敏度分析四、对偶关系的经济解释第第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 线性规划的对偶关系线性规划的对偶关系线性规划的对偶关系线性规划

2、的对偶关系 min w = 8y1 + 12y2 + 36y3 y1 + 3y3 3 2y2 + 4y3 5 y1 , y2, y3 0 s.t. X*= (4,6)Tz* = 42线性规划的对偶关系线性规划的对偶关系对偶构造用矩阵表示为： max z = CX AXb X0 s.t. (原问题原问题):(对偶问题对偶问题): min w = Yb YAC Y0 s.t.记向量和矩阵为： 其他方式的对偶问题其他方式的对偶问题假设模型中原问题约束条件的符号与规范方式相反变变 形形对偶变量对偶变量Y令令Y=Y其他方式的对偶问题其他方式的对偶问题假设模型中原问题变量的符号与规范方式相反设设X= -X

3、对偶问题对偶问题对偶变量对偶变量Y对偶问题典式对偶问题典式其他方式的对偶问题其他方式的对偶问题关系：普通对偶关系关系：普通对偶关系线性规划的对偶关系线性规划的对偶关系 例例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 0s.t.s.t.y1 y2y3线性规划的对偶关系线性规划的对偶关系例例2-22max z = 2y1+5y2+1y3 2

4、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. 线性规划的对偶关系线性规划的对偶关系练习练习解解 线性规划的对偶关系线性规划的对偶关系对偶问题的性质对偶问题的性质 性质性质1 对称性对称性 对偶问题的对偶是原问题。对偶问题的对偶是原问题。 性质性质2 弱对偶性弱对偶性 设设X, Y分别为原问题与对偶问题的恣意分别为原问题与对偶问题的恣意 可行解，那么存

5、在可行解，那么存在 CX Yb 对偶问题的性质对偶问题的性质性质性质3 无界性无界性 假设原问题对偶问题为无界解，那么假设原问题对偶问题为无界解，那么其对偶问题原问题无可行解。其对偶问题原问题无可行解。原问题原问题对偶问题对偶问题注：逆命题不真，原问题与对偶问题均无可行解。注：逆命题不真，原问题与对偶问题均无可行解。对偶问题的性质对偶问题的性质性质性质4 可行解是最优解时的性质可行解是最优解时的性质 设设X是原问题的可行解，是原问题的可行解，Y是对偶问题的可行解。当是对偶问题的可行解。当CX=Yb时，时，X，Y分别是原问题分别是原问题与对偶问题的最优解。与对偶问题的最优解。 对偶问题的性质对偶

6、问题的性质性质性质5 对偶定理对偶定理 假设原问题有最优解，那么对偶问题也有假设原问题有最优解，那么对偶问题也有最优解；且目的函数相等。最优解；且目的函数相等。 对偶问题的性质对偶问题的性质性质性质6 兼容性兼容性 该性质主要讨论原问题检验数与对偶问题解该性质主要讨论原问题检验数与对偶问题解的关系。原问题与对偶问题规范化后，具有一样的分量个数。的关系。原问题与对偶问题规范化后，具有一样的分量个数。这些分量相互之间存在着对应的关系。原问题单纯形表的检这些分量相互之间存在着对应的关系。原问题单纯形表的检验数行对应其对偶问题的一个根本解，且目的函数值相等。验数行对应其对偶问题的一个根本解，且目的函数

7、值相等。我们把这样一对根本解称为互补根本解。我们把这样一对根本解称为互补根本解。 对偶问题的性质对偶问题的性质 : 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

8、+12y2+36y3 y1 +3y3 -y4 = 3 2y2+4y3 -y5 = 5 y1 , y2 , y3 , 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*对偶问题的性质对偶问题的性质 (P)的根本解 与(D)的根本解 相互对应, 且二者目的值相等。我们把这样一对根本解 与 ，称为(P)与(D)的互补根本解。 (P) 目目 标标 值值 (D) 序序号号 极极点点 基基 本本 解解 k Xk可可 行行 z = w Yk可可 行行 基基 本本 解解

9、 k 1 O (0 ，0 ，8 ， 12 ， 36) 是是 0 否否 (0 ，0 ，0 ，- -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 ,

10、 , 0 , , 1 , , 0 , , - -1) 7 G (0 ，9 ，8 ，- -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) 对偶问题的性质对偶问题的性质性质性质7 互补松弛性互补松弛性 设设X，Y分别为原问题和对偶问题的可分别为原问题和对偶问题的可行解，那么行解，那么YXS=0 和和 YSX=0；当且仅当，；当且仅当，X，Y为最优为最优解。解。 对偶问题的性质对偶问题的性质 由对偶问题的第由对偶问题

11、的第1个约束条件，可知对偶问题无可行解；根据对偶问题的性质，个约束条件，可知对偶问题无可行解；根据对偶问题的性质，可知原问题只存在无界解和无可行解两种情况。恣意找到原问题的一个可行解，可知原问题只存在无界解和无可行解两种情况。恣意找到原问题的一个可行解，如如X=1，0T，因此可以判别原问题有可行解，因此原问题解的情况应为无界，因此可以判别原问题有可行解，因此原问题解的情况应为无界解。解。对偶问题的性质对偶问题的性质对偶问题的性质对偶问题的性质对偶问题的性质对偶问题的性质对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法2为使迭代后表中对偶问题的解仍为可行解，令为使迭代后表

12、中对偶问题的解仍为可行解，令称称ark为主元素，为主元素，xk为进基变量；为进基变量；3进展矩阵行变换，得到新的基。反复以上步骤。进展矩阵行变换，得到新的基。反复以上步骤。4当一切的当一切的bi0时，当前解是最优解。时，当前解是最优解。 当存在当存在br0，且对所对应的行中一切分量，且对所对应的行中一切分量arj0。那么。那么第第r行的约束方程为行的约束方程为对偶单纯形法对偶单纯形法 当存在当存在br0，且对所对应的行中一切分量，且对所对应的行中一切分量arj0。那么。那么第第r行的约束方程为行的约束方程为 因因arj0j=m+1,n,又又br0，故不能够存在，故不能够存在xj0j=1,n的解，故原问题无可行解，这时对偶问题的解，故原问题无可行解，这时对偶问题的目的函数值无界。的目的函数值无界。 例例2-26 用对偶单纯形法求解以下问题用对偶单纯形法求解以下问题对偶单纯形法对偶单纯形法 列出初始单纯形表列出初始单纯形表Cj -4 -12 -18 0 0对偶单纯形法对偶单纯形法Cj -4 -12 -18 0 0当前基既是原始可行基，又是对偶可行基，因此是最优基。当前基既是原始可行基，又是对偶可行基，因此是最优基。最优解为最优解为x1=0，x2=3/2，x3=1，max z，=-36，即即min z=36对偶单纯形法对偶单纯