货运列车的编组调度问题的研究

对于货运列车的编组调度问题,建立了以压缩中时和增加运量为双目标、多约束的0-1规划模型,采用逐步紧缩中时约束的方法得到了问题一的调度方案.在此基础上对装载特别物资的车辆施加更强的中时约束得到了问题二的调度方案.提出了列车匹配系数的概念并建立了列车最优配对原则,根据该原则对列车进行优化编组得到了问题三的调度方案.基于问题二的数据转换处理得到了问题四的调度方案.     

Solving some optimal control problems using the barrier penalty function method

In this paper we present a new approach to solve a two-level optimization problem arising from an approximation by means of the finite element method of optimal control problems governed by unilateral boundary-value problems. The problem considered is to find a minimum of a functional with respect to the control variablesu. The minimized functional depends on control variables and state variablesx. The latter are the optimal solution of an auxiliary quadratic programming problem, whose parameters depend onu.Our main idea is to replace this QP problem by its dual and then apply the barrier penalty method to this dual QP problem or to the primal one if it is in an appropriate form. As a result we obtain a problem approximating the original one. Its good property is the differentiable dependence of state variables with respect to the control variables. Furthermore, we propose a method for finding an approximate solution of a penalized lower-level problem if the optimal solution of the original QP problem is known. We apply the result obtained to some optimal shape design problems governed by the Dirichlet-Signorini boundary-value problem.This research was supported by the Academy of Finland and the Systems Research Institute of the Polish Academy of Sciences.     

Inverse Problem for an Integro-Differential Equation of Acoustics

We consider the hyperbolic integro-differential equation of acoustics. The direct problem is to determine the acoustic pressure created by a concentrated excitation source located at the boundary of a spatial domain from the initial boundary-value problem for this equation. For this direct problem, we study the inverse problem, which consists in determining the onedimensional kernel of the integral term from the known solution of the direct problem at the point x = 0 for t > 0. This problem reduces to solving a system of integral equations in unknown functions. The latter is solved by using the principle of contraction mapping in the space of continuous functions. The local unique solvability of the posed problem is proved.     

A variational iteration method for solving Troesch’s problem

Troesch’s problem is an inherently unstable two-point boundary value problem. A new and efficient algorithm based on the variational iteration method and variable transformation is proposed to solve Troesch’s problem. The underlying idea of the method is to convert the hyperbolic-type nonlinearity in the problem into polynomial-type nonlinearities by variable transformation, and the variational iteration method is then directly used to solve this transformed problem. Only the second-order iterative solution is required to provide a highly accurate analytical solution as compared with those obtained by other analytical and numerical methods.     

Inverse sorting problem by minimizing the total weighted number of changes and partial inverse sorting problems

In this paper, we consider two types of inverse sorting problems. The first type is an inverse sorting problem by minimizing the total weighted number of changes with bound constraints. We present an O(n ²) time algorithm to solve the problem. The second type is a partial inverse sorting problem and a variant of the partial inverse sorting problem. We show that both the partial inverse sorting problem and the variant can be solved by a combination of a sorting problem and an inverse sorting problem. Supported by the Hong Kong Universities Grant Council (CERG CITYU 103105) and the National Key Research and Development Program of China (2002CB312004) and the National Natural Science Foundation of China (700221001, 70425004).     

The Transportation Problem and its Variants

For 54 unimodular linear programming problems it is shown that either (i) the objective function is unbounded, or (ii) the problem is infeasible, or (iii) the problem can be solved by solving a related transportation problem. The related transportation problem is obtained by adding at the most two new constraints to the original problem.     

Duality theorem for a generalized Fermat-Weber problem

The classical Fermat-Weber problem is to minimize the sum of the distances from a point in a plane tok given points in the plane. This problem was generalized by Witzgall ton-dimensional space and to allow for a general norm, not necessarily symmetric; he found a dual for this problem. The authors generalize this result further by proving a duality theorem which includes as special cases a great variety of choices of norms in the terms of the Fermat-Weber sum. The theorem is proved by applying a general duality theorem of Rockafellar. As applications, a dual is found for the multi-facility location problem and a nonlinear dual is obtained for a linear programming problem with a priori bounds for the variables. When the norms concerned are continuously differentiable, formulas are obtained for retrieving the solution for each primal problem from the solution of its dual.     

Quasiperiodic solutions of variational problems of motion in a central force field

A method is proposed for computing nearly optimal trajectories of dynamic systems with a small parameter by splitting the original variational problem into two separate problems for "fast" and "slow" variables. The problem for "fast" variables is solved by improving the zeroth approximation — the extremals of the linearized problem — by the Ritz method. The solution of the problem for "slow" variables is constructed by passing from a discrete argument — the number of revolutions around the attracting center— to a continuous argument. The proposed method does not require numerical integration of systems of differential equations and produces a highly accurate approximate solution of the problem.Kiev University. Translated from Vychislitel'naya i Prikladnaya Matematika, No. 68, pp. 113–118, 1989.     

Reformulation and solution approach for non-separable integer quadratic programs

We consider quadratic programs with pure general integer variables. The objective function is quadratic and convex and the constraints are linear. An exact solution approach is proposed. It is decomposed into two phases. In the first phase, the initial problem is reformulated into an equivalent problem with a separable objective function. This is done by use of a Gauss decomposition of the Hessian matrix of the initial problem and requires the addition of some continuous variables and constraints. In the second phase, the reformulated problem is linearized by an approximation of each squared term by a set of K linear functions that correspond to the tangents of a hyperbola in K points. We give a proof of the intuitive property that when K is large enough, the optimal value of the obtained linear program is very close to optimal value of the two previous problems, the initial problem and the reformulated separable problem. The reminder is dedicated to the implementation of a branch-and-bound algorithm for the solution of linearized problem, and its application to a set of instances. Several points are considered among which choice of the right value for parameter K and the implementation of a sophisticated heuristic solution algorithm. The numerical comparison is done with CPLEX 12.2 since, in this case, the initial problem as well as the problem reformulated by the first step can be solved by CPLEX. We show that with our approach, the total CPU time is divided by a factor ranging from 1.2 to 131.6 for instances with 40–60 variables.     

Scheduling a single machine to minimize earliness penalties subject to the SLK due-date determination method

This paper considers a single machine scheduling problem. There are n jobs to be processed on a single machine. The problem is to minimize total earliness penalties subject to no tardy jobs. The problem is NP-complete if the due-dates are arbitrary. We study the problem when the due-dates are determined by the equal slack (SLK) method. Two special cases of the problem are solved in polynomial time. The first one is the problem with equally weighted monotonous penalty objective function. The second one is the problem with weighted linear penalty objective function.     

A new algorithm for the quasi-assignment problem

The quasi-assignment problem can be used to solve the bus scheduling problem, the tourist guide problem, and the minimum number of chains in a partially ordered set. A successive shortest path algorithm for the assignment problem is extended to the quasiassignment problem. The algorithm is a variation of the primal-dual algorithm, and its computational complexity isO(n ³).The research for this paper was partly supported by the Chinese National Science Foundation.     

Solution of boundary-value problems in the theory of analytic functions of several variables in Vladimirov algebras

A solution is given for the Riemann problem for tubular domains in Vladimirov algebras in closed form by means of an integral representation of Bochner-Vladimirov type which is constructed here. In particular, the Schwartz problem is solved. The statement of the Hilbert problem in Vladimirov algebras is examined and its solution is given by a reduction to the Riemann problem, and in one case by a reduction to the Schwartz problem.Translated from Matematicheskie Zametki, Vol. 22, No. 1, pp. 51–60, July, 1977.     

Numerical solution of the Gel'fand-Levitan equation

The inverse Sturm-Liouville problem is solved by using the Gel'fand-Levitan equation. The equation is discretized by the trapezoidal rule and the problem reduced to solving a sequence of systems of linear equations. The convergence of the method is established. It is shown that the problem can be arbitrarily ill conditioned. Finally, the accuracy of the method is illustrated by two numerical examples.     

Relaxation of Optimal Control Problem Governed by Semilinear Elliptic Equation with Leading Term Containing Controls

An optimal control problem governed by semilinear elliptic partial differential equation is considered. The equation is in divergence form with the leading term containing controls. A relaxed problem is constructed by homogenization. By studying the G-closure problem, a local representation of admissible set of relaxed control is given. Finally, the maximum principle of relaxed problem is established via homogenization spike variation.     

Classification Problem for Graphs and Lattices is Wild

The classification problem for finite and infinite algebraic lattices has also been extensively addressed. A wild classification problem contains the classification problem of pairs of matrices up to simultaneous similarity. In this paper, we prove that the classification problem for graphs is wild by reducing the classification problem for finite 2-nilpotent p-groups to the classification problem for graphs.     

Solution of Special Linear Programming Problems with Additional Constraints

This paper gives a method of solution for linear programming problems whose constraints can be split into two sets, the first having a special structure, such as that of the transportation problem for example, while the second set is quite general. A problem with only the first set of constraints is referred to as a favoured problem, while a problem with both sets is called a complete problem.The proposed method is basically the simplex procedure specialized for a problem with a particular structure, and the feasibility and optimality criteria and the rules for basis change are the same as those used in the simplex procedure. However, the method takes advantage of the simple algorithms developed for the favoured problem and uses them to solve the complete problem in an efficient manner.Such problems could also be solved by the Decomposition Principle and, vice versa, Decomposition problems can be solved by the present method. The two methods are, however, essentially different in their approach to the problem.     

Orbits of linear maps and regular languages

The equivalence is established of the problem of hitting a polyhedral set by the orbit of a linear map and the intersection of a regular language and a language of permutations of binary words ( P_\mathbbBP_\mathbb{B}-realizability problem). The decidability of the both problems is presently unknown, and the first one is a straightforward generalization of the famous Skolem problem and the nonnegativity problem in the theory of linear recurrent sequences.     

A posteriori error analysis for linearization of nonlinear elliptic problems and their discretizations

The paper is devoted to a posteriori quantitative analysis for errors caused by linearization of non-linear elliptic boundary value problems and their finite element realizations. We employ duality theory in convex analysis to derive computable bounds on the difference between the solution of a non-linear problem and the solution of the linearized problem, by using the solution of the linearized problem only. We also derive computable bounds on differences between finite element solutions of the nonlinear problem and finite element solutions of the linearized problem, by using finite element solutions of the linearized problem only. Numerical experiments show that our a posteriori error bounds are efficient.     

Process and content: two ways of using SSM

Soft systems methodology (SSM) includes several ways of gaining a rich appreciation of the problem situation addressed. ‘Analysis One’, exploration of the intervention itself, is the subject here, since it is sparsely covered in the literature. The analysis is conducted in terms of three roles: ‘client’, ‘problem solver’ and ‘problem owner’. Whoever is in the role of ‘problem solver’ is free to define a list of possible ‘problem owners’, which brings many perspectives to bear on the situation. It was realized that ‘client’ and ‘problem solver’ should themselves feature in the ‘problem owner’ list. The ‘problem’ owned by the ‘problem solver’ is that of undertaking the intervention. This led to a realization that SSM is relevant to both the content of a perceived situation (SSMc) and the process of dealing with that content (SSMp). This development is described and illustrated by work in the National Health Service. The focus of the SSM use was to define the intellectual process for a service specification project which NHS professionals would themselves carry out.