|
设
备
分
配
问
题
小组组员:
学号:1101110033
学号:1101110032
学号:1101110019
班级:信息与计算科学
摘要
动态规划是解决多阶段决策过程最优化问题的一种方法。1951年美国数学家贝尔曼等人,根据一类多阶段决策问题的特性,提出了解决这类问题的“最优性原理”,并研究了许多实际问题,从而创建了最优化问题的一种新方法——动态规划。动态规划在工程技术、管理、经济、工业生产、军事及现代控制工程等方面都有广泛的应用,而且由于动态规划方法有独特之处,在解决某些实际问题时,显得更加方便有效。由于决策过程的时间参数有离散的和连续的情况,故决策过程分为离散决策过程和连续离散过程。动态规划是解决最优控制的一种重要方法之一,算法的优点有:(1)易于确定全局最优解;(2)能得到一族解,有利于分析结果;(3)能利用经验,提高求解的效率。动态规划方法虽然存在许多不足之处,但随着计算机的日益普及,动态规划的应用越来越广泛,它能够巧妙地解决科学技术和实际生活中的许多实例。
本题研究的是电信设备分配问题,也即是资源分配问题,资源分配问题可以是多阶段决策过程,也可以是静态规划问题,都能构造动态规划模型求解。此次模型是一个明显的利用动态规划相关知识来解决的最优化问题,即是效益最大化问题。本论文通过对动态规划的基本概念和基本思路的认识理解,并利用Matlab对规划中的资源设备分配问题进行了分析,然后利用Matlab语言进行了程序设计和计算,使复杂问题简单化,避免了繁琐的计算,从而使问题能更方便地得到解决。
关键词:动态规划、资源分配问题、Matlab语言
一、问题重述:
根据题目给出的问题,起始甲、乙、丙三支局具有的设备带来的效益分别是38、40、48万元,现有四套新设备要分给甲、乙、丙三支局,如果每支局分配的新设备套数不一样那么各支局最后所得到的收益也就不相同。而如何分配才能使总收益达到最大化,就成了现在我们需要讨论的一个问题,在这里我们按照各支局的收益进行了分配和处理比较,以便得出更好的实行方案。
按照使总收益最大的情况下,首先我们对设备的分配规定一个顺序,即先考虑分配给甲支局,其次乙支局,最后丙支局。然后通过MATLAB编程对数据的处理,来解决总收益最大问题。各支局具体收益情况如下表所示:
(单位:万元)
问:应如何分配,使总收益最大?
二、问题分析:
动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种特殊算法,因而,它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。除了要对基本概念和方法正确理解外,应以丰富的想象力去建立模型,用创造性的技巧去求解。
此题是一个资源分配问题,首先所谓的资源分配问题就是将数量一定的一种或若干种资源(例如原材料、资金、机器设备、劳力、食品、人力、设备等等),恰当地分配给若干个使用者,而使使用者效益达到最大化也即是使目标函数达到最优化。本题是把四套电信设备分配给甲、乙、丙三支局并使总效益达到最大化,本题可根据题意与动态规划基本知识可以把问题按支局分为三个阶段,甲、乙、丙三个支局分别编号为1、2、3。
三、基本假设:
1、假设四套设备都是一样的,都是完好无损的;
2、假设各支局的运行与应用环境是一样的;
3、假设甲、乙、丙三支局的设备维修费用一样;
4、假设设备的分配不受人为因素的影响;
5、假设设备的工作效率是一样的。
6、假设不受外界因素的影响,只考虑甲、乙、丙所分配到的设备。
四、符号说明:
k:表示第k支局要分配的设备套数(阶段数阶段k=1,2,3);
xk:表示分配给第k个支局至第3个支局的设备套数,即第k阶段初尚未分配的设备套数(状态变量);
uk:表示分配给第k支局的设备套数(决策变量);
gk(uk):表示uk台设备分配到第k个支局所得的收益值;
fk(xk):表示将xk台设备分配到第k个支局至第3阶段所得到的最大收益值;
max:表示最大值。
五、模型建立:
将问题按分配过程分为三个阶段k=1,2,3,根据动态规划逆序算法。
用逆推法得到基本递推方程为:
当
时
当
时,
当
时,
六、模型求解:
1、k=3时,丙地区的分配方案和总收益。
最大收益:f3(x3)=max[g3(x3)] (uk=0,1,2,3,4,5,6)
即是第三阶段:设将x3套设备(x3=0,1,2,3,4)全部分给支局丙时,则最大效益为f3(x3)=max[g3(u3)],其中u3=x3=0,1,2,3,4因为此时只有一个支局丙,故有多少套设备就全部分配给支局丙,因此它的效益值就是该段的最大效益值,如下表:
u3 x3 |
g3(u3) |
f3(x3) |
|
||||
0 |
1 |
2 |
3 |
4 |
|||
0 |
48 |
|
|
|
|
48 |
0 |
1 |
|
64 |
|
|
|
64 |
1 |
2 |
|
|
68 |
|
|
68 |
2 |
3 |
|
|
|
78 |
|
78 |
3 |
4 |
|
|
|
|
78 |
78 |
4 |
其中
表示f3(x3)为最大值时的最优决策。
2、k=2时,支局乙的分配方案和总收益。
最大收益:
即是第二阶段:设把x2套设备分给支局乙和丙,则对每一个x2(x2=0,1,2,3,4)值都有一个最优化分配方案,使其最大效益为:
f2(x2)=max[g2(u2)+ f3(x2-u2)],其中u2=0,1,2,3,4;因为分给乙支局u2套,其效益为g2(u2),余下的x2-u2套就分给丙支局,则它的效益最大值为f3(x2-u2),现要选择x2的值,使得g2(u2)+ f3(x2-u2)取得最大值,其数值计算如下所示:
u2 x2 |
g2(u2)+ f3(x2-u2) |
f2(x2) |
|
||||
0 |
1 |
2 |
3 |
4 |
|||
0 |
40 |
|
|
|
|
88 |
0 |
1 |
40+64 |
42+48 |
|
|
|
104 |
0 |
2 |
40+68 |
42+68 |
50+48 |
|
|
110 |
1 |
3 |
40+78 |
42+68 |
50+64 |
60+48 |
|
118 |
0 |
4 |
40+78 |
42+78 |
50+68 |
60+64 |
66+48 |
124 |
3 |
3、k=1时,市场甲的分配方案和总收益。
最大收益:f1(x1)=max[g1(u1)+f2(x1-u1)]=max[g1(u1)+f2(4-u1)]
即是第一阶段:设把x1套设备分给甲、乙、丙三个支局时,此时x1只有一种情况即是x1=5,则最大效益值为:
f1(x1)=max[g1(u1)+f2(x1- u1)], 其中u1=0,1,2,3,4;因为分给甲支局了u1套,其效益为g1(u1),剩下的x1- u1套也即是5-u1套分给乙和丙两个支局,则它的效益最大值为f2(x1- u1),现要选择u1的值,使得g1(u1)+f2(x1- u1)取最大值,它就是所求的总效益最大值,其数值计算如下:
u1 x1 |
g1(u1)+ f2(x1-u1) |
f2(x1) |
|
||||
0 |
1 |
2 |
3 |
4 |
|||
4 |
38+124 |
41+118 |
48+110 |
60+104 |
66+88 |
164 |
3 |
综上所述最大收益为164,具体分配方案为分给甲支局3套,乙支局0套,丙支局一套。
七、利用Matlab解题:
7.1算法流程图:
7.2运用Matlab语言编程解决问题,程序如下:
clear
>> m=1;
A=[48 64 68 78 78];
B=[88 104 110 118 124];
C=[0 0 0 0 164];
for i=1:5
for j=1:5
for k=1:5
if i+j+k==7
d(m)=A(i)+B(j)+C(k);
E(m,1)=i;
E(m,2)=j;
E(m,3)=k;
m=m+1;
else
continue;
end
end
end
end
MAXNum=d(1);
for l=1:size(d,2)
if d(l)>MAXNum
MAXNum=d(1);
p=1;
else
continue;
end
end
for l=1:size(d,2)
if d(l)=MAXNum
E(1,:)
else
continue;
end
end
MAXNum
程序运行结果:
ans =
3 0 1
MAXNum =
164
然后可以容易得到最大利润为164,最优分配方案有一个:(3,0,1)。
这样通过计算机的运行可以方便简洁的得到结果,避免了繁琐的计算,大大降低了工作量。
八、模型评价与总结:
通过本次建立模型并求解,让我们了解到了做动态规划这样的问题,我们可以按下列步骤进行:
( = 1 \* roman i)将过程划分成恰当的阶段。
( = 2 \* roman ii)正确选择状态变量
,使它既能描述过程的状态,又满足无后效性,同时确定允许状态集合
。
( = 3 \* roman iii)选择决策变量
,确定允许决策集合
。
( = 4 \* roman iv)写出状态转移方程。
( = 5 \* roman v)确定阶段指标
及指标函数
的形式(阶段指标之和,阶段指标之积,阶段指标之极大或极小等)。
( = 6 \* roman vi)写出基本方程即最优值函数满足的递归方程,以及端点条件。
九、模型的推广:
本文是综合利用了多层次目标规划进行解答的,在解答过程中也运用了静态方法,在实际生活和工作中,多层次目标规划是常常遇见的问题,即所要考虑的目标不单单是一个,当有多个目标时,我们要求得一个相对优化的解,使得它在多个目标里能综合考虑各个目标。所以此模型可以运用到其他任何资源分配问题上去求解,如:超市进货怎样才能利益最大化问题、工厂怎样安排生产才能得到最大利益等等,都可用此模型中的方法解答。
十、参考文献:
[1]戴朝寿,孙世亮。数学建模建明教材[M]。北京:高等教育出版社,2007。
[2]姜启源,谢金星,叶俊。数学建模[M]。北京:高等教育出版社。2003
[3]叶其孝。大学生数学建模竞赛辅导教材(二)[M]。长沙:湖南教育出版社,1997.
[4]曾文艺。数学建模简明教程[M]。北京:人民教育出版社,2003.
[5]刘卫国,陈昭平。MATLABA程序设计与应用[M]。第2版。北京:高等教育出版社,2006
附录:
动态规划是运筹学的一个分支,它是解决多阶段决策过程最优化问题的一种数学方法。1951年美国数学家贝尔曼(R.Bellman)等人,根据一类多阶段决策问题的特点,提出了解决这类问题的“最优性原理”,研究了许多实际问题,从而创建了解决最优化问题的一种新方法——动态规划。
动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题。
1、阶段和阶段变量
一个阶段就是在多段决策过程中,需要作出一个决策的子问题部分,通常按决策时间和空间顺序划分的,用字母k表示。
2、 状态和状态变量
状态就是描述系统情况所必须的信息,状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。按照过程进行的先后,每个阶段状态分为初始状态和终止状态。阶段k的初始状态表示为
\* MERGEFORMAT
,终止状态表示为
\* MERGEFORMAT
。状态变量的取值有一定允许集合或范围,称为状态可能集,用
\* MERGEFORMAT
表示,其中
\* MERGEFORMAT
。
3、 决策,决策变量和决策序列
决策就是确定系统过程发展的方案,实质是关于状态的选择。阶段决策就是决策者从本阶段状态出发对下一阶段所作出的选择。在阶段k,如果给出了决策变量
\* MERGEFORMAT
随状态变量
\* MERGEFORMAT
变化的对应关系,我们就确定了根据不同当前状态作出不同决策的规则,既是决策变量
\* MERGEFORMAT
是状态变量
\* MERGEFORMAT
的函数,称为决策函数,记为
\* MERGEFORMAT
。决策变量的取值也有一定的取值范围,称为允许决策集合,记为
\* MERGEFORMAT
。
决策序列也叫政策,策略。整个n段决策过程依次进行的n个阶段决策构成的决策序列表示为:
\* MERGEFORMAT
。
4、 状态转移方程
系统在阶段k处于状态
\* MERGEFORMAT
,执行决策
\* MERGEFORMAT
的结果是系统状态的转移,既系统由阶段k的初始状态
\* MERGEFORMAT
转移到终止状态
\* MERGEFORMAT
,亦即是阶段k的状态
\* MERGEFORMAT
转移到阶段k+1的状态
\* MERGEFORMAT
,多阶段决策过程的发展就是这样用阶段状态的相继演变来描述的。对于具有无后效性的多段决策过程,系统由阶段k到阶段k+1的状态转移方程是:
\* MERGEFORMAT
,就是说,阶段k+1的状态
\* MERGEFORMAT
完全由阶段k的状态
\* MERGEFORMAT
和决策
\* MERGEFORMAT
确定,与系统过去的决策和状态都无关。其中
\* MERGEFORMAT
称为变换函数或变换算子。
5、阶段效益和目标函数
效益函数(又称目标函数)是用来衡量所实现过程优劣的一种数量指标,它是定义在过程上的数量函数,用
\* MERGEFORMAT
表示:
\* MERGEFORMAT
阶段效益(又称阶段指标)是衡量阶段效果的数量指标,它是执行决策是所带来的目标函数值的增量,用
\* MERGEFORMAT
来表示。
目标函数
\* MERGEFORMAT
的最优值,称为最优函数目标值,记为
\* MERGEFORMAT
,它表示从第k阶段状态
\* MERGEFORMAT
出发到过程结束时所获得的最优目标值。
(1) 适于动态规划求解的问题的目标函数,必须具有关于阶段效应的可分离形式,k子过程的目标函数可表示为:
\* MERGEFORMAT
,其中
\* MERGEFORMAT
表示某种运算,可以是加,减,乘,除等。。
Powered by Discuz! X2.5 © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 ) 论坛法律顾问:王兆丰
GMT+8, 2025-8-13 00:59 , Processed in 0.296465 second(s), 27 queries .