- 1、本文档共17页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
关于分油问题的两个最优数学模型
关于分油问题的两个最优数学模型
摘要:针对分油经典的问题,本文运用逻辑推理演算的推理过程,对问题的实质进行数学剖析,从而建立出了两个最优的数学模型:
模型Ⅰ:动态规划模型,通过逻辑思考后建立了三维坐标,对问题进一步分析得出
数学模型,并运用了图解法和程序分别对本求解模型;
模型Ⅱ:图论模型,对问题进行深层分析建立了图论模型,利用求最短通路的
Dijk-stra算法编程,求出了模型的最优解。
最后,对此模型进行分析、评价并推广到工作生活的实际问题中,进而使模型得到优化。论文中还存在许多不足之处
关键词:多步决策过程、状态、决策状态、图论模型、Dijk-stra算法编程。
一、 问题重述
有一个人用装10斤油的瓶装了一瓶油拿到市场上去卖,正好来了两个买油的,每人要买5斤,但是没有秤,只有二只空瓶,一个能装7斤油,另一个能装3斤油。试建立模型分析应如何用这3个瓶把10斤油分成两份各为5斤的油。
二、问题分析
2.1针对动态规划模型的分析
对于这一分油的益智问题,经过一系列的逻辑思考后,得出结果,即(1)10斤瓶向7斤瓶倒油。(2)7斤瓶向3斤瓶倒油。(3)3斤瓶向10斤瓶倒油。(4) 7斤瓶向3斤瓶倒油。(5) 3斤瓶向10斤瓶倒油。(6) 3斤瓶向7斤瓶倒油。(7) 10斤瓶向7斤瓶倒油。(8) 7斤瓶向3斤瓶倒油。(9) 3斤瓶向10斤瓶倒油。
表1:各瓶内油量化过程
由表1可得到(如图1所示)的一个三维坐标图,由图1我们可得出以下结论:
(1) 当点落到zox平面时,表示3斤瓶是空瓶;
(2) 当点落到yoz平面时,表示7斤瓶是空瓶;
(3) 当点落到xoy平面时,表示10斤瓶是空瓶;
(4) 当点落到x轴时,表示10斤瓶和3斤瓶是空瓶;
(5) 当点落到y轴时,表示10斤瓶和7斤瓶是空瓶;
(6) 当点落到z轴时,表示3斤瓶和7斤瓶是空瓶;
(7) 当点既不落在坐标轴上也不落在平面时,表示三个瓶子都是有油的。
我们所要解决的问题就是从图1中寻找一条(0,0,10)到(5,0,5)的道路,图中的(1)((9)按照箭头所指的方向走,就是我们找到的一种分油办法。(见表1中的结果)
2.2针对图论模型的分析
我们以x,y,z表示油桶的盛油量,则x,y,z满足如下条件:
……………………………………()
()式中共有32组非负整数解,它们是:
()式的每一组非负整数解,均表示三个容器盛油的一种状态。我们要求的不仅仅限于()式的所有非负整数解,而是研究非负整数集合中元素间的相互关系,即从一组非负整数解出发,怎样才能转移到另一组非负整数解。由于要求分油速度快,这就存在了一个优化问题,显然我们将用到图论这一工具。据此我们建立图论模型。
三、模型的假设及符号的说明
3.1模型的假设:a、假设10斤瓶里的是准确的10斤油;
b、假设7斤和3斤的瓶子装满都是准确的7斤油和3斤油;
c、假设每次倒油的过程中都能不计有油沾在瓶内;
d、假设每次倒油,油没有损失即没有油溢出瓶外;
e、假设分油过程是在常温下进行的无任何外界干扰。
3.2符号的说明:
3.2.1模型Ⅰ的符号说明
——第k次倒油时7斤瓶内的油量;
——第k次倒油时3斤瓶内的油量;
——第k次倒油时10斤瓶内的油量;
——第k次倒油时7斤瓶中油量的改变量;
——第k次倒油时3斤瓶中油量的改变量;
——第k次倒油时10斤瓶中油量的改变量;
——初始状态 ; ——状态;
——末状态; ——决策;
A——10斤的油瓶子; B——7斤的油瓶子;C——3斤的油瓶子。
3.2.2模型Ⅱ的符号说明
L(20,20)——图的长度矩阵(用99代替);
D(20)——存放顶点到各顶点的最短通路长;
T(20)——各顶点最短路径是否计算完;
W(20)——记载求最短通路的次序。
四、模型建立
4.1动态规划模型(模型Ⅰ)
我们用有序数组的变化来表示整个倒油的过程的集合:
…………...()
每次倒油后是7斤瓶子和3斤瓶子某一瓶是空的或是不空的,故状态集合为:
…………….()
同理得决策集合为:
……………………….()
由此可得状态决策的规律:
…………………………………………………...()
()式称为状态转移方程,也表明了本问题的状态递归关系。求,使 按照状态转移方程()(状态递归关系),则由以下的多步决策问题可得出具体行之有效的分
文档评论(0)