共查询到19条相似文献,搜索用时 62 毫秒
1.
2.
本文针对同一机场中同机型的多架飞机受到干扰后, 飞机路径恢复的多目标最优化问题进行研究。首先根据航空公司实际航班调整的常用原则和航班干扰管理的基本思想, 基于连接网络建立多目标规划模型, 其中两个目标按照优先级排列:第一个目标为最小化航班的最大延误时间, 第二个目标为最小化参与交换的飞机数量。然后根据该问题的航班波结构特点, 结合求解多目标规划的分层序列法, 分析优化问题的若干最优性质, 并基于快速排序算法和最小费用路算法设计出多项式算法。最后用算例验证了算法的有效性。该研究结果可以为航空公司减少航班延误提供理论和技术支持。 相似文献
3.
4.
不可恢复道路堵塞路径选择问题及其算法 总被引:1,自引:0,他引:1
针对不可恢复道路堵塞的路径选择问题,分析了堵塞发生的不同起始时间对通过被堵塞边的费用(时间)产生的影响,这种影响引起的后效性使得这个问题不适合用动态规划中逆序推算方法求解。本设计了一种算法(MDA),对经典的Dijkstra算法中的权值计算进行了修正,证明了算法的复杂性为O(n^2),并用该算法对模型进行了求解。最后通过一个算例分析,对算法进行了验证。 相似文献
5.
6.
本文从代数及组合两个方面论证了NP完全问题存在多项式时间算法 .以往利用线性规划 (LP)技术来分析NP完全问题中的TSP问题 ,因其存在子环游问题 ,从而使问题得不到有效解决 .文中发展一分层网络 ,在求解TSP问题时 ,存在另一类(不完全 )子环游问题 .但两模型允许解集的交集避免了两类子环游基本可行解 ,从而使TSP问题可利用LP技术多项式时间内得以解决 ,同时给出了求哈密尔顿回路的多项式标记证明方法 ,开创了NPC问题研究的新局面 . 相似文献
7.
讨论下列数学模型Ⅰ:求x=(x_1,x_2,…,x_n)适合条件{■a_(ij)x_j≥b_i (i=1,2,…,m) x_j≥0且整数(j=1,2,…,n)使f(x)■{c_jx_j}达到最小值,其中m<n,a_(ij),b_i及c_j均为正整数。对该模型,建立了两个多项式算法,其复杂度均为O(n~2),并列举了一个数值例子. 相似文献
8.
为了提高经济领域统计数据的预测精度,代数多项式预测模型的建模方法应运而生.该方法使用代数多项式模型拟合给定的经济统计数据,并使用递推最小二乘法(RLS)对多项式拟合模型的加权系数进行递推计算以获得最优模型参数,然后通过获得的最优多项式模型计算未来预测数据.文章以实际统计的经济数据为例进行了仿真计算,研究结果表明,该方法不仅能实现统计数据的高精度拟合,而且具有很好的预测能力,在经济领域具有广阔的应用前景. 相似文献
9.
10.
求解车辆路径问题的免疫算法 总被引:1,自引:0,他引:1
将免疫算法用于求解车辆路径问题,并根据车辆路径问题的具体情况提出了一种基于分组匹配的亲和力计算方法.实验结果表明,免疫算法能有效地应用于车辆路径问题. 相似文献
11.
Anand Srivastav Hartmut Schroeter Christoph Michel 《Annals of Operations Research》2001,107(1-4):321-338
In this paper we study the problem of finding placement tours for pick-and-place robots, also known as the printed circuit board assembly problem with m positions on a board, n bins containing m components and n locations for the bins. In the standard model where the working time of the robot is proportional to the distances travelled, the general problem appears as a combination of the travelling salesman problem and the matching problem, and for m=n we have an Euclidean, bipartite travelling salesman problem. We give a polynomial-time algorithm which achieves an approximation guarantee of 3+. An important special instance of the problem is the case of a fixed assignment of bins to bin-locations. This appears as a special case of a bipartite TSP satisfying the quadrangle inequality and given some fixed matching arcs. We obtain a 1.8 factor approximation with the stacker crane algorithm of Frederikson, Hecht and Kim. For the general bipartite case we also show a 2.0 factor approximation algorithm which is based on a new insertion technique for bipartite TSPs with quadrangle inequality. Implementations and experiments on real-world as well as random point configurations conclude this paper. 相似文献
12.
13.
研究机场终端区进离港航班排序优化问题,对于提高跑道利用率以及降低航班延误损失具有重要意义。本文首先考虑航班运行方式(降落和起飞)、飞机类型以及航班的重要程度(航程是否连续)的不同所造成延误损失的不同,设计三维优先级表反映调度优先等级,并将其转化为延误成本系数。其次,为实现调度的公平性和减轻管制人员的工作负荷,设置允许延误的航班架次约束、邻边约束以及最大限制位置约束。再次,以最小化航班总延误成本为目标建立模型,提出相应的改进蚁群算法(GJAC)进行求解。最后通过数值实验验证所提算法在考虑调度优先等级及上述约束条件的同时能有效减少进离港航班队列的总延误成本。 相似文献
14.
Given ann × n matrixM and ann-dimensional vectorq, the problem of findingn-dimensional vectorsx andy satisfyingy = Mx + q, x 0,y 0,x
i
y
i
= 0 (i = 1, 2,,n) is known as a linear complementarity problem. Under the assumption thatM is positive semidefinite, this paper presents an algorithm that solves the problem in O(n
3
L) arithmetic operations by tracing the path of centers,{(x, y) S: x
i
y
i
= (i = 1, 2,,n) for some > 0} of the feasible regionS = {(x, y) 0:y = Mx + q}, whereL denotes the size of the input data of the problem. 相似文献
15.
一个积和式计数公式的等价形式及其证明 总被引:1,自引:0,他引:1
扈生彪 《数学的实践与认识》2002,32(3):483-485
给出了一个积和式计数公式在图论意义下的一般表达式 ,并证明了它们之间的等价关系 相似文献
16.
17.
Let G be a plane bipartite graph and M(G) the set of perfect matchings of G. The Z-transformation graph of G is defined as a graph on M(G): M,MM(G) are joined by an edge if and only if they differ only in one cycle that is the boundary of an inner face of G. A property that a certain orientation of the Z-transformation graph of G is acyclic implies a partially ordered relation on M(G). An equivalent definition of the poset M(G) is discussed in detail. If G is elementary, the following main results are obtained in this article: the poset M(G) is a finite distributive lattice, and its Hasse diagram is isomorphic to the Z-transformation digraph of G. Further, a distributive lattice structure is established on the set of perfect matchings of any plane bipartite graph. 相似文献
18.
This paper presents an infeasible-interior-point algorithm for a class of nonmonotone complementarity problems, and analyses its convergence and computational complexity. The results indicate that the proposed algorithm is a polynomial-time one. 相似文献
19.
针对传统排课方法排课效率低、成功率低、冲突率高等无法满足现代高校教务管理要求的现状,提出一种基于离散型荧火虫算法的智能排课模型.首先,根据教师、班级、课程、教室及授课时间要求建立一个多目标、多约束的排课数学模型,采用二分图完美匹配操作初始可行排课方案;然后,利用离散型荧火虫优化算法在可行方案中寻找最优排课方案;最后,通过Matlab仿真实验验证其可行性与有效性. 相似文献