chap2_线性规划的对偶理论.ppt

影子价格的性质 影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0 影子价格反映了资源在系统内部的紧缺程度： 对偶问题与原问题解的关系 例： maxZ=9x1+5x2 +8x3 3x1+x2+ x3 ? 5 x1+x2+8x3 ? 1 x1 , x2 , x3 ? 0 LP： min w = 5y1+y2 3y1+ y2 ? 9 y1+ y2 ? 5 y1+8y2 ? 8 y1 , y2 ? 0 DP： 对偶问题与原问题解的关系 标准化： maxZ=9x1+5x2 +8x3 3x1+x2+ x3 + x4 =5 x1+x2+8x3 + x5 =1 x1 , x2 , x3 ? 0 LP： min w = 5y1+y2 3y1+ y2 – y3 = 9 y1+ y2 – y4 = 5 y1+8y2 – y5 = 8 y1 , y2 , y3 ,y4 ,y5 ? 0 DP： 原问题单纯形表 9 5 8 0 0 CB 基 b x1 x2 x3 x4 x５ 0 x４ 5 3 1 1 1 0 0 x５ 1 1 1 8 0 1 ?j 9 5 8 0 0 1 x1 9 2 0 -2 -23 -3 0 -4 -64 -9 原问题的最优解：X*=[1, 0, 0, ２, 0]T， z*=9 对偶问题与原问题解的关系 对偶问题的最优解：Y*=[0, *,０, *, *]T 根据松弛互补性： y1 (0) y2 (*) y3 (0) y4 (*) y5 (*) x1(1) x2 (0) x3 (0) x4 (2) x5 (0) 原问题的最优解：X*=[1, 0, 0, ２, 0]T 对偶问题与原问题解的关系 y2 ＝ 9 y2 － y４ ＝ 5 8y2 － y５ ＝8 yi ? 0 将Y*=[0, *,０, *, *]T代入对偶问题得 min w = 5y1+y2 3y1+ y2 – y3 = 9 y1+ y2 – y4 = 5 y1+8y2 – y5 = 8 y1 , y2 , y3 , y4 , y5 ? 0 对偶问题最优解：Y*=[0, 9, 0, 4, 64]T ， w*=9 原问题单纯形表 9 5 8 0 0 CB 基 b x1 x2 x3 x4 x５ 0 x４ 5 3 1 1 1 0 0 x５ 1 1 1 8 0 1 ?j 9 5 8 0 0 1 x1 9 2 0 -2 -23 -3 0 -4 -64 -9 原问题最优解：X*=[1, 0, 0, ２, 0]T， z*=9 对偶问题最优解：Y*=[0, 9, 0, 4, 64]T ， w*=9 是巧合？或是必然？ 对偶问题与原问题解的性质 性质：原问题的检验数对应于对偶问题的一个基解 证明：当 Y= (CBB-1)T， Ys = -(C - CBB-1A)T 时 ATY-Ys = CT 即对偶问题的约束条件成立。 由于检验数至少有m个变量为0，故为对偶问题基解。 原问题基变量的检验数为0 原问题的检验数?对偶问题的基解 原变量 X Xs 检验数 C - CBB-1A -CBB-1 对偶变量 -Ys -Y 原问题 约束(松弛变量) 变量 基解 检验数 对偶问题 变量 约束(松弛变量) 检验数 基解 对应关系 对偶问题与原问题最优解的性质 当XB= B-1b为原问题最优解时，检验数： (C- CBB-1A) ?0 故Y为对偶问题的最优解。 故 [Y，Ys] ? 0，为对偶基可行解。 - CBB-1 ?0 z*=CB XB= CB B-1b w=bTY= CB B-1b=z* 原变量 X Xs 检验数 C - CBB-1A -CBB-1 对偶变量 -Ys -Y 单纯形法思路 单纯形法思路： 单纯形法：找基B，满足B-1b?0，若 C - CBB-1 A不全? 0，（即检验数）。 迭代 保持B-1b?0，使C - CBB-1 A ? 0 保持X为可行解，使Y演变为对偶可行解 对偶单纯形法的思路 对偶单纯形法：寻找初始基B，满足 C - CBB-1 A? 0，但B-1b不全?0 迭代 保持C -CBB-1 A? 0，使B-1b?0 保持Y为可行解，使X演变为可行解 初始单纯形法表 c1 … cm … cj … cn cB 基 b x1 … xm … xj … xn c1 x1 b1 1 … 0 … a1j … a1n c2 x2 b2 0 … 0 … a2j … a2n ?: : : : : : : cm xm bm 0 … 1 … am