数学建模分油最优化模型.doc

楚雄师范学院
2013年数学建模培训第一次预赛论文

  题 目 分油最优化模型

          姓 名

          系（院） 数学系

          专 业 信息与计算科学

  2013 年 5 月 14 日

分油最优化模型

【摘要】 本文主要是针对分油问题建立动态规划模型，从特殊的分油问题利用图解法求出决策方案，最后用剩余类知识将其推广到一般的模型。
【关键字】 线性规划 图表显像法 作图法 递归作图

一、问题重述
有一个人用装10斤油的瓶装了一瓶油拿到市场上去卖，正好来了两个买油的，每人要买5斤，但是没有秤，只有二只空瓶，一个能装7斤油，另一个能装3斤油。试建立模型分析应如何用这3个瓶把10斤油分成两份各为5斤的油。

二、问题分析
这是韩信分油法，首先将上述的问题表述为数学语言：现有三个无刻度的容器A、BC，容量分别为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）。
3
2
1
0
1
2
3
4
5
6
7
A
B
C
图（1），分油问题方案1

3
2
1
0
1
2
3
4
5
6
7
A
B
C
图（2），分油问题方案2

4.结果分析 将图1，图2画在同一坐标轴上，如图3（虚线为图1方案，实线为图2方案），可看到X轴上坐标1,2,3,4,5,6,7都曾被箭头所指，从而可知，利用这三个容器可分出1,2,3,4,5,6,7,斤油。这里并不要求A的容量一定是10斤。

3
2
1
0
1
2
3
4
5
6
7
A
B
C
图（3），分油结果

5.模型评价与推广 对于这个分油问题，我们可拓展思路，提出疑问，即3个容器A,B.C的容量分别为斤，；现容器A中装满斤油，B,C为空，如何利用容器将斤油二等分？
当c=1时，自然可以将油分出1至b斤；当，时我们可以利用上述的图解法，对问题进行求解，也可以将油分出1至b斤。

参考文献
【1】数学建模教育与国际数学建模竞赛 《工科数学》专辑。
【2】数学模型，姜启源编，高等教育出版社(1987年第一版，1993年第二版，2003年第三版；第一版在 1992年国家教委举办的第二届全国优秀教材评选中获"全国优秀教材奖")．
【3】数学模型与计算机模拟，江裕钊、辛培情编，电子科技大学出版社，(1989)．数学模型选谈(走向数学从书)，华罗庚，王元著，王克译，湖南教育出版社；(1991)．
【4】数学建模--方法与范例，寿纪麟等编，西安交通大学出版社(1993)．