具有次限制的最小树问题

F.Glover和D.Klingman在[2]中给出了予先确定的一个点x具有固定次数为k的最小树算法。 本文给出了任意m个互不关联点具有次数限制的最小树问题的算法.算法的基础是线性规划的对偶理论。     

关于有向图上的最小树形图——具等双回路特性的情况

如果我们要在某些城镇之间建立联系这些城镇的线路(例如电线等),假设线路的交叉点只能在代表这些城镇的点上,如何能使设立的线路总长度最短呢?这类问题在图论上叫无向图上的最小树问题。又如渠道设计中,有一个水源,要把水引到若干个点上,要求渠道的分叉点必须是在给定的点上,希望设计的渠道路线总长度最短。它和最小树问题的区别在于两点之问水流是有方向的,称谓有向图上的最小树形图问题。这些问题在理论上和实际应用中均有一定的意义。最小树形图和一类有向截集有对偶性的联系。寻求最小树的方法要点是,对每一点,在以其为顶点的所有边中选一条最短的,然后把由此产生的部分图中的每个连通片中收缩成一点,对新图重复上述步骤。求最小树形图时,对每一点取指向这个顶点的一条长度最短的弧。收缩时,不是收缩一个连通片,而只能收缩每个连通片中的一条回路。因此前者的收敛速度要比后者快。本文对于具有从无向图到有向图过渡性质的一类有向图提供了一个算法,寻求其最小树形图时,可以收缩一个连通片。     

关于拟阵的最小限制基问题

关于求拟阵的最小基问题,众所周知,有很简明的算法(被称为Greedy Algorithm)。本文考虑求带剖分限制的最小基问题,同样也给出了较简单的有效算法,最后举例说明,许多组合问题都可以化成拟阵的最小限制基问题而求解。     

变量有上界线性规划问题的对偶算法

1 基本概念 我们考虑如下的线性规划问题：~~     

线性规划的内点法

有解时,记它的最优解为x(v)。则x=x(v)定义了S_+中的一条曲线,称为规划(P)的“中心线”。 1984年,Karmarkar用对数函数为罚函数,把线性规划问题化为无约束最优化问题,然后,使用带投影变换的最速下降法求解,创造了一个新的线性规划多项式算法,从而掀起了深入研究“内点法”的热潮。Karmarkar算法的迭代次数为O(nL),计算复杂性为O(n~(3.5)L),其中L表示问题的数据输入计算机时的编码长度,在复杂性理论中,称为问题的规模。紧接     

线性规划问题的多项式算法

<正> 大家知道,用电子计算机解一个数学问题时,一个算法的好坏通常是用它的计算量、存储量等指标来衡量。在算法分析中,若以 L 表示某一数学问题的规模(例如变量的个数、方程的个数、初始数据写成二进制数码的长度等等),一个算法,如果它所需要的基本运算(如+、-、×、÷,比较等)的次数是 L 的多项式函数,我们就称这个算法是多项式算法.多     

网络上两类物资联合最大流问题的极流特征

当网络上(诸如交通网络、通讯网络)有多种不同物资或信息同时分别从相应的发点输送到相应的收点,要求每条线路上各类物资或信息的输送量总和不超过线路的容量时,寻求所有物资的最大输送量的问题,就是所谓网络多种物资的最大流问题,这个问题在生产实际和理论上都有着重要的意义,1963年T.C.Hu提出了求两类物资联合最大流的标号方法,但是为了保证有限步达到最大流,要求边的容量是偶数。 本文是文献[3]的继续,用图论的语言描述了两类物资最大流问题极流的特征,并对标号方法作了一点修改,使得有限步得到最大流,或者在某一步得到极流后,保证以后的迭代是从极流到极流.这样因极流的个数是有限的,并且最大流总可以在极流上达到,从而保证了有限步内得到所要求的最大流,无须对边的容量作任何限制, 本文所提的算法是使图形特征很强的标号算法和线性规划的极点迭代结合起来,这就使得有可能把这种方法,推广到更大的一类问题中,例如,研究容量的改变对最大流量的影响。     

交错链方法简介

组合最优化是研究各式各样的带组合性质的最优化问题的一门学科。在这门学科里,不同的问题往往用完全不同的办法来处理。虽然大家都很想建立一套系统的方法和理论,但是成果不多。这里我们主要是想介绍一类求解某些最优独立集问题的交错链方法。这是在组合最优化算法中,比较有系统的一部分。图论中极大部     

多面体组合

多面体组合的主要任务就是研究这种表示为整点凸包形式的多面体的不等式表示.假如能找出不等式表示,那么,整数规划就化为线性规划问题,从而可利用对偶定理来得到一些纯组合性的定理.     

关于Steiner最小树问题

在本刊第二卷第二期上,我们曾发表了黄光明的《最短网络》一文,对Steiner最小树问题在当时的发展情况作了一些介绍。最近由于他与堵丁柱共同解决了Gilbert和Pallak在1968年所提出的一个猜想,不少读者对于这一问题产生了兴趣。为此,我们组写了这篇文章,目的在于使读者对这一问题的历史和连带产生的问题以及目前的发展状况有一较确切的和较全面的了解。