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

1、. - - . 可修编. . z. - - . 可修编. *理工学院最优化方法课程论文题目：线性规划的单纯形算法姓 名：专 业：统计学班 级：2011级1班学 号：完成日期：2014年6月27日*理工学院理学院二O一 四 年 六 月-. z.摘 要线性规划是运筹学中研究较早、开展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进展科学管理的一种数学方法。是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。为了得到线性目标函数的极值，我们有多重方法。本文采用单纯性算法求解线性规划问题，并通过Matlab软件编写程序进展求解。关键词：线性规划 单纯性算法 Matlab编程. - -.

2、 z.目 录 TOC o 1-5 h z u HYPERLINK l _Toc24242 一、 单纯性方法简介 PAGEREF _Toc24242 1 HYPERLINK l _Toc17343 1.1 单纯性方法提出 PAGEREF _Toc17343 1 HYPERLINK l _Toc31101 1.2单纯性方法的根本思想和步骤 PAGEREF _Toc31101 1 HYPERLINK l _Toc16127 1.2.1根本思想 PAGEREF _Toc16127 1 HYPERLINK l _Toc14838 1.2.2计算步骤 PAGEREF _Toc14838 1 HYPERLI

3、NK l _Toc10125 二、问题的提出与分析 PAGEREF _Toc10125 1 HYPERLINK l _Toc16512 2.1问题提出 PAGEREF _Toc16512 1 HYPERLINK l _Toc6386 2.2问题分析 PAGEREF _Toc6386 2 HYPERLINK l _Toc3182 三、程序设计 PAGEREF _Toc3182 2 HYPERLINK l _Toc18292 3.1算法设计 PAGEREF _Toc18292 2 HYPERLINK l _Toc29221 3.2算法框图 PAGEREF _Toc29221 3 HYPERLINK

4、 l _Toc18999 3.3程序编制 PAGEREF _Toc18999 4 HYPERLINK l _Toc14149 四、结果分析 PAGEREF _Toc14149 6 HYPERLINK l _Toc22331 4.1设计结果 PAGEREF _Toc22331 6 HYPERLINK l _Toc11558 4.2 进一步讨论和验证 PAGEREF _Toc11558 8 HYPERLINK l _Toc2159 五、完毕语 PAGEREF _Toc2159 8 HYPERLINK l _Toc9257 5.1设计的优缺点 PAGEREF _Toc9257 8 HYPERLINK

5、 l _Toc14895 5.2 收获与总结 PAGEREF _Toc14895 9 HYPERLINK l _Toc9903 参考文献 PAGEREF _Toc9903 10 HYPERLINK l _Toc22250 附录 PAGEREF _Toc22250 11-. z. - - . 可修编. 单纯性方法简介1.1 单纯性方法提出单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的,这是20世纪数学界最重大的成果之一。由于这一方法的有效性，几十年来一直在几乎所有的领域得到广泛应用。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸

6、集，其最优值如果存在必在该凸集的*顶点处到达。顶点所对应的可行解称为根本可行解。1.2单纯性方法的根本思想和步骤1.2.1根本思想单纯形法的根本思想是：先找出一个根本可行解，对它进展鉴别，看是否是最优解；假设不是，则按照一定法则转换到另一改良的根本可行解，再鉴别；假设仍不是，则再转换，按此重复进展。因根本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。1.2.2计算步骤 1、对于一般的的线性规划，将其化为标准型； 2、求出初始根本可行解； 3、先检验其最优性； 4、如果不是最优的，则从取负值的非基变量中选取一个最负确定为入基变量； 5、选好入基变量后，再在

7、基变量中选取一个出基变量； 6、选好入基变量和出基变量后，进展高斯消去，得到新的可行解； 7、重复以上过程，直至找到最优解。、二、问题的提出与分析2.1问题提出本文运用单纯性算法求解以下问题：Ma* s.t 并编写MATLAB程序求解。2.2问题分析在用单纯性算法解决现行规划问题时，我们通常考察标准形现行规划问题，其标准形如下：现在将本文所讨论的线性规划化为标准线性规划的形式：Min S.t. 其中 A=2 3 0 1 0 0 0 2 4 0 1 0 3 2 5 0 0 1，三、程序设计3.1算法设计解，求得，令，计算目标函数值,以记的第i个分量；计算单纯性乘子w，,得到,对于非基变量，计算判

8、别系数，令，R为非基变量集合，假设判别系数，则得到一个最根本可行解，运算完毕；否则，转到下一步解，得到；假设，即的每一个分量均非正数，则停顿计算，问题不存在有限最优解，否则，进展步骤4;确定下标r，使，为出基变量，为入基变量，用替换，得到新的基矩阵B，返回步骤1。3.2算法框图开场初始可行解令计算单纯形乘子，计算判别数非基变量令是得到最优解解方程，得到。否是不存在有限最优解确定下标，是否为进基变量，用替换，得到新的基矩阵3.3程序编制A=input(A=);b=input(b=);c=input(c=);format ratm,n=size(A);E=1:m;E=E; F=n-m+1:n;F=

9、F;D=E,F; *=zeros(1,n); if(nm) fprintf(不符合要求需引入松弛变量) flag=0;else flag=1; B=A(:,n-m+1:n); cB=c(n-m+1:n); while flag w=cB/B; panbieshu=w*A-c z,k=ma*(panbieshu); fprintf(b./(BA(:,%d)为,k); b./(BA(:,k)if(z0.000000001) flag=0; fprintf( 已找到最优解!n); *B=(Bb); f=cB*B; for i=1:n mark=0;for j=1:mif (D(j,2)=i) mar

10、k=1; *(i)=*B(D(j,1); endendif mark=0 *(i)=0; endend fprintf(基向量为:); * fprintf(目标函数值为:) ; felseif(BA(:,k)0) & (b1(i)/(A(i,k)+eps)temp ) temp=b1(i)/A(i,k); r=i;endend fprintf(*(%d)进基，*(%d)退基n,k,D(r,2); B(:,r)=A(:,k); cB(r)=c(k); D(r,2)=k; endendendend四、结果分析4.1设计结果在命令窗口中输入： A=2,3,0,1,0,0;0,2,4,0,1,0;3,

11、2,5,0,0,1 b=1200,800,2000得到如下结果:我们可以看到，程序经过4次换基迭代，得到目标函数的最优值为-2600，即目标函数的最小值为-2600。从而，原问题的最大值为2600。4.2 进一步讨论和验证 对于MATLAB程序的正确性与软件运行的可行性。由于计算量并不是很大，我们通过单纯性表进展手工计算。经过几次换基迭代，我们选取的入基变量和出基变量与以上软件运行过程得到的结果完全一样。由此，我们可以认定目标函数的最小值为-2600，即原问题的最大值为2600。五、完毕语5.1设计的优缺点设计优点：设计的程序是根据课本的步骤编写的；程序的编制能得到正确结果；编制的程序得到的结

12、果中具体表达每一步的出基变量与入基变量，清晰明了；设计缺点：不能直观的反响迭代步数，如假设迭代次数过多，则想要了解迭代步数则比拟麻烦；不能给出完整的单纯性表。5.2 收获与总结 通过本次课程论文设计，让我对单纯性法有了进一步的了解，明确了它的具体思想理论，算法步骤。此外，通过此次课程设计，初次接触了MATLAB软件，让我对MATLAB软件有了初步的了解，此次论文的完成，主要是通过根据算法设计，编制MATLAB程序，通过MATLAB软件对模型求解。因此，此次设计的最大问题在于怎样设计算法程序，但这对于我们来说难度还是比拟大，所以，此次的单纯性算法程序直接利用网上给出的算法程序进展设计。但网上的很多程序也存在很多问题，需要在