最优化理论与方法--对偶原理

第4章对偶原理4.1线性规划中的对偶理论4.2对偶单纯形法原问题与对偶问题线性规划中普遍存在着配对的现象，即对每一个线性规划问题，都存在另一个与之密切联系的线性规划问题，其中之一称为原问题，而另一个成为它的对偶问题。对偶问题深刻揭示了每对问题中原问题与对偶问题的内在联系。【例】原问题与对偶问题某工厂拟生产甲、乙两种产品，需消耗煤、电、油三种资源。有关数据如表所示：产品资源单耗资源甲乙资源限量煤（t）94360电（kW·h）45200油（t）310300单位产品价格（万元）712问题一：试拟订使总收入最大的生产方案。问题二：若厂家不再打算生产甲、乙产品，而是打算将其资源全部卖掉。厂家要求：其收入不低于生产产品时的收入；买方希望：原料价格越低越好。试拟定能够保证卖方收入且使买方支出最小的定价方案。问题二：试拟定能够保证卖方收入且使买方支出最小的定价方案。解：设煤、电、油三种资源的定价分别为y1,y2,y3，买方总支出为w。【例】原问题与对偶问题1212121212max712..9436045200310300,0zxxstxxxxxxxx问题一：试拟订使总收入最大的生产方案。解：设拟生产甲、乙产品各x1,x2单位，总收入为z。min360200300123..9437123451012123,,0123wyyystyyyyyyyyy下面将会看到，这两个问题互为对偶问题，其中一个称为原问题，则另一问题就是它的对偶问题。资源甲乙数量煤94360电45200油310300单价712对偶问题的表述—对称形式原问题对偶问题min..0cxstAxbxmax..0wbstwAcw其中是矩阵，是m维列向量，是n维行向量，是由原问题的变量组成的n维列向量，是由对偶问题的变量组成的m维行向量。1(,...,)nAppmn1(,...,)Tmbbb1(,...,)nccc1(,...,)Tnxxx1(,...,)m对偶问题的表述–非对称形式对称形式原问题：对偶问题min..0cxstAxbxmax..0wbstwAcwmin..0cxstAxbxmax..wbstwAc非对称形式对偶问题的表述（一般形式）原问题对偶问题112233min..0cxstAxbAxbAxbx112233112233132max..00wbwbwbstwAwAwAc无限制原问题与对偶问题间的相互转换关系原问题（或对偶问题）一一对应对偶问题（或原问题）min问题max问题有m个约束条件,n个变量有m个变量,n个约束条件第i个约束条件为≤关系第i个变量≤0第i个约束条件为≥关系第i个变量≥0第i个约束条件为等式关系第i个变量无非负约束，是自由变量第j个变量≥0第j个约束条件为≤关系第j个变量≤0第j个约束条件为≥关系第j个变量无非负约束，是自由变量第j个约束条件为＝关系对偶问题的基本性质对偶问题的对偶是原问题。对偶定理（以对称对偶形式叙述）【定理4.1.1】若和分别是(4.1.1)和(4.1.2)的可行解，则。（可得到以下重要推论：）若和分别是(4.1.1)和(4.1.2)的可行解，且则和分别是(4.1.1)和(4.1.2)的最优解。对偶规划(4.1.1)和(4.1.2)有最优解的充要条件是它们同时有可行解。若原问题(4.1.1)的目标函数值在可行域上无下界，则对偶问题(4.1.2)无可行解；反之，若对偶问题(4.1.2)的目标函数值在可行域上无上界，则原问题(4.1.1)无可行解。(0)x(0)w(0)w(0)x(0)x(0)(0)cxwb(0)(0)cxwb(0)wmin..0cxstAxbxmax..0wbstwAcw（4.1.1）（4.1.2）对偶定理（以对称对偶形式叙述）【定理4.1.2】设原问题或对偶问题中有一个问题存在最优解，则另一个问题也存在最优解，且两个问题的目标函数值相等。【推论】若线性规划(4.1.1)存在一个对应基B的最优基本可行解，则单纯形乘子是对偶问题(4.1.2)的一个最优解。根据这个推论，能够从原问题的最优单纯形表中直接获得对偶问题的一个最优解。1BwcB对偶问题的基本性质互补松弛性质（见教材）对于对偶规划，当知道一个问题的最优解时，根据互补松弛定理求出另一个问题的最优解。对偶可行的基本解考虑线性规划问题(4.2.1)定义:设x(0)是(4.2.1)式的一个基本解，它对应的基矩阵为B，记w=cBB-1，若w是(4.2.1)式的对偶问题的可行解，即对所有j，成立，则称x(0)为原问题的对偶可行的基本解。min..0cxstAxbx0jjwpcmax..wbstwAc称为方程组的一个基本解10BNxBbxx对偶单纯形法的基本思想从原问题的一个对偶可行的基本解出发，求改进的对偶可行的基本解，当得到的对偶可行的基本解是原问题的可行解时，就达到最优解。这里改进的对偶可行的基本解的含义是：根据定义，对每个对偶可行的基本解都对应一个对偶问题的可行解w=cBB-1，相应的对偶问题的目标函数值为wb=cBB-1b。所谓改进的对偶可行的基本解，是指对于原问题的这个基本解，相应的对偶问题的目标函数值wb有改进。0Bxx对偶单纯形法的基本思想求改进的对偶可行的基本解的过程，也就是选择离基变量和进基变量，进行主元消去的过程。这与单纯形方法有类似之处。与前面介绍的单纯形法的区别在于：在单纯形法的迭代过程中，始终保持右端列(目标函数值除外)非负，即保持原问题的可行性；而在对偶单纯形法中，要保持所有的判别数(对于极小化问题)，即保持对偶可行性。（当然，在每次迭代中不要求右端列各分量均非负，正因为如此，也就不需要引入人工变量。）0jjwpc