复旦大学 数学模型 张云新.doc

期末考试复习张云新1. 抽屉原理or容斥原理：a) 容斥原理：i. 核心：从入手考虑问题ii. 基本定理：中能被整除的个数：iii. 例1：（欧拉函数）：且与互质的正整数的个数，其中解：将作质因数分解：令全集，则，再用iii，ii，i即可求解结论：iv. 例2：做全排列，不出现与的排列种数注意捆绑法：出现的种数为，的种数为，同时出现的种数为 v. 例3：求不超过120的素数的个数不超过120的合数必是2、3、5、7的倍数 ，而11以内的素数只有2、3、5、7令全集，则用iii，ii，i即可求注意 1）虽然2、3、5、7本身是其倍数，但是素数2）虽然1不是2、3、5、7的倍数，但既不是素数也不是合数综上，结果为+4-1vi. 例4：（错排数）：对个元素重新排列，所有元素都不在原来的位置上的个数记为数在第个位置上的全体排列的集合，则结果：1）2）理解：情况一：第一位排，第二位不排1，则可将第二位看作新的第一位，对作 错排情况二：第一位排，第二位排1，对剩下的做的错排（当然，也可以考虑第一位排，第位排不排1的情况，故乘以）应用： 1）19中所有偶数都在原来位置上，而奇数不在的错排数： 2）19中所有奇数都在原来位置上，而偶数不在的错排数：3）19中所有奇数都不在原位置的错排数：注意，若用做，应小心分类讨论：奇数和所有偶数都不在原位置+奇数和1个偶数不在原位置+奇数和2个偶数不在原位置+奇数和3个偶数不在原位置+偶数固定，奇数不在原位置=（4）也是同样的） 4）19中所有偶数都不在原位置的错排数：vii. 例5：的排列中没有的形式的个数应用：8名学生排成一排跑步，后一天与前一天相比，没有一个学生的前面的人与前一天相同，排法有几种：b) 抽屉原理：i. 核心：造个抽屉和个/组元素，这样必有2个以上元素放在同一抽屉里ii. 构造方法：分割图形成目标数据： 1）在边长为1的正方形内任意放置五个点，则其中必有两个点距离 证：将正方形等分成4个正方形2）在边长为1的正方形中，任意放入9个点，则在以这些点为顶点的三角形中，必有一个面积不超过证：将正方形等分成4个长方形根据认识与不认识划分：1）位代表参加会议，每位至少认识其他一位，则至少两位认识人一样多 证：个抽屉，每个抽屉里代表认识人数相同2）6个人中必有3个人互相认识或互相不认识 证：选定一个人，则与他认识的和与他不认识的人中必有一组有3个从头开始求和：（特点：若干连续问题）1）个整数中必存在连续若干连续个数之和能被整除 证：令，根据的同余类作抽屉2）一个棋手下11个星期的棋，每天至少一盘，每周不超过12盘， 则存在连续的若干天该棋手恰好下了21局棋 证：作，其中为第天下的盘数 根据条件估计的范围来构造抽屉奇数的技巧： 从中取个数，则其中至少有一对数，其中一个是另一个的倍数 证：任何一个数可以表示成其中是奇数，但中就个奇数找严格单调子列： 从个不同的数中一定可以找到个数称为严格单增/减的子列 证：令为以开始能找到的最长的严格单减/增的子列长度 只要讨论的情况，这样至少有个一样 则这个数构成一个严格单减的子列模的剩余类： 1）一定存在完全由构成数是其倍数 证：构造作模的剩余类 2）， 证：构造，注意到 将等分，则个必有两个在一个小区间中2. 交通路口的红绿灯问题：a) 假设：十字路口忽略黄灯、转弯一个周期取单位时间东西方向先开车流量稳定、均匀单位时间内从东西方向到达路口的车辆数为，单位时间内从南北方向到达路口的车辆数位，一个周期内，东西方向开红灯、南北方向开绿灯的时间为，一个周期内，东西方向开绿灯、南北方向开红灯的时间为停车后司机见到绿灯重新发动到开动的时间为确定（一个周期内东西方向红灯比率）：【即使总滞留时间最小】一辆车在路口的滞留时间通常包括两部分：一部分是遇红灯后的停车等待时间：即一个周期内平均被拦下的车辆*拦下车辆平均等灯时间东西方向，南北方向另一部分是重新启动的时间：即求的最小值结论：若忽略启动时间，则两个方向开绿灯时间之比应等于两个方向车流量之比b) 红绿灯管理下的十字路口，若绿灯亮15秒，问最多可有多少汽车通过此交叉路口？假设：十字路口不发生阻塞 所有车辆直行，不拐弯，且为单行道 所有车长均为定值米，且均从静止开始匀加速 红灯下等待的每相邻两辆车之间的距离相等，为米 前一辆车启动后，下一辆车启动的延迟时间相等，为秒用来表示第辆车在秒时的位置，记原点为交通灯的位置（）用来表示第辆车的启动时间，来表示第辆车的加速时间，为限速则3. 双层玻璃的隔热问题：a) 物理定律：单位时间由温度高的一侧向温度低的一侧通过单位面积的热量：其中为热传导系数，为两侧温差，为玻璃厚度b) 假设：室内温度，室外温度保持不变热量传播过程只有传导，没有对流，即两层玻璃之间的空气是不流动的玻璃材料均匀，热传导系数是常数，玻璃的为，空气为c) 单层玻璃：（厚度为）d) 双层玻璃：（每层厚度均为，中间夹的空气厚度为）记双层玻璃内层玻璃外层温度为，外层玻璃内层温度为求解过程注意先用一三式解的关系，再用一二式解与的关系e) 结论：，即双层玻璃隔热效果比单层玻璃好！代入做最保守估计，当后下降变缓（约为）4. 变分法：a) 最简泛函：被积函数包含b) 无约束条件的泛函极值，即求泛函的极值，此类问题中端点固定的情况，即满足边界条件且二次可微：核心公式：Euler方程c) 几种特殊情形：i. ：，一般不满足边界条件无解ii. ：，两边积分求出iii. ：（无论哪一项为0）iv.d) 例题：最速降线问题： 用c)/iv： 用参数法解这个常微分方程：令，这样就可直接积分用可以得到参数解： 常数由另一个边界条件确定最小旋转面问题：用c)/iv：用参数法解这个常微分方程：令，这样就可直接积分得到参数解：（注意：）5. 动态规划：a) 核心：用逆序法递归穷举，后一步的最优方案一定是前一步最优方案的一部分 （事实上，顺序法也是一样的）b) 例1（最短路线问题）：题型：求铺设一个线路网络使得总长度/费用最小解：设：从出发到目的地的最短距离，下标表示正在经过第个结点c) 例2（高低负荷有折损率生产）：解：设：第年初从台出发到最后一年结束产品产量的最大值不妨设总共年，则，注意：根据折损率有一个状态转移方程，与第年投入高负荷生产的台数有关的范围在内当终端固定，即结束时要求有一定量机器时，最后一年的生产分配事实上是由固定的d) 例3：已经4季度的交货量，每季度开工固定成本（不开工为0），单位产品生产成本，工厂每季度最大生产能力，每季度单位产品库存费用（按每季度初库存量计算），且年初年末无库存，求各季度产量如何分配使得全年费用最小？解：每阶段初库存量，有状态转移方程，且：每阶段生产量，从0规定的最大值：每阶段交货量：每阶段总费用，：第阶段从状态出发到第四季度末的总费用最小值，从最后一个季度开始对最后一个季度初的储存量分类讨论， 对每个季度列表，在中确定最优解 注意每年的除了定义域外，还有实际意义的限制，即：不会超过前个季度均满负荷生产扣除需求量后带来的库存，也不会超过以后所有季度生产要求的总和，同样要使下一个季度满足上面两条6. 指派问题（必考，最小/大值的优化）：a) 假设：每一个人做一项任务（人与任务个数相同）b) 定理：系数矩阵每一行、每一列减去相同的值不改变可行解矩阵c) 做法：Step1：每一行、每一列减去该行、列最小的元素，凑出尽可能多的零Step2：只有一个零的行/列画，并将相应列/行的其他零画Step3：如果的个数小于总人数（也即总任务数），则在没有的行打号， 对打号行中所有的所在的列打号， 对打号的列中含的行打号 重复、，直到打不出号为止 用直线划出没有打号的行和已经打号的列可以覆盖所有0Step4：在没有被直线覆盖的元素中取最小，对没有打号各行减去这个值，对已经打号各列加上这个值Step5：重复Step2d) 推广上面的做法求最小值，若求最大值，则用系数矩阵中最大元减去所有元素，构成新的系数矩阵，这样就转化为求最小值了当任务多人少时，可以复制一个人的数据当人多任务少时，可以加一个所有人都费时为0的任务当某个人不能去完成某项任务时，将其记为无穷大7. 网络模型（必考最短路or最大流）：a) Euler Thm：在连通多重图中能找到一条回路，过每边一次且仅一次图中无奇点b) 例：节目安排，每位演员需要参加两个以上节目，相邻两个节目不能有相同演员：解：将没有相同演员的节目连线，找到从头到尾的一笔画c) 最小树求法：i. 避圈法：任取一点打包，记为A，将剩余点也打包，记为B，找到权数最小的边，将这边相连的结点也打包入A，剔除出B重复此过程ii. 破圈法：任取一个圈，去掉权数最大边，直到无圈可去d) 最短路问题：i. 狄克斯屈标号法：适用于所有权数非负的网络！初始：始点标(0)，其余均为标与确定点相邻点的数字（取小），在最小的数字上打括号重复上述步骤直到最后一个点注：这里可能出现要标的与待定的数字相同的情况，此时两条路都要画箭头，表示均可以走例：设备更新问题ii. 距离矩阵摹乘法：距离矩阵其中表示从第点到第点的距离，且第点到第点的距离记为0；若不能直接到达或方向不对，则记为摹乘： ：中第个元素为中第行元素加上列元素取最小一个 或：中第个元素为行元素加上中第列元素取最小一个 或（与上面类似）求各点至某点的最短路：l 把各点到该点的距离写成列向量，作为初始的l 做摹乘，一直做到为止l 看最后中各个元素的由来，若有非的形式，则将对应中那一个元素画圈，若没有就对0画圈l 最短路即从出发，到画圈的点，再继续这样找下去直到目的点l 最短路的长度即列向量中的数值求某点至各点的最短路：l 把该点到各点的距离写成行向量，作为初始的l 做摹乘，一直做到为止【以后步骤与相同】求各点至各点的最短路：l 做摹乘，一直做到为止l 这样至多做次e) 网络的中心和重心：i. 中心：做法：其中表示从到的最短路程即：最终的距离矩阵中最后加一列，该列中的元素为每一行的最大，然后再求最后一列中最小的值对应的行指标例：商店建在哪里，使得到各村都较近ii. 重心：做法：，其中表示点的权重即：将距离矩阵中元素乘以相应的权数，在距离矩阵中最后加一行，该行中的元素为每一列的和，然后再求这行最小值对应的列指标例：各村小学生人数不同，小学应建在哪里f) 最大流问题：福特富尔克逊标号法：从零流或者随意一个可行流开始对始点标并打号，并找与始点相连的结点，若道路方向同向，则标上；若道路方向反向，则标上其中为该道路剩余流量注意：1）标过的点不再标注2）同向时不标注，返向时道路流量为0不标注若能标注到，且标注值为则在能标注到的路上对正向加上，反向减去，反复前三步，直到标注不到结束，最大流即与始点相连的线上的数值之和注：最大流的线路可根据上述步骤中每次标到的路来确定例：甲乙丙工作指定个数的零件，尽量平均解：将甲乙丙看成一组点、四种零件看成另一组点，找平均时能否达到最大流8. 决策问题：每一种方案都有相应的多种可能性a) 乐观法（最大最大决策准则）：取每种方案最好可能性的最大值b) 悲观法（最大最小决策准则）：取每种方案最坏可能性的最大值c) 折衷法（乐观系数法）：加权最好、最坏可能性（乐观系数）后再取最大值d) 平均法（等可能准则）：对每种方案所有情况取平均值，再取最大值推广：也可对每种情况加权平均e) 最小遗憾法（后悔值法）：找出每列中的最大值，再用这个值减去这一列其他值得到后悔损失阵，再取每行最大值的最大值f) 最大可能法则：只考虑概率最大的情况（当一组自然状态的概率比其他状态明显大时效果较好）g) 期望值方法（EMV）：按概率算每个方案的数学期望，再取最大值h) 最小机会损失决策准则（EOL）：对机会损失值（不仅仅是亏的情况）做期望，再取最小值例：日生产多少产品损失最小，列表求机会损失的期望i) 后验概率方法（贝叶斯决策）：适用于有自然概率，后验概率两个概率存在的时候全概率公式： （证明：为同时发生的概率，而对于任何一个，它必与某个同时发生）贝叶斯公式：（证明：若记为、同时发生的概率，表示发生的情况下发生的概率，则，同理：）例：某石油公司考虑钻井，出现无油、少油、富油的概率为0.5、0.3、0.2，钻井费用7万元。若少量出油，可收入12万元；若大量出油，可收入27万元；若不出油，收入为零。若勘探，费用为1万元，勘探结果为地质状况，与油井出油关系为下表，则应该如何根据勘探结果选择？且应该勘探与否？构造较差构造一般构造良好无油0.60.30.11.0少油0.30.40.31.0富油0.10.40.51.0首先求，为求，应求再对地质勘探的各种情况作数学期望，最后与不勘探挖、不勘探不挖作比较j) 决策树方法：决策点画，决策点对应的分叉上写决策方案，及方案代价确定决策后再决策点上写上最优结果方案点画，方案点后面按可能性分叉，方案点上方写此方案的结果（记得算上方案代价）取到所有方案的最大值后用/划去其他方案结果点画注：可对发生的自然概率作灵敏度分析9. 排队问题：a) 泊松流（单位时间发生几次）：i. 假设：在不相重叠的时间区间内顾客到达数是相互独立的（即：无后效性）对充分小的，在时间区间内有1个顾客到达的概率与无关，而约与区间长成正比，即其中表示单位时间有一个顾客到达的概率，称为概率强度对于充分小的，在时间区间内有2个或2个以上顾客到达的概率极小，以至于可以忽略ii. 泊松分布：，其中表示内有个顾客到达的概率，期望与方差相等b) 负指数分布（多少时间发生一次）：概率密度：分布函数：，上式对积分而来数学期望，方差，标准差c) 的意义：（表示单人平均服务时间）i. 服务机构的繁忙程度（繁忙时间比例）ii. 服务机构的利用率iii. ：平均到达率与平均服务率之比，即相同时区内顾客到达的平均数与被服务数的平均数之比iv. 为一个顾客的服务时间与到达间隔时间之比d) 标准的MM1模型：（单服务台、顾客无限、队长无限制）i. 图解：ii. 稳态方程：推导：一般情况有个人的情况为：有个人，不来不走有个人，来了又走有个人，走1个有个人，来1个但没有人的情况只有两种情况，要注意！考虑稳态：，这里要求（否则将排至无限远）iii. 利用归一化条件求解：iv. 系统中的平均顾客数：队列中等待的平均顾客数：在系统中顾客逗留时间的期望值：在队列中顾客等待时间的期望值：e) 系统的容量有限制：（单服务台、顾客无限、队长有限制）i. 图解：ii. 稳态方程：，只要求iii. 利用归一化条件求解：iv. 注意：在有6个椅子接待排队理发顾客时，系统最大容量为7（有正在理发的）顾客一到就可以理发的概率系统中的平均顾客数：队列中等待的平均顾客数：有效到达率：在系统中顾客逗留时间的期望值：在队列中顾客等待时间的期望值：在可能到来的顾客中不等待就离开的概率，即理发馆的损失率：10. 席位分配：a) 惯例分配法：先分整数个，再比较小数点，多出的席位小数点后较大的b) Q值法：（相对不公平度最小，认为公平即）建立在相对不公平度或上公式：，逐个席位分配（Q值大的优先），分配完后重新计算Q值 其中为当前已经分配的席位个数推导：设，则再分配一个席位会出现三种情况（第四种与假设矛盾） 分给比较两者，若，则说明把席位给的相对不公平度要小，满足要求 ，计算 ，计算 归纳的条件，得到公式c) dHondt方法：将人数用正整数相除，取商最大的N个数（对应势力得一席）d) 理想化原则：i. 原则一：，即必取二者之一（即取值在按比例的小数的上下取整之间）ii. 原则二：，即总席位增加时不减e) 比例加惯例满足原则一，但不满足原则二；Q值法满足原则二，但不满足原则一11. 森林管理：a) 假设：被售出的树木价值取决于树木的高度，有高度对应价格表vs要求砍一棵种一棵，所以森林中树木总数为固定值两次收获之间是森林的生长期，一个生长期内树木至多只能生长一个高度级同级树木的生长速度相同，为一年内第级树木进入第级的比例除砍伐外，树木不会死掉b) 建模：生长矩阵（即转移矩阵）：意义：即不砍伐时的状态转移：收获向量：，种植向量：收获模型：注意到稳态解即，为常数，这样得到一个方程组且幼苗经济价值为0，故不妨设又注意到，所以问题转化为的线性规划只收获第级的全部树木由定理：线性规划的可行解域是凸集 线性规划的最优解在可行解域的顶点上达到注意到稳态解意味着以后再也没有第级及以后的树木，代回方程组即可求解c) 结论：，其中为稳定时森林中树木总数12. 基因遗传：a) 随机交配：i. 设三种基因类型数量比例为记则表示父代提供的概率，表示父代提供的概率转移矩阵【行向量左乘】注意转移矩阵中元素的意义：如 、ii. 结论：（Hardy-Weinberg平稳定律）即使初始第一代不是从群体中随机选取，在随机交配方式下，经过足够长时间3种基因类型的分布也趋向于首次返回平均换代数目：b) 近亲繁殖：i. 需要先求父母基因型为时，子代基因型为的概率ii. 与随机交配类似的求出转移矩阵注意转移矩阵中元素的意义：如 、iii. 需要注意子代为时概率要乘以2！（因为可以是雄为，雌为，也可以是雄为，雌为）iv. 为吸收态，所以若干代以后全为13. 存储策略（卖钢琴no Poison分布、报纸）：a) 钢琴销售的存贮策略：i. 假设：钢琴需求量服从泊松分布，平均每周卖出一台，即存贮策略：每周周末库存为0时订购3架，否则不订购周初库存量记为ii. 转移矩阵：，表示从库存量为转向的概率iii. 稳定解即时的，即关于特征值1的一个特征向量！iv. 失去销售机会的概率为，这里要对用全概率公式：v. 第周的平均销售量，要注意需求量超过存量时只能售掉存量vi. 敏感性问题：换的值b) 卖报纸：i. 假设：零售价，进价，退回价，ii. 记：需求量为的概率iii. 期望进份报纸获得的钱： iv. 方一：连续化，注意上下限与被积函数中均有，要小心，尤其是下限要+“-”v. 方二：非连续化14. 二物种生态模型（单物种不考）：i. 相互竞争的二物种群体系统：1）假设：自然增长率为，在独自生存状态下上限为第二（一）物种生物个体消耗的资源相当于第一（二）种生物的倍，其中有关系式2）模型（增长率与环境限制、物种数量有关）：3）平衡点：对非线性自治常微分方程组，用Perron定理：考察对应的线性自治方程组：解的特征值，若均小于零则稳定（注：特征值可能不能直接解出，但可以看判别式结合韦达定理作出判断）4）结论： 在考虑两种生物个体消耗资源倍数的情况下，环境能维持哪个物种更多，另一个劣势物种就会趋于灭绝（即，则第二物种灭绝）ii. 二物种弱肉强食系统：1）假设：第一种生物除了受限模型外，第二种生物越多捕杀机会越多，繁殖越快，其系数为 第一种生物越多，第二种生物被捕杀的也越多，从而减少得越快，其系数为2）模型：（事实上考虑号，可与iii统一）iii. 掠肉鱼-小鱼系统模型：1）假设：无大鱼侵扰时小鱼自然增长率，