数学建模案例分析-- 图与网络方法建模3设备更新与中心选址

《数学建模案例分析-- 图与网络方法建模3设备更新与中心选址》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、§3设备更新与中心选址一、指定顶点对之间的最短路径算法对图每一条边都规定一个正实数与之对应，所得到的图称为赋权图，称为边的权。边上的权记成。对赋权图，，，中的一路称为最短路，如果它的各边的权和是中任一条一路中各边权和最小的。找寻最短路最有效的算法是Dijkstra算法：其主要思路是假定我们已经知道了在图中与起点有最短路径的个顶点以及从到这些顶点间的最短路径，然后求出第个顶点使之与前个顶点有相同的属性。其实现方法是比较法。对于每一个未着色的顶点，考虑所有已着色的顶点，从通过已着色的顶点到的不同路径中选出它们中的最短路径，从而也就确定了新染色的点和相应的最短路径，不断重复上

2、述过程直至求得从到的最短路径为止。算法步骤如下：1、最初，所有的边和顶点均未着色，对每一顶点指定一个数，表示从到且仅使用已着色顶点作为中间顶点的最短路径长度。2、令，并对所有，有，对顶点着色并令。3、对于每一个未着色顶点，重新定义如下：如果对于所有未着色的顶点，，则算法停止，因为此时从到任一未着色的顶点都没有路，也就不存在从到的路径。否则找出一个具有最小的值的顶点，对其着色并令。4、重复步骤3直到顶点已经着色时为止，算法终止。从到的最短路径已求出。例：用Dijkdtra算法求下图中从顶点到的最短路径。34278233321、对着色，令，且对其余顶点均有，.2、令，对所有

3、求解：由于最小，再对着色，并对边着色。由于未着色，继续上述步骤。3、令，比较与所有未着色的顶点。由于最小，所以首先对着色，并对边着色。由于未着色，继续上述步骤。4、令，比较还未着色的顶点。由于最小，所以首先对着色，并对边着色。由于未着色，继续上述步骤。5、令,继续比较有对顶点着色，并对边着色。6、令,计算最后对顶点着色和对边着色，形成从到的最短路，最短路径为8，由边组成最短路径。二、所有顶点间最短路径算法一个图中所有顶点间的最短路径算法是一个更具有普遍意义的问题。以下介绍（福劳德）提出的算法，其具体思路如下：对一个有个顶点的图，将顶点用个整数（从1到）进行编号。令表示从

4、顶点到的一条只允许前个顶点作为中间顶点时的最短距离。如果这样的路不存在，则。由此定义可知，表示从顶点到的边长度（如果没有这条边存在，则），显然。而就是我们所要求解的从到的最短路径距离。算法步骤如下：1、将图中各顶点编号为确定矩阵，如果顶点和之间有边相连，等于该边长度，否则，而。2、对，依次利用递归公式由已知的各元素确定的各元素值。每确定一个元素，可记下它所表示的路径，在算法终止时，不仅通过矩阵的各元素知道了各点间的最短距离，而且也知道了形成这条路径的各边的组成。例：对下图用算法求出各点间的最短路径长度。12721263534412的各元素和相应的最短路径计算如下：的第一

5、行和第一列元素与相同，对角线上的元素均为0，则需计算其余6个元素如下：由此可知采用类似的办法可求得矩阵为中各元素值就是要求解的相应顶点间的最短路径。三、应用举例在通信传输网中，要找出二点间信息传递具有最大可靠性的路径；在城市建设中，要设计出费用最小的交通运输干线；在交通运输中，希望选择一个最佳最经济的路线（距离最短或单位运价最低）等等。这些问题都等价于找一个图的最短路径问题。　例1　某单位使用一种设备，每年年初需对该设备是否更新作出决策。若换用新设备，就要支付一笔购置费用；若继续使用原设备，则要支付一定的维修费：设备使用的年数越长，每年的维修费就越大。若已知该单位在第一

6、年年初购进了一台新设备，该设备在五年内购买的价格和设备使用不同年限的维修费如表所示。问应如何制定设备更新计划，使单位五年内购置新设备的费用和维修旧设备的费用的总和最少？（年）12345购买价格i（万元）1111121213使用期(0,1](1,2](2,3](3,4](4,5]维修费用i（万元）5681118　　事实上，设备更新方案是很多的。例如每年年初均更新设备，这时五年内购买新设备的费用为11+11+12+12+13=59，而维修费用为5+5+5+5+5=25，总费用为59+25=84。如果五年内不更新设备，则其总的费用为11+5+6+8+11+18=59。如果穷举

7、各种情况，我们显然要花费太多的时间。为此，我们改用建立网络模型的最短路算法求解。建立网络模型如下：表示第年的年初，代表第五年末。边表示第年年初购买一台设备并一直使用到第年末（即第年初）。边的权表示第年年初购买这台设备的费用加上年里的设备维修费，即从而得网络如下图所示。v164122162230591841231717303123这样，制订一个最优的设备更新方案就等价于求从到的最短路。用狄克斯特拉算法求得最短路为或，即第1年、第3年购买的新设备，总费用为53，或第1年、第4年购买新设备，总费用亦为53。当然，从设备更新的角度考虑，第二种方案