《运筹学与最优化matlab编程》由会员分享，可在线阅读，更多相关《运筹学与最优化matlab编程（10页珍藏版）》请在金锄头文库上搜索。
1、运筹学与最优化MATLAB编程实验报告 院系： 专业： 姓名： 学号： 指导老师： 完成日期： 割平面法求解整数规划问题一、 引言： 通过对MATLAB实践设计的学习，学会使用MATLAB解决现实生活中的问题。该设计是在MATLAB程序设计语言的基础上，对实际问题建立数学模型并设计程序，使用割平面法解决一个整数规划问题。经实验，该算法可成功运行并求解出最优整数解。二、 算法说明：割平面法有许多种类型，本次设计的原理是依据Gomory的割平面法。Gomory割平面法首先求解非整数约束的线性规划，再选择一个不是整数的基变量，定义新的约束，增加到原来的约束中，新的约束缩小了可行域，但是保留了原问题的
2、全部整数可行解。算法具体设计步骤如下：1、首先，求解原整数规划对应的线性规划，设最优解为x*。2、如果最优解的分量均为整数，则x*为原整数规划的最优解；否则任选一个x*中不为整数的分量，设其对应的基变量为xp，定义包含这个基变量的切割约束方程，其中xp为非基变量。3、令，其中为高斯函数符号，表示不大于某数的最大整数。将切割约束方程变换为，由于01，0 A=0.01 0.01 0.01 0.03 0.03 0.03 1 0 0 0;0.02 0 0 0.05 0 0 0 1 0 0;0 0.02 0 0 0.05 0 0 0 1 0;0 0 0.03 0 0 0.08 0 0 0 1; c=-2
3、0;-14;-16;-36;-32;-30; b=850;700;100;900; intx,intf=DividePlane(A,c,b,7 8 9 10)3、实验结果及分析：intx = 35000 5000 30000 0 0 0intf = -1250000实验结果求出的目标函数值是化为标准型的最小值，则转化为原问题的目标函数值应取相反数，所以从实验结果可知：生产各种产品的产量分别应为为，生产A 35000、生产B 5000、生产C 30000、生产D 、E、F均为0，此时的季度产值为最大即1250000元。该结果是可信的，故通过该实例说明该程序能够运用于实际，用来解决实际生活中求解整
4、数规划的问题。五、 结束语：Matlab是个很强大的软件，提供了大量的函数来处理各种数学、工程、运筹等的问题，并且含有处理二维、三维图形的功能，使用matlab能够解决许多实际生活中的问题。通过这个学期的学习，仅是了解了matlab的部分函数功能和简单的GUI界面设计，掌握了一些基本的程序编写技能，同时，在老师的指导下简单了解了使用LinGo和Excel解决线性和非线性规划问题的求解方法，收获相当丰富，同时认识到要学好matlab仍然需要一个长期的过程。六、 参考文献：1 龚纯，王正林.精通MATLAB最优化计算.北京：电子工业出版社，20092吴祈宗，郑志勇，邓伟等.运筹学与最优化MATLA
5、B编程.北京：机械工业出版社，20093邓成梁.运筹学的原理和方法(第二版).武汉：华中科技大学出版社，2002七、 附录：function intx,intf = DividePlane(A,c,b,baseVector)%功能：用割平面法求解整数规划%调用格式：intx,intf=DividePlane(A,c,b,baseVector)%其中，A：约束矩阵；% c：目标函数系数向量；% b：约束右端向量；% baseVector：初始基向量；% intx：目标函数取最小值时的自变量值；% intf：目标函数的最小值；sz = size(A);nVia = sz(2);n = sz(1);
6、xx = 1:nVia; if length(baseVector) = n disp(基变量的个数要与约束矩阵的行数相等！); mx = NaN; mf = NaN; return;end M = 0;sigma = -transpose(c) zeros(1,(nVia-length(c);xb = b; %首先用单纯形法求出最优解while 1 maxs,ind = max(sigma);%-用单纯形法求最优解- if maxs = 0 %当检验数均小于0时，求得最优解。 vr = find(c=0 ,1,last); for l=1:vr ele = find(baseVector =
7、 l,1); if(isempty(ele) mx(l) = 0; else mx(l)=xb(ele); end end if max(abs(round(mx) - mx)= 0 %判断如果右端向量均大于0，求得最优解 if max(abs(round(xb) - xb)1.0e-7 %如果用对偶单纯形法求得了整数解，则返回最优整数解 vr = find(c=0 ,1,last); for l=1:vr ele = find(baseVector = l,1); if(isempty(ele) mx_1(l) = 0; else mx_1(l)=xb(ele); end end intx = mx_1; intf = mx_1*c; return; else %如果对偶单纯形法求得的最优解不是整数解，继续添加切割方程 sz = size(A); sr = sz(1); sc = sz(2);
