改进单纯形法幻灯片

《改进单纯形法幻灯片》由会员分享，可在线阅读，更多相关《改进单纯形法幻灯片（29页珍藏版）》请在装配图网上搜索。

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

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

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

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

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

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

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

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

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

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

11、,3),(0,0)TBTNBNBP P PXx x xXx xCCC基基变量非基变量价值系数第第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对应新的基新的基:31525125,;101/201/241202001/411/4BP P PxB P 主元素换入变量的系数向量是计算计算B的逆矩阵：的逆矩

12、阵：331/411/401/201/201/801/81E构造1133211/40101/201/4001/2041221/2101/81001/41/21/80BE B计算非基变量的检验数计算非基变量的检验数:333133334,01/401 0 0,0(2,0,3)21/210 13/2,1/81/21/800 0 NNBCC B NNP P 已无正检验数注意：得到最优解：得到最优解：1*153201/48421/21641/21/8122xXxB bx *1342,0,34142BzC B b 目标函数的最优值为：目标函数的最优值为：部分资料从网络收集整理而来，供大家参考，感谢您的关注！