第17讲应急设施的优化选址问题
问题（AMCM-86B题）里奥兰翘镇迄今还没有自己的应急设施。1986年该镇得到了建立两个应急设施的拨款，每个设施都把救护站、消防队和警察所合在一起。图17-1指出了1985年每个长方形街区发生应急事件的次数。在北边的L形状的区域是一个障碍，而在南边的长方形区域是一个有浅水池塘的公园。应急车辆驶过一条南北向的街道平均要花15秒，而通过一条东西向的街道平均花20秒。你的任务是确定这两个应急设施的位置，使得总响应时间最少。
图17-1 1985年里奥兰翘每个长方街区应急事件的数目（I）假定需求集中在每个街区的中心，而应急设施位于街角处。
（II）假定需求是沿包围每个街区的街道上平均分布的，而应急设施可位于街道的任何地方。
§1 若干假设
1、图17-1所标出的1985年每个长方形街区应急事件的次数具有典型代表性，能够反映该街区应急事件出现的概率的大小。
2、应急车辆的响应时间只考虑在街道上行驶时间，其他因纱（如转弯时间等）可以忽略不计。
3、两个应急设施的功能完全相同。在应急事件出现时，只要从离事件发生地点最近的应急设施派出应急车辆即可。
4、执行任何一次应急任务的车辆都从某一个应急设施出发，完成任务后回到原设施。不出现从一个应急事件点直接到另一事件点的情况。（这是因为，每一个地点发生事件的概率都很小，两个地点同时发生事故的概率就更是小得可以忽略不计）。
§2 假定（I ）下的模
在假定（I ）下，应急需求集中在每个街区中心。我们可以进一步假定应急车辆只要到达该街区四个街角中最近的一个，就认为到达了该街区，可以开始工作了。按假定（I ），每个应急设施选在街角处，可能的位置只有6×11=66个。两个应急设施的位置的可能的组合至多只有66×65/2=2145个。这个数目对计算机来说并不大，可用计算机进行穷举，对每种组合一一算出所对应的总响应时间，依次比较得出最小的响应时间及对应的选址方案。具体算法是：
建立直角坐标系，以该镇的西北角为原点，从北到南为X -轴正方向，从西到东为Y -轴正方向，在南北、东西方向上分别以一个街区的长作为单位长，则街角的坐标),(Y X 是满足条件50,100≤≤≤≤Y X 的整数。而每个街区中心的坐标具有形式)5.0,5.0(++j i ，其中j i ,是满足条件：40,90≤≤≤≤j i 的整数。如果不考虑障碍和水塘的影响，同应急车辆从设在),(Y X 点的应急设施到以)5.0,5.0(++j i 为中心的街区的行驶时间等于
)5.05.0(20)5.05.0(15),,,(---+---=j Y i X j i Y X t
)5.17)5.0(20)5.0((15-+-++-=j Y i X 秒
记),(j i p 为以)5.0,5.0(++j i 为中心的街区的事故发生频率（即在图上该街区所标的数字）。如果应急设施设在),(),,(2211Y X Y X 这两点，总不妨设21X X ≤，则该设置方案的总响应时间为
),,,(2211Y X Y X T
∑∑===904
02211)},,,(),,,,(min{),(i j j i Y X t j i Y X t j i p
让1X 取遍0—10，2X 取遍101-X ，21,Y Y 分别独立地取遍0—4。依次对四数组),,,(2211Y X Y X 的每一个值算出对应的总响应时间的最小值及对应的四数组。
以上算法不难用计算机编程实现。由于数组的个数不算多（只有两千多个），计算机可很快得出答案。答案是：
两个应急设施分别设在点（2，3），（6，3）时最优。
这是在不考虑L 形障碍区域和水塘的影响的假定下得出的最优解，但从这两个点到
任何街区都可避开L 形障碍区域和水塘，故它们也就是原题所需的最优选址。
§2 假定（II ）下的模型
在假定（II ）下，由于允许应急设施设在街道上任何位置，这就有无穷多种可能位置，不能直接用计算机穷举。不过，我们可证明：应急设施仍应设在街角处，才能使总响应时间最少。
对已选定的两个应急设施的位置A 和B ，我们先来看总响应时间怎样计算。首先，我们将街道上所有的点的集合划分成两个责任区B A V V ,，分别由B A ,进行救助：街道上的点P 如果由A 点去救助比由B 点去救助的路程更近，就将P 划进A 的责任区A V ，反之就划进B V ，为叙述方便，我们将每个长方形街区的四条边中的每一条称为一条“街道”，街道的一段称为“街段”。每条街道中属于A V 的点与属于B V 的点各组成一个街段，分别称为A 的或B 的“责任段”。一条街道最多被分成两个责任段（也有可能整条街道属于同一个责任区，因而本身就是一个责任段），责任地段只有有限多条，对每个应急设施，我们分别算出它的每个责任段的总响应时间，将这些总响应时间求和就得到这个设施的责任区的总响应时间。将两个责任区各自的总响应时间相加就得到这一选址方案的总响应时间。
下面需要知道：任一设施A 到它的一个责任段EF 的总响应时间怎样计算。按假定（II ），街区出现事故的频率平均分布在它周围的四条街道上，每条街段的事故发生频率与它的长度成正比。将应急车辆每秒钟行驶的路程作为长度单位，则当街区事故频率为p 、街段的长度为t 时，这一街段的事故频率为70,70/t p ?是街区的周长，即车辆绕街区行驶一周需70秒。在大多数情况下，一条街段同时与两个街区相邻，两个街区的事故它都有份，它的事故频率应为q p t q p 、,70/)(?+分别是两个街区的事故的总频率（即原题图上标出的数）。当然可以用积分的方法。即插入分点将责任段EF 分成许多微小街段i δ，对每一小段i δ按其长度计算出它的事故发生频率i i kds p =，其中i ds 是i δ的长度，k 是与i 无关（但与EF 的选取有关）的常数。取应急车辆人A 到i δ中任意一点的行驶时间i T 作为A 到i δ的时间，则微小街段i δ的响应时间近似地等于i i ds T 。对这些微小的响应时间求和即得到EF 的总响应时间的近似值。让每个0→i ds ，求和变成求积分即可。但在这里，问题比较简单，可以不用积分。事实上，由于EF 的每一小段的事故发生频
率只与这一小段的长度有关，换句话说：频率密度是常数，只要求出EF 到A 的平均行驶时间T ，再乘以EF 的总的事故频率就行了。当A 设在街角处时，平均行驶时间也就是A 到EF 的中点M 的行驶时间212015m Y m X T MA -+-=秒，这里),(),,(21m m Y X 分别是M A ,的坐标，而且不考虑障碍和水塘的影响。将MA T 乘以EF 的事故频率，就得到EF 的总响应时间。换句话说，就是将EF 的事故频率EF P 集中到M 点，认为M 按频率EF P 发生事故，而EF 的其他点都不发生事故。这样不会改变EF 的总响应时间，却便于计算，如果应急设施A 不是设在街角处，而是设在某条街道CD 的两个端点D C 、之间，则可能出现这样的情况：从A 出发到EF 中的某些点的最短救助路线应向C 方向行驶，崦到另一些点去则应向D 方向行驶。这时，平均时间就不等于A 到EF 中点M 的时间AM T ，而是比AM T 小。在这样的情况下EF 可以分成两段GF EG 、，从A 到其中一段（比如EG ）上的所有的点的最短救助路线应向C 方向行驶，而到另一段（比如GF ）上的所有的点的点则应向D 方向行驶。分别计算GF EG 、的事故发生频率GF EG P P ,，将这两个频率分别集中在GF EG 、各自的中点21,M M ，就可分别算出GF EG 、的总响应时间，再将它们相加就得到EF 的总响应时间。
下面证明：最短的总响应时间必可由设在街角处的应急设施B A 、来实现。假定已选择两个应急设施B A 、的位置使总响应时间最短，且至少有一个设施（比如A ）不是设在街角处，而是设在某一条街道CD 的两个端点D C 、之间。我们证明：可以把这个设施从A 移到C 或D ，使总响应时间不增加，（而且很可能减少）。证明的主要想法是：将设施迁移到街角后，它到某些街段缩短了一段路程，同时到另外某些街段增加同样长的一段路程。如果路程缩短的那些街段的事故总频率大于路程增加的那些街段的事故总频率，则总响应时间缩短了，设施位置得到优化，说明原来的位置不是最优。先考虑与街道CD 相邻的街区，也就是与急救站A 相邻的街区。要使总响应时间最少，两个急救站B A ,的位置显然不应当靠得太近。因此，可以假定与A 相邻的街区周界上所有的点到A 的路程都小于它们到B 的路程，因而都应当由A 负责救助。这个街区的事故频率p 均匀分布在街区的周界上。我们指出：救助这个街区的事故频率p 均匀分布在街区的周界上。我们指出：救助这个街区的事故的总响应时间与A 在CD 上的位置选取无关。事实上，无论A 处于街道CD 上哪一个位置，总存在一点A '将街区周界分成路程相等的两段，
第一段由A 经C 到A '，第二段由A 经D 到A '，每一段的总行驶时间是7/2=35秒，事故
总频率是2/p 。由A 出发去救助每一段上各点的平均行驶时间等于35/2秒，因而两段的总响应时间为2)2/35()2/(??p 秒，确实与A 点位置的选取无关。因此，在讨论A 在CD 上的位置选取时，不需考虑到CD 相邻的街区的事故的影响，不妨暂时假定这样的街区的事故频率为0，特别是街道CD 上不发生事故，不需要救助。设P 是A 的责任区A V 内需要救助的任一点，从A 出发到P ，有两种可能的最短救助路线AP ：一种是沿AC 、经由C 点到P ，另一种是沿AD 、经由D 点到P 。凡是AP 属于前一种情况的，这样的点P 组成的集合记作C U ；凡是AP 属于后一种情况的，这样的点P 组成的集合记作D U 。这样就将A 的责任区按最短救助路线出发时的两个不同方向分成了两个区域（各由一些街段组成）。比较D C U U ,这两个区域各自的事故总频率D C P P ,的大小。如果C P 比D P 大，我们就将设施从A 移到C ，向C U 靠拢（同时远离D U ）；反之，当D P 比C P 大时，将设施由A 迁到D 去靠近D U （同时远离C U ）；当D C P P =时将设施任意迁到C 或D 都可以。我们证明：将设施经过这样的迁移后，总响应时间只可能减少，不可能增加。因此，假如迁移前的方案最优，迁移后一定还是最优（事实上，当D C P P ≠时，迁移后的方案一定比原来更优，说明原来不可能最优）。不妨先假定D C P P ≥，设施从A 迁到C 点。（C D P P >的情况同理）。为了便于比较迁移前后的总响应时间的变化情况，我们先作下面两个假设（其中所说的“旧”是指设施迁移前的情况，而“新”则是指迁移后的情况）：
（1）应急设施从A 搬透到C 后，两个旧的责任区B A V V ,先仍分别由C 和B 负责救助，暂不改变。如果在这样不改变责任区的情况下都能证明总响应时间不增加，则再进一步合理调整C 、B 的责任区还可能进一步缩短（至少不会增加）总响应时间，更加说明搬迁方案的优越。
（2）搬迁后从新设施C 到旧区域C U 中的任何一点P 的救助路线为：从C 出发离开CD ，沿原先A 的的旧的救助路线到P 。从C 到旧区域D U 的任何一点P 的救助路线为：从C 出发沿CD （经过A ）到D ，再沿原先A 的旧的救助路线到P 。
设应急车辆从A 到C 的行驶时间为T 。则按（2）的行驶路线，C U 的点到设施的路程都减少了AC ，行驶时间减少T ，总响应时间减少D C U T P ;的点则相反，路程都增加AC ，行驶时间都增加T ，总响应时间增加T P D 。由于T P T P P P D C D C ≥≥,，总响应时间减少量超过（或等于）增加量，总的效果是减少了（或不改变）总响应时间，设施搬迁后的位置比原来更优，至少同样优。
假设（2）的路线不一定是最短路线。如果再进一步选择最短路线，则还有可能进一步缩短新设施方案的总响应时间，更加说明其优越性，假设（1）的责任区的贡分不一定是合理的，可以再进行调整，将街道上的每一点划给离它最近的设施的责任区，这样又可能再减少新设施方案的总响应时间，再一次增加它的优越程度，这样就证明了新设施比旧设施更优，或同样优。
因此，在假定（II ）下，仍可设应急设施设在街角处。于是与假定（I ）的情况类似地可用计算机穷举算出答案来，对任一对候选的应急设施位置),(),,(2211Y X B Y X A ，（坐标为整数），求出每一条街道CD 的总响应时间，将所有街道的总响应时间相加就得到这
一选址方案的总响应时间。进行比较就可得出最短的总响应时间及对应的选址方案。
CD 的总响应时间的计算方法已在前面讲过。并且由于设施都设在街角处，只要将CD 分成两个责任段（在多数情形下实际上只有一个责任段）ED CE ,，将这两个责任段的事故频率分别集中在它们各自的中点计算就可以了。
计算结果：应急设施以设在点（2,3）,(7,3)时最优。
在假定（II ）之下本题还有一种更简单一些的近似算法。按照这个算法，假定（II ）和假定（I ）下得出同样的答案。我们将假定（I ）和假定（II ）进行比较。首先，既然已经证明在假定（II ）下应急设施仍应设在街角处，这就与假定（1）相同了，只是对每一对候选位置B A 、计算总响应时间时的算法不同。我们考虑每一个街区和它周围的四条街道在两种不同假设下算出的总响应时间有何不同。注意大部分街道都是街区的分界线，属于两个街区共同所有，分担两个街区的事故频率。但我们可以把这样的街道顺着街道方向剖开成为两部分（左半部分和右半部分），认为每半部分各只属于一个街区，只承担这一个街区的事故发生频率，不用再将两个相邻街区的频率相加。求出所有这些“半边街道”的总响应时间之和，也就是整个城镇的总响应时间了。现在我们来看在假设（II ）下围成每个街区的四条边（“半边街道”）的总响应时间。如果这四条边处在同一个责任区中，我们称这个街区为非边界街区。在计算非边界街区的四条边的总响应时间时把它们所分担的事故频率各自集中在它们的中点。相对的两条边分担的事故频率相等，在求它们的响应时间之和时可以用这两条边各自的中点到应急设施的行驶时间的平均值T 乘上它们的事故频率之和（即每一个的事故频率的两倍）来计算。但这个平均值T 就是街区中心到应急设施的行驶时间，（想象有穿过街区中心的东西方向南北方向的
道路供行驶）。因此，可以把相对两边的事故频率集中在街区的中心，从而把整个街区的事故频率集中到街区中心。设这个街区的中心M的坐标为)5.0
i，
+j
,5.0
(+≤j
≤
i，而这个街区所属的应急设施A的坐标为)
≤
4
)
≤
0,9
0(是整数
X，则这个街区
(Y
,
周围的四条街道到A的平均行驶时间就等于
+
+
-j
Y
X（2）
i
-
(
)5.0
秒
(
20
)5.0
15+
将这一结果与假定（1）下从)
,
Y
X
t（见前面（1）
(j
i
,
X
(Y
A到这个街区救助的行驶时间)
,,
式）相比，只相差一个常数17.5秒。换句话说，按假定（1）只要求应急车辆到达街区的最近的一个街角，而现在相当于要求车辆继续行驶到街区的中心（假定存在着可供车辆行驶的穿过该中心的东西、南北两条道路）。如果在假定（1）下也改为要求车辆行驶到街区中心，则每一种选址方案的总响应时间增加一个常数，最短的总响应时间也就增加一个常数，而方案的优劣不会因此改变，原来的最优方案仍然最优。但这样一来在两个假定下对非边界街区的总响应时间的计算方法就完全相同了。唯一有区别的地方是被责任区分界线一分为二的街区。在假定（I）下是按该街区中心所在责任区将它整个划归这个责任区。按假定（II）则将街区分成两部分，分别属于两个责任区，这样可使这个街区的总响应时间比按假定（I）略小一些。在假定（II）下，如果在计算时对所有的街区也按街区中心的归属将这个街区全部划入一个责任区，这样算出来的就是近似的总响应时间，而按这样的算法得出的最优解就是近似的最优。而这个近似的最优解必定就是假定（I）下的最优解（2，3）（6，3），无须重新计算。在假定（II）下精确计算这个方案的总响应时间，与前面用计算机求出的真正的最优方案（2，3），（7，3）相比较，只相差1秒钟。考虑到原始数据（街区的事故次数）本身并不能百分之百的代表今后的事故频率，1秒钟的误差应该说是在允许范围，并不能说明用近似算出的解就一定不是最优，在实际中完全可以当最优解来用。更何况，即使在假定（II）下，如果采用方案（2,3），（6,3），则每个街区都整个的在一个责任区中，没有哪个街区被分割开来分别划进两个责任区；而方案(2,3)，（7,3）却将5个街区分割开了，这给应急设施进行救助带来不方便，权衡利弊，我们得出下面的结论：
按假定（II），方案（2,3），（7,3）比方案（2,3），（6,3）的总响应时间约少1秒钟，（分别为5121.4秒、5122.5秒）。但考虑到实施救助的方便起见，宁肯采用方案（2,3），（6,3）。
§3 算法的进一步讨论
以上算法是建立在用计算机进行穷举的基础上，可以称为：
算法1 计算机穷举法。
穷举的方法当然可以说是笨办法，它对一些明显不优的位置仍要一个个去验证，这实在显得太笨。但穷举的办法也有一个好处，那就是：不用再证明最后答案的最优性。这个答案已经和所有的别的可能方案都比较过了，比它们都优，最优性已经得到证明。本题的一个特点是需要穷举的可能方案的数目不大，用计算机进行穷举所花的时间很少，因而是可行的，也是优越的。但假如考虑更一般的城市，街道数目较多，且应急设施的个数也可能不止两个，而是更多，则计算机所花时间将会大大增加。能不能有一种非穷举的有效算法呢？可以考虑采用如下的方法。
算法2 逐次改进法：它的基本想法是先从一个初始的方案（不一定最优）出发，逐步加以改进，直到得到一个不能再改进的方案，就有可能是最优方案，具体作法是：
先任选两个位置（坐标为整数的点）00,B A 作为应急设施B A ,的最初的选址。比如可选)5,10(),0,0(00B A ，即选这个城镇的西北角、东南角分别作为00,B A 。（当然也可一开始凭直觉将00,B A 选得更好一些，更快地达到最后结果）。试考虑将设施A 向东、西、南或北四个方向各移动一个街区（即将A 的横坐标或纵坐标增加或减少一个单位），B 暂时不动，看总响应时间如何变化。（当然，如果在某个方向上已经不可能移动，即已经处于城镇的边界，就不考虑这一方向上的移动）。如果向某一方向上的移动引起总响应时间的增加（或不变），这一方向不是好方向，再换另一个方向试试。如果向某一方向的移动引起总响应时间的减少，这一方向就是好方向，将A 向这一方向移动一个街区（从
0A 移到1A ）
，以B A ,的新位置作为出发点重新向各个方向试探。如果A 向四个方向的移动都不能缩短总响应时间，则将A 固定不动，再试B 的移动，直到B 向四个方向上的移动都不能缩短总响应时间，再考虑A 的移动。这样将B A ,两个设施轮流移动以优化方案，直到不能再优化为止：即B A ,中任何一个向任何方向的移动都不能使总响应时间再缩短。这时这个优化过程就收敛了，我们可以认为找到了最优方案。如果从我们刚才所说的两点（0,0），（10,5）出发，采用假定（I ）的算法，进行逐次改进，最后就收敛于（2,3），
（6,3）这两点，已经知道它确实是最优方案。
能否证明：从任意两点出发都收敛于最优方案？从数学理论上讲，这样的逐次改进的方法达到的是“极好值点”，而不一定是“最好值点”。即：将总响应时间T 作为两个应急设施位置的四个坐标2211,,,Y X Y X 的函数，用逐次改进法所得到的是函数的极小值点，但不一定是最小值点。如果能证明这个函数只有一个极小值点，它也就是最小值点。但这一般是不成立的，即使成立也是很难证明的。比如本题。如果从（4,0），（4,5）这两点出发，就会发现最后收敛于（4,1），（5,4）这两个位置，不是最优方案。（按假定（I ）的算法，方案（4,1），（5,4）的总响应时间为3355秒，而方案（2,3），（6,3）和（4,1），（5,4）。由于选择的初始位置不同，逐次改进后分别收敛于这两组位置。初始的两个点的横坐标比较接近的，容易收敛于后一组解。反之一般收敛于前一组解。对本题来说，由于城镇的形状是东西方向窄，南北方向宽，从直观上讲，一开始选的两个点应该一个偏北，另一个偏南，这样才使每个责任区中相距最远的点的距离都不大，总响应时间才不会太大。如果选的两个位置呈东西方向排列（即械坐标很接近），如上面所说的（4,0），（4,5）两点，则两个责任区都是南北方向上的长条，责任区西北端的点和东南端的点相距很远，总响应时间显然不会小，因而一开始就是不合理的，收敛过程也就容易误入歧途。
由此可见，上述的逐次改进法在理论上是不完善的，但在实用上却是可行的，只要最初的两个位置不是选的太不合理，实际上仍能得出最优解。当然也可以从不同的初始位置出发多试几次，如果经过收敛得到若干个不同的解，再通过比较从这些解中选出一个最优的就行了。不过，就本题来说，计算机穷举法计算量本来就不大，在理论上又没有漏洞。逐次改进法虽然可以提高一些速度，但仍然不能用手工计算，反而带来理论上的缺陷，似乎还是得不偿失，不如计算机穷举法来得干净利落。
§4 最优解满足的条件
上述的逐次改进法，试图改进计算机穷举发不管好坏一概穷举的“穷举”之处，但它自己也同样笨拙：一开始的初始位置随便乱选，也是不管好坏；试探的时候不管怎样只走一步，而不敢向好的方向大踏步的改进。能不能将它再改进一下，使得能比较容易
判断方案？为此，先来考察一下最优解到底应该满足什么样的条件，即使不能得出充分条件，哪怕得出一些操作方便的必要条件也行。
说起来也简单，最优满足的必要充分的条件是：用任何方法都不能将它改进。当然，“任何方法”是难以操作的；谁也不好担保他所找到的方法已经穷尽了所有的方法。但是，如果找到一种方法将它改进，就足以说明它不是最优。因此，最优解满足的必要条件：用你所找到的方法不能将它改进，这一条件比较操作，前提是必须尽量找到一些方法，使得用你的方法不能改进的解很少。下面就给出一个这样的方法。
先将问题简化，改为：只设一个应急设施。此是存在非穷举的有效算法如下。这个方法有些类似于求质点系统的力学重心（但只是类似而并不完全相同），为叙述方便，不妨称为“重心法”。
设应急设施的最优位置在A 点，其坐标为),(Y X 。我们的基本想法是：如果A 点北面（即横坐标X ≤）的街区与南面（即横坐标X >）的街区的事故发生的频率悬殊很大，则将设施向事故较多的那个方向移动就可以减少总响应时间，从而将方案改进。因此，最优位置A 应使得它的北面和南面发生事故的频率尽可能相等，换句话说，北面发生的事故应当尽可能接近整个城镇事故总数的一半。同理，它的东面和西面的事故频率也应该尽可能相等，西面发生的事故应尽可能接近事故总数的一半。
为此，对横坐标100<≤x 的每个整数值定义-x 事故频率函数)(x p ，它等于所有满足条件x i ≤的街区),(j i 的事故频率的总和。这里，我们用每个街区东南角的坐标),(j i 来代表这个街区。这样，)(x p 是单调递增函数。0)0(=p 。当1≥x 时)1()(--x p x p 就是横坐标等于x 的5个街区的事故频率之和。因此0)1()(≥--x p x p 。而且，这本题的数据而言，0)1()(>--x p x p 对1=，2,…,9,10成立，)(x p 是严格单调递增函数。)10(p P =就是整个城镇的事故频率总和，本题中109=P 。按照上面的说法，最优解),(Y X A 的横坐标X 应使2/)(P X p -最小。这样的X 最多只有两个（分别大于和小于2/P ）。就本题的数据而言，计算得：
100-=i 时)(i p 依次为0,15,28,38,47,65,78,85,92,99,109。
47)4(=p 最接近5.542/=P ，故4=X 。同样，对纵坐标50≤≤y 的每个整数值定义)(y q 为满足条件y j ≤的街区),(j i 的事故频率总和，本题为：
50-=j 时)(j q 依次为0,25,40,57,83,109。
同样找出Y 使2/)(P Y q -最小，得)5.542/10957)3((,3最接近与===q Y 。因此，如果不考虑障碍和水塘的影响，确实就是所求的最优位置。
下面证明这个方法的正确性。最优位置显然存在，只要证明其他的位置都可以改进，不是最优，则),(Y X 当然就是最优了。考虑应急设施的任一其他位置),(y x 。先考察M 的横坐标x 。过M 作一条东西方向的直线1l 将城镇分为两部分。将事故频率小的那一部分称为1U ，事故频率较大的那部分称为2U （两部分事故频率相等时，任意指定一个为1U ，另一个为2U ，不过本题并不出现这一情况）。考虑将M 向2U 那一侧移动一个街我到N 点（纵坐标仍为y ，横坐标变为11-+x x 或）。过N 点再作一条东西方向的直线2l （与1l 平行），2l 将事故较多的这一区域2U 再分成两部分，其中21,l l 之间的那部分记为0U ，另一部分记为1V ，我们来看101,,V U U 这三部分到设施的路程的变化及由此引起的总响应时间的变化，结果是：
0U 中的街区到新旧设施的路程相等，对总响应时间没有影响。
1U 中的街区到新设施N 的路程比到旧设施M 增加1个街区，引起总响应时间增加15×1p 秒，1p 是1U 的事故总频率。
1V 中的街区到新设施N 的路程比到M 减少1个街区，引起总响应时间减少15×2p 秒，2p 是1V 的事故总频率。
容易看出，只要12p p >，则移动设施的总效果是总响应时间减少，方案优化，原方案不优。
如果设0U 的事故总频率为0p ，则按照原来的假设，2U （由0U ，1V 组成）中的事故频率02p p +大于1U 中的事故频率1p 。如果02p p +比1p 大得太多，以至于从02p p +中减去0p 后所得的2p 仍大于1p ，原来的方案就不是最优了。我们证明：当X x ≠时一定是这样。先设2/)(P X p ≤。（比如本题5.5447)4(<=p ，就是这样。）如果X x <，则)1(2/)(,2/)()1()(,1+-≤<≤≤+<≤+x p P P x p P X p x p x p X x 。考虑将设施从旧位置),(y x 移动到新位置),1(y x +，则)(x p 就是旧设施北面的事故总数，)1(+-x p P 就是新设施南面的事故总数。既然)1()(+- 1(+X p 与)(X p 同样接近2/P ，1+X 也可以取来作为),1(,Y X X +与),(Y X 同样优。假设不是这样的情况（如本题），则)1()().(2/2/)1(+->->-+x p P X P X p P P x p ，即),(y x 北面的事故比),1(y X +南面的事故多，将设施从),(y x （即),1(y X +）向北移到),(y x 可以引起优化。这就在2/)(P X p ≤的情况下证明：当X x ≠时),(y x 一定不是最优。对2/)(P X p >的情况，同理可以证明同样的结论。同理还可证明：当Y y ≠时),(y x 也一定不是最优，结果只剩下),(Y X 才有可能最优，因而也就确实是最优。 现在回到原题条件，考虑设两个应急设施的情形，假如按前面所说的算法2，指定了两个点00,B A 作为应急设施的候选位置，这一组位置是否已经最优了？如果不是，有什么方法较快地改进它，而不要一步一步地试探着前进？我们可以先按设施的两个候选位置00,B A 划定它们的责任区00,B A V V 的范围，将每个街区（按假定（I ））或街道上的每个点（按假定（II ））划给离它最近的设施的责任区。到两个设施的路程相等的，任意划给一个责任区。然后，在每个责任区内可以按前述的“重心法”各找到一个的最佳位置11,B A 。用11,B A 分别取代00,B A ，即使在不调整责任区的情形下已经能够说明方案被优化了。如果11,B A 的位置与00,B A 不完全相同，责任区也可能发生变化。按设施的新位置 11,B A 重新划定责任区。在两个新的责任区范围内再一次用“重心法”各选一个新位置。这样，调整责任区范围和在每个责任区内寻找最优位置交替进行，每进行一次都使方案得到优化。这个过程必定收敛（因为方案不能无穷地优化下去），即设施位置及责任区范围都不能再改变。这就达到了这个方法所能找到的最优方案。 以上方法可以作为算法3，仍称为“重心法”（因为它是在两个责任区内分别用重心法求最优位置）。而且，在实际计算时，可以颠倒一下顺序：第一步不先选两点位置，而先按某种方案将所有街区划分成两个区域，作为最初的责任区，要在责任区内分别用重心法求出两个点。 重心法通常都比算法2的一步一步改进要快，很快就可收敛到一组不能再改进的方案，收敛后是否就得到了最优解？与算法2的情形类似，仍然不能肯定，很可能与一开始划定责任区范围的方式有关。 使用重心法时，还应当考虑到这样的情况：如果不改变责任区，11,B A 在各自的责任区内当然是最优位置，一移动就会使总响应时间增加，设增加量为1t 。但如果移动后引起责任区改变，则调整责任区可再使总响应时间减少某个2t ，假如移动的方式选得适 当，使12t t >，则方案仍然获得改进。这说明，在用重心法达到收敛后，还应该用算法2再试探一下，看是否还有改进的余地。不过，不需要具体计算出总响应时间，只要考察总响应时间的增减情况就行了。由于试探时设施只移动一步（一个街区的长度），引起的责任区改变只有半步，2t 一般都很小，实际上很难使12t t >，要使1t 比2t 更小，将责任区内已经达到最优位置),(Y X 的点的坐标X （或Y ）变动为1±X （或1±Y ）时应尽量使频率函数值)1(±X p （或)1(±Y q ）仍很接近2/1P ，这里1P 是该责任区内的事故频率总数。但要2/)1(2/)(11P X p P X p -±-与（或2/)1(2/)(11P Y q P Y q -±-与）都很接近于0，只有它们符号相反时才有可能。也就是说：只考虑),(Y X 向事故多的方向上的移动。 下面用重心法来计算本题的最优解。由于收敛速度很快，可以用手算实现，只要第一步的责任区划分得不是太不合理，求出的也的确是最优解。 先在假定（I ）下计算： 考虑到城镇是长方形，很自然先用沿东西方向的直线5=x 将城镇分成同样大的南、北两块（各含25个街区）11,V U ，这样做的理由是：可以使每块内部点与点之间的最远程不会太长，有利于降低总响应时间。分别计算这两块的频率函数得： 北块：-x 频率函数值：0,15,28,38,47,65；-y 频率函数值；0,16,23,36,50,65。 南块：-x 频率函数值：0,13,20,27,34,44；-y 频率函数值：0,9,17,21,33,44。 北块：-x 频率函数值最接近65/2=32.5的是28，-y 频率函数值最接近65/2=32.5的是36。最优点1A 的坐标为（2,3）。同理可算出南块的最优点为)3,7(1B 。 再划分11,B A 的责任区；横坐标为4的四个街区的中心离11,B A 的路程相等，划给1A 或1B 都可以。如果划给1A ，则就是原来的责任区方案11,V U ，设施位置不能再优化。考虑将它们划给1B ，则新的责任区22,V U 分别由北面的20个街区（横坐标3≤的）和南面的30个街区（横坐标4≥的）组成。对这两块重新选最优点。2U 的最优点仍是21).3,2(V A 的最优点变成)3,6(2B 。 21,B A 的责任区仍只能分为22,V U ，各自的最优点当然还是21,B A ，已不能再优化，将它们作为最终答案。（与算法1的结果比较知它们确实是最优）。 再在假定（II ）下计算： 第一步：仍先平均分成南、弱两个相等的区域11,V U ，最优点仍分别为)3,7(),3,2(11B A 第二步：11,B A 的责任区的边界为直线5.4=x ，它将横坐标为4的5个街区都沿东西方向剖为两半，各属于一个责任区，这些街区的事故频率总和18也被这两半所平分，各占9。仍将1A 的责任区记为12,B U 的责任区记为2V 。则2U 的-x 频率函数值为0,15,28,38,47,56,28)2(=p 最接近56/2=28，故最优点的横坐标仍为2；-y 频率函数值为： 0,17.5,26.5,41,56.5,74，最接近74/2=37的是41)3(=q ，最优点纵坐标为3，即2U 的最优点仍为)3,2(1A 。同理可计算出2V 的最优点也还是)3,7(1B 。即过程已经收敛。 第三步：考虑用算法2（逐次改进法）能否再改进方案。比如，考虑)3,7(1B 能否移动。在原来的责任区2V 内，1B 的北面的事故总频率为29，南面为24，考虑向北面移动一个街区。但这样移动使南面的街区的行驶时间都增加了15秒，总响应时间增加15×24秒；而北面的街区中有5个（它们的事故总频率为7）的行驶时间没有改变，而另外有事故频率为22的街区的行驶时间减少了15秒，引起总响应时间减少15×22秒，减少量<增加量，得不偿失，但二者的差别15×（24-22）=30秒已经不大，看看能否通过责任区的调整得到补偿。由于设施从)3,7(1B 移到)3,6(2B ，责任区边界由5.4=x 变为4=x ，向北移了半个街区，造成了5个“半街区”从1A 的责任区变为2B 的责任区。这5个“半街区”的北面一侧的街道调整前后的行驶时间相同，不引起总响应时间的改变。剩下只有东西两侧偏北的半条街道的行驶时间减少了7.5秒（南北方向半个街区的行驶时间），而这些街段占街区周长的（15/2×2）/70=3/14（70秒为车辆绕街区行驶一周的时间），故事故总频率为18×3/14（18是这5个街区事故频率之和）。故责任区的调整引起总响应时间减少7.5×18×3/14≈28.9秒，尚差1.1秒才能补偿前面所增加的30秒总响应时间。因此，将第二个设施从（7,3）移到（6,3）反而引起总响应时间增加1.1秒，还是以不移动为优。（注意：这1.1秒之差就是前面计算机穷举法时用假定（I ）下的结果近似地作为假定（II ）下的结果造成的差别）。 如果在一开始不用直线5=x 来分割责任区，而用直线4=x ，则第一步得到的方案就是（2,3），（6,3）。类似的分析可得出：在假设（II ）下，如果将(6,3)向南移动一个街区，可使总响应时间减少1.1秒，从而方案得到优化。 如果一开始用南北方向的直线5.2=y 来分割责任区，将城镇分成同样大小的东、西两块，在假定（I ）下用重心法计算的结果，最后收敛于（4.1），（5,4）两点，恰好就是逐次改进法所得到的另一对极值点。但这样的责任区分割方案显然是不可取的。 学校选址问题 摘 要 本文针对某地新开发的20个小区建设配套小学问题建立了0-1规划模型和优化模型。为问题一和问题二的求解，提供了理论依据。 模型一： 首先：根据目标要求，要建立最少学校的方案列出了目标函数： ∑==16 1i i x s 然后：根据每个小区至少能被一所学校所覆盖，列出了20个约束条件; 最后：由列出的目标函数和约束函数，用matlab 进行编程求解，从而得到，在每个小区至少被一所学校所覆盖时，建立学校最少的个数是四所，并且一共有22种方案。 模型二： 首先：从建校个数最少开始考虑建校总费用，在整个费用里面，主要是固定费用，由此在问题一以求解的条件下，进行初步筛选，得到方案1,4,8的固定成本最少。 然后：在初步得出成本费用最少时，对每个这三个方案进一步的求解，求出这三个方案的具体的总费用，并记下这三套方案中的最小费用。 其次：对这三套方案进行调整，调整的原则是：在保证每个小区有学校覆盖的条件下，用多个固定成本费用低的备选校址替换固定成本费用高的备选校址。在替换后，进行具体求解。 再次：比较各种方案的计算结果，从而的出了如下结论： 选用10,11,13,15,16号备选校址的选址方案，花费最少，最少花费为13378000元。 最后：对该模型做了灵敏度分析，模型的评价和推广。 关键字：最少建校个数 最小花费 固定成本 规模成本 灵敏度分析 1. 问题重述 1.1问题背景： 某地新开发的20个小区内需要建设配套的小学，以方便小区内居民的的孩子上学。但是为了节省开支，建造的学校要求尽量的少，为此，设备选定的16个校址提供参考，各校址覆盖的小区情况如表1所示： 表1-1备选校址表 备选校址 1 2 3 4 5 6 7 8 覆盖小区 1,2,3, 4,6 2,3,5,8, 11,20 3,5,11,20 1,4,6,7, 12 1,4,7,8,9,11,13, 14 5,8,9,10 11,16,20 10,11,1516,19, 20 6,7,12, 13,17, 18 备选校址 9 10 11 12 13 14 15 16 覆盖小区 7,9,13, 14,15, 17,18, 19 9,10,14,15,16, 18,19 1,2,4,6, 7 5,10,11, 16,20, 12,13，14,17, 18 9,10,14, 15 2,3,,5, 11,20 2,3,4,5,8 1.2 问题提出： 问题一、求学校个数最少的建校方案，并用数学软件求解（说明你所使用的软件并写出输入指令）。 问题二、设每建一所小学的成本由固定成本和规模成本两部分组成，固定成本由学校所在地域以及基本规模学校基础设施成本构成，规模成本指学校规模超过基本规模时额外的建设成本，它与该学校学生数有关，同时与学校所处地域有关。设第i 个备选校址的建校成本i c 可表示为 ?? ???-??+=， 否则， 若学生人数超过学生人数0600 )600(50 1002000i i i c βα 其中i α和i β由表1-2给出： 表1-2 学校建设成本参数表（单位：百万元） 备选校址 1 2 3 4 5 6 7 8 i α 5 5 5 5 5 5 5 3.5 i β 0.15 0.15 0.15 0.15 0.15 0.15 0.15 0.1 备选校址 9 10 11 12 13 14 15 16 i α 3.5 3.5 3.5 3.5 2 2 2 2 i β 0.1 0.1 0.1 0.1 0.05 0.05 0.05 0.05 考虑到每一小区的学龄儿童数会随住户的迁移和时间发生变化,当前的精确数据并不能作为我们确定学校规模的唯一标准，于是我们根据小区规模大小用统计方法给出每个小区的学龄儿童数的估计值，见表1-3： 表1-3.各小区1到6年级学龄儿童数平均值（样本均值） 小区 1 2 3 4 5 6 7 8 9 10 学龄儿童数 120 180 230 120 150 180 180 150 100 160 物流预选址问题 (2) 摘要 .............................................................................................. 错误！未定义书签。 一、问题重述 (3) 二、问题的分析 (3) 2.1 问题一：分析确定合理的模型确定工厂选址和建造规模 (4) 2.2 问题二：建立合理的仓库选址和建造规模模型 (4) 2.3 问题三：工厂向中心仓库供货的最佳方案问题 (5) 2.4 问题四：根据一组数据对自己的模型进行评价 (5) 三、模型假设与符号说明 (5) 3.1条件假设 (5) 3．2模型的符号说明 (5) 四、模型的建立与求解 (6) 4.1 问题一：分析确定合理的模型为两个工厂合理选址并确定建造规模 (6) 4.1.1模型的建立 (7) 4.2 问题二：建立合理模型确定中心仓库的位置及建造规模 (10) 4.2.1 基于重心法选址模型 (10) 4.2.2 基于多元线性回归法确定中心仓库的建造规模 (12) 4.3 问题三：工厂向中心仓库供货方案 (13) 4.4 问题四：选用一组数据进行计算 (14) 五、模型评价 (21) 5.1模型的优缺点 (21) 5.1.1 模型的优点 (21) 5.1.2 模型的缺点 (21) 六参考文献 (21) 物流预选址问题 摘要 在物流网络中，工厂对中心仓库和城市进行供货，起到生产者的作用，而中心仓库连接着工厂和城市，是两者之间的桥梁，在物流系统中有着举足轻重的作用，因此搞好工厂和中心仓库的选址将对物流系统作用的发挥乃至物流经济效益的提高产生重要的影响。 本论文在综述工厂和中心仓库选址问题研究现状的基础上，对二者选址的模型和算法进行了研究。对于问题一二，通过合理的分析，我们采用了重心法选址模型找到了工厂和中心仓库的大致位置并给出了确定工厂和中心仓库建造规模的参数和公式，通过用 学校选址问题 摘要 本文为解决学校选址问题，建立了相应的数学模型。 针对模型一 首先，根据已知信息，对题目中给出的数据进行处理分析。在保证每个小区,学生至少有一个校址可供选择的情况下，运用整数规划中的0-1规划法，列出建校方案的目标函数与其约束条件，通过LINGO软件，使用计算机搜索算法进行求解。得出建立校址的最少数目为4个。再运用MATLAB软件编程，运行得到当建校的个数为4个时，学 首先，对文中给出的学校建设成本参数表和各校区1到6年级学龄儿童的平均值（样本均值）进行分析，可知20个小区估计共有4320个学龄儿童，当每个学校的平均人数都小于600时，至少需要建设8个学校；其次，模型一得到最少的建校数目为4个，运用MATLAB软件编程，依次列出学校个数为4、5、6、7、8时的最优建校方案，分别算出其最优建校方案下的总成本；最后，通过对比得出，最低的建校总成本为1650万，即选取校址10、11、13、14、15、16建设学校。 最后，我们不但对模型进行了灵敏度分析，，保证了模型的有效可行。 关键词：MATLAB灵敏度 0-1规划总成本选址 1 问题重述 当代教育的普及，使得学校的建设已成为不得不认真考虑的问题。 1.1已知信息 1、某地新开发的20个小区需要建设配套的小学，备选的校址共有16个，各校址覆盖的小区情况如表1所示： 2、在问题二中，每建一所小学的成本由固定成本和规模成本两部分组成，固定成本由学校所在地域以及基本规模学校基础设施成本构成，规模成本指学校规模超过基本规模时额外的建设成本，它与该学校学生数有关，同时与学校所处地域有关。设第i 个备选校址的建校成本i c 可表示为 （单元：元）学生人数)600-(50100200010? ?? ???+=i i i c βα，若学生人数超过600人，其中 i α和i β由表2给出： 并且考虑到每一小区的学龄儿童数会随住户的迁移和时间发生变化，当前的精确数据并不能作为我们确定学校规模的唯一标准，于是我们根据小区规模大小用统计方法给出每个小区的学龄儿童数的估计值，见表3： 1.2提出问题 1、要求建立数学模型并利用数学软件求解出学校个数最少的建校方案。 2、求出总成本最低的建校方案。 2 问题假设与符号说明 《数学建模》选题(一) 1、选址问题研究 在社会经济发展过程中, 经常需要在系统中设置一个或多个集散物质、传输信息或执行某种服务的“中心”。在设计和规划商业中心、自来水厂、消防站、医院、飞机场、停车场、通讯系统中的交换台站等的时候,经常需要考虑将场址选在什么位置才能使得系统的运行效能最佳。选址问题, 是指在指定的范围内, 根据所要求的某些指标,选择最满意的场址。在实际问题中,也就是关于为需要设置的“设施”选择最优位置的问题。选址问题是一个特殊类型的最优化问题,它属于非线性规划和组合最优化的研究范围。由于它本身所具有的特点,存在着单独研究的必要性和重要性。 1.1“中心”为点的情形 如图1，有一条河，两个工厂P 和Q位于河岸L（直线）的同一侧，工厂 P 和 Q 距离河岸L分别为8千米和10千米，两个工厂的距离为14千米，现要在河的工厂一侧选一点R，在R处建一个水泵站，向两工厂P、Q 输水，请你给出一个经济合理的设计方案。 图1 图2 （即找一点 R ，使 R 到P、Q及直线l的距离之和为最小。） 要求和给分标准： 提出合理方案，建立坐标系，分情况定出点R的位置，0分——70分。 将问题引申： （１）、若将直线 L缩成一个点（如向水库取水），则问题就是在三角形内求一点R，使R到三角形三顶点的距离之和为最小（此点即为费尔马点）。 （２）、若取水的河道不是直线，是一段圆弧（如图2），该如何选点？ 对引申问题给出给出模型和讨论30分——50分。 抄袭者零分；无模型者不及格；无程序和运行结果扣20-30分；无模型优缺点讨论扣10分。 1.2“中心”为线的情形 在油田管网和公路干线的设计中提出干线网络的选址问题： 问题A ：在平面上给定n 个点n P P P ,,,21 ，求一条直线L ，使得 ∑=n i i i L P d w 1 ),( （1） 为最小，其中i w 表示点i P 的权，),(L P d i 表示点i P 到第直线L 的距离。 问题B ：平面上给定n 条直线n L L L ,,,21 , 求一点X , 使 ∑=n i i i L X d w 1 ),( （2） 为最小，其中i w 表示直线i L 的权，),(i L X d 表示点X 到第直线i L 的距离。 问题C ：在平面上给定n 个点n P P P ,,,21 ，求一条直线L ，使得 ),(max 1L P d w i i n i ≤≤ （1） 为最小，其中i w 表示点i P 的权，),(L P d i 表示点i P 到第直线L 的距离。 问题D ：平面上给定n 条直线n L L L ,,,21 , 求一点X , 使 ),(max 1i i n i L X d w ≤≤ （2） 为最小，其中i w 表示直线i L 的权，),(i L X d 表示点X 到第直线i L 的距离。 参考文献 【1】林诒勋, 尚松蒲. 平面上的点—线选址问题[J]. 运筹学学报,2002,6(3):61—68. 【2】尚松蒲, 林诒勋. 平面上的min-max 型点—线选址问题[J]. 运筹学学报,2003,7(3):83—91. 要求和给分标准： 选择问题A 和B(或者C 和D)进行研究：根据文献重述模型（10分），提出自己的算法(30分)，计算机仿真验证算法的正确性（40分，含如何在平面上随机产生n 个点，对每个点随机赋权，按照算法编程实现求干线的程序，并将寻得的干线和点在平面上图示，建议用MATLAB 编程）。 将问题引申： 如果同时确定两条、三条干线，应该如何讨论？其他情形的讨论？ 对引申问题给出给出模型和讨论20分——30分。 抄袭者零分；无模型者不及格；无程序和运行结果扣20-30分；无模型优缺 高速公路突发事件应急救援设施选址优化 摘要：首先对高速公路交通事故紧急救助的资源需求进行了探讨，分析了救援响应时间与救援资源布局的关系，针对交通突发事件的特点建立救援资源配置模型，该研究为目前高速公路应急资源的科学布局提供了重要的参考依据。 关键词：突发事件，应急救援，资源配置 2010年底，我国高速公路通车里程已达到7.4万公里，预计2011年底全国高速公路规模达到8.5万公里左右。高速公路上由于汽车行驶速度快，汽车运行时动量较大，容易发生交通事故，且高速公路交通事故的危害程度高于普通公路上同类事故的数倍乃至几十倍。为此，我国各级政府和交通管理部门特别重视高速公路交通事故的救援。当前，我国交通应急救援工作处于各自独立、分散管理的状态，缺少统一的指挥调度平台，很难实现各部门间的配合与协调。交通突发事件紧急救援系统将为交通安全救援时的多方协作，共同作业提供平台和空间，真正实现紧急救援及应急处理的联合行动。为此引入现代数学中的优化控制方法来进行深入研究。 1 突发事件资源需求与布局 1.1 高速公路突发事件资源需求 高速公路交通救援资源一般可分为常用救援资源和特殊救援资源。常用救援资源包括：交警巡逻车、路政巡逻车、清障车、拖车、消防车、救护车、巡逻车。特殊救援资源：大型起吊设备，一般在发生重特大交通事故时才使用。应急救援需要用到的资源分别由交警、路政、排障、养护、消防以及救护部门的资源配置点派出[1]。高速公路突发事件应急救援，主要涉及高速公路管理部门、交警、医务部门、消防部门、事故排除部门、特种物品(化学物品等)处置部门、气象部门、安全监管部门等。 1.2 响应时间与资源布局 国内外相关研究表明，根据交通事故伤的特点，对于交通事故重伤者，在事发后90min内给予急救，其生存率为10%以下；在60 min内得到救援，其生存率为40%；在30 min内获救，其生存率高达80%。因此，高速公路上应按照救援响应的时间要求配置救援资源，并对救援资源的分布进行科学、合理的规划，使路段上任意一点发生交通事故后都能得到及时救助。 2紧急救援点及权重描述 2.1 紧急救援点描述 由于高速公路上新建专用的紧急救助点成本较高，结合我国目前的实际情况，可依托现有的高速公路紧急服务设施为救助点配置救援资源。其中，可供 学校选址问题 摘要 本文针对某地新开发的20个小区建设配套小学问题建立了0-1规划模型和优化模型。为问题一和问题二的求解，提供了理论依据。 模型一： 首先：根据目标要求，要建立最少学校的方案列出了目标函数： 然后：根据每个小区至少能被一所学校所覆盖，列出了20个约束条件; 最后：由列出的目标函数和约束函数，用matlab进行编程求解，从而得到，在每个小区至少被一所学校所覆盖时，建立学校最少的个数是四所，并且一共有22种方案。 模型二： 首先：从建校个数最少开始考虑建校总费用，在整个费用里面，主要是固定费用，由此在问题一以求解的条件下，进行初步筛选，得到方案1,4,8的固定成本最少。 然后：在初步得出成本费用最少时，对每个这三个方案进一步的求解，求出这三个方案的具体的总费用，并记下这三套方案中的最小费用。 其次：对这三套方案进行调整，调整的原则是：在保证每个小区有学校覆盖的条件下，用多个固定成本费用低的备选校址替换固定成本费用高的备选校址。在替换后，进行具体求解。 再次：比较各种方案的计算结果，从而的出了如下结论： 选用10,11,13,15,16号备选校址的选址方案，花费最少，最少花费为13378000元。 最后：对该模型做了灵敏度分析，模型的评价和推广。 关键字：最少建校个数最小花费固定成本规模成本灵敏度分析 1.问题重述 1.1问题背景： 某地新开发的20个小区内需要建设配套的小学，以方便小区内居民的的孩子上学。但是为了节省开支，建造的学校要求尽量的少，为此，设备选定的16个校址提供参考，各校址覆盖的小区情况如表1所示： 1.2 问题一、求学校个数最少的建校方案，并用数学软件求解（说明你所使用的软件并写出输入指令）。 问题二、设每建一所小学的成本由固定成本和规模成本两部分组成，固定成本由学校所在地域以及基本规模学校基础设施成本构成，规模成本指学校规模超过基本规模时额外的建设成本，它与该学校学生数有关，同时与学校所处地域有关。设第i个备选校址的建校成本 c可表示为 i 长沙学院数学建模课程设计说明书 题目选址问题 系(部) 数学与计算机科学 专业(班级) 数学与应用数学 姓名 学号 指导教师 起止日期 2015、6、1——2015、6、5 课程设计任务书 课程名称：数学建模课程设计 设计题目：选址问题 已知技术参数和设计要求： 选址问题（难度系数1.0） 已知某地区的交通网络如下图所示，其中点代表居民小区，边代表公路，边上的数字为小区间公路距离（单位：千米），各个小区的人数如下表所示，问区中心医院应建在哪个小区，可使离医院最远的小区居民人均就诊时所走的路程最近？ 各阶段具体要求： 1．利用已学数学方法和计算机知识进行数学建模。 2．必须熟悉设计的各项内容和要求，明确课程设计的目的、方法和步骤。 3．设计中必须努力认真，独立地按质按量地完成每一阶段的设计任务。 4．设计中绝对禁止抄袭他人的设计成果。 5．每人在设计中必须遵守各组规定的统一设计时间及有关纪律。 6．所设计的程序必须满足实际使用要求，编译出可执行的程序。 7．要求程序结构简单，功能齐全，使用方便。 设计工作量： 论文：要求撰写不少于3000个文字的文档，详细说明具体要求。 1v 5 工作计划： 提前一周：分组、选题；明确需求分析、组内分工； 第一天：与指导老师讨论，确定需求、分工，并开始设计；第二~四天：建立模型并求解； 第五天：完成设计说明书，答辩； 第六天：针对答辩意见修改设计说明书，打印、上交。 注意事项 ?提交文档 长沙学院课程设计任务书（每学生1份） 长沙学院课程设计论文（每学生1份） 长沙学院课程设计鉴定表（每学生1份） 指导教师签名：日期： 教研室主任签名：日期： 系主任签名：日期： 第17讲应急设施的优化选址问题 问题（AMCM-86B题）里奥兰翘镇迄今还没有自己的应急设施。1986年该镇得到了建立两个应急设施的拨款，每个设施都把救护站、消防队和警察所合在一起。图17-1指出了1985年每个长方形街区发生应急事件的次数。在北边的L形状的区域是一个障碍，而在南边的长方形区域是一个有浅水池塘的公园。应急车辆驶过一条南北向的街道平均要花15秒，而通过一条东西向的街道平均花20秒。你的任务是确定这两个应急设施的位置，使得总响应时间最少。 图17-1 1985年里奥兰翘每个长方街区应急事件的数目（I）假定需求集中在每个街区的中心，而应急设施位于街角处。 （II）假定需求是沿包围每个街区的街道上平均分布的，而应急设施可位于街道的任何地方。 §1 若干假设 1、图17-1所标出的1985年每个长方形街区应急事件的次数具有典型代表性，能够反映该街区应急事件出现的概率的大小。 2、应急车辆的响应时间只考虑在街道上行驶时间，其他因纱（如转弯时间等）可以忽略不计。 3、两个应急设施的功能完全相同。在应急事件出现时，只要从离事件发生地点最近的应急设施派出应急车辆即可。 4、执行任何一次应急任务的车辆都从某一个应急设施出发，完成任务后回到原设施。不出现从一个应急事件点直接到另一事件点的情况。（这是因为，每一个地点发生事件的概率都很小，两个地点同时发生事故的概率就更是小得可以忽略不计）。 §2 假定（I ）下的模 在假定（I ）下，应急需求集中在每个街区中心。我们可以进一步假定应急车辆只要到达该街区四个街角中最近的一个，就认为到达了该街区，可以开始工作了。按假定（I ），每个应急设施选在街角处，可能的位置只有6×11=66个。两个应急设施的位置的可能的组合至多只有66×65/2=2145个。这个数目对计算机来说并不大，可用计算机进行穷举，对每种组合一一算出所对应的总响应时间，依次比较得出最小的响应时间及对应的选址方案。具体算法是： 建立直角坐标系，以该镇的西北角为原点，从北到南为X -轴正方向，从西到东为Y -轴正方向，在南北、东西方向上分别以一个街区的长作为单位长，则街角的坐标),(Y X 是满足条件50,100≤≤≤≤Y X 的整数。而每个街区中心的坐标具有形式)5.0,5.0(++j i ，其中j i ,是满足条件：40,90≤≤≤≤j i 的整数。如果不考虑障碍和水塘的影响，同应急车辆从设在),(Y X 点的应急设施到以)5.0,5.0(++j i 为中心的街区的行驶时间等于 )5.05.0(20)5.05.0(15),,,(---+---=j Y i X j i Y X t )5.17)5.0(20)5.0((15-+-++-=j Y i X 秒 记),(j i p 为以)5.0,5.0(++j i 为中心的街区的事故发生频率（即在图上该街区所标的数字）。如果应急设施设在),(),,(2211Y X Y X 这两点，总不妨设21X X ≤，则该设置方案的总响应时间为 ),,,(2211Y X Y X T ∑∑===904 02211)},,,(),,,,(min{),(i j j i Y X t j i Y X t j i p 让1X 取遍0—10，2X 取遍101-X ，21,Y Y 分别独立地取遍0—4。依次对四数组),,,(2211Y X Y X 的每一个值算出对应的总响应时间的最小值及对应的四数组。 以上算法不难用计算机编程实现。由于数组的个数不算多（只有两千多个），计算机可很快得出答案。答案是： 两个应急设施分别设在点（2，3），（6，3）时最优。 这是在不考虑L 形障碍区域和水塘的影响的假定下得出的最优解，但从这两个点到 机场选址问题 摘要 针对机场选址问题，文章共建立了三个模型用以解决该类问题。为了计算出任意两城市之间的距离，我们利用公式（1）将利用题目中所给的大地坐标得出了任意两点之间的距离，见附录2。 对于问题1，我们主要利用0-1变量法，从而对问题进行了简化。我们设了第i个 y以及第i个城市是否是以第j个支线机场为最近机场的()j i x,。城市是否建支线机场的 i 然后将任意两点之间的距离与该城市的总人数之积，再乘以0-1变量()j i x,，最后得出每一个所有城市到最近机场的距离与该城市人口的乘积，然后利用LINGO进行编写程序，进行最优化求解，最后得出的结果见表1和表2，各大城市以及支线机场的分布见图2。 对于问题2，该问题是属于多目标规划的问题，目标一是居民距离最近机场的距离最短，目标二是每个机场覆盖人口数尽可能相等。我们在第一题的基础上，又假设了一些正、负偏差变量，对多个目标函数设立优先级，把目标函数转化为约束条件，进而求得满足题目要求的结果。 对于问题3，我们分析到影响客流量的因素是GDP跟居民人数，所以通过所搜集的资料分析我们给予这两个因素以不同的权重。然后同样采取问题2中所给的反求机场覆盖的方法，求的各个机场所覆盖的客流量，再让其在平均客流量水平上下浮动。通过LINGO程序的运行得到的六个机场的坐标见表6，六个机场的分布见图7。 针对论文的实际情况，对论文的优缺点做了评价，文章最后还给出了其他的改进方向，以用于指导实际应用。 关键词：选址问题；多目标规划；LINGO；0-1变量法；加权 1．问题的重述 近年来，随着我国经济社会的迅猛发展，公共交通基础设施日趋需要进一步完善与提高。支线机场作为我国交通运输体系的有机组成部分，对促进欠发达地区经济社会的发展具有基础性的作用。现某区域有30个城市，本区域计划在未来的五年里拟建6个支线机场。 任务1，确定6个支线机场的所在城市，建立居民到最近机场之间的平均距离最小的数学模型。 任务2，在任务一基础上，确定6个支线机场的所在城市，建立使得每个支线机场所覆盖的居民人数尽可能均衡的数学模型。 任务3，在任务一基础上，根据近一年每个城市的GDP 情况，确定6个支线机场的所在城市，建立使得每个支线机场的客流量尽量均衡的数学模型。 2．问题的分析 2．1 问题1 题目要求是建立居民到最近机场之间的平均距离最小的数学模型，该问题其实就是利用的0-1变量建立的模型。首先我们设两个0-1变量，一个是控制某个城市是否为支线机场的i y ，一个是控制某个城市的最近机场是哪一个的ij x 。针对于上述两个0-1变量，我们分别设立了约束条件。同时又为了满足问题所要求的使局面平均距离最小，我们将某一个城市到离它最近的机场的距离与该城市的人口乘积作为目标函数，在LINGO 软件中，通过设立一约束条件，最后将目标函数进行最优化求解。 2．2 问题2 该问题可以归结为多元目标线性规划的问题，所以我们在第一问的基础上又增加了一个目标函数，最后利用加权的方法将两个目标函数转化成了一个目标函数，将另一个目标函数作为约束条件。同时我们又引入了正负偏差变量，通过控制该变量达到覆盖居民人数均衡以及居民到城市之间的平均距离尽量小。 2．3 问题3 该问题要求的是客流量尽量均衡，经过分析可以知道，城市的GDP 越高，说明该城市经济越繁荣，货币流通越快，从而反映出客流量越大。另一方面城市越大、人口越多，也在一定程度上反映出了该城市客流量越大。基于上述两点，我们对GDP 跟城市人口分别给予了不同的权重来反映其对客流量的影响大小。按照第二问的方法，我们依然利用多元目标线性规划的只是进行求解。通过LINGO 编写程序，最中求得可行解。 投资的收益与风险问题 摘要 对市场上的多种风险资产和一种无风险资产（存银行）进行组合投资策略的设计需要考虑两个目标：总体收益尽可能大和总体风险尽可能小，而这两个目标在一定意义上是对立的。 本文我们建立了投资收益与风险的双目标优化模型，并通过“最大化策略”，即控制风险使收益最大，将原模型简化为单目标的线性规划模型一；在保证一定收益水平下，以风险最小为目标，将原模型简化为了极小极大规划模型二；以及引入收益——风险偏好系数，将两目标加权，化原模型为单目标非线性模型模型三。然后分别使用Matlab的内部函数linprog，fminmax，fmincon对不同的风险水平，收益水平，以及偏好系数求解三个模型。 关键词：组合投资，两目标优化模型，风险偏好 2.问题重述与分析 3.市场上有种资产（如股票、债券、…）()供投资者选择，某公司有数额为的 一笔相当大的资金可用作一个时期的投资。公司财务分析人员对这种资产进行了评估，估算出在这一时期内购买的平均收益率为，并预测出购买的风险损失率为。考虑到投资越分散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的中最大的一个风险来度量。 购买要付交易费，费率为，并且当购买额不超过给定值时，交易费按购买计算（不买当然无须付费）。另外，假定同期银行存款利率是, 且既无交易费又无风险。（） 1、已知时的相关数据如下： 试给该公司设计一种投资组合方案，即用给定的资金，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总体风险尽可能小。 2、试就一般情况对以上问题进行讨论，并利用以下数据进行计算。 本题需要我们设计一种投资组合方案，使收益尽可能大，而风险尽可能小。并给出对应的盈亏数据，以及一般情况的讨论。 这是一个优化问题，要决策的是每种资产的投资额，要达到目标包括两方面的要求:净收益最大和总风险最低，即本题是一个双优化的问题，一般情况下，这两个目标是矛盾的，因为净收益越大则风险也会随着增加，反之也是一样的，所以，我们很难或者不可能提出同时满足这两个目标的决策方案，我们只能做到的是：在收益一定的情况下，使得风险最小的决策，或者在风险一定的情况下，使得净收益最大，或者在收益和风险按确定好的偏好比例的情况下设计出最好的决策方案，这 选址问题数学模型 摘要 本题是用图论与算法结合的数学模型，来解决居民各社区生活中存在三个的问题：合理的建立3个煤气缴费站的问题；如何建立合理的派出所；市领导人巡视路线最佳安排方案的问题。通过对原型进行初步分析，分清各个要素及求解目标，理出它们之间的联系.在用图论模型描述研究对象时，为了突出与求解目标息息相关的要素，降低思考的复杂度。对客观事物进行抽象、化简，并用图来描述事物特征及内在联系的过程.建立图论模型是为了简化问题，突出要点，以便更深入地研究问题 针对问题1：0-1规划的穷举法模型。该模型首先采用改善的Floyd-Warshall 算法计算出城市间最短路径矩阵见附录表一；然后，用0-1规划的穷举法获得模型目标函数的最优解，其煤气缴费站设置点分别在Q、W、M社区，各社区居民缴费区域见表7-1，居民与最近的缴费点之间平均距离的最小值11.7118百米。 针对问题2：为避免资源的浪费，且满足条件，建立了以最少分组数为目标函数的单目标最优化模型，用问题一中最短路径的Floyd算法，运用LINGO软件编程计算,得到个社区之间的最短距离，再经过计算可得到本问的派出所管辖范围是2.5千米。最后采用就近归组的搜索方法，逐步优化，最终得到最少需要设置3个派出所，其所在位置有三种方案，分别是：（1）K区，W区，D区；（2）K区，W区，R区；（3）K区，W区，Q区。最后根据效率和公平性和工作负荷考虑考虑，其第三种方案为最佳方案，故选择K区，W区，Q区，其各自管辖区域路线图如图8-1。 针对问题3：建立了双目标最优化模型。首先将问题三转化为三个售货员的最佳旅行售货员问题，得到以总路程最短和路程均衡度最小的目标函数，采用最短路径Floyd算法，并用MATLAB和LINGO软件编程计算，得到最优树图，然后按每块近似有相等总路程的标准将最优树分成三块，最后根据最小环路定理，得到三组巡视路程分别为11.8km、11km和12.5km，三组巡视的总路程达到35.3km，路程均衡度为12%,具体巡视路线安排见表9-1和图9.2 。 关键词Floyd-Warshall算法穷举法最小生成树最短路径 1问题重述 1.1问题背景 这是一个最优选址问题，是一种重要的长期决策，它的好坏直接影响到服务方法，服务质量，服务效率，服务成本，所以选址问题的研究有着重大的经济社 与最大、最小、最长、最短等等有关的问题都是优化问题。 解决优化问题形成管理科学的数学方法：运筹学。运筹学主要分支：（非）线性规划、动态规划、图与网络分析、存贮学、排队伦、对策论、决策论。 6.1 线性规划 1939年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》 1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论. 1. 问题 例1 作物种植安排 一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力1/2 1/3 1/4, 预计每亩产值分别为110元, 75元, 60元. 如何规划经营使经济效益最大. 分析：以取得最高的产值的方式达到收益最大的目标. 1. 求什么？分别安排多少亩地种蔬菜、棉花、水稻？ x 1亩、 x 2 亩、 x 3 亩 2. 优化什么？产值最大 max f=10x 1+75x 2 +60x 3 3. 限制条件？田地总量 x 1+x 2 +x 3 ≤ 50 劳力总数 1/2x 1 +1/3x 2 +1/4x 3 ≤ 20 模型I : 设决策变量：种植蔬菜x1亩, 棉花x2亩, 水稻x3亩， 求目标函数f=110x1+75x2+60x3 在约束条件x1+x2+x3≤ 50 1/2x1+1/3x2+1/4x3 ≤20 下的最大值 规划问题：求目标函数在约束条件下的最值, 规划问题包含3个组成要素: 决策变量、目标函数、约束条件。 当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题, 否则称为非线性规划问题。 2. 线性规划问题求解方法 称满足约束条件的向量为可行解,称可行解的集合为可行域, 称使目标函数达最值的可行解为最优解. 命题 1 线性规划问题的可行解集是凸集. 因为可行解集由线性不等式组的解构成。两个变量的线性规划问题的可行解集是平面上的凸多边形。 命题2 线性规划问题的最优解一定在可行解集的某个极点上达到. 图解法：解两个变量的线性规划问题，在平面上画出可行域，计算目标函数在各极点处的值，经比较后，取最值点为最优解。 命题 3 当两个变量的线性规划问题的目标函数取不同的目标值时，构成一族平行直线,目标值的大小描述了直线离原点的远近。 于是穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点即为取的极值的极点—最优解。 单纯形法: 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解集的极点中搜寻最优解. 正则模型: 决策变量: x 1,x 2 ,…,x n . 目标函数: Z=c 1 x 1 +c 2 x 2 +…+c n x n . 约束条件: a 11 x1+…+a1n x n≤b1, ……a m1x1+…+a mn x n≤b m, 模型的标准化 10. 引入松弛变量将不等式约束变为等式约束. 若有 a i1x 1 +…+a in x n ≤b i , 则引入 x n+i ≥ 0, 使得 a i1 x 1 +…+a in x n + x n+i =b i 若有 a j1x 1 +…+a jn x n ≥b j , 则引入 x n+j ≥ 0, 使得 a j1 x 1 +…+a jn x n - x n+j =b j . 数学建模物流配送中心 选址模型 文件管理序列号：[K8UY-K9IO69-O6M243-OL889-F88688] 物流配送中心选址模型 姓名：学号：班级： 摘要：在现代络中，配送中心不仅执行一般的职能，而且越来越多地执行指挥调度、信息处理、作业优化等神经中枢的职能，是整个络的灵魂所在。因此，发展现代化配送中心是现代业的发展方向。文章首先使用重心法计算出较为合适的备选地，再考虑到各项配送中心选址的固定成本和可变成本，从而使配送中心选址更加优化和符合实际。 关键词：物流选址；选址；重心法；优化模型； 1．背景介绍 1．1 研究主题 如下表中，有四个零售点的坐标和物资需求量，计算并确定物流节点的位置。 1.2 前人研究进展 1.2.1国内外的研究现状： 国外对物流配送选址问题的研究已有60余年的历史，对各种类型物流配送中心的选址问题在理论和实践方面都取得了令人注目的成就，形成了多种可行的模型和方法。归纳起来，这些配送中心选址方法可分为三类： （1）应用连续型模型选择地点； （2）应用离散型模型选择地点； （3）应用德尔菲（Delphi）专家咨询法选择地点。 第一类是以重心法为代表，认为物流中心的地点可以在平面取任意点，物流配送中心设置在重心点时，货物运送到个需求点的距离将最短。这种方法通常只是考虑运输成本对配送中心选址的影响，而运输成本一般是运输需求量、距离以及时间的函数，所以解析方法根据距离、需求量、时间或三者的结合，通过坐标上显示，以配送中心位置为因变量，用代数方法来求解配送中心的坐标。解析方法考虑影响因素较少，模型简单，主要适用于单个配送中心选址问题。解析方法的优点在于计算简单，数据容易搜集，易于理解。由于通常不需要对进行整体评估，所以在单一设施定位时应用解析方法简便易行。 第二类方法认为物流中心的各个选址地点是有限的几个场所，最适合的地址只能按照预定的目标从有限个可行点中选取。 第二类方法的中心思想则是将专家凭经验、专业知识做出的判断用数值形式表示，从而经过分析后对选址进行决策。 国内在物流中心选址方面的研究起步较晚，只有10余年历史，但也有许多学者对其进行了较深入的研究，在理论和实践上都取得了较大的成果。北方交通大学鲁晓春等对配送中心的重心法地址做出了深入的研究，认为原有的重心法存在着问题，并把原有的计算公式用流通费用偏微分方程来取代。中国矿业大学周梅 本科14组 许泽东，邹志翔，陈佳成 选址问题及最佳巡视路线的数学模型 摘 要 本文解决的问题是缴费站、派出所选址和最佳巡视路线的确定。合理设置缴费站，可以为居民缴费节省大量时间和精力。派出所位置和数量的不同选择，会产生不同的建设成本和管理经费。而最佳巡视路线的确立，可以让领导在最短时间内巡视完所有社区。为解决以上问题，我们建立的三个最优化模型。 针对问题一，我们先用floyd 算法求出各社区间的最短路，然后用计算机枚举出所有选址方案。对每一种选址方案都会产生一个平均距离S ，我们以此为指标对方案进行评估。经过合理化推导，我们得出最优解11712S .=（百米），且此时应该在M,Q,W 三社区设置煤气缴费站。 针对问题二，我们在问题一求出的最短路基础上，建立了0-1线性规划模型。然后借助matlab 软件求得最优解3=X （即应该设置3个派出所），并给出了各派出所管辖范围。这样既满足了每个社区在3分钟内至少能得到一个派出所服务，也为派出所的建设管理节省了不少成本。具体结果如下表3： 构建了社区网络的完全图，然后考虑到最优哈密顿圈的求解极其困难，我们连续使用30次模拟退火的方法求得连接各社区的近似最优哈密顿圈。其中，我们对每次求出的哈密顿圈都进行了合理划分，产生了三个子圈，即三组巡视路线。最终得到近似最优解128，见表4。接着，我们还对哈密顿圈划分方法进行了改进，求得近似最优解125（具体结果见表5）。 1.问题重述 问题背景 社区已是现代都市的的基础，随着城市社会经济的飞速发展，社区与人们生活的联系越来越密切，人们需要在社区解决日常生活涉及的各种利益和需要，因而人们对社区社会生活服务提出更高的要求，而政府也希望能够更好的指导和管理城市社区，社区生 典型问题 选址－分配问题 (Location Allocation Problem) 东北大学系统工程研究所 2014.09 选址－分配问题 ● 选址－分配(location-allocation) 问题 也称作多韦伯(multi-Weber ) 问题或P 中位(P-median )问题。 ● 单韦伯(single Weber)问题 在欧几里德空间上典型的单韦伯(single Weber) 问题是寻找一个位置，使从代表顾客位置的一些固定点到它的距离和最小。 ● 问题描述： 有m 个“设施”需要选址，n 个已知位置的“顾客”分配给不同的设施，每个顾客的需求为b j ，j =1,2,…,n ；每个设施具有的能力为a i ，i =1,2,…,m 我们需要找到 设施的位置（选址） 顾客对设施的分配 使顾客和服务他们的设施间的距离总和最小。 图形描述 m : 设施总数n : 顾客总数 F i : 第i 个设施,i =1,2,…,m C j : 第j 个顾客,j =1,2,…,n a i : 第i 个设施的能力b j : 第j 个顾客的需求 F i =(x i , y i ):设备i 的未知位置，决策变量C j =(u j , v j ):顾客j 的已知位置 C 3 C 1C n C 2 F 1F m (x 1, y 1) (u 1, v 1)b 1 a 1 (x m , y m ) (u n , v n )b n a m … 数学模型 n j m i z n j z z g m i a z b z g z C F t z F f ij m i ij j m i ij n j j i ij m i n j j i ,,2,1,,,2,11, or 0 ,,2,1,1)(,,2,1,)( t.s. ),(),( min 1 1 11 =======≤=?=∑∑∑∑=+== = C j F i (x i , y i ) b j a i (u j , v j ) …… 2 2) ()(),(j i j i j i v y u x C F t -+-=? 变量: z ij : 0-1 决策变量 z ij =1,顾客j 由设施i 服务；否则z ij =0F i = (x i , y i ) :设施i 的未知位置，决策变量 ? 参数： t (F i ,C j ): 由设施 i 到顾客j 的欧几里得距离。 保证不超过每个 设施的服务能力 保证每个顾客只由一个设施服务 数学建模学校选址问题 模型 GE GROUP system office room 【GEIHUA16H-GEIHUA GEIHUA8Q8- 学校选址问题 摘要 本文针对某地新开发的20个小区建设配套小学问题建立了0-1规划模型和优化模型。为问题一和问题二的求解，提供了理论依据。 模型一： 首先：根据目标要求，要建立最少学校的方案列出了目标函数： 然后：根据每个小区至少能被一所学校所覆盖，列出了20个约束条件; 最后：由列出的目标函数和约束函数，用matlab进行编程求解，从而得到，在每个小区至少被一所学校所覆盖时，建立学校最少的个数是四所，并且一共有22种方案。 模型二： 首先：从建校个数最少开始考虑建校总费用，在整个费用里面，主要是固定费用，由此在问题一以求解的条件下，进行初步筛选，得到方案1,4,8的固定成本最少。 然后：在初步得出成本费用最少时，对每个这三个方案进一步的求解，求出这三个方案的具体的总费用，并记下这三套方案中的最小费用。 其次：对这三套方案进行调整，调整的原则是：在保证每个小区有学校覆盖的条件下，用多个固定成本费用低的备选校址替换固定成本费用高的备选校址。在替换后，进行具体求解。 再次：比较各种方案的计算结果，从而的出了如下结论： 选用10,11,13,15,16号备选校址的选址方案，花费最少，最少花费为13378000元。 最后：对该模型做了灵敏度分析，模型的评价和推广。 关键字：最少建校个数最小花费固定成本规模成本灵敏度分析 1.问题重述 1.1问题背景： 某地新开发的20个小区内需要建设配套的小学，以方便小区内居民的的孩子上学。但是为了节省开支，建造的学校要求尽量的少，为此，设备选定的16个校址提供参考，各校址覆盖的小区情况如表1所示： 表1-1备选校址表 应急设施 摘要： 此问题属于最佳选址问题，要求服务设施到所有被服务点所用的时间最少，在此我们用MATLAB软件编程可求得。再通过分析因有障碍物的特殊情况。最终得到结果。 关键词： 问题重述： 某镇至今尚无应急设施，今得到一笔拨款用于建立一个应急设施，将消防队，医疗中心和警卫队合并在一处，已知去年各街区发生应急事件的次数如下表： 左边“L”形区域有一障碍，右边长方形区域有一浅水塘公园，应急车驶过南北向一个街区平均花15S，东西街区20S，问将应急设施建于何处使应急响应时间最短。 注：（1）阴影部份应急事件次数均为零 （2）应急事件集中在街区中心而应急设施在街角处 模型的假设： 1．在同一时刻各街区及街区内不会同时发生两件应急事件； 2．应急事件集中在街区中心，而应急设施在街角处； 3．障碍区及浅水塘应急事件次数为零。 模型的建立与求解： 在不考虑因故障物所造成的影响，通过以下程序找出在各街区建立应急措施的总反应时间。 MATLAB程序： X=[5,2,2,1,5,0,3,2,4,2; 2,3,3,3,3,4,1,3,0,4; 4,3,3,0,3,4,0,0,0,0; 1,2,0,0,4,3,2,2,0,1; 3,2,2,5,3,2,1,0,3,3]; t=0;t1=0; for m=1:5; for n=1:10; for i=1:5; for j=1:10; t1=( (abs(m-i))*20 + (abs(n-j))*15 + (15+20)/2 )*X(i,j); t=t+t1;t1=0; end end T(m,n)=t; t=0; end end 运行结果： T = 12405 11235 10425 9915 9675 9975 10665 11565 12675 13995 11285 10115 9305 8795 8555 8855 9545 10445 11555 12875 11205 10035 9225 8715 8475 8775 9465 10365 11475 12795 11805 10635 9825 9315 9075 9375 10065 10965 12075 13395 13005 11835 11025 10515 10275 10575 11265 12165 13275 14595 结果分析： 上面我们忽略了障碍物的影响，求出min T=8475，在此我们应把障碍的影响加入综合考虑，得出结果为min T=8555，即在b(2,5) 处建立应急设施。数学建模 学校选址问题模型
数学建模论文__物流与选址问题
数学建模学校选址问题
《数学建模》选题.
高速公路突发事件应急救援设施选址优化
数学建模 学校选址问题模型
数学建模报告选址问题
4.第17讲 应急设施的优化选址问题(数学建模)
机场选址问题数学建模论文
数学建模：投资问题
选址问题数学模型
数学建模中的优化问题与规划模型
数学建模物流配送中心选址模型
选址问题及最佳巡视路线的数学模型 (1)
典型优化问题的遗传算法求解— 选址分配问题
数学建模学校选址问题模型
应急设施模型
相关主题
文本预览