自习教室开放的优化管理-数学建模--王猛-刘福伦-材料102
安徽工程大学数学建模（选修课）课程论文
题目：自习教室开放的优化管理
摘要：
本文在合理的假设之下，针对三个问题建立了合适的模型。在求解方面，我们充分利用计算机模拟顺利求得结果。对于各个问题，既能达到省电的目的，又能使同学们的满意程度在合理范围内。
问题一：针对其要求，要使用电量达到最省，并且又要更好的满足同学们的需要。我们把用电量最省作为目标函数，其它条件（如上自习的学生人数、同学的满足程度、教室满座率）作为约束条件建立了一个0-1规划模型，并利用Visual C++6.0模拟蚁群算法，逐步搜索最优解，最终得到了应该开放36个教室的最佳方案。
问题二：对于如何安排教室既达到节约用电的目的又能提高学生的满意度的问题，先考虑到学生的满意度与教室的满座率和宿舍区到自习区这两个因素有关，我们运用模糊数学建立满意度函数，最后再运用最优规划模型，并用MATLAB进行计算得到开放39个教室为5
10
2
,3
，
，既能达到省电的目的又能提高学生的，
，
，
，
,1
,3
4
,1
,4
32
43
2
30
14
,6
满意程度使得满意度达到0.9717.
问题三：我们先假设开放全部教室，很显然，不能满足要求，所以我们先计算出了还所需的座位数，从而得出了至少要再建二个以上的教室的结果。然后，利用灰局势决策，严格按照步骤要求，得到了在第二区、第五区和第七区各建立一个教室的方案。
在分析所得结果的基础上，我们指出了这几个模型的优缺点。通过以上几个方案，以及提出的关于如何合理利用学校教室资源的方法，能够有效加强学校教室资源管理使节约资源的做法有了科学依据与科学方法。
关键词：非线性规划、蚁群算法、最优解、模糊数学、灰决策。
队员1：王猛（材料102 3100102204）队员2: 刘福伦（材料102 3100102209）
指导老师：周金明
成绩：
完成日期：2012.11.7
一、问题重述
近年来，大学用电浪费比较严重，集中体现在学生上晚自习上，一种情况是去某个教室上自习的人比较少，但是教室内的灯却全部打开，第二种情况是晚上上自习的总人数比较少，但是开放的教室比较多，这要求我们提供一种最节约、最合理的管理方法。某学校收集的部分数据（相关数据见附录1附表一），请完成以下问题。
管理人员只需要每天晚上开一部分教室供学生上自习，每天晚上从7：00---10：00开放（如果哪个教室被开放，则假设此教室的所有灯管全部打开）。
现在有以下问题：
1．假如学校有8000名同学，每个同学是否上自习相互独立，上自习的可能性为0.7.要使需要上自习的同学满足程度不低于95%，开放的教室满座率不低于4/5，同时尽量不超过90%。问该安排哪些教室开放，能达到节约用电的目的.
2．假设这8000名同学分别住在10个宿舍区，现有的45个教室分为9个自习区，按顺序5个教室为1个区，即1,2,3,4,5为第1区，…，41,42,43,44,45为第9区。这10个宿舍区到9个自习区的距离见表2。学生到各教室上自习的满意程度与到该教室的距离有关系，距离近则满意程度高，距离远则满意程度降低。假设学生从宿舍区到一个自习区的距离与到自习区任何教室的距离相同。请给出合理的满意程度的度量，并重新考虑如何安排教室，既达到节约用电目的，又能提高学生的满意程度。另外尽量安排开放同区的教室。
3．假设临近期末，上自习的人数突然增多，每个同学上自习的可能性增大为0.85，要使需要上自习的同学满足程度不低于99%，开放的教室满座率不低于4/5，同时尽量不超过95%。这时可能出现教室不能满足需要，需要临时搭建几个教室。假设现有的45个教室仍按问题2中要求分为9个区。搭建的教室紧靠在某区，每个区只能搭建一个教室，搭建的教室与该区某教室的规格相同（所有参数相同），学生到该教室的距离与到该区任何教室的距离假设相同。问至少要搭建几个教室，并搭建在什么位置，既达到节约用电目的，又能提高学生的满意程度.
表2 学生区(标号为A)到自习区(标号为B)的距离(单位:米) （注：见附录2）
二、问题的假设
2.1 问题的基本假设
1.假设同学们上自习的概率不受天气影响，即概率不变；
2.假设该校在晚上没有安排任何课程，即晚上由学生自由活动；
3.因为每天开放的时间是相同的，所以把时间假设为一个整体1；
4.问题一中同学们的满足程度与到自习室的距离无关；即同学们会自动的找到符合要求的教室；
5.问题二中假设每个宿舍区住有相同数量的同学，即每个宿舍区住有8000/10=800名同学；
6.每个宿舍区的同学都是理想化同一个概率；
7.在问题二和问题三中，为了满足题中给出的尽量安排开放同区的教室这一条件，假设10个学生区的学生至多只会去两个区且是等量的；
8. 假设距离与座位数对满意度的影响一样；
9.问题三中学生选择老教室和临时教室上自习是等可能的，即不存在对临时教室的厌恶情况，也不存在对老教室的排斥情况。
三、符号的约定
i d 表示第i 个教室)452,1( =i ；
i E 表示第i 个教室的灯管数量)452,1( =i ； i P 表示相应教室的灯管的功率)452,1( =i i S 表示去相应教室上自习的学生人数；
i Z 表示相应教室的座位数；
E 表示总用电量；
j E 表示第j 个区的总用电量)92,1( =j ；
H 表示总人数；
ij B 表示第i 个宿舍区到第j 个自习区的满意度)92,11021(i ==j ；，；
a 表示事件；j
b 表示相应的分区)92,1( =j ；
i λ表示在相应的区域的教室开放与不开放1,0=i λ)452,1( =i ； ij x 表示第i 区的学生是否到第j 区的自习室上自习1,0=ij x )92,11021(i ==j ；，； j C 表示第j 区的座位数)92,1( =j ；
四、建模前的准备
在第二问中，模糊综合评价模型基本步骤： （1）确定评价指标；
（2）求每一个指标的评语的隶属度，得到模糊评价矩阵n m ij p P ?=)(；
（3）给出指标的权重i W ，A w w w n =),,,(21 ，其中121=+++n w w w ； （4）用权重乘以模糊评价矩阵得到综合模糊评价向量b ，AP b =.
在问题三,我们引入了灰局势决策论,下面就灰局势决策论的相关内容描述如下: 灰局势决策的要素:称事件、对策、样本为灰局势决策的四要素；变称局势、目标、样本为灰局势决策的三要素。
()1效果测试算式：
令为事件j i b a ,为对策，有局势ij s 。设局势ij s
(),,j i ij b a s =
{}{}m J j n I i ,,2,1,,,2,1 =∈=∈
在p 目标下的效果样本为p ij u ，{
}l P p ,,2,1 ∈.称U 为p 目标下的效果样本矩阵 ??????
????????=p nm p n p n p m p p p m p
p u u u u u u u u u 112222111211U 令eff M 为变换，p ij u 为p 目标下局势ij s 的效果样本，p ij r 为p ij u 在eff M 下的像
当其满足
1、p ij r 具有正极性；
2、[]1,0∈p ij r ,称eff M 为效果测试变换，或效果变换，称p ij r 为局势p ij s 在目标p 下的效果测度。当
p ij u 为正极性时，称eff M 为上限效果测度变换；
p ij u 为负极性时，称eff M 为下限效果测度变换； p ij u 为中极性时，称eff M 为适中效果测度变换。
()2极大值目标变换算式（上限效果测度算式）
令eff M 为效果变换，p ij u 为正极性效果样本，p ij r 为p ij u 在eff M 下的像，则极大值目标下的效果变换算式为
()
p
ij j
i
p
ij p ij eff u u u M max max =
，
p ij
j
i
p
ij p ij
u
u r max max =
()3极小目标变换算式（下效果测度算式）
令eff M 为效果变换，p ij u 为极性负果样本，p ij r 为p ij u 在eff M 下的像，则极大值目标下的效果变换算式为
()
p ij
p
ij j
i
p ij eff u
u u M min min =
，
p ij
p
ij j i
p ij u
u r min min =
()4令eff M 为效果变换，p ij u 为中性效果样本，p ij r 为p ij u 在eff M 下的像，则极大值目标下的效果变换算式为
(){}{}p ij
p
ij p ij
eff
u u u u u M ,max ,min 00=， {}{}
p ij
p ij
p ij
u u u u r ,max ,min 0
= ()5统一测度
令p ij r 为局势p ij s 在目标p 下的效果测度，当l p ,,2,1 =则称∑ij r 为ij s 的统一效果测度，或统一测度，即
∑=∑=l p p
ij ij
r l r 1
1
令i S 及i r 分别为事件i a 的局面与统一测度空间，若有
∑∑=*ij j
ij r r max ，
()*=*?*∑j i ij ij b a s r ,
则*ij s 称为i a 的满意局势，*j b 为i a 的满意对策。
五、问题的分析
5.1 问题一的分析
题中要求在满足同学们的需求的同时达到用电量最省，自然而然把我们引到了规划
问题上。考虑到众多的数据，难以求解。我们需要在以下几个约束条件下建立模型：
第一，上自习的人数方面，我们要满足两个条件，第一个是每个同学去上自习的概率为0.7，第二个则是同学满足程序不能低于95%，有如下约束：
∑=?≤≤??45
17.08000%95.708000i i i z λ
第二，要求被开放的教室的满座率不能低于4/5，同时不超过90%，即有以下约束：
i i i Z S Z 10
954≤≤ 运用0-1规划建立最优化模型，再引入了现代智能算法中的蚁群算法，面向对象编程。从而很好地求得结果。 4.2 问题二的分析
在现实生活中，对我们每个人而言，我们肯定会选择靠近宿舍的教室上自习，如果靠近的教室得不到满足，我们选择较远教室时同时满意程度就相应下降，距离越远，则越不满意，在确定学生只是自习区距离对满意度的影响时，可以用模糊分布函数来描述。结合实际情况，所选择的目标模糊分布函数应满足以下要求：
1、在300—400米，满意度接近为1；
2、函数是单调递减的；
3、当距离增加时，函数应该趋近为0.
而第二问中，不仅只有自习区距离影响满意度，还有教室的满座率会影响。若只考虑教室的满座率即总共的座位数对满意度的影响，结合实际情况，所选择的目标模糊分布函数应满足以下要求：
1、由第一题所说，开放的教室满座率不低于4/5,同时尽量不超过90%时，满间程度就不低于95%。在第二题中如果一个区的学生去一个自习区，若要使满意度为95%，则座位数不低于约600，不超过700，即当一个自习区的的座位数达到600—700时，满意度为95%；
2、函数是单调递增的；
3、当座位数增加时，函数应该趋近为1.
给出函数并画出曲线图，以区间为单位，分别给了相应的满意度。
结合距离与座位数分别的满意度，对附表1和附表2进行分析，分别写出所有学生区到所有自习区距离和距离的满意度，利用模糊综合评价模型，分为10个模糊评价矩阵，得到10个学生区综合模糊评价向量，再由假设和题中所给的信息应用0-1规划模型得到最大满意度函数，进而安排教室。
对于在适当的位置搭建教室既达到节约用电的目的又能提高学生的满意程度的问题，我们首先考虑根据临近期末每个同学上自习的可能性增大为85.0且要使需要上自习的同学的满足程度不低于%99，然后通过计算得到应该搭建几个教室。然后我们要进一步地确定要在哪些自习区搭建教室，我们考虑运用会决策模型去确定，根据用电量应该是越低越好我们对用电量进行了下限效果处理，然而满意度是越高越好因此我们对满意度进行了上限效果处理，最后进行统一测度最终确定在哪些自习区搭建教室。
六、模型的建立与求解
6.1模型一的建立与求解
然后，我们再来分析我们的目标，我们要使用电量最少，即要使用电量E 达到最小，于是，有：
i i i P λ∑==45
1i N E
????
?
?????≥??≥?≤∑∑==i
451
45
1Z 54%957.08000,7.08000.i i i i i i i S Z Z t s λλ 问题一，我们应用了Visual C++6.0采用面向对象编程，模拟蚁群算法（相关程序及结果见附录），得出了在最省电的情况下，应该开放3,4,5，6，7，8，9，10，11，12，13,14,17,18，19，20,22,23，24，25，26，27，28，29，30，31，32，33，34，35，36，37，38，39,40和43，总共36个 教室，共计5927个座位。同时，我们计算出了最少用电量，因为每开放三个小时，所以，每天的最少用电量是E=74.525*3=223.575kw 时。
6.2模型二的建立与求解
1、只考虑自习区距离对满意度
根据问题二的分析，综合目标模糊分布函数要求，同时参考学生的实际心理角度，最终选择偏大型的正态分布函数为满意函数)(A x ，表达式为：
0,])300(exp[)(2
≥--=x x x A δ
其函数曲线如图1.
2、只考虑教室的满座率即总共的座位数对满意度的影响 与1相同，得到满意函数B(x)，表达式为：
0,])(exp[1)(2≥--=x x
x B δ
其函数曲线如图
2.
3
1A ???? ?
?=95.0198.019.095.098.09.095.0195.095.09.095.018.011
P 1 上个矩阵是学生区1A 分别到921B B 、B 分别关于距离（第一行）、座位数（第二行）的满意度
的评价矩阵。
由假设可知距离与座位的权重为）
（5.0,5..0A = 它的综合模糊评价向量)975.0,975.0,965.0,95.0,925.0,975.0,89.0,95.0,975.0(1=B
1B 就是1A 分别到921B B 、B 的满意度。
由以上的方法可以分别得到932A A A 、的满意度：
)875.0,95.0,99.0,975.0,925.0,925.0,965.0,9.0,875.0(2=B
)875.0,95.0,965.0,95.0,85.0,95.0,99.0,85.0,875.0(3=B )875.0,99.0,99.0,9.0,925.0,95.0,99.0,9.0,975.0(4=B )875.0,9.0,965.0,95.0,95.0,95.0,965.0,85.0,875.0(5=B )925.0,9.0,99.0,95.0,85.0,95.0,965.0,9.0,95.0(6=B )975.0,1,94.0,9.0,9.0,875.0,89.0,59.0,975.0(7=B )975.0,5.90,94.0,1,95.0,925.0,965.0,59.0,95.0(8=B )975.0,5.90,94.0,5.90,925.0,975.0,94.0,59.0,975.0(9=B )925.0,5.970,94.0,5.90,9.0,975.0,965.0,259.0,95.0(10=B
满意度函数
20
)(max 919
1
∑∑===
i j ij
ij
x B
x f
??
??
?
????=≥???≤???∑∑==1,0457.08005.09107.08005.0.9
1
9
1ij i j ij i j ij x C x C x t s
其中)67010007861051580630781590666(=C ； 可以解得
9717.0)(max =x f
满意度达到最大时，开放的教室分别是5,4434,33230,6,1142,110,32 ，，，，，，，一共39个教室。
6.3模型三的建立与求解
根据要求，我们先确定要建几个教室，假设建好的教室的总座位为S'，则 因为
29095.0/99.0/95.0*85.0*'45
1=??
???????
??-=∑=i i Z H s
又因为
()45,,2,1,290 =>i Z i
所以我们确定，搭建一个教室是肯定不够的，要搭建的教室一定是两个以上的， 在建模前的准备中，我们已经给出了灰局势决策的各个定义，下面，我们将用这种方法来解决问题三，请见下面步骤：
1.确定事件、对策、局势：
按照灰局势的步骤，我们可以得到以下内容：
步骤一 确定事件、对策、局势.
令学生选择教室上自习为事件a ，方案i b ，i=1,2,…,9为对策，有局势i c
{}();,,,,,)(c 5432111d d d d d a b a ，
，== {}();,,,,,)(c 10987622d d d d d a b a ，
，== {}();,,,,,)(c 151413121133d d d d d a b a ，
，== {}();,,,,,)(c 201918171644d d d d d a b a ，
，== {}();,,,,,)(c 252423222155d d d d d a b a ，
，== {}();,,,,,)(c 302928272666d d d d d a b a ，
，== {}();,,,,,)(c 353433323177d d d d d a b a ，
，== {}();,,,,,)(c 403938373688d d d d d a b a ，
，== {}();,,,,,)(c 454443424199d d d d d a b a ，
，== 式中表示学生可以选择九个区中的任意一个区上自习，每个区有五间教室，故有九
种局势。
步骤二 确认目标及其极性
目标1，总用电量E 最少，极小值极性；
目标2，学生上自习的满意程度ij B 最高，极大值极性.
步骤三 给出局势效果样本，作效果测度变换 （1）目标1（总用电量E 最少），极小值目标. 1.效果样本
各个区的总用电量）（10518119219819129831093980289780=j E 2.下限效果测度算式与计算
9,21min r 1j
1j
1j ，，，??==
j u u j
{}
7488,,,,,,,,min min 1
918171615141312111j ==u u u u u u u u u u j
,7488min 1
j
1j 1
j
1
j u u u j == 7656.097807488
748811
j
11====u r j ， ,9327.080287488748821
j
12===
=u r j ， ,6845.0109397488748831
3
13===
=u r j ， ,7704.097207488
7488414
14====u r j ，
,174887488
7488515
15====u r j ，
,5768.0129837488
748861
6
16===
=u r j ， 0.7626,98197488
7488717
17====u r j ，
,6286.0119217488
7488818
18====u r j ，
7119.010*******
7488919
19====u r j ，
（2）目标2,极大值目标
① 效果样本（在第二问中，我们已经假设了一个满意度，下表即为效果样本）
② 上限效果测度算式及计算
222max j
j
j j u u r =
在此，我们选择每一行得出最大值，我们就得到了十个宿舍区到九个自习区的满意
状况，即：
宿舍第一区：{}
975.0,,,,,,,,,max max 1
2
928272625242322212==u u u u u u u u u u j j 宿舍第二区：{}
975.0,,,,,,,,,max max 22
928272625242322212==u u u u u u u u u u j j 宿舍第三区：{}
975.0,,,,,,,,,max max 32
928272625242322212==u u u u u u u u u u j j 宿舍第四区：{}
975.0,,,,,,,,,max max 42
928272625242322212==u u u u u u u u u u j
j
宿舍第五区：{}
95.0,,,,,,,,,max max 52
928272625242322212==u u u u u u u u u u j j 宿舍第六区：{}975.0,,,,,,,,,max max 62
928272625242322212==u u u u u u u u u u j j 宿舍第七区：{}1,,,,,,,,,max max 72
928272625242322212==u u u u u u u u u u j j 宿舍第八区：{}
1,,,,,,,,,max max 82
928272625242322212==u u u u u u u u u u j j 宿舍第九区：{}95.0,,,,,,,,,max max 92
928272625242322212==u u u u u u u u u u j
j 利用测度算式可以得到以下结果:
（1） 统一效果测度算式
2,1,2121
==∑∑=j r r p p j j
（2）局势),(1i E a c =
2ij 步骤五 找出满意局势 （1）求最大
我们要求的是在哪个区域建自习教室，所以，我们用满意度的每一列和用电量之和的商作为我们求得的最大
，
（2）确定满意局势
ij B
B1 B2 B3 B4 B5 B6 B7 B8 B9 A1 0.9744 0.9744 0.8974 0.9744 0.9487 0.9744 0.9744 1.0000 0.9744 A2 0.8718 0.9231 0.9744 0.9231 0.9487 1.0000 1.0000 0.9744 0.8718 A3 0.8718 0.8718 1.0000 0.9487 0.8718 0.9744 0.9744 0.9744 0.8718 A4 0.9744 0.9231 1.0000 0.9487 0.9487 0.9231 1.0000 0.9231 0.8718 A5 0.8947 0.8947 1.0000 0.9737 1.0000 1.0000 1.0000 0.9474 0.8947 A6 0.9487 0.9231 0.9744 0.9487 0.8718 0.9744 1.0000 0.9231 0.9231 A7 0.9500 0.9500 0.8750 0.8500 0.9000 0.9000 0.9250 1.0000 0.9500 A8 0.9250 0.9500 0.9500 0.9000 0.9500 1.0000 0.9250 0.9500 0.9500 A9 1.0000 1.0000 0.9737 1.0000 0.9737 1.0000 0.9737 1.0000 1.0000 A10
0.9487
0.9487
0.9744
0.9744
0.9231
0.9744
0.9487
1.0000
0.9231
0.7656 0.9327 0.6845 0.7704 1.0000 0.5768 0.7626 0.6286 0.7119
结合要求，我们得出了，要搭建三个教室的方案，即在第二区，第五七和第七区各搭建一个教室才能满足条件。
（4）确定满意方案
经过我们的筛选，最终得出了两个方案：1、在第二区建立一个与第9号教室相同规格的教室（即座位数110，灯管数36，灯管功率40w）、在第五区建立一个与第23号教室相同规格的教室（即座位数110，灯管数36，灯管功率40w）和在第七区建立一个与第33号教室相同规格的教室（即座位数70，灯管数276，灯管功率40w）；
2、在第二区建立一个与第9号教室相同规格的教室（即座位数110，灯管数36，灯管功率40w）、在第五区建立一个与第23号教室相同规格的教室（即座位数70，灯管数26，灯管功率40w）和在第七区建立一个与第33号教室相同规格的教室（即座位数110，灯管数36，灯管功率40w）；
七、结果分析
模型一的结果表明，开放36个教室分别为43
3，
,1
4
14
，
，
,既能
，
，
，
，
,1
2
,2
3
7
,2
40
18
9
,2
达到节约用电的目的开放这些教室一个晚上的用电量为223.575度，也能使需要上自习的同学满足程度不低于95%开放的教室的座位总数达到5927个.
对于问题二，应用模糊数学求得满意度，利用最优化模型并用MATLAB用得答案，可以减少一些人工误差，但是为了求解的简便，我们假设了10个学生区的学生至多只会去两个区且是等量的，这样我们主观的给学生规定了只能去两个自习区，这样使答案与实际有一定的偏差。
模型三的结果表明，由于临近期末上自习的人数增加，即使所有的教室都开放也不能是上自习的同学满足程度达到99%，于是需要在2，5，7自习区各搭建一个教室，根据题中要求搭建的教室与该区某教室的规格相同，因此我们得到搭建的教室的规格分别为110，110，70既达到节约用电目的又能提高学生的满意度.
八、模型的评价与改进
8.1、模型的优点：1、运用蚁群算法得出结果有科学依据；
2、模型一的最优化方案的设计综合考虑了教室满座率和用电量最少，具有实用性；
3、模型二中先引入了距离与座位数的满意度函数，再利用模糊综合评价模型算出了每一区的学生到每一区自习室的满意度，此模型在综合性、合理性、科学性等方面得到了改进，使定性评价与定量评价能很好地结合，并能较好地控制人为的干扰因素，远离了数据的漩涡。最后建立了最优化模型，且容易编程得到答案；
8.2、模型的缺点：1、不能准确的定位模型中的参数，只能较好的靠近最佳参数范围，这将直接影响到模型的效益；
2、运用灰决策确定在哪些自习区搭建教室由于没有考虑搭建教室后该自习区的用电量，存在一定的误差。
8.3、模型的改进:对满意程度进行更加细致的量化，同时考虑到教室的满座率对同学上自习的满意程度的影响。可以考虑尽量开放座位数多但教室内总功率小的教室，但模型的求解对数据的依赖行很大，需要对数据进行比较分析。考虑到对满意度有影响的因素不仅仅只是距离，学生对教室的选择也有其他因素的影响，可尝试建立多元函数模型求解。
参考文献
[1] 黄席樾等，现代智能算法理论及应用，第三部分——蚁群优化算法理论及应用。北京：科学出版社，2005
[2] 钱能.C++程序设计教程（第二版）.北京：清华大学出版社，2005
[3] 中国电力网
[4] 邓聚龙.灰预测与灰决策.湖北：华中科技大学出版社，2002
[5] 李庆扬，王能超，易大义. 数值分析[M]. 北京：清华大学出版社，2008
附录
附录1：某学校收集的数据，表1教室相关数据
附录2：表2 学生区(标号为A)到自习区(标号为B)的距离(单位:米)
附录3：问题一的程序如下
先建立一个文本文档“information.txt”，按顺序记录相应教室的座位数、灯管数和灯管的功率，把它放在C++搜索目录下，以便程序识别，如下图：
程序如下：
#include
#include
#include
#define ANTS 100
#define MAX 5600 //最大值，即8000*0.7 #define MIN 5320//最小8000*0.7*0.95 using namespace std;
class ANT
{
int i=1;
int classroomsNum[] //教室编号int sets[]; //相应教室的座位数int lampsNum[];//相应教室的灯管数int lampsPower[];//教室灯管的功率public:
int input();
//设置输入函数，将45个相应变量初始化到数组中
int totlepower(); int assemble(); //设置组合数,并设置约束条件 int print(); //设置打印函数
};
void ANT::input() {
for(int i=1,i<=45,i++)
classroomsNum[i]=i;
char *p=new char[1024];
ifstream i_file("informations.txt",ios::in); //打开文件
while(!i_file.eof())
{
i_file.getline(pf,1024,'\n');
for(int i=1,i<=45,i++)
sets[i]==string::npos);
for(int i=1,i<=45,i++)
lampsNum[i]==string::npos);
for(int i=1,i<=45,i++)
lampPower[i]==string::npos);
}
}
void ANT::totlepower() {
int i=1,j[];
for(int i=1,i<=45,i++)
j[i]=lampsNum[i]*lampsPower[i];
}
void ANT::assemble() {
int ant,count; //开始在搜索路径上放置蚂蚁 for(ant=1,ant<=45,ant++)
{
sum=sum+set[ant];
if(sum>=MAX)
break;
}
for(i=1,i<=45;i++)
count=lampsNum[i]*lampsPower[i]; }
void ANT::print()
{
int a;
a.assemble();
for(int i=1;i<=45;i++)
cout<<"开放最省电的教室组合"< cout< cout<<"最省电量为： "< } int main() //主函数 { ANT w; w.input(); //分别调用各个函数 w.totlepower(); w.assemble(); w.print(); } 程序运行结果： 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月进行。 浅谈最优控制 发表时间：2008-12-10T10:25:09.263Z 来源：《黑龙江科技信息》供稿作者：李晶1 陈思2 [导读] 主要阐述了关于最优控制问题的基本概念，最优控制是最优化方法的一个应用。最优化一般可以分为最优设计、最优计划、最优管理和最优控制四个方面。 摘要：主要阐述了关于最优控制问题的基本概念，最优控制是最优化方法的一个应用。最优化一般可以分为最优设计、最优计划、最优管理和最优控制四个方面。而最优控制理论是研究和解决从一切可能的控制方案中寻找最优解的一门学科，解决最优控制问题的主要方法有古典变分法、极大值原理和动态规划。通过以上知识的讲解使初学者能够快速掌握最优控制的问题。关键词：最优化；最优控制；极值 最优控制是最优化方法的一个应用，如果想了解最优控制必须知道什么是最优化方法。所谓最优化方法为了达到最优化目的所提出的各种求解方法。从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。 最优化一般可以分为最优设计、最优计划、最优管理和最优控制四个方面。（1）最优设计:世界各国工程技术界,尤其是飞机、造船、机械、建筑等部门都已广泛应用最优化方法于设计中，从各种设计参数的优选到最佳结构形状的选取等，结合有限元方法已使许多设计优化问题得到解决。一个新的发展动向是最优设计和计算机辅助设计相结合。电子线路的最优设计是另一个应用最优化方法的重要领域，它存在着巨大的开发潜力，尤其是对于学电工学的学生来说。配方配比的优选方面在化工、橡胶、塑料等工业部门都得到成功的应用,并向计算机辅助搜索最佳配方、配比方向发展。（2）最优计划:现代国民经济或部门经济的计划，直至企业的发展规划和年度生产计划，尤其是农业规划、种植计划、能源规划和其他资源、环境和生态规划的制订,都已开始应用最优化方法。一个重要的发展趋势是帮助领导部门进行各种优化决策，使工作结构简单，工作效率最高化，节省了很多时间。（3）最优管理：一般在日常生产计划的制订、调度和运行中都可应用最优化方法。随着管理信息系统和决策支持系统的建立和使用，使最优管理得到迅速的发展。（4）最优控制：主要用于对各种控制系统的优化。下面着重来解释一下最优控制。 最优控制理论是研究和解决从一切可能的控制方案中寻找最优解的一门学科。它是现代控制理论的重要组成部分。这方面的开创性工作主要是由贝尔曼（R.E.Bellman）提出的动态规划和庞特里亚金等人提出的最大值原理。这方面的先期工作应该追溯到维纳（N.Wiener）等人奠基的控制论（Cybernetics）。1948年维纳发表了题为《控制论——关于动物和机器中控制与通讯的科学》的论文，第一次科学的提出了信息、反馈和控制的概念，为最优控制理论的诞生和发展奠定了基础。钱学森1954年所著的《工程控制论》（EngineeringCybernetics）直接促进了最优控制理论的发展和形成。 为了解决最优控制问题，必须建立描述受控运动过程的运动方程，即系统的数学模型，给出控制变量的允许取值范围，指定运动过程的初始状态和目标状态，并且规定一个评价运动过程品质优劣的性能指标。通常，性能指标的好坏取决于所选择的控制函数和相应的运动状态。系统的运动状态受到运动方程的约束，而控制函数只能在允许的范围内选取。因此，从数学上看，确定最优控制问题可以表述为：在运动方程和允许控制范围的约束下，对以控制函数和运动状态为变量的性能指标函数（称为泛函）求取极值（极大值或极小值）。解决最优控制问题的主要方法有古典变分法、极大值原理和动态规划。 1 古典变分法 研究对泛函求极值的一种数学方法。古典变分法只能用在控制变量的取值范围不受限制的情况。在许多实际控制问题中，控制函数的取值常常受到封闭性的边界限制，如方向舵只能在两个极限值范围内转动，电动机的力矩只能在正负的最大值范围内产生等。因此，古典变分法对于解决许多重要的实际最优控制问题，是无能为力的。 2 极大值原理 极大值原理，是分析力学中哈密顿方法的推广。极大值原理的突出优点是可用于控制变量受限制的情况，能给出问题中最优控制所必须满足的条件。 3 动态规划 动态规划是数学规划的一种，同样可用于控制变量受限制的情况，是一种很适合于在计算机上进行计算的比较有效的方法。随着社会科技的不断进步,最优控制理的应用领域十分广泛，如时间最短、能耗最小、线性二次型指标最优、跟踪问题、调节问题和伺服机构问题等。但它在理论上还有不完善的地方，其中两个重要的问题就是优化算法中的鲁棒性问题和最优化算法的简化和实用性问题。大体上说，在最优化理论研究和应用方面应加强的课题主要有：（1）适合于解决工程上普遍问题的稳定性最优化方法的研究；（2）智能最优化方法、最优模糊控制器设计的研究；（3）简单实用的优化集成芯片及最优化控制器的开发和推广利用；（4）复杂系统、模糊动态模型的辩识与优化方法的研究；（5）最优化算法的改进。相信随着对这些问题的研究和探索的不断深入，最优控制技术将越来越成熟和实用，它也将给人们带来不可限量的影响。 参考文献 [1]胡寿松.最优控制理论与系统[M].（第二版）北京：科学出版社，2005. [2]阳明盛.最优化原理、方法及求解软件[M].北京：科学出版社，2006. [3]葛宝明.先进控制理论及其应用[M].北京：机械工业出版社，2007. [4]章卫国.先进控制理论与方法导论[M].西安：西北工业大学出版社，2000. 选路的优化模型 摘要: 本题是一个有深刻背景的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数据呈现指数或曲线的形式 ②微分方程预测（备用） 无法直接找到原始数据之间的关系，但可以找到原始数据变化速度之间的关系，通过公式 数学建模常用的十种解题方法 摘要 当需要从定量的角度分析和研究一个实际问题时，人们就要在深入调查研究、了解对象信息、作出简化假设、分析内在规律等工作的基础上，用数学的符号和语言，把它表述为数学式子，也就是数学模型，然后用通过计算得到的模型结果来解释实际问题，并接受实际的检验。这个建立数学模型的全过程就称为数学建模。数学建模的十种常用方法有蒙特卡罗算法；数据拟合、参数估计、插值等数据处理算法；解决线性规划、整数规划、多元规划、二次规划等规划类问题的数学规划算法；图论算法；动态规划、回溯搜索、分治算法、分支定界等计算机算法；最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法；网格算法和穷举法；一些连续离散化方法；数值分析算法；图象处理算法。 关键词：数学建模；蒙特卡罗算法；数据处理算法；数学规划算法；图论算法 一、蒙特卡罗算法 蒙特卡罗算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法。在工程、通讯、金融等技术问题中, 实验数据很难获取, 或实验数据的获取需耗费很多的人力、物力, 对此, 用计算机随机模拟就是最简单、经济、实用的方法; 此外, 对一些复杂的计算问题, 如非线性议程组求解、最优化、积分微分方程及一些偏微分方程的解⑿, 蒙特卡罗方法也是非常有效的。 一般情况下, 蒙特卜罗算法在二重积分中用均匀随机数计算积分比较简单, 但精度不太理想。通过方差分析, 论证了利用有利随机数, 可以使积分计算的精度达到最优。本文给出算例, 并用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 充分大时, 有 数学建模常用的十大算法==转 (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 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的 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 最优化方法与最优控制复习文件 1. 非线性优化的基本概念，最优解的一阶和二阶条件，最速下降方法，拟牛顿法情况，BFGS 修正。 2. 变分问题的最优必要性条件推导，各种情况下的必要性条件，Hamilton 函数、拉格让日 函数。PPT 中讲到的最优控制实例，包括求解过程需要掌握。 3. 极大值原理搞清楚，以及PPT 中的计算实例。 4. 动态规划，原理和简单的求解技术。 5. LQR 问题也要看一下。 除此之外，还有几个作业题目大家做一下，如下所示： 1. 非线性优化中，从直观考虑最速下降法是一种最快速的迭代优化方法，实际过程中为什 么不理想？为什么采用二阶方法？二阶方法中的二阶导数矩阵怎么得到的？有什么要求？ （15分） 2. 对于函数形式为 的优化问题，若采用最速下降法求解，请给出最优搜索方向p k 的表达式。变量初值为X0=[1,1,1]T ，请写出第一步迭代过程，以及得到的X1的关于搜索步长α0表达式，在这种情况下，使得))0()0((F 0p x α+最小的搜索步长α0应该等于多少？（15分） 3. 题目要求如下，采用动态规划方法寻求从A 点到B 点的最小时间路径（A 到B 仅能向前 走），（20分） 4. 对于以下简单的标量非线性系统，请通过求解相关HJB 方程得到其最优反馈控制策略。 提示，HJB 微分方程允许如此形式的解。 5.写出如下优化控制问题的Hamiltonian 函数、优化求解的必须性条件，并通过必要性条 件的求解计算出该优化控制和状态轨线。最小化目标函数 6.根据你对优化控制求解方法的了解，目前对于优化控制问题（或者成为动态优化问题， DAOPs问题）有哪些求解方法， 7. 投资的收益与风险问题 摘要 对市场上的多种风险资产和一种无风险资产（存银行）进行组合投资策略的设计需要考虑两个目标：总体收益尽可能大和总体风险尽可能小，而这两个目标在一定意义上是对立的。 本文我们建立了投资收益与风险的双目标优化模型，并通过“最大化策略”，即控制风险使收益最大，将原模型简化为单目标的线性规划模型一；在保证一定收益水平下，以风险最小为目标，将原模型简化为了极小极大规划模型二；以及引入收益——风险偏好系数，将两目标加权，化原模型为单目标非线性模型模型三。然后分别使用Matlab的内部函数linprog，fminmax，fmincon对不同的风险水平，收益水平，以及偏好系数求解三个模型。 关键词：组合投资，两目标优化模型，风险偏好 2.问题重述与分析 3.市场上有种资产（如股票、债券、…）()供投资者选择，某公司有数额为的 一笔相当大的资金可用作一个时期的投资。公司财务分析人员对这种资产进行了评估，估算出在这一时期内购买的平均收益率为，并预测出购买的风险损失率为。考虑到投资越分散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的中最大的一个风险来度量。 购买要付交易费，费率为，并且当购买额不超过给定值时，交易费按购买计算（不买当然无须付费）。另外，假定同期银行存款利率是, 且既无交易费又无风险。（） 1、已知时的相关数据如下： 试给该公司设计一种投资组合方案，即用给定的资金，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总体风险尽可能小。 2、试就一般情况对以上问题进行讨论，并利用以下数据进行计算。 本题需要我们设计一种投资组合方案，使收益尽可能大，而风险尽可能小。并给出对应的盈亏数据，以及一般情况的讨论。 这是一个优化问题，要决策的是每种资产的投资额，要达到目标包括两方面的要求:净收益最大和总风险最低，即本题是一个双优化的问题，一般情况下，这两个目标是矛盾的，因为净收益越大则风险也会随着增加，反之也是一样的，所以，我们很难或者不可能提出同时满足这两个目标的决策方案，我们只能做到的是：在收益一定的情况下，使得风险最小的决策，或者在风险一定的情况下，使得净收益最大，或者在收益和风险按确定好的偏好比例的情况下设计出最好的决策方案，这 数学建模有下面十种常用算法, 可供参考： 1.蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问 题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法） 2.数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数 据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3.线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多 数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4.图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算 法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5.动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算 法设计中比较常用的方法，很多场合可以用到竞赛中） 6.最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些 问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7.网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很 多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8.一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计 算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9.数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分 析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10.图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中 也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab 进行处理） 分数: ___________ 任课教师签字：___________ 华北电力大学研究生结课作业 学年学期：2013-2014第二学期 课程名称：优化理论和最优控制 学生姓名： 学号： 提交时间：2014年4月26日 《优化理论和最优控制》结课总结 摘要：最优控制理论是现代控制理论的核心，控制理论的发展来源于控制对象的要求。尽50年来，科学技术的迅速发展，对许多被控对象，如宇宙飞船、导弹、卫星、和现代工业设备的生产过程等的性能提出了更高的要求，在许多情况下要求系统的某种性能指标为最优。这就要求人们对控制问题都必须从最优控制的角度去进行研究分析和设计。最优控制理论研究的主要问题是：根据已建立的被控对象的时域数学模型或频域数学模型，选择一个容许的控制律，使得被控对象按预定要求运行，并使某一性能指标达到最优值[1]。 关键字：最优控制理论，现代控制理论，时域数学模型，频域数学模型，控制率 Abstract： The Optimal Control Theory is the core of the Modern Control Theory，the development of control theory comes from the requires of the controlled objects.During the 50 years， the rapid development of the scientific technology puts more stricter requires forward to mang controlled objects，such as the spacecraft，the guide missile，the satellite，the productive process of modern industrial facilities，and so on，and requests some performance indexes that will be best in mang cases.To the control problem，it requests people to research ,analyse，and devise from the point of view of the Optimal Control Theory. There are mang major problems of the Optimal Control Theory studying,such as the building the time domain’s model or the frenquency domain’s model according to the controlled objects,controlling a control law with admitting, making the controlled objects to work according to the scheduled requires, and making the performance index to reseach to a best optimal value. Keywords: The Optimal Control Theroy， The Modern Control Theroy， The 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) 数学建模中常见的十 大模型 精品文档 数学建模常用的十大算法==转 (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 题逢山开路，山体海拔高度的 收集于网络，如有侵权请联系管理员删除 根据对偶问题的定义知道，原问题与对偶问题是互为对偶的。在给出原问题的对偶问题过程中应注意的几点关系： (1) 原问题各约束条件中的限制符号，必须统一是“≤”或统一为“≥”，不必考虑向量b 的元素是否是正值； (2) 如原问题有等式约束，则将该条件用等价的两个不等式约束条件替换，即“k f =)x (”可改写成两个不等式条件“k f ≤)x (，k f -≤-)x (”； (3) 对偶前后都要求变量是非负的； (4) 对偶关系是，“极大”对“极小”；“≤”对“≥”；向量c 与向量b 对调位置；矩阵A 转置。 例3-14 给出以下线性规划问题的对偶问题 212max x x z += 12321≤+x x ； 521=+x x ； 16421≤+x x ； 21≥x ；02≥x 。 解：原问题的规范形式及对偶形式写在表3-17中。 表3-17 线性规划对偶问题 原问题 对偶问题 min 543212551612w w w w w s --++= max 212x x z += 1354321≥--++w w w w w 12321≤+x x ； 244321≥-++w w w w 16421≤+x x ； 0≥i w ，51≤≤i 。 521≤+x x ； 对偶问题的线性规划标准形式 521-≤--x x ； max 543212551612w w w w w s ++---= 21-≤-x ； 13654321=---++w w w w w w 01≥x ，02≥x 。 2474321=--++w w w w w 0≥i w ，71≤≤i 。 下面介绍线性规划对偶问题的一些性质。 定理3-4 在式(3-23)定义的对偶问题中，若x 和w 分别是原问题和对偶问题的任意可 行解，则一定有 w b x c T T ≤。 (3-24) 证 因为是可行解，必然满足各自的全部约束条件，即 b A ≤x ，0x ≥； c w T ≥A ，0w ≥。 由此导出， b w x w T T ≤A ； c x w x T T T ≥A 。 标量的转置就是标量本身，即 在手机普遍流行的今天，建设基站的问题分析对于运营商来说很有必要。本文针对现有的条件和题目的要求进行讨论。在建设此模型中，核心运用到了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 .什么是数学模型与数学建模
浅谈最优控制
数学建模路线优化问题
数学建模算法分类
数学建模常用的十种解题方法
数学建模中常见的十大模型
数学建模优化问题经典练习
最优化方法与最优控制复习文件
数学建模：投资问题
数学建模十种常用算法
优化理论和最优控制
数学建模面试最优化问题
数学建模中常见的十大模型讲课稿
最优化方法与最优控制5
数学建模课程设计——优化问题
数学建模中的优化问题与规划模型