1、运 筹 学 与 最 优 化 MATLAB 编 程实 验 报 告院系: 专业: 姓名: 学号: 指导老师: 完成日期: 割平面法求解整数规划问题一、 引言: 通过对 MATLAB 实践设计的学习,学会使用 MATLAB 解决现实生活中的问题。该设计是在 MATLAB 程序设计语言的基础上,对实际问题建立数学模型并设计程序,使用割平面法解决一个整数1规划问题。经实验,该算法可成功运行并求解出最优整数解。二、 算法说明:割平面法有许多种类型,本次设计的原理是依据 Gomory 的割平面法。Gomory 割平面法首先求解非整数约束的线性规划,再选择一个不是整数的基变量,定义新的约束,增加到原来的约束中
2、,新的约束缩小了可行域,但是保留了原问题的全部整数可行解。算法具体设计步骤如下:1、首先,求解原整数规划对应的线性规划 ,*)(minxcf,设最优解为 x*。0.xbAts2、如果最优解的分量均为整数,则 x*为原整数规划的最优解;否则任选一个 x*中不为整数的分量,设其对应的基变量为 xp,定义包含这个基变量的切割约束方程 ,其中 xp为非基变conjjipbxr量。3、令 , ,其中为高斯函数符号,表ijijijrconconb示不大于某数的最大整数。将切割约束方程变换为,由于 0 A=0.01 0.01 0.01 0.03 0.03 0.03 1 0 0 0;0.02 0 0 0.05
3、 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=-20;-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、
4、生产 D 、E、F 均为 0,此时的季度产值为最大即 12500005元。该结果是可信的,故通过该实例说明该程序能够运用于实际,用来解决实际生活中求解整数规划的问题。五、 结束语:Matlab 是个很强大的软件,提供了大量的函数来处理各种数学、工程、运筹等的问题,并且含有处理二维、三维图形的功能,使用matlab 能够解决许多实际生活中的问题。通过这个学期的学习,仅是了解了 matlab 的部分函数功能和简单的 GUI 界面设计,掌握了一些基本的程序编写技能,同时,在老师的指导下简单了解了使用LinGo 和 Excel 解决线性和非线性规划问题的求解方法,收获相当丰富,同时认识到要学好 mat
5、lab 仍然需要一个长期的过程。六、 参考文献:1 龚纯,王正林.精通 MATLAB 最优化计算.北京:电子工业出版社,20092吴祈宗,郑志勇,邓伟等.运筹学与最优化 MATLAB 编程.北京:机械工业出版社,20093邓成梁.运筹学的原理和方法(第二版).武汉:华中科技大学出版社,2002七、 附录:function intx,intf = DividePlane(A,c,b,baseVector)%功能:用割平面法求解整数规划%调用格式:intx,intf=DividePlane(A,c,b,baseVector)%其中,A:约束矩阵;6% c:目标函数系数向量;% b:约束右端向量;%
6、 baseVector:初始基向量;% intx:目标函数取最小值时的自变量值;% intf:目标函数的最小值;sz = size(A);nVia = sz(2);n = sz(1);xx = 1:nVia;if length(baseVector) = ndisp(基变量的个数要与约束矩阵的行数相等!);mx = NaN;mf = NaN;return;endM = 0;sigma = -transpose(c) zeros(1,(nVia-length(c);xb = b;%首先用单纯形法求出最优解while 1 maxs,ind = max(sigma);%-用单纯形法求最优解-if m
7、axs = 0 %判断如果右端向量均大于0,求得最优解if max(abs(round(xb) - xb)09bz = xb(j)/A(j,ind);if bzminbminb = bz;chagB = j;endendendsigma = sigma -A(chagB,:)*maxs/A(chagB,ind);xb(chagB) = xb(chagB)/A(chagB,ind);A(chagB,:) = A(chagB,:)/A(chagB,ind);for i =1:nif i = chagBxb(i) = xb(i)-A(i,ind)*xb(chagB);A(i,:) = A(i,:) - A(i,ind)*A(chagB,:);endendbaseVector(chagB) = ind;endM = M + 1;if (M = 1000000)disp(找不到最优解!);mx = NaN; minf = NaN;return;endend