4 对偶理论_58606137.ppt

第四章　对偶原理 窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象 写出对称形式的对偶规划的要点： (1) min变成max (2) 价值系数与右端向量互换 (3) 系数矩阵转置 (4) ≥ 变 ≤ 原问题中约束条件的个数=对偶问题中变量的个数 原问题中变量的个数=对偶问题中约束条件的个数 例 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 一般情形LP问题的对偶问题 min cx s.t. A1x ≥b1 A1 为m1×n , b1为m1×1 A2x =b2 A2 为m2×n , b2为m2×1 A3x ≤ b3 A3 为m3×n , b3为m3×1 x ≥0 引入松弛变量 min cx s.t. A1x –xs =b1 xs为m1×1 A2x =b2 A3x +xt = b3 xt为m3×1 x, xs , xt ≥0 min max 变 ≥0 ≤ 约 量 ≤0 ≥ 束 无限制 = 方 程 约 ≥ ≥0 束 ≤ ≤0 变 方 = 无限制 量 程 第二节 对偶问题的基本性质 原问题(L) 对偶问题(D) min cx max wb s.t. Ax ≥ b s.t. wA ≤ c x ≥ 0 w ≥ 0 方法 由于(L) 化成标准形式时,松弛变量xn+j对应的列为-ej，它在目标函数中的价格系数＝０，所以， 判别数＝cBB-1(-ej)-0=-wj 则松弛变量对应的判别数均乘以(-1)，得到单纯形乘子w=(w1,…,wm). 当原问题达最优时,单纯形乘子即为对偶问题的最优解. 若把原问题的约束条件看成是广义的资源约束,则右端项的值表示每种资源的可用量. 对偶解的经济含义:资源的单位改变量引起目标函数值的增加量. 通常称对偶解为影子价格. 影子价格的大小客观地反映了资源在系统内的稀缺程度.资源的影子价格越高,说明资源在系统内越稀缺,而增加该资源的供应量对系统目标函数值贡献越大. 对偶单纯形法 定义：设x(0)是(L)的一个基本解（不一定是可行解），它对应的矩阵为B，记w=cBB-1，若w是(L)的对偶问题的可行解，即对任意的j, wPj-cj ≤0，则称x(0)为原问题的对偶可行的基本解。 结论：当对偶可行的基本解是原问题的可行解时，由于判别数≤0，因此，它就是原问题的最优解。 基本思想： 从原问题的一个对偶可行的基本解出发； 求改进的对偶可行的基本解：每个对偶可行的基本解x=(xBT,0)T对应一个对偶问题的可行解w=cBB-1，相应的对偶问题的目标函数值为wb=cBB-1b，所谓改进的对偶可行的基本解，是指对于原问题的这个基本解，相应的对偶问题的目标函数值wb有改进（选择离基变量和进基变量，进行主元消去）； 当得到的对偶可行的基本解是原问题的可行