下载文档原格式
数学建模中的图论方法一、引言我们知道，数学建模竞赛中有问题A和问题B。
一般而言，问题A是连续系统中的问题，问题B是离散系统中的问题。
由于我们在大学数学教育内容中，连续系统方面的知识的比例较大，而离散数学比例较小。
因此很多人有这样的感觉，A题入手快，而B题不好下手。
另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。
但是这类问题在MCM中非常少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个P类问题，不能显示参赛者的建模及解决实际问题能力之大小；还有一类所谓的NP问题，这种问题每一个都尚未建立有效的算法，也许真的就不可能有有效算法来解决。
命题往往以这种NPC问题为数学背景，找一个具体的实际模型来考验参赛者。
这样增加了建立数学模型的难度。
但是这也并不是说无法求解。
一般来说，由于问题是具体的实例，我们可以找到特殊的解法，或者可以给出一个近似解。
图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。
应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。
图论方法已经成为数学模型中的重要方法。
许多难题由于归结为图论问题被巧妙地解决。
而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如：AMCM90B－扫雪问题；AMCM91B－寻找最优Steiner树；AMCM92B－紧急修复系统的研制(最小生成树)AMCM94B－计算机传输数据的最小时间(边染色问题)CMCM93B－足球队排名(特征向量法)CMCM94B－锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性)CMCM98B－灾情巡视路线(最优回路)等等。
这里面都直接或是间接用到图论方面的知识。
要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。
《数学模型》作业解答第一章（2008年9月9日）4．在“椅子摆放问题”的假设条件中，将四脚的连线呈正方形改为呈长方形，其余条件不变.试构造模型并求解.解：设椅子四脚连线呈长方形ABCD. AB 与CD 的对称轴为x 轴，用中心点的转角θ表示椅子的位置.将相邻两脚A 、B 与地面距离之和记为)(θf ;C 、D 与地面距离之和记为)(θg .并旋转0180.于是，设,0)0(,0)0(=g f 就得到()()0,0=ππf g .数学模型：设()()θθg f 、是[]π2,0上θ的非负连续函数.若[]πθ2,0∈∀,有()()0=θθg f ,且()()()()0,0,00,00==ππf g f g ,则[]πθ2,00∈∃,使()()000==θθg f .模型求解:令)()()(θθθg f h -= .就有,0)0( h 0)(0)()()( ππππg g f h -=-=.再由()()θθg f ,的连续性,得到()θh 是一个连续函数. 从而()θh 是[]π,0上的连续函数.由连续函数的介值定理：()πθ,00∈∃,使()00=θh .即()πθ,00∈∃,使()()000=-θθg f .又因为[]πθ2,0∈∀,有()()0=θθg f .故()()000==θθg f .8. 假定人口的增长服从这样的规律：时刻t 的人口为)(t x ,单位时间内人口的增量与)(t x x m -成正比（其中m x 为最大容量）.试建立模型并求解.作出解的图形并与指数增长模型、阻滞增长模型的结果比较.解：现考察某地区的人口数，记时刻t 的人口数为()t x （一般()t x 是很大的整数）,且设()t x 为连续可微函数.又设()00|x t x t ==.任给时刻t 及时间增量t ∆,因为单位时间内人口增长量与)(t x x m -成正比, 假设其比例系数为常数r .则t 到t t ∆+内人口的增量为：()()()t t x x r t x t t x m ∆-=-∆+)(. 两边除以t ∆,并令0→∆t ,得到⎪⎩⎪⎨⎧=-=0)0()(x x x x r dtdxm 解为rtm m e x x x t x ---=)()(0如图实线所示，当t 充分大时 m x 它与Logistic 模型相近.0x t9．为了培养想象力、洞察力和判断力，考察对象时除了从正面分析外，还常常需要从侧面 或反面思考.试尽可能迅速回答下面问题：（1） 某甲早8：00从山下旅店出发，沿一条路径上山，下午5：00到达山顶并留宿. 次日早8：00沿同一路径下山，下午5：00回到旅店.某乙说，甲必在两天中的同一时刻经 过路径中的同一地点.为什么？（2） 37支球队进行冠军争夺赛，每轮比赛中出场的每两支球队中的胜者及轮空者 进入下一轮，直至比赛结束.问共需进行多少场比赛，共需进行多少轮比赛.如果是n 支球队比赛呢？（3） 甲乙两站之间有电车相通，每隔10分钟甲乙两站相互发一趟车，但发车时刻 不一定相同.甲乙之间有一中间站丙，某人每天在随机的时刻到达丙站，并搭乘最先经过丙站的那趟车，结果发现100天中约有90天到达甲站，仅约10天到达乙站.问开往甲乙两站的电车经过丙站的时刻表是如何安排的？（4） 某人家住T 市在他乡工作，每天下班后乘火车于6：00抵达T 市车站，他的 妻子驾车准时到车站接他回家，一日他提前下班搭早一班火车于5：30抵T 市车站，随即步行回家，他的妻子象往常一样驾车前来，在半路上遇到他，即接他回家，此时发现比往常 提前了10分钟.问他步行了多长时间？（5） 一男孩和一女孩分别在离家2 km 和1 km 且方向相反的两所学校上学，每天 同时放学后分别以4 km/h 和2 km/h 的速度步行回家.一小狗以6 km/h 的速度由男孩处奔向女孩，又从女孩处奔向男孩，如此往返直至回到家中，问小狗奔波了多少路程？如果男孩和女孩上学时小狗也往返奔波在他们之间，问当他们到达学校时小狗在何处？解：（1）方法一：以时间t 为横坐标，以沿上山路径从山下旅店到山顶的行程x 为纵坐标， 第一天的行程)(t x 可用曲线（I ）表示 ，第二天的行程)(t x 可用曲线（I I ）表示，（I ）（I I ）是连续曲线必有交点),(000d t p ,两天都在0t 时刻经过0d 地点.方法二：设想有两个人， 一人上山，一人下山，同一天同 时出发，沿同一路径,必定相遇. 0d t早8 0t 晚5方法三：我们以山下旅店为始点记路程,设从山下旅店到山顶的路程函数为)(t f (即t 时刻走的路程为)(t f ),同样设从山顶到山下旅店的路函数为)(t g ,并设山下旅店到山顶的距离为a (a >0).由题意知：,0)8(=f a f =)17(,a g =)8(,0)17(=g .令)()()(t g t f t h -=,则有0)8()8()8(<-=-=a g f h ，0)17()17()17(>=-=a g f h ，由于)(t f ,)(t g 都是时间t 的连续函数,因此)(t h 也是时间t 的连续函数,由连续函数的介值定理,]17,8[0∈∃t ,使0)(0=t h ,即)()(00t g t f =.（2）36场比赛，因为除冠军队外，每队都负一场；6轮比赛，因为2队赛1轮，4队赛2轮，32队赛5轮. n 队需赛1-n 场，若k k n 221≤- ，则需赛k 轮.（3）不妨设从甲到乙经过丙站的时刻表是8：00，8：10，8：20，…… 那么从乙到甲经过丙站的时刻表应该是8：09，8：19，8：29……（4）步行了25分钟.设想他的妻子驾车遇到他后，先带他前往车站，再回家，汽车多行驶了10分钟，于是带他去车站这段路程汽车多跑了5分钟，而到车站的时间是6：00，所以妻子驾车遇到他的时刻应该是5：55.（5）放学时小狗奔跑了3 km .孩子上学到学校时小狗的位置不定（可在任何位置），因为设想放学时小狗在任何位置开始跑，都会与孩子同时到家.之所以出现位置不定的结果，是由于上学时小狗初始跑动的那一瞬间，方向无法确定.10*. 某人第一天上午9：00从甲地出发，于下午6：00到达乙地.第二天上午9：00他又从乙地出发按原路返回，下午6：00回到甲地.试说明途中存在一点，此人在两天中同一时间到达该处.若第二天此人是下午4：00回到甲地，结论将如何？答：（方法一）我们以甲地为始点记路程,设从甲地到乙地的路程函数为)(t f (即t 时刻走的路程为)(t f ),同样设从乙地到甲地的路函数为)(t g ,并设甲地到乙地的距离为a (a >0).由题意知：,0)9(=f a f =)18(,a g =)9(,0)18(=g . 令)()()(t g t f t h -=,则有0)9()9()9(<-=-=a g f h ，0)18()18()18(>=-=a g f h 由于)(t f ,)(t g 都是时间t 的连续函数,因此)(t h 也是时间t 的连续函数,由连续函数的介值定理,]18,9[0∈∃t ,使0)(0=t h ,即)()(00t g t f =. 若第二天此人是下午4：00回到甲地,则结论仍然正确,这是因为0)9()9()9(<-=-=a g f h ，0)16()16()16()16(>=-=f g f h .（方法二）此题可以不用建模的方法,而变换角度考虑：设想有两个人，一人从甲地到乙地,另一人从乙地到甲地,同一天同时出发,沿同一路径,必定相遇.若第二天此人是下午4：00回到甲地,则结论仍然正确.《数学模型》作业解答第二章(1)（2008年9月16日）1． 学校共1000名学生，235人住在A 宿舍，333人住在B 宿舍，432人住在C 宿舍.学生们要组织一个10人的委员会，试用下列办法分配各宿舍的委员数：（1）. 按比例分配取整数的名额后,剩下的名额按惯例分给小数部分较大者; （2）. §1中的Q 值方法；（3）.d ’Hondt 方法：将A 、B 、C 各宿舍的人数用正整数n=1,2,3,……相除，其商数如下表：将所得商数从大到小取前10个（10为席位数），在数字下标以横线，表中A 、B 、C 行有横线的数分别为2，3，5，这就是3个宿舍分配的席位.你能解释这种方法的道理吗？如果委员会从10个人增至15人，用以上3种方法再分配名额，将3种方法两次分配的结果列表比较.解：先考虑N=10的分配方案，,432 ,333 ,235321===p p p ∑==31.1000i ip方法一（按比例分配） ,35.23111==∑=i ipNp q ,33.33122==∑=i ipNp q 32.43133==∑=i ipNp q分配结果为： 4 ,3 ,3321===n n n 方法二（Q 值方法）9个席位的分配结果（可用按比例分配）为：4 ,3 ,2321===n n n第10个席位：计算Q 值为,17.92043223521=⨯=Q ,75.92404333322=⨯=Q 2.93315443223=⨯=Q3Q 最大，第10个席位应给C.分配结果为 5 ,3 ,2321===n n n方法三（d ’Hondt 方法）此方法的分配结果为：5 ,3 ,2321===n n n此方法的道理是：记i p 和i n 为各宿舍的人数和席位（i=1,2,3代表A 、B 、C 宿舍）.iin p 是每席位代表的人数，取,,2,1 =i n 从而得到的i i n p 中选较大者，可使对所有的,i ii n p尽量接近.再考虑15=N 的分配方案，类似地可得名额分配结果.现将3种方法两次分配的结果列表如下：2． 试用微积分方法，建立录像带记数器读数n 与转过时间的数学模型. 解： 设录像带记数器读数为n 时，录像带转过时间为t.其模型的假设见课本.考虑t 到t t ∆+时间内录像带缠绕在右轮盘上的长度，可得,2)(kdn wkn r vdt π+=两边积分，得⎰⎰+=ntdn wkn r k vdt 0)(2π)22 2n wk k(r n πvt +=∴ .2 22n vk w n v rk t ππ+=∴第二章(2)（2008年10月9日）15．速度为v 的风吹在迎风面积为s 的风车上，空气密度是ρ ，用量纲分析方法确定风车获得的功率P 与v 、S 、ρ的关系.解: 设P 、v 、S 、ρ的关系为0),,,(=ρs v P f ， 其量纲表达式为: [P]=32-TML , [v ]=1-LT,[s ]=2L ,[ρ]=3-ML ,这里T M L ,,是基本量纲.量纲矩阵为：A=)⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---ρ()()()()()()(001310013212s v P T M L齐次线性方程组为：⎪⎩⎪⎨⎧=--=+=-++030032221414321y y y y y y y y 它的基本解为)1,1,3,1(-=y由量纲i P 定理得 1131ρπs v P -=， 113ρλs v P =∴ ， 其中λ是无量纲常数. 16．雨滴的速度v 与空气密度ρ、粘滞系数μ和重力加速度g 有关，其中粘滞系数的定义是：运动物体在流体中受的摩擦力与速度梯度和接触面积的乘积成正比，比例系数为粘滞系数，用量纲分析方法给出速度v 的表达式.解：设v ,ρ,μ,g 的关系为(f v ,ρ,μ,g )=0.其量纲表达式为[v ]=LM 0T -1，[ρ]=L -3MT 0，[μ]=MLT -2（LT -1L -1）-1L -2=MLL -2T -2T=L -1MT -1，[g ]=LM 0T -2,其中L ，M ，T 是基本量纲.量纲矩阵为A=)()()()()()()(210101101131g v T M L μρ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡----- 齐次线性方程组Ay=0 ，即⎪⎩⎪⎨⎧==+=+02y -y - y -0y y 0y y -3y -y 431324321 的基本解为y=(-3 ,-1 ,1 ,1)由量纲i P 定理 得 g v μρπ13--=. 3ρμλgv =∴，其中λ是无量纲常数. 16*．雨滴的速度v 与空气密度ρ、粘滞系数μ、特征尺寸γ和重力加速度g 有关，其中粘滞系数的定义是：运动物体在流体中受的摩擦力与速度梯度和接触面积的乘积成正比，比例系数为粘滞系数，用量纲分析方法给出速度v 的表达式.解：设v ,ρ,μ,γ，g 的关系为0),,,,(=g v f μργ.其量纲表达式为[v ]=LM 0T -1，[ρ]=L -3MT 0，[μ]=MLT -2（LT -1L -1）-1L -2=MLL -2T -2T=L -1MT -1，[γ]=LM 0T 0 ，[g ]=LM 0T -2其中L ，M ，T 是基本量纲. 量纲矩阵为A=)()()()()()()()(21010110011311g v T M L μργ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-----齐次线性方程组Ay=0 即⎪⎩⎪⎨⎧=---=+=+--+020035414354321y y y y y y y y y y 的基本解为⎪⎩⎪⎨⎧---=--=)21,1,1,23,0()21,0,0,21,1(21y y得到两个相互独立的无量纲量⎩⎨⎧==-----2/112/322/12/11g g v μργπγπ 即 1212/12/31,--==πμργπγg g v . 由0),(21=Φππ , 得 )(121-=πϕπ∴ )(12/12/3-=μργϕγυg g , 其中ϕ是未定函数.20.考察阻尼摆的周期，即在单摆运动中考虑阻力，并设阻力与摆的速度成正比.给出周期的表达式，然后讨论物理模拟的比例模型，即怎样由模型摆的周期计算原型摆的周期. 解：设阻尼摆周期t ,摆长l , 质量m ,重力加速度g ，阻力系数k 的关系为0),,,,(=k g m l t f其量纲表达式为：112120000000)(]][[][,][,][,][,][-----======LT MLT v f k T LM g MT L m T LM l T M L t 10-=MT L ， 其中L ，M ，T 是基本量纲.量纲矩阵为A=)()()()()()()()(120011010001010k g m l t T M L ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-- 齐次线性方程组⎪⎩⎪⎨⎧=--=+=+02005415342y y y y y y y 的基本解为⎪⎩⎪⎨⎧--=-=)1,21,1,21,0()0,21,0,21,1(21Y Y 得到两个相互独立的无量纲量∴g l t =1π, )(21πϕπ=, 2/12/12mg kl =π ∴)(2/12/1mg kl g l t ϕ=，其中ϕ是未定函数 . 考虑物理模拟的比例模型，设g 和k 不变，记模型和原型摆的周期、摆长、质量分别为t ,'t ；l ,'l ;m ,'m . 又)(2/12/1g m l k g l t '''='ϕ 当无量纲量l l mm '='时， 就有 ll l g g l tt '=⋅'='. 《数学模型》作业解答第三章1（2008年10月14日）1. 在3.1节存贮模型的总费用中增加购买货物本身的费用,重新确定最优订货周期和订货批量．证明在不允许缺货模型中结果与原来的一样，而在允许缺货模型中最优订货周期和订货批量都比原来结果减少．解：设购买单位重量货物的费用为k ,其它假设及符号约定同课本．01 对于不允许缺货模型，每天平均费用为：kr rTc T c T C ++=2)(212221r c Tc dT dC+-= 令0=dTdC， 解得 rc c T 21*2= ⎩⎨⎧==---22/112/112/12/1ππk g m l g tl由rT Q = ， 得212c rc rT Q ==** 与不考虑购货费的结果比较，Ｔ、Ｑ的最优结果没有变．02 对于允许缺货模型，每天平均费用为：⎥⎦⎤⎢⎣⎡+-++=kQ Q rT r c r Q c c T Q T C 23221)(221),(2223322221222T kQ rT Q c r c rT Q c T c T C--+--=∂∂Tk rT Q c c rT Qc Q C ++-=∂∂332 令⎪⎪⎩⎪⎪⎨⎧=∂∂=∂∂00Q CTC， 得到驻点：⎪⎪⎩⎪⎪⎨⎧+-+-+=-+=**323222233232132233221)(22c c krc c c r k c c c c c r c Q c c k c c c rc c T与不考虑购货费的结果比较，Ｔ、Ｑ的最优结果减少．2．建立不允许缺货的生产销售存贮模型．设生产速率为常数k ，销售速率为常数r ，r k >．在每个生产周期Ｔ内，开始的一段时间()00T t <<一边生产一边销售，后来的一段时间)(0T t T <<只销售不生产，画出贮存量)(t g 的图形.设每次生产准备费为1c ，单位时间每件产品贮存费为2c ，以总费用最小为目标确定最优生产周期，讨论r k >>和r k ≈的情况.解：由题意可得贮存量)(t g 的图形如下：贮存费为 ∑⎰=→∆⋅-==∆ni Ti i t TT r k c dt t g c t g c 1022022)()()(limξ又 )()(00T T r T r k -=- ∴ T k r T =0 , ∴ 贮存费变为 kTT r k r c 2)(2⋅-=于是不允许缺货的情况下，生产销售的总费用（单位时间内）为kTr k r c T c kT T r k r c T c T C 2)(2)()(21221-+=-+=k r k r c Tc dT dC 2)(221-+-=. 0=dT dC令, 得)(221r k r c k c T -=* 易得函数处在*T T C )(取得最小值，即最优周期为： )(221r k r c kc T -=*rc c ，Tr k 212≈>>*时当 . 相当于不考虑生产的情况. ∞→≈*，Tr k 时当 . 此时产量与销量相抵消，无法形成贮存量.第三章2（2008年10月16日）3．在3.3节森林救火模型中，如果考虑消防队员的灭火速度λ与开始救火时的火势b 有关，试假设一个合理的函数关系，重新求解模型.解：考虑灭火速度λ与火势b 有关，可知火势b 越大，灭火速度λ将减小，我们作如下假设: 1)(+=b kb λ， 分母∞→→+λ时是防止中的011b b 而加的. 总费用函数()xc b kx b x t c b kx b t c t c x C 3122121211)1()(2)1(2+--++--++=βββββββ最优解为 []k b k c b b b c kbc x ββ)1(2)1()1(223221+++++=5．在考虑最优价格问题时设销售期为T ，由于商品的损耗，成本q 随时间增长，设t q t q β+=0)(，为增长率β.又设单位时间的销售量为)(为价格p bp a x -=.今将销售期分为T t TT t <<<<220和两段，每段的价格固定，记作21,p p .求21,p p 的最优值，使销售期内的总利润最大.如果要求销售期T 内的总售量为0Q ，再求21,p p 的最优值. 解：按分段价格，单位时间内的销售量为⎪⎩⎪⎨⎧<<-<<-=T t T bp a T t bp a x 2,20,21又 t q t q β+=0)(.于是总利润为[][]⎰⎰--+--=22221121)()()()(),(TTT dt bp a t q p dt bp a t q p p p=22)(022)(20222011T Tt t q t p bp a T t t q t p bp a ⎥⎦⎤⎢⎣⎡---+⎥⎦⎤⎢⎣⎡---ββ=)8322)(()822)((20222011T t q T p bp a T T q T p bp a ββ---+--- )(2)822(12011bp a T T T q T p b p -+---=∂∂β )(2)8322(22022bp a TT t q T p b p -+---=∂∂β 0,021=∂∂=∂∂p p 令, 得到最优价格为: ⎪⎪⎩⎪⎪⎨⎧⎥⎦⎤⎢⎣⎡++=⎥⎦⎤⎢⎣⎡++=)43(21)4(210201T q b a b p T q b a b p ββ 在销售期T 内的总销量为⎰⎰+-=-+-=20221210)(2)()(T TT p p bTaT dt bp a dt bp a Q 于是得到如下极值问题：)8322)(()822)((),(m ax 2022201121T t q T p bp a T T q T p bp a p p ββ---+---=t s . 021)(2Q p p bTaT =+-利用拉格朗日乘数法，解得：⎪⎩⎪⎨⎧+-=--=880201TbT Q b a p T bT Q b a p ββ 即为21,p p 的最优值.第三章3（2008年10月21日）6. 某厂每天需要角钢100吨，不允许缺货.目前每30天定购一次，每次定购的费用为2500元.每天每吨角钢的贮存费为0.18元.假设当贮存量降到零时订货立即到达.问是否应改变订货策略？改变后能节约多少费用？解：已知：每天角钢的需要量r=100(吨);每次订货费1c ＝2500（元）; 每天每吨角钢的贮存费2c ＝0.18（元）.又现在的订货周期T 0＝30（天） 根据不允许缺货的贮存模型：kr rT c T c T C ++=2121)( 得：k T TT C 10092500)(++=令0=dTdC， 解得：35092500*==T 由实际意义知：当350*=T （即订货周期为350）时，总费用将最小. 925002+-=TdT dC又k T C 10035095025003)(*+⨯+⨯=＝300＋100k k T C 100309302500)(0+⨯+==353．33＋100k)(0T C －)(*T C ＝（353.33＋100k ）－（300＋100k ）32＝53．33.故应改变订货策略.改变后的订货策略（周期）为T *=350，能节约费用约53．33元.《数学模型》作业解答第四章（2008年10月28日）1. 某厂生产甲、乙两种产品,一件甲产品用A 原料1千克, B 原料5千克；一件乙产品用A 原料2千克,B 原料4千克.现有A 原料20千克, B 原料70千克.甲、乙产品每件售价分别为20元和30元.问如何安排生产使收入最大？ 解：设安排生产甲产品x 件,乙产品y 件，相应的利润为S 则此问题的数学模型为：max S=20x+30ys.t. ⎪⎩⎪⎨⎧∈≥≤+≤+Z y x y x y x y x ,,0,7045202这是一个整线性规划问题，现用图解法进行求解可行域为：由直线1l ：x+2y=20, 2l :5x+4y ＝702l以及x=0,y=0组成的凸四边形区域. 直线l ：20x+30y=c 在可行域内 平行移动.易知：当l 过1l 与2l 的交点时， x S 取最大值. 由⎩⎨⎧=+=+7045202y x y x 解得⎩⎨⎧==510y x此时 m ax S ＝2053010⨯+⨯＝350（元）2. 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量以及可获利润如下表：货物 体积（立方米/箱）重量 （百斤/箱）利润 （百元/箱）甲 5 2 20 乙4510已知这两种货物托运所受限制是体积不超过24立方米，重量不超过13百斤.试问这两种货物各托运多少箱，使得所获利润最大，并求出最大利润.解:设甲货物、乙货物的托运箱数分别为1x ,2x ,所获利润为z .则问题的数学模型可表示为211020 m ax x x z +=⎪⎩⎪⎨⎧∈≥≤+≤+Z y x x x x x x x st ,,0,13522445212121这是一个整线性规划问题. 用图解法求解. 可行域为：由直线2445:211=+x x l1352:212=+x x l 及0,021==x x 组成直线 c x x l =+211020:在此凸四边形区域内平行移动.易知：当l 过l 1与l 2的交点时，z 取最大值 由⎩⎨⎧=+=+135224452121x x x x 解得 ⎩⎨⎧==1421x x90110420max =⨯+⨯=z .3．某微波炉生产企业计划在下季度生产甲、乙两种型号的微波炉.已知每台甲型、乙型微波炉的销售利润分别为3和2个单位.而生产一台甲型、乙型微波炉所耗原料分别为2和32ll1x1l2x个单位,所需工时分别为4和2个单位.若允许使用原料为100个单位,工时为120个单位,且甲型、乙型微波炉产量分别不低于6台和12台.试建立一个数学模型,确定生产甲型、乙型微波炉的台数,使获利润最大．并求出最大利润.解：设安排生产甲型微波炉x 件,乙型微波炉y 件,相应的利润为S. 则此问题的数学模型为：max S=3x +2ys.t. ⎪⎩⎪⎨⎧∈≥≥≤+≤+Z y x y x y x y x ,,12,61202410032这是一个整线性规划问题 用图解法进行求解可行域为：由直线1l ：2x+3y=100, 2l :4x+2y ＝120 及x=6,y=12组成的凸四边形区域.直线l ：3x+2y=c 在此凸四边形区域内平行移动. 易知：当l 过1l 与2l 的交点时, S 取最大值.由⎩⎨⎧=+=+1202410032y x y x 解得⎩⎨⎧==2020y x .m ax S ＝320220⨯+⨯＝100.《数学模型》作业解答第五章1（2008年11月12日）1.对于5.1节传染病的SIR 模型，证明：（1）若处最大先增加，在则σσ1)(,10=s t i s ，然后减少并趋于零；)(t s 单调减少至.∞s（2）.)()(,10∞s t s t i s 单调减少至单调减少并趋于零，则若σ解：传染病的SIR 模型（14）可写成⎪⎩⎪⎨⎧-=-=i s dtds s i dt diλσμ)1(.)(lim 0.(t) .)( .0,t 存在而单调减少知由∞∞→=∴≥-=s t s s t s dtdsi s dt ds λ.)(∞s t s 单调减少至故（1）.s s(t) .s(t) .100≤∴单调减少由若σs;)(,0 .01,10单调增加时当t i dtdis s s ∴-σσ.)(,0 .01,1单调减少时当t i dtdis s ∴-σσ.0)(lim .0)18(t ==∞→∞t i i 即式知又由书上.)( .0,1m i t i dtdis 达到最大值时当∴==σ（2）().0 0.1-s ,1,10 dtdit s s σσσ从而则若()().0.0lim ==∴∞∞→i t i t i t 即单调减少且4．在5.3节正规战争模型（3）中，设乙方与甲方战斗有效系数之比为.4=ba初始兵力00y x 与相同.(1) 问乙方取胜时的剩余兵力是多少,乙方取胜的时间如何确定.(2) 若甲方在战斗开始后有后备部队以不变的速率r 增援,重新建立模型,讨论如何判断双方的胜负.解:用()()t y t x ,表示甲、乙交战双方时刻t 的士兵人数,则正规战争模型可近似表示为:()()()⎪⎪⎩⎪⎪⎨⎧==-=-=000,01 ,yy x x bx dtdyay dt dx现求(1)的解: (1)的系数矩阵为⎥⎦⎤⎢⎣⎡--=00b a Aab ab b aA E ±=∴=-==-1,22 .0λλλλλ⎪⎪⎭⎫⎝⎛⎪⎪⎭⎫⎝⎛-1212,21，对应的特征向量分别为λλ ()()()tab t ab eC e C t y t x -⎪⎪⎭⎫ ⎝⎛+⎪⎪⎭⎫⎝⎛-=⎪⎪⎭⎫ ⎝⎛∴1212121的通解为.再由初始条件，得()()2 220000 tab tab e y x ey x t x -⎪⎭⎫ ⎝⎛++⎪⎭⎫ ⎝⎛-=又由().1aybx dx dy =可得其解为 ()3 ,202022 bx ay k k bx ay -==-而(1) ()().231000202011y a b y a bx ay ak t y t x =-=-===时，当 即乙方取胜时的剩余兵力数为.230y又令().0222,01100001=-⎪⎭⎫⎝⎛++⎪⎭⎫⎝⎛-=t ab t ab e y x e y x t x ）得由（注意到000020022,1x y y x ey x t ab -+==得. .43ln ,3121bt et ab =∴=∴ (2) 若甲方在战斗开始后有后备部队以不变的速率r 增援.则()()⎪⎪⎩⎪⎪⎨⎧==-=+-=000,)0(4 yy x x bx dtdyr ay dt dx().,4rdy aydy bxdx bxray dy dx -=-+-=即得由 相轨线为,222k bx ry ay =-- .222220.020k a r bx a r y a bx ry ay k =--⎪⎭⎫ ⎝⎛---=或 此相轨线比书图11中的轨线上移了.a r 乙方取胜的条件为.,0222020a r x a b a r y k +⎪⎭⎫ ⎝⎛- 亦即 第五章2（2008年11月14日）6. 模仿5.4节建立的二室模型来建立一室模型（只有中心室），在快速静脉注射、恒速静脉滴注（持续时间为τ）和口服或肌肉注射3种给药方式下求解血药浓度，并画出血药浓度曲线的图形.解: 设给药速率为(),0t f()()()()().,,0/t VC t x t f t kx t x k ==+则排除速率为常数(1)快速静脉注射: 设给药量为,0D 则()()().,0,0000t k e VDt C V D C t f -===解得 (2)恒速静脉滴注(持续时间为τ): 设滴注速率为()(),00,000==C k t f k ，则解得()()()()⎪⎩⎪⎨⎧-≤≤-=----τττ t e e Vkk t e Vkk t C t k kt kt,10 ,10(3) 口服或肌肉注射: ()()，解得）式节（见134.5010010tk eD k t f -=()()()⎪⎪⎩⎪⎪⎨⎧=≠--=---010101001 ,,01k k te VkD k k e e k k V D k t C kt t k kt3种情况下的血药浓度曲线如下：第五章3（2008年11月18日）8. 在5.5节香烟过滤嘴模型中,(1) 设3.0,/50,08.0,02.0,20,80,80021=======a s mm b mm l mm l mg M νβ求./21Q Q Q 和(2) 若有一支不带过滤嘴的香烟,参数同上,比较全部吸完和只吸到1l 处的情况下，进入人体毒物量的区别.解)(857563.229102.07.050103.01508002.07.0502008.0/01/2毫克≈⎪⎪⎭⎫ ⎝⎛-⨯⨯⨯=⎪⎪⎭⎫ ⎝⎛-=⨯⨯-⨯---e e e eba v aw Q v bl a vl β ()10/10==l M w 其中，()()97628571.0502002.008.0212===⨯----ee Q Q vl b β(2) 对于一支不带过滤嘴的香烟,全部吸完的毒物量为⎪⎪⎭⎫⎝⎛-=-vbl a e b a v aw Q '103‘ 只吸到1l 处就扔掉的情况下的毒物量为⎪⎪⎭⎫ ⎝⎛-=--vbl a v ble e b a v aw Q 1'21'04 .256531719.1110096.0032.0012.004.0508002.03.0508002.05010002.03.05010002.043111'1'≈--=--=--=⎪⎪⎭⎫ ⎝⎛-⎪⎪⎭⎫ ⎝⎛-=⨯⨯⨯⨯⨯⨯--e e e e e e e e e e e e e e e e Q Q v abl v bl v abl v bl v bl a v bl v bl a vbl 44.235,84.29543≈≈ ＱQ4．在5.3节正规战争模型（3）中，设乙方与甲方战斗有效系数之比为.4=ba初始兵力00y x 与相同.(1) 问乙方取胜时的剩余兵力是多少,乙方取胜的时间如何确定.(2) 若甲方在战斗开始后有后备部队以不变的速率r 增援,重新建立模型,讨论如何判断双方的胜负.解:用()()t y t x ,表示甲、乙交战双方时刻t 的士兵人数,则正规战争模型可近似表示为:()()()⎪⎪⎩⎪⎪⎨⎧==-=-=000,01 ,yy x x bx dtdyay dt dx现求(1)的解: (1)的系数矩阵为⎥⎦⎤⎢⎣⎡--=00b a Aab ab b aA E ±=∴=-==-1,22 .0λλλλλ⎪⎪⎭⎫⎝⎛⎪⎪⎭⎫⎝⎛-1212,21，对应的特征向量分别为λλ ()()()tab t ab eC e C t y t x -⎪⎪⎭⎫ ⎝⎛+⎪⎪⎭⎫⎝⎛-=⎪⎪⎭⎫ ⎝⎛∴1212121的通解为.再由初始条件，得()()2 220000 tab tab e y x ey x t x -⎪⎭⎫ ⎝⎛++⎪⎭⎫ ⎝⎛-=又由().1aybx dx dy =可得其解为 ()3 ,202022 bx ay k k bx ay -==-而(1) ()().231000202011y a b y a bx ay ak t y t x =-=-===时，当 即乙方取胜时的剩余兵力数为.230y 又令().0222,01100001=-⎪⎭⎫⎝⎛++⎪⎭⎫⎝⎛-=t ab t ab e y x e y x t x ）得由（注意到000020022,1x y y x ey x t ab -+==得. .43ln ,3121bt et ab =∴=∴ (2) 若甲方在战斗开始后有后备部队以不变的速率r 增援.则()()⎪⎪⎩⎪⎪⎨⎧==-=+-=000,)0(4 yy x x bx dtdyr ay dt dx().,4rdy aydy bxdx bxray dy dx -=-+-=即得由 相轨线为,222k bx ry ay =-- .222220.02k a r bx a r y a bx ry ay k =--⎪⎭⎫ ⎝⎛---=或 此相轨线比书图11中的轨线上移了.a r 乙方取胜的条件为.,0222020a r x a b a r y k +⎪⎭⎫ ⎝⎛- 亦即《数学模型》作业解答第六章（2008年11月20日）1.在6.1节捕鱼模型中，如果渔场鱼量的自然增长仍服从Logistic 规律，而单位时间捕捞量为常数h ．(1)分别就4/rN h >，4/rN h <，4/rN h =这3种情况讨论渔场鱼量方程的平衡点及其稳定状况．(2)如何获得最大持续产量，其结果与6.1节的产量模型有何不同．解：设时刻t 的渔场中鱼的数量为()t x ，则由题设条件知：()t x 变化规律的数学模型为h Nxrx dt t dx --=)1()( 记h Nxrx x F --=)1()( (1).讨论渔场鱼量的平衡点及其稳定性： 由()0=x F ，得0)1(=--h Nxrx ． 即()102=+-h rx x Nr )4(42Nhr r N rh r -=-=∆ ， (1)的解为：2412,1N rNhN x -±=①当4/rN h >，0<∆，(1)无实根，此时无平衡点； ②当4/rN h =，0=∆，(1)有两个相等的实根，平衡点为20N x =. Nrxr N rx N x r x F 2)1()('-=--=，0)(0'=x F 不能断定其稳定性. 但0x x ∀ 及0x x 均有04)1()( rNN x rx x F --= ，即0 dtdx ．∴0x 不稳定；③当4/rN h <，0>∆时，得到两个平衡点：2411N rNhN x --=， 2412N rNh N x -+=易知：21N x <， 22N x > ，0)(1'>x F ，0)(2'<x F ∴平衡点1x 不稳定，平衡点2x 稳定.(2)最大持续产量的数学模型为⎩⎨⎧=0)(..max x F t s h即 )1(max Nxrx h -=， 易得 2*0N x = 此时 4rN h =，但2*0N x =这个平衡点不稳定．这是与6.1节的产量模型不同之处．要获得最大持续产量，应使渔场鱼量2N x >，且尽量接近2N ，但不能等于2N ． 2.与Logistic 模型不同的另一种描述种群增长规律的是Gompertz 模型：()xNrx t x ln '=．其中r 和N 的意义与Logistic 模型相同．设渔场鱼量的自然增长服从这个模型，且单位时间捕捞量为Ex h =．讨论渔场鱼量的平衡点及其稳定性，求最大持续产量m h 及获得最大产量的捕捞强度m E 和渔场鱼量水平*0x ．解：()t x 变化规律的数学模型为()Ex xNrx dt t dx -=ln 记 Ex xNrx x F -=ln)( ① 令()0=x F ，得0ln =-Ex xNrx ∴r ENe x -=0，01=x ．∴平衡点为1,0x x . 又 ()E r xNr x F --=ln'，()()∞=<-=1'0',0x F r x F ． ∴ 平衡点o x 是稳定的，而平衡点1x 不稳定.②最大持续产量的数学模型为：⎪⎩⎪⎨⎧≠=-=.0,0ln ..max x Ex x N rx t s Ex h Ex()x f由前面的结果可得 rE ENeh -=r Er Ee r EN Ne dE dh ---=，令.0=dEdh 得最大产量的捕捞强度r E m =．从而得到最大持续产量e rN h m /=，此时渔场鱼量水平eNx =*0． 3．设某渔场鱼量)(t x (时刻t 渔场中鱼的数量)的自然增长规律为：)1()(Nxrx dt t dx -= 其中r 为固有增长率,`N 为环境容许的最大鱼量. 而单位时间捕捞量为常数h .10．求渔场鱼量的平衡点,并讨论其稳定性;20．试确定捕捞强度m E ,使渔场单位时间内具有最大持续产量m Q ,求此时渔场鱼量水平*0x . 解：10．)(t x 变化规律的数学模型为h Nxrx dt t dx --=)1()( 记h N x rx x f --=)1()(,令 0)1(=--h N x rx ，即 02=+-h rx x Nr ----（1）)4(42Nhr r N rh r -=-=∆ ， （1）的解为：2412,1N rNhN x -±=① 当0 ∆时，（1）无实根，此时无平衡点； ② 当0=∆时，（1）有两个相等的实根，平衡点为20Nx =. Nrx r N rx N x r x f 2)1()('-=--= ，0)(0'=x f 不能断定其稳定性. 但0x x ∀ 及0x x 均有04)1()( rN N x rx x f --= ，即0 dt dx∴0x 不稳定； ③ 当0 ∆时，得到两个平衡点：2411rNhN N x --=， 2412rNh N N x -+=易知 21N x， 22N x ∴0)('1 x f ， 0)('2 x f ∴平衡点1x 不稳定 ，平衡点2x 稳定.20．最大持续产量的数学模型为： ⎩⎨⎧=0)(..max x f t s h即 )1(max Nx rx h -=，易得 2*0N x = 此时 4rN h =，但2*0N x =这个平衡点不稳定. 要获得最大持续产量，应使渔场鱼量2N x ,且尽量接近2N ,但不能等于2N.《数学模型》第七章作业（2008年12月4日）1．对于7.1节蛛网模型讨论下列问题：（1）因为一个时段上市的商品不能立即售完，其数量也会影响到下一时段的价格，所以第1+k 时段的价格1+k y 由第1+k 和第k 时段的数量1+k x 和k x 决定，如果仍设1+k x 仍只取决于k y ，给出稳定平衡的条件，并与7.1节的结果进行比较.2．已知某商品在k 时段的数量和价格分别为k x 和k y ，其中1个时段相当于商品的一个生产周期.设该商品的需求函数和供应函数分别为)(k k x f y =和)2(11-++=k k k y y g x .试建立关于商品数量的差分方程模型，并讨论稳定平衡条件.3． 已知某商品在k 时段的数量和价格分别为k x 和k y ，其中1个时段相当于商品的一个生产周期.设该商品的需求函数和供应函数分别为)2(11kk k x x f y +=++和)(1k k y g x =+.试建立关于商品数量的差分方程模型，并讨论稳定平衡条件.《数学模型》作业解答第七章（2008年12月4日）2． 对于7.1节蛛网模型讨论下列问题：（1）因为一个时段上市的商品不能立即售完，其数量也会影响到下一时段的价格，所以第1+k 时段的价格1+k y 由第1+k 和第k 时段的数量1+k x 和k x 决定，如果仍设1+k x 仍只取决于k y ，给出稳定平衡的条件，并与7.1节的结果进行比较.（2）若除了1+k y 由1+k x 和k x 决定之外，1+k x 也由前两个时段的价格k y 和1-k y 确定.试分析稳定平衡的条件是否还会放宽.解：（1）由题设条件可得需求函数、供应函数分别为：⎪⎩⎪⎨⎧=+=+++)()2(111k k k k k y h x x x f y 在),(000y x P 点附近用直线来近似曲线h f ,，得到⎪⎩⎪⎨⎧>-=->-+-=-+++)2( 0, )()1( 0),2(0010101 ββααy y x x x x x y y k k k k k 由（2）得 )3( )(0102 y y x x k k -=-++β （1）代入（3）得 )2(0102x x x x x kk k -+-=-++αβ0012222 x x x x x k k k αβαβαβ+=++∴++对应齐次方程的特征方程为 02 2=++αβαβλλ特征根为48)(22,1αβαβαβλ-±-=当8≥αβ时，则有特征根在单位圆外，设8<αβ，则248)()4(2222,1αβαβαβαβλ=+-+= 2 12,1<⇔<∴αβλ即平衡稳定的条件为2<αβ与207P 的结果一致. （2）此时需求函数、供应函数在),(000y x P 处附近的直线近似表达式分别为：⎪⎩⎪⎨⎧>-+=->-+-=--+++)5( 0 , )2()4( 0),2(01010101ββααy y y x x x x x y y k k k k k k 由（5）得，)( ) y y y β(y )x (x k k k 62010203 -+-=-+++ 将（4）代入（6），得 ⎥⎦⎤⎢⎣⎡-+--+-=-++++)2()2()(20101203x x x x x x x x k k k k k ααβ 001234424 x x x x x x k k k k αβαβαβαβ+=+++∴+++对应齐次方程的特征方程为(7) 024 23=+++αβαβλαβλλ 代数方程（7）无正实根，且42 ,αβαβ---, αβ不是（7）的根.设（7）的三个非零根分别为321,,λλλ，则⎪⎪⎪⎩⎪⎪⎪⎨⎧-==++-=++424321133221321αβλλλαβλλλλλλαβλλλ 对（7）作变换：,12αβμλ-=则,03=++q p μμ其中 )6128(41 ),122(412233322αββαβαβααβ+-=-=q p 用卡丹公式：⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧+--+++-=+--+++-=+--+++-=33233223332233223323321)3()2(2)3()2(2)3()2(2)3()2(2)3()2(2)3()2(2p q q w p q q w p q q w p q q w pq q p q q μμμ 其中,231i w +-=求出321,,μμμ，从而得到321,,λλλ，于是得到所有特征根1<λ的条件.2．已知某商品在k 时段的数量和价格分别为k x 和k y ，其中1个时段相当于商品的一个生产周期.设该商品的需求函数和供应函数分别为)(k k x f y =和)2(11-++=k k k y y g x .试建立关于商品数量的差分方程模型，并讨论稳定平衡条件.解：已知商品的需求函数和供应函数分别为)(k k x f y =和)2(11-++=k k k y y g x . 设曲线f 和g 相交于点),(000y x P ，在点0P 附近可以用直线来近似表示曲线f 和g ：0,)(00 ααx x y y k k --=- ----------------------（1）0,)2(0101 ββy y y x x k k k -+=--+ --------------------（2） 从上述两式中消去k y 可得,2,1,)1(22012=+=++++k x x x x k k k αβαβαβ， -----------（3） 上述（3）式是我们所建立的差分方程模型，且为二阶常系数线性非齐次差分方程. 为了寻求0P 点稳定平衡条件，我们考虑（3）对应的齐次差分方程的特征方程：022=++αβαβλλ容易算出其特征根为48)(22,1αβαβαβλ-±-=---------------（4） 当αβ 8时，显然有448)(22αβαβαβαβλ----= -----------（5） 从而2λ 2，2λ在单位圆外．下面设8 αβ，由(5)式可以算出 22,1αβλ=要使特征根均在单位圆内，即2,1λ1 ，必须 2 αβ．故0P 点稳定平衡条件为 2 αβ．3． 已知某商品在k 时段的数量和价格分别为k x 和k y ，其中1个时段相当于商品的一个生产周期.设该商品的需求函数和供应函数分别为)2(11k k k x x f y +=++和)(1k k y g x =+.试建立关于商品数量的差分方程模型，并讨论稳定平衡条件.解：已知商品的需求函数和供应函数分别为)2(11k k k x x f y +=++和)(1k k y g x =+. 设曲线f 和g 相交于点),(000y x P ，在点0P 附近可以用直线来近似表示曲线f 和g ：0,)2(0101 ααx x x y y k k k -+-=-++ --------------------（1） 0,)(001 ββy y x x k k -=-+ --- ----------------（2）由（2）得 )(0102y y x x k k -=-++β --------------------（3）（1）代入（3），可得)2(0102x x x x x k k k -+-=-++αβ ∴ ,2,1,2220012=+=++++k x x x x x k k k αβαβαβ， --------------（4）上述（4）式是我们所建立的差分方程模型，且为二阶常系数线性非齐次差分方程.为了寻求0P 点稳定平衡条件，我们考虑（4）对应的齐次差分方程的特征方程：022=++αβαβλλ容易算出其特征根为 48)(22,1αβαβαβλ-±-= ---------------（4） 当αβ≥8时，显然有448)(22αβαβαβαβλ-≤---= -----------（5） 从而2λ 2，2λ在单位圆外．下面设8 αβ，由(5)式可以算出 22,1αβλ=要使特征根均在单位圆内，即 2,1λ1 ，必须 2 αβ．故0P 点稳定平衡条件为 2 αβ．。
目录目录 (1)乘公交，看奥运 (2)一问题的重述 (3)二符号说明 (3)三模型假设 (4)3.1基本假设 (4)3.2 其它假设 (4)四问题的分析 (5)五建模前的准备 (5)5．1数据的存储 (5)5．2搜寻经过每个站点的公交路线 (6)5．3统计任意两条公交线路的相交（相近）站点 (6)六模型的建立与求解 (7)6．1模型一的建立 (7)6．1．1 公汽路线的数学表示 (7)6．1．2最优路线模型的建立 (8)6．1．3模型的算法描述 (8)6. 1. 4模型一的求解 (9)6.2 模型二 (11)6．2．1模型二的建立 (11)6．2．2模型二的求解 (12)6. 3 模型三 (14)七模型的优缺点及改进 (15)7.1模型的评价 (15)7.1.1 模型优点 (15)7.1.2 模型缺点 (15)7.2 模型的改进 (16)八参考文献 (18)[1] 344000温小文臧德彦，城市公交信息查询系统设计初探，江西测绘，第65期，2006 (18)九附件 (18)十附录 (20)10.1画地铁位置关系的程序 (20)10.2问题一的相关源程序 (21)10.2．1（文件名：CalculateStandars.h） (21)10.2.2（文件名：CalulateWays.h） (29)10.2.3 (文件名：LoadMessage.h) (35)10.2.4(文件名：ShortPathCalculate.cpp) (36)10.3问题二的相关程序 (40)10.3.1（文件名：CalculateStandars.h） (40)10.3.2(文件名：CalulateWays.h) (45)10.3.3(文件名：DataPreProcess.h) (53)10.3.3(文件名：ShortPathCalculate.cpp) (57)乘公交，看奥运【摘要】本文要解决的问题是以即将举行的08年北京奥运会为背景而提出的。
