实验十遗传算法与优化问题
一、问题背景与实验目的
遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位．
本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算．1．遗传算法的基本原理
遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）．
（1）遗传算法中的生物遗传学概念
由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念．
首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下：
序号遗传学概念遗传算法概念数学概念
1 个体要处理的基本对象、结构也就是可行解
2 群体个体的集合被选定的一组可行解
3 染色体个体的表现形式可行解的编码
4 基因染色体中的元素编码中的元素
5 基因位某一基因在染色体中的位置元素在编码中的位置
6 适应值个体对于环境的适应程度，
或在环境压力下的生存能力可行解所对应的适应函数值
7 种群被选定的一组染色体或个体根据入选概率定出的一组
可行解
8 选择从群体中选择优胜的个体，
淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解
9 交叉一组染色体上对应基因段的
交换根据交叉原则产生的一组新解
10 交叉概率染色体对应基因段交换的概
率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.90
11 变异染色体水平上基因变化编码的某些元素被改变
12
变异概率
染色体上基因变化的概率（可能性大小） 开区间(0,1)内的一个值, 一般为0.001~0.01
13 进化、 适者生存 个体进行优胜劣汰的进化，一代又一代地优化 目标函数取到最大值，最
优的可行解 （2）遗传算法的步骤
遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或称为算子）：选择（Selection ）、交叉（Crossover ）、变异（Mutation ）．
遗传算法基本步骤主要是：先把问题的解表示成“染色体”，在算法中也就是以二进制编码的串，在执行遗传算法之前，给出一群“染色体”，也就是假设的可行解．然后，把这些假设的可行解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群．经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解．
下面给出遗传算法的具体步骤，流程图参见图1：
第一步：选择编码策略，把参数集合（可行解集合）转换染色体结构空间； 第二步：定义适应函数，便于计算适应值；
第三步：确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；
第四步：随机产生初始化群体；
第五步：计算群体中的个体或染色体解码后的适应值；
第六步：按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；
第七步：判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数，不满足则返回第五步、或者修改遗传策略再返回第六步．
图1 一个遗传算法的具体步骤
产生初始群体
是否满足终止条件
得到结果
结束程序
是
否
计算每个个体的适应值
以概率选择遗传算子
选择一个个体复制到新群体 选择两个个体进行交叉插入到新群体 选择一个个体进行变异插入到新群体
得到新群体
遗传算法有很多种具体的不同实现过程，以上介绍的是标准遗传算法的主要步骤，此算法会一直运行直到找到满足条件的最优解为止．
2．遗传算法的实际应用
例1：设2()20.5f x x x =-++，求 max (), [1,2]f x x ∈-．
注：这是一个非常简单的二次函数求极值的问题，相信大家都会做．在此我们要研究的不是问题本身，而是借此来说明如何通过遗传算法分析和解决问题．
在此将细化地给出遗传算法的整个过程． （1）编码和产生初始群体 首先第一步要确定编码的策略，也就是说如何把1-到2这个区间内的数用计算机语言表示出来．
编码就是表现型到基因型的映射，编码时要注意以下三个原则：
完备性：问题空间中所有点（潜在解）都能成为GA 编码空间中的点（染色体位串）的表现型；
健全性：GA 编码空间中的染色体位串必须对应问题空间中的某一潜在解； 非冗余性：染色体和潜在解必须一一对应．
这里我们通过采用二进制的形式来解决编码问题，将某个变量值代表的个体表示为一个{0，1}二进制串．当然，串长取决于求解的精度．如果要设定求解精度到六位小数，由于区间长度为2(1)3--=，则必须将闭区间 [1,2]-分为6310?等分．因为216222097152231024194304=
将一个二进制串（b 21b 20b 19…b 1b 0）转化为区间[1,2]-内对应的实数值很简单，只需采取以下两步（Matlab 程序参见附录4）：
1）将一个二进制串（b 21b 20b 19…b 1b 0）代表的二进制数化为10进制数：
21
212019102100
()(2)'i i i b b b b b b x =?=?=∑
2）'x 对应的区间[1,2]-内的实数：
12)1(2'122---?
+-=x x
例如，一个二进制串a=<1000101110110101000111>表示实数0.637197． 'x =(1000101110110101000111)2=2288967
637197
.0123
2288967122=-?+-=x
二进制串<0000000000000000000000>，<1111111111111111111111>，则分别表示区间的两个端点值-1和2．
利用这种方法我们就完成了遗传算法的第一步——编码，这种二进制编码的方法完全符合上述的编码的三个原则．
首先我们来随机的产生一个个体数为4个的初始群体如下： pop(1)={
<1101011101001100011110>， %% a1 <1000011001010001000010>， %% a2 <0001100111010110000000>， %% a3
<0110101001101110010101>} %% a4（Matlab 程序参见附录2） 化成十进制的数分别为：
pop(1)={ 1.523032，0.574022 ，-0.697235 ，0.247238 } 接下来我们就要解决每个染色体个体的适应值问题了． （2）定义适应函数和适应值
由于给定的目标函数2()20.5f x x x =-++在[1,2]-内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础．
对于本题中的最大化问题，定义适应函数()g x ，采用下述方法：
min min (), ()0
()0,f x F f x F g x -->?=?
?
若其他 式中min F 既可以是特定的输入值，也可以是当前所有代或最近K 代中()f x 的最小值，这里为了便于计算，将采用了一个特定的输入值．
若取min 1F =-，则当()1f x =时适应函数()2g x =；当() 1.1f x =-时适应函数
()0g x =．
由上述所随机产生的初始群体，我们可以先计算出目标函数值分别如下（Matlab 程序参见附录3）：
f [pop(1)]={ 1.226437 , 1.318543 , -1.380607 , 0.933350 } 然后通过适应函数计算出适应值分别如下（Matlab 程序参见附录5、附录6）： 取min 1F =-，
g[pop(1)]= { 2.226437 , 2.318543 , 0 , 1.933350 } （3）确定选择标准
这里我们用到了适应值的比例来作为选择的标准，得到的每个个体的适应值比例叫作入选概率．其计算公式如下：
对于给定的规模为n 的群体pop={123,,,,n a a a a }，
个体i a 的适应值为()i g a ，则其入选概率为
1
()
(),1,2,3,,()
i s i n
i
i g a P a i n g a ==
=?∑
由上述给出的群体，我们可以计算出各个个体的入选概率． 首先可得
4
1
() 6.47833
0i
i g a
==∑， 然后分别用四个个体的适应值去除以4
1
()i i g a =∑，得：
P (a 1)=2.226437 / 6.478330 = 0.343675 %% a 1
P (a 2)=2.318543 / 6.478330 = 0.357892 %% a 2 P (a 3)= 0 / 6.478330 = 0 %% a 3
P (a 4)=1.933350 / 6.478330 = 0.298433 %% a 4（Matlab 程序参见附录7） （4）产生种群
计算完了入选概率后，就将入选概率大的个体选入种群，淘汰概率小的个体，并用入选概率最大的个体补入种群，得到与原群体大小同样的种群（Matlab 程序参见附录8、附录11）．
要说明的是：附录11的算法与这里不完全相同．为保证收敛性，附录11的算法作了修正，采用了最佳个体保存方法（elitist model），具体内容将在后面给出介绍．
由初始群体的入选概率我们淘汰掉a3，再加入a2补足成与群体同样大小的种群得到newpop(1)如下：
newpop(1)={
<1101011101001100011110>，%% a1
<1000011001010001000010>，%% a2
<1000011001010001000010>，%% a2
<0110101001101110010101>} %% a4
（5）交叉
交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体（Matlab程序参见附录9）．
我们把之前得到的newpop(1)的四个个体两两组成一对，重复的不配对，进行交叉．（可以在任一位进行交叉）
<110101110 1001100011110>，<1101011101010001000010>
交叉得：
<100001100 1010001000010>，<1000011001001100011110>
<10000110010100 01000010>，<1000011001010010010101>
交叉得：
<01101010011011 10010101>，<0110101001101101000010>
通过交叉得到了四个新个体，得到新的群体jchpop (1)如下：
jchpop(1)={
<1101011101010001000010>，
<1000011001001100011110>，
<1000011001010010010101>，
<0110101001101101000010>}
这里采用的是单点交叉的方法，当然还有多点交叉的方法，不过有些烦琐，这里就不着重介绍了．
（6）变异
变异也就是通过一个小概率改变染色体位串上的某个基因（Matlab程序参见附录10）．
现把刚得到的jchpop(1)中第3个个体中的第9位改变，就产生了变异，得到了新的群体pop(2)如下：
pop(2)= {
<1101011101010001000010>，
<1000011001001100011110>，
<1000011011010010010101>，
<0110101001101101000010> }
然后重复上述的选择、交叉、变异直到满足终止条件为止．
（7）终止条件
遗传算法的终止条件有两类常见条件：（1）采用设定最大（遗传）代数的方法，一般可设定为50代，此时就可能得出最优解．此种方法简单易行，但可能不是很精确（Matlab 程序参见附录1）；（2）根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制．
3．遗传算法的收敛性
前面我们已经就遗传算法中的编码、适应度函数、选择、交叉和变异等主要操作的基本内容及设计进行了详细的介绍．作为一种搜索算法，遗传算法通过对这些操作的适当设计和运行，可以实现兼顾全局搜索和局部搜索的所谓均衡搜索，具体实现见下图2所示．
图2 均衡搜索的具体实现图示
应该指出的是，遗传算法虽然可以实现均衡的搜索，并且在许多复杂问题的求解中往往能得到满意的结果，但是该算法的全局优化收敛性的理论分析尚待解决．目前普遍认为，标准遗传算法并不保证全局最优收敛．但是，在一定的约束条件下，遗传算法可以实现这一点．
下面我们不加证明地罗列几个定理或定义，供读者参考（在这些定理的证明中，要用到许多概率论知识，特别是有关马尔可夫链的理论，读者可参阅有关文献）．
定理 1 如果变异概率为)1,0(∈m P ，交叉概率为]1,0[∈c P ，同时采用比例选择法（按个体适应度占群体适应度的比例进行复制），则标准遗传算法的变换矩阵P 是基本的．
定理2 标准遗传算法（参数如定理1）不能收敛至全局最优解．
由定理2可以知道，具有变异概率)1,0(∈m P ，交叉概率为]1,0[∈c P 以及按比例选择的标准遗传算法是不能收敛至全局最最优解．我们在前面求解例1时所用的方法就是满足定理1的条件的方法．这无疑是一个令人沮丧的结论．
然而，庆幸的是，只要对标准遗传算法作一些改进，就能够保证其收敛性．具体如下：我们对标准遗传算法作一定改进，即不按比例进行选择，而是保留当前所得的最优解（称作超个体）．该超个体不参与遗传．
最佳个体保存方法（elitist model ）的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中．此种选择操作又称复制（copy ）．De Jong 对此方法作了如下定义：
定义设到时刻t（第t代）时，群体中a*（t）为最佳个体．又设A（t＋1）为新一代群体，若A（t＋1）中不存在a*（t），则把a*(t)作为A（t＋1）中的第n+1个个体（其中，n为群体大小）（Matlab程序参见附录11）．
采用此选择方法的优点是，进化过程中某一代的最优解可不被交叉和变异操作所破坏．但是，这也隐含了一种危机，即局部最优个体的遗传基因会急速增加而使进化有可能限于局部解．也就是说，该方法的全局搜索能力差，它更适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索．所以此方法一般都与其他选择方法结合使用．
定理3具有定理1所示参数，且在选择后保留当前最优值的遗传算法最终能收敛到全局最优解．
当然，在选择算子作用后保留当前最优解是一项比较复杂的工作，因为该解在选择算子作用后可能丢失．但是定理3至少表明了这种改进的遗传算法能够收敛至全局最优解．有意思的是，实际上只要在选择前保留当前最优解，就可以保证收敛，定理4描述了这种情况．
定理4具有定理1参数的，且在选择前保留当前最优解的遗传算法可收敛于全局最优解．
例2：设2
f x x∈，编码长度为5，采用上述
=-+，求max(),[0,2]
f x x x
()3
定理4所述的“在选择前保留当前最优解的遗传算法”进行．
此略，留作练习．
二、相关函数（命令）及简介
本实验的程序中用到如下一些基本的Matlab函数：ones, zeros, sum, size, length, subs, double 等，以及for, while 等基本程序结构语句，读者可参考前面专门关于Matlab的介绍，也可参考其他数学实验章节中的“相关函数（命令）及简介”内容，此略．
三、实验内容
上述例1的求解过程为：
群体中包含六个染色体，每个染色体用22位0—1码，变异概率为0.01，变量区间为[1,2]
-，遗传代数为50代，则运用第一种终止条件（指-，取Fmin=2
定遗传代数）的Matlab程序为：
[Count,Result,BestMember]=Genetic1(22,6,'-x*x+2*x+0.5',-1,2,-2,0.01,50)
执行结果为：
Count =
50
Result =
1.0316 1.0316 1.0316 1.0316 1.0316 1.0316
1.4990 1.4990 1.4990 1.4990 1.4990 1.4990
BestMember =
1.0316
1.4990
图2 例1的计算结果
（注：上图为遗传进化过程中每一代的个体最大适应度；
而下图为目前为止的个体最大适应度——单调递增）
我们通过Matlab软件实现了遗传算法，得到了这题在第一种终止条件下的最优解：当x取1.0316时，Max () 1.4990
f x=．
当然这个解和实际情况还有一点出入（应该是x取1时，Max () 1.5000
f x=），但对于一个计算机算法来说已经很不错了．
我们也可以编制Matlab程序求在第二种终止条件下的最优解．此略，留作练习．实践表明，此时的遗传算法只要经过10代左右就可完成收敛，得到另一个“最优解”，与前面的最优解相差无几．
四、自己动手
1．用Matlab编制另一个主程序Genetic2.m，求例1的在第二种终止条件下的最优解．
提示：一个可能的函数调用形式以及相应的结果为：
[Count,Result,BestMember]=Genetic2(22,6,'-x*x+2*x+0.5',-1,2,-2,0.01,0.00001) Count =
13
Result =
1.0392 1.0392 1.0392 1.0392 1.0392 1.0392
1.4985 1.4985 1.4985 1.4985 1.4985 1.4985 BestMember =
1.0392
1.4985
可以看到：两组解都已经很接近实际结果，对于两种方法所产生的最优解差异很小．可见这两种终止算法都是可行的，而且可以知道对于例1的问题，遗传算法只要经过10代左右就可以完成收敛，达到一个最优解．
2．按照例2的具体要求，用遗传算法求上述例2的最优解．
3．附录9子程序Crossing.m中的第3行到第7行为注解语句．若去掉前面的%号，则程序的算法思想有什么变化？
4．附录9子程序Crossing.m中的第8行至第13行的程序表明，当Dim(1)>=3时，将交换数组Population的最后两行，即交换最后面的两个个体．其目的是什么？
5．仿照附录10子程序Mutation.m，修改附录9子程序Crossing.m，使得交叉过程也有一个概率值（一般取0.65~0.90）；同时适当修改主程序Genetic1.m或主程序Genetic2.m，以便代入交叉概率．
6．设2
f x x∈-，要设定求解精度到15位小数．
=--+，求max(),[2,2]
()41
f x x x
五、附录
附录1：主程序Genetic1.m
function
[Count,Result,BestMember]=Genetic1(MumberLength,MemberNumber,FunctionFitn ess,MinX,MaxX,Fmin,MutationProbability,Gen)
Population=PopulationInitialize(MumberLength,MemberNumber);
global Count;
global CurrentBest;
Count=1;
PopulationCode=Population;
PopulationFitness=Fitness(PopulationCode,FunctionFitness,MinX,MaxX,Mumbe rLength);
PopulationFitnessF=FitnessF(PopulationFitness,Fmin);
PopulationProbability=Probability(PopulationFitnessF);
[Population,CurrentBest,EachGenMaxFitness]=Elitist(PopulationCode,Populatio nFitness,MumberLength);
EachMaxFitness(Count)=EachGenMaxFitness;
MaxFitness(Count)=CurrentBest(length(CurrentBest));
while Count NewPopulation=Select(Population,PopulationProbability,MemberNumber); Population=NewPopulation; NewPopulation=Crossing(Population,FunctionFitness,MinX,MaxX,MumberLength); Population=NewPopulation; NewPopulation=Mutation(Population,MutationProbability); Population=NewPopulation; PopulationFitness=Fitness(Population,FunctionFitness,MinX,MaxX,MumberLength); PopulationFitnessF=FitnessF(PopulationFitness,Fmin); PopulationProbability=Probability(PopulationFitnessF); Count=Count+1; [NewPopulation,CurrentBest,EachGenMaxFitness]=Elitist(Population,PopulationFitn ess,MumberLength); EachMaxFitness(Count)=EachGenMaxFitness;; MaxFitness(Count)=CurrentBest(length(CurrentBest)); Population=NewPopulation; end Dim=size(Population); Result=ones(2,Dim(1)); for i=1:Dim(1) Result(1,i)=Translate(Population(i,:),MinX,MaxX,MumberLength); end Result(2,:)=PopulationFitness; BestMember(1,1)=Translate(CurrentBest(1:MumberLength),MinX,MaxX,Mumb erLength); BestMember(2,1)=CurrentBest(MumberLength+1); close all subplot(211) plot(EachMaxFitness) subplot(212) plot(MaxFitness) 【程序说明】主程序Genetic1.m包含了8个输入参数： (1) MumberLength：表示一个染色体位串的二进制长度．（例1中取22） (2) MemberNumber：表示群体中染色体的个数．（例1中取6个） (3) FunctionFitness：表示目标函数，是个字符串，因此用表达式时，用单引号括出．（例1中是2 =-++） f x x x ()20.5 (4) MinX：变量区间的下限．（例1中是[1,2] -中的） (5) MaxX：变量区间的上限．（例1中是[1,2] -中的2） (6) Fmin：定义适应函数过程中给出的一个目标函数的可能的最小值，由操作者自己给出．（例1中取Fmin=2 -） (7) MutationProbability：表示变异的概率，一般都很小．（例1中取0.01） (8) Gen：表示遗传的代数，也就是终止程序时的代数．（例1中取50） 另外，主程序Genetic1.m包含了3个输出值：Count 表示遗传的代数；Result 表示计算的结果，也就是最优解；BestMember表示最优个体及其适应值． 附录2：子程序PopulationInitialize.m function Population=PopulationInitialize(MumberLength,MemberNumber) Temporary=rand(MemberNumber,MumberLength); Population=(Temporary>=0.5*ones(size(Temporary))); 【程序说明】子程序PopulationInitialize.m用于产生一个初始群体．这个初始群体含有MemberNumber个染色体，每个染色体有MumberLength个基因（二进制码）． 附录3：子程序Fitness.m function PopulationFitness= Fitness(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength) Dim=size(PopulationCode); PopulationFitness=zeros(1,Dim(1)); for i=1:Dim(1) PopulationFitness(i)= Transfer(PopulationCode(i,:),FunctionFitness,MinX,MaxX,MumberLength); end 【程序说明】子程序Fitness.m用于计算群体中每一个染色体的目标函数值．子程序中含有5个输入参数：PopulationCode表示用0—1代码表示的群体，FunctionFitness 表示目标函数，它是一个字符串，因此写入调用程序时，应该用单引号括出，MumberLength表示染色体位串的二进制长度．MinX和MaxX 分别指变量区间的上下限． 附录4：子程序Translate.m function PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength) PopulationData=0; Dim=size(PopulationCode); for i=1:Dim(2) PopulationData=PopulationData+PopulationCode(i)*(2^(MumberLength-i)); end PopulationData=MinX+PopulationData*(MaxX-MinX)/(2^Dim(2)-1); 【程序说明】子程序Translate.m把编成码的群体翻译成变量的数值．含有4个输入参数，PopulationCode, MinX, MaxX, MumberLength． 附录5：子程序Transfer.m function PopulationFitness= Transfer(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength) PopulationFitness=0; PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength); PopulationFitness=double(subs(FunctionFitness,'x',sym(PopulationData))); 【程序说明】子程序Transfer 把群体中的染色体的目标函数值用数值表示出来，它是Fitness的重要子程序．其有5个输入参数分别为PopulationCode, FunctionFitness, MinX, MaxX，MumberLength． 附录6：子程序FitnessF.m function PopulationFitnessF=FitnessF(PopulationFitness,Fmin) Dim=size(PopulationFitness); PopulationFitnessF=zeros(1,Dim(2)); for i=1:Dim(2) if PopulationFitness(i)>Fmin PopulationFitnessF(i)=PopulationFitness(i)-Fmin; end if PopulationFitness(i)<=Fmin PopulationFitnessF(i)=0; end end 【程序说明】子程序FitnessF.m是用于计算每个染色体的适应函数值的．其输入参数如下：PopulationFitness 为群体中染色体的目标函数值，Fmin为定义适应函数过程中给出的一个目标函数的可能的最小值． 附录7：子程序Probability.m function PopulationProbability=Probability(PopulationFitness) SumPopulationFitness=sum(PopulationFitness); PopulationProbability=PopulationFitness/SumPopulationFitness; 【程序说明】子程序Probability.m 用于计算群体中每个染色体的入选概率，输入参数为群体中染色体的适应函数值PopulationFitness． 附录8：子程序Select.m function NewPopulation= Select(Population,PopulationProbability,MemberNumber) CProbability(1)=PopulationProbability(1); for i=2:MemberNumber CProbability(i)=CProbability(i-1)+PopulationProbability(i); end for i=1:MemberNumber r=rand(1); Index=1; while r>CProbability(Index) Index=Index+1; end NewPopulation(i,:)=Population(Index,:); end 【程序说明】子程序Select.m 根据入选概率（计算累计概率）在群体中按比例选择部分染色体组成种群，该子程序的3个输入参数分别为：群体Population，入选概率PopulationProbability，群体中染色体的个数MemberNumber． 附录9：子程序Crossing.m function NewPopulation= Crossing(Population,FunctionFitness,MinX,MaxX,MumberLength) %%PopulationFitness= %% Fitness(Population,FunctionFitness,MinX,MaxX,MumberLength); %%PopulationProbability=Probability(PopulationFitness); %%[SortResult,SortSite]=sort(PopulationProbability); %%Population=Population(SortSite,:); Dim=size(Population); if Dim(1)>=3 Temp=Population(Dim(1),:); Population(Dim(1),:)=Population(Dim(1)-1,:); Population(Dim(1)-1,:)=Temp; end for i=1:2:Dim(1)-1 SiteArray=randperm(Dim(2)); Site=SiteArray(1); Temp=Population(i,1:Site); Population(i,1:Site)=Population(i+1,1:Site); Population(i+1,1:Site)=Temp; end NewPopulation=Population; 【程序说明】子程序Crossing.m 用于群体中的交叉并产生新群体．其输入参数为：Population, FunctionFitness，MinX，MaxX，MumberLength． 附录10：子程序Mutation.m function NewPopulation=Mutation(Population,MutationProbability) Dim=size(Population); for i=1:Dim(1) Probability=rand(1); Site=randperm(Dim(2)); if Probability if Population(i,Site(1))==1 Population(i,Site(1))=0; end if Population(i,Site(1))==0 Population(i,Site(1))=1; end end end NewPopulation=Population; 【程序说明】子程序Mutation.m用于群体中少量个体变量并产生新的群体．输入参数为：群体Population和变异概率MutationProbability． 附录11：子程序Elitist.m function [NewPopulationIncludeMax,CurrentBest,EachGenMaxFitness]= Elitist(Population,PopulationFitness,MumberLength) global Count CurrentBest; [MinFitness,MinSite]=min(PopulationFitness); [MaxFitness,MaxSite]=max(PopulationFitness); EachGenMaxFitness=MaxFitness; if Count==1 CurrentBest(1:MumberLength)=Population(MaxSite,:); CurrentBest(MumberLength+1)=PopulationFitness(MaxSite); else if CurrentBest(MumberLength+1) CurrentBest(1:MumberLength)=Population(MaxSite,:); CurrentBest(MumberLength+1)=PopulationFitness(MaxSite); end Population(MinSite,:)=CurrentBest(1:MumberLength); end NewPopulationIncludeMax=Population; 【程序说明】子程序Elitist.m用到最佳个体保存方法（“优胜劣汰”思想）．输入参数为：群体Population, 目标函数值PopulationFitness和染色体个数MumberLength． “遗传算法”专题 一、遗传算法的主要特征： 我们的目的是获得“最好解”，可以把这种任务看成是一个优化过程。对于小空间，经典的穷举法就足够了；而对大空间，则需要使用特殊的人工智能技术。遗传算法(Genetic Algorithm)是这些技术中的一种，它是一类模拟生物进化过程而产生的由选择算子、杂交算子和变异算子三个基本算子组成的全局寻优算法。它从一个初始族出发，由选择算子选出性状好的父本，由杂交算子进行杂交运算，变异算子进行少许变异，在一定概率规则控制下随机搜索模型空间。一代代进化，直到最终解族对应的误差泛函值达到设定的要求。 遗传算法的结构： 图1. 遗传算法的结构 在第t 次迭代，遗传算法维持一个潜在解的群体},,,{)(21t n t t x x x t p =。 每个解t i x 用其“适应值”评价。然后通过选择更合适个体（1+t 次迭代）形成一个新的群体。新的群体的成 员通过杂交和变异进行变换，形成新的解。杂交组合了两个亲体染色体（即待求参数的二进制编码串）的特征，通过交换父代相应的片断形成了两个相似的后代。例如父代染色体为 ),,,,(11111e d c b a 和),,,,(22222e d c b a ，在第二个基因后杂交，产生的后代为),,,,(22211e d c b a 和),,,,(11122e d c b a 。杂交算子的目的是在不同潜在解之间进行信息交换。变异是通过用一个等于变异率的概率随机地改变被选择染色体上的一个或多个基因（染色体中的一个二进制位）。变异算子的意图是向群体引入一些额外的变化性。 遗传算法的特点： (1). 它不是直接作用于参变量集上，而是作用于参变量的某种编码形成的数字串上。 (2). 它不是从单个点，而是从一个解族开始搜索解空间，与传统的“点对点”式的搜索方法 不同。 (3). 它仅仅利用适应值信息评估个体的优劣，无须求导数或其它辅助信息。 (4). 它利用概率转移规则，而非确定性规则。 ?优势： (1). 不容易陷入局部极值，能以很大的概率找到全局最优解。 Procedure Genetic Algorithm begin 0←t initialize )(t P evaluate )(t P while (not termination-condition) do begin 1+←t t select )(t P from )1(-t P alter )(t P evaluate )(t P end end (2). 由于其固有的并行性，适合于大规模并行计算。 二、遗传算法的运行步骤： 1. 一般性描述： 不失一般性，考虑求最大值的问题。问题： 1） 编码和解码： 要达到要求的精度，每个域i D 应该被分割为610)(?-i i a b 个等尺寸的区间。用i m 表示使1210)(6-≤?-i m i i a b 成立的最小整数。这样，对每个变量i x ，由串长为i m 的二进 制编码表达可以满足精度要求。以下的公式对应于每个串的自变量的值： 1 2)0011001(2--? +=m i i i i a b decimal a x 其中)(2string decimal 表示二进制串的十进制值。 代表一个潜在解的染色体被长度为∑==k i i m m 1的二进制串表达；前1m 位对应区间[11,b a ]里的一个值，随后的2m 位对应区间[22,b a ]里的一个值，等等；最后的k m 位对应区间[k k b a ,]里的一个值。 2） 产生潜在解初始群体： 简单地以位的方式随机地设定size pop _个染色体。如果确实有一些关于最优分布的知识，可以使用这些信息来设定初始潜在解的集合。 3） 根据适应值评价解的适应程度并据此生成新群体： 通常使用一个根据适应值调节刻度宽度的轮盘。按照如下方法构造轮盘（假设这里的适应值时正值，否则可以使用一些比例机制调整）： ● 计算每个染色体)_,,1(size pop i i =v 的适应值)(i eval v ； ● 计算群体的总适应值： ∑== size pop i i eval F _1 )(v ● 计算每个染色体)_,,1(size pop i i =v 的选择概率i p ： F eval p i i /)(v = ● 计算每个染色体)_,,1(size pop i i =v 的累计概率i q ： ∑∑====i j i i j j i p e v a l F q 1 1)(1v 对轮盘转动size pop _次，每次按照下面的方法为新群体选择一个单个的染色体： ● 产生一个在区间[0，1]里的随机数； ● 如果1q r <，则选择第一个染色体1v ；否则选择使i i q r q ≤<-1成立的第i 个染色体 求一个有k 个变量的函数R R x x x f k k → :),,,(21 的f 的最大值。假设每个变量i x 为域R b a D i i i ?=],[内的一个值，且对所有的i i D x ∈，0),,(1>k x x f 。假定以某个要求的精度优化函数f ：这里取自变量小数点后第6位。 i v (size pop i _2<≤)。 这样做的效果是：好的染色体得到多个拷贝，中等染色体保持平稳，最差染色体死 亡。 4） 杂交(crossover)和变异(mutation)——决定新群体的性状： 设杂交概率为c p ，此概率给出预计要进行杂交的染色体个数size pop p c _?。对于新群体中的每个染色体： ● 产生一个在区间[0，1]里的随机数r ； ● 如果c p r <，则选择给定的染色体进行杂交。 随机地对被选择的染色体配对：对染色体中的每一个，产生一个在区间[1, 1-m ]（m 为总长，即染色体位数）里的随机整数pos 。pos 表示杂交点的位置。两个染色体 )(121m pos pos b b b b b + 和 )(121m pos pos c c c c c + 被他们的子代 )(121m pos pos c c b b b + 和 )(121m pos pos b b c c c + 所替代。 下一步的变异，是在一位一位(bit-by-bit)的基础上进行的。另一个遗传系统参数，变异率m p ，给出了我们预计的变异位数：size pop m p m _??。整个群体中所有染色体的每一位都有均等的机会经历变异，即从0到1或者相反： ● 产生一个在区间[0，1]里的随机数r ； ● 如果m p r <，变异此位。 随着选择、杂交和变异的进行，新群体就为下一次的评价做好了准备。该评价是用 来为下一次选择过程建立概率分布的，即建立一个根据当前适应值构造宽距的轮盘。其它的部分只是上述步骤的循环重复，见图1。 2. 例子： 问题：求下列函数的极大值： )20sin()4sin(5.21),(221121x x x x x x f ππ?+?+=， 其中1.120.31≤≤-x 及8.51.42≤≤x 。假定对每个变量要求的精度是小数点后第4位。 图2. 函数)20sin()4sin(5.21),(221121x x x x x x f ππ?+?+=的图 按上面介绍的步骤求解此问题： 1） 解码和解码： 变量1x 的定义域长度为15.1，所要求的精度意味着区间[-3.0, 12.1]至少要被分为15.1×10000个等距区间。由于181721510002<<，因此染色体的第一部分需要18位。 变量2x 的定义域长度为1.7，所要求的精度意味着区间[4.1, 5.8]至少要被分为1.7×10000个等距区间。由于151********<<，因此染色体的第一部分需要15位。 因此染色体的总长度为331518=+=m 位，前18位为1x ，后15位为2x 。 例如，染色体 (010001001011010000111110010100010) 的前18位010001001011010000表示 052426.11 2) 0.3(1.12)110100000100010010(0.318 21=---? +-=decimal x ； 后15位111110010100010表示 755330.51 21 .48.5)000101111100101(1.41522=--?+=decimal x ； 所以该染色体对应于>>=<<755330.5,052426.1,21x x ，该染色体的适应值为 252640.20)755330.5 ,052426.1(=f 。 2） 产生潜在解初始群体： 设20_=size pop ，随机产生一个初始化的20个染色体组成的群体，并计算相应的适应函数值： 很明显，染色体15v 是最好的，2v 是最差的。 3） 根据适应值评价解的适应程度并据此生成新群体： 现在系统为选择过程建立一个轮盘。群体的总适应值为 776822.387)(20 1 == ∑=i i eval F v 对每个染色体)20,,2,1( =i i v ，选择概率i p 为： 每个染色体)20,,2,1( =i i v 的累计概率i q 为： 现在，准备转动轮盘20次，每次为新群体选择一个单个的染色体。假定在区间[0, 1]里的20个数的一个随机序列是： 0.513870 0.175741 0.308652 0.534534 0.947628 0.171736 0.702231 0.226431 0.494773 0.424720 0.703899 0.389647 0.277226 0.368071 0.983437 0.005398 0.765682 0.646473 0.767139 0.780237 第一个数513870.0=r 大于10q 而小于11q ，意味着染色体11v 被选择；第二个数175741.0=r 大于3q 而小于4q ，意味着染色体4v 被选择，等等。最后，新群体由以下染色体组成： 4） 杂交(crossover)和变异(mutation)——决定新群体的性状： 设杂交概率25.0=c p ，所以预计染色体中平均有25%（即20个中的5个）将经历杂交。杂交按照下面的方法进行：对新群体中的每个染色体，产生一个在区间[0, 1]里的随机数r ，如果25.0 这说明染色体2v '、11v '、13v '和18v '被选择杂交。这里很幸运，给选择的染色体数是偶数，可 以很容易地配对；如果选择的染色体数为奇数，可以加入一额外的染色体或者移走一被选择 染色体，这种选择同样是随机的。对被选择染色体随机进行配对：设为前两个（即2v '和11v '） 和后两个（即13 v '和18v '）被配对。对这两对中的每一对，产生区间[1, 32]（33为染色体总长度）里的一个随机整数pos 。数字表示杂交点的位置。第一对染色体是： 产生的数为9=pos 。这对染色体在第9位后的部分互换，生成新的一对染色体： 第二对染色体是： 产生的数为20=pos 。这对染色体在第20位后的部分互换，生成的新的染色体对为： 群体的当前版本为： 1. 什么是数学模型与数学建模 简单地说：数学模型就是对实际问题的一种数学表述。 具体一点说：数学模型是关于部分现实世界为某种目的的一个抽象的简化的数学结构。 更确切地说：数学模型就是对于一个特定的对象为了一个特定目标，根据特有的内在规律，做出一些必要的简化假设，运用适当的数学工具，得到的一个数学结构。数学结构可以是数学公式，算法、表格、图示等。 数学建模就是建立数学模型，建立数学模型的过程就是数学建模的过程（见数学建模过程流程图）。数学建模是一种数学的思考方法，是运用数学的语言和方法，通过抽象、简化建立能近似刻划并"解决"实际问题的一种强有力的数学手段。 2.美国大学生数学建模竞赛的由来： 1985年在美国出现了一种叫做MCM的一年一度大大学生数学模型（1987年全称为Mathematical Competition in Modeling,1988年改全称为Mathematical Contest in Modeling,其所写均为MCM）。这并不是偶然的。在1985年以前美国只有一种大学生数学竞赛（The william Lowell Putnam mathematial Competition,简称Putman(普特南）数学竞赛），这是由美国数学协会（MAA--即Mathematical Association of America的缩写）主持，于每年12月的第一个星期六分两试进行，每年一次。在国际上产生很大影响，现已成为国际性的大学生的一项著名赛事。该竞赛每年2月或3月进行。 我国自1989年首次参加这一竞赛，历届均取得优异成绩。经过数年参加美国赛表明，中国大学生在数学建模方面是有竞争力和创新联想能力的。为使这一赛事更广泛地展开，1990年先由中国工业与应用数学学会后与国家教委联合主办全国大学生数学建模竞赛（简称CMCM），该项赛事每年9月进行。 选路的优化模型 摘要: 本题是一个有深刻背景的NPC问题，文章分析了分组回路的拓扑结构，并构造了多个模型，从多个侧面对具体问题进行求解。最短树结构模型给出了局部寻优的准则算法模型体现了由简到繁，确保较优的思想而三个层次分明的表述模型证明了这一类问题共有的性质。在此基础上我们的结果也是比较令人满意的。如对第一题给出了总长为599.9，单项长为216的分组，第二题给出了至少分四组的证明。最后，我们还谈到了模型的优缺点及推广思想。 一、问题描述 “水大无情，人命关天”为考察灾情，县领导决定派人及早将各乡（镇），村巡视一遍。巡视路线为从县政府所在地出发，走遍各乡（镇），村又回到县政府所在地的路线。 1.若分三组巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2.假定巡视人员在各乡（镇）停留时间为T=2小时，在各村停留时间为t =1 小时， 汽车行驶速度为V=35公里/时，要在24小时内巡视完，至少分成几组；给出这 种分组下你认为最佳的巡视路线。 3.上述关于T，t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多 少？给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 4.巡视组数已定（如三组）要求尽快完成巡视，讨论T，t和V改变时最佳路线的 影响（图见附录）。 二、问题假设 1、乡（镇）村只考察一次，多次经过时只计算一次停留时间。 2、非本县村不限制通过。 3、汽车的行驶速度始终一致。 三、符号说明 第i 人走的回路Ti=vv i(i) v2(i)v n(i) Ti=00表示第i人在0点没移动 四、模型建立 在这一节里，我们将提出若干个模型及其特点分析，不涉及对题目的求解。 最简树结构模型 在这个模型中我们依靠利用最短树的特殊结构所给出的准则，进行局部寻优，在一个不大的图里，我们较易得到较优解。 (a)分片 准则1利用最短树的长度可大致的估算出路程长，在具体操作中，各片中 的最短路程长度不宜相差太大。 准则 2 尽可能将最短树连成一个回路，这可保证局部上路程是较短的。 (b)片内调整 a2 a3 a4 a5 a6假设a3 a4有路相连 细准1对于右图的最短树结构，最好的走法是a 若a3 a4 进去重复走的话，它与上述的走法路程差w(a3, a2)+w(a2 ,a5)+w(a4, a5)—w(a3, a4)。由两点间最小原则上式是大于0的优劣可见 细准2若有如图所示结构，一般思想是：将中间树枝上的点串到两旁树枝，以便连成回路。 五、模型求解 问题一该问题完全可以用均衡模型表述 用算法模型 1 经过局部优化手工多次比较我们能够给出的最佳结果为第一组路径为 0—P—28—27—26—N—24—23—22-17—16—1—15—1—18—K—21—20—25— M--0 长191.1 经5 镇6 村 第二组路径为 0—2—5—6—L—19—J—11--G—13—14—H—12—F—10—F—9—E—8—E—7—6—5—2—0 长216.5 经6 镇11 村第三组路径为O—2—3—D—4—D—3—C—B—1—A—34—35—33—31—32—30—Q—29 —R 长192.3 经6 镇11 村总长S=599.9 公里 由算法2 给出的为 1组0—P—29—R—31—33—A—34—35—32—30—Q—28—27—26—N—24—33—22—23—N—2 6—P—0 5 乡13 村长215.2 公里 2组0—M—25—21—K—17—16—I—15—I—18—K—21—25—20—L—19—J—11—G—13—14 —O 5 乡11 村长256.2 公里 3组 O—2—5—6—7—E—9--F—12--H--—12—F—10—F—9—E-8—4—0—7—6—M—5-2—3—L —13—1—0 8 乡11 村长256.3 公里 总长727.7 公里 数学模型按照不同的分类标准有许多种类： 1.按照模型的数学方法分，有几何模型，图论模型，微分方程模型。概率模型，最优控制模型，规划论模型，马氏链模型。 2.按模型的特征分，有静态模型和动态模型，确定性模型和随机模型，离散模型和连续性模型，线性模型和非线性模型。 3.按模型的应用领域分，有人口模型，交通模型，经济模型，生态模型，资源模型。环境模型。 4.按建模的目的分，有预测模型，优化模型，决策模型，控制模型等。 5.按对模型结构的了解程度分，有白箱模型，灰箱模型，黑箱模型。 数学建模的十大算法： 蒙特卡洛算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，比较好用的算法。） 数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用matlab作为工具。） 线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用lingo、lingdo软件实现）图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。） 动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题时用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需谨慎使用） 网格算法和穷举法（当重点讨论模型本身而情史算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 一些连续离散化方法（很多问题都是从实际来的，数据可以是连续的，而计算机只认得是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。） 图像处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用matlab来处理问题。） 数学建模方法 统计：1.预测与预报2.评价与决策3.分类与判别4.关联与因果 优化：5.优化与控制 预测与预报 ①灰色预测模型（必须掌握） 满足两个条件可用： a数据样本点个数少，6-15个 b数据呈现指数或曲线的形式 ②微分方程预测（备用） 无法直接找到原始数据之间的关系，但可以找到原始数据变化速度之间的关系，通过公式 数学建模的背景： 人们在观察、分析和研究一个现实对象时经常使用模型，如展览馆里的飞机模型、水坝模型，实际上，照片、玩具、地图、电路图等都是模型，它们能概括地、集中地反映现实对象的某些特征，从而帮助人们迅速、有效地了解并掌握那个对象。数学模型不过是更抽象些的模型。 当需要从定量的角度分析和研究一个实际问题时，人们就要在深入调查研究、了解对象信息、作出简化假设、分析内在规律等工作的基础上，用数学的符号和语言，把它表述为数学式子（称为数学模型），然后用通过计算得到的模型结果来解释实际问题，并接受实际的检验。这个全过程就称为数学建模。 近半个多世纪以来, 随着计算机技术的迅速发展，数学的应用不仅在工程技术、自然科学等领域发挥着越来越重要的作用, 而且以空前的广度和深度向经济、金融、生物、医学、环境、地质、人口、交通等新的领域渗透，所谓数学技术已经成为当代高新技术的重要组成部分。 不论是用数学方法在科技和生产领域解决哪类实际问题，还是与其它学科相结合形成交叉学科，首要的和关键的一步是建立研究对象的数学模型，并计算求解。人们常常把数学建模和计算机技术在知识经济时代的作用比喻为如虎添翼。 数学建模日益显示其重要作用，已成为现代应用数学的一个重要领域。为培养高质量、高层次人才，对理工、经济、金融、管理科学等各专业的大学生都提出“数学建模技能和素质方面的要求”。 数学建模在现代社会的一些作用 (1）在一般工程技术领域，数学建模仍然大有用武之地。在以声、光、热、力、电这些物理学科为基础的诸如机械、电机、土木、水利等工程技术领域中，数学建模的普遍性和重要性不言而喻，虽然这里的基本模型是已有的，但是由于新技术、新工艺的不断涌现，提出了许多需要用数学方法解决的新问题；高速、大型计算机的飞速发展，使得过去即便有了数学模型也无法求解的课题（如大型水坝的应力计算，中长期天气预报等）迎刃而解；建立在数学模型和计算机模拟基础上的CAD技术，以其快速、经济、方便等优势，大量地替代了传统工程设计中的现场实验、物理模拟等手段。 (2）在高新技术领域，数学建模几乎是必不可少的工具。无论是发展通讯、航天、微电子、自动化等高新技术本身，还是将高新技术用于传统工业去创造新工艺、开发新产品，计算机技术支持下的建模和模拟都是经常使用的有效手段。数学建模、数值计算和计算机图形学等相结合形成的计算机软件，已经被固化于产品中，在许多高新技术领域起着核心作用，被认为是高新技术的特征之一。在这个意义上，数学不再仅仅作为一门科学，它是许多技术的基础，而且直接走向了技术的前台。国际上一位学者提出了“高技术本质上是一种数学技术”的观点。 (3）数学迅速进入一些新领域，为数学建模开拓了许多新的处女地。随着数学向诸如经济、人口、生态、地质等所谓非物理领域的渗透，一些交叉学科如计量经济学、人口控制论、数学生态学、数学地质学等应运而生。一般地说，不存在作为支配关系的物理定律，当用数学方法研究这些领域中的定量关系时，数学建模就成为首要的、关键的步骤和这些学科发展与应用的基础。在这些领域里建立不同类型、不同方法、不同深浅程度模型的余地相当大，为数学建模提供了广阔的新天地。马克思说过，一门科学只有成功地运用数学时，才 数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MA TLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的 数学建模常用的十种解题方法 摘要 当需要从定量的角度分析和研究一个实际问题时，人们就要在深入调查研究、了解对象信息、作出简化假设、分析内在规律等工作的基础上，用数学的符号和语言，把它表述为数学式子，也就是数学模型，然后用通过计算得到的模型结果来解释实际问题，并接受实际的检验。这个建立数学模型的全过程就称为数学建模。数学建模的十种常用方法有蒙特卡罗算法；数据拟合、参数估计、插值等数据处理算法；解决线性规划、整数规划、多元规划、二次规划等规划类问题的数学规划算法；图论算法；动态规划、回溯搜索、分治算法、分支定界等计算机算法；最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法；网格算法和穷举法；一些连续离散化方法；数值分析算法；图象处理算法。 关键词：数学建模；蒙特卡罗算法；数据处理算法；数学规划算法；图论算法 一、蒙特卡罗算法 蒙特卡罗算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法。在工程、通讯、金融等技术问题中, 实验数据很难获取, 或实验数据的获取需耗费很多的人力、物力, 对此, 用计算机随机模拟就是最简单、经济、实用的方法; 此外, 对一些复杂的计算问题, 如非线性议程组求解、最优化、积分微分方程及一些偏微分方程的解⑿, 蒙特卡罗方法也是非常有效的。 一般情况下, 蒙特卜罗算法在二重积分中用均匀随机数计算积分比较简单, 但精度不太理想。通过方差分析, 论证了利用有利随机数, 可以使积分计算的精度达到最优。本文给出算例, 并用MA TA LA B 实现。 1蒙特卡罗计算重积分的最简算法-------均匀随机数法 二重积分的蒙特卡罗方法(均匀随机数) 实际计算中常常要遇到如()dxdy y x f D ??,的二重积分, 也常常发现许多时候被积函数的原函数很难求出, 或者原函数根本就不是初等函数, 对于这样的重积分, 可以设计一种蒙特卡罗的方法计算。 定理 1 )1( 设式()y x f ,区域 D 上的有界函数, 用均匀随机数计算()??D dxdy y x f ,的方法: (l) 取一个包含D 的矩形区域Ω,a ≦x ≦b, c ≦y ≦d , 其面积A =(b 一a) (d 一c) ; ()j i y x ,,i=1,…,n 在Ω上的均匀分布随机数列,不妨设()j i y x ,, j=1，…k 为落在D 中的k 个随机数, 则n 充分大时, 有 数学建模在经济学中的应用 摘要：高校的经济学教学中经常会融入一些数学模型的思想，实际上数学模型的建立与经济学的教学和研究有着很大的内在联系，两者之间有着必然的关系，文本笔者将会从数学与经济学的关系出发，具体的介绍数学经济模型及其重要性，并对构建数学经济模型以及一些实例进行具体的论述。 关键词：数学模型；经济学；高校教学；应用 现如今的高校教学当中可以说数学建模与经济学之间有着密切的关系，任何一项经济学的研究和计算都离不开数学模型的建立，采用数学模型来辅助经济学的发展可以更加直观的让人们从中看出经济的发展形势。例如在经济学的宏观控制和价格控制中，都有数学建模的融入，利用数学建模可以有助于经济学实验的宏观经济分析，在一些实验和价格控制当中，都经常会涉及到数学问题在微观经济中数理统计的实验设计，这时候就体现出了数学建模对于经济学的促进性作用。下面笔者将会针对数学建模对于经济学的重要作用进行具体的分析。 1.数学经济模型对于经济学研究的重要性： 一般情况下，单独的依靠数学模型是不够解决所有的经济学问题，很多经济领域中的问题是需要从微观角度进行细致的分析才能够总结出其中的规律。要想利用数学知识来 解决经济学中所出现的问题，就一定要建立适当的经济学模型。运用数学建模来解决经济学中的问题并不是没有道理的，很多时候从经济学的角度仅仅能够知道问题的方向和目的，至于其中的过程并不能有着详细的分析，而利用数学模型就可以彻底的解决这一问题。数学建模可以通过自身在数字、图像以及框图等形式来更加真实地反映出现有经济的实际状况。 2.构建经济数学模型的一般步骤： 要想利用数学模型来更好的解决现有的经济学问题，主要分为两个步骤，第一先要分清楚问题发生的背景并且熟悉问题，然后要通过假设的形式来完善现有的经济学问题，通过抽象以及形象化的方式来构建一些合理的数学模型。运用数学知识和技巧来描述问题中变量参数之间的关系。这样可以得出一些有关经济类的数据，进而将建模中得到的数据与实际情况进行对比和分析，最终得出结果。 3.应用实例： 商品提价问题的数学模型： 3.1问题： 现如今经济学在很多的商场中都有所运用，例如同样的商品要想获得最大的经济效益，既要考虑到规定的售价，又要考虑到销售的数量，如果定价过低，则销售数量较多，如果定价较高，利润是大了，但是却影响了销售数量。怎样 数学建模10种常用算法 1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问 题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法（如果在比赛中采用高级语言进行 编程的话，那一些数值分析中常用的算法比如方程组 求解、矩阵运算、函数积分等算法就需要额外编写库 函数进行调用） 10、图象处理算法（赛题中有一类问题与图形有关， 即使与图形无关，论文中也应该要不乏图片的，这些 图形如何展示以及如何处理就是需要解决的问题，通 常使用Matlab进行处 参数估计 C.F. 20世纪60年代,随着电子计算机的 。参数估计有多种方法，有最小二乘法、极大似然法、极大验后法、最小风险法和极小化极大熵法等。在一定条件下，后面三个方法都与极大似然法相同。最基本的方法是最小二乘法和极大似然法. 基本介绍 参数估计（parameter 尽可能接近的参数 误差 平方和 θ,使已知数据Y 最大,这里P(Y│θ)是数据Y P(Y│θ)。在实践中这是困难的，一般可假设P（Y│θ 1、高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳 万元，可使用的金属板有500t，劳动力有300人/月，机器有100台/月，此外，不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号为100万元，中号为150万元，大号为200万元，现在要制定一个生产计划，使获得的利润为最大， max=4*x1+5*x2+6*x3-100*y1-150*y2-200*y3; 2*x1+4*x2+8*x3<=500; 2*x1+3*x2+4*x3<=300; 1*x1+2*x2+3*x3<=100; @bin(y1); @bin(y2); @bin(y3); y1+y2+y3>=1; Global optimal solution found. Objective value: 300.0000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost X1 100.0000 0.000000 X2 0.000000 3.000000 X3 0.000000 6.000000 Y1 1.000000 100.0000 Y2 0.000000 150.0000 Y3 0.000000 200.0000 Row Slack or Surplus Dual Price 1 300.0000 1.000000 2 300.0000 0.000000 3 100.0000 0.000000 4 0.000000 4.000000 5 0.000000 0.000000 数学建模中常见的十 大模型 精品文档 数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的 收集于网络，如有侵权请联系管理员删除 投资的收益与风险问题 摘要 对市场上的多种风险资产和一种无风险资产（存银行）进行组合投资策略的设计需要考虑两个目标：总体收益尽可能大和总体风险尽可能小，而这两个目标在一定意义上是对立的。 本文我们建立了投资收益与风险的双目标优化模型，并通过“最大化策略”，即控制风险使收益最大，将原模型简化为单目标的线性规划模型一；在保证一定收益水平下，以风险最小为目标，将原模型简化为了极小极大规划模型二；以及引入收益——风险偏好系数，将两目标加权，化原模型为单目标非线性模型模型三。然后分别使用Matlab的内部函数linprog，fminmax，fmincon对不同的风险水平，收益水平，以及偏好系数求解三个模型。 关键词：组合投资，两目标优化模型，风险偏好 2.问题重述与分析 3.市场上有种资产（如股票、债券、…）()供投资者选择，某公司有数额为的 一笔相当大的资金可用作一个时期的投资。公司财务分析人员对这种资产进行了评估，估算出在这一时期内购买的平均收益率为，并预测出购买的风险损失率为。考虑到投资越分散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的中最大的一个风险来度量。 购买要付交易费，费率为，并且当购买额不超过给定值时，交易费按购买计算（不买当然无须付费）。另外，假定同期银行存款利率是, 且既无交易费又无风险。（） 1、已知时的相关数据如下： 试给该公司设计一种投资组合方案，即用给定的资金，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总体风险尽可能小。 2、试就一般情况对以上问题进行讨论，并利用以下数据进行计算。 本题需要我们设计一种投资组合方案，使收益尽可能大，而风险尽可能小。并给出对应的盈亏数据，以及一般情况的讨论。 这是一个优化问题，要决策的是每种资产的投资额，要达到目标包括两方面的要求:净收益最大和总风险最低，即本题是一个双优化的问题，一般情况下，这两个目标是矛盾的，因为净收益越大则风险也会随着增加，反之也是一样的，所以，我们很难或者不可能提出同时满足这两个目标的决策方案，我们只能做到的是：在收益一定的情况下，使得风险最小的决策，或者在风险一定的情况下，使得净收益最大，或者在收益和风险按确定好的偏好比例的情况下设计出最好的决策方案，这 数学建模有下面十种常用算法, 可供参考： 1.蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问 题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法） 2.数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数 据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3.线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多 数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4.图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算 法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5.动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算 法设计中比较常用的方法，很多场合可以用到竞赛中） 6.最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些 问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7.网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很 多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8.一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计 算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9.数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分 析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10.图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中 也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab 进行处理） 数学建模背景： 数学技术 近半个多世纪以来，随着计算机技术的迅速发展，数学的应用不仅在工程技术、自然科学等领域发挥着越来越重要的作用，而且以空前的广度和深度向经济、管理、金融、生物、医学、环境、地质、人口、交通等新的领域渗透，所谓数学技术已经成为当代高新技术的重要组成部分。 数学模型（Mathematical Model）是一种模拟，是用数学符号、数学式子、程序、图形等对实际课题本质属性的抽象而又简洁的刻划，它或能解释某些客观现象，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略。数学模型一般并非现实问题的直接翻版，它的建立常常既需要人们对现实问题深入细微的观察和分析，又需要人们灵活巧妙地利用各种数学知识。这种应用知识从实际课题中抽象、提炼出数学模型的过程就称为数学建模（Mathematical Modeling）。[1] 不论是用数学方法在科技和生产领域解决哪类实际问题，还是与其它学科相结合形成交叉学科，首要的和关键的一步是建立研究对象的数学模型，并加以计算求解（通常借助计算机）。数学建模和计算机技术在知识经济时代的作用可谓是如虎添翼。 建模应用 数学是研究现实世界数量关系和空间形式的科学，在它产生和发展的历史长河中，一直是和各种各样的应用问题紧密相关的。数学的特点不仅在于概念的抽象性、逻辑的严密性，结论的明确性和体系的完整性，而且在于它应用的广泛性，自从20世纪以来，随着科学技术的迅速发展和计算机的日益普及，人们对各种问题的要求越来越精确，使得数学的应用越来越广泛和深入，特别是在21世纪这个知识经济时代，数学科学的地位会发生巨大的变化，它正在从国家经济和科技的后备走到了前沿。经济发展的全球化、计算机的迅猛发展，数理论与方法的不断扩充使得数学已经成为当代高科技的一个重要组成部分和思想库，数学已经成为一种能够普遍实施的技术。培养学生应用数学的意识和能力已经成为数学教学的一个重要方面。 2建模过程 模型准备 了解问题的实际背景，明确其实际意义，掌握对象的各种信息。以数学思想来包容问题的精髓，数学思路贯穿问题的全过程，进而用数学语言来描述问题。要求符合数学理论，符合数学习惯，清晰准确。 模型假设 根据实际对象的特征和建模的目的，对问题进行必要的简化，并用精确的语言提出一些恰当的假设。 模型建立 在假设的基础上，利用适当的数学工具来刻划各变量常量之间的数学关系，建立相应的数学结构（尽量用简单的数学工具）。 模型求解 利用获取的数据资料，对模型的所有参数做出计算（或近似计算）。 模型分析 对所要建立模型的思路进行阐述，对所得的结果进行数学上的分析。 模型检验 将模型分析结果与实际情形进行比较，以此来验证模型的准确性、合理性和适用性。如果模型与实际较吻合，则要对计算结果给出其实际含义，并进行解释。如果模型与实际吻合较差，则应该修改假设，再次重复建模过程。 C题面试时间问题 有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队(即在任何一个阶段4名同学的顺序是一样的)。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示(单位：分钟)： 这4名同学约定他们全部面试完以后一起离开公司．假定现在时间是早晨8:00问他们最早何时能离开公司? 面试时间最优化问题 摘要： 面试者各自的学历、专业背景等因素的差异，每个面试者在每个阶段的面试时间有所不同，这样就造成了按某种顺序进入各面试阶段时不能紧邻顺序完成，即当面试正式开始后，在某个面试阶段，某个面试者会因为前面的面试者所需时间长而等待，也可能会因为自己所需时间短而提前完成。因此本问题实质上是求面试时间总和的最小值问题，其中一个面试时间总和就是指在一个确定面试顺序下所有面试者按序完成面试所花费的时间之和，这样的面试时间总和的所有可能情况则取决于n 位面试者的面试顺序的所有排列数 根据列出来的时间矩阵，然后列出单个学生面试时间先后次序的约束和学生间的面试先后次序保持不变的约束，并将非线性的优化问题转换成线性优化目标，最后利用优化软件lingo变成求解。 关键词：排列排序0-1非线性规划模型线性优化 (1) （一）问题的提出 根据题意，本文应解决的问题有： 1、这4名同学约定他们全部面试完以后一起离开公司。假定现在的时间是早晨8：00，求他们最早离开公司的时间； 2、试着给出此类问题的一般描述，并试着分析问题的一般解法。 （二）问题的分析 问题的约束条件主要有两个：一是每个面试者必须完成前一阶段的面试才能进入下一阶段的面试(同一个面试者的阶段次序或时间先后次序约束)，二是每个阶段同一时间只能有一位面试者(不同面试者在同一个面试阶段只能逐一进行)。 对于任意两名求职者P、Q，不妨设按P在前，Q在后的顺序进行面试，可能存在以下两情况： （一）、当P进行完一个阶段j的面试后，Q还未完成前一阶段j-1的面试，所以j阶段的考官必须等待Q完成j-1阶段的面试后，才可对Q进行j阶段的面试，这样就出现了考官等待求职者的情况。这一段等待时间必将延长最终的总时间。 （二）、当Q完成j-1的面试后，P还未完成j阶段的面试，所以，Q必须等待P完成j阶段的面试后，才能进入j阶段的面试，这样就出现了求职者等待求职者的情况。同样的，这个也会延长面试的总时间。 以上两种情况，必然都会延长整个面试过程。所以要想使四个求职者能一起最早离开公司，即他们所用的面试时间最短，只要使考官等候求职者的时间和求职者等候求职者的时间之和最短，这样就使求职者和考官的时间利用率达到了最高。他们就能以最短的时间完成面试一起离开公司。这也是我们想要的结果。 （三）模型的假设 1.我们假设参加面试的求职者都是平等且独立的，即他们面试的顺序与考官无关； 2.面试者由一个阶段到下一个阶段参加面试，其间必有时间间隔，但我们在这里假定该时间间隔为0； 3.参加面试的求职者事先没有约定他们面试的先后顺序； 4.假定中途任何一位参加面试者均能通过面试，进入下一阶段的面试。即：没有中途退出面试者； 5.面试者及各考官都能在8：00准时到达面试地点。 （四）名词及符号约束 1. aij （i=1,2，3，4；j=1,2,3)为求职者i在j阶段参加面试所需的时间 甲乙丙丁分别对应序号i=1，2,3，4 2.xij （i=1,2，3，4；j=1,2,3) 表示第i名同学参加j阶段面试的开始时间（不妨把早上8:00记为面试的0时刻） (2) 第23卷第1期大 学 数 学Vol.23,№.1 2007年2月COLL EGE MA T H EMA TICS Feb.2007从诺贝尔经济学奖看数学建模的价值 韩 明 (福建工程学院数理系,福州350014) [摘 要]分为三个部分,第一部分,诺贝尔经济学奖的概述;第二部分,数学建模在经济学中的应用情 况;最后一部分,展望经济科学的发展趋势. [关键词]诺贝尔奖;数学建模;经济学 [中图分类号]F224;O213 [文献标识码]C [文章编号]167221454(2007)0120181206 1 诺贝尔经济学奖的概述 1968年瑞典银行为庆祝建行300周年,决定从1969年起同样以诺贝尔的名义,颁发经济学奖.这一奖项的全称是:“瑞典银行为纪念阿尔弗雷德?诺贝尔的经济科学奖(The Central Bank of Sweden Prize of Nobel in Economic Sciences in Memory of Alfred Nobel)”.除了奖金来源不同外,诺贝尔经济学奖的整个程序与其他诺贝尔奖完全相同. 获得当今世界上最具影响力的经济学奖项———诺贝尔经济学奖,几乎是每个经济学家的梦想.诺贝尔经济学奖从1969年第一次颁奖到2004年,已经有55人获此殊荣(同时获奖的人数最多不超过3人).1969年首届授予计量经济学的奠基人Regnar Frisch(挪威,1895-1979)和J an Tinbergen(荷兰, 1903-1994). 正如著名经济学家、后来的瑞典皇家科学院院长Erik L undberg在首届颁奖仪式上的讲话所说:“过去四十年中,经济科学在经济行为的数学规范化和统计定量化的方向上已经越来越发展.沿着这样的路线的科学分析,通常用来解释诸如经济增长、商情周期波动以及为各种目的来对经济资源重新配置那样的复杂经济现象…….然而,经济学家对有关战略性的经济关系构造数学模型的企图,以至借助于时间序列的统计分析来定量地阐明它们,事实上已经被证实是成功的.经济研究的这条路线,也就是数理经济学和计量经济学,已经在最近几十年里刻画了这一宗旨的发展.……”“近二十年来,Frisch教授和Tinbergen教授正在沿着本质上是同样的路线在进行研究.他们的目的是对经济理论赋予数学上的严谨性,并使它具有允许经验定量和统计假设检验的形式.其本质目标之一是要使经济学摆脱模糊的、较为‘文学’的类型.例如在Frischt和Tinbergen的著作中,商情周期波动的原因的任意‘命名’已经被抛弃,代之以陈述经济变量之间相互关系的数学系统.”从Erik L undberg的这段讲话,我们能看出经济科学在1969年前四十年的发展概况. 我们从经济科学的发展概况中,似乎能感觉到数学所起的作用.那么诺贝尔经济学奖得主的工作中数学建模起什么作用呢?它对开展大学生数学建模竞赛活动和我国大学数学教育又有什么启发呢? 2 数学建模在经济学中的应用情况 本文简要地介绍诺贝尔经济学奖得主的主要工作,从中我们能看到数学建模的应用情况和数学建 [收稿日期]2005208210 [基金项目]福建工程学院教育科学基金项目(G B-06-20) 在手机普遍流行的今天，建设基站的问题分析对于运营商来说很有必要。本文针对现有的条件和题目的要求进行讨论。在建设此模型中，核心运用到了0-1整数规划模型，且运用lingo 软件求解。 对于问题一： 我们引入0-1变量，建立目标函数：覆盖人口最大数=所有被覆盖的社区人口之和，即max=15 1j j j p y =∑，根据题目要求建立约束条件，并用数学软件LINGO 对其模型求解，得到最优解。 对于问题二： 同样运用0-1整数规划模型，建立目标函数时，此处假设每个用户的正常资费相同，所以68%可以用减少人口来求最优值，故问题二的目标函数为：max=∑=15 1j j j k p 上述模型得到最优解结果如下： 关键字：基站; 0-1整数规划；lingo 软件 1 问题的重述．．．．．．．．．．．．．．．．．．．．．．．．．3 2 问题的分析．．．．．．．．．．．．．．．．．．．．．．．．．4 3 模型的假设与符号的说明．．．．．．．．．．．．．．．．．．．5 3.1模型的假设．．．．．．．．．．．．．．．．．．．．．． 5 3.2符号的说明．．．．．．．．．．．．．．．．．．．．．． 5 4 模型的建立及求解．．．．．．．．．．．．．．．．．．．．．. 5 4.1模型的建立．．．．．．．．．．．．．．．．．．．．．． 5 4.2 模型的求解．．．．．．．．．．．．．．．．．．．．．． 6 5 模型结果的分析．．．．．．．．．．．．．．．．．．．．．．．7 6 优化方向．．．．．．．．．．．．．．．．．．．．．．．．．．7 7 参考文献．．．．．．．．．．．．．．．．．．．．．．．．．．8 8、附录．．．．．．．．．．．．．．．．．．．．．．．．．．． 9 与最大、最小、最长、最短等等有关的问题都是优化问题。 解决优化问题形成管理科学的数学方法：运筹学。运筹学主要分支：（非）线性规划、动态规划、图与网络分析、存贮学、排队伦、对策论、决策论。 6.1 线性规划 1939年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》 1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论. 1. 问题 例1 作物种植安排 一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力1/2 1/3 1/4, 预计每亩产值分别为110元, 75元, 60元. 如何规划经营使经济效益最大. 分析：以取得最高的产值的方式达到收益最大的目标. 1. 求什么？分别安排多少亩地种蔬菜、棉花、水稻？ x 1亩、 x 2 亩、 x 3 亩 2. 优化什么？产值最大 max f=10x 1+75x 2 +60x 3 3. 限制条件？田地总量 x 1+x 2 +x 3 ≤ 50 劳力总数 1/2x 1 +1/3x 2 +1/4x 3 ≤ 20 模型I : 设决策变量：种植蔬菜x1亩, 棉花x2亩, 水稻x3亩， 求目标函数f=110x1+75x2+60x3 在约束条件x1+x2+x3≤ 50 1/2x1+1/3x2+1/4x3 ≤20 下的最大值 规划问题：求目标函数在约束条件下的最值, 规划问题包含3个组成要素: 决策变量、目标函数、约束条件。 当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题, 否则称为非线性规划问题。 2. 线性规划问题求解方法 称满足约束条件的向量为可行解,称可行解的集合为可行域, 称使目标函数达最值的可行解为最优解. 命题 1 线性规划问题的可行解集是凸集. 因为可行解集由线性不等式组的解构成。两个变量的线性规划问题的可行解集是平面上的凸多边形。 命题2 线性规划问题的最优解一定在可行解集的某个极点上达到. 图解法：解两个变量的线性规划问题，在平面上画出可行域，计算目标函数在各极点处的值，经比较后，取最值点为最优解。 命题 3 当两个变量的线性规划问题的目标函数取不同的目标值时，构成一族平行直线,目标值的大小描述了直线离原点的远近。 于是穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点即为取的极值的极点—最优解。 单纯形法: 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解集的极点中搜寻最优解. 正则模型: 决策变量: x 1,x 2 ,…,x n . 目标函数: Z=c 1 x 1 +c 2 x 2 +…+c n x n . 约束条件: a 11 x1+…+a1n x n≤b1, ……a m1x1+…+a mn x n≤b m, 模型的标准化 10. 引入松弛变量将不等式约束变为等式约束. 若有 a i1x 1 +…+a in x n ≤b i , 则引入 x n+i ≥ 0, 使得 a i1 x 1 +…+a in x n + x n+i =b i 若有 a j1x 1 +…+a jn x n ≥b j , 则引入 x n+j ≥ 0, 使得 a j1 x 1 +…+a jn x n - x n+j =b j .什么是数学模型与数学建模
数学建模路线优化问题
数学建模算法分类
数学建模的作用意义
数学建模中常见的十大模型
数学建模常用的十种解题方法
数学建模在经济学中的应用
数学建模10种常用算法
数学建模优化问题经典练习
数学建模中常见的十大模型讲课稿
数学建模：投资问题
数学建模十种常用算法
数学建模背景
数学建模面试最优化问题
从诺贝尔经济学奖看数学建模的价值
数学建模课程设计——优化问题
数学建模中的优化问题与规划模型
相关主题
文本预览