化实验报告(单纯形法的matlab程序lingo程序).doc

南昌航空大学数学与信息科学学院实验报告 实验一：线性规划单纯形算法一、实验目的通过实验熟悉单纯形法的原理，掌握Matlab循环语句的应用,提高编程的能力和技巧。二、实验用仪器设备、器材或软件环境Windows Xp操作系统 ,Matlab6.5，计算机三、算法 对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始基本可行解。设初始基为B,然后执行如下步骤：(1).解,求得，(2).计算单纯形乘子, ,得到,对于非基变量，计算判别数,令 ,R为非基变量集合若判别数 ,则得到一个最优基本可行解，运算结束；否则，转到下一步(3).解,得到；若,即的每个分量均非正数，则停止计算，问题不存在有限最优解，否则，进行步骤(4).(4).确定下标r,使为离基变量。为进基变量，用替换，得到新的基矩阵，返回步骤（1）。对于极大化问题，可以给出完全类似的步骤，只是确定进基变量的准则不同。对于极大化问题，应令 四、计算框图 开始 初始可行解令计算单纯形乘子，计算判别数（非基变量）令是得到最优解解方程，得到。否是不存在有限最优解确定下标，是否为进基变量，用替换，得到新的基矩阵五、计算程序function x,f=zuiyouhua(A,b,c)size(A)=m,n;i=n+1:n+m;%基变量集合,后面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);%x(k)为进基变量; if a=0 flag=0; break else y=inv(B)*A(:,k) if y0); a,r1=min(b1(t)./y(t) r=t(r1); %基变量中第r个变量为退基变量; i(:,r)=k B(:,r)=A(:,k);%换基，即将原基中第个变量换成第个变量; cb=c(:,i);%新的价值系数; xb=inv(B)*b; b0=xb; x=zeros(1,n+m) x(:,i)=xb f=cb*xb z=cb*inv(B)*A-c;%可用z=cb*(BA)-c,判别数. end end六、数值实验及结果分析求解线性规划问题:在工作区输入:A=3,3,1,0;-4,-4,0,1;2,-1,0,0;b=30,16,12;c=-3,1,0,0; x,f=zuiyouhua(A,b,c)x = 7.3333 2.6667 0 0 0 56.0000 0f = -19.3333检验结果正确七、心得体会通过这次试验，使我对单纯形法的计算有了更进一步的了解。但是在编程过程中由于对matlab不是很熟悉还是遇到了很多麻烦，所以我觉得老师在让我们编程的时候不能只是简单的介绍一下算法，更要着重说明一下软件的使用方法。这样我们在编程的时候就能更加的得心应手。本次完全仿照老师给的程序，没有能够形成自己的东西。自己编程的能力还是很差的，对于这种已经给出算法的程序也不能正确的编写出来。所以在今后要加强这方面的学习。 实验二：Lingo求解动态规划问题一、实验目的 通过本实验熟悉动态规划的原理，了解动态规划的应用，并能利用数学软件（Lingo）求解动态规划模型。二、问题重述某公司打算向他的营业区增设4个销售点，各区赚取的利润与增设的销售点个数有关，其数据为：销售店增加数第一区利润（万元）第二区利润（万元）第三区利润（万元）第四区利润（万元）01601902002501310225298308254144539948736005176016554705632721674试求各区应分配几个增设的销售书店，才能使利润最大？其值是多少？三、数学模型 设为第区增设销售点的个数，为增设第个点所得到的盈利。故问题模型为：四、计算编程 model:sets:quyu/1.4/;zl/0.4/;lirun(quyu,zl):g,c;endsetsdata:g=160 310 541 600 705, 190 225 445 517 632, 200 298 399 601 721, 250 308 487 655 674;enddatamax=sum(lirun(i,j):g(i,j)*c(i,j);for(quyu(i):sum(lirun(i,j):c(i,j)=1);for(lirun:bin(c);sum(lirun(i,j):(j-1)*c(i,j)=4;End五、计算结果 Global optimal solution found. Objective value: 1436.000 Objective bound: 1436.000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost G( 1, 1) 160.0000 0.000000 G( 1, 2) 310.0000 0.000000 G( 1, 3) 541.0000 0.000000 G( 1, 4) 600.0000 0.000000 G( 1, 5) 705.0000 0.000000 G( 2, 1) 190.0000 0.000000 G( 2, 2) 225.0000 0.000000 G( 2, 3) 445.0000 0.000000 G( 2, 4) 517.0000 0.000000 G( 2, 5) 632.0000 0.000000 G( 3, 1) 200.0000 0.000000 G( 3, 2) 298.0000 0.000000 G( 3, 3) 399.0000 0.000000 G( 3, 4) 601.0000 0.000000 G( 3, 5) 721.0000 0.000000 G( 4, 1) 250.0000 0.000000 G( 4, 2) 308.0000 0.000000 G( 4, 3) 487.0000 0.000000 G( 4, 4) 655.0000 0.000000 G( 4, 5) 674.0000 0.000000 C( 1, 1) 0.000000 -160.0000 C( 1, 2) 0.000000 -310.0000 C( 1, 3) 1.000000 -541.0000 C( 1, 4) 0.000000 -600.0000 C( 1, 5) 0.000000 -705.0000 C( 2, 1) 0.000000 -190.0000 C( 2, 2) 0.000000 -225.0000 C( 2, 3) 1.000000 -445.0000 C( 2, 4) 0.000000 -517.0000 C( 2, 5) 0.000000 -632.0000 C( 3, 1) 1.000000 -200.0000 C( 3, 2) 0.000000 -298.0000六、分析、检验和结论 结果中Variable 列对应的，表示第区，表示增加个销售点，Value列对应的0.000000表示不增加销售点，1.000000表示增加销售点。例如 C( 1, 3) 1.000000表示第一区增加两个销售点。表示第行第列对应的值。从结果中我们知道最优解是第一区和第二区分别增加2个销售点，第三区和第四区增加0个销售点此时盈利1436为最优值。经过检验结果正确。七、心得体会 通过实验我熟悉了Lingo的使用方法，学会了用Lingo编写计算程序。同时也掌握了分配问题的算法。由于之前没有接触过Lingo软件，老师也没有系统的讲述Lingo的使用规则，所以我通过老师给的例题，依葫芦画瓢的写出了本问题的程序。但是对实质性的东西还不是很了解，