最优化方与法之 对偶理论讲解 .ppt

最优化方法 Optimization第七讲 窗含西岭千秋雪， 门泊东吴万里船。 -----(唐)杜甫 min变成max 价值系数与右端向量互换 系数矩阵转置 ≥ 变 ≤ 原问题中约束条件的个数=对偶问题中变量的个数 原问题中变量的个数=对偶问题中约束条件的个数 例 min 5x1+4x2+3x3 s.t. x1+x2+x3=4 3x1+2x2+x3 =5 x1 ≥ 0, x2 ≥0, x3 ≥0 对偶问题为 max 4w1+5w2 s.t. w1+3w2≤5 w1+2w2 ≤ 4 w1+w2 ≤ 3 若把原问题的约束条件看成是广义的资源约束,则右端项的值表示每种资源的可用量. 对偶解的经济含义:资源的单位改变量引起目标函数值的增加量. 通常称对偶解为影子价格. 影子价格的大小客观地反映了资源在系统内的稀缺程度.资源的影子价格越高,说明资源在系统内越稀缺,而增加该资源的供应量对系统目标函数值贡献越大. 对偶单纯形法 定义：设x(0)是(P)的一个基本解（不一定是可行解），它对应的矩阵为B，记w=cBB-1，若w是(P)的对偶问题的可行解，即对任意的j, wPj-cj ≤0，则称x(0)为原问题的对偶可行的基解。 结论：当对偶可行的基解是原问题的可行解时，由于判别数≤0，因此，它就是原问题的最优解。 基本思想： 从原问题的一个对偶可行的基解出发； 求改进的对偶可行的基解：每个对偶可行的基解x=(xBT,0)T对应一个对偶问题的可行解w=cBB-1，相应的对偶问题的目标函数值为wb=cBB-1b，所谓改进的对偶可行的基解，是指对于原问题的这个基解，相应的对偶问题的目标函数值wb有改进（选择离基变量和进基变量，进行主元消去）； 当得到的对偶可行的基解是原问题的可行解时，就达到最优解。 与原单纯形法的区别： 原单纯形法保持原问题的可行性，对偶单纯形法保持所有检验数wPj-cj ≤0，即保持对偶问题的可行性。 特点：先选择出基变量，再选择进基变 量。 推论 在用单纯形法求解LP问题（P）的最优单纯 形表中松弛变量的检验数的相反数(单纯形 乘子w=(B-1)TcB)就是其对偶问题（D）的最优解. 由于(P)化成标准形式时,松弛变量xn+j 对应的列为-ej，它在目标函数中的价格系数＝０，所以，判别数为 (B-1)TcB(-ej)-0=-wj 则松弛变量对应的判别数均乘以(-1)，便得到单纯形乘子w=(w1,…,wm). 当原问题达最优时,单纯形乘子即为对偶问题的最优解. 解：化为标准形 例: 求下列问题之对偶问题的最优解 x1 x2 x3 x4 x5 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 -2 -3 0 0 0 x3 x4 x5 8 16 12 0 1 0 1 0 -1/2 4 0 0 1 0 0 1 0 0 1/4 -2 0 0 0 3/4 x3 x4 x2 2 16 3 9 4 1 x1 x2 x3 x4 x5 1 0 1 0 -1/2 0 0 -4 1 2 0 1 0 0 1/4 0 0 2 0 -1/4 x1 x4 x2 2 8 3 13 2 1 0 0 1/4 0 0 0