单纯形法的矩阵计算PPT学习教案

1、会计学1单纯形法的矩阵计算单纯形法的矩阵计算3.1 单纯形法的矩阵描述单纯形法的矩阵描述3.2 单纯形法的矩阵计算单纯形法的矩阵计算3.3 对偶问题的提出对偶问题的提出3.4 线性规划的对偶理论线性规划的对偶理论3.5 影子价格影子价格3.6 对偶单纯形法对偶单纯形法3.7 灵敏度分析灵敏度分析第1页/共27页第2页/共27页第3页/共27页()()ljljlkljijijiklkaailaaaaaila ,2ijljijljlkaaaaa 设设是是本本次次表表中中的的数数字字，是是迭迭代代后后表表中中数数字字，是是主主元元素素，由由第第 章章知知111211212mlllmmmmmaaaaa

2、aaaa1111211212/0101/00/1klkmlllmlkmklkmmmmaaaaaaaaaaaaaa 第4页/共27页11111(, ,)newllmBEBEeeee , , 其其中中111/1/kklklklkmklkmkaaaPaaaaa 主主元元素素这样就求得新基的逆矩阵。这样就求得新基的逆矩阵。 第5页/共27页.42 .,. 4. ,)()(0)()()(min ,)(0)(max . 3., 0. 2,. 111111111步直到求出结果重复的求出此得到新的出基行对应的则若入基则若基变换否则转下一步则得最优解若求取可行基BBBxlPBbBPBPBbBxNBCCBBllk

3、likikiikkNjNjBNN第6页/共27页n 改进单纯形法的步骤：改进单纯形法的步骤：（1 1）据）据LPLP问题的标准型，确定初始基变量和初始可行问题的标准型，确定初始基变量和初始可行基。求逆矩阵基。求逆矩阵-1-1，得初始基本可行解，得初始基本可行解 （2 2）计算单纯形乘子）计算单纯形乘子 和目标函数值和目标函数值（3 3）计算非基变量检验数）计算非基变量检验数, ,若若，则已得最优解，停止计算；否则转下一步。，则已得最优解，停止计算；否则转下一步。（4 4）据，确定为换入变量，计算）据，确定为换入变量，计算, ,若若 00，则问题没有有限最优解，停止计算，否则，则问题没有有限最优

4、解，停止计算，否则转下一步。转下一步。-1B=C B-1NNBN=C -C B N=C -N-1BZ=C B b=b-1BNX =B b,X0jjkmax / 0 =kx-1kB P-1kB PN0第7页/共27页（5 5）据）据 ，确定，确定 为换出变量。为换出变量。 （6 6）用替代）用替代 得新基得新基1 1，由变换公式，由变换公式 计算计算1 1-1-1，求出新的基本可行解。，求出新的基本可行解。 其中为变换矩阵，构造方法：其中为变换矩阵，构造方法：将换入变量将换入变量 对应的系数列向量对应的系数列向量 做如下变形，主元素做如下变形，主元素 （应在主对角线上）取倒数，其他元素除以主元素

5、（应在主对角线上）取倒数，其他元素除以主元素 并并取相反数。然后用它替换单位矩阵出发，把换出变量取相反数。然后用它替换单位矩阵出发，把换出变量 在在基基B B中的对应列的单位向量。中的对应列的单位向量。重复（重复（2 2）（）（6 6）直至求得最优解。）直至求得最优解。 -1-1-1iki-1-1kik(B b)(B b)min/(B P ) 0 =(B P )(B P )llxlPlkP-1-11k BE Blk Elkal-1kB Pxlkxkal第8页/共27页123451231425max2300028416412zxxxxxxxxxxxx 第9页/共27页034503451( ,)

6、,1;1TBXx x xBPPP（2）计算非基变量的检验数，确定换入变量）计算非基变量的检验数，确定换入变量。012( ,)TNXx x10111B 000100012(,)NNBCCB NNP P 121001 22,3(0,0,0) 0104 02,3,0010 4x x 第10页/共27页(3) 确定换出变量确定换出变量 101021025min0812min, ,324iiB bB PB Px （4）基变换）基变换新基1342,BPPP2121/ 2001/44P ；第11页/共27页1111011/ 21101/ 21010101/41001/4BE B115(,)TNXxx 111

7、1111/ 2111/ 241044011/4101/4NB N 第12页/共27页（6）计算）计算RHS1111/ 2821016161/4123B b ),(),(C,CC;x ,xX;x ,x ,xX;P,P,PBNBTNTB023001111512432431价值系数非基变量基变量基第13页/共27页11111111515(,)101/21 02,0(0,0,3) 0104 0001/40 1(2, 3/4),NNBCC B NNP Px x对应换入变量注：115( , )TNXx x第14页/共27页 111111113min02 16 3min,2140iiB bB PB Px （

8、4）由此得到新的基。）由此得到新的基。 2142,BP P P 12011440P 主主元元素素第15页/共27页11221100101/ 2101/ 2410010412001001/4001/4BE B （4）计算）计算RHS 。 12101/ 282412168001/4123B b 第16页/共27页),(),(C,CC;x,xX;x,x,xX;P,P,PBNBTNTB003022222532412412价值系数非基变量基变量基第17页/共27页235(,)TNXxx (3)确定换出变量确定换出变量 121251254min0283min,41/ 2 2 1/4iiB bB PB Px

9、 22212223535(,)101/ 21 00,0(2,0,3)4130 0001/40 12,1/4,NNBCC B NNP Pxx 第18页/共27页 3152,;BP P P 31/41/ 21/8 125101/ 201/ 24120001/411/42B P 1133211/40101/ 201/ 2041201/81001/401/4021/ 211/ 21/80BE B 5x入入量量的的系系 向向量量是是第19页/共27页 333133334(,)01/401 00,0(2,0,3)21/ 210 11/ 21/800 03/ 2,1/8NNBCC B NNP P 已无正的检

10、验数已无正的检验数33,4()TNXx x 第20页/共27页1*153201/48421/ 21641/ 21/8122xXxB bx 最优值为 3*1342,0,34142BzC B b 第21页/共27页2 算例算例max z = 5x1+2x2+3x3x4+x5 x1+2x2+2x3+x4 = 8 3x1+4x2+x3+x5 = 7 x1, x2, x3, x4, x5 0 1） 101430122154321pppppA系数矩阵：系数矩阵：78b常数项：常数项：11325c价值系数：价值系数：1001540ppB7878100110540bBxxXB 403122325 143221

11、113253210N x3 入基入基41728minmin31010PBbB x4 出基出基第22页/共27页2） 101430122154321pppppA系数矩阵：系数矩阵：78b常数项：常数项：11325c价值系数：价值系数：1102531ppB347812/102/111531bBxxXB 241164125 04312112/102/1131254211N x1 入基入基562/532/14minmin11111PBbB x5 出基出基第23页/共27页3） 3112131ppB5/65/17785/25/15/15/312132bBxxXB5259526 1040125/25/15/15/3531125422N最优解：最优解：X* =(6/5, 0, 17/5, 0, 0 )T101430122154321pppppA系数矩阵：系