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