数学建模中的整数规划问题研究论文.doc

数学建模中的整数规划问题研究论文引言应用数学学科的一项重要任务是从自然科学、社会科学、工程技术以及现代化管理中提出问题和解决问题。这就要求我们学会如何将实际问题经过分析、简化转化为一个数学问题然后用适当的数学方法解决即建立数学模型。随着科学技术的发展特别是计算机技术的发展数学的应用领域已由传统的物理领域迅速的扩展到非物理领域。数学在发展高科技、提高生产力水平和实现现代化管理等方面的作用越来越明显。正是这样的背景下数学模型这个词汇越来越多的出现在现代化生产、工作和社会生活中。数学模型的分类方法有很多种例如按照建模所用的数学方法的不同可分为:初等模型、运筹学模型、微分方程模型、概率统计模型、控制论模型等。而运筹学模型中的规划模型又可分为非线性规划模型和线性规划模型本文通过实例剖析线性规划中整数规划方法在数学模型种的应用主要结果数学建模中的整数规划问题在研究线性规划的问题中一般问题的最优解都是非整数即为分数或小数但对于实际中的具体问题的解常常要求必须取整数例如问题的解表示是人数、机器设备的台数、机械车辆数等都是整数为了求整数解我们设想把所求得的非整数解采用“舍人取整”的方法处理似乎是变成了整数解但事实上这样得到的结果未必可行因为取整以后就不一定是原问题的可行解了或者虽然是可行解但也不一定是最优解因此对于要求最优整数解的问题需要寻求直接的求解方法这就是整数规划方法整数规划的基本概念nmaxmin,cx,,jjz,jn,整数规划的一般模型为:()ax,(,,,)bi,,,？,m,,ijji,st,j,,x,,x为整数j,,,？,n,jj,整数规划求解方法总的基本思想是:松弛问题()中的约束条件(譬如去掉整数约束条件)使构成易于求解的新问题松弛问题(A)如果这个问题(A)的最优解是元问题()的可行解则就是原问题()的最优解否则在保证不改变松弛问题(A)的可行性的条件下修正松弛问题(A)的可行域(增加新的约束)变成新的问题(B)再求问题(B)的解重复这一过程直到修正问题的最优解在原问题()的可行域内为止即得到了原问题的最优解整数规划的解法整数规划的分枝定界法分枝定界法的基本思想:将原问题()中的整数约束去掉变为问题(A)求出问题(A)的最优解如果它不是原问题的可行解则通过附加线性不等式约束将问题(A)分枝变为若干子问题()(i=…I)即对每一个非整数变量附加两个互相排斥(不Bi交叉)的整型约束即可得到两个子问题继续求解定界重复这一过程知道得到最优解为止。分枝定界法的一般步骤:()将原整数规划问题()去掉所有的整数约束变为线性规划问题(A)用线性规划的方法求解问题(A)则有下列情况:)问题(A)无可行解则原问题()也无可行解停止计算:*X)问题(A)有最优解并不是原问题()的可行解则此解就是(A)的最优解计算结束*X)问题(A)有最优解但不是原问题()的可行解转下一步。,*()将代入目标函数其只记为并用观察法找出原问题()的一个可行Xz解(整数解不妨取)求得目标函数值(下界值)记为x,(j,,,？,n)zj,,**即有转下一步则原问题()的最优值记为zz,z,z,()分枝:在问题(A)的最优解中任选一个不满足整数约束的变量(非整x,bjj数)附加两个整数不等式约束:和分别加入到问题(A),,,,x,bx,bjjjj中构成两个新的子问题()和()仍不考虑整数约束求问题()和BBB()的解。B,定界:对每一个子问题的求解结果找出最优值的最大者为新的上界从所z有符合整数约束条件的分枝中找出目标函数值最大的一个为新的下界。z,()比较与剪枝:将各分枝问题的最优值同比较如果其值小于则这个分枝zz,,可以剪掉以后不再考虑。如果其值大于且又不是原问题()的可行解则z,**继续分枝返回()直到最后得到最优解使z=即为原问题x(j,,,？,n)zj,()的最优解。整数规划的割平面法割平面法的基本思想:首先把原整数规划问题()去掉整数约束条件变为线性规划问题(A)然后引入线性约束条件使问题(A)的可行域逐步缩小每次切割掉的是问题非整数解的一部分不切掉任何整数解知道最后使得目标函数达到最优的整数解成为可行域的一个顶点为止这也就是原问题()的最优解。即利用线性规划的求解方法逐步缩小可行域最后找到整数规划问题的最优解。割平面法的计算步骤:设原问题()中有n个决策变量m个松弛变量共nm个变量略去整数约束求解线性规划问题将最终的求解结果放入如表中。其中x(i,,,？,m)表i示基变量y(j,,,？,n)表示非基变量则具体计算步骤如下:j()在最优解中任取一个具有分数值的基变量不妨设为由此可得x(,i,m)in,,即xay,biji,ij,jn,,()x,b,ay,i,miij,ij,j,,()将和(为假分数)分为整数部分和菲负分数的真a(,i,mj,,,？,n)biji分数即nm()xNy,N,f,fy,i,m,,iijjjiijj,,jj()要使和都为整数()式的左端必为整数右端也是整数而且由xyjin是非负整数故此。又因是真分数于是有yf,fx,fy,,jiijj,jn则必有f,fy,f,,iijji,jn()()f,fy,,i,m,iijj,j这就是所要求的一个切割方程(Gomory约束条件)()对()式引入一个松弛变量则()式变为Sin()S,fy,,f,i,m,iijji,j将其带入原问题中去求解新的线性规划问题()应用对偶单纯形法求解如果所求最优解为原问题的可行解则就是原问题的最优解计算结束。否则继续构造Gomory约束条件知道其最优解为整数解停止。整数规划如果整数线性规划问题的所有决策变量x仅限于或两个数值则称此问题为i线性整数规划简称为规划。变量x称为变量或二进制变量其变量i取值的约束可变为=或等价于和且为整数。于是规划的一般xx,x,iii模型为nmax(min)z,cx,jj,jn,ax(,)b(i,,？,m),,,,,ijji,,stj,,,x或(j,,？,n),,j,整数规划的LINGO解法LINGO软件是LinusSchrage教授于年前后开发的一套专门用于求解最优化问题的工具包(后来经过了多年的不断完善和扩充(并成立了LINDO系统公司进行商业化运作。取得了巨大成就。该软件操作简单(求解速度快。目前利用LINGO软件求解整数规划模型是一种比较有效的方法。针对一般的准归属规划模型()给出LINGO模型如下MODEL:sets:numimbnumjn:x,clink(numi,mumj):aendsetsdata:b=b(),b(),…,b(m)c=c(),c(),…,c(n)a=a(,),a(,),…,a(,n),a(,),a(,),…,a(,n),…………a(m,),a(m,),…,a(m,n)enddataOBJmax=sum(numj(j):c(j)*x(j))for(numi(i):sum(numj(j):a(i,j)*x(j))<b(i))for(numj(j):x(j)>=)for(numj(j):GIN(x(j)))END说明:LINGO模型中的目标函数是按最大化问题约束条件都是按“小于等于”的情况给出的实际中要根据具体情况修正。应用举例生产资源分配模型问题的提出生产企业制定生产计划分配生产资源时某原材料月分配计划单位为百吨日分配计划单位为吨这样常出现企业各车间总的日计划分配额不等于各车间日计划分配额的总合情况(祥见表)。表为企业按照该种原材料的存储及运输能力各车间的生产情况以百吨(或其他整数单位)为单位制定的初步分配计划(按照该月初步计划(每日以吨(或其他整数单位)为单位向各车间供应该种原材料(表中(日计划为按照月计划分配额。以天计算(四舍五入取整)的各车间日分配额(各车间日供应合计为吨。全月供应总量吨超出了企业供应能力(可能会造成企业生产的不连续性。基于这个问题就要对各车间的分配计划进行微量调整(调整方法:()保持总计划不变()车间月计划要整百的进行调整。表一月原材料计划表生产单位个月计划(吨)每日计划(吨)一车间二车间三车间四车间五车间六车间七车间八车间九车间十车间总计调整后结果见表。由表可以看出(调整后的每日计划总合与总的每日计划结果一致。表一月原材料计划表(调整后)生产单位个月计划(吨)每日计划(吨)一车间二车间三车间四车间五车间六车间七车间八车间九车间十车间总计(问题的分析根据上述问题(设生产计划向量和×的调整矩阵A(其中为与之间调整的数量各车间月计划按下式进行调a,Z,a,xxijijji整:aa？a,,,,aa？a,,A,,,？？？？,,,,aa？a,,由上面假设(可以得出下面的整数规划模型:'x,xa,a,,iiijji,,jj,,其中。()式为目标函数(式中的为调整总量(即调整总量最小()z,a,,ij,,ij()式为约束条件(()式要求调整后的生产计划满足每日总计划与总的每日计划相等Int(R)为对R进行向下取整(Int(R)为对R进行整数位的四舍五入()式要求调整量为非负整数又由于车间月计划要整百的调整(所以在()式中为a,ijj,问题的求解证明证明上述整数规划问题的可行域不为空。即证明:n,S,x,A,(a),a,Na,,(i,j,,,？,n)使得()式成立。首先把,iijijiji,T分解为两项:X,XXX,x,x,？,xn其中:为可被整除的最大整数X,(x,x,？,x)xin。X,(x,x,？x)x,x,xniii？,,,,？,,,,A,令,,？？？？？,,？,,,,xxx？n,,nn,,',,这样前n一个调整后的值(i=„n)x,,xxaa,,iii,jj,ii,,j,,j,,'可以被整除调整后的值与S对的整除性质相同。所以()式为左边xxnn=nnnn,,,,,,,xaa,,xaa,,,,,ii,jj,ini,jj,i'n,,x,,,,,jj,,jj,n,,,,IntIntInt,,,,,,,,i,,,,,,,,,,,,,,n,,,,x,iS,,,,i,==右边,IntInt,,,,,,,,,,所以说(上述整数规划问题的可行域不为空。求解:本例子采用LINGO软件进行求解以下是求解上述问题的LINGO程序:Model:TitleScheduleProblomSets:L,,:xR,,:link(L,R):aEndSetsData:x=,,,,,,,,,NDay=EndDatasum(L(i):Floor((x(i)*sunl(R(j):a(i,j))*sum(R(j):a(ji))),NDayO))=Floor(sum(L(i):x(i),NDay))for(L(i):for(R(j):GIN(a(ij))))OBJmin=Sum(L(i):sum(R(j):a(i,j)))End求解用时s,求解结果为:Objectivevalue:OOOOOVaffableValueReducedCost…A(,)…A(,)„未列出的都为零(既只需其余不变。调整后结果ax,x,,x,i,j见表。因此企业生产计划中的原材料分配问题可以归结为整数规划问题建立具体的数学模型(并利用LINGO软件进行计算可快速得到准确的结果。说明整数规划在生产计划中的实际应用为分配生产计划提供科学的方法(具有一定的实用价值。水泵优化选型模型问题的提出水泵选型对于泵站的工程投资和运行费用等诸多问题都有很大影响。因此水泵优化选型已引起很大关注。水泵优化选型的方法很多这里以设计流量为s设计净扬程为m的某泵站为例介绍一种在现有水泵产品中进行优m化选型的整数规划法。问题的分析根据泵站的设计净扬程和估算的流道(或管道)阻力损失在现有的水泵产品中选择若干种水泵型号。根据本例中泵站设计扬程和流量可以初步选择ALB一、ZL、CJ一种型号的水泵。见表l。这里需要解决的问题是确定该站应选择哪几种泵型以及各自的台数、、。xxx如果计算结果为===说明该站只选台CJ一型大型轴流泵即xxx可。计算结果也可能出现==l=这就说明该站应该选择两种泵型xxx即Zl型台CJ一型台。这种不同泵型的搭配可以调节流量避免水量浪费达到节能节水的目的因此国外不少泵站采用了这种不同型号的组合方式。表可供选择的几种水泵的主要参数水泵型号设计流量设计扬程配套功率,mkwm,sZLBZLCJ由此可见各种泵型的台数、、可以作为水泵优化选型的决策变量。xxx通常表示泵站技术特征的主要指标有工程投资和运行费用。同时考虑这两个因素的指标有年支出或水费成本等。因此很多优化问题可以用年支出或水费成本最小作为目标函数。但是在泵站初步设计的规划阶段工程投资和运行费用都不容易计算出来。因此以年支出或运行费最小作为目标函数将会给计算工作带来很多麻烦。由于泵站的水费成本或年支出都与泵站的装机容量有密切的关系如装机容量过大不仅会造成工程投资的增加而且往往会引起效率的下降从而增加运行费用。为此在初步设计阶段可以把装机容量最小作为水泵优化选型目标函数。对本例而言其目标函数可用下式表示:()minN,xxx()若所选的水泵台数为零表示不选该种泵型但水泵台数为负数却毫无意义。因此水泵选型必须满足的约束条件。x、x、x,()水泵台数也可能为小数任何泵站的起动台数为零点几是无法实现的在此水泵选型必须满足、、为非负整数的约束。xxx()根据泵站必须满足设计流量的要求还可以得出的等式xxx,约束条件。但是对于跨流域调水或用水灌溉的多级提水泵站其流量是允许有一定变化幅度的。流量太小不能满足生产要求流量太大又会引起级间弃水造成能量和水量的浪费。如果本例中的流量变化幅度为则上述ms等式约束可以变换为两个不等式约束条件。因此本问题的约束条件可以归纳为:()xxx,xxx,()()x、x、x,、、x为整数()xx由上述目标函数和约束方程可见水泵优化选型在初设阶段选择现有水泵产品时可以简化为整数规划问题。问题的求解首先不考虑上述数学模型中的式()表示的约束条件。这当然就是一般的线性规划问题。可以用单纯形法求出最优解:===泵站的装机容量xxxN=kw为最小值(计算过程略)。说明只需选择一处CJ型水泵即可。但是其台数=台不是整数不能满足约束式()的要求。如果把台数增加x到=此时不仅会使目标函数N增到lkW而且会使泵站的流量增大到x即大于不能满足约束条件式()的要求。为此可见本问msms题仅用非整数线性规划是无法得到最优解的因此需要用整数规划的方法求解。用整数松驰求解线性规划问题即将上述问题分枝为以下两个问题:T()xxx,()xxx,()x,()x、x、x,T()xxx,()xxx,()x,x、x、x,()对于第个问题()不能同时满足式()、式()故为无解。对于第一个T问题()同样可以用单纯形法求解得这时的装机容量Tx,,x,,x,()(计算过程略)。但是这时仍然没有满足整数的要求故需对再TN,kw进行分枝约束条件变为T()xxx,()xxx,()x,()x,()x、x、x,T()xxx,()xxx,()x,()x,()x、x、x,()再用单纯形法求得的解为===,。TxxxTN,kw()()()的解为。因为故将剪枝Tx,,x,,x,N,kwN,N(即无需往下求解)。而对再分为和两枝并求出相应的最优解。用同TTT样的方法进行分枝求解直至全部的决策变量均为整数为止。其中装机容量最小者为最优决策。由此可见本问题最优解为===。这时的泵站装xxx机容量为N=kw和非整数规划的最优解(===)N=kwxxx相比装机容量增加了kw这就是整数化所造成的结果。致谢毕业论文正代表着大学的终结完成它既有一种收获感又有一种失落感可无论如何它代表着我四年的努力代表了我四年的历程。当它终于完工的时候我不禁想起了很多人很多事尤其是辛勤培养我的老师们谢谢你们～首先要特别感谢我的指导老师王艺霏老师。王老师在我毕业论文的撰写过程中给我提供了极大的帮助和指导。从开始选题到中期修正再到最终定稿自始至终为本文的研究给予精心的指导和帮助倾注了大量的心血花费了很多宝贵时间(她的热心教导和孜孜不倦的精神感染了我给了我最大的鼓励和信心(其次感谢帮助过我的同学和一直关心支持着我的家人对我的教诲、帮助和鼓励。我要在这里对他们表示深深的谢意～最后对老师同学和家人再次致以我最衷心的感谢～参考文献唐焕问、贺明峰数序模型引论M北京:高等教育出版社,():韩中庚数学建模方法及其应用M北京:高等教育出版社林秋红整数规划在数学建模中的应用J大众科技,():陈林航空公司实行多级票价的经济数学模型J中国民航大学学报,():胡浩云、贾艳辉浅析整数规划法求解生产资源分配问题J中国校外教育,():吴亚敏均衡生产计划的数学模型J消费导刊,():周杰多产品供应商选择的模糊多目标整数规划模型J工业工程,():陈静一类整数规划问题的Lagrange求解方法J金陵科技学院学报,():白咏梅、叶晓红浅议水泵优化选型的整数规划法J水利科技与经济,():刘永亮用整数规划方法选择煤炭行业最优规划方案J运筹与管理():