线性规划的对偶理论2-对偶问题的性质.ppt
第二章第二章对偶理论与灵敏度分析对偶理论与灵敏度分析第二节第二节对偶问题的基本性质对偶问题的基本性质 例：例：某公司计划生产甲、乙两种产品，已知各生产一件某公司计划生产甲、乙两种产品，已知各生产一件时分别占用的设备时分别占用的设备A、B的台时、调试时间和调试工序每天的台时、调试时间和调试工序每天可用于这两种产品的能力、各销售一件时的获利情况，如下可用于这两种产品的能力、各销售一件时的获利情况，如下表所示。问该公司应生产两种产品各多少件，使获取的利润表所示。问该公司应生产两种产品各多少件，使获取的利润为最大。为最大。甲甲乙乙每天可用能力每天可用能力设备设备A(h)设备设备B(h)调试工序调试工序(h)06152115245利润（元）利润（元）21设设和和分别表示该公司生产甲乙两种产品的数量分别表示该公司生产甲乙两种产品的数量(LP1)化标化标准形准形+0 x3+0 x4+0 x5(LP2)化标化标准形准形+0 x3+0 x4+0 xcj 21000CB基基bx1x2x3x4x50 x315051000 x424620100 x5511001cj-zj 21000(LP1)cj 21000CB基基bx1x2x3x4x50 x315051000 x424620100 x5511001cj-zj 21000cj 21000CB基基bx1x2x3x4x50 x315051000 x424620100 x5511001cj-zj 210000 x315051002x1412/601/600 x5102/30-1/61cj-zj 01/30-1/30cj 21000CB基基bx1x2x3x4x50 x315051000 x424620100 x5511001cj-zj 210000 x315051002x1412/601/600 x5102/30-1/61cj-zj 01/30-1/300 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj 000-1/4-1/2最优解为最优解为X=(2/7,2/3,15/2,0,0)T，代入目标函数得，代入目标函数得z=8.5。加人工加人工变量变量(LP2)两阶段法两阶段法第一阶段第一阶段第二阶段第二阶段cj 00000-1-1CB基基by1y2y3y4y5y6y7-1y62061-1010-1y715210-101cj-zj 582-1100cj 00000-1-1CB基基by1y2y3y4y5y6y7-1y62061-1010-1y715210-101cj-zj 582-11000y21/3011/6-1/601/60-1y71/3502/31/3-1-1/31cj-zj 502/31/3-1-1/30cj 00000-1-1CB基基by1y2y3y4y5y6y7-1y62061-1010-1y715210-101cj-zj 582-11000y21/3011/6-1/601/60-1y71/3502/31/3-1-1/31cj-zj 502/31/3-1-1/300y21/3011/6-1/601/600y11/15102/151/15-1/5-1/151/5cj-zj 00000-1-1问题问题LP2有可行解，去除人工变量，并从最后一个表出发，有可行解，去除人工变量，并从最后一个表出发，继续用单纯形法求解。继续用单纯形法求解。cj -15-24-500CB基基by1y2y3y4y5-24y21/3011/6-1/60-15y11/15102/151/15-1/5cj-zj cj -15-24-500CB基基by1y2y3y4y5-24y21/3011/6-1/60-15y11/15102/151/15-1/5cj-zj 001-3-3cj -15-24-500CB基基by1y2y3y4y5-24y21/3011/6-1/60-15y11/15102/151/15-1/5cj-zj 001-3-3-24y21/4-5/410-1/41/4-5y31/215/2011/2-3/2cj-zj -15/200-7/2-3/2LP2的最优解为的最优解为Y=(0,1/4,1/2,0,0)T，代入目标函数得，代入目标函数得w=8.5。将将LP1和和LP2的最终单纯形表进行比较，我们观察有什的最终单纯形表进行比较，我们观察有什么特点？么特点？cj 21000CB基基bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj 000-1/4-1/2cj -15-24-500CB基基by1y2y3y4y5-24y21/4-5/410-1/41/4-5y31/215/2011/2-3/2cj-zj -15/200-7/2-3/2原问题变量原问题变量原问题松弛变量原问题松弛变量CB基基bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj 000-1/4-1/2对偶问题剩余变量对偶问题剩余变量对偶问题变量对偶问题变量y4y5y1y2y3对偶问题变量对偶问题变量对偶问题剩余变量对偶问题剩余变量CB基基by1y2y3y4y5-24y21/4-5/410-1/41/4-5y31/215/2011/2-3/2cj-zj -15/200-7/2-3/2原问题松弛变量原问题松弛变量原问题变量原问题变量x3x4x5x1x2maxz=CXs.t.AX+XS=bX,XS0minW=YTbs.t.ATY-YS=CTY,YS0XTYS=0YTXS=0mn=YYSAT-ICTn=AXS IbnmmX原问题和对偶问题变量、松弛变量的维数原问题和对偶问题变量、松弛变量的维数 y1yiymym+1ym+jyn+mx1xjxnxn+1xn+ixn+m对偶问题的变量对偶问题的变量对偶问题的松弛变量对偶问题的松弛变量原始问题的变量原始问题的变量原始问题的松弛变量原始问题的松弛变量互补松弛性互补松弛性xj ym+j=0yi xn+i=0(i=1,2,m；j=1,2,n)即：在一对变量中，其中一个大于即：在一对变量中，其中一个大于0，另一个一定等于，另一个一定等于0。对偶问题的基本性质：对偶问题的基本性质：2无界性：无界性：若原问题（对偶问题）为无界解，则其对偶问题若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。（原问题）无可行解。4强对偶性（对偶定理）：强对偶性（对偶定理）：若原问题及其对偶问题均具有可行若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。解，则两者均具有最优解，且它们最优解的目标函数值相等。1弱对偶性：弱对偶性：若若是原问题的可行解，是原问题的可行解，是对偶问题的可行是对偶问题的可行解，则存在解，则存在。3最优性：最优性：设是原问题的可行解，是对偶问题的设是原问题的可行解，是对偶问题的可行解，当时，和是最优解。可行解，当时，和是最优解。5互补松弛性：互补松弛性：若若，分别是原问题和对偶问题的可行解，分别是原问题和对偶问题的可行解，那么那么和和，当且仅当，当且仅当，为最优解。为最优解。1、可行解的目标函数值之间的关系、可行解的目标函数值之间的关系设设X、Y 分别是原始问题和对偶问题的可行解，则分别是原始问题和对偶问题的可行解，则z=CX YT b=w2、最优解的目标函数值之间的关系最优解的目标函数值之间的关系设设Xo、Yo分别是原始问题和对偶问题的最优解分别是原始问题和对偶问题的最优解z=CXo=yoTb=w3、原始问题和对偶问题最优解之间的互补松弛关系、原始问题和对偶问题最优解之间的互补松弛关系maxz=CXs.t.AX+XS=bX,XS0maxw/=-yT bs.t.AT Y-YS=CTY,YS0maxz=CXs.t.AX bX0minw=YTbs.t.AT YCTY0对偶对偶引进松弛变量引进松弛变量引进松弛变量引进松弛变量XT YS=0YT XS=0互补松弛关系互补松弛关系X，XsY，Ys例例 已知线性规划问题已知线性规划问题试用对偶理论证明上述线性规划问题无最优解试用对偶理论证明上述线性规划问题无最优解。证明：证明：该问题存在可行解，例如该问题存在可行解，例如X=(0,0,0)，其对偶问题其对偶问题为为由由第一约束条件可知对偶问题无可行解，因而无最优解。第一约束条件可知对偶问题无可行解，因而无最优解。
