运筹学与最优化MATLAB编程课程报告

1、基于MATLAB编程语言采用大M法求 解线性规划问题线性规划单纯形法 大M法 MATLAB编程语言1引言伴随着计算机技术的高速发展，最优化理论与方法取得了巨大的 进步，并日益受到重视，而解决实际最优化问题的软件也得到了飞速 发展，其中MATLAB这个强大的计算平台，既可以利用MATLAB优化工 具箱(OptimizationToolbox)中的函数，又可以通过对算法编程实 现相应的最优化计算，是目前最流行的计算软件之一。摘要本程序是采用运筹学中的求解线性规划的大M法来解现实问题， 并采用MATLAB编程语言。本文通过投资问题的实例分析了投资项 日和各项目收益率确定的情况下，并结合公司实际，如何

2、合理的分配 利用，最终确定使得该公司收益最大的投资方案。说明了线性规划在 现代企业投资管理中的应用，对企业的投资管理决策提供了支持。但 是本程序只实现了线性规划的部分功能，所以有待进一步完善。算法说明3.1算法原理单纯形法的基本思路是将可行域中某个基可行解转换到一个新 的可行解，同时使得目标函数值有所改进。而大M法则是通过将人 工变量加入到原约束方程组中作为虚拟变量，并使得这些虚拟变量从基变量中被置换出来。为此只需假定人工变量在日标函数中的系数为M（M0,是个充分大的数），这样，对于求极大值问题，只要在基本可行解中，还有人工变量是基变量，且取值不为0，则日标函数就不可能达到最大值；对于极小值问

3、题而言，人工变量在日标函数中的系数取+M，这种方法称为大M法。3.2算法步骤用大M法求解下列线性规划问题minf=cxs.t.=的步骤如下:r Ax=b=01.首先将线性规划问题minf=cx，s.t.=转化为如下问题:Minf=cx+MeTy,s.t.=r Ax=0Ax+y=02.确定初始基变量矩阵B，求解方程令xN=0计算f=cBxB其中xB、xN分别代表基变量和非基变量的值，cB 表示基变量在日标函数中的系数；求解方程wB=CB,对于所有非基变量计算判别数Z.-C.wP.-C.，其中 Pj为非基变量在约束系数距震中相对应的列，令Zk-Ck=max（Z.-C.）, 如果Zk-Ck0，将目标

4、函数改写为如式2），就可按原单纯形法的步骤进行迭代。6.2本程序设计缺点本程序设计时只涉及了求极小值的方法，所以在求解极大值问题 时需要先将模型转化为求最小值的模型；而且在用大M法求解线性 规划时也需先把一般形式化为标准形式；在计算时要给M赋予一个 适当的定值（特别是在编程时），但究竟应该取多大，事先无法估计， 过大的话容易引起计算误差。6.3算法需改进之处应该设计一种既能求解极大值又能求解极小值的算法，而不需来回转 换，本程序的设计也未考虑当原问题无界时这种情况，所以有待进一 止土 步兀善。6.4算法对比效果算法改进后，会使得本程序设计的功能更强大，更完善，大大简化繁 琐的转换过程。7.总结

5、与心得体会通过对本次课程报告的编写，大大加强了自己的实践动手能力与 MATLAB编程能力，实现了理论与实际的紧密结合，同时也提高了 自己解决实际问题的能力，为以后的编程打下了基础。由于接触MATLAB编程语言的时间还比较短，所以对它掌握的 还不是特别的熟练，以至于在算法的编程实现过程中会出现种种问 题。本次最大的收获就是学会了 MATLAB的基本操作及基本编程，遇到问题首先要自己认真思考，提高自己的思维创新能力，需要更加 的努力才能真正的把MATLAB学好，学会理论联系实际。参考文献运筹学的原理和方法(第二版)/邓成梁 主编.一武汉：华中科技大学出版社，2002年1月MATLAB语言高级编程/

6、张德丰等编著，一北京：机械工业出版社，2010年1月精通MATLAB最优化计算/龚纯，王正林编著，一北京：电子工业 出版社，2009年4月附件(程序代码)function x,minf=CmpSimpleMthd(A,c,b,basevector)%约束矩阵:A%日标函数系数向量：c%约束右端向量：b%初始基向量：basevector%日标函数取最小值时的自变量值：x%日标函数的最小值：minf%sz=size(A);nVia=sz(2);n=sz(1);xx=1:nVia;nobase=zeros(1,1); m=1;if c=0vr二find(c=0,1, last);rgv二inv(A(

7、:,(nVia-n+1):nVia)*b;if rgv=0 x=zeros(1,vr);minf=0;elsedisp(the best answer do not exist!);x=nan;minf=nan;return;endendfor i=1:nViaif (isempty(find(basevector=xx(i),1)% 获取非基变量下标 nobase(m)=i;m=m+1;elseendend bCon=1;M=0;while bConnB=A(:,nobase);%非基变量矩阵ncb=c(nobase);%非基变量系数B=A(:,basevector);% 基变量矩阵cb=c

8、(basevector);% 基变量系数xb=inv(B)*b;f=cb*xb;w=cb*inv(B);for i=1:length(nobase)% 判别sigma二w*nB(:,i)-ncb(i);endmaxs,ind=max(sigma);%ind 为进基变量下标if maxs=0minf=cb*xb;vr二find(c=0,1, last);for i=1:vrele=find(basevector=i,1);if(isempty(ele)x(i)=0;elsex(i)=xb(ele);endendbCon=0;elsey=inv(B)*A(:,nobase(ind);if y0bz=xb(j)/y(j);if bzminbminb=bz;chagB=j;endendtmp二basevector(chagB);%更新基矩阵和非基矩阵 basevector(ch