《数学建模--最佳分油模型》由会员分享，可在线阅读，更多相关《数学建模--最佳分油模型（12页珍藏版）》请在金锄头文库上搜索。
1、楚雄师范学院2013 年数学建模培训第一次预赛论文题 目 最佳分油模型 姓 名 系（院） 专 业 2013 年 5 月 17 日1最佳分油模型【摘要】 本文主要是根据分油问题而建立的数学模型，从分油问题出发写出相关代码，最终求出最佳的决策方案，并用所学的知识推广成一般数学模型。2【关键字】 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
3、、假设每次倒油的时候都没有油漏掉；2、假设倒油时三个容器都不会将由留剩余容器壁上；2、假设 A、B、C 三个容器都没有损坏。四、符号说明：表示容器*向容器 XX 倒入油：B 中的油量kx：C 中的油量y：第 次倒油时，B 容器内的油改变量ku：第 次倒油时，C 容器内的油改变量vD：允许决策集合3五、模型的建立与求解1、基本问题解决基于问题，我们通过逻辑推理，用最基本方法：将一容器内的油向另外的容器中倾倒的方法，得出下面分油方法动态规划模型的思想写出代码，最终得出结果。分油问题代码，如下：function algorythm()/*分油问题 Halve Oil 某人用只 10 千克的桶装满了一
4、桶油去卖， 正好来了两个买油的，每人要买 5 千克，但没有秤，只有两只可装 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、， 那么，我们的目的是要将油倒来倒去，最后达到目标状态 (5,0)于是分油问题便成为在图中寻求从点 (0,0) 到点 (5,0) 的有向路径。有两个4问题需要解决：一是有多少条不同的路径；二是哪条路径最短对于问题一，我们采用回溯技术，于每种状态从上下左右斜五个方向对整个状态空间进行搜索，直至找出所有解对于问题二，利用上面的算法固然可以找出最佳解，但搜索整个状态空间却费时太多。必须另外设计算法。下面算法的思想是：设三个桶由大到小分别为 C,B,A 并将其摆成三角形 C B A 第一轮，有条件地逆时钟方向倒油，直至达到目标状态第二轮，有条件地顺时针方向倒油，达到目标状态后，比较两轮倒油的次数。较少
6、者便是分油问题的最隹解 = */ /= function halveOil(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;idir.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=
7、0;ep0=x,x=a,a=b,b=x;var p=e00C)?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(step=0)if(+dirstepd
8、irs)labeledpotBsteppotAstep=false,dirstep-=0;else if(nodePass(step)if(potBstep+1=halfelse labeledpotB+steppotAstep=true;return ; return bestsol:bestSol,getSol:findSol; /= function halveOil_Datas()return 8,5,3,10,7,3,12,7,5; /= function halveOil_Form()var solutions,oilPot; var showSolution=function()
9、var sol=oilPot.getSol();7if(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.innerText=getansStr(sol)+The best solution.;else solbest.innerText=无解
10、! var getansStr=function(sol)var c=sol01+sol11+sol21;var solStr= +c+ 0 0 n;for(var i=1;i;ctrlPanel.innerHTML=分油问题+potC：+potB：+potA： +找到方案+按钮+;addEvent();()2.模型构成 分油问题可看作一个多步决策问题，记第 倒油时，B 中的油量k为 ，C 中的油量为 ，将二维向量 定义为状态，我们用序数kxky),(kkyxs组 的变化来表示整个倒油过程，集合),(y30,7 yxS（1）称为状态集合，由于每次都以为着摸一个容器被灌满或者被倒空，所以允许状态
11、集合为9 7,02;7,01;70,370, xyxyxyxyxS（2）记 次倒油时，B 容器内的油改变量为 ，C 内油的改变量为 ，将二维向量k kukv定义为决策，则允许决策集合为 D，由各容器的的容量可知),(kkvud3,7D（3）状态变化规律是kkdS1（4）（4）式称为状态转移律，则制定分油方案归结为如下的多步决策问题：求决策 ，使状态 按照状态转移律（4） ，由初始状态DkSk )0,(s经有限步 n 到状态 。)0,5(ns3.模型求解 我们可以通过编写程序，利用计算机进行求解，也可以用图解法来处理这个问题，如图（1）所示，所有的操作应该在举行 OABC 的界面上进行，决策变量
12、 沿方格线左右平移 7 格表示由 B 向 A 倒空油或者 A 向 B 倒满kd油； 沿方格上下平移 3 格，表示由 A 向 C 倒空油或者 C 向 A 倒满油； 沿k kd方格线左上方 移过 k 行，表示 B 向 C 倒 k 斤油； 沿方格右下方 移过o15 kdo45k 行，表示 C 向 B 倒 k 斤油；寻求决策方案的过程即是在上述规定下，将坐标点从（0,0）移至（0,5）的过程。根据图（1）这个模型，我们还可以很快的找到问题的另外一组解，如图（2） 。103210 1 2 3 4 5 6 7ABC分油问题方案4.结果分析 将图 1，图 2 画在同一坐标轴上，如图 3（虚线为图 1 方案，
13、实线为图 2 方案） ，可看到 X 轴上坐标 1,2,3,4,5,6,7 都曾被箭头所指，从而可知，利用这三个容器可分出 1,2,3,4,5,6,7,斤油。这里并不要求 A 的容量一定是 10 斤。3210 1 2 3 4 5 6 7ABC分油结果5.模型评价与推广 对于这个分油问题，我们可拓展思路，提出疑问，即 3 个容器 A,B.C 的容量分别为 斤， ；现容器 A 中装满 斤油，B,C 为cba,ca空，如何利用容器将 斤油二等分？当 c=1 时，自然可以将油分出 1 至 b 斤；当 ，时我们可以利用上述的111图解法，对问题进行求解，也可以将油分出 1 至 b 斤。参考文献【1】数学建模-方法与范例，寿纪麟等编，西安交通大学出版社(1993)。【2】数学实验 高等教育出版社 王向东、戎海武、文翰 编著。【3】数学模型，姜启源编，高等教育出版社(1987 年第一版，1993 年第二版，2003 年第三版；第一版在 1992 年国家教委举办的第二届全国优秀教材评选中获 全国优秀教材奖)。【4】几何画板课件制作教程（第三版）科学出版社，刘胜利 编
