《运筹学》课程教学资源（PPT课件讲稿）第二章 线性规划的进一步研究 2.1 单纯形法的矩阵描述、2.2 对偶原理

第二章线性规划的进一步研究 2.1单纯形法的矩阵描述 为什麽要研究单纯形法的矩阵描述? &进一步讨论修正单纯形法 &便于理论推导(如对偶定理的证明) 二、怎样进行矩阵描述? 关键—写出两个基本的表达式

2.1单纯形法的矩阵描述 一 、为什麽要研究单纯形法的矩阵描述？ & 进一步讨论修正单纯形法 & 便于理论推导（如对偶定理的证明） 二、怎样进行矩阵描述？ 关键——写出两个基本的表达式。 第二章 线性规划的进一步研究

1、准备工作: (1)标准型的矩阵形式 Maxz= cX AX-b st X≥0 (2)将式中矩阵写成分块矩阵形式 C=(CB: CN) X=(XB: XN) △ A=(1,P2,…,Pn)=(B:N)

1、准备工作： （1）标准型的矩阵形式——     = = 0 . . X AX b st MaxZ CX （2）将式中矩阵写成分块矩阵形式 ( ) C CB CN =  ( ) X XB X N =  ( , , , ) ( ) A P1 P2  Pn BN  = =

2、将分块形式代入矩阵形式标准 型,得出两个基本表达式: (1)由约束条件 AX=(B:N) -BX+NX=b 可得用非基变量表示基变量的表达式: XR=B(6-NX)=Bb-BNXN(2-1)

2、将分块形式代入矩阵形式标准 型，得出两个基本表达式： （1）由约束条件 BX NX b X X AX B N B N N B = + =           = (  )  可得 用非基变量表示基变量的表达式： B N B NX N X B b NX B b 1 1 1 ( ) − − − = − = − （2-1）

(2)将式(2-1)代入目标函数的表 达式,可得: 用非基变量表示目标函数的表达式: Z=CX=(CB:CM).=CBXB+CNXN X CB(Bb-B"NXN)+CNXN CBBb-CBBNX+CNXN =CBb+( CN-CRBN)XN「令0=C-CBM得 Z=C B6+o X (2-2)

（ ） 令 得 2 2 ( ) ( ) ( ) 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 N X C X C B b B N X C X C X C X X X Z C X C C     （2）将式（2-1）代入目标函数的表 达式，可得： 用非基变量表示目标函数的表达式：

(3)借助一个恒等式推出用非基变量表 示目标函数的另一个等价表达式: CR-CRB B)XR=0 CRXR-CRB BXR=0 代入式(2-2),并令z=CB Z=CBB +(CN-CBB NXN+CBXB-CBB-BX b+(C-4)X (2-4) 单纯形乘子

（3）借助一个恒等式推出用非基变量表 示目标函数的另一个等价表达式： ( ) 0 1 − = − CB CB B B XB 0 1 − = − CB XB CB B BX B 代入式（2-2），并令 −1  = CB B b C A X Z CB B b CN CB B N X N CB X B CB B BX B ( ) ( ) 1 1 1 =  + − = + − + − − − − （2-4） 单纯形乘子

三、单纯形表格的矩阵形式: b TB X TⅩ BbBB BN 0 B b CM-CB N

三、单纯形表格的矩阵形式： cj  j T XB T X N T CB XB B b −1 B B −1 B N −1 − Z C B b B −1 − CN CB B N −1 − CB XB xj b CB CN 0

2.2对偶原理 对偶问题的提出 1、对偶思想举例 周长一定的矩形中,以正方形面积 最大;面积一定的矩形中,以正方形 周长最小;

一、对偶问题的提出 1、 对偶思想举例 周长一定的矩形中，以正方形面积 最大；面积一定的矩形中，以正方形 周长最小； 2．2 对偶原理

2、换个角度审视生产计划问题 例2-1要求制定一个生产计划方案,在劳动 力和原材料可能供应的范围内,使得产品 的总利润最大 Maxz=2x1+3x2 +3x3 x1+x2+x2<3 St.x1+4x2+7x2≤9 OX x,≥0 15253

2、 换个角度审视生产计划问题       + +  + +  = + + , , 0 4 7 9 3 . . 2 3 3 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x st MaxZ x x x 例2-1要求制定一个生产计划方案，在劳动 力和原材料可能供应的范围内，使得产品 的总利润最大

它的对偶问题就是一个价格系统, 使在平衡了劳动力和原材料的直接成本 后,所确定的价格系统最具有竞争力: Minw=3v,+9y y1+y2≥2(用于生产第种产品的资 y1+4y2≥3 s.t.. 源转让收益不小于生产该 1+7y2≥3 种产品时获得的利润) y1,2≥0 对偶变量的经济意义可以解释为对工时 及原材料的单位定价;

它的对偶问题就是一个价格系统， 使在平衡了劳动力和原材料的直接成本 后，所确定的价格系统最具有竞争力：         +  +  +  = + , 0 7 3 4 3 2 . . 3 9 1 2 1 2 1 2 1 2 1 2 y y y y y y y y st MinW y y （用于生产第i种产品的资 源转让收益不小于生产该 种产品时获得的利润） 对偶变量的经济意义可以解释为对工时 及原材料的单位定价 ；

若工厂自己不生产产品A、B和C,将现 工时及原材料转而接受外来加工时, 那么上述的价格系统能保证不亏本又最富 有竞争力(包工及原材料的总价格最低) 当原问题和对偶问题都取得最优解时,这 对线性规划对应的目标函数值是相等的: Zmax=wmin=8

若工厂自己不生产产品A、B和C，将现 有的工时及原材料转而接受外来加工时， 那么上述的价格系统能保证不亏本又最富 有竞争力（包工及原材料的总价格最低） 当原问题和对偶问题都取得最优解时，这 一对线性规划对应的目标函数值是相等的： Zmax=Wmin=8