最优化方法课程论文.docx
四川理工学院最优化方法课程论文题目:线性规划的单纯形算法姓名：专业：统计学班级：2011级1班学号：完成日期：2014年6月27日四川理工学院理学院二0一四年六月摘要线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。为了得到线性目标函数的极值，我们有多重方法。本文采用单纯性算法求解线性规划问题，并通过Mat1.ab软件编写程序进行求解。关键词：线性规划单纯性算法MatIab编程一、单纯性方法简介11.1单纯性方法提出11.2单纯性方法的基本思想和步骤11.2. 1基本思想11.3. 2计算步骤1二、问题的提出与分析11. 1问题提出12. 2问题分析2三、程序设计22.1 算法设计23. 2算法框图33. 3程序编制4四、结果分析63.1 设计结果64. 2进一步讨论和验证8五、结束语85. 1设计的优缺点85.2收获与总结10参考文献11附录错误!未定义书签。一、单纯性方法简介1.1单纯性方法提出单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的,这是20世纪数学界最重大的成果之一。由于这一方法的有效性，几十年来一直在几乎所有的领域得到广泛应用。它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。1. 2单纯性方法的基本思想和步骤1.2. 1基本思想单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解;若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。1.2.2计算步骤1、对于一般的的线性规划，将其化为标准型；2、求出初始基本可行解；3、先检验其最优性；4、如果不是最优的，则从取负值的非基变量中选取一个最负确定为入基变量；5、选好入基变量后，再在基变量中选取一个出基变量；6、选好入基变量和出基变量后，进行高斯消去，得到新的可行解；7、重复以上过程，直至找到最优解。二、问题的提出与分析2. 1问题提出本文运用单纯性算法求解下列问题:MaxZ= 3x1 + 5 X2 + 4 X3S.t2匹+3x712002x2+4x38003x+2元+5Xo2000x1,x2,x30并编写MAT1.AB程序求解。2.2问题分析在用单纯性算法解决现行规划问题时.，我们通常考察标准形现行规划问题，其标准形如下：min/(x)=C1Xs.t.Ax=b,xO现在将本文所讨论的线性规划化为标准线性规划的形式：Miny=-z=-31-5%4马S.t.2xi+3x2+x4=12002x2+4x3+x5=8003x1+2x2+5x3+x6=2000其中c=-3,-5,-4A=230100024010325001Z?=1200,800,2000XB4,5,6,XN=1.,2,3三、程序设计3.1 算法设计1、解BXB=人，求得XB=B-Ib,号XN=O，计算目标函数值=Q/,以"(i=1,2,m)记5%的第i个分量；2、计算单纯性乘子W,WB=CB,得到W=C“5一：对于非基变量，计算判别系数6=ZCi=CBB-'pc”令巴=嗯xz,-q,R为非基变量集合，若判别系数%0,则得到一个最基本可行解，运算结束；否则，转到下一步3、解Bak=Pk,得到W=BTPZ若%T0,即4.的每一个分量均非正数，则停止计算,问题不存在有限最优解，否则，进行步骤4；4、确定下标r,使，-=min2火0】为出基变量，为入基变量，用0替换PBJ得到新的基输阵B,返骤1。3.2算法框图为进基变量，用Pa.替换PBJ得到新的基矩阵B3.3程序编制A=inputCA=');b=input(,b=');c=input(,C-');formatratm,n=size(A);E=I:m;E=E'F=n-m+1.nF=F,;D=E,F;X=zeros(1,n);if(n<m)fprintf(,不符合要求需引入松弛变量')fIag=O;e1.sef1.ag=1.;B=A(:,n-m+1:n);cB=c(n-m+1.:n);whi1.ef1.agw=cBB;panbieshu=w*A-cz,k=max(panbieshu);fprintf(,b,./(BA(:,%d)为'，k);b,.(BA(z,k)if(z<O.000000001)f1.ag=0;fprintf(,己找到最优解！n');XB=(Bb')'f=cB*xB,;fori=1.:nmark=0;forj=1.:mif(D(j,2)=i)mark=1.;X(i)=xB(D(j,1);endendifmark=0X=0；endendfprintf('基向量为:')；Xfprintf('目标函数值为:')；fe1.seif(BA(:,k)<=0)f1.ag=O;fprintf(>n此问题不存在最优解!n');e1.seb1.=Bb,;temp=inf;fori=1.:mif(A(i,k)>0)&&(b1.(i)/(A(i,k)+eps)<tcmp)temp=b1.(i)A(i,k);r=i;endendfprintf(,x(%d)进基，x(%d)退基n,k,D(r,2);B(:,r)=A(:,k)；cB(r)=c(k);D(rt2)=k;endendendend四、结果分析4.1设计结果在命令窗口中输入：A=2,3,0,1,0,0;0,2,4,0,1,0;3,2,5,0,0,1b=1200,800,2000c=-3,-5,-4,0,0,0得到如下结果：panbieshu=354000b,.(BA(!j2)ans=4004001000x(2)进基，x(4)退基panbieshu-1/3O4b'./(BA(:,3)为ans=1/0200400I、x(3)进基，x(5)退基panbieshu=100ans=1800-2400600-5/300-1-10x(1.)进基，x(2)退基Panbieshu=O-3/2O-3/2-1Ob'(BA",1.)为ans=12001/01/0已找到最优解！基向里为：X=600020000-800目标函数值为：f=-2600我们可以看到，程序经过4次换基迭代，得到目标函数的最优值为-2600,即目标函数的最小值为-2600。从而，原问题的最大值为2600。4. 2进一步讨论和验证对于MAT1.AB程序的正确性与软件运行的可行性。由于计算量并不是很大，我们通过单纯性表进行手工计算。经过几次换基迭代，我们选取的入基变量和出基变量与以上软件运行过程得到的结果完全相同。由此，我们可以认定目标函数的最小值为-2600,即原问题的最大值为2600。五、结束语4.1 设计的优缺点设计优点：1、设计的程序是根据课本的步骤编写的；2、程序的编制能得到正确结果；3、编制的程序得到的结果中具体体现每一步的出基变量与入基变量，清晰明了；设计缺点：1、不能直观的反应迭代步数，如若迭代次数过多，则想要了解迭代步数则比较麻烦;2、不能给出完整的单纯性表。5. 2收获与总结通过本次课程论文设计，让我对单纯性法有了进一步的了解，明确了它的具体思想理论，算法步骤。此外，通过此次课程设计，初次接触了MAT1.AB软件，让我对MAT1.AB软件有了初步的了解,此次论文的完成，主要是通过根据算法设计，编制MAT1.AB程序，通过MAT1.AB软件对模型求解。因此，此次设计的最大问题在于怎样设计算法程序，但这对于我们来说难度还是比较大，所以，此次的单纯性算法程序直接利用网上给出的算法程序进行设计。但网上的很多程序也存在很多问题，需要在一次一次的错误中不断的更正问题，直到最后得到模型正确的结果。由于对MAT1.AB软件的不了解，对于程序设计的优缺点不是很明白。而对于以后，还是希望能多学习一下软件的知识，能够深入了解一下软件的程序设计以及问题分析。参考文献U精通MAT1.AB最优化计算（第二版）龚纯等2
