第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