第二章线性规划的进一步研究 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 BN = =
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
