2.1-2对偶定义性质1.ppt

线性规划的对偶与对偶单纯形法 对偶的定义 对偶问题的性质 对偶的对偶就是原始问题 对偶定理 互补松弛关系 对偶可行基对偶单纯形法 对偶的经济解释DUAL对偶原理对偶问题概念：对偶问题概念：任何一个线性规划问题都有一个与之相对应任何一个线性规划问题都有一个与之相对应的线性规划问题，如果前者称为原始问题，后者的线性规划问题，如果前者称为原始问题，后者就称为就称为“对偶对偶”问题。问题。对偶问题是对原问题从另一角度进行的描述，对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系，在其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。理论，是线性规划理论的重要内容之一。问题的导出ABC拥有量工 时1113材 料1479单件利润233ABC拥有量工 时1113材 料1479单件利润233假设有客户提出要求，购买工厂所拥有的假设有客户提出要求，购买工厂所拥有的工时和材料，为客户加工别的产品，由客工时和材料，为客户加工别的产品，由客户支付工时费和材料费。那么工厂给工时户支付工时费和材料费。那么工厂给工时和材料制订的最低价格应是多少，才值得和材料制订的最低价格应是多少，才值得出卖工时和材料出卖工时和材料?ABC拥有量工 时1113材 料1479单件利润233出卖资源获利应不少于生产产品的获利出卖资源获利应不少于生产产品的获利;约束约束价格应该尽量低，这样，才能有竞争力价格应该尽量低，这样，才能有竞争力;目标目标价格应该是非负的价格应该是非负的 ABC拥有量工 时1113材 料1479单件利润233用用y1和和y2分别表示工时和材料的出售价格分别表示工时和材料的出售价格总利润最小总利润最小 min W=3y1+9y2保证保证A产品利润产品利润 y1+y22 保证保证B产品利润产品利润 y1+4y23 保证保证C产品利润产品利润 y1+7y23 售价非负售价非负 y10 y20ABC拥有量工 时1113材 料1479单件利润233对偶问题的定义对称形式的对偶问题对偶的定义对偶的定义原始问题原始问题min f(x)=CTXs.t.AXbX 0对偶问题对偶问题max z(y)=bTys.t.ATyCy 0minbACTCATbTmaxmnmn对偶问题的特点对偶问题的特点l（1）目标函数在一个问题中是求最大值在）目标函数在一个问题中是求最大值在另一问题中则为求最小值另一问题中则为求最小值l（2）一个问题中目标函数的系数是另一个）一个问题中目标函数的系数是另一个问题中约束条件的右端项问题中约束条件的右端项l（3）一个问题中的约束条件个数等于另一）一个问题中的约束条件个数等于另一个问题中的变量数个问题中的变量数l（4）原问题的约束系数矩阵与对偶问题的）原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵约束系数矩阵互为转置矩阵min f=CTXs.t.AXbX 0max z=bTYs.t.ATYC Y 0其他形式问题的对偶其他形式问题的对偶min f=CTXs.t.AXbX 0max z=bTYs.t.ATYC Y 0min f=CTXs.t.AX=bX 0max z=bTYs.t.ATYC Y：unr 一般线性规划问题的对偶问题对偶问题对应表对偶问题对应表原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）目标函数目标函数min目标函数目标函数max约束条件：约束条件：m个个第第i个约束类型为个约束类型为“”第第i个约束类型为个约束类型为“”第第i个约束类型为个约束类型为“”变量数：变量数：m个个第第i个变量个变量0第第i个变量个变量0第第i个变量是自由变量个变量是自由变量 变量数：变量数：n个个第第j个变量个变量 0第第j个变量个变量 0第第j个变量是自由变量个变量是自由变量 约束条件：约束条件：n个个第第j个约束类型为个约束类型为“”第第j个约束类型为个约束类型为“”第第j个约束类型为个约束类型为“”例写出如下LP问题的对偶问题对偶问题对偶问题的性质1、对偶的对偶就是原始问题、对偶的对偶就是原始问题max z=-CTXs.t.-AX-bX 0min y=-bTWs.t.-ATW-CW 0max y=bTWs.t.ATWCW 0min z=CTXs.t.AXb X 0对偶的定义对偶的定义对偶的定义对偶的定义2、对偶定理（1）弱对偶性（可行解的目标函数值之间的关系）弱对偶性（可行解的目标函数值之间的关系）设设X、Y分别是原始问题和对偶问题的可行解分别是原始问题和对偶问题的可行解 f=CTX YTAX YTb=z（3）最优性）最优性（2）无界性）无界性如果原问题（对偶问题）具有无界解，如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。则其对偶问题（原问题）无可行解。无界性在一对对偶问无界性在一对对偶问题，若其中一个问题可行题，若其中一个问题可行但目标函数无界，则另一但目标函数无界，则另一个问题不可行；反之不成个问题不可行；反之不成立。这也是对偶问题的无立。这也是对偶问题的无界性。界性。关于无界性有如下结论：关于无界性有如下结论：问题无界问题无界无可无可行解行解无可行解无可行解无可行解无可行解问题无界问题无界对偶问题对偶问题原问题原问题无界无界如：如：（原）（原）无可无可行解行解（对）（对）已知已知试用对偶理论证明原问题无界。试用对偶理论证明原问题无界。解：解：=（0.0.0）是）是 P 的一个可行解，而的一个可行解，而 D 的第一的第一个约束条件不能成立（因为个约束条件不能成立（因为y1,y2 0)。因此，对偶问因此，对偶问题不可行，可知，原问题无界。题不可行，可知，原问题无界。（4）强对偶性（最优解的目标函数之间的关系）强对偶性（最优解的目标函数之间的关系）如果原问题有最优解，则其对偶问题也一定有如果原问题有最优解，则其对偶问题也一定有最优解，且两者的目标函数值相等最优解，且两者的目标函数值相等设设X*、Y*分别是原始问题和对偶问题的最优解分别是原始问题和对偶问题的最优解 f=CTX*=Y*TAX*=Y*Tb=z3、原始问题和对偶问题最优解之间的互补松弛关系min z=CTXs.t.AX-XS=b X,XS0max y=bTWs.t.ATW+WS=C W,WS0min z=CTXs.t.AXb X 0max y=bTWs.t.ATWC W0对偶引进松弛变量引进松弛变量XTWS=0 WTXS=0两者都是最优解互补松弛关系X，XsW，Wsw1 wi wm wm+1 wm+j wn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量 对偶问题的松弛变量 原始问题的变量 原始问题的松弛变量xjwm+j=0wixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0在线性规划问题的最优解中，在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；则该约束条件取严格等式；反之如果约束条件取严格不等式，反之如果约束条件取严格不等式，3、互补松弛性互补松弛性则其对应的对偶变量一定为零。则其对应的对偶变量一定为零。即即例2 线性规划解：先写出它的对偶问题例、已知线性规划问题例、已知线性规划问题:其对偶问题的最优解。其对偶问题的最优解。试用试用互补松弛定理互补松弛定理找出原问题的最优解。找出原问题的最优解。解：原问题的对偶问题为：解：原问题的对偶问题为：由对偶问题最优解可知，由对偶问题最优解可知，由互补松弛定理，由互补松弛定理，解方程组解方程组 所以原问题最优解所以原问题最优解l练习已知线性规划问题对偶单纯形法对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。对于标准线性规划问题：可行基B 若B对应的基本解是可行解最优基B 若B对应的基本解是最优解对偶可行基B 若CBB-1是对偶问题可行解 即 C-CBB-1A0 或 检验数0 对于标准线性规划问题：最优基B可行基B 对偶可行基B单纯形法可行基B 保持可行性 对偶可行基B对偶单纯形法可行基B 保持对偶可行性 对偶可行基B对于标准线性规划问题：对偶单纯形法可行基B 保持对偶可行性 对偶可行基B 找一个基，建立初始对偶单纯形表，检验数全部非负；若b列元素非负，则已经是最优基。反之，则取相应行的基变量为出基变量；为保证能对基的可行性有所改进，则将来的主元应该为负数；为保证下一个基还能是对偶可行基，应使检验数仍为非负的。主元变换l下面通过例题说明对偶单纯形法的步骤：例3 用对偶单纯形法求解线性规划问题：解：先将问题改写为：2）算法步骤第一步：建立一个初始单纯形表，使表中检验行的 值全部 即对其对偶问题而言是一基本可行解约束条件两端乘“1”，得根据原问题和对偶问题之间的对称关系，这时单纯形表中原基变量列数字相当于对偶问题解的非基变量的检验数第二步：由于对偶问题的求解是使目标函数达到最小值所以最优判别准则是当所有检验数大于等于零时 为最优（也即这时原问题是可行解）如果不满足这个条件，找出绝对值最大的负检验数，设为，其对应的原问题的基变量即为对偶问题的换入变量第三步：将行数字与表中第行对应的数字对比令第五步：重复第二四步，一直到找出最优解为止。第五步：重复第二四步，一直到找出最优解为止。第四步：用换入变量替换对偶问题中的换出变量（在单纯第四步：用换入变量替换对偶问题中的换出变量（在单纯 形表中反映为用形表中反映为用 替原问题的基变量替原问题的基变量 ），），得到一个新的单纯形表。得到一个新的单纯形表。表中数字计算同用单纯形法时完全一样。表中数字计算同用单纯形法时完全一样。新表中对偶问题仍保持基本可行解，原问题基变新表中对偶问题仍保持基本可行解，原问题基变量列数字相当于对偶问题的检验数。量列数字相当于对偶问题的检验数。y2 1/3 y5 1/3 0 1 1/6 1/6 05 0 -2/3 1/3 1Cj -8 15 0 1 4 0 y2 1/4 y3 5/4 1 0 1/4 1/415/2 0 1 1/2 3/2cj -17/2 15/2 0 0 7/2 3/2 15 24 5 0 0 y1 y2 y3 y4 y5 y4 2 y5 1 0 6 1 1 0 5 2 1 0 1cj 0 15 24 5 0 0例4 考虑线性规划问题基变量右端项f 6.8 3 0 0 0 0 0 x3 -2.6 -1 1 0 0 0 -800 x4 -3.8 -3 0 1 0 0 -1000 x5 -1.6 -1 0 0 1 0 -100 x6 -6 -10 0 0 0 1 -6000基变量右端项f 5 0 0 0 0 0.3 -1800 x3 -2 0 1 0 0 -0.1 -200 x4 -2 0 0 1 0 -0.3 800 x5 -1 0 0 0 1 -0.1 500 x2 0.6 1 0 0 0 -0.1 600基变量右端项f 0 0 2.5 0 0 0.05 -2300 x1 1 0 -0.5 0 0 0.05 100 x4 0 0 -1 1 0 0.02 1000 x5 0 0 -0.5 0 1 0.05 600 x2 0 1 0.3 0 0 0.13 540 至此，右端项的所有分量都已非负，当前的迭代至此，右端项的所有分量都已非负，当前的迭代点已是一个对偶可行的饿基本可行解，因而也是最优点已是一个对偶可行的饿基本可行解，因而也是最优解，即最优解为解，即最优解为 相应的目标函数值为相应的目标函数值为l单纯形法是在基本可行解中寻找满足最优性条件（简约价值系数非负）的最优解l对偶单纯形法则是在所有满足最优性条件（简约价值系数非负）的最优解中寻找满足可行的最优解单纯形法与对偶单纯形法对偶的经济解释1、原始问题是利润最大化的生产计划问题单位产品的利润（单位产品的利润（元元/件）件）产品产量产品产量（件）（件）总利润总利润（元）（元）资源限量资源限量（吨）（吨）单位产品消耗的资源（吨单位产品消耗的资源（吨/件）件）剩余的资源剩余的资源（吨）吨）消耗的资源消耗的资源（吨）（吨）2、对偶问题资源限量资源限量（吨）（吨）资源价格（元资源价格（元/吨）吨）总利润总利润（元）（元）对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为称为m种资源的影子价格（种资源的影子价格（Shadow Price）原始和对偶问题都取得最优解时，原始和对偶问题都取得最优解时，最大利润最大利润 max z=min y3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于的影子价格一定等于0w1w2wm4、产品的机会成本机会成本机会成本表示减少一件产品所节省的资源可以增加的利润表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源减少一件产品可以节省的资源5、互补松弛关系的经济解释在利润最大化的生产计划中在利润最大化的生产计划中（1）边际利润大于）边际利润大于0的资源没有剩余的资源没有剩余（2）有剩余的资源边际利润等于）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产）机会成本大于利润的产品不安排生产