最优化理论与方法对偶原理ppt课件.pptx

第4章 对偶原理,4.1线性规划中的对偶理论4.2对偶单纯形法,原问题与对偶问题,线性规划中普遍存在着配对的现象，即对每一个线性规划问题，都存在另一个与之密切联系的线性规划问题，其中之一称为原问题，而另一个成为它的对偶问题。对偶问题深刻揭示了每对问题中原问题与对偶问题的内在联系。,【例】原问题与对偶问题,某工厂拟生产甲、乙两种产品，需消耗煤、电、油三种资源。有关数据如表所示：,问题一：试拟订使总收入最大的生产方案。问题二：若厂家不再打算生产甲、乙产品，而是打算将其资源全部卖掉。厂家要求：其收入不低于生产产品时的收入；买方希望：原料价格越低越好。试拟定能够保证卖方收入且使买方支出最小的定价方案。,问题二：试拟定能够保证卖方收入且使买方支出最小的定价方案。解：设煤、电、油三种资源的定价分别为y1,y2,y3，买方总支出为w。,【例】原问题与对偶问题,问题一：试拟订使总收入最大的生产方案。解：设拟生产甲、乙产品各x1,x2 单位，总收入为z。,下面将会看到，这两个问题互为对偶问题，其中一个称为原问题，则另一问题就是它的对偶问题。,对偶问题的表述对称形式,原问题 对偶问题,其中 是 矩阵，是m 维列向量，是n 维行向量，是由原问题的变量组成的n 维列向量，是由对偶问题的变量组成的 m维行向量。,对偶问题的表述 非对称形式,对称形式原问题：对偶问题,非对称形式,对偶问题的表述（一般形式）,原问题,对偶问题,原问题与对偶问题间的相互转换关系,对偶问题的基本性质,对偶问题的对偶是原问题。,对偶定理（以对称对偶形式叙述）,【定理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)无可行解。,（4.1.1）,（4.1.2）,对偶定理（以对称对偶形式叙述）,【定理4.1.2】设原问题或对偶问题中有一个问题存在最优解，则另一个问题也存在最优解，且两个问题的目标函数值相等。【推论】若线性规划(4.1.1)存在一个对应基B的最优基本可行解，则单纯形乘子 是对偶问题(4.1.2)的一个最优解。根据这个推论，能够从原问题的最优单纯形表中直接获得对偶问题的一个最优解。,对偶问题的基本性质,互补松弛性质（见教材）对于对偶规划，当知道一个问题的最优解时，根据互补松弛定理求出另一个问题的最优解。,对偶可行的基本解,考虑线性规划问题(4.2.1)定义:设 x(0)是(4.2.1)式的一个基本解，它对应的基矩阵为B，记w=cBB-1，若 w 是(4.2.1)式的对偶问题的可行解，即对所有j，成立，则称 x(0)为原问题的对偶可行的基本解。,称为方程组的一个基本解,对偶单纯形法的基本思想,从原问题的一个对偶可行的基本解出发，求改进的对偶可行的基本解，当得到的对偶可行的基本解是原问题的可行解时，就达到最优解。这里改进的对偶可行的基本解的含义是：根据定义，对每个对偶可行的基本解 都对应一个对偶问题的可行解w=cBB-1，相应的对偶问题的目标函数值为wb=cBB-1b。所谓改进的对偶可行的基本解，是指对于原问题的这个基本解，相应的对偶问题的目标函数值wb有改进。,对偶单纯形法的基本思想,求改进的对偶可行的基本解的过程，也就是选择离基变量和进基变量，进行主元消去的过程。这与单纯形方法有类似之处。与前面介绍的单纯形法的区别在于：在单纯形法的迭代过程中，始终保持右端列(目标函数值除外)非负，即保持原问题的可行性；而在对偶单纯形法中，要保持所有的判别数(对于极小化问题)，即保持对偶可行性。（当然，在每次迭代中不要求右端列各分量均非负，正因为如此，也就不需要引入人工变量。）,