运筹学对偶问题学习版.ppt

定理1（对称性定理） 对偶问题（B）的对偶规划为线性规划（A） 对称性定理是很重要的。它表明原规划问题（A）和对偶规划问题（B）是互为对偶的。也就是说，如果（B）是（A）的对偶，那么（A）也是（B）的对偶。这就为以后的讨论带来方便。不难理解，如果当A具有某种性质时可以推出B的某些性质，于是可以无需另加证明地得到：当B具有某种性质时，问题A也具有那些性质。 必威体育精装版文档 * 定理2（弱对偶定理） 当原问题A是求最大值max，而对偶问题是求最小值时，如果X0是原问题的任意可行解，Y0是对偶问题的任意可行解，则有以下关系式成立： 必威体育精装版文档 * 定理3（最优性定理） 设 和 分别是问题A和B的可行解，若相应于 和 ，A和B的目标函数值相等，即 ，则 和 分别是A和B的最优解。 必威体育精装版文档 * 定理4（无界性定理） 如果原问题A的目标函数值无界，则对偶问题B无可行解；如果对偶问题B的目标函数值无界，则原问题A无可行解。 必威体育精装版文档 * 以上三个定理可以这样记忆 原问题A和对偶问题B如果有可行解，则它们的可行解区域只可能相接，不可能相交。两个区域的交界线即是它们的最优解，如果原问题A的目标函数无界，意味着可行解区域无界，向外扩张，挤占了对偶问题B的可行解区域，则对偶问题无可行解，反之同理可说明。 对偶问题(B) minW 原问题(A) maxZ y0b cx0 必威体育精装版文档 * 定理5（强对偶定理） 若线性规划A存在最优解，则对偶规划B也存在最优解，并且它们的最优值相等；相反地，若规划B存在最优解，则规划A也存在最优解，并且它们的最优值相等。 必威体育精装版文档 * 定理6（存在性定理） 若线性规划A和B都存在可行解，则A和B都存在最优解。 必威体育精装版文档 * 第三节 对偶单纯形法 条件： ①b列中至少有一个bi0； ②原问题A的检验数满足符号条件。 必威体育精装版文档 * 例 必威体育精装版文档 * 解： min max 解：引入松弛变量，化为标准形式： 必威体育精装版文档 * 观察A矩阵 必威体育精装版文档 * 解 以上标准形式中没有完全单位向量组，我们将约束条件进行变换，两边同乘（-1）。 A矩阵中存在完全单位向量组，但bi0，考虑求解。 用单纯形法求解。 必威体育精装版文档 * 第四章 对偶问题 对偶问题的一般形式 对偶问题的经济意义 对偶性质 对偶单纯形法 对偶单纯形法的解题原理 必威体育精装版文档 * 一、对偶问题的一般形式 若设一线性规划问题如下 ： （A） 必威体育精装版文档 * 则以下线性规划问题： （B） 称为原问题（A）的对偶线性规划问题， 或称A、B互为对偶问题。 必威体育精装版文档 * 如果采用向量、矩阵来表示 （A） （B） 其中： 必威体育精装版文档 * 可以将以上关系列成以下对偶表： max min x1 x2 … xn b y1 a11 a12 … a1n ≤ b1 y2 a21 a22 … ≤ b2 … … … … … … … ym am1 am2 … amn ≤ bm ≥ ≥ … ≥ c c1 c2 … cn 必威体育精装版文档 * 例 写出下列线性规划问题的对偶问题 必威体育精装版文档 * 解： 可以将原问题的有关参数列成下表 max min x1 x2 x3 b y1 1 4 2 ≤ 48 y2 1 2 4 ≤ 60 ≥ ≥ ≥ c 6 14 13 必威体育精装版文档 * ∴ 对偶规划问题为 必威体育精装版文档 * 比较 以上我们介绍的对偶问题是严格定义的对偶问题，也成为对称对偶问题 。 它满足两个条件： 必威体育精装版文档 * 两个条件： 1、所有变量非负：即X0，Y0 2、约束条件均为同向不等式。若原问题约束条件均为“≤”，则它的对偶问题的约束条件都是“≥”。 当原问题的约束条件的符号不完全相同时，也存在对偶问题，这种对偶问题称为非对称对偶问题。 必威体育精装版文档 * 例 分析： 为求对偶问题，可先做过渡，将问题对称化： 必威体育精装版文档 * 对称化 必威体育精装版文档 * 则，原问题变为 （A） （A‘） 必威体育精装版文档 * 则（A’）的对偶问题如下： （B‘） （A‘） 必威体育精装版文档 * 对比结果 以上对偶问题（B‘）并非原问题（A）的对偶问题，它是线性规划问题（A’）的对偶问题。 （A） （B‘） 必威体育精装版文档 * 调整 对照问题B‘目标函数系数的符号与原问题A中约束条件右端常数项的符号，可做以下调整： 令y1=y1’，y2=-y2’，y3=y4’-y3’ 必威体育精装版文档 * 令y1=y1’，y2=-y2’，y3=y4’-y3’则得到以下对偶问题 （B‘） （B） 必威体育精装版文档 * 合并 （B） 必威体育精装版文档 * 比