对偶线性规化问题.pptVIP

第二章 对偶线性规划 对偶的定义 对偶问题的性质 原始对偶关系 目标函数值之间的关系 最优解之间的互补松弛关系 最优解的Kuhn-Tucker条件 对偶可行基对偶单纯形法 对偶的经济解释 对偶的定义 原始问题 min z=CTX s.t. AX≥b X ≥0 min z=CTX s.t. AX+XS=b X, XS≥0 max y=bTW s.t. ATW+WS=C W ≤0, WS≥0 单纯形表和对偶(2) max y=bTW s.t. ATW≤C W ≤ 0 对偶问题 min z=CTX s.t. AX ≤ b X ≥0 原始问题 引进松弛变量 引进松弛变量 min z=CTX s.t. AX+XS=b X, XS≥0 max y=bTW s.t. ATW+WS=C W ≤0, WS≥0 WT=CBTB-1 WST=CT-WTA max z=CTX s.t. AX-XS=b X, XS≥0 max y=bTW s.t. ATW-WS=C W ≤0, WS≥0 单纯形表和对偶(3) min y=bTW s.t. ATW ≥ C W ≤ 0 对偶问题 max z=CTX s.t. AX ≥ b X ≥0 原始问题 引进松弛变量 引进松弛变量 max z=CTX s.t. AX-XS=b X, XS≥0 min y=bTW s.t. ATW-WS=C W ≤0, WS≥0 WT=CBTB-1 WST=WTA- CT max z=CTX s.t. AX+XS=b X, XS≥0 max y=bTW s.t. ATW-WS=C W, WS≥0 单纯形表和对偶(4) min y=bTW s.t. ATW ≥ C W ≥ 0 对偶问题 max z=CTX s.t. AX ≤ b X ≥0 原始问题 引进松弛变量 引进松弛变量 max z=CTX s.t. AX+XS=b X, XS≥0 min y=bTW s.t. ATW-WS=C W, WS≥0 WT=CBTB-1 WST=WTA- CT min z=6x1+8x2+3x3 s.t. x1+ x2 -x4 =1 x1+2x2+x3 -x5 =-1 x1, x2, x3 ,x4, x5≥0 max y=w1-w2 s.t. w1+w2+w3 =6 w1+2w2 +w4 =8 w2 +w5=3 w1, w2, w3, w4, w5≥0 (w1, w2, w3, w4, w5)=(6, 0, 0, 2, 3) (x1, x2, x3, x4, x5)=(1, 0, 0, 0, 2) -1 -1 0 1 2 1 0 x5 1 0 -1 0 1 1 0 x1 0 0 0 -3 -8 -6 1 z RHS x5 x4 x3 x2 x1 z 1 1 0 -1 -2 -1 0 x5 1 0 -1 0 1 1 0 x1 6 0 -6 -3 -2 0 1 z RHS x5 x4 x3 x2 x1 z 1 1 0 -1 -2 -1 0 x5 1 0 -1 0 1 1 0 x1 0 0 0 -3 -8 -6 1 z RHS x5 x4 x3 x2 x1 z 2 1 -1 -1 -1 0 0 x5 1 0 -1 0 1 1 0 x1 6 0 -6 -3 -2 0 1 z RHS x5 x4 x3 x2 x1 z -w3 –w4 –w5 –w1 –w2 如何从最优单纯形表中读出对偶问题的解（1） * -1 0 0 * * * * 0 x7 * * 0 RHS 0 0 0 x7 -1 0 * * * * 0 x6 0 -1 * * * * 0 x5 0 0 * * * * 1 z x6 x5 x4 x3 x2 x1 z 0 RHS -w3 x7 -w2 -w1 -w7 -w6 -w5 -w4 1 z x6 x5 x4 x3 x2 x1 z 初始 单纯形表 最优 单纯形表 如何从最优单纯形表中读出对偶问题的解（2） * 1 0 0 * * * * 0 x7 * * 0 RHS 0 0 0 x7 1 0 * * * * 0 x6 0 1 *