模型与算法(思考题4道)

模型与算法（思考题共4题）思考题1大小包装问题题目：在超市购物时你注意到大包装商品比小包装商品便宜这种现象吗？比如洁银牙膏50g装的每支1.50元，120g装的每支3.00元，二者单位重量的价格比是1.2:1，试用比例方法构造模型解释这种现象。（1）分析商品价格C与商品重量w的关系。（2）给出单位重量价格c与w的关系，并解释其实际意义。Tips：决定商品价格的主要因素：生产成本、包装成本、其他成本。23Cww；13cww；4321'3cww；7334''29cww解：（1）问题分析：商品价格C随着商品重量w的增加而增加，由题可得二者并不是简单的线性关系。商品的价格C=成本D+利润P（其中，成本D包括生产成本sC、包装成本bC、其他成本qC）。为得到商品价格C与商品重量w的关系，需要细化组成价格的成本及利润与商品重量的关系。（2）模型假设：1）包装的重量对商品来说可以忽略不计，即包装重量为零。2）生产单位重量的商品投入的劳动力无差别，即单位重量的商品生产成本相同。3）不同重量大小的包装的材料（厚度质量）无差别，即包装成本只与使用材料的多少相关。4）不同重量的商品形状一致，即23Sw5）每件商品都有固定的其他成本为qC。6）商品的利润与商品的重量呈线性相关关系。（3）模型建立：根据模型假设得：1）生产成本1sCaw2）包装成本23223bCaSaaw3）利润4Paw4）商品价格sbqCPCCC234123qawawaawC23ww其中：1a、2a、3a、4a——单位重量生产成本、单位面积包装成本、23:Sw的比值、单位重量的利润S、w——商品包装面积、商品重量41()aa、23aa、qC且1a、2a、3a、4a、S、w、、、0（4）模型求解与检验分析：1）经模型建立，得商品价格C与重量w的关系表达如下：23sbqCPCCCww不是简单的线性关系，随着商品重量的增加商品价格也随之增加，但并非成比例增加。2）单位重量价格c与商品重量w的关系为：2133Cwwc由4321'03cww，7334''209cww即单位重量价格c随之商品重量w的提高而减小，减小速度随商品重量的增加而变缓慢。可得，当商品重量较轻时，商品包装成本及其他成本对价格影响力大，当商品重量比较重时，包装成本及其他成本的影响力越来越小。当商品重量趋近于无穷时，单位重量价格趋近于（单位生产成本+单位重量利润），符合实际情况。思考题2划艇比赛的成绩题目：赛艇是一种靠浆手划桨前进的小船，分单人艇、双人艇、四人艇、八人艇四种。各种艇虽大小不同，但形状相似。T.A.McMahon比较了各种赛艇1964—1970年四次2000m比赛的最好成绩(包括1964年和1968年两次奥运会和两次世界锦标赛)，见下表。建立数学模型解释比赛成绩与浆手数量之间的关系。表1比赛成绩与浆手数量之间的关系表艇种2000m成绩t(min)艇长l(m)艇宽b(m)l/bW0(kg)与n之比1234平均单人7.167.257.287.177.217.930.29327.016.3双人6.876.926.956.776.889.760.35627.413.6四人6.336.426.486.136.3211.750.57421.018.1八人5.875.925.825.735.8418.280.61030.014.7解：（1）问题分析：1）受力分析：前进方向动力F阻力f浮力f浮总重力G总赛艇前进时受到的阻力主要是艇浸没部分与水之间的摩擦力，桨手提供动力克服阻力保持一定的速度前进。2）阻力影响分析：阻力的大小受到划艇速度、艇浸没部分与水的接触面积影响。人数越多，速度越快，单位阻力越大。又由于浮力f浮等于艇排水的质量，即赛艇和桨手总质量的增加会使艇浸没面积加大，从而增大阻力。因而水中阻力大小与赛艇的形状关系密切。表1第7至10列可得桨手数n增加时，艇的尺寸l，b及赛艇重0都随之增加，但比值l/b和0/n变化不大。由题得赛艇大小不同但形状相似，因而假定l/b是常数，则可得到艇浸没面积与排水体积之间的关系。3）建模目的：建立数学模型解释比赛成绩与浆手数量之间的关系。由于赛艇加速是一个加速度减小的变加速运动，其过程较为复杂。注意到在实际比赛中桨手在极短的时间内使艇加速到最大速度，然后把这个速度保持到终点。因而可合理假设艇速在整个赛程中保持不变，使问题简化为建立桨手数量与艇速之间的关系。此外还需对桨手体重、划桨功率、阻力与艇速的关系等方面做出简化且合理的假设，才能运用合适的物理定律建立需要的模型。（2）模型假设：1）各种艇的几何形状相同，1/lbC；艇重与桨手数呈线性关系，02/nC。2）桨手的体重相同，为；在比赛中每个桨手的划桨功率p保持不变，且p与成正比。3）赛艇前进时受的阻力f只与赛艇浸没面积S以及划艇速度v相关。其中单位面积阻力f与v2成正比。4）赛艇可看作长方体，浸没面积为+2=+2SSlbhlblbh深深底（）（），排水质量等于浮力为=fShglbhg深深浮底水水。5）在赛艇前行过程中，赛艇及浆手作为整体，只受到动力F、阻力f、浮力f浮、总重力G总四个力。（3）模型建立：在赛艇匀速前进过程中，水平方向与竖直方向受力平衡可得以下方程式：1）水平方向受力平衡：动力功率Pnp动阻力功率31fPvfSvSav阻，其中21fav为单位面积阻力与速度平方的比值。浸没面积+2Slblbh深（）PP阻动3311(+2)npSavalblbhv深（）（式1.1）2）竖直方向受力平衡总重力0(+)Gng总浮力为=fShglbhg深深浮底水水Gf浮总0(+)=nglbhg深水，又02/nC化简得02+(+)=nnChlblb深水水（式1.2）3）将式1.2带入式1.1得：321()(+2)npvnCalblblb水（）由1/lbC，30b，02/nC，得33/bnC。23123111331313233121113313  2(1)()[()+]()2(1)()[+]  npvnCCaCCnCCnnpCCaCCCC水水令213312141133132(1)(){[+]}CCCpaCCCC水，得194vnC，则19vn4）由上述推倒，得赛艇时间19tn艇种（人数n）2000m成绩t(min)m=n^(-1/9)t/m单人7.2117.21双人6.880.937.43四人6.320.867.37八人5.840.797.36（4）模型求解与检验分析：1）根据（3）模型建立中的推导，设：19tn，图1赛艇成绩t与n^(-1/9)关系图根据excel中利用最小二乘法得到的线性关系，得7.335，即197.335tn，相关系数²0.9774R拟合效果较好。2）结果检验与分析艇种m=n^(-1/9)t'(min)=αn^(-1/9)实际成绩t(min)绝对误差相对误差单人1.007.347.210.131.73%双人0.936.796.88-0.09-1.29%四人0.866.296.32-0.03-0.51%八人0.795.825.84-0.02-0.31%这个模型建立在一些不太精细的假设的基础上，因为我们只关心各种赛艇成绩与浆手人数的关系，所以数学工具只用到比例方法。用这种方法建模虽然不能得到关于艇速的完整的表达式，但是对于我们的建模目的来说已经足够了。结果与实际数据吻合较好，有数据量过少的成分在里面。思考题3旅行商问题的数学模型y=7.3347xR²=0.9774012345678900.20.40.60.811.2题目：旅行商问题，即TSP问题（TravelingSalesmanProblem）是数学领域中著名问题之一。假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。解：（1）问题分析：对于n个城市，如果城市两两之间可以直接联系，那么就可以有n！种排列组合。若固定起点城市，同时认为路网是对称的，则有(1)!2n种可能性。TSP问题是一个NPC问题。传统方法可以采用：枚举法（适合小规模，搜索时间长，可以得到最优解）；贪婪算法（得到较优解，搜索时间较短）；动态规划法（适用规模较大，比枚举法好，可以得最优解）等等。随机分布的TSP城市，假定采用欧式距离度量，则关于最短的TSP路径的期望长度*L的一个经典公式：*LknR其中n为城市数目，R是一个正方形面积，随机放置的各城市均位于该正方形之内，k为一个经验常数，成为Held-Karp下界。对于100n，k与n的期望比例关系为：0.708050.522291.315723.07474()knnnn相关文献建议采用k=0.749（2）模型假设：1）城市之间的距离为平面物理距离，即可用公式22(xx)()ijijyy计算。2）运费与运距成线性关系，不同路段的单位运费一致。（3）模型建立：目标：路径的选择目标是要求得的路径路程为所有路径之中的最小值：11min(x)nnijijijijFcdX约束：路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市：每个点只能出发一次：1      1nijjXiV（式1.1）每个点只能到达一次：11      nijiVXj（式1.2）各城市子集的路段选择不构成回路(如下图，满足式1.1&式1.2但不满足题目要求)：1234567,1,21,1,2,ijijsXSSnS…,n（式1.3）   ,?  ,0,11,2,iXijjnij、…,（式1.4）其中：ijc——OD点i到j路段，单位里程的费用；ijd——OD点i到j路段的里程ijX——OD点i到j路段是否被选择，若选择为1，若不选为0。S——城市点的子集。思考题4排课问题的数学描述问题描述及分析：排课涉及到资源合理分配、多任务交叉安排、冲突协调及组合优化等同题。排课流程：确定学生的培养方案（各年级每学期的课程）确定老师的授课任务（教学任务分配）上课时间地点安排最终排课结果以北京交通大学为例，学院在确定每个年级的教学任务后，课程安排中主要涉及以下问题：（1）问题主要因素：1）教学资源(即教师)：某教师能上哪些课程，所上每门课程的效果2）任务配置(即课程)：课程由哪些教师讲授，需要提供多少课容量供学生选课3）地点选择(即课室)：某课程在某课室的开课时间，容纳的人数（2）相关约束：1）时间的约束：①排课时间(如一周按五天，每天按四个时间段：上午2次、下午1次、晚间1次)。②同一教师不同课程的上课时间不能冲突③某一年级的必修课的上课时间不能冲突2）课容量的约束：①课程提供的总课容量大于等于需要选课的学生数量②一门课程的课容量小于分配到的课室的容纳人数3）排课数量的约束排课次数不能多于容许安排的时间次数（3）排课效果评价：1）每个教师开课数目相对平均2）时间安排与上课效果的关系3）课室的合理利用课表编排规则：每周以5天为单位进行编排；每天最多只能编排6节课，上午2节，下午2节，晚上2节。模型假设（1）假设学院四个年级共开课程b门，编号为Cb，每个课程需要的课容量为Cba；教师共有m名，编号为Tm；教室间n，编号为Rn，课室容量为Rna。（2）一周的课程时间按先后进行编号，编号为t，如第一周第一节课为1，第二节课为2。（3）编号Cb的课程，前q门课程为必修课，后b-q门为选修课。（4）在确定课室安排前，学院已经规划好教师的教课任务。（5）假设学校在安排课程数量的时候会充分考虑到课室资源，能够将课程全部排好。（6）1bbcbai开