第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+IX=b;X,X=0 这里I是m×m单位矩阵。 1 0 二
标准型： 给这线性规划问题的约束条件加入松弛变 量以后，得到 max z=CX+0X s; AX+IXs=b; X，X s≥0 这里I 是m×m单位矩阵。 ⎟⎟⎟⎠⎞ ⎜⎜⎜⎝⎛ = 10 01 " #%# " I
系数矩阵、X的分解： 若以X为基变量，并标记成X ·将系数矩阵(A,I)分为(B,N)两块 一B是基变量的系数矩阵 一N是非基变量的系数矩阵 ·决策变量分为： X= ·目标函数的系数C分为C,CN XN 分别对应于基变量X,和非基变量X 记作C=(CB,CN)
系数矩阵、X的分解： • 若以X s为基变量，并标记成X B • 将系数矩阵（A，I）分为（B，N）两块 – B是基变量的系数矩阵 – N是非基变量的系数矩阵 • 决策变量分为： • 目标函数的系数C分为C B，C N 分别对应于基变量X B和非基变量X N 。 记作C= （ C B, C N ） ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = N B X X X
若经过迭代运算后，可表示为： 基变量： (XB XB Xs 可包含原基变量和松变量 非基变量：XN= XN Xs:
; : 2 1 1 1 ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = S N N S B B X X X X X X 非基变量： 可包含原基变量和松弛变量 基变量 若经过迭代运算后，可表示为：