从特殊到一般的分油问题的模型建立.docVIP

【摘要】本文主要是针对分油问题建立动态规划模型，从特殊的分油问题利用图解法求出决策方案，最后用剩余类知识将其推广到一般的模型。 【关键字】动态规划模型 多步决策 图解法 剩余类方法 一、问题重述 有一个人用装10斤油的瓶装了一瓶油拿到市场上去卖，正好来了两个买油的，每人要买5斤，但是没有秤，只有二只空瓶，一个能装7斤油，另一个能装3斤油。试建立模型分析应如何用这3个瓶把10斤油分成两份各为5斤的油。 二、问题分析 这是一道古老的分油益智游戏题，首先将上述的问题表述为数学语言：现有三个无刻度的容器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、假设三个容器是干净没有污秽的； 2、假设A、B、C三个容器没有破损； 3、假设在进行上述活动时没有意外发生。 四、符号说明 →：表示容器**向容器**倒入油 ：B中的油量 ：C中的油量 ：第次倒油时，B容器内的油改变量 ：第次倒油时，C容器内的油改变量 D：允许决策集合 五、模型的建立与求解 1、基本问题解决 基于问题，我们通过逻辑推理，用最基本方法：将一容器内的油向另外的容器中倾倒的方法，得出下面两种分油方法（方法1和方法2），并运用动态规划模型的思想列出表格，最终得出结果。 方法1 各容器油量的变化过程如下 操作顺序 A（斤） B(斤） C（斤） A 10 0 0 A→B 3 7 0 B→C 3 4 3 C→A 6 4 0 B→C 6 1 3 C→A 9 1 0 B→C 9 0 1 A→B 2 7 1 B→C 2 5 3 方法2 各容器油量的变化过程如下 操作顺序 A（斤） B(斤） C（斤） A 10 0 0 A→C 7 0 0 C→B 7 3 0 A→C 4 3 3 C→B 4 6 0 A→C 1 6 3 C→B 1 7 2 B→A 8 0 2 C→B 8 2 0 A→C 5 2 3 2.模型构成 分油问题可看作一个多步决策问题，记第倒油时，B中的油量为，C中的油量为，将二维向量定义为状态，我们用序数组的变化来表示整个倒油过程，集合 （1） 称为状态集合，由于每次都以为着摸一个容器被灌满或者被倒空，所以允许状态集合为 （2） 记次倒油时，B容器内的油改变量为，C内油的改变量为，将二维向量定义为决策，则允许决策集合为D，由各容器的的容量可知 （3） 状态变化规律是 （4） （4）式称为状态转移律，则制定分油方案归结为如下的多步决策问题： 求决策，使状态按照状态转移律（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）。 4.结果分析 将图1，图2画在同一坐标轴上，如图3（虚线为图1方案，实线为图2方案），可看到X轴上坐标1,2,3,4,5,6,7都曾被箭头所指，从而可知，利用这三个容器可分出1,2,3,4,5,6,7,斤油。这里并不要求A的容量一定是10斤。 5.模型评价与推广 对于这个分油问题，我们可拓展思路，提出疑问，即3个容器A,B.C的容量分别为斤，；现容器A中装满斤油，B,C为空，如何利用容器将斤油二等分？ 当c=1时，自然可以将油分出1至b斤；当，时我们可以利用上述的