1、第四章 对偶规划、灵敏度分析与应用Dual Problem and Sensitivity analysisn 1 单纯型法的矩阵表示 n 2 线性规划的对偶问题n 3 对偶规划的基本性质n 4 影子价格（对偶价格）n 5 对偶单纯形法n 6 单纯形表的灵敏度分析11 单纯型法的矩阵表示Max z= CX Max z = CX+0Xss.t. AXb s.t. AX+IXs =b X0 X0C=(c1, c2, cn ) A= ( p1, p2 , pn )2若取基为 则Max z =CBXB CN XN s.t. BXB NXN= b3Max z=CBXB CN XN B =(p1 ,p2,
2、 pm)s.t. BXB NXN=b 为一个基为一个基XB ,XN0 （ A， I） =（ B， N）XB= B-1b B-1NXN N=(pm+1 , pn)z=CBXB CN XN = CBB-1b +( CN CBB-1N ) XN z+ 0XB+(CBB-1N CN) XN = CBB-1b0 z + XB+ B-1NXN = B-1b-z+ 0XB+(CN CBB-1N) XN = CBB-1b0 z + XB+ B-1NXN = B-1b国内书籍国外书籍P384非基 变 量 基 变 量 右端 项系数 基 变 量 XB XN XsCs=0 Xs B N I bCB CN 0 0基 变
3、 量 非基 变 量 右端 项系数 基 变 量 XB XN XsCB XB I B-1N B-1 B-1b0 CN CBB-1N Cs CBB-1 -CBB-1b迭 代j =1,n85Basic variable 系数 右端 项 Z 原来 变 量 X 松弛 变 量 XSZ 1 -C 0 0CB XB 0 A I bany Z 1 C CBB-1A CBB-1 ( ) CBB-1bXB 0 B-1A B-1( S*) B-1bXB= B-1b Z= CBB-1b216cj 31 22 0 0 0 b iCB XB x1 x2 x3 x4 x50 x3 6 2 1 0 0 1800 x4 4 10
4、0 1 0 4000 x5 3 5 0 0 1 210-Z 31 22 0 0 0 0最 终单纯 型表31 x1 1 0 5/24 0 1/12 200 x4 0 0 5/12 1 13/6 2022 x2 0 1 1/8 0 1/4 3031 x1 0 0 89/24 0 35/12 1280207最终表的矩阵计算（矩阵表示） P26表 1-658以第二章例一为例Max z = 50 x1 + 100 x2 Max z = 50 x1 + 100 x2 s.t. x1 + x2 300 s.t. x1 + x2 + s1 300 2 x1 + x2 400 2 x1 + x2 + s2 40
5、0x2 250 x2 + s3 250x1 , x2 0 x1 , x2 ， s1 ， s2 ， s3 0如果9单纯型法迭代过程表迭代次数基 变量 CBx1 x2 s3 s4 s5 b 比 值 ibi/ai2 50 100 0 0 00s1s2s30001 1 1 0 02 1 0 1 00 1 0 0 1300400250300/1400/1250/1zj 0 0 0 0 050 100 0 0 0z=0迭代次数基 变量 cBx1 x2 s3 s4 s5 b 比 值bi/aij 50 100 0 0 02x1s2x25001001 0 1 0 -10 0 -2 1 10 1 0 0 15050250zj 50 100 50 0 500 0 -50 0 -502750055最终单纯形表初始单纯形表10
