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

第2节改进单纯形法 重复以上的步骤,直到获得 E.…EE,A= A 可见EnE2E1=A1。用这方法可以求得单纯形法的基矩阵B的 逆矩阵B1 清华大学出版社

清华大学出版社 22 第2节 改进单纯形法 重复以上的步骤，直到获得 1 2 1 1 1 1 − =               Em E E A = A   可见En…E2E1=A-1。用这方法可以求得单纯形法的基矩阵B的 逆矩阵B -1

第2节改进单纯形法 以例1为例进行计算 maXz=2x1+3x2+0x3+0x4+0x5 x1+2x2+x3 4x +x4=16 4. +x=12 清华大学出版社

清华大学出版社 23 第2节 改进单纯形法 以例1为例进行计算。 4 12 4 16 2 8 2 3 0 0 0 2 5 1 4 1 2 3 1 2 3 4 5 + = + = + + = = + + + + x x x x x x x max z x x x x x

第2节改进单纯形法 第1步:确定初始基,初始基变量;确定换入,换出变量 (1)确定初始基和初始基变量: B=(2,P,P) KB=x (2)计算非基变量的检验数,确定换入变量。 C-CaB6N(注意:N=(P2 0/12 ,3)-(0001040 04 (2,3)→ 对应(,x 换入变量 清华大学出版社

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

第2节改进单纯形法 (3)确定换出变量 表示选择>0的元素 0=minl (B BP>O (B-B) 81612 min 204=3→对应x 清华大学出版社

清华大学出版社 25 第2节 改进单纯形法 (3) 确定换出变量 ( ) ( ) 3 5 4 12 0 16 2 8 2 0 1 0 2 1 0 1 0 min , , x B P B P B b min i i  =  对应      =         =  − − −  表示选择>0的元素

第2节改进单纯形法 (4)基变换计算 将新的基(P,P,P)→单位矩阵。计算: 1/2 1/2 P2=0→51=0构造E 10 1/4 主元素 1/4 -1/2Y/1 1/2 B=E B 10 10 1/4 1/4 清华大学出版社

清华大学出版社 26 第2节 改进单纯形法 （4）基变换计算 将新的基 (P3 ,P4 ,P2 ) 单位矩阵。计算：           − =          −  =           = 1 4 1 0 1 1 2 1 4 0 1 2 4 0 2 2 1 1 / / E / / P ；构造 主元素            − =                     − = = − − 1 4 1 0 1 1 2 1 1 1 1 4 1 0 1 1 2 1 1 0 1 1 / / / / B E B