一类弱支配集问题的近似算法

支配集问题和集合覆盖问题均是图论中的经典问题,尤其是集合覆盖问题,它的近似算法在许多其他问题中均有非常多的应用,如设施选址问题、服务器的安置问题等。本文研究了支配集问题和集合覆盖问题的关系,讨论了几个弱支配集问题和弱覆盖问题、弱集合覆盖问题等,给出完全支配集问题的近似比为Inn的近似算法,分析了弱完全支配集问题的不可近似比最小规模,讨论了集合击中问题和弱集合b-覆盖问题的最小规模,同时讨论了完全支配集问题、集合d-击中等问题的不可近似性。     

信息技术营造数学教育情景的通常策略

多媒体技术的应用给数学教学改革带来一片生机。多媒体起始课问题情境需要生活性,多媒体训练思维问题情境需要启发性,多媒体突破难点问题情境需要动态性,多媒体研究性问题情境需要启发性,多媒体实验问题情境需要探究性,多媒体课后探究问题情境需要趣味性。     

利用遗传算法求解圆排列问题

圆排列问题是一个典型的组合优化问题,也是一个NP完全问题.遗传算法是根据自然界生物学进化而发展起来的一种进化方法,其具有简单、易行、抽象性与鲁棒性特征,已成功地解决了许多工程优化问题.给出基于改进遗传算法给出求解圆排列问题的新方法.首先,分析了圆排列问题与旅行商问题之间的关系.然后,将圆排列问题转化为旅行商问题.接着,利用所给改进遗传算法进行了求解.最后,在仿真实验中,与已有算法进行了比较,结果表明,所给算法是一种能够简单有效地求解圆排列问题的新方法.     

过程间并发程序分析不可判定的一个新证明方法

过程间并发程序分析问题是一个不可判定问题,理解这个不可判定问题的来源是发展一个有效的分析算法的基础.现有的证明[1]通过构造三个并发任务的PCP问题实例,证明过程间并发程序分析是一个不可判定问题.利用反射的思想,仅仅用两个并发任务构造该问题的一个PCP问题实例,证明在两个并发任务的情况下,过程间并发程序分析是一个不可判定问题.     

板料优化排样问题

在材料加工领域,板料优化排样是实现薄板和厚板材料充分利用的一个常见问题。该问题是典型的NP完全问题,其求解过程复杂,求解耗时大,难以获得精确解。这不利于该问题的工程应用,为此,目前学术界提出了多种用于解决该问题的近似算法,求取在工程应用中可接受且耗时合理的优化排样方案。该文在对板料排样问题进行阐述的基础上,对近年来国内在板料优化排样问题方面所开展的研究进行了分析,对板料排样问题的发展前景进行了展望。     

Guided Local Search for Solving SAT and Weighted MAX-SAT Problems

In this paper, we show how Guided Local Search (GLS) can be applied to the SAT problem and show how the resulting algorithm can be naturally extended to solve the weighted MAX-SAT problem. GLS is a general, penalty-based meta-heuristic, which sits on top of local search algorithms to help guide them out of local minima. GLS has been shown to be successful in solving a number of practical real-life problems, such as the traveling salesman problem, BT"s workforce scheduling problem, the radio link frequency assignment problem, and the vehicle routing problem. We present empirical results of applying GLS to instances of the SAT problem from the DIMACS archive and also a small set of weighted MAX-SAT problem instances and compare them with the results of other local search algorithms for the SAT problem.     

基于列生成算法求解动态库存板坯分配问题

针对钢铁企业中遇到的动态库存板坯分配问题进行了研究。建立了一个0-1整数规划数学模型,该模型的目标是最小化板坯与合同规格差异费用以及板坯在库停留所产生的库存成本费用之和。根据问题特点,使用Danzig-Wolfe策略将这个模型分解为一个带有集划分约束的主问题和一个具有背包特征约束的价格子问题,开发了分支价格算法进行求解。计算结果表明所开发的分支价格算法能够最优求解生产实际问题。     

Computing near-optimal solutions for the dominating subset with minimal weight problem

In this work, we consider a combinatorial “dominating subset with minimal weight” problem, which is an associative problem for solving global optimization problem. This problem can be expressed as a kind of assignment problem. The mathematical model and the economical interpretations of the problem are given and its properties are described. Then, we propose a new algorithm which has a ratio bound in polynomial time, by using above properties for solving the problem and present the results of numerical experiments.     

在逐点状态约束下一个四阶线性系统的时间最优控制

在逐点状态约束下,最优控制问题的求解是很困难的,已有的最大值原理和形态规划理论很难用来求解在逐点状态约束下最优控制问题.本文讨论逐点状态约束下一个四阶线性系统的时间最优控制问题.我们采用转换的方法给出了最优时间与最优控制的具体表达式.     

A rigorous solution of the infinite time interval LQ problem with constant state tracking

A linear quadratic constant state tracking problem is considered over an infinite time horizon. It is shown that the solution cannot be obtained as a limit from a finite time horizon problem, as in general the limiting problem is ill-posed. To obtain a rigorous solution, the problem is split in two natural well-posed subproblems. One optimal control problem addresses the transient and the other optimal control problem concerns the steady state behavior. It is shown that the transient problem and the steady state problem are solved by the same control law.     

Constrained optimal control of switched systems based on modified BFGS algorithm and filled function method

In this paper, we consider an optimal control problem of switched systems with a continuous-time inequality constraint. Because of the complexity of this constraint, it is difficult to solve this problem by standard optimization techniques. To overcome this difficulty, the problem is divided into a bi-level optimization problem involving a combination of a continuous-time optimal control problem and a discrete optimization problem. Then, a modified Broyden-Fletcher-Goldfarb-Shanno algorithm and a discrete filled function method is first proposed to solve this bi-level optimization problem. Finally, a numerical example is presented to illustrate the efficiency of our method.     

Optimal distributed linear averaging

A new optimal distributed linear averaging (ODLA) problem is presented in this paper. This problem is motivated by the distributed averaging problem which arises in the context of distributed algorithms in computer science and coordination of groups of autonomous agents in engineering. The aim of the ODLA problem is to compute the average of the initial values at nodes of a graph through an optimal distributed algorithm in which the nodes in the graph can only communicate with their neighbors. Optimality is given by a minimization problem of a quadratic cost functional under infinite horizon. We show that this problem has a very close relationship with the notion of semistability. By developing new necessary and sufficient conditions for semistability of linear discrete-time systems, we convert the proposed ODLA problem into an equivalent, constrained optimization problem and then derive a solvable, fixed-structure convex optimization problem.     

多一次Paillier求逆问题与并发安全的鉴别方案

从计算难解性的角度重新考察Paillier的陷门单向函数,并提出多一次Paillier求逆问题这一关于Paillier求逆问题的推广问题.从计算难解性的角度考察了多一次Paillier求逆问题与Bellare等人提出的多一次RSA求逆问题之间的关系,并证明了在计算难解性的意义上。多一次Paillier求逆问题等价于多一次RSA求逆问题.以此为基础,进而提出一种新的鉴别方案,并证明在多一次Paillier求逆问题的难解性假设下这一鉴别方案具备并发安全性.     

一类优化问题的分解算法

讨论一类大规模系统的优化问题,提出一种递阶优化方法．该方法首先将原问题转化为多目标优化问题,证明了原问题的最优解在多目标优化问题的非劣解集中,给出了从多目标优化问题的解集中挑出原问题最优解的算法,建立了算法的理论基础．仿真结果验证了算法的有效性．     

排课表问题的闭环DNA计算模型的算法

排课表问题是NP-完全问题。基于闭环DNA计算模型引入多种生化实验得出求解排课表问题的DNA算法。本算法采用两部编码方式产生初始数据池,引入批删除实验解决了教师和班级的冲突问题和同班课问题;引入批分离实验解决了正常合班课问题和教师时间要求问题;引入电泳实验解决了排课的均衡分配问题;引入标记实验得到了排课表问题的全局最优解集,并给出了算法的生化实现过程。最后,对算法的正确性进行了证明,并讨论了算法的复杂性。     

基于遗传算法的物流配送路径优化问题研究

遗传算法是一种基于自然进化原理的全局搜索随机算法。遗传算法在选址问题、配送问题、调度问题、运输问题、布局问题方面意义重大。在建立物流配送路径优化问题数学模型的基础上,构造了求解该问题的遗传算法。该遗传算法采用常用的二进制编码,在个体选择上结合使用最优个体保留策略和轮盘赌法。最后以这种方法进行了实验计算,通过计算结果表明,用遗传算法进行物流配送路径优化,可以方便有效地求得问题的最优解或近似最优解。     

The Definition and Numerical Method of Final Value Problem and Arbitrary Value Problem

Many Engineering Problems could be mathematically described by FinalValue Problem, which is the inverse problem of InitialValue Problem. Accordingly, the paper studies the final value problem in the field of ODE problems and analyses the differences and relations between initial and final value problems. The more general new concept of the endpoints-value problem which could describe both initial and final problems is proposed. Further, we extend the concept into inner-interval value problem and arbitrary value problem and point out that both endpoints-value problem and inner-interval value problem are special forms of arbitrary value problem. Particularly, the existence and uniqueness of the solutions of final value problem and inner-interval value problem of first order ordinary differential equation are proved for discrete problems. The numerical calculation formulas of the problems are derived, and for each algorithm, we propose the convergence and stability conditions of them. Furthermore, multivariate and high-order final value problems are further studied, and the condition of fixed delay is also discussed in this paper. At last, the effectiveness of the considered methods is validated by numerical experiment.     

Problem reduction heuristic for the 0-1 multidimensional knapsack problem

This paper introduces new problem-size reduction heuristics for the multidimensional knapsack problem. These heuristics are based on solving a relaxed version of the problem, using the dual variables to formulate a Lagrangian relaxation of the original problem, and then solving an estimated core problem to achieve a heuristic solution to the original problem. We demonstrate the performance of these heuristics as compared to legacy heuristics and two other problem reduction heuristics for the multi-dimensional knapsack problem. We discuss problems with existing test problems and discuss the use of an improved test problem generation approach. We use a competitive test to highlight the performance of our heuristics versus the legacy heuristic approaches. We also introduce the concept of computational versus competitive problem test data sets as a means to focus the empirical analysis of heuristic performance.     

The three-dimensional assignment and partition problems. New lower bounds

For the three-dimensional assignment problem, new sharp lower bounds are derived from its relationship with the partition problem. The new sharp lower bounds derived for the partition problem from optimal control theory are of great value not only for the three-dimensional assignment problem, but also for the partition problem itself.