单纯形法的matlab实现.doc

《单纯形法的matlab实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、大连民族学院数学实验报告课程：最优化方法实验题目:单纯形法的matlab实现系别：理学院专业：信息与计算科学姓名：班级：信息102班指导教师：葛仁东完成学期：2013年9月2日实验目的：1.通过本次实验，进一步的了解单纯形法的基本原理；2.掌握matlab的基本操作，学习matlab循环语句的应用，学习编写matlab程序，提高编程能力和技巧；3.学习用已学的知识解决实际问题，将理论应用于实际。实验内容：（问题、数学模型、要求、关键词）问题：某工厂要制作100套钢筋架，每套需要2.9m、2.1m和1.5m的钢筋各一根，这些钢筋均

2、长7.4m的原材料切割而成，问如何切割原材料才能使原材料的使用最节省？数学模型：线性规划的单纯形法要求：按问题解出优质的方案，基于单纯形法的原理，利用matlab编程进行求解。关键字：单纯形法线性规划matlab软件实验方法和步骤（包括数值公式、算法步骤、程序）：考察标准形式的线性规划问题：设为一个基本可行解，单纯形方法首先检验它的最优性。如果它不是最优的，确定与该顶点相连的一条使目标函数下降的边；接下来确定沿这个边移动多远可以到达另一个更优的相邻点，也就是得出一个新的基本可行解。算法步骤：步骤1：给定一个初始基本可行解，记迭代

3、次数；步骤2：计算单纯形乘子和简约价值系数向量；步骤3：最优性检验，计算，如果，则为最优解，停止迭代；否则有，选为入基变量；步骤4：确定出基变量，计算，如果对所有，有，则问题无有界的最优解，停止迭代；否则确定出基变量指标；步骤5：交换的列与的列得到新的基矩阵和，计算新的基本可行解,置后转步骤2；在上述算法中，当存在不止一个简约价值系数时，选取最负的的指标为，并以作为入基变量。Matlab计算程序：Function[x,f]=zuiyouhua(A,b,c)Size(A)=[m,n];i=n+1:n+m;N=1:n;B=eye(m

4、,m);xb=b’;xn=zeros(m,1);f1=0;w=zeros(1,m);z=-c;flag=1;while(1)[a,k]=max(z);Ifa<=0flag=0;breakelsey=inv(B)*A(:,k)ify<=0flag=0;fprintf(‘不存在最优解’)breakendt=find(y>0);[a,rl]=min(bl(t)/y(t))r=t(rl);i(:,k)=kB(:,k)=A(:,k);cb=C(:,i);xb=inv(B)*b;b0=xb;x=zeros(1,n+m)x(:,i)=xb’f

5、=cb*xbz=cb*inv(B)*A-C;endend实验数据和分析：根据题意，可以列出以下8种可能的切割方案，其目标是使总剩余的废料最小。设分别代表采用切割方案的套数，表示总剩余的废料，则上述问题的线性规划如下：在matlab的输入区域输入：A=[2,1,1,1,0,0,0,0;0,2,1,0,3,2,1,0;1,0,1,3,0,2,3,4];b=[100,100,100]’;c=[0.1,0.3,0.9,0,1.1,0.2,0.8,1.4];[x,f]=zuiyouhua(A,b,c)Matlab输出内容：x=105003

6、00000f=-16结果分析：可以看出只需要90根原料，其中，方案1需要10根，方案2需要50根，方案4需要30根，即可达到要求，此时总剩余废料最小，为16m。附：方案2.9m2.1m1.5m合计余料12017.30.121207.10.331116.50.941037.4050306.31.160227.20.270136.60.8800461.4实验的启示：通过本次实验加深了我对单纯形法的进一步理解，利用matlab程序求解线性规划问题，在生活中有不少问题都是线性规划问题。例如本次实验中的钢材下料问题，学习用已学习的知识解决

7、实际问题是我们的最终目标。