第二章 对偶理论与灵敏度分析
第二章 对偶理论与灵 敏度分析
82.1单纯形法矩阵描述一、为什摩要研究单纯形法的矩阵描述？&进一步讨论修正单纯形法&便于理论推导（如对偶定理的证明）怎样进行矩阵描述？关键写出两个基本的表达式
一、为什麽要研究单纯形法的矩阵描述？ 一、为什麽要研究单纯形法的矩阵描述？ & 进一步讨论修正单纯形法 进一步讨论修正单纯形法 & 便于理论推导（如对偶定理的证明） 便于理论推导（如对偶定理的证明） 二、怎样进行矩阵描述？ 二、怎样进行矩阵描述？ 关键——写出两个基本的表达式。 写出两个基本的表达式。 §2.1 单纯形法矩阵描述 单纯形法矩阵描述
1、准备工作：（1）标准型的矩阵形式CXMaxZ=AXbS.t.X0≥（2）将式中矩阵写成分块矩阵形式C =(CB:Cn)X =(XB:X~)AA =(P,P2,".:,P)=(B:N)
1、准备工作： （1）标准型的矩阵形式 ）标准型的矩阵形式—— ⎩⎨⎧ ≥= = 0 . . X AX b s t MaxZ CX （2）将式中矩阵写成分块矩阵形式 ）将式中矩阵写成分块矩阵形式 ( ) C CB CN = M T X XB X N = ( M ) ( , , , ) ( ) A P1 P2 L Pn BMN Δ = =
2、将分块形式代入矩阵形式标准型，得出两个基本表达式(1)由约束条件(XBAX =(B N)= BXβ + NX = b可得用非基变量表示基变量的表达式Xβ=B'(b-NX)=B"b-B'NX(2.2)
2、将分块形式代入矩阵形式标准 、将分块形式代入矩阵形式标准 型，得出两个基本表达式： 型，得出两个基本表达式： （1）由约束条件 BX NX b X X AX B N B N N B = + = ⎟⎟⎟⎠⎞ ⎜⎜⎜⎝⎛ = ( ) 可得 用非基变量表示基变量的表达式： 用非基变量表示基变量的表达式： B N B NXN X B b NX B b 1 1 1 ( ) − − − = − = − （2.2）
（2）将式（2.2）代入目标函数的表达式可得：用非基变量表示目标函数的表达式：XBZ=CX=(CBCN)=C,Xβ+CNXNXN)=C(B"b-B'NX)+CXN=C,B"b-C,B-'NX +CX令O~=C-C,B'N得=C,B"b+(C-C,B'M)X(2.3)Z=C,Bb+0nX
（ ） 令 得 2.3 ( ) ( ) ( ) 1 1 1 1 1 1 1 1 B N N B N B N N N B B B N N N B N N N B B N N N B B N Z C B b X C B b C C B N X C C B N C B b C B NX C X C B b B NX C X C X C X X X Z CX C C σ σ = + = + − = − = − + = − + = + ⎟⎟⎟⎠⎞ ⎜⎜⎜⎝⎛ = = − − − − − − − − （2）将式（2.2）代入目标函数的表达式， ）代入目标函数的表达式， 可得：用非基变量表示目标函数的表达式： 用非基变量表示目标函数的表达式：