运筹学课件单纯形法的迭代原理.ppt

1、，用单位阵的每一个列向量对应的决策变量用单位阵的每一个列向量对应的决策变量作为作为“基变量基变量”，这样，出现在单纯形表，这样，出现在单纯形表格中的格中的B(i)列（即约束方程的右边常数）列（即约束方程的右边常数）值正好就是基变量的取值。值正好就是基变量的取值。构造单位阵构造单位阵（2）写出初始基可行解）写出初始基可行解令令).3,2,1(0.11njxbxPtsxcMaxZjnjjjnjjj100010001),(21mPPPB：当线性规划的约束条件均为当线性规划的约束条件均为，其松弛变量的系数矩阵为单位，其松弛变量的系数矩阵为单位矩阵；当线性规划的约束条件均为矩阵；当线性规划的约束条件均为

2、或或=，为便于找到初始基，为便于找到初始基可行解，构造人工变量，人为产生一个单位矩阵。可行解，构造人工变量，人为产生一个单位矩阵。TmTmbbbxxxX)0,.,0,0,.,()0,.,0,0,(2100201)0(式中式中p p1 1,p,pm m 为基变量为基变量,同其所对应的同其所对应的x x1 1,x,x2 2,.,x,.,xm m为基变量；其它变量为基变量；其它变量x xm+1m+1,x,xm+2m+2，,x,xn n为非基变量。令所有的非基变量为非基变量。令所有的非基变量等于零。等于零。定义：两个基可行解称为相邻的，如果它们之间变换定义：两个基可行解称为相邻的，如果它们之间变换且仅

3、变换一个基变量。且仅变换一个基变量。初始基可行解的前初始基可行解的前m m个为基变量，个为基变量，2、基变换、基变换TmooxxxX),.,.,(00201)0(代入约束条件有代入约束条件有miiibxp10).3,2,1(0.11njxbxPtsxcMaxZjnjjjnjjj系数矩阵的增广矩阵系数矩阵的增广矩阵mnmjmmmnjmnjmnjmmbaaabaaabaaabpppppp,1,2,2,21,21,1,11,1121.1.00.0.10.0.01.因为因为p1,pm,是一个基，其他向量是一个基，其他向量pj可以这个基可以这个基的线性组合表示：的线性组合表示：miiijjpap1mii

4、ijjpap1miiibxp1)0(bppaxbxppapjimiijimiiimiiijj10101)(,)(相减，然后乘上一个正数,加上经过整理得到：njjjbxp1TmjmjaxaxX)0,.,.,0,.,(0101)1(找到满足约束方程组的另一点：0)(1miiijjpap第j个大于0只变换1个变量；前m个变量必须换出1个,00ijiaxaljxaaxalijijiji000|min,0上式成立，令)(,0)(,00liliaxiji其中其中是是X X（1 1）的第的第j j个坐标的值，要使个坐标的值，要使X X（1 1）是一个是一个基可行解，对所有的基可行解，对所有的i=1,m,i=

5、1,m,存在存在令这m个不等式至少有一个等号成立，当是一个可行解。因为变量是一个可行解。因为变量x11,x21,xl-11,xl+11,xm1,xj1所对应的向量，所对应的向量，经过重新排列后加行经过重新排列后加行b列形成的增广矩阵为：列形成的增广矩阵为：mmjljllljljljjmljlbababababababpppppp10000.010000000000100.000.100.00.01.111122111121Lalj(1/alj)=1rL(-al-1j)+rL-10-(bL/aLj)+bL-1TmjmjaxaxX)0,.,.,0,.,(0101)1(所以，所以，P P1 1,P,

6、P2 2,P,Pl-1l-1,P,Pj j,P,Pl+1l+1,P,Pm m,是一个基。是一个基。进行初等行变换，将第进行初等行变换，将第L L行乘上行乘上1/a1/aljlj,再分别乘以再分别乘以-a-aijij,(i=1,l-1,l+1,m),(i=1,l-1,l+1,m)加到各行，增广矩阵加到各行，增广矩阵的左边变成一个单位矩阵，的左边变成一个单位矩阵，),.,.,(),.,.,(11211111111mljlTjmmjlljlljxxxxxxababababb是相邻的基可行解。与)0()1(XX、最优性检验和解的判别、最优性检验和解的判别将代入目标函数计算：)1()0(XX和jjmii

7、jijjmiijijjmiijiimiiizcaccaccZcaxcZxcZ11)0(10)1(10)0(、如果所有的检验数，表明现有的顶点对应、如果所有的检验数，表明现有的顶点对应的基可行解为最优解。的基可行解为最优解。、当所有的检验数，又对某个非基变量、当所有的检验数，又对某个非基变量xj的检验数等于，并且可以找到的检验数等于，并且可以找到0,这表明可以找这表明可以找到一个顶点目标函数达到最大，说明到一个顶点目标函数达到最大，说明LP有无穷多个有无穷多个最优解。最优解。、如果存在某个检验数、如果存在某个检验数0,又又0,表明目标函数达到无限，说明表明目标函数达到无限，说明LP有无界解。有无

8、界解。0j0jjjP取值无限，,0,00ijijiaax第四节第四节单纯形法计算步骤单纯形法计算步骤第一步：求第一步：求将将LPLP化为标准型，化为标准型，引入适当的引入适当的松驰变量、剩余变量和人工变量，使约束条件化松驰变量、剩余变量和人工变量，使约束条件化为等式，为等式，cjc1cmcjcnCB基bx1xmxjxnc1c2.cmx1x2.xmb1b2.bm10.000.1a1ja2j.amja1na2n.amn cj-zj00miininjacc1第二步：最优性检验第二步：最优性检验是是结束，写出最优解和目标函数最优值；结束，写出最优解和目标函数最优值；检查相应系数列检查相应系数列 0 0

9、？是是结束，该结束，该LPLP无界解。无界解。，转入下一步，转入下一步基变换。基变换。确定是停止迭代还是转入基变换？确定是停止迭代还是转入基变换？选择（最大）选择（最大）对应的系数列为对应的系数列为，主元列对应的非，主元列对应的非基变量基变量x xk k 为为最小比值最小比值对应的行为对应的行为，主元行对应的基变量，主元行对应的基变量x xl l为为。主元行和主元列的交叉元素主元行和主元列的交叉元素alklk称为主元素。称为主元素。0|maxjjjklklikikiabaab0|min完成一次迭代，得到新的基可行解和相完成一次迭代，得到新的基可行解和相应的目标函数值应的目标函数值该迭代过程直至

10、下列情况之一发生时停止该迭代过程直至下列情况之一发生时停止例题：使用单纯形法求解线性规划问题例题：使用单纯形法求解线性规划问题0,52426155.2max212121221xxxxxxxstxxZ解：化成标准形式052426155.0002max515214213254321xxxxxxxxxstxxxxxZ其约束条件系数矩阵的增广矩阵为其约束条件系数矩阵的增广矩阵为5100112401026151015054321bpppppp3,p4,p5构成单位矩阵，对应的基变量构成单位矩阵，对应的基变量x3,x4,x5,令非基变量令非基变量x1,x2=0,找到一个初始基可行解找到一个初始基可行解X=

11、(0,0,15,24,5)T,以此列出初始单纯形表以此列出初始单纯形表Cj21000CB基基bX1X2X3X4X50X315051000X424620100X5511001j=Cj-Zj=Cj-(C1a1j+C2a2j+Cmamj)210001=2-(00+06+01)=2;2=1-(05+02+01)=13=0-(01+00+01)=0;4=0-(00+01+01)=05=0-(00+00+01)=0 0|maxjjklklikikiabaab0|min4624)15,624,015min(0|minlklikikiabaab检验数检验数1和和2均大于均大于0，所以表中的基可行解不是最优解。

12、，所以表中的基可行解不是最优解。12，选择最大正检验数对应的系数列为主元列，选择最大正检验数对应的系数列为主元列，主元列对应的非基变量主元列对应的非基变量X1为换入变量；为换入变量；，Cj21000CB基基bX1X2X3X4X50X315051000X424620100X5511001j=Cj-Zj=Cj-(C1a1j+C2a2j+Cmamj)21000最小比值对应的行为主元行，主元行对应的基变量最小比值对应的行为主元行，主元行对应的基变量X4为换出变量。得到一个新的基为换出变量。得到一个新的基P3,P1,P5，列出新的单纯形表，列出新的单纯形表，继续计算。继续计算。x12142/601/60

13、014/601-1/601/30-1/30Cj21000CB基基bX1X2X3X4X50X315051002X1412/601/600X5104/60-1/61j=Cj-Zj=Cj-(C1a1j+C2a2j+Cmamj)01/30-1/302最大，最大，X2为进基变量；为进基变量；5.16/41)6/41,6/24,515min(0|minlklikikiabaabx21106/40-1/43/2017/201/4-1/20015/215/4-15/2000-1/4-1/2X5为出基变量。P2,P3,P1一个新的基,列出新的单纯形表，继续计算。Cj21000CB基基bX1X2X3X4X50X3

14、15/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2j=Cj-Zj=Cj-(C1a1j+C2a2j+Cmamj)000-1/4-1/21=02=03=04=0-(05/4+21/4-11/4)=-1/45=0-(-015/2-21/2+13/2)=-1/2所有的所有的0，基变量不含有人工变量，基变量不含有人工变量，所以可行解所以可行解X=(7/2,3/2,15/2,0,0)T为最优解，为最优解，代入目标函数得到代入目标函数得到Z=8.5小结小结1 1、线性规划单纯形法基本原理。、线性规划单纯形法基本原理。2 2、单纯形法计算步骤。、单纯形法计算步骤。作业1.3(1)1.4(1)