3.8 选址模型。
问题描述。设有m个村庄各有小学生人，现要合建一所小学校，使全部学生所走的总路程最短，问应如何选择校址？
建立模型。设ai的坐标为(xi,yi) ,i=1,2,3……m）校址在 a(x,y)处，那么全部学生所走的总路程为：
设ei为方向上的单位向量。
若令。则等价于。
s 的最小值只能在ai（i=1,2,3……m）（在这些点s不可导）和满足（3.8.1）的点去找。
可以证明：若点a(x,y)满足(3.8.1)，则在该点s达最小值。
三角形的费尔马点。
考虑选址问题中，的特例。
费尔马问题---要在所在平面上找一点a，使a到三顶点距离之和最小。
费尔马点---费尔马问题中的点a
费尔马距离---费尔马问题中的点a到三顶点距离之和，即。
显然a点不应在之外。
1）情形1，当的内角都小于120时，由上述（3.8.1）即得：
对(3.8.3)两边分别点乘， 得到下面方程组。
解得：，即。
此时， 费尔马点唯一存在。
2）情形2，当的最大内角≥120时，可设想：原来最大内角< 120 。则由（1）可知使s最小的a点在△内出现，保持与的长度不变。
让逐渐张大，则点a趋于点，如图3.8.4所示，当θ=120时，点a与点重合。
显然点a不可能在之外，从而即使θ继续扩大仍然点a与点重合。
性质：费尔马距离任两边边长之和，等号仅在费尔马点与的顶点重合时才会成立。
3）三角形费尔马点的几何作法。
若δabc的三个内角都小于120o，分别在δabc之外作等边δabe和等边δadc，则直线bd与ce的交点f就是δabc 的费尔马点，且bd与ce就是费尔马距离，即bd=ce=af+bf+cf.
4）费尔马点在工程上的应用例子。
例3.8.1 如图3.8.5,设a为电厂，b和c为村庄。如何从a铺设电缆到b和c使电缆总长度最短？（单位：km）
如果不添加节点，比较下面各方案。
方案1： ac+bc=8+7=15
方案2： ab+bc=6+7=13
方案3： ab+ac=6+8=14
总长度最短者为方案2，只需13km .
如果考虑添加节点，方案2就不是最优方案。最优方案是先找出△abc的费尔马点m(1.7,3.
7)，再象图3.8.6,把电缆铺成”y”字形：
am+mb+mc=12.04.这样，比起方案2节省了近1km的电缆。
例3.8.2有两个城市a、b要在河边（x轴） 合建一个自来水厂，向它们供水。试设计自来水厂的位置以及铺设水管的方法，使所铺设的水管总长度为最短。（单位：km）
若用”v”型法，则如图3.8.7, 先作点b关于x轴的对称点b’(6,-4),再作线段ab’交x轴于点w，以点w为自来水厂的位置，水管按 awb铺设成”v”型，其总长度为ab’=10.
3km.
如果考虑添加费尔马点，把水管铺成“y”型。 则效果更佳。见图3.
8.8. 设水厂的位置在点m 处，点a与b在x轴上的垂足分别是a’ 与b’,显然m应在a’ 与b’之间；设n(x,y)为δabm的费尔玛点，则必有mn⊥x轴，才可能使 an+bn+mn 达到最短， 从而，点m的坐标为m (x,0)，即点n与点m横坐标相同。
过点n作直线pq∥x轴，由费尔玛点性质可知，∠anm=∠bnm=120o,从而，∠anp=∠bnq=30o
列出方程：
化作线性方程组。
解方程组得：
由此得点m的坐标为m (4.3660,0)，点n的坐标为n (4.3660,3.0566), 铺设水管的方法当然是从点n分别引向点a、点b和点m，成“y”型。
第二方案的水管总长度8.83km比第一方案的水管总长度10.3km缩短了16.6% .这是科学方法给我们带来的效益。
注：此问题一般化得：
这里要求。5)费尔马点的坐标计算。
当知道δabc三顶点的坐标时，怎样求点d和点e的坐标？
由于δabe和δacd是等边三角形，故很自然会想到利用边长相等的关系来计算点d和点e的坐标，即ab=ae=be 和ac=ad=cd. 但是要注意：用两端点坐标来表达一线段的长度时，表达式含有根号会给解方程带来很大困难。
借助平面几何知识，如图2,设t是ab的中点，an与em平行于y轴，mt与bn平行于x轴。
下面用点的字母作坐标的下标，如。
可见，点e的坐标很容易通过点a与点b的坐标计算出来。 同理得。
然后求线段ce与bd的交点就得费尔马点f的坐标。 若分别用与表示线段ce与bd的斜率，即，则易求得。
一般地，a、b、c三点的位置未必与图2一致，从而影响结果的计算公式。 因此，还要对此进一步讨论。
我们不妨设，即把横坐标最小者称为点a, 最大者称为点c, 中间者称为点b.这样仍按上述推导方法，设的ab边外与点e构成等边三角形，ac边外与点d构成等边三角形，可得如下结论。
当点b在直线ac之上， 即时。
其他情况。不论哪种情况，费尔马点的坐标计算，仍用式(3).
6）实际案例：输油管的布置。
某油田计划在铁路线一侧建造两家炼油厂，同时在铁路线上增建一个车站，用来运送成品油。由于这种模式具有一定的普遍性，油田设计院希望建立管线建设费用最省的一般数学模型与方法。
两炼油厂的具体位置由附图所示，其中a厂位于郊区（图中的i区域），b厂位于城区（图中的ii区域），两个区域的分界线用图中的虚线表示。图中a = 5km，b = 8km，c = 15km，l = 20km。
若所有管线的铺设费用均为每千米7.2万元。 铺设在城区的管线还需增加拆迁和工程补偿等附加费用每千米21.4万元。 请为设计院给出管线布置的最优方案及相应的费用。
设点m是车站，点h是输油管在两个区域的分界点，点n是三角形ahm的费尔马点，三角形ahe是等边三角形，则点e的坐标。
而且，，则总费用。
s只是的一元函数。令，解得。
s的最小值万元。
斯坦纳（steiner）最短树问题。
在平面上给定了n个点，怎样用一些直线段把它们连接起来，使其总长最短？
通常，直接连不是最短，而应该添加一些特殊的点后再连。
例 n=3图论中的几个概念：
顶点v的度---与该顶点关联的边数，记为；
树---无圈（回路）的连通图；
steiner树---两相邻边的夹角都不小于120°的树；
steiner点（简称s点）--有三边相连，且任两相邻边的夹角都是120°（即情形1的费尔马点）
图论中的几个性质：
1）图的性质：全部顶点的度之和=2×边数；（）
2）树的性质：边数=顶点数-1；
3）steiner树的性质：任一顶点的度 ≤ 3。
steiner树的重要定理：
在有n个给定顶点的steiner树中，至多添加n-2个steiner点。
证明：设一steiner树有n个给定顶点和s个s点，再设表示n个给定顶点中，k度点的数目。由性质（3），再由性质（2），又，最后由性质（1），化简得， 从而，.
n=3时，即是费尔玛问题。
n=4时，至多添加2个s点。
1)不需添加s点的情形。
(2)需添加1个s点的情形。
3）需添加2个s点的情形。
步骤如下：1. 在ab的左边找1个点e,使δabe为等边三角形；
2. 找出δcde的s点s1;
3. 再找出δabs1的s点s2（也是δabf的s点，δcdf为等边三角形）;
4. 连接as2, bs2, s2s1, s1c, s1d得一steiner树，记为ta;
ef=ta总长。
5. 同理可能得另一steiner树tb;
mn=tb总长。
6. 比较ta与tb的总长，确定steiner最短树；
方法一】直接比较ef与mn
方法二】若s1s2>s3s4, 则ta的总长更简单的方法：
波拉克（henry o pollak）定理：
设a，b，c，d是四个给定点，且两斯坦纳树ta与tb都存在，则s点落在四边形abcd的两对角线的夹角为锐角的区域内的斯坦纳为最短。
注：若，则ta与tb一样长；若ta与tb只存在一个，不存在另一个，则存在的这一个，就是steiner最短树。
n=5时，情况复杂，有多棵steiner树。
n > 5时，情况就更加复杂，通常只能求近似解。
数学建模第三章作业
4 解答 假设银行利率在这批奖学金发放的期间不变，现行银行定期存款年利率为，所以在下面的计算中我们按银行定期存款年利率计算。记每年发放的奖学金为b元，第年取出当年的奖学金之后，继续存在银行的捐款帐户余额为万元，则列式得。其解为数列 将20万存入银行一年后可以得到利息元。1 每年发奖学金不高于6500...
数学建模作业第三章
数学建模作业。3 2 电视机最佳销售 设销售量 产量 x与 p关系 需求关系为。1 x me ap m,a 0 m 最大需求量 a 系数。设成本c与销售量x的关系 生产关系为。2 c c0 klnx c0,k 0,x 1 c0 只生产一件时的成本 k 规模系数。已知仅生产一台电视机的单位成本是500...
第三章作业
v s 顺序执行下述两个动作 1.s值加1，即s s 1 2.如果s 0，则该进程继续运行 3.如果s 0，则唤醒等待信号量s阻塞队列中的头一个进程 把阻塞态改为就绪态 执行v操作的进程继续运行。procedure s var s semaphore begin s s 1 if s 0 then ...