对偶与对偶算法教学课件

《对偶与对偶算法教学课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对偶性与对偶算法线性规划对偶性质求解标准线性规划问题最终要找到一个基阵满足而最优目标值等于记，原问题有最优解时，满足以下约束可否在满足以上约束的解中找到，进而找到？设是原问题的任意一个可行解，即满足对任何满足不等式约束的，成立下述线性规划问题的最优目标值不会小于原问题任何可行解的目标函数值当是原问题最优基阵时，满足其中是决定的最优的基本可行解求解上面的线性规划问题能找到原问题的最优基矩阵定义：标准线性规划问题的对偶问题原问题对偶问题矩阵形式（）原问题和对偶问题之间的关系强对偶性：若原问题有最优解，则对偶问题一定也有最优解，并且最优目标值相等，即则

2、弱对偶性：若和分别是原、对偶问题可行解，即规范形式线性规划问题的对偶问题原问题标准线性规划问题标准线性规划对偶问题原问题对偶问题等价问题标准线性规划问题对偶问题的对偶问题原问题对偶问题对偶问题的对偶问题是原问题结论：任何原问题和对偶问题之间都存在下述相互关系弱对偶性：原对偶问题任何可行解的目标值都是另一问题最优目标值的界（推论：原对偶问题目标值相等的一对可行解是各自的最优解）强对偶性：原对偶问题只要有一个有最优解，另一个就有最优解，并且最优目标值相等原对偶有最优解有最优解问题无界问题无界无可行解无可行解不会不会不会不会不会不会出现的情况：原问题对

3、偶问题含义：如果原（对偶）问题某不等式是松的（不等于0）则其相应的对偶（原）变量必须是紧的（等于0）互补松弛性定理若、分别是原（对偶）问题可行解，则它们分别是各自问题最优解的充要条件是满足互补松弛性等式等价于证明充分性：由以上两式可得，根据弱对偶性的推论可知两者分别是各自问题的最优解证明必要性：当和是原、对偶问题的最优解时，所以由强对偶性可知，再利用可行性条件可得例原问题对偶问题已知原问题最优解，求对偶问题最优解利用互补松弛定理少一个方程，还有没有其它信息可以利用？对偶问题原问题最优解影子价格原问题如果增加某些的数值，最优目标值应该增加能否定量地

4、刻划增加不同的效果？例1最优目标值增量第一个约束的常数项加1:最优目标值增量第二个约束的常数项加1最优目标值增量第三个约束的常数项加1不同约束常数项对最优目标值的影响例1对偶问题最优解对偶问题最优解正好是最优目标函数的增量！（用对偶性验证）设对偶问题最优解为，由强对偶性知，原问题的最优目标值为所以，原问题最优目标关于的偏导数分别是，说明增加一个单位可望增加的最优目标值，故称其为的影子价格原问题对偶问题一般情况原问题对偶问题如果原问题的某个约束在最优解处不是严格等式，例如，增加不会增加最优目标值，所以其影子价格等于0，因此有互补松弛等式同样道理可得

5、设是原问题的最优解，是对偶问题的最优解物理意义为生产单位产品的利润减去按影子价格计算的资源的总成本，如果差值大于零，应继续生产，所以最优解必须满足所有检验数非正如果原问题为标准型是最优基矩阵，在推导强对偶性时已说明其对偶问题的最优解为，于是，非基变量的检验数可写成影子价格只能在局部范围内反映资源增长（即增加约束的右边常数）可以产生的目标函数的增值，一旦资源增长导致最优基矩阵改变，原来的最优对偶变量值一般情况下不等于单位资源增长带来的目标函数的增值，从而失去影子价格的意义注意改变，但不变，影子价格不变改变导致改变，影子价格改变影子价格不变，最优目标

6、值增量等于例如：例1中第三个约束的常数项加1如果最优基改变，最优目标值增量不等于对偶单纯型法例1如果取，用左乘等式约束两边，可将其变换成以下等价的标准线性规划模型将的表示式代入目标函数，原问题等价为变换后的等价问题对应的单纯型表为该单纯型表的检验数均为非正数，如果右边常数没有负数，已经得到原问题的最优解能否在保持检验数非正的前提下消除负的右边数？②①①×(-0.5)+②①×(-2)+②或合格不合格选比值小的进基！出基变量行非基变量的系数全为负数②①①×(-2)+②合格选比值小的变量进基时不用考虑负数！出基变量行非基变量的系数中有正数出基变量行的变

7、量系数全为正数时原问题无解！不可能同时成立出基变量行非基变量的系数全为正数一般情况：要处理的等式约束和目标约束可写成用进基替换，可验证所有检验数保持非正若中没负数，原问题无可行解否则可确定其中是出基变量，，其中用进基替换得到新的检验数的过程如下：①①×()+②②所有检验数保持非正进基出基后的表回到开始的单纯型表常数项全部非负检验数全部非正已经得到最优解一般情况：消除负的右边常数后可能在常数项中产生新的负常数，例如，在原表中将第三行除以得变换后的前两个常数值取决于所在列的前两个数据，完全可能出现负数继续迭代能否保证收敛？由于每次迭代是从一个不可行的

8、基矩阵转到另一个不可行的基矩阵（一旦遇到可行的基矩阵就得到了最优解），而基矩阵的总数是有限的，如果不出现循环，算法一定在有限步内停止于最