改进单纯形法优秀课件

1、1单纯形法的矩阵描述单纯形法的矩阵描述2设线性规划问题可以用如下矩阵形式表示：设线性规划问题可以用如下矩阵形式表示： 目标函数目标函数 max z=CX 约束条件约束条件 AXb 非负条件非负条件 X03 将该线性规划问题的约束条件加入松弛变将该线性规划问题的约束条件加入松弛变量后，得到标准型量后，得到标准型： max z=CX+0Xs AX+IXs=b X，X s0 其中，其中，I 是是mm单位矩阵。单位矩阵。 4 若以若以Xs为基变量，并标记成为基变量，并标记成XB，可将系数矩阵，可将系数矩阵(A，I)分为分为 (B，N) 两块。两块。B是基变量的系数矩阵，是基变量的系数矩阵，N是非基变量

2、是非基变量的系数矩阵。并同时将决策变量也分为两部分：的系数矩阵。并同时将决策变量也分为两部分： 相应地可将目标函数系数相应地可将目标函数系数C分为两部分：分为两部分：CB和和CN，分，分别对应于基变量别对应于基变量XB和非基变量和非基变量XN，并且记作，并且记作: C=（CB, CN）BNXXX5若经过迭代运算后，可表示为：若经过迭代运算后，可表示为：相应有相应有:1112;BBSNNSXXXXXX 基变量可包含原基变量和松弛变量非基变量：1212;SSSNBANNSXXX系数矩阵其中基变量松弛变量：非基变量6线性规划问题可表示为：线性规划问题可表示为：11221212max (2 1) (2

3、2),0 (2BBNNBBNNSSBNBNSBNzC XC XC XC XC XBXNXBXN XS XbXX目标函数: 约束条件:非负条件: 3)7将（将（2-2）式移项及整理后得到：）式移项及整理后得到：121211212111121111 ; ; ()()BNSBNsBNBNSBSBXbN XS XXB bB N XB S XzC B bCC B N XCC B I X目标函数：8令非基变量令非基变量=0，由上式得到：，由上式得到：1(1)1 ; 0BB bXzC B b基可行解:目标函数的值: 9（1）非基变量的系数表示为：）非基变量的系数表示为：1-11-1-1(-): -(1,2,

4、 ) -NBjjBBCC B NczjnC C B AC B对应已用的检验数符号检验数也可表示为：与10 （2）规则表示为：规则表示为： RHS值值 表示选用表示选用0的分量的分量 换入变量的系数向量换入变量的系数向量11111()()min()0()()iijijijiB bB bB PB PB P11（3）单纯形表与矩阵表示的关系）单纯形表与矩阵表示的关系:12111111110110(27)BNNBBNBzXB NBXCC B NC BXB bC B b12单纯形表中的数据单纯形表中的数据:基变量基变量 非基变量非基变量等式右边等式右边系数矩阵系数矩阵检验数检验数1 1 0BXB B11

5、1111111 NsNBBBXXRH SB NBB bCCB NCBCB b13小结小结1）掌握矩阵的运算；）掌握矩阵的运算；2）理解基矩阵的作用；）理解基矩阵的作用；3）了解矩阵运算与单纯表的关系。）了解矩阵运算与单纯表的关系。14改进单纯形法改进单纯形法求解线性规划问题的关键是计算求解线性规划问题的关键是计算B-1 。以下介绍一种比较简便的计算以下介绍一种比较简便的计算B-1的方法。的方法。15 设设m n系数矩阵为系数矩阵为A，求其逆矩阵时，可先从第，求其逆矩阵时，可先从第1列开始。列开始。111212122212mmmmmmaaaaaaAaaa以以a11为主元素为主元素, 进行变换：进

6、行变换：11112121111111111/ (1)/mmaaaaaPaaa主元素16然后构造含有（然后构造含有（1）列，而其他列都是单位列的矩阵）列，而其他列都是单位列的矩阵11211111111/00/1/1maaaEaa(1)(1)121(1)(1)2221 11(1)(1)21100;00mmmmmaaaaE PE Aaa 2121211122121111 aaaaaaaa可得到：可得到：17而后以第而后以第2列的列的 为主元素，进行变换为主元素，进行变换:(1)22a(1)(1)1222(1)(1)2222(1)(1)222/1/ (2)/maaaPaa(1)(1)1222(1)22

7、2(1)(1)2221/001/00/1maaaEaa然后构造含有（然后构造含有（2）列，而其他列都是单位列的矩阵）列，而其他列都是单位列的矩阵:可得到可得到:(2)(2)131(2)(2)23221(2)(2)3100100mmmmmaaaaE E Aaa18重复以上的步骤，直到获得重复以上的步骤，直到获得:121111mEE E AA可见，可见，EnE2E1=A-1。用这方法可以求得单纯形法的基矩阵用这方法可以求得单纯形法的基矩阵B的逆矩阵的逆矩阵B-1 19以例以例1为例进行计算。为例进行计算。123451231425max2300028416. .4120,1,2,3,4,5jzxxx

8、xxxxxxxstxxxj20第第1步：确定初始基，初始基变量步：确定初始基，初始基变量;确定换入，换出变量确定换入，换出变量（1）确定初始基和初始基变量：）确定初始基和初始基变量： （2）计算非基变量的检验数，确定换入变量。）计算非基变量的检验数，确定换入变量。030345451,1;1BxBPPPXxx00010001212(,)1001 22,3(0,0,0) 0104 02,3,0010 4NNBCC B NNP Px x对应换入变量注意：21(3) 确定换出变量确定换出变量5101021028 16 12min0min,3204iiB bB PxB P对应表示选择0的元素（4）基变换

9、计算）基变换计算将新的基将新的基 单位矩阵。计算：单位矩阵。计算：342,P P P21121/211/2001041/41/4PE 主元素；构造1111011/2111/2101101/411/4BE B22（5）计算非基变量的系数矩阵）计算非基变量的系数矩阵（6）计算）计算RHS1111111/2111/241044011/411/4NB N1111/2821016161/4123B b23第第1步计算结束后的结果步计算结束后的结果:1111134234215,;,;,;,(0,0,3),(2,0)TBTNBNBP P PXx x xXx xCCC基基变量非基变量价值系数计算非基变量的检验

10、数，确定换入变量：计算非基变量的检验数，确定换入变量：11111111515(,)101/21 02,0(0,0,3) 0104 0001/40 12,3/4, NNBCC B NNP Px x对应换入变量注意：24确定换出变量：确定换出变量：1111111112 16 3min0min,2140iiB bB PxB P对应由此得到新的基：由此得到新的基： 21421211221,111004441000001100101/2101/2410010412001001/4001/42BP P PPEBE B 主元素25计算计算RHS12101/282412168001/4123B b 第第2步计

11、算结束后的结果：步计算结束后的结果：2222214214235,;,;,;,(2,0,3),(0,0)TBTNBNBP P PXx x xXx xCCC基基变量非基变量价值系数26第第3步：计算非基变量（步：计算非基变量（x3, x5）的检验数）的检验数:22212223535(,)101/21 00,0(2,0,3)4130 0001/40 12,1/4,NNBCC B NNP Px x 对应正检验数换入变量注意：确定换出变量确定换出变量:412125125283min0min,41/2 2 1/4iiB bB PxB P对应27新的基新的基:31525125,;101/201/241202001/411/4BP P PxB P 主元素换入变量的系数向量是计算计算B的逆矩阵：的逆矩阵：331/411/401/201/201/801/81E构造1133211/40101/201/4001/2041221/2101/81001/41/21/80BE B28计算非基变量的