数学建模--最佳分油模型.

1、楚雄师范学院2013年数学建模培训第一次预赛论文 题 目 最佳分油模型 姓 名 系（院） 专 业 2013 年 5 月 17 日 最佳分油模型【摘要】 本文主要是根据分油问题而建立的数学模型，从分油问题出发写出相关代码，最终求出最佳的决策方案，并用所学的知识推广成一般数学模型。【关键字】 C+实现 线性规划 图表显像法 递归作图一、问题重述有一个人用装10斤油的瓶装了一瓶油拿到市场上去卖，正好来了两个买油的，每人要买5斤，但是没有秤，只有二只空瓶，一个能装7斤油，另一个能装3斤油。试建立模型分析应如何用这3个瓶把10斤油分成两份各为5斤的油。二、问题分析古有“韩信分油”的典故，根据“韩信分油”

2、将上述的问题用数学语言描述为：有三个无容量刻度的容器A、B、C，且容量分别为10、7、3斤。容器A中装满10斤油，B、C为空容器，怎么利用三个容器将10斤油平均分给另外两个小的容器中？经过思考、查阅资料，我们可以利用逐项列举的图解法，得出分油结果。可当容器A、B、C容量很大时，这种逻辑方法就很难完成分油任务。 所以面对该分油问题，我们将它进行推广，记三个容器A、B、C且容量分别为a、b、c斤；容器A中装满a升油，B、C都为空容器。怎么利用三个容器将a升油平均二等分?对于这个问题，应用数学知识构建立数学模型，提出一种通用的方法进行求解。三、问题假设1、假设每次倒油的时候都没有油漏掉；2、假设倒油

3、时三个容器都不会将由留剩余容器壁上；2、假设A、B、C三个容器都没有损坏。四、符号说明：表示容器*向容器XX倒入油：B中的油量：C中的油量：第次倒油时，B容器内的油改变量：第次倒油时，C容器内的油改变量D：允许决策集合 五、模型的建立与求解1、基本问题解决基于问题，我们通过逻辑推理，用最基本方法：将一容器内的油向另外的容器中倾倒的方法，得出下面分油方法动态规划模型的思想写出代码，最终得出结果。分油问题代码，如下：function algorythm()/* 分油问题 Halve Oil 某人用只 10 千克的桶装满了一桶油去卖， 正好来了两个买油的，每人要买 5 千克，但没有秤，只有两只可装

4、7 千克和 3 千克的空桶。问怎样利用这两只空桶将油平均分成两份 很显然，每次倒油时必须是倒空或倒满一只桶。三只桶里油的重量之和总是不变的，所以，我们只需讨论用来分油的两只桶装油数量的变化情况。这样我们便可通过平面上的点来表示各种可能的状态，如图 设三个桶的容量分别为 C、B、A (B) 3 2 (A) (A) 1 0 0 1 2 3 4 5 6 7 (B) 为可能状态 为不可能状态 若 A+BC 则上面的矩形将不同程度地缺掉右上角。 每倒油一次，三个桶便由一种状态变为另一种状态。如果用 (B,A) 表示两个分油桶装油的数量， 那么，我们的目的是要将油倒来倒去，最后达到目标状态 (5,0) 于

5、是分油问题便成为在图中寻求从点 (0,0) 到点 (5,0) 的有向路径。有两个问题需要解决：一是有多少条不同的路径；二是哪条路径最短 对于问题一，我们采用回溯技术，于每种状态从上下左右斜五个方向对整个状态空间进行搜索，直至找出所有解 对于问题二，利用上面的算法固然可以找出最佳解，但搜索整个状态空间却费时太多。必须另外设计算法。下面算法的思想是：设三个桶由大到小分别为 C,B,A 并将其摆成三角形 C B A 第一轮，有条件地逆时钟方向倒油，直至达到目标状态 第二轮，有条件地顺时针方向倒油，达到目标状态后，比较两轮倒油的次数。较少者便是分油问题的最隹解 = */ /= function hal

6、veOil(C,B,A) var labeled,dir,potB,potA,half,dirs,step; var initialization=function() labeled=,dir=,potB=0,0,potA=0,0; half=C/2,dirs=5,step=0; for(var i=0;i=B;i+) labeledi=; for(j=0;j=A;j+)labeledij=false; for(var i=0;i=B+B+A+A;i+)diri=0; labeled00=true; () var bestSol=function() var a=A,b=B; var e=0

7、,0,0,0,f=0,0,0,0; for(var p=0;pdir.length)return ; if(t0) var h=C-b-fpx-1; h=(h0)t=(ts)?s:t,epx=s-t,fpx=fpx-1+t; else epx=b-h,fpx=fpx-1; else epx=s,fpx=0; ep0=x,x=a,a=b,b=x; var p=e00e10?0:1,pC=,pB=,pA=; for(var k=1;k=ep0;k+) pAk=p?epk:fpk; pBk=epk+fpk-pAk; pCk=C-pBk-pAk; return pC,pB,pA; var fullDa

8、ta=function(s) var potC=; for(var i=0;iC)?C-i:A;break; case 2:j=0;break; case 3:i=0;break; case 4:i=(j+BC)?C-j:B;break; case 5:if(j=A|i=0)j=pB?p-B:0,i=p-j; else i=pA?p-A:0,j=p-i;break; if(!labeledij&(i!=potBs|j!=potAs) potBs+1=i,potAs+1=j;return true; else return false; var findSol=function() while(

9、step=0) if(+dirstepdirs)labeledpotBsteppotAstep=false,dirstep-=0; else if(nodePass(step) if(potBstep+1=half&potAstep+1=0)return fullData(step+1); else labeledpotB+steppotAstep=true; return ; return bestsol:bestSol,getSol:findSol; /= function halveOil_Datas() return 8,5,3,10,7,3,12,7,5; /= function h

10、alveOil_Form() var solutions,oilPot; var showSolution=function() var sol=oilPot.getSol(); if(sol.length) potsol.innerText=getansStr(sol); solmes.innerText=solutions = +(+solutions); else allover.innerText=solutions?求解完毕 !:无解 !; var showbest=function() var sol=oilPot.bestsol(); if(sol.length)solbest.

11、innerText=getansStr(sol)+The best solution.; else solbest.innerText=无解 ! var getansStr=function(sol) var c=sol01+sol11+sol21; var solStr= +c+ 0 0 n; for(var i=1;isol0.length;i+) solStr+=step +i+ +sol0i+ +sol1i+ +sol2i+ n; return(solStr); var initOil=function() var c=parseInt(potC.optionspotC.selecte

12、dIndex.text); var b=parseInt(potB.optionspotB.selectedIndex.text); var a=parseInt(potA.optionspotA.selectedIndex.text); oilPot=halveOil(c,b,a);solutions=0; solbest.innerText=allover.innerText=;showSolution(); var addEvent=function() potC.innerHTML=potB.innerHTML=potA.innerHTML=; for(var i=8;i21;i+)p

13、otC.add(new Option(i); for(var i=5;i12;i+)potB.add(new Option(i); for(var i=3;i10;i+)potA.add(new Option(i); reset.onclick=function()initOil(); pbest.onclick=function()showbest(); pasol.onclick=function()showSolution(); initOil(); var initComponents=function() initMainForm(halveOil); mainFrame.inner

14、HTML=; ctrlPanel.innerHTML=分油问题+ potC：+ potB：+ potA： + 找到方案+ + 按钮+ + + ; addEvent(); ()2.模型构成 分油问题可看作一个多步决策问题，记第倒油时，B中的油量为，C中的油量为，将二维向量定义为状态，我们用序数组的变化来表示整个倒油过程，集合 （1）称为状态集合，由于每次都以为着摸一个容器被灌满或者被倒空，所以允许状态集合为 （2）记次倒油时，B容器内的油改变量为，C内油的改变量为，将二维向量定义为决策，则允许决策集合为D，由各容器的的容量可知 （3）状态变化规律是 （4）（4）式称为状态转移律，则制定分油方案归

15、结为如下的多步决策问题： 求决策，使状态按照状态转移律（4），由初始状态经有限步n到状态。3.模型求解 我们可以通过编写程序，利用计算机进行求解，也可以用图解法来处理这个问题，如图（1）所示，所有的操作应该在举行OABC的界面上进行，决策变量沿方格线左右平移7格表示由B向A倒空油或者A向B倒满油；沿方格上下平移3格，表示由A向C倒空油或者C向A倒满油；沿方格线左上方移过k行，表示B向C倒k斤油；沿方格右下方移过k行，表示C向B倒k斤油；寻求决策方案的过程即是在上述规定下，将坐标点从（0,0）移至（0,5）的过程。根据图（1）这个模型，我们还可以很快的找到问题的另外一组解，如图（2）。32101

16、234567ABC分油问题方案4.结果分析 将图1，图2画在同一坐标轴上，如图3（虚线为图1方案，实线为图2方案），可看到X轴上坐标1,2,3,4,5,6,7都曾被箭头所指，从而可知，利用这三个容器可分出1,2,3,4,5,6,7,斤油。这里并不要求A的容量一定是10斤。32101234567ABC分油结果 5.模型评价与推广 对于这个分油问题，我们可拓展思路，提出疑问，即3个容器A,B.C的容量分别为斤，；现容器A中装满斤油，B,C为空，如何利用容器将斤油二等分？当c=1时，自然可以将油分出1至b斤；当，时我们可以利用上述的图解法，对问题进行求解，也可以将油分出1至b斤。参考文献【1】数学建

17、模-方法与范例，寿纪麟等编，西安交通大学出版社(1993)。【2】数学实验 高等教育出版社 王向东、戎海武、文翰 编著。【3】数学模型，姜启源编，高等教育出版社(1987年第一版，1993年第二版，2003年第三版；第一版在 1992年国家教委举办的第二届全国优秀教材评选中获全国优秀教材奖)。【4】几何画板课件制作教程（第三版）科学出版社，刘胜利 编著。 附录 韩信分油韩信是汉代的大将，小时候便爱动脑筋，聪明过人。 传说有一天，街上的两个卖油人正在争吵不休。路过这里的韩信，出于好奇， 呆呆地看着。他终于明白，原来这两个人合伙卖油，因意见不合，准备把油桶里还剩下的十斤油平分后各奔东西，又为了分油不均而争执不下。 韩信仔细端详着，他们手头没有秤，只有一个能装3斤的油葫芦和一个能装7斤的瓦罐。他们用油桶倒来倒去，双方总不满