清华大学出版社：《数学建模》课程教材PPT教学课件（线性规划与目标规划）第3章 对偶理论和灵敏度分析

第2节改进单纯形法 (5)计算非基变量的系数矩阵 1/2)1 N1=4→B1N 104 1/4人1 1-1/2 40 1/4 (6)计算RHS 1-1/28(2 B1b=1016|=16 1/412)(3 清华大学出版社

清华大学出版社 27 第2节 改进单纯形法 （5）计算非基变量的系数矩阵 （6）计算RHS           − =                     −  =           = − 1 4 0 1 2 4 1 1 4 1 1 4 1 0 1 1 2 1 4 1 1 1 1 1 / / / / N B N           =                     − = − 3 16 2 12 16 8 1 4 1 0 1 1 2 1 1 / / B b

第2节改进单纯形法 第1步计算结束后的结果 基B1=(P3,P,P 基变量XB=(x,x4,x2); 非基变量X=(x,x3)y 价值系数C=(,C)=(00320) 清华大学出版社

清华大学出版社 28 第2节 改进单纯形法 第1步计算结束后的结果 ( ) ( ) ( ) C (C ,C ) (( , , ),( , )) X x ,x ; X x ,x ,x ; B P ,P ,P ; B N T N T B 0 0 3 2 0 1 1 1 1 1 5 3 4 2 1 3 4 2 = = = = = 价值系数 非基变量 基变量 基

第2节改进单纯形法 计算非基变量的检验数,确定换入变量 aN= C - M1(注意:N1=(P,P) 01/2Y10 =(2,0)-(00301040 001/401 ,-3/4)→对(x,x) 换入变量 清华大学出版社

清华大学出版社 29 第2节 改进单纯形法 计算非基变量的检验数，确定换入变量 ( ) ( ) ( ) ( ) 换入变量 对应 注意： 1 5 1 1 1 5 1 1 2 3 4 1 0 0 0 4 1 0 0 1 4 0 1 0 1 0 1 2 2 0 0 0 3 1 1 1 , / x ,x / / , ( , , ) C C B N ( N P ,P ) N N B = −                      − = − = − = − 

第2节改进单纯形法 确定换出变量 (B 0=min iBP>0 BI P) 2163 mn(40 =2→对应x 清华大学出版社

清华大学出版社 30 第2节 改进单纯形法 确定换出变量 ( ) ( ) 2 1 0 3 4 16 1 2 1 0 1 1 1 1 1 1 1 min , , x B P B P B b min i i  =  对应      =         =  − − − 

第2节改进单纯形法 由此得到新的基 B2=(P,P4,P2) 主元素 00 4→E 4 0 0 00 10010-1/2 Bl=E、B 410010 001人(001/4 10-1/ 412 001/4 清华大学出版社

清华大学出版社 31 第2节 改进单纯形法 由此得到新的基 ( )           − − =           −           = = −            = −            = −           = = − − 0 0 1 4 4 1 2 1 0 1 2 0 0 1 4 0 1 0 1 0 1 2 0 0 1 4 1 0 1 0 0 0 0 1 4 1 0 1 0 0 0 4 1 0 4 1 1 2 1 1 2 1 2 2 1 4 2 / / / / B E B P E B P ,P ,P  2 主元素