美赛常用模型二.ppt

《美赛常用模型二.ppt》由会员分享，可在线阅读，更多相关《美赛常用模型二.ppt（61页珍藏版）》请在三一文库上搜索。

1、美赛常用模型（二）,数学中国网站站长：马壮,,本讲的主要内容,调度模型 物理模型 评价模型 决策模型 概率模型,,【问题提出】 某办公楼有11层高，办公室分别安排在7，8，9，10，11层上假设办公人员都乘电梯上楼，每层有60人办公现有三部电梯A，B，C可供使用，每层楼之间电梯的运行时间为3秒，最底层(1层)的停留时间为20秒，其他各层若停留，则停留时间为10秒每台电梯的最大容量是10人，在上班前电梯只在7，8，9，10，11层停留请问：怎样调度电梯能使得办公人员到达相应楼层所需总的时间最少？试给出一种具体实用的电梯运行方案,例1 电梯调度问题,,【模型假设】 （1）办公人员都乘电梯上楼； （

2、2）早晨8：00以前办公人员已陆续到达一层； （3）保证每部电梯在底层等待时间内(20秒)都能达到电梯的最大容量； （4）电梯在各层相应的停留时间内，办公人员能够完成出入电梯的动作； （5）当无人使用电梯时，电梯在底层待命,,【模型建立】 （1）电梯运行配置方案一 容易想到的一个运行方案是，将56=300名办公人员平均分配给三部电梯运送，每部电梯运送100人，每趟运送10人，需运送10趟每趟运行因有往返，故电梯待命及人员出人时间为20+510=70 秒，在途中运行时间为610=60 秒，总计一趟运行耗时130秒由于三部电梯彼此独立运行，因此，若它们同时开始运行，将300人运送完总耗时应为101

3、30=1300 秒，约21.7分钟,,【模型建立】 （2）对电梯运行方案一的改进 为了改进电梯的运行方案，首先推导一部电梯运行一趟耗时的计算公式 假设该电梯在第一层楼以外停留的次数是N，最高到达的层数是F，则其一趟运行耗时为 T=20+6（F-1）+10N(秒) (1) 其中7F11,1N5. 从公式(1)可以看到，要使电梯运行的时间T变小，关键是减少N（即减少中途无谓的开门次数）,,【模型建立】 （2）对电梯运行方案一的改进 由此想到一种最极端的电梯运行方案，即每部电梯每次运行只去某一特定的楼层，以保证中途仅开门一次 为了电梯运行时间均匀起见，三部电梯各去每层楼两趟，依照这种运行方案，每部电

4、梯赴7，8，9，10，11层楼分别用时66，72，78，84，90秒 总计用时为： 2(66+72+78+84+90)=780（秒）=13 （分钟） 这也许是最省时间的运行方案了,,【模型建立】 （2）对电梯运行方案一的改进 下面的两种方案(见表一，表二)，你觉得哪一种更好些? 表一 电梯运行配置方案二,,【模型建立】 表二 电梯运行配置方案三,,通过对比可以看出，表一简单明了、便于操作，但是它使高层的办公人员等待时间较长，同时由于它是从低层到高层运人，容易发生电梯等人（因为目标楼层的人员可能未到齐）的现象，或者使较低楼层的人员由于稍来迟一点而没有电梯可乘表二对这方面的考虑要好一些，它使各层人

5、员的平均等待时间大体相当，并且目标分布比较均匀，但控制起来不太方便,【模型建立】 （3）从统计角度出发设计电梯运行配置方案 通过一段时间的观察统计，发现这300人不都是按时上班的。比如，大约有73的工作人员是8:00以前到达第一层电梯的，那么只有220人需要在8:00以后用电梯送走。 这样，即使按照第一种方案，每部电梯的运行次数也不超过8趟，可使运行时间减少到8130=104（秒）， 约为17.3分钟,,【模型建立】 （4）从随机角度出发设计电梯运行配置方案 此方案借助概率知识，不对电梯的运行加以任何人为的限制假设每部电梯都能随机地“选择”10位乘客，为此，考虑几种理想的情况： 电梯上的10人

6、都工作在某一楼层，如第11层，这种情况发生的概率为：,,而这样的情况共有5种，总计概率也不会超过0.005,【模型建立】 （4）从随机角度出发设计电梯运行配置方案 电梯上的10人都工作在某两个楼层，如7，8层，这种情况发生的概率为：,,这样的情况共有 种，总计概率也不会超过0.05,【模型建立】 （4）从随机角度出发设计电梯运行配置方案 电梯上的10人都工作在某3个楼层，如7，8，9层，这种情况发生的概率为：,,这样的情况也有10种，总计概率约为0.05,【模型建立】 （4）从随机角度出发设计电梯运行配置方案 电梯上的10人都工作在某4个楼层，如7，8，9，10层，这种情况发生的概率为：,,同

7、理，电梯上的10人中无一人工作在10层（9，8，7层）的概率均约为0.1类似的情况共有5种,【模型建立】 （4）从随机角度出发设计电梯运行配置方案 情况至是在电梯一天的运行中几乎不可能发生的小概率事件，在方案中可不予考虑而情况意味着10趟运行中可能有一次发生，这样即使按方案一配置，每部电梯至少也可以节约10秒（若是11层，可节约16秒）最有可能的一种情况是，每部电梯的10次运行中有5次是每层都停的，有5次是至少停一层的这种情况下算出的一部电梯的运行时间是： T=5130+1114（不停11层）+4120=1244（秒） =20.7（分钟） 比方案一节省约1分钟,,,如果把几种思考方案结合起来，

8、还可以找到更多的电梯运行方案另外，对方案一的改进也可考虑三部电梯每趟运行的时间不一致的情形还可以对原始问题作各种改进，使之“衍生”出更多问题，例如，增、减办公楼的层数，改变电梯的数量和电梯运行的参数（如运行速度）等更切合实际的考虑是事先模拟人员到来的频率，用排队模型来求解。,2 量纲分析与无量纲化,物理量的量纲,长度 l 的量纲记 L=l,质量 m的量纲记 M=m,时间 t 的量纲记 T=t,动力学中基本量纲 L, M, T,速度 v 的量纲 v=LT-1,导出量纲,加速度 a 的量纲 a=LT-2,力 f 的量纲 f=LMT-2,引力常数 k 的量纲 k,对无量纲量，=1(=L0M0T0),

9、量纲齐次原则,=fl2m-2=L3M-1T-2,,量纲齐次原则,等式两端的量纲一致,量纲分析利用量纲齐次原则寻求物理量之间的关系,例：单摆运动,求摆动周期 t 的表达式,设物理量 t, m, l, g 之间有关系式,1, 2, 3 为待定系数，为无量纲量,(1)的量纲表达式,对比,,对 x,y,z的两组测量值x1,y1,z1 和x2,y2,z2， p1 = f( x1,y1,z1), p2 = f( x2, y2,z2 ),为什么假设这种形式,设p= f(x,y,z),x,y,z的量纲单位缩小a,b,c倍,,单摆运动中 t, m, l, g 的一般表达式,,设 f(q1, q2, , qm)

10、= 0,ys = (ys1, ys2, ,ysm)T , s = 1,2, m-r,F( 1, 2, m-r ) = 0 与 f (q1, q2, , qm) =0 等价, F未定,Pi定理 (Buckingham),是与量纲单位无关的物理定律，X1,X2, , Xn 是基本量纲, nm, q1, q2, , qm 的量纲可表为,量纲矩阵记作,,g = LT-2, l = L, = L-3M, v = LT-1, s = L2, f = LMT-2,量纲分析示例：波浪对航船的阻力,航船阻力 f,航船速度v, 船体尺寸l, 浸没面积 s, 海水密度, 重力加速度g。,m=6, n=3,,Ay=0

11、 有m-r=3个基本解,rank A = 3,rank A = r,Ay=0 有m-r个基本解,ys = (ys1, ys2, ,ysm)T s = 1,2, m-r,,F(1, 2 ,3 ) = 0与 (g,l,v,s,f) = 0 等价,为得到阻力 f 的显式表达式,F=0, 未定,F( 1, 2, m-r ) = 0 与 f (q1, q2, , qm) =0 等价,,量纲分析法的评注,物理量的选取,基本量纲的选取,基本解的构造,结果的局限性, () = 0中包括哪些物理量是至关重要的,基本量纲个数n; 选哪些基本量纲,有目的地构造 Ay=0 的基本解,方法的普适性,函数F和无量纲量未定

12、,不需要特定的专业知识,,量纲分析在物理模拟中的应用,例: 航船阻力的物理模拟,通过航船模型确定原型船所受阻力,模型船的参数(均已知),可得原型船所受阻力,已知模型船所受阻力,原型船的参数 (f1未知，其他已知),注意：二者的相同,,按一定尺寸比例造模型船，量测 f，可算出 f1 物理模拟,,5 无量纲化,例：火箭发射,星球表面竖直发射。初速v, 星球半径r, 表面重力加速度g,研究火箭高度 x 随时间 t 的变化规律,t=0 时 x=0, 火箭质量m1, 星球质量m2,牛顿第二定律，万有引力定律,3个独立参数,,用无量纲化方法减少独立参数个数,用参数r,v,g的组合,分别构造与x,t具有相同

13、量纲的xc, tc （特征尺度）,无量纲变量,如,令,,xc, tc的不同构造,1）令,为无量纲量,,3）令,2）令,,1）2）3）的共同点,重要差别,考察无量纲量,在1）2）3）中能否忽略以为因子的项？,1),无解,,2),3),,原问题,是原问题的近似解,,为什么3)能忽略项，得到原问题近似解，而1) 2)不能?,3）令,火箭到达最高点时间为v/g, 高度为v2/2g,大体上具有单位尺度,林家翘：自然科学中确定性问题的应用数学,,例3 天气预报的评价,明天是否下雨的天气预报以有雨概率形式给出.,问题,已得到某地一个月4种预报方法的有雨概率预报，和实际上有雨或无雨的观测结果.,怎样根据这些数

14、据对4种预报方法给以评价,计数模型,根据明天是否有雨的实测，统计预报的正确率,有雨概率=50% 毫无意义, 不予统计,正确率 0.57,正确率 0.71,正确率 0.81,正确率 0.93,计数模型,从实用角度看，更重要的是误报率.,预报无雨而实测有雨的概率P2,预报有雨而实测无雨的概率P1,设两种后果的损失之比为1 : 2,P1=10/16,P2=3/14,误报率P=P1/3+2P2/3=0.35,误报率P=0.20,误报率P=0.06,缺点: 未考虑预报概率的具体值,记分模型,将预报有雨概率与实测结果比较并记分,模型1,pk第k天预报有雨概率,vk=1第k天有雨， vk=0无雨,第k天的预

15、报得分,对k 求和得到预报的分数S1,S1 (A) =1.0， S1 (B) = 2.6， S1 (C) = 7.0， S1 (D) = 6.7,实测有雨,S1越大越好,记分模型,模型2,pk第k天预报有雨概率,vk=1第k天有雨， vk=0无雨,第k天的预报得分,对k 求和得到预报的分数S2,S2越小越好,S2 (A) =14.5，S2 (B) = 12.9， S2 (C) = 8.5， S2 (D) = 8.8,模型3,第k天的预报得分,对k 求和得到预报的分数S3,S3越小越好,S3 (A) =8.95，S3 (B) = 6.39， S3 (C) =4.23， S3 (D) =3.21,

16、记分模型,S2 (A) =14.5，S2 (B) = 12.9， S2 (C) = 8.5， S2 (D) = 8.8,S3 (A) =8.95，S3 (B) = 6.39， S3 (C) =4.23， S3 (D) =3.21,S1 (A) =1.0， S1 (B) = 2.6， S1 (C) = 7.0， S1 (D) = 6.7,模型1, 2对4种预报的优劣排序、相对分差都相同,f理论上的有雨概率,模型3的期望分数,p预报有雨概率,v=1有雨， v=0无雨,P(v=1)= f, P(v=0)= 1- f,比较模型3与模型2的优劣,p=f 时E(S)最小,考察一般模型,求E(S)的极值,此

17、意义下模型3最佳！,图形模型,*号几乎随机分布, 预报效果很差,模型1,*号的p没有变化, 毫无用途,v=0*号在p=0.6左边,无雨预报较好; v=1 *号分散 ,有雨预报较差,v=0 *号在p=0.5左边,v=1 *号在p=0.4右边,无雨、有雨预报都好,*上( )中数字是坐标在*的天数,图形模型,模型2,p 预报有雨概率, q实测有雨天数比例,p和q越接近越好,*离对角线越近越好,*几乎均匀分布,明显不好,只有一个*, 几乎在q=p上,比A好一些,未显示出优势,模型缺陷,不能用于预报B的情况,数据量小可能是预报D未得到正确评价的原因,用*与q=p的竖直距离度量模型的优劣, 并考虑各个*的

18、权重，模型2可量化为分数模型 .,深入讨论,评价预报的优劣，需制定评价标准,没有统一看法, 提出三类层次、内涵不但相互关联的标准,第一类标准：预报者本身的一致性,指预报者根据知识、信息和经验对预报的事件做出的判断，与他对外发布的预报之间的关系.,不完全一致,预报者没有利用全部判断，只从使用者的需要出发.,出于预报效益等考虑，对判断作了适当改变.,一致性受预报者控制，外界通常难以掌握,在预报以概率形式给出的情况下，当预报与预报者的判断一致时，才会得到与实际观测最相符的结果.,深入讨论,第二类标准: 根据预报和实测间的关系,评价预报的品质,利用预报(随机变量x)与观测(随机变量y)的联合分布F(x

19、, y),可靠性,决定性,将特定预报x下观测y的条件均值与x之差对所有x平均,作为可靠性的数量指标.,由条件分布F(yx) 和边际分布F(x) 计算得到,将特定预报x下观测y的条件均值与y的无条件均值之差对所有x平均, 作为决定性的数量指标.,越小越好,越大越好,深入讨论,第二类标准: 根据预报和实测间的关系,评价预报的品质,分辨度,敏锐性,将特定观测y下预报x的条件均值与y之差对所有y平均,作为分辨度的数量指标.,越小越好,将这个条件均值与y的无条件均值之差对所有y平均, 作为分辨度的又一数量指标.,越大越好,预报本身的敏锐, 与事件无关. 由边际分布F(x)决定.,如预报有雨概率多数接近1

20、或0.,由条件分布F(xy) 和边际分布F(y) 计算得到,不确定性,实际事件发生的不确定，与预报无关.会给预报带来困难,深入讨论,第二类标准: 根据预报和实测间的关系,评价预报的品质,由边际分布F(y)决定,计数、记分、图形模型都从某一侧面反映第二类标准.,第三类标准：利用预报所实现的效益或带来的费用,用决策分析法估计预报的效益或费用的期望值，与不用预报(做先验估计)相比.,与预报的品质，即第二类标准密切相关.,在谷物种植、耕种计划、水果保护等领域有广泛应用.,为了选修课程门数最少，应学习哪些课程 ？,例4 选课策略,要求至少选两门数学课、三门运筹学课和两门计算机课,选修课程最少，且学分尽量

21、多，应学习哪些课程 ？,0-1规划模型,决策变量,目标函数,xi=1 选修课号i 的课程（xi=0 不选）,选修课程总数最少,约束条件,最少2门数学课，3门运筹学课， 2门计算机课.,先修课程要求,最优解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它为0；6门课程，总学分21.,0-1规划模型,约束条件,x3=1必有x1 = x2 =1,模型求解（LINGO）,学分最多,多目标优化的处理方法：化成单目标优化。,两目标(多目标)规划,讨论：选修课程最少，学分尽量多，应学习哪些课程？,课程最少,以学分最多为目标,不管课程多少.,以课程最少为目标,不管学分多少.,多目标规划

22、,对学分数和课程数加权形成一个目标，如三七开.,最优解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x9 =1， 其它为0；总学分28.,多目标规划,在课程最少的前提下以学分最多为目标.,最优解： x1 = x2 = x3 = x5 = x7 = x9 =1, 其它为0；总学分由21增至22.,注意：最优解不唯一！,LINGO不能告诉优化问题的解是否唯一.,可将x9 =1 易为x6 =1,讨论与思考,最优解与1=0，2=1的结果相同学分最多.,多目标规划,最优解与1=1，2=0的结果相同课程最少.,选 课 策 略,用0-1变量表示策略选择是常用的方法,“要选甲 (x

23、1)必选乙 (x2)” 可用x1 x2描述.,“要选甲 (x1)必不选乙 (x2)” 怎样描述?,“甲乙二人至多选一人” 怎样描述?,“甲乙二人至少选一人” 怎样描述?,双(多)目标规划的处理方法,加权组合成一个新目标, 化为单目标规划.,一个目标作为约束, 解另一个目标的规划.,例五 报童的诀窍,问题,报童售报： a (零售价) b(购进价) c(退回价),售出一份赚 a-b；退回一份赔 b-c,每天购进多少份可使收入最大？,分析,购进太多卖不完退回赔钱,购进太少不够销售赚钱少,应根据需求确定购进量.,每天需求量是随机的,优化问题的目标函数应是长期的日平均收入,等于每天收入的期望,建模,设每天购进 n 份，日平均收入为 G(n),调查需求量的随机规律每天需求量为 r 的概率 f(r), r=0,1,2,准备,求 n 使 G(n) 最大,已知售出一份赚 a-b；退回一份赔 b-c,求解,将r视为连续变量,结果解释,取n使,a-b 售出一份赚的钱 b-c 退回一份赔的钱,联系方式,网址：(数学中国) QQ：75822904 电话：13948315451 邮箱：,谢谢大家,,