多重分派问题

系统分析了多重分派问题的线性规划模型的性质和特点，得到一个直接求解多重分派问题的算法，利用该算法来求解古典题，无需要求完全二部图，特别是求解过程不会受到已化解的影响。     

城市配送车辆路径优化集束式算法的客户点归并策略

VRP问题的研究起步较早,求解方法也非常丰富,然而,面对客户规模庞大,交通网络复杂的多约束车辆优化调度问题,现有算法显得无能为力.为有效解决需求点规模庞大的城市配送车辆优化调度问题,提出一种新的两阶段启发式算法——集束式算法,采用"集中后分派,分派后扩展"的思想,对末梢客户和同路段客户进行客户点合并,从全局上降低搜索范围,并提出相关客户点归并算法.     

工作分派问题的一种模糊决策模型

针对一类流水线式的工作分派问题,建立了在赋模糊权的二部图中求解模糊最大最小匹配的数学模型,给出了该模型的一个有效算法,并利用模糊决策思想得到了优化此类工作分派问题的一种决策方法     

一类排序问题的最优解算法

文[1]讨论了将多个零件分派给多台机器加工的一类排序问题,对满足特定条件的分派给出使总花费时间最少的计算方法.但条件过于苛刻,本文讨论一般的排序问题的最优解算法.     

灰色分派问题及其应用

在分派问题中，总假设被分派工作的人（或机器等）做各项工作的效率（或所费时间）都是确定的值．但实际上．对于以往未做过的工作，或做过但情况变化较大的工作都难以定下确切的工作效率，而只能估计出一个大概的范围．这也就是说有些工作效率是有理灰数．我们把这一类分派问题称为灰色分派问题．木文给出了灰色分派问题有关定理的证明以及一个应用实例．     

最优分派的算法

设有 n 项工作,每项工作需要 k 个工人共同完成,现有 kn 个工人,他们每人做其中的任意一项工作,都有一定的效益,如何分派他们的工作,使总的效益最大?这就是最优分派问题.当 k=1时,Kuhn 和 Munkres 已给出一个好的算法,对于任意的自然数 k≥2,本文给出一个好的算法.     

P-枢纽航线网络设计问题的一种启发式算法

针对无容量限制的多重分派枢纽中位问题(UMApHMP),提出了一种基于禁忌搜索和最短路算法的新的启发式算法。利用CAB基准数据对该算法进行了验证,计算结果表明所提算法具有较强寻优能力和较快的求解效率。     

分派问题一种标号算法

文章采用一定技巧,把求最短路的Ｄｉｊｋｓｔｒａ算法用于求解分派问题,得到一种标号算法,计算复杂性仅为Ｏ（ｎ２）,比以往的算法减少了一个数量阶Ｏ（ｎ）。     

非平衡分派问题的次数序列算法

根据 [2 ]中的结论 ,得到一个利用顶点的次数向量求解非平衡分派问题的算法 ,该算法不受退化解的影响 ,且其复杂性为 O(n· m3 ) .     

求解运输问题的一种新算法

本文将求解分派问题的标号算法成功地用于运输问题,并证明其中的非负处理可以省略,从而把Dijk-stra算法扩展到可能出现负边权的运输问题。与通常方法比较,这种方法具有直观、简单、计算量少、及易于推广等优点;最后证明该算法是多项式的,计算复杂性仅为o(n3)(当m≤n时)。     

COMPUTING THE NEAREST BISYMMETRIC POSITIVE SEMIDEFINITE MATRIX UNDER THE SPECTRAL RESTRICTION

Let A and C denote real n × n matrices. Given real n-vectors x1, ... ,xm, m ≤ n, and a set of numbers L = {λ1,λ2,... ,λm}. We describe (I) the set (?) of all real n × n bisymmetric positive seidefinite matrices A such that Axi is the "best" approximate to λixi, i = 1,2,...,m in Frobenius norm and (II) the Y in set (?) which minimize Frobenius norm of ||C - Y||.An existence theorem of the solutions for Problem I and Problem II is given and the general expression of solutions for Problem I is derived. Some sufficient conditions under which Problem I and Problem II have an explicit solution is provided. A numerical algorithm of the solution for Problem II has been presented.     

双对称矩阵逆特征值问题解存在的条件

This paper discuss the following two problems:Problem I. Given . Find A,such thatAX=XA,where BSRn×n is the set of all n × n bisymmetric matrices.Problem II. Given Find A SE such that where SE is the solution set of Problem I,is the Frobenius norm.In this paper, the sufficient and necessary conditions under which SE is nonempty are obtained. The general form of SE has been given. Then expression of the solution A of Problem II is presented.     

关于具有最大路长限制的顺序二分树

本文给出了一个构造具有最大路长限制的最小价格顺序二分树的算法;引进了分界数的概念。并证明了关于分界数的基本定理,从而使算法的计算量同O(n~2L)成比例,文中还讨论了具有最大路长限制的Huffman树问题,给出相应的算法,计算量也为O(n²L)。     

Transgenetic algorithm for the Traveling Purchaser Problem

In this paper an evolutionary algorithm is presented for the Traveling Purchaser Problem, an important variation of the Traveling Salesman Problem. The evolutionary approach proposed in this paper is called transgenetic algorithm. It is inspired on two significant evolutionary driving forces: horizontal gene transfer and endosymbiosis. The performance of the algorithm proposed for the investigated problem is compared with other recent works presented in the literature. Computational experiments show that the proposed approach is very effective for the investigated problem with 17 and 9 new best solutions reported for capacitated and uncapacitated instances, respectively.     

An exact DSatur-based algorithm for the Equitable Coloring Problem

This paper describes an exact algorithm for the Equitable Coloring Problem, based on the well known DSatur algorithm for the classic Coloring Problem with new pruning rules specifically derived from the equity constraint. Computational experiences show that our algorithm is competitive with those known in literature.     

An exact algorithm for minimizing resource availability costs in project scheduling

A new exact algorithm that solves the Resource Availability Cost Problem (RACP) in project scheduling is shown to yield a significant improvement over the existing algorithm in the literature. The new algorithm consists of a hybrid method where an initial feasible solution is found heuristically. The branching scheme solves a Resource-Constrained Project Scheduling Problem (RCPSP) at each node where the resources of the RACP are fixed. The knowledge of previously solved RCPSPs is used to produce cuts in the search tree. A worst-case-performance theorem is established for this new algorithm. Experiments are performed on instances adapted from the PSPLIB database. The new algorithm can be used to minimize any resource availability cost problem once a procedure for the underlying resource-constrained problem is available.     

On Smale's 17th Problem: A Probabilistic Positive Solution

Smale's 17th Problem asks “Can a zero of n complex polynomial equations in n unknowns be found approximately, on the average [for a suitable probability measure on the space of inputs], in polynomial time with a uniform algorithm?” We present a uniform probabilistic algorithm for this problem and prove that its complexity is polynomial. We thus obtain a partial positive solution to Smale's 17th Problem.     

A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem

In this paper we consider the Cumulative Capacitated Vehicle Routing Problem (CCVRP), which is a variation of the well-known Capacitated Vehicle Routing Problem (CVRP). In this problem, the traditional objective of minimizing total distance or time traveled by the vehicles is replaced by minimizing the sum of arrival times at the customers. We propose a branch-and-cut-and-price algorithm for obtaining optimal solutions to the problem. To the best of our knowledge, this is the first published exact algorithm for the CCVRP. We present computational results based on a set of standard CVRP benchmarks and investigate the effect of modifying the number of vehicles available.     

线性流形上双对称阵逆特征值问题

１．引言 令Ｒ表示所有ｎ×ｍ阶实对称阵集合,Ｒ＝Ｒ,Ｒ表示Ｒ中秩为ｒ的子集; ＯＲ是ｎ阶正交阵之集; Ａ＋表示Ａ的Ｍｏｏｒｓ－ｐｅｎｒｏｓｅ广义逆;Ｉｋ表示ｋ阶单位阵; ＳＲ表示 ｎ×ｎ表示ｎ阶实对称阵的全体; Ｒ（Ａ）表示 Ａ的列空间; Ｎ（Ａ）表示 Ａ的零空间; ｒａｎｋ（Ａ）表示 Ａ的秩,对 Ａ＝（ａｉｊ）, Ｂ＝（ｂｉｊ） Ｒ, Ａ＊ Ｂ表示 Ａ与 Ｂ的 Ｈａｄａｍａｒｄ乘积,其定义为 Ａ＊ Ｂ＝（ａｉｊ　ｂｉｊ）,并且定义 Ａ与 Ｂ的内积为（Ａ,Ｂ）＝ｔ,（ＢＡ）,由此内积导出的范数为（Ａ,Ａ）＝（ｔ,（Ａ…