这里仅介绍最短路问题和最小生成树问题，可用破圈法求解最小生成树问题，破圈算法具体如下：
（1） 在给定的赋权的连通图（若不是连通图，则不存在生成树）上任找一个圈；
（2） 在所找的圈中去掉一条权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）；
（3） 如果所余下的图已不含圈，则算法结束，余下的图即为最小生成树.否则返回步骤（1）.
下面通过一个例子来说明破圈法求解最小生成树问题的具体过程.
例9某大学准备对所属的7个二级学院办公室进行计算机联网，这个网络的可能连通的途径如图52图G所示.图中v1,…,v7表示7个二级学院的办公室，图中的边为可能联网的途径，边上的数值为这条路线所需的网线长度（单位：百米）.请设计一个网络能连通这7个办公室，并且使总的网线长度最短.
图52
解：此问题实际上是求图中G的最小生成树.我们采用破圈法，具体求解过程如下：
（1） 在图G中任找一个圈（v1,v6,v7,v1），此圈的边[v1,v6]的权数??16=10为最大，去掉边[v1,v6]，得图52中的图G1；
（2） 在图G1中任找一个圈（v3,v4,v5,v7,v3），此圈的边[v4,v5]的权数??45=8为最大，去掉边[v4,v5]，得图52中的图G2；
（3） 在图G2中任找一个圈（v2,v3,v5,v7,v2），此圈的边[v5,v7]的权数??57=5为最大，去掉边[v5,v7]，得图52中的图G3；
（4） 在图G3中任找一个圈（v3,v5,v6,v7,v3），此圈的边[v3,v7],[v5,v6]的权数??37=??56=5为最大，去掉边[v5,v6]（或去掉边[v3,v7]），得图52中的图G4；
（5） 在图G4中只有一个圈（v2,v3,v7,v2），此圈的边[v3,v7]的权数??37=4为最大，去掉边[v3,v7]，得图52中的图G5；
（6） 在图G5中已无圈，破圈法结束.可知图G5即为图G的最小生成树，总权数等于19.因此该大学可按图52中的图G5设计计算机网络，且所需网线长度最短为19百米.
上面我们讨论了从赋权的无向图中寻找最小生成树的问题，同样，也可以对赋权的有向图做类似的讨论.
对图D=（V,A）的每一条弧（vi,vj）赋予相应的一个数cij，称这样的图D为赋权图，cij称为弧（vi,vj）上的权.如果我们在赋权的有向图D=（V,A）中指定了一点（称为发点，记为vs），指定另一点（称为收点，记为vt），其余的点称为中间点，并把D中的每一条弧（vi,vj）的权数cij称为弧的容量，则又把这样的赋权有向图称为网络.
最短路问题是对一个赋权的有向图D中指定的两个点vs和vt，找到一条从vs到vt的路P，使得路P上所有弧的权数之和最小，这样的路P称为从vs到vt的最短路，最短路上所有弧的权数之和称为从vs到vt的距离.显然图D中从vs到vt的距离与从vt到vs的距离不一定相等.
当图D中的每条弧的权数cij≥时，可用Dijkstra算法求解从vs到vt的最短路.Dijkstra算法是目前公认最好的方法，又称双标号法.所谓双标号，就是对图中点vj规定两个标号（lj,kj），lj用以表示从vs到vt的最短路的距离，kj用以表示从vs到vt的最短路P上vj前面一个零点的标号.此算法是由Dijkstra于1959年提出来的，其基本思想是：
（1） 给出发点vs标号（0,s），表示从vs到vs的距离为0，vs为出发点；
（2） 找出已标号的点的集合I、没标号的点的集合J以及弧的集合{（vi,vj）|vi∈I,vj∈J}；
（3） 如果上述弧的集合是空集，则算法结束.此时有两种情况：如果vt已标号（lt,kt），则从vs到vt的距离即为lt，而从vs到vt的最短路，可以从vt反向追踪到发点vs而得到.如果vt未标号，则不存在从vs到vt的（有向）路.
如果上述弧的集合不是空集，转到第（4）步；
（4） 对上述弧的集合中的每一条弧，计算sij=li+cij，找出sij值最小的弧，不妨设为（vc,vd），给此弧的终点以双标号（scd,c），返回第（2）步.
注意，在第（4）步中，若sij值最小的弧有多条，则既可以任选一条弧的终点进行标号，也可以都予以标号；若这些弧中的有些弧的终点为同一点，则此点应有多个双标号，以便最后可找到多条最短路.
例10求图53（a）中v1到v6的最短路.
解：（1）给出发点v1标号（0,s），表示从v1到v1的距离为0，v1为出发点；
（2） 已标号点的集合I={v1}，未标号点的集合J={v2,v3,v4,v5,v6}，弧集合为{（v1,v2）,（v1,v3）,（v1,v4）}，并有s12=l1+c12=0+3=3，s13=0+c13=2，s14=0+c14=5，min（s12,s13,s14）=s13=3.给弧（v1,v3）的终点v3标号（2,1）（如图53（b）所示），表示从v1到v3的距离为2，从v1到v3的最短路中v3的前面一个点是v1；
（3） 此时I={v1,v3}，J={v2,v4,v5,v6}，弧集合{（v1,v2）,（v1,v4）,（v3,v4）}，并有s34=l3+c34=2+1=3，min（s12,s14,s34）=s12=s34=3.给弧（v1,v2）的终点v2标号（3,1），给弧（v3,v4）的终点v4标号（3,3）；
图53
（4） 此时I={v1,v2,v3,v4}，J={v5,v6}，弧集合{（v2,v6）,（v4,v6）}，并有s26=l2+c26=3+7=10，s46=l4+c46=3+5=8，min（s26,s46）=s46=8.给弧（v4,v6）的终点v6标号（8,4）；
（5） 此时I={v1,v2,v3,v4,v6}，J={v5}，弧集合为??，Dijkstra算法结束.
根据收点v6的标号（8,4）知从v1到v6的距离是8；从v1到v6的最短路P中v6前面的一点是v4.从v4的标号（3,3）知v4前面的一点是v3，从v3的标号（2,1）知v3前面的一点是v1，因此从v1到v6的最短路P为v1→v3→v4→v6.
事实上，根据图53（b）中各点的标号，我们可以得到从v1到图中各点vi的距离及从v1到各点vi的最短路.由于v5没有标号，因此不存在从v1到v5的（有向）路.
如果把无向图G=（V,A）的每一条边[vi,vj]都用方向相反的两条弧（vi,vj）和（vj,vi）代替，那么无向图G可看作是一个特殊的有向图.这样，我们就也可以用Dijkstra算法来求无向图的最短路（链）问题，只需在Dijkstra算法中把弧集合{（vi,vj）|vi∈I,vj∈J}改成边集合{[vi,vj]|vi∈I,vj∈J}即可.注意弧是有方向的，而边是无方向的.
例11燃气公司准备在甲、乙两地沿公路铺设一条输气管道，问如何架设可使管道长度最短？图54给出了甲、乙两地间的交通图，图中的点v1,v2,…,v7表示7个地名，v1为甲地，v7为乙地，点之间的连线表示两地之间的公路，边的权数表示两地间公路的长度（单位：km）.
图54
解：因为公路的距离与方向无关，所以两地间的输气管道最短或公路距离最短是一个无向图的最短路问题.使用Dijkstra算法，具体过程如下：
（1） 给发点v1标号（0,s）；
（2） 已标号点的集合I={v1}，未标号点的集合J={v2,v3,v4,v5,v6,v7}，边集合为{[v1,v2],[v1,v3]}，并有s12=l1+c12=0+15=15，s13=l1+c13=0+10=10，min（s12,s13）=s13=10.给边[v1,v3]的点v3标号（10,1），表示从v1到v3的距离为10，从v1到v3的最短路中v3的前面一个点是v1；
（3） 此时I={v1,v3}，J={v2,v4,v5,v6,v7}，边集合{[v1,v2],[v3,v2],[v3,v5]}，并有s32=l3+c32=10+3=13，s35=l3+c35=10+4=14，min（s12,s32,s35）=s32=13.给边[v3,v2]的点v2标号（13,3）；
（4） 此时I={v1,v2,v3}，J={v4,v5,v6,v7}，边集合{[v2,v4],[v2,v7],[v3,v5]}，并有s24=l2+c24=13+6=19，s27=l2+c27=13+17=30，min（s24,s27,s35）=s35=14.给边[v3,v5]的点v5标号（14,3）；
（5） 此时I={v1,v2,v3,v5}，J={v4,v6,v7}，边集合{[v2,v4],[v2,v7],[v5,v4],[v5,v6]}，并有s54=l5+c54=14+4=18，s56=l5+c56=14+2=16，min（s24,s27,s54,s56）=s56=16.给边[v5,v6]的点v6标号（16,5）；
（6） 此时I={v1,v2,v3,v5,v6}，J={v4,v7}，边集合{[v2,v4],[v2,v7],[v5,v4],[v6,v7]}，并有s67=l6+c67=16+6=22，min（s24,s27,s54,s67）=s54=18.给边[v5,v4]的点v4标号（18,5）；
（7） 此时I={v1,v2,v3,v4,v5,v6}，J={v7}，边集合{[v2,v7],[v4,v7],[v6,v7]}，并有s47=l4+c47=18+5=23，min（s27,s27,s67）=s67=22.给边[v6,v7]的点v7标号（22,6）；
（8） 此时I={v1,v2,v3,v4,v5,v6,v7}，J=??，算法结束.
根据收点v7的标号（22,6）知从v1到v7的距离是22；从v1到v7的最短路P中v7前面的一点是v6，从v6的标号（16,5）知v6前面的一点是v5，从v5的标号（14,3）知v5前面的一点是v3，从v3的标号（10,1）知v3前面的一点是v1，因此从v1到v7的最短路P为v1→v3→v5→v6→v7.从而，燃气公司应该按照v1→v3→v5→v6→v7沿公路铺设输气管道.
习题五
1. 某医院24小时内需要的护士数如下：2：00~6：00 10人，6：00~10：00 15人，10：00~14：00 25人，14：00~18：00 20人，18：00~22：00 18人，
22：00~2：00 12人，护士分别在2：00，6：00，10：00，14：00，18：00，22：00分6批上班，并连续工作8小时，试确定：医院至少应设多少名护士，才能满足值班需要.
2. 求下列各图的最小生成树.
3. 求下图所示网络中从v1到其他各点的最短路.
4. 有四个工人，要指派他们分别完成A、B、C、D四项工作，每人做每项工作所消耗的时间如下表，请设计一套方案，使总的消耗时间最少？
ABCD
甲919311
乙3593
丙33815
丁133137
5. 某人有一笔30万元的资金，在今后三年内有下列投资项目：
（1） 三年内的每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年投资；
（2） 只允许第一年年初投入，到第二年末能可收回，本利合计为投资额的150%，但规定最大投资额不超过15万元；
（3） 于三年内第二年初允许投资，可于第三年末收回，本利合计为投资额的160%，但规定最大投资额不超过20万元；
（4） 于三年内第三年初允许投资，一年收回，可获利40%，但规定最大投资额不超过10万元，为该人确定一个使第三年末本利总额为最大的投资方案.
第六章统计类模型
第六章统计类模型
对社会经济现象的研究，需要进行统计资料的调查、整理和分析，用以描述社会经济现象发展过程的数量变化和数量关系.不仅要研究它的过去和现在，而且还要根据现实的统计资料，采用科学的方法，预测其未来发展的趋势.本章将介绍统计预测的基本概念、种类和意义,让人们掌握统计预测的基本方法,能够使用简单的模型进行统计预测.