对偶与对偶算法教学课件

对偶与对偶算法教学课件1、不要轻言放弃，否则对不起自己。2、要冒一次险!整个生命就是一场冒险。走得最远的人，常是愿意去做，并愿意去冒险的人。“稳妥”之船，从未能从岸边走远。--戴尔．卡耐基。3、人生就像一杯没有加糖的咖啡，喝起来是苦涩的，回味起来却有久久不会退去的余香。4、守业的最好办法就是不断的发展。5、当爱不能完美，我宁愿选择无悔，不管来生多么美丽，我不愿失去今生对你的记忆，我不求天长地久的美景，我只要生生世世的轮回里有你。对偶与对偶算法教学课件对偶与对偶算法教学课件1、不要轻言放弃，否则对不起自己。2、要冒一次险!整个生命就是一场冒险。走得最远的人，常是愿意去做，并愿意去冒险的人。“稳妥”之船，从未能从岸边走远。--戴尔．卡耐基。3、人生就像一杯没有加糖的咖啡，喝起来是苦涩的，回味起来却有久久不会退去的余香。4、守业的最好办法就是不断的发展。5、当爱不能完美，我宁愿选择无悔，不管来生多么美丽，我不愿失去今生对你的记忆，我不求天长地久的美景，我只要生生世世的轮回里有你。对偶性与对偶算法线性规划对偶性质当是原问题最优基阵时，满足其中是决定的最优的基本可行解求解上面的线性规划问题能找到原问题的最优基矩阵定义：标准线性规划问题的对偶问题原问题对偶问题矩阵形式（）原问题和对偶问题之间的关系强对偶性：若原问题有最优解，则对偶问题一定也

有最优解，并且最优目标值相等，即则弱对偶性：若和分别是原、对偶问题可行解，即规范形式线性规划问题的对偶问题原问题标准线性规划问题标准线性规划对偶问题原问题对偶问题等价问题标准线性规划问题对偶问题的对偶问题原问题对偶问题对偶问题的对偶问题是原问题结论：任何原问题和对偶问题之间都存在下述相互关系弱对偶性：原对偶问题任何可行解的目标值都是另一问

题最优目标值的界（推论：原对偶问题目标值相等的一对可行解是各自的最优解）强对偶性：原对偶问题只要有一个有最优解，另一个就

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