线性规划的对偶与对偶单纯形法

对偶原理对偶问题概念：任何一个线性规划问题都有一个与之相对应的线性规划问题，如果前者称为原始问题，后者就称为“对偶”问题。对偶问题是对原问题从另一角度进行的描述其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。问题的导出ABC拥有量工时1113材料1479单件利润233321332maxxxxZ0,0,09743..321321321xxxxxxxxxtsABC拥有量工时1113材料1479单件利润233假设有客户提出要求，购买工厂所拥有的工时和材料，为客户加工别的产品，由客户支付工时费和材料费。那么工厂给工时和材料制订的最低价格应是多少，才值得出卖工时和材料?ABC拥有量工时1113材料1479单件利润233•出卖资源获利应不少于生产产品的获利;约束•价格应该尽量低，这样，才能有竞争力;目标•价格应该是非负的ABC拥有量工时1113材料1479单件利润233用y1和y2分别表示工时和材料的出售价格总利润最小minW=3y1+9y2保证A产品利润y1+y2≥2保证B产品利润y1+4y2≥3保证C产品利润y1+7y2≥3售价非负y1≥0y2≥0ABC拥有量工时1113材料1479单件利润2332193minyyW0,037342..21212121yyyyyyyyts321332maxxxxZ0,0,09743..321321321xxxxxxxxxts对偶问题的定义1122minnnZcxcxcx111112121222221212..,,,0nnmmmnnmnxbaaaaaaxbstaaaxbxxx1122maxmmWbybyby111121112222221212..,,,0mmnnmnmnmycaaaaaaycstaaaycyyy对称形式的对偶问题对偶的定义原始问题minf(x)=CTXs.t.AX≥bX≥0对偶问题maxz(y)=bTys.t.ATy≤Cy≥0≥minbACTCATbT≤maxmnmn对偶问题的特点（1）目标函数在一个问题中是求最大值在另一问题中则为求最小值（2）一个问题中目标函数的系数是另一个问题中约束条件的右端项（3）一个问题中的约束条件个数等于另一个问题中的变量数（4）原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵minf=CTXs.t.AX≤bX≥0maxz=bTYs.t.ATY≤CY≤0其他形式问题的对偶minf=CTXs.t.AX≥bX≥0maxz=bTYs.t.ATY≤CY≥0minf=CTXs.t.AX=bX≥0maxz=bTYs.t.ATY≤CY：unr一般线性规划问题的对偶问题1122minnnfcxcxcxnjjmnmnmmnnnnxbxaxaxabxaxaxabxaxaxa~1),0(0),(),(),(22112222212111212111或符号不限1122maxmmzbybyby11121211121222221122,)1~(,)(,)(,)0(0mmmmnnmnmnjimayayaycayayaycayayaycy符号不限或对偶问题对应表原问题（对偶问题）对偶问题（原问题）目标函数min目标函数max约束条件：m个第i个约束类型为“≥”第i个约束类型为“≤”第i个约束类型为“＝”变量数：m个第i个变量≥0第i个变量≤0第i个变量是自由变量变量数：n个第j个变量≤0第j个变量≥0第j个变量是自由变量约束条件：n个第j个约束类型为“≥”第j个约束类型为“≤”第j个约束类型为“＝”例写出如下LP问题的对偶问题123min23fxxx123123123123,3264235390,xxxxxxxxxxxx符号不限0,123max659zyyy123123123123,y0,y03412232353yyyyyyyyyy符号不限对偶问题对偶问题的性质1、对偶的对偶就是原始问题maxz’=-CTXs.t.-AX≤-bX≥0miny=-bTWs.t.-ATW≥-CW≥0maxy=bTWs.t.ATW≤CW≥0minz=CTXs.t.AX≥bX≥0对偶的定义对偶的定义2、对偶定理（1）弱对偶性（可行解的目标函数值之间的关系）设X、Y分别是原始问题和对偶问题的可行解f=CTX≥YTAX≥YTb=zminTfCX..0TAYCstYmaxTzbYTTTTTCXAYXYAXYbbY..0AXbstX11ˆ(1,2,,)ˆ(1,2,,)ˆˆˆ(1,2,,)ˆ(1,2,,)jinmjjiijijixjnyimcxbyxjnyim如果是原问题的可行解　　是其对偶问题的可行解且有　　　则是原问题的最优解　是其对偶问题的最优解（3）最优性（2）无界性如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。无界性在一对对偶问题，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。关于无界性有如下结论：问题无界无可行解无可行解无可行解问题无界对偶问题原问题0,0242max21212121xxxxxxxxZ无界如：（原）0,01224min21212121yyyyyyyyW无可行解（对）已知12123123123:max2221,,0Zxxxxxxxxxxx原1212121212:min22120,0Wyyyyyyyyyy对试用对偶理论证明原问题无界。解：=（0.0.0）是P的一个可行解，而D的第一个约束条件不能成立（因为y1,y2≥0)。因此，对偶问题不可行，可知，原问题无界。__X（4）强对偶性（最优解的目标函数之间的关系）如果原问题有最优解，则其对偶问题也一定有最优解，且两者的目标函数值相等设X*、Y*分别是原始问题和对偶问题的最优解f=CTX*=Y*TAX*=Y*Tb=z**,TTBYBcAYc令则有**1TTTTBBYbYbBccBb这时是对偶问题的可行解，它使　　　**1TTBXcXcBb又由于是原问题的最优解，故　　　　***TTcXbYY　由此得到　　　　　　　可见是对偶问题的最优解。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，3、互补松弛性则其对应的对偶变量一定为零。即11ˆˆ0ˆˆ0niijjijnijjiijyaxbaxby如果，则　　如果　，则　123123123123min23..33122,,0xxxstxxxxxxxxx例2　给定线性规划问题　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　12111(,),77Tyyy已知对偶问题的最优解为试用互补松弛性质求原问题的最优解.1212121212max2..322331,0yystyyyyyyyy　　　　　12312,0,,yyxyy将最优解的值代入约束条件，得第3个约束为严格不等式，由互补松弛性得又由于的值均大于零，因此原问题的两个约束条件应取等式，故有12312331232xxxxxx解：先写出它的对偶问题12123min4,5/7,(,,)(4/7,5/7,0)23/7TTxxxxxxf求解后得到/7故原问题的最优解为　　　练习已知线性规划问题123451234512345min23523..2342330,1,2,,5jxxxxxstxxxxxxxxxxxj　　　　　　(1,0,0,0,1)Tx已知原问题的最优解为试用互补松弛性质找出对偶问题的最优解.对偶单纯形法对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。对于标准线性规划问题：可行基B若B对应的基本解是可行解最优基B若B对应的基本解是最优解对偶可行基B若CBB-1是对偶问题可行解即C-CBB-1A≥0或检验数≥0minfCX..TstAYC0..XbAXtsmaxzbY对于标准线性规划问题：最优基B可行基B对偶可行基B单纯形法可行基B保持可行性对偶可行基B对偶单纯形法可行基B保持对偶可行性对偶可行基BminfCX..TstAYCmaxzbY0..XbAXts对于标准线性规划问题：minfCX0..XbAXts对偶单纯形法可行基B保持对偶可行性对偶可行基B①找一个基，建立初始对偶单纯形表，检验数全部非负；②若b列元素非负，则已经是最优基。反之，则取相应行的基变量为出基变量；③为保证能对基的可行性有所改进，则将来的主元应该为负数；为保证下一个基还能是对偶可行基，应使检验数仍为非负的。④主元变换下面通过例题说明对偶单纯形法的步骤：例3用对偶单纯形法求解线性规划问题：12323123123min1524562521,,0wyyyyyyyyyyy　　　解：先将问题改写为：12323123123min1524562521,,0wyyyyyyyyyyy　　　'123452341235min1524500625210(1,2,3,4,5)iwyyyyyyyyyyyyyi　　　　　　'123452341235min1524500625210(1,2,3,4,5)iwyyyyyyyyyyyyyi　　　-　　　2）算法步骤第一步：建立一个初始单纯形表，使表中检验行的值全部即对其对偶问题而言是一基本可行解约束条件两端乘“－1”，得0,j'123452341235min1524500625210(1,2,3,4,5)iwyyyyyyyyyyyyyi　　　-　　　1234515245000[6]110521011524500yyyyy0j4521yy根据原问题和对偶问题之间的对称关系，这时单纯形表中原基变量列数字相当于对偶问题解的非基变量的检验数第二步：由于对偶问题的求解是使目标函数达到最小值所以最优判别准则是当所有检验数大于等于零时为最优（也即这时原问题是可行解）如果不满足这个条件，找出绝对值最大的负检验数，设为，其对应的原问题的基变量即为对偶问题的换入变量第三步：将行数字与表中第行对应的数字对比令lblxjlˆˆmin0jjljlljlklkkccaaaax　　即为主元素，为对偶问题的换出变量第五步：重复第二～四步，一直到找出最优解为止。第四步：用换入变量替换对偶问题中的换出变量（在单纯形表中反映为用替原问题的基变量），lxkx得到一个新的单纯形表。表中数字计算同用单纯形法时完全一样。新表中对偶问题仍保持基本可行解，原问题基变量列数字相当于对偶问题的检验数。y21/3y5－1/3011/6－1/60－50[-2/3]－1/31Cj-8150140y21/4y3½－5/410－1/41/415/2011/2－3/2cj-17/215/2007