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

第3章对偶理论和灵敏度分析 第1节单纯形法的矩阵描述 第2节改进单纯形法 第3节—对偶问题的提出 ■第4节线性规划的对偶理论 ■第5节对偶问题的经济解释—影子价格 ■第6节对偶单纯形法 ■第7节灵敏度分析 ■第8节*参数线性规划 清华大学出版社

清华大学出版社 2 第3章 对偶理论和灵敏度分析 ◼第1节 单纯形法的矩阵描述 ◼第2节 改进单纯形法 ◼第3节 对偶问题的提出 ◼第4节 线性规划的对偶理论 ◼第5节 对偶问题的经济解释——影子价格 ◼第6节 对偶单纯形法 ◼第7节 灵敏度分析 ◼第8节* 参数线性规划

第1节单纯形法的矩阵描述 设线性规划问题可以用如下矩阵形式表示: 目标函数max=CX 约束条件AK<b 非负条件≌0 清华大学出版社

清华大学出版社 3 第1节 单纯形法的矩阵描述 设线性规划问题可以用如下矩阵形式表示： 目标函数 max z=CX 约束条件 AX≤b 非负条件 X≥0

第1节单纯形法的矩阵描述 将该线性规划问题的约束条件加入松弛变量后,得到标 准型: max ==CX+OX AX+X=b X,X>0 其中1是m×m单位矩阵。 清华大学出版社

清华大学出版社 4 第1节 单纯形法的矩阵描述 将该线性规划问题的约束条件加入松弛变量后，得到标 准型： max z=CX+0Xs AX+IXs=b X，Xs ≥0 其中I 是m×m单位矩阵

第1节单纯形法的矩阵描述 若以X为基变量,并标记成X,可将系数矩阵(A,I) 分为(B,N)两块。B是基变量的系数矩阵,N是非基 变量的系数矩阵。并同时将决策变量也分为两部分: X XX 相应地可将目标函数系数C分为两部分:C和CN,分别 对应于基变量X和非基变量X,并且记作 C=(C. C 清华大学出版社

清华大学出版社 5 第1节 单纯形法的矩阵描述 若以Xs为基变量，并标记成XB，可将系数矩阵（A，I） 分为（B，N）两块。B是基变量的系数矩阵，N是非基 变量的系数矩阵。并同时将决策变量也分为两部分： 相应地可将目标函数系数C分为两部分：CB和CN，分别 对应于基变量XB和非基变量XN，并且记作 C=（CB , CN）         = N B X X X

第1节单纯形法的矩阵描述 若经过迭代运算后,可表示为: 基变量 可包含原基变量和松弛变量 X X 相应有 非基变量:Xx=) B N 系数矩阵A=:其中N N 基变量 松弛变量:Xs2x)非基变量 清华大学出版社

清华大学出版社 6 第1节 单纯形法的矩阵描述 若经过迭代运算后，可表示为： 相应有 ; X X X X X X S N N S B B         =         = 2 1 1 1 非基变量： 可包含原基变量和松弛变量 基变量 非基变量 基变量 松弛变量： 系数矩阵 其中 →        =         =         = 2 1 2 1 S S S X X X ; S N ; N N B A

第1节单纯形法的矩阵描述 线性规划问题可表示为: 目标函数maxz=CBYB+CHN CBXB+CNXN +CsXs(2-1) 约束条件BXB+NXx=BB+NX+S2X b (2-2) 非负条件XB,X≥0 (3-2) 清华大学出版社

清华大学出版社 7 第1节 单纯形法的矩阵描述 线性规划问题可表示为： ,X ( ) b ( ) NX BX N X S X C X C X C X ( ) X C X N N B N S B B N N S S B N N X 0 3 2 2 2 BX 2 1 max z C B B 1 2 B 1 2 1 1 2 2  − = − + = + + = + + − = + 非负条件 约束条件 目标函数

第1节单纯形法的矩阵描述 将(2-2)式移项及整理后得到: BXB=b-NXN-S2Xs X=B.X 目标函数: z=CBBb+(CN -CRBNXN +(CS.-CRB1X 清华大学出版社

清华大学出版社 8 第1节 单纯形法的矩阵描述 将（2-2）式移项及整理后得到： S B S B N B N B N s B N S (C C B I )X z C B b (C C B N )X X B b B N X B S X ; BX b N X S X ; 1 1 1 1 2 1 1 1 1 1 2 2 1 1 1 2 1 2 − − − − − − + − = + − = − − = − − 目标函数：

第1节单纯形法的矩阵描述 令非基变量=0,由上式得到: 基可行解x/Bb 0 目标函数的值z=CBBb 清华大学出版社

清华大学出版社 9 第1节 单纯形法的矩阵描述 令非基变量=0，由上式得到： B b ; B b X ( ) 1 B 1 1 z C 0 − − =         = 目标函数的值 基可行解

第1节单纯形法的矩阵描述 (1)非基变量的系数表示为: (CN,-CBB NI 对应已用的检验数符号 C1-1(j=1,2,…,n) 检验数也可表示为: C-CaBA与-CaB1 清华大学出版社

清华大学出版社 10 第1节 单纯形法的矩阵描述 （1）非基变量的系数表示为： 1 B 1 B j 1 1 C-C -C c 1 2 1 − − − − = − B A B z ( j , , ,n ) (C C B N ) j N B 与 检验数也可表示为： 对应已用的检验数符号 

第1节单纯形法的矩阵描述 (2)规则表示为: RHS值 表示选用>0的分量 6=mi/(8 BP>0= (Bb) (BP) (B Pi) 换入变量的系数向量 清华大学出版社

清华大学出版社 11 第1节 单纯形法的矩阵描述 （2）θ规则表示为： RHS值 表示选用>0的分量 换入变量的系数向量 j i i j i j i i ( B P ) ( B b ) ( B P ) ( B P ) ( B b ) min 1 1 1 1 1 0 − − − − − =          = 