清华大学出版社：《运筹学》课程教学资源（PPT课件讲稿，教材第三版）第2章 对偶理论和灵敏度分析 第1节 单纯形法的矩阵描述

运筹学 第2章 对偶理论和灵 (第三版) 敏度分析 第1节 《运筹学》教材编写组编 单纯形法的矩 阵描述 钱颂迪制作 清华大学出版社

运筹学 （第三版） 《运筹学》教材编写组 编 清华大学出版社 第2章 对偶理论和灵 敏度分析 第1节 单纯形法的矩 阵描述 钱颂迪 制作

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

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

第1节单纯形法的矩阵描述 设线性规划问题 目标函数maxz=CX; 约束条件AX≤b 非负条件X≥0

第1节 单纯形法的矩阵描述 设线性规划问题 : 目标函数 max z=CX; 约束条件 AX≤b; 非负条件 X≥0

给这线性规划问题的约约束条件 加入松弛变量以后,得到标准型 max z=CX+OX: ax+lx=b:x20 这里Ⅰ是m×m单位矩阵 0 0

给这线性规划问题的约约束条件 加入松弛变量以后，得到标准型： max z=CX+0Xs ; AX+IXs =b; X，X s≥0 这里I 是m×m单位矩阵。           = 0 1 1 0      I

若以X。为基变量,并标记成X8 这是将系数矩阵(A,I)分为(B,N)两 块。B是基变量的系数矩阵, N是非基变量的系数矩阵 决策变量分为: X

若以Xs为基变量，并标记成XB 这是将系数矩阵（A，I）分为（B，N）两 块。B是基变量的系数矩阵， N是非基变量的系数矩阵。 决策变量分为：         = N B X X X

将目标函数的系数C分为C,CN 分别对应于基变量X2和非基变量x 并且记作C=(CB,CN)

将目标函数的系数C分为CB，CN 分别对应于基变量XB和非基变量XN。 并且记作C=（CB , CN）

若经过迭代运算后,可表示为 基变量 B同可包含原基变量和松弛变量 X Ⅹ, 非基变量:XN=×5)

若经过迭代运算后，可表示为： ; X X X X X X S N N S B B         =         = 2 1 1 1 非基变量： 可包含原基变量和松弛变量 基变量

相应有 其中= B 系数矩阵A= 基变量 松啪变量.X(Xs,)非基变量

相应有 非基变量 基变量 松弛变量： 系数矩阵 其中 →        =         =         = 2 1 2 1 S S S X X X ; S N ; N N B A

线性规划问题可表示为: 目标函数maxz=CBXB+CNXN -CRXR+CN XN +CS.X(2-1) 约束条件BXB+NXN=B+N1YN+S2Y (2-2) 非负条件X,XN≥0 3-2)

线性规划问题可表示为： ,X ( ) b ( ) N X 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  − = − + = + + = + + − = + 非负条件 约束条件 目标函数

将(2-2)式移项及整理后: BX=6-MX-sX XB=B b-BMXN-BS2Xs 目标函数: z=CBB b+(CN, -CBB NXN +(C.-CBB DXS

将（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 − − − − − − + − = + − = − − = − − 目标函数：