单纯形法的matlab实现

1大连民族学院数学实验报告课程：最优化方法实验题目:单纯形法的matlab实现系别：理学院专业：信息与计算科学姓名：班级：信息102班指导教师：葛仁东完成学期：2013年9月2日2实验目的：1.通过本次实验，进一步的了解单纯形法的基本原理；2.掌握matlab的基本操作，学习matlab循环语句的应用，学习编写matlab程序，提高编程能力和技巧；3.学习用已学的知识解决实际问题，将理论应用于实际。实验内容：（问题、数学模型、要求、关键词）问题：某工厂要制作100套钢筋架，每套需要2.9m、2.1m和1.5m的钢筋各一根，这些钢筋均长7.4m的原材料切割而成，问如何切割原材料才能使原材料的使用最节省？数学模型：线性规划的单纯形法要求：按问题解出优质的方案，基于单纯形法的原理，利用matlab编程进行求解。关键字：单纯形法线性规划matlab软件实验方法和步骤（包括数值公式、算法步骤、程序）：考察标准形式的线性规划问题：min()..,0TfxCxstAxbx设()kxF为一个基本可行解，单纯形方法首先检验它的最优性。如果它不是最3优的，确定与该顶点相连的一条使目标函数下降的边；接下来确定沿这个边移动多远可以到达另一个更优的相邻点，也就是得出一个新的基本可行解。算法步骤：步骤1：给定一个初始基本可行解，记迭代次数1k；步骤2：计算单纯形乘子()TkkkByBC和简约价值系数向量()()ˆkkTNNkkCCNy；步骤3：最优性检验，计算()()ˆˆmin{}kkpjkCCjN，如果()ˆ0kpC，则()kx为最优解，停止迭代；否则有0px，选px为入基变量；步骤4：确定出基变量，计算()1ˆkpkpaBa，如果对所有kjB，有()ˆ0kjpa，则问题无有界的最优解，停止迭代；否则确定出基变量指标()()()()()ˆmin{0,}ˆˆkkqjkjpkkkqpjpbbajBaa；步骤5：交换kB的列qa与kN的列pa得到新的基矩阵+1kB和+1kN，计算新的基本可行解(1)kx,置:1kk后转步骤2；在上述算法中，当存在不止一个简约价值系数()ˆ0kjC时，选取最负的()ˆkjC的指标为p，并以px作为入基变量。Matlab计算程序：Function[x,f]=zuiyouhua(A,b,c)Size(A)=[m,n];i=n+1:n+m;N=1:n;B=eye(m,m);xb=b’;xn=zeros(m,1);f1=0;w=zeros(1,m);z=-c;flag=1;while(1)[a,k]=max(z);4Ifa=0flag=0;breakelsey=inv(B)*A(:,k)ify=0flag=0;fprintf(‘不存在最优解’)breakendt=find(y0);[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=cb*xbz=cb*inv(B)*A-C;endend实验数据和分析：根据题意，可以列出以下8种可能的切割方案，其目标是使总剩余的废料最小。设128,xxx分别代表采用切割方案1~8的套数，()fx表示总剩余的废料，则上述问题的线性规划如下：12345678min()0.10.30.901.10.20.81.4fxxxxxxxxx123423567134678123456782100232100..3234100,,,,,,,0xxxxxxxxxstxxxxxxxxxxxxxx在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];5b=[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=10500300000f=-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程序求解线性规划问题，在生活中有不少问题都是线性规划问题。例如本次实验中的钢材下料问题，学习用已学习的知识解决实际问题是我们的最终目标。