运筹学对偶问题

第四章对偶问题对偶问题的一般形式对偶问题的经济意义对偶性质对偶单纯形法对偶单纯形法的解题原理一、对偶问题的一般形式若设一线性规划问题如下：（A）0,0,0..max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcF则以下线性规划问题：（B）称为原问题（A）的对偶线性规划问题，或称A、B互为对偶问题。0,0,0..min21221122222112112211112211mnmmnnnmmmmmmyyycyayayacyayayacyayayatsybybybW如果采用向量、矩阵来表示0..maxXBAXtsCXF0..minYCYAtsYBWTncccC21myyyY21mbbbB21nxxxX21mnmnnnaaaaaaaaaA212222111211（A）（B）其中：可以将以上关系列成以下对偶表：maxminx1x2…xnby1a11a12…a1n≤b1y2a21a22…≤b2…………………ymam1am2…amn≤bm≥≥…≥cc1c2…cn例写出下列线性规划问题的对偶问题0,0,060424824..13146max321321321321xxxxxxxxxtsxxxF解：可以将原问题的有关参数列成下表maxminx1x2x3by1142≤48y2124≤60≥≥≥c61413∴对偶规划问题为0,0134214246..6048min2121212121yyyyyyyytsyyW比较以上我们介绍的对偶问题是严格定义的对偶问题，也成为对称对偶问题。它满足两个条件：0,0,060424824..13146max321321321321xxxxxxxxxtsxxxF0,0134214246..6048min2121212121yyyyyyyytsyyW两个条件：1、所有变量非负：即X0，Y02、约束条件均为同向不等式。若原问题约束条件均为“≤”，则它的对偶问题的约束条件都是“≥”。当原问题的约束条件的符号不完全相同时，也存在对偶问题，这种对偶问题称为非对称对偶问题。例分析：为求对偶问题，可先做过渡，将问题对称化：为自由变量2121212121,0510342023..54maxxxxxxxxxtsxxZ对称化为自由变量2121212121,0510342023..54maxxxxxxxxxtsxxZ0x,0x,xxx55103443432212121设xxxxxx521xx则，原问题变为0,0,0551033420223..554'max431431431431431431xxxxxxxxxxxxxxxtsxxxZ为自由变量2121212121,0510342023..54maxxxxxxxxxtsxxZ（A）（A‘）则（A’）的对偶问题如下：0',0',0',0'5'''3'25'''3'24'''4'3..'5'5'10'20'min43214321432143214321yyyyyyyyyyyyyyyytsyyyyW（B‘）0,0,0551033420223..554'max431431431431431431xxxxxxxxxxxxxxxtsxxxZ（A‘）对比结果以上对偶问题（B‘）并非原问题（A）的对偶问题，它是线性规划问题（A’）的对偶问题。0',0',0',0'5'''3'25'''3'24'''4'3..'5'5'10'20'min43214321432143214321yyyyyyyyyyyyyyyytsyyyyW为自由变量2121212121,0510342023..54maxxxxxxxxxtsxxZ（A）（B‘）调整对照问题B‘目标函数系数的符号与原问题A中约束条件右端常数项的符号，可做以下调整：令y1=y1’，y2=-y2’，y3=y4’-y3’令y1=y1’，y2=-y2’，y3=y4’-y3’则得到以下对偶问题为自由变量321321321321321,0,0532532443..51020minyyyyyyyyyyyytsyyyW0',0',0',0'5'''3'25'''3'24'''4'3..'5'5'10'20'min43214321432143214321yyyyyyyyyyyyyyyytsyyyyW（B‘）（B）合并为自由变量321321321321321,0,0532532443..51020minyyyyyyyyyyyytsyyyW为自由变量321321321321,0,0532443..51020minyyyyyyyyytsyyyW（B）比较对于任何一个线性规划问题，我们都可以求出它的对偶问题。为自由变量2121212121,0510342023..54maxxxxxxxxxtsxxZ（A）（B）为自由变量321321321321,0,0532443..51020minyyyyyyyyytsyyyW原问题与对偶问题的相应关系原问题A（对偶问题B）对偶问题B（原问题A）最大化max最小化minA系数矩阵ATB右端常数（列向量）目标函数系数(行向量)C目标函数系数右端常数（列向量）第i个约束条件为等式“=”yi为自由变量第i个约束条件为不等式“≤”yi≥0第i个约束条件为不等式“≥”yi≤0xj为自由变量第j个约束条件为等式“=”xj≥0第j个约束条件为不等式“≥”xj≤0第j个约束条件为不等式“≤”例：写出下列问题的对偶形式：为自由变量321321321321321,0,041632532..34maxxxxxxxxxxxxxtsxxxZ解：为自由变量321321321321321,0,036543132..42minyyyyyyyyyyyytsyyyW为自由变量321321321321321,0,041632532..34maxxxxxxxxxxxxxtsxxxZ例：写出下列问题的对偶问题,0,,0247325433432..4323min43,21432143243214321xxxxxxxxxxxxxxxtsxxxxZ为自由变量解：为自由变量32132132132131321,0,04444373323232..253maxyyyyyyyyyyyyyytsyyyW,0,,0247325433432..4323min43,21432143243214321xxxxxxxxxxxxxxxtsxxxxZ为自由变量二、对偶问题的经济意义：若原规划问题是“在一定条件下，使工作或成果（产品产量、利润等）尽可能的大”，那么它的对偶问题就是“在另外一些条件下，使工作的消耗（浪费、成本等）尽可能的小”。实际上是一个问题的两个方面。例：某产品计划问题的线性规划数学模型为0,10251553..2max21212121xxxxxxtsxxF（设备的约束）（原料的约束）假设生产部门根据市场变化，决定停止生产甲、乙产品，而将原有的原料、设备专用于接受外来订货以生产市场急需的紧俏商品，则需要考虑决策的问题就是“在什么样的价格条件下，才能接受外来订货？”。问题的实质就是如何确定原料、设备的收费标准？分析若设y1为单位原材料的价格，y2为设备单位台时价格，由于用了3个单位原料和5个单位设备台时就可以生产一个单位甲产品而获利2个单位，现在不生产甲产品，转而接受外来订货加工，则收取的费用不能低于2个单位，否则自己生产甲产品更有利。因此，可以得到下面的条件：25321yy分析同理，将生产乙产品的原料和设备工时用于接受外来加工订货，收取的费用不能低于乙产品的单位利润1个单位：12521yy分析另外，为了争取外来加工订货，在满足上述要求的基础上，收费标准应尽可能低从而具有竞争力，因此总的收费w=15y1+10y2应极小化。这样，就得到一个目标函数：211015minyyW这样，就得到另一个线性规划模型：0,0125253..1015min21212121yyyyyytsyyW比较0,0125253..1015min21212121yyyyyytsyyW0,10251553..2max21212121xxxxxxtsxxF生产问题（要利用资源）资源利用问题（会影响生产）第二节对偶理论定理1（对称性定理）对偶问题（B）的对偶规划为线性规划（A）对称性定理是很重要的。它表明原规划问题（A）和对偶规划问题（B）是互为对偶的。也就是说，如果（B）是（A）的对偶，那么（A）也是（B）的对偶。这就为以后的讨论带来方便。不难理解，如果当A具有某种性质时可以推出B的某些性质，于是可以无需另加证明地得到：当B具有某种性质时，问题A也具有那些性质。定理2（弱对偶定理）当原问题A是求最大值max，而对偶问题是求最小值时，如果X0是原问题的任意可行解，Y0是对偶问题的任意可行解，则有以下关系式成立：BYCX00定理3（最优性定理）设和分别是问题A和B的可行解，若相应于和，A和B的目标函数值相等，即，则和分别是A和B的最优解。xyxybyxcyx定理4（无界性定理）如果原问题A的目标函数值无界，则对偶问题B无可行解；如果对偶问题B的目标函数值无界，则原问题A无可行解。以上三个定理可以这样记忆原问题A和对偶问题B如果有可行解，则它们的可行解区域只可能相接，不可能相交。两个区域的交界线即是它们的最优解，如果原问题A的目标函数无界，意味着可行解区域无界，向外扩张，挤占了对偶问题B的可行解区域，则对偶问题无可行解，反之同理可说明。对偶问题(B)minW原问题(A)maxZy0bcx0byxc定理5（强对偶定理）若线性规划A存在最优解，则对偶规划B也存在最优解，并且它们的最优值相等；相反地，若规划B存在最优解，则规划A也存在最优解，并且它们的最优值相等。定理6（存在性定理）若线性规划A和B都存在可行解，则A和B都存在最优解。第三节对偶单纯形法条件：①b列中至少有一个bi0；②原问题A的检验数满足符号条件。例)4,3,2,1(024232..34min43214321421jxxxxxxxxxtsxxxZj解：minmax解：引入松弛变量，化为标准形式：)6,,2,1(024232..34'max6432154321421jxxxxxxxxxxxtsxxxZj观察A矩阵101412011121A解以上标准形式中没有完全单位向量组，我们将约束条件进行变换，两边同乘（-1）。A矩阵中存在完全单位向量组，但bi0，考虑求解。用单纯形法求解。)6,,2,1(024232..34'max6432154321421