最优化方法之 对偶理论讲解ppt课件

1、优化方法Optimization第七届，第四章对偶理论，窗口包括西岭千秋雪、门泊东吴万里船。 (唐)杜甫，对偶是普遍的现象，主要内容是，设对偶问题的形式是L P对偶形式和定理对偶问题经济解释对偶单纯形法原对偶算法、对偶和鞍点问题、Lagrange对偶问题，(1)，定义(1)普遍存在的集合制约D=x|x0，则该线性修正画问题的Lagrange函数线性校正像素的对偶问题是LP对偶问题的表示，所述LP对偶问题是求下一个非线性校正像素问题的对偶问题：对偶问题3360、对偶定理、定理1 (弱对偶定理)、推论13360，(1)对称LP问题定义，(2)对称LP问题的对偶问题，(p )、(d )，例如写以下的

2、LP问题的对偶问题，双例如，写对偶问题(d )、(DD )、min是max价值系数和右端向量兼容系数矩阵转置变原问题中的限制条件的个数=对偶问题中的变量的个数=对偶问题中的限制条件的个数，对称形式的对偶校正像的点、非对称形式的对偶、对称形式、对偶、(p ) 书写的示例min5x 14 x23 x3s.t.x1x2x3=43 x 12 x2=5x 10、x 2、x3 0对偶问题是max4w1w2s.t.w1w25w2w2w1w23，通常是LP问题的对偶，、练习题、LP对偶问题的基本性质、原问题定理1 (弱对偶定理)，例如，1 2 )对偶问题(D1 )一个可行解w=(1 1 1 1 )目标价值=1

3、0 10是(P1 )最佳目标价值的下边界。与推论1、推论2、极大化问题的任何一个可行解对应的目标函数值是该对偶问题的目标函数值的下边界。 与极小化问题中任一个可行解对应的目标函数值是该对偶问题的目标函数值的上限。 如果在推论3、问题(p )或(d )中存在无界解，则该对偶问题(d )或(p )存在如下倾向，即，如果没有可行解，在问题(p )或(d )中没有可行解，则没有该对偶问题(d )或(p )或可行解，或者目标函数值变为无限。 定理2 (最佳基准)、例、定理3 (强对偶定理)、(p )、(d )都有可行解，则(p )、(d )都有最佳解，从而证明(p )、(d )都有最佳解求解的最佳单纯形

4、表中缓和变量的检验常数的倒数(单纯形乘法运算符w=()这是目标函数中的价格系数，因此，如果判别数为(B-1)TcB(-ej)-0=-wj，则将与缓和变量对应的判别数乘以(-1 )，得到单纯形乘法运算符w=(w1，wm )的x *=(总结原问题(min )对应关系对偶问题(max )、有最佳解、有最佳解、无界解、不可能、不可能、无界解的例子考虑3360次问题、解3360、1、定义、对偶问题的经济学解释：影价(自学)、2、含义， 在最优解中考虑右端项bi的微小变动对目标函数值的影响右边的项目值表示各资源的可使用量。对偶解的经济意义：资源的单位变化量引起目标函数值的增加量。对偶解称为影子价格。影子价

5、格的大小客观地反映了资源在系统内的稀少度。资源的显示资源在系统内稀少，木门木窗木工4小时3小时120小时/日漆工2小时1小时50小时/日收入56 30解：设置该工厂每天x1 x2 x3 x4生产木门x1风扇安排木窗x2x 3410120 maxz=56 x 130 x 20150 s.t.4 x 13 x 20 2250-20281400 x21-220 X10-1/2-1/202241440，对偶问题的解是：w*=(2、24 )、 (3)为全新产品定价提供依据的对偶单纯形法，定义： x(0)为(p )的基本解(不一定是可行解)，对应的矩阵为b、w=cBB-1，告诉管理员增加哪些资源对企业更有利因此，x(0)是可对偶的基解。 基本思想：从原问题的可对偶基解出发求出改进的可对偶基解：各可对偶基解x=(xBT，0)T对应于对偶问题的可行解w=cBB-1，对应的对偶问题的目标函数值是wb=cBB-1b，改进的对偶可基解是指原问题的这个与原单纯形法的不同：原单纯形法维持原问题的可行性，对偶单纯形法维持所有检验数wPj-cj 0，即维持对偶问题的可