对偶理论与灵敏度分析 本章内容重点 改进单纯形法 线性规划的对偶问题概念、狸论及经 济意义 √线性规划的对偶单纯形法 √线性规划的灵敏度分析
对偶理论与灵敏度分析 本章内容重点 ü改进单纯形法 ü线性规划的对偶问题概念、理论及经 济意义 ü线性规划的对偶单纯形法 ü线性规划的灵敏度分析
单純形法的矩阵描述 设线性规划闷题: 加入松弛变量后得到标准型: 目标函数Mz=CX Max z=cx toXs 约束条件AX≤b AX+XS=b 非负条件X0 X,X>0 以X为基变量,并标记成YB,这射将糸数矩阵(4,D 分为(B,N两块。B是基变量的糸教矩阵,N是非基变量 的糸数矩阵。相应的决策变量分为:X=(XB,XN),同时将 目标函数的糸数C分为CB,CN,分别对应于基变量XB和非 基变量XN,养且记作C=(CB,CN
单纯形法的矩阵描述 设线性规划问题 : 目标函数 Max Z=CX 约束条件 AX≤b 非负条件 X≥0 加入松弛变量后得到标准型: Max Z=CX +0Xs AX+IXs=b X，Xs≥0 以Xs为基变量，并标记成XB，这时将系数矩阵(A，I) 分为(B，N)两块。B是基变量的系数矩阵，N是非基变量 的系数矩阵。相应的决策变量分为: X=(XB，XN)T ，同时将 目标函数的系数C分为CB，CN，分别对应于基变量XB和非 基变量XN，并且记作C=(CB, CN)
单純形法的矩阵描述 若经过迭代运算后,在基矩阵中可能还存在松弛变量或 全无松弛变量。为了阐述方便,设: B X X NI X SI A= N SI X S2 B,N,S分别表示对应基变量、非基变量、松弛变量的 糸数矩阵。这肘线性规划问题可以表示为: 目标函数Maz=CBXB+CNXN=CBXB+CMXM+Cs2Xs2(2-1 约束条件BXB+NXN=BXB+N1XM+S2Xs2=b (2-2) 非负条件XBXN≥0
单纯形法的矩阵描述 若经过迭代运算后，在基矩阵中可能还存在松弛变量或 全无松弛变量。为了阐述方便，设: ú û ù ê ë é = ú û ù ê ë é = ú û ù ê ë é = ú û ù ê ë é = ú û ù ê ë é = 2 1 2 1 2 1 1 1 ; ; ; ; S N N N B A X X X X X X X X X S S S S N N S B B B，N，S分别表示对应基变量、非基变量、松弛变量的 系数矩阵。这时线性规划问题可以表示为: 条件 0 (2 3) 约束条件 (2 2) 目标 (2 1) 1 1 2 2 1 1 2 2 ³ - + = + + = - = + = + + - B N B N B N S B B N N B B N N S S X X BX NX BX N X S X b MaxZ C X C X C X C X C X 非负 ， 函数
单純形法的矩阵描述 将(2-2)式移项后得到: BXB=6-MXNI-S2Xs2 给等式两边左乘B1后得到: XB=Bb-B MXNI-BS2Xs2 将(2-4)式代入目标函数(2-1)式,因S2是单位矩阵,得到: Z=CBBb+(CNI-CBBMXN +(Cs2-CBBD)Xs2(2-5) 令非基叟量XN=0,可得到一个基本可行解: Bb 此附目标函数值为:Z=CBb
单纯形法的矩阵描述 将(2-2)式移项后得到: BXB b N1X N1 S2XS2 = - - 给等式两边左乘B-1后得到: (2 4) 2 2 1 1 1 1 1 = - - - - - - XB B b B N X N B S XS 将(2-4)式代入目标函数(2-1)式，因S2是单位矩阵，得到: ( ) ( ) (2 5) 2 1 1 1 2 1 1 1 = + - + - - - - - B N B N S B XS Z C B b C C B N X C C B I 令非基变量XN=0，可得到一个基本可行解: 此时目标函数值为: ú û ù ê ë é = -0 1 (1) B b X Z CBB b -1 =
单純形法的矩阵描述 (1)检验数的表示 非基变量的糸数(CM1-CBN)就是上章中用符号c表示的 检验数。因为Cs2=0,I是草位矩阵,故Xs2的糸数是-CBB1。 XB在(2-5)式中的糸数为0,实质上是 CB-CBB1B=0,因此所 有`量的检验数可以用C-CB14和CBB1表示。 (2)0规则表示为: 6= min (Bb (B b) (B Pi) (BP)>0 (B Pi) 这里的(B1b.表示(B1b)中的第计个元素,(BP表示向 量BP)中的第个元素
单纯形法的矩阵描述 j i i j i j i i B P B b B P B P B b ( ) ( ) ( ) 0 ( ) ( ) min 1 1 1 1 1 - - - - - = úû ù êë é q = > (1)检验数的表示: 非基变量的系数(CN1-CBB-1N1)就是上章中用符号cj-zj表示的 检验数。因为CS2=0,I是单位矩阵,故XS2的系数是-CBB-1。 XB在(2-5)式中的系数为0，实质上是CB-CBB-1B=0，因此所 有变量的检验数可以用C-CBB-1A和-CBB-1表示。 (2) θ规则表示为: 这里的(B-1b)i表示(B-1b)中的第i个元素， (B-1Pj)i表示向 量(B-1Pj)中的第i个元素