上海交通大学：《线性规划与非线性规划》教学资源_第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+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 非基变量： 可包含原基变量和松弛变量 基变量 若经过迭代运算后，可表示为：

相应有 系数矩阵A= 松驰变量：X:气X) 基变量 ”非基变量

相应有 非基变量 基变量 松弛变量： 系数矩阵 其中 →⎟⎟⎠⎞ ⎜⎜⎝⎛ = ⎟⎟⎠⎞ ⎜⎜⎝⎛ = ⎟⎟⎠⎞ ⎜⎜⎝⎛ = 2 1 2 1 S S S X X X ; S N N; N B A

线性规划问题可表示为： 目标函数 max Z=CBX8+CN XN =CEXB+CN,XN +Cs,Xs, (2-1) 约束条件 BXB+NXN BXE+NiXN +S2Xs. =b (2-2) 非负条件XB,XN≥0 (3-2)

线性规划问题可表示为： 0, )23( )22( )12( 1 2 11 22 1 2 ≥ − = − ++=+ ++= − += N N B N S SSNNBB NNB X b XSXNBXNX XCXCXC XCX B B B X BX Czmax 非负条件 约束条件 目标函数

将(2-2)式移项及整理后： BXB =b-NIXN -S2X5:3 X8=B-b-B-N XN -B-S2Xs 目标函数： CgB-b+(CN -CgB-N)XN +(C.C,8D)X

2 2 1 1 1 2 1 2 ( ) ( ) ; ; 1 1 1 1 2 1 1 1 1 1 2 BS S B N B N B N s B N S XIBCC XNBCCbBCz XSBXNBbBX XSXNbBX − − − − − − −+ −+= −= − −−= 目标函数： 将（2-2）式移项及整理后： 0

令非基变量=O;由上式得到： 基可行解 Bb 0 目标函数的值 Z=CBB b

令非基变量=0；由上式得到： bB ; bB X )( 1 B 1 1 Cz 0 − − = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = 目标函数的值 基可行解

(1)非基变量的系数表示为： (CN-CEB-N) C's.-CBB 对应已用的检验数符号 cj-3j(j=1,2,…,n) 检验数也可表示为： C-CBB-1A与-CBB

（1）非基变量的系数表示为： 1 1 1 1 ),,2,1( ( ) 1 − − − =− − BAB jz n NBCC j N B B B j C-C C￾c 与 检验数也可表示为： 对应已用的检验数符号 " 2 1 C CB S B − −