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

《《管理运筹学》02-5对偶原理.ppt》由会员分享，可在线阅读，更多相关《《管理运筹学》02-5对偶原理.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、 y3 3 2 2 2y y1 1+2 2y y2 2 +4 4y y4 4 3 3 Min wMin w=12y y1 1+8y y2 2+16y y3 3+12y y4 421402 22 20 04 412128 8 16 16 1212A B C D车间车间 产品产品 甲甲 乙乙单耗（工时单耗（工时/件）件）加工能力加工能力（工时（工时/天）天）利润利润 2 3s.t.s.t.2 2x x1 1+2 2x x2 2 12 12 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1 ，x x2 2 0 0 max z=2m

3、ax z=2x x1 1+3+3x x2 2y y1 1，y y2 2，y y3 3，y y4 4 0 0 y y3 3第3节 对偶与灵敏度分析4 原问题原问题原问题原问题 对偶问题对偶问题对偶问题对偶问题线性规划的对偶关系线性规划的对偶关系第3节 对偶与灵敏度分析5线性规划的对偶关系线性规划的对偶关系 min w=8y1+12y2+36y3 y1 +3y3 3 2y2 +4y3 5 y1,y2,y3 0 s.t.Y*Y*=(0(0,1/21/2,1)1)T T w*w*=42 42 maxmax z z =3 3 x x1 1 +5 5x x2 2 x x1 1 8 8 2 2x x2 2

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

5、题变量的符号与标准形式相反设设X=-X对偶问题对偶问题对偶变量对偶变量Y第3节 对偶与灵敏度分析9对偶问题典式对偶问题典式第3节 对偶与灵敏度分析其他形式的对偶问题其他形式的对偶问题10关系关系：一般一般一般一般对偶关系对偶关系第3节 对偶与灵敏度分析线性规划的对偶关系线性规划的对偶关系11 例例2-212-21 max z=8 8 x1+5 5 x2 -x1+2 2 x2 4 4 3 3 x1 -x2 =7 7 2 2 x1+4 4 x2 8 8 x1,x2 0 min w=4 4y1+7 7y2+8 8y3 -y1+3 3 y2+2 2y3 8 8 2 2 y1 -y2+4 4y3 5 5

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

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

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

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

10、这样一对基本解称为互补基本解互补基本解。第3节 对偶与灵敏度分析对偶问题的性质对偶问题的性质20:max z=3x1+5x2 x1 8 2x2 12 3x1+4x2 36 x1 ，x2 0s.t.(P1):min w=8y1+12y2+36y3 y1 +3y3 3 2y2+4y3 5 y1,y2,y3 0s.t.(D1):max z=3x1+5x2 x1 +x3 =8 2x2 +x4 =12 3x1+4x2 +x5 =36 x1,x2,x3,x4,x5 0s.t.(Ps s):min w=8y1+12y2+36y3 y1 +3y3-y4 =3 2y2+4y3 -y5=5 y1,y2,y3,y4

11、,y5 0s.t.(Ds s)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

12、 ，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,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,-1

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

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

15、法对偶单纯形法基本思想：基本思想：基本思想：基本思想：在迭代过程中保持对偶可行条件和互补松在迭代过程中保持对偶可行条件和互补松在迭代过程中保持对偶可行条件和互补松在迭代过程中保持对偶可行条件和互补松弛条件满足，并且在迭代过程中不断改进原始可行弛条件满足，并且在迭代过程中不断改进原始可行弛条件满足，并且在迭代过程中不断改进原始可行弛条件满足，并且在迭代过程中不断改进原始可行条件。当原问题和对偶问题均为可行解时，即求得条件。当原问题和对偶问题均为可行解时，即求得条件。当原问题和对偶问题均为可行解时，即求得条件。当原问题和对偶问题均为可行解时，即求得了最优解。了最优解。了最优解。了最优解。第3节 对

16、偶与灵敏度分析27对偶单纯形法对偶单纯形法算法步骤：算法步骤：算法步骤：算法步骤：11线性规划的检验数行线性规划的检验数行zjcj 0，但，但bi中存在负的分量。中存在负的分量。即该问题的即该问题的对偶问题是基本可行解对偶问题是基本可行解，原问题不是基本，原问题不是基本可行解。可行解。22确定出基变量确定出基变量确定出基变量确定出基变量：在小于零的在小于零的bi时，令出基变量时，令出基变量br=min bi，其对应的变量，其对应的变量xr作为出基变量。作为出基变量。33确定进基变量确定进基变量确定进基变量确定进基变量：（1）为使迭代后的表中第为使迭代后的表中第r行基变量为非负，因而只有行基变量

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

18、析29对偶单纯形法对偶单纯形法 当存在当存在br0，且对所对应的行中所有分量，且对所对应的行中所有分量arj0。则第。则第r行的约束方程为行的约束方程为 因因arj0（j=m+1,n）,又又br0，故不可能存在，故不可能存在xj0（j=1,n）的解，故原问题无可行解，这时对偶）的解，故原问题无可行解，这时对偶问题的目标函数值无界。问题的目标函数值无界。第3节 对偶与灵敏度分析例例2-26 用对偶单纯形法求解以下问题30对偶单纯形法对偶单纯形法第3节 对偶与灵敏度分析31列出初始单纯形表列出初始单纯形表Cj -4 -12 -18 0 0第3节 对偶与灵敏度分析对偶单纯形法对偶单纯形法32Cj -

19、4 -12 -18 0 0当前基既是原始可行基，又是对偶可行基，因而是最优基。当前基既是原始可行基，又是对偶可行基，因而是最优基。最优解为最优解为x1=0，x2=3/2，x3=1，max z，=-36，即即min z=36第3节 对偶与灵敏度分析对偶单纯形法对偶单纯形法33练习练习练习练习min z=3x1+2x2s.t.2x1+3x2 18 x1-x2 2 x1+3x2 10 x1,x2 0解解解解max z=-3x1-2x2s.t.2x1+3x2+x3 =18 x1 -x2 x4 =2 x1+3x2 x5=10 x1,x2,x3,x4,x5 0 x1+x2 +x4 =2x13x2 +x5=10第3节 对偶与灵敏度分析对偶单纯形法对偶单纯形法X*=(4,2)Tz*=16