对偶与对偶算法教学课件.ppt

对偶性与对偶算法,线性规划对偶性质,求解标准线性规划问题,最终要找到一个基阵 满足,而最优目标值等于,记，原问题有最优解时，满足以下约束,可否在满足以上约束的解中找到，进而找到？,设 是原问题的任意一个可行解，即满足,对任何满足不等式约束 的，成立,下述线性规划问题的最优目标值不会小于原问题任何可行解的目标函数值,当 是原问题最优基阵时，满足,其中 是 决定的最优的基本可行解,求解上面的线性规划问题能找到原问题的最优基矩阵,定义：标准线性规划问题的对偶问题,原问题,对偶问题,矩阵形式（）,原问题和对偶问题之间的关系,强对偶性：若原问题有最优解，则对偶问题一定也 有最优解，并且最优目标值相等，即,则,弱对偶性：若 和 分别是原、对偶问题可行解，即,规范形式线性规划问题的对偶问题,原问题,标准线性规划问题,标准线性规划对偶问题,原问题对偶问题,等价问题,标准线性规划问题对偶问题的对偶问题,原问题,对偶问题,对偶问题的对偶问题是原问题,结论：任何原问题和对偶问题之间都存在下述相互关系,弱对偶性：原对偶问题任何可行解的目标值都是另一问 题最优目标值的界（推论：原对偶问题目标 值相等的一对可行解是各自的最优解）强对偶性：原对偶问题只要有一个有最优解，另一个就 有最优解，并且最优目标值相等,原,对偶,有最优解,有最优解,问题无界,问题无界,无可行解,无可行解,不会,不会,不会,不会,不会,不会出现的情况：,原问题,对偶问题,含义：如果原（对偶）问题某不等式是松的（不等于0）则其相应的对偶（原）变量必须是紧的（等于0）,互补松弛性定理,若、分别是原（对偶）问题可行解，则它们分别是各自问题最优解的充要条件是满足互补松弛性等式,等价于,证明充分性：,由以上两式可得，根据弱对偶性的推论可知两者分别是各自问题的最优解,证明必要性：当 和 是原、对偶问题的最优解时，,所以,由强对偶性可知，再利用可行性条,件 可得,例,原问题,对偶问题,已知原问题最优解，求对偶问题最优解,利用互补松弛定理,少一个方程，还有没有其它信息可以利用？,对偶问题,原问题最优解,影子价格,原问题,如果增加某些 的数值，最优目标值应该增加,能否定量地刻划增加不同 的效果？,例1,最优目标值增量,第一个约束的常数项加1:,最优目标值增量,第二个约束的常数项加1,最优目标值增量,第三个约束的常数项加1,不同约束常数项对最优目标值的影响,例1对偶问题,最优解,对偶问题最优解正好是最优目标函数的增量！,（用对偶性验证）,设对偶问题最优解为，由强对偶性知，原问题,的最优目标值为,所以，原问题最优目标关于 的偏导数分别是，说明 增加一个单位可望增加 的最优目标值，故称其为 的影子价格,原问题,对偶问题,一般情况,原问题,对偶问题,如果原问题的某个约束在最优解处不是严格等式，例如，增加 不会增加最优目标值，所以其影子价格 等于0，因此有互补松弛等式同样道理可得,设,是原问题的最优解，,是对偶问题的最优解,物理意义为生产单位 产品的利润减去按影子价格计算的资源的总成本，如果差值大于零，应继续生产，所以最优解必须满足所有检验数非正,如果原问题为标准型,是最优基矩阵，在推导强对偶性时已说明其对偶问题的最优解为，于是，非基变量 的检验数可写成,影子价格只能在局部范围内反映资源增长（即增加约束的右边常数）可以产生的目标函数的增值，一旦资源增长导致最优基矩阵改变，原来的最优对偶变量值一般情况下不等于单位资源增长带来的目标函数的增值，从而失去影子价格的意义,注意,改变，但 不变，影子价格 不变,改变导致 改变，影子价格 改变,影子价格不变，最优目标值增量等于,例如：例1中第三个约束的常数项加1,如果,最优基改变，最优目标值增量不等于,对偶单纯型法,例1,如果取，用 左乘等式约束两边，可将其变换成以下等价的标准线性规划模型,将 的表示式代入目标函数，原问题等价为,变换后的等价问题对应的单纯型表为,该单纯型表的检验数均为非正数，如果右边常数没有负数，已经得到原问题的最优解,能否在保持检验数非正的前提下消除负的右边数？,(-0.5)+,(-2)+,或,合格,不合格,选比值小的进基！,出基变量行非基变量的系数全为负数,(-2)+,合格,选比值小的变量进基时不用考虑负数！,出基变量行非基变量的系数中有正数,出基变量行的变量系数全为正数时原问题无解！,不可能同时成立,出基变量行非基变量的系数全为正数,一般情况：要处理的等式约束和目标约束可写成,用 进基替换，可验证所有检验数保持非正,若 中没负数，原问题无可行解,否则可确定,其中 是出基变量，,其中,用 进基替换 得到新的检验数的过程如下：,()+,所有检验数保持非正,进基 出基后的表,回到开始的单纯型表,常数项全部非负检验数全部非正已经得到最优解,一般情况：消除负的右边常数后可能在常数项中产生新的负常数，例如，在原表中将第三行除以 得,变换后的前两个常数值取决于 所在列的前两个数据，完全可能出现负数,继续迭代能否保证收敛？,由于每次迭代是从一个不可行的基矩阵转到另一个不可行的基矩阵（一旦遇到可行的基矩阵就得到了最优解），而基矩阵的总数是有限的，如果不出现循环，算法一定在有限步内停止于最优解,所以，关键问题是，迭代过程是否不会出现循环？,为回答收敛问题，先确定一步迭代后下式中的,由于上式来自()+，其中,可得,如果,（相当于非退化条件），因为,所以,由于 和 都是由对应的基矩阵决定的，说明在 以后产生的基矩阵不可能等于 对应的基矩阵，因此，在非退化条件下可以保证算法收敛于最优解，在退化情况下，只要采取辅助措施避免在具有相同 值的几个基矩阵中循环就可以保证收敛,为什么叫对偶单纯型法？,原问题,对偶问题,和一次迭代后的 都是对偶问题的可行解，目标值满足，该算法的本质是 在对偶问题的可行顶点集中沿着目标函数下降路径找到最优顶点，所以叫对偶单纯型法,可行集,例 1 的可行集和目标函数等值线如下图所示，其中黄点是基本可行解，黑点是不可行基矩阵确定的点,对偶单纯型法的几何意义,对偶单纯型法是从不可行区域逐渐减少目标函数值逼近最优解，如右图从 到最优解,什么时候用对偶单纯型法？,例、,等价问题,上述问题没有明显的初始可行基，需引入人工变量，但有明显的对偶可行基，用对偶单纯型法不需要人工变量,原问题,结论：对偶单纯型法适用于 的下述线性规划问题,灵敏度分析,假定已求得最优可行基，并获得 等有关数据,对于标准线性规划问题,若某些参数发生变化，如,如何利用已知数据确定新的最优解？,例1,最终单纯型表,如果目标函数改变：,最终单纯型表,继续迭代,如果常数向量改变：,最终单纯型表,其中新的常数向量为，如果，已经得到最优解，否则可用对偶单纯型法继续迭代,能否从最终单纯型表中找出？,初始单纯型表,最终单纯型表,一般情况：若在标准型初始矩阵 中存在单位阵，比如,由于单纯型表的各列向量等于,所以,只要将最初的单位向量所在列的最终数据按单位向量在单位矩阵中的位置排好就可以得到,注意：中各 所在列数取决于基变量所在行数！,