(自由模板)最优化方法课程论文

四川理工学院《最优化方法》课程论文题目：线性规划的单纯形算法姓名：专业：统计学班级：2011级1班学号：完成日期：2014年6月27日四川理工学院理学院二O一四年六月摘要线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。为了得到线性目标函数的极值，我们有多重方法。本文采用单纯性算法求解线性规划问题，并通过Matlab软件编写程序进行求解。关键词：线性规划单纯性算法Matlab编程目录一、单纯性方法简介..............................................................................................................11.1单纯性方法提出..............................................................................................................................11.2单纯性方法的基本思想和步骤...............................................................................................11.2.1基本思想...............................................................................................................................11.2.2计算步骤...............................................................................................................................1二、问题的提出与分析............................................................................................................12.1问题提出..........................................................................................................................................12.2问题分析..........................................................................................................................................2三、程序设计............................................................................................................................23.1算法设计..........................................................................................................................................23.2算法框图..........................................................................................................................................33.3程序编制..........................................................................................................................................4四、结果分析............................................................................................................................64.1设计结果..........................................................................................................................................64.2进一步讨论和验证..........................................................................................................................8五、结束语................................................................................................................................85.1设计的优缺点.....................................................................................................................85.2收获与总结........................................................................................................................9参考文献..................................................................................................................................10附录.........................................................................................................错误!未定义书签。四川理工学院《最优化方法》课程论文1一、单纯性方法简介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问题提出本文运用单纯性算法求解下列问题：Max321453xxxzs.t12003221xx8004232xx2000523321xxx0,,321xxx四川理工学院《最优化方法》课程论文2并编写MATLAB程序求解。2.2问题分析在用单纯性算法解决现行规划问题时，我们通常考察标准形现行规划问题，其标准形如下：xcxfT)(min0,..xbAxts现在将本文所讨论的线性规划化为标准线性规划的形式：Min321453xxxzyS.t.120032421xxx80042532xxx20005236321xxxx其中4,5,3cA=[230100024010325001]2000,800,1200b6,5,4Bx，3,2,1Nx三、程序设计3.1算法设计1、解bBxB，求得bBxB1，令0Nx，计算目标函数值BBxcf,以)m,2,1(ibi记bB1的第i个分量；2、计算单纯性乘子w，BCwB,得到1BCwB,对于非基变量，计算判别系数iiBiiicpBccz1，令iiRikczmax，R为非基变量集合，若判别系数0k，则得到一个最基本可行解，运算结束；否则，转到下一步3、解kkpBa，得到kkpBa1；若0ka，即ka的每一个分量均非正数，则停止计算，问题不存在有限最优解，否则，进行步骤4;四川理工学院《最优化方法》课程论文34、确定下标r，使0minrkrkirkraabab，rBx为出基变量，kx为入基变量，用kp替换rBp，得到新的基矩阵B，返回步骤1。3.2算法框图是否是否开始初始可行解B令1,0,BNBBxBbbxfcx计算单纯形乘子1BwcB，计算判别数,ijjwpcjR（非基变量）令max{,}kjjR0?k得到最优解解方程kkpBa，得到kkpBa1。?0ka不存在有限最优解确定下标r，是0minrkrkirkraabab四川理工学院《最优化方法》课程论文43.3程序编制A=input('A=');b=input('b=');c=input('c=');formatrat[m,n]=size(A);E=1:m;E=E';F=n-m+1:n;F=F';D=[E,F];X=zeros(1,n);if(nm)fprintf('不符合要求需引入松弛变量')flag=0;elseflag=1;B=A(:,n-m+1:n);cB=c(n-m+1:n);whileflagw=cB/B;panbieshu=w*A-c[z,k]=max(panbieshu);fprintf('b''./(B\\A(:,%d))为',k);b'./(B\A(:,k))if(z0.000000001)flag=0;为进基变量，用kxkp替换rBp，得到新的基矩阵B四川理工学院《最优化方法》课程论文5fprintf('已找到最优解!\n');xB=(B\b')';f=cB*xB';fori=1:nmark=0;forj=1:mif(D(j,2)==i)mark=1;X(i)=xB(D(j,1));endendifmark==0X(i)=0;endendfprintf('基向量为:');Xfprintf('目标函数值为:');felseif(B\A(:,k)=0)flag=0;fprintf('\n此问题不存在最优解!\n');elseb1=B\b';temp=inf;fori=1:mif((A(i,k)0)&&(