线性规划中的对偶规划模型及对偶理论

一、对偶问题的提出1、对偶思想举例：某工厂拥有一定生产原材料时，该工厂考虑是自己进行产品生产所赚的利润大还是将其原材料直接出售给其它工厂时所以赚取的利润大的问题。第二章线性规划的对偶模型2、换个角度审视生产计划问题0x,x15x516x412x2x2.t.sx3x2MaxZ21212121例：（第一章例2）要求制定一个生产计划方案，在劳动力和原材料可能供应的范围内，使得产品的总利润最大。它的对偶问题就是一个价格系统，使在平衡了劳动力和原材料的直接成本后，所确定的价格系统最具有竞争力：0，y，yy3y5y22y4y2.t.sy15y16y12MinW3213121321（用于生产第i种产品的资源转让收益不小于生产该种产品时获得的利润）对偶变量的经济意义可以解释为对工时及原材料的单位定价；若工厂自己不生产产品A、B和C，将现有的工时及原材料转而接受外来加工时，那么上述的价格系统能保证不亏本又最富有竞争力（包工及原材料的总价格最低）当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的：Zmax=Wmin二、原问题和对偶问题的关系1、对称形式的对偶关系（1）定义：若原问题是0,,,..21221122222112112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcMaxZ则定义其对偶问题为0,,,..21221122222112112211112211mnnmnnnnmmmmmyyycyayayacyayayacyayayatsybybybMinW这两个式子之间的变换关系称为“对称形式的对偶关系”。原问题与对偶问题的对比：0,,,..21221122222112112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcMaxZ0,,,..21221122222112112211112211mnnmnnnnmmmmmyyycyayayacyayayacyayayatsybybybMinW若原问题对偶问题（2）对称形式的对偶关系的矩阵描述0..YCYAtsbYMinW（D）0..XbAXtsCXMaxZ（L）（3）怎样从原始问题写出其对偶问题？按照定义；记忆法则：“上、下”交换，“左、右”换位，不等式变号，“极大”变“极小”例写出下面线性规划的对偶问题：0x,x10x2x515x4x3.t.sxx2MaxZ212121210,124253..101521212121yyyyyytsyyMinW2、非对称形式的对偶关系：njxmibxatsxcMaxZjnjijijnjjj,,2,10,,2,1..11miynjcyatsxbMinWimijiijmiii,,2,1,,2,1..11符号不限，（1）原问题对偶问题（特点：对偶变量符号不限，系数阵转置）(特点：等式约束)（2）怎样写出非对称形式的对偶问题？把一个等式约束写成两个不等式约束，再根据对称形式的对偶关系定义写出；按照原始-对偶表直接写出；（3）原始-对偶表原问题（或对偶问题）对偶问题（或原问题）目标函数MaxZ目标函数MinW变量数：n个变量≥0变量≤0变量无约束约束条件数：n个约束条件≥约束条件≤约束条件=约束条件：m个约束条件≤约束条件≥约束条件=变量数：m个变量≥0变量≤0无约束课堂练习：写出下面线性规划的对偶规划：0,,01413121110987654..32432121321321321xxxxxxxxxxxtsxxxMinZ符号不限下面的答案哪一个是正确的？为什麽？0,0,31062139541284..1411732121321321321yyyyyyyyyyytsyyyMaxW符号不限0,0,31062139541284..1411732121321321321yyyyyyyyyyytsyyyMaxW符号不限（原问题是极小化问题，因此应从原始对偶表的右边往左边查！）√×三、对偶定理对偶定理是揭示原始问题的解与对偶问题的解之间重要关系的一系列性质。对称性——对偶问题的对偶是原问题。性质1弱对偶性——如果是原问题的可行解，其对偶问题的可行解，则恒有：0..XbAXtsCXMaxZ（L）0..YCYAtsbYMinW和（D）均有可行解，分别为和，则C≤b。X~X~Y~Y~证明思路：由（L）bXA~左乘，得bYXAY~~~Y~由（D）CAY~右乘，得X~XCXAY~~~bYXC~~),,1(~njXj),,1(~niYimiiinjjjybxc11~~miiinjjjybxc11~~•关于“界”的结果；•极小化问题有下界——推论1极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。•极大化问题有上界——推论2极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。性质2最优性若、分别为对称形式对偶线性规划的可行解，且两者目标函数的相应值相等，即则，分别为原始问题和对偶问题的最优解。X~X~Y~Y~miiinjjjybxc11~~性质3无界性如果原问题（对偶问题）具有无界解，则对偶问题（原问题）无可行解。注意：这个性质逆不成立。因为当原问题（对偶问题）无可行解时，其对偶问题（原问题）或无可行解或具有无界解。性质4强对偶性(或称对偶定理)如果原问题有最优解，则其对偶问题也一定具有最优解，且有minmaxz性质5互补松弛性在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。即：njijijibxa则y如果1ˆ,0ˆ0ˆˆ1injijijy，则bxa如果性质6线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松驰变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基解变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有：z