运筹学对偶原理.pptx

第三章对偶原理3.1 3.1 LPLP的对偶关系的对偶关系DUAL3.1.13.1.1问题的提出问题的提出例1:某工厂拥有A、B、C三个车间，生产甲、乙两种产品。每件产品在生产中需要占用生产能力时数，每件产品可以获得的利润以及三个车间可利用的时数如下表所示：产品甲x1产品乙x2 生产能力（工时/天）A1 10 08 8B0 02 21212C3 34 43636利润（百元/件）3 35 5目标函数 Max z=3x1+5x2约束条件 x1 8 s.t.2x2 12 3x1+2x2 36 x1，x2 0 设有，设有，y1,y2,y3 分别为出售分别为出售A，B，C工时所得工时所得利润（百元利润（百元/工时），工时），w为总盈利额（百元）为总盈利额（百元）对偶的定义对偶的定义线性规划问题在形式上，可以形成一对对称线性规划问题在形式上，可以形成一对对称问题，对任何线性规划求最大值问题，都有问题，对任何线性规划求最大值问题，都有一个与之对称的求最小值问题，这两个有关一个与之对称的求最小值问题，这两个有关的约束条件的系数矩阵，具有相同的数据，的约束条件的系数矩阵，具有相同的数据，仅形式互为转置，并且目标函数与约束右端仅形式互为转置，并且目标函数与约束右端项互换，其目标函数的最优值也是彼此相等项互换，其目标函数的最优值也是彼此相等的，我们把线性规划的这个对称问题称为对的，我们把线性规划的这个对称问题称为对偶问题。偶问题。原始问题max z=CTXs.t.AX bX 0对偶问题min w=bTYs.t.ATY CY 0maxbACTCATbTminmnmn原始问题Primal problem 对偶问题Dual problemP1D13.1.23.1.2 对偶关系对偶关系 关系关系1 规范对偶关系规范对偶关系对称对偶对称对偶关系关系2 标准性标准性LP问题的对偶关系问题的对偶关系 非非对对称称对对偶偶自自由由Y关系关系3 一般对偶关系一般对偶关系 原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 MaxZ目标函数目标函数 MinW约束条件数：约束条件数：m个个第第 i个个 约约 束束 条条 件件 类类 型型 为为“”第第 i个个 约约 束束 条条 件件 类类 型型 为为“”第第i个约束条件类型为个约束条件类型为“=”对偶变量数：对偶变量数：m个个第第i个变量个变量0第第i个变量个变量0第第i个变量是自由变量个变量是自由变量 决策变量数：决策变量数：n个个第第j个变量个变量0第第j个变量个变量0第第j个变量是自由变量个变量是自由变量 约束条件数：约束条件数：n第第 i个个 约约 束束 条条 件件 类类 型型 为为“”第第 i个个 约约 束束 条条 件件 类类 型型 为为“”第第i个约束条件类型为个约束条件类型为“=”关系关系3 一般对偶关系一般对偶关系min z=CTXs.t.AXbX 0maxw=bTYs.t.ATYCY0 几种形式的对偶关系几种形式的对偶关系maxz=CTXs.t.AXbX0minw=bTYs.t.ATYCY0maxz=CTXs.t.AX=bX0minw=bTYs.t.ATYCY：自由求对偶问题求对偶问题例题例题 max=7y1+4y2-2y3minZ=3x1+2x2-6x3+x5 2y1+y2-y3 3 2x1+x2-4x3+x4+3x5 7 y1 +3y3 2 x1+2x3-x4 4 -4y1+2y2 -6 -x1+3x2 -x4+x5 =-2 y1 -y2 -y3 0 x1，x2，x3 0;3y1 +y3=1 x4 0;x5无限制无限制 y1 0y2 0y3 无约束无约束 3.2 对偶问题的基本性质对偶问题的基本性质1 1 对称性：对偶问题的对偶问题对称性：对偶问题的对偶问题是原问题是原问题 对偶的对偶就是原始问题对偶的对偶就是原始问题minz=-CTXs.t.-AX-bX0max w=-bTYs.t.-ATY-CY0min w=bTYs.t.ATYCY 0max z=CTXs.t.AX b X 0对偶的对偶的定义定义对偶的定义对偶的定义2 2 弱对偶性：极大化原问题的弱对偶性：极大化原问题的任一可行解的目标函数值，不任一可行解的目标函数值，不大于其对偶问题任意可行解的大于其对偶问题任意可行解的目标函数值目标函数值 3 3 最优性：最优性：XX、YY分别为分别为原问题与对偶问题的可行解，原问题与对偶问题的可行解，且且CX=YbCX=Yb，则两者均为最优，则两者均为最优解。解。P 774 4 对偶定理：对偶定理：LPLP问题的问题的P P和和D D问题问题1 1）若一个问题有最优解，则另一问题也）若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。有最优解，且目标函数值相等。2 2）原问题无界，对偶问题无可行解。原问题无界，对偶问题无可行解。5 兼容性兼容性 原始问题的检验矢给出对偶问题的一个基本解原始问题的检验矢给出对偶问题的一个基本解6 6、原始问题和对偶问题最优解之间的、原始问题和对偶问题最优解之间的互补松弛关系互补松弛关系min z=CTXs.t.AXb X 0max y=bTYs.t.ATYC Y0min z=CTXs.t.AX-XS=b X,XS0max y=bTYs.t.ATY+YS=C Y,YS0XTYS=0 YTXS=0对偶对偶引进松弛变量引进松弛变量Y，YsX，Xs引进松弛变量引进松弛变量互补松弛关系互补松弛关系y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0，另一个一定等于，另一个一定等于0例例4 求解下列求解下列LP问题，并给出对偶问题的最优解问题，并给出对偶问题的最优解Max Z=x1+2 x2 2 x1+2 x2 8 0 x1+2 x2 4 x1,x2 0对偶问题为对偶问题为:Min w=8y1+4y22y1+0 y2 12y1+2 y2 2y1,y2 0 最优解为最优解为:x1=2,x2=2,x3=0,x4=0 y1=1/2,y2=1/2,y3=0,y4 =0Cj1200CbxBbx1x2x3x40 x30 x4 00201221084y3y4y1y24/2=2/8/2=44/2=2 Min20101/2-100102x3x22 1 0 1/2 -1/22 0 1 0 1/20 0 1/2 1/2-1 -2 0 04 2 0 1 -1x1x2y3y4y1y212y3 y4 y1 y2 4 63.3对偶的经济解释对偶的经济解释原始问题是利润最大化的生产计划问题原始问题是利润最大化的生产计划问题单位产品的利润（单位产品的利润（元元/件）件）产品产量（件）产品产量（件）总利润（元）总利润（元）资源限量（吨）资源限量（吨）单位产品消耗的资源（吨单位产品消耗的资源（吨/件）件）剩余的资源（剩余的资源（吨）吨）消耗的资源（吨）消耗的资源（吨）W=yb=(y1 ym)b1bm=b1 y1+b2 y2+bm ymbi：第第 i 种资源的数量种资源的数量yi：对偶解对偶解bi增加增加 bi,其它资源数量不变时其它资源数量不变时,目标函数目标函数的增量的增量 Z=bi yi3.3对偶的经济解释对偶的经济解释 Z bi=yi对偶解对偶解y y：b b 的单位改变量所引起的目标函数的单位改变量所引起的目标函数改变量。改变量。也为第也为第I I种资源的边际价值种资源的边际价值(影子价影子价格格)Zz=421/2影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于价格一定等于0用影子价格与市场价格相比较，帮助决策是否买入该资用影子价格与市场价格相比较，帮助决策是否买入该资源源对偶变量的经济解释对偶变量的经济解释(影子价格影子价格(Shadow Price)目标函数 Max z=3x1+5x2约束条件 x1+8 s.t.2x2 12 3x1+2x2 36 x1，x2 0 目标函数 Max z=3x1+5x2约束条件 x1+x x3 3 =8 s.t.2x2 +x x4 4 =12 3x1+2x2 +x x5 5 =36 x1，x2，x x3 3，x x4 4 ，x x5 5 0 3.4 对偶单纯形法对偶单纯形法 由于单纯形法表格同时给出原始、对偶问题的由于单纯形法表格同时给出原始、对偶问题的互补基本解互补基本解,引出对偶单纯形法的思路引出对偶单纯形法的思路 P84P843.4.1 3.4.1 规范对偶单纯形法规范对偶单纯形法计算步骤计算步骤 P85 3.5 交替单纯形法交替单纯形法