图3 易证,SA+SB+SC<AC+BC(注意SA+SC=SD)。 当n=4时,方法仍是用一新点E代替两原顶点C,D(△ECD成一正三角形),先求△ABE的 斯点S1,连SE交外接圆于S2,则S1和S2即为所求(图4)。同样若以新点E’代替A,C,则可另 得二个斯点,如此递归进行,可以求出任意个顶点的所有斯点。 S1.S2 图4 问题是图形数目太多(当n=7,S≤5,共有62370个图形),有人( Garey等)已证明最短网络 是NP- complete问题,因此n略大时,譬如n≥100,计算机就不能胜任,目前可做10个顶点的问 题 现在研究方向有二,其一是对具有特殊性质的点集构造斯坦纳树,如对正n边形顶点集合,当 n>5时,斯坦纳最小树即是最小生成树(详见,翁家丰,应用数学学报,2(1985)),其二是对一般 的集合构造次优树,即不一定最短但接近最短,通常以最小生成树为次优树,人们对点集A,定义 r(4)斯坦纳最小树长 最小生成树长 称厂=mfH为最小斯坦纳比例,猜测P=√,由正三角形的例子知p≤当2=086,曾 证得3<n<5时,p= 黄光明③证明了ρ≥0.8(1983年),钟金芳蓉和 Graham又宣布了 ρ=0.8241(计算机结果),已经很接近了。最近(2000年)我国运筹学家越民义证明了猜测为 真。替代结果,最坏情形増加13.4%的网络长,对随机情形只增加3% (II)作业时间的优化 作业时间的优化问题,象大规模工程、房屋建筑、产品开发设计、维修以及工厂的开工投产活 动等一次完成的规划项目,如果对完工时间要求很严(如附有罚款条件),那么采用网络分析,以缩 短工时,则具有特别重要的意义 运用网络来描述规划,制作进度表,可以有以下几方面的好处 1.有助于管理者系统的、全面的考虑规划,弄清程序,便于估计完成时间和找出可能的改进 方案,从而加快规划的实现。 2.能提供工程计划的简明概况,其形式便于有关部门进行评论和参考,从而便于汇集各方面 的意见,找出存在的问题和延误工程的原因。 3.对网络进行分析可找出关键路线,这就是网络中所需时间最长的一组活动。网络的解可以9 图 3 易证，SA＋SB＋SC<AC+BC（注意 SA＋SC＝SD）。 当 n＝4 时，方法仍是用一新点 E 代替两原顶点 C，D（△ECD 成一正三角形），先求△ABE 的 斯点 S1，连 S1E 交外接圆于 S2，则 S1 和 S2 即为所求（图 4）。同样若以新点 E 代替 A，C，则可另 得二个斯点，如此递归进行，可以求出任意个顶点的所有斯点。 A B D C E E 1 S 2 S 图 4 问题是图形数目太多（当 n S =  7, 5 ，共有 62370 个图形），有人（Garey 等）已证明最短网络 是 NP-complete 问题，因此 n 略大时，譬如 n 100 ，计算机就不能胜任，目前可做 10 个顶点的问 题。 现在研究方向有二，其一是对具有特殊性质的点集构造斯坦纳树，如对正 n 边形顶点集合，当 n>5 时，斯坦纳最小树即是最小生成树（详见，翁家丰，应用数学学报，2（1985）），其二是对一般 的集合构造次优树，即不一定最短但接近最短，通常以最小生成树为次优树，人们对点集 A，定义 r A( ) = 斯坦纳最小树长 最小生成树长 称 inf ( ) A ＝ r A 为最小斯坦纳比例，猜测 3 2  = ，由正三角形的例子知 3 0.866 2    ，曾 证得 3<n<5 时， 3 2  = ，黄光明[3]证明了   0.8 （1983 年），钟金芳蓉和 Graham 又宣布了  = 0.8241 （计算机结果），已经很接近了。最近（2000 年）我国运筹学家越民义[4]证明了猜测为 真。替代结果，最坏情形增加 13.4%的网络长，对随机情形只增加 3%。 （III）作业时间的优化 作业时间的优化问题，象大规模工程、房屋建筑、产品开发设计、维修以及工厂的开工投产活 动等一次完成的规划项目，如果对完工时间要求很严（如附有罚款条件），那么采用网络分析，以缩 短工时，则具有特别重要的意义。 运用网络来描述规划，制作进度表，可以有以下几方面的好处。 1． 有助于管理者系统的、全面的考虑规划，弄清程序，便于估计完成时间和找出可能的改进 方案，从而加快规划的实现。 2． 能提供工程计划的简明概况，其形式便于有关部门进行评论和参考，从而便于汇集各方面 的意见，找出存在的问题和延误工程的原因。 3． 对网络进行分析可找出关键路线，这就是网络中所需时间最长的一组活动。网络的解可以