限制情况下装卸工问题的最优解

装卸工问题是从现代物流技术中提出的一个实际问题,这个问题的雏形早在上个世纪60年代中国科学院数学研究所就提出和研究过.现代物流技术迅速发展,促成和推动装卸工问题的提出和研究.装卸工问题是一个新的NP困难的组合优化问题,首先介绍装卸工问题及限制情况下装卸工问题的数学模型,然后分析限制情况下的装卸工问题的性质,最后给出该问题的所有最优解.     

On the Main Aspects of the Inverse Conductivity Problem

We consider a nonlinear inverse problem for an elliptic partial differential equation known as the Calder{\''o}n problem or the inverse conductivity problem. Based on several results, we briefly summarize them to motivate this research field. We give a general view of the problem by reviewing the available results for $C^2$ conductivities. After reducing the original problem to the inverse problem for a Schr\"odinger equation, we apply complex geometrical optics solutions to show its uniqueness. After extending the ideas of the uniqueness proof result, we establish a stable dependence between the conductivity and the boundary measurements. By using the Carleman estimate, we discuss the partial data problem, which deals with measurements that are taken only in a part of the boundary.     

Turing Machines Connected to the Undecidability of the Halting Problem

The problem of finding a Turing machine with undecidable halting problem whose program contains the smallest number of instructions is well known. Obviously, such a machine must satisfy the following condition: by deleting even a single instruction from its program, we get a machine with decidable halting problem. In this paper, Turing machines with undecidable halting problem satisfying this condition are called connected. We obtain a number of general properties of such machines and deduce their simplest corollaries concerning the minimal machine with undecidable halting problem.     

Solving the optimal control problem of the parabolic PDEs in exploitation of oil

In this paper, the optimal control problem is governed by weak coupled parabolic PDEs and involves pointwise state and control constraints. We use measure theory method for solving this problem. In order to use the weak solution of problem, first problem has been transformed into measure form. This problem is reduced to a linear programming problem. Then we obtain an optimal measure which is approximated by a finite combination of atomic measures. We find piecewise-constant optimal control functions which are an approximate control for the original optimal control problem.     

Boundary conditions of the second-order differential equation and the Riccati equation

The conversion of a second-order linear ordinary differential equation with variable coefficients into a Riccati equation depends on whether the second-order problem is an initial-value or two-point boundary-value problem. The distinction is critical in determining the initial condition for the Riccati equation. If the second-order problem is an initial-value problem, the choice of the Riccati transformation depends on whether a zero initial condition for the function or its derivative is specified. If the problem is a two-point boundary-value problem, special methods must be introduced as described in the paper.     

三种新变形的全一问题

该文研究三种新变形的全一问题及最小全一问题. 原始的全一问题可被形象的称为顶点点亮顶点问题, 而这三类新问题则分别被称为顶点点亮边问题,边点亮顶点问题,边点亮边问题. 顶点点亮顶点问题已经得到了广泛的研究. 比如,解的存在性问题和求解的有效算法已经被解决,一般图上的最小顶点点亮顶点问题已经被证明是NP- 完备的,树、单圈图和双圈图上的最小顶点点亮顶点问题的线性时间最优算法也已被给出等. 该文对于顶点点亮边问题,证明一个图有解当且仅当它是二部图,因此只可能有两组解和最优解. 对于边点亮顶点问题,证明一个图有解当且仅当它包含偶数个顶点,并通过将其最优问题多项式变换成最小权的完美匹配问题,得出一般图上的最小边点亮顶点问题可在多项式时间内求解. 边点亮边问题可归约成线图上的顶点点亮顶点问题.     

On the use of Kronecker's algorithm in the generalized rational interpolation problem

Kronecker's algorithm can be used to solve the generalized rational interpolation problem. In order to present the algorithm, rational forms are used here instead of too restrictive rational fractions. The proposed algorithm is reliable as soon as the functionals that characterize the problem satisfy two precise conditions. These conditions are fulfilled in the modified Hermite rational interpolation problem and, as a consequence, in the special case of the Cauchy problem and of the Padé approximation problem. This reliability covers two properties: on one hand, every rational form resulting from the algorithm is a solution of the problem whereas, on the other hand, every solution of the problem is found by the algorithm (with the exception of a possible reduction of the rational form). However, if the algorithm yields a non-reduced rational form, then the corresponding rational fraction is not a solution of the problem.     

Using the Dinkelbach-type algorithm to solve the continuous-time linear fractional programming problems

A Dinkelbach-type algorithm is proposed in this paper to solve a class of continuous-time linear fractional programming problems. We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary problem that will be formulated as parametric continuous-time linear programming problem. We also introduce a dual problem of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this practical algorithm.     

From the restricted to the full three-body problem

The three-body problem with all the classical integrals fixed and all the symmetries removed is called the reduced three-body problem. We use the methods of symplectic scaling and reduction to show that the reduced planar or spatial three-body problem with one small mass is to the first approximation the product of the restricted three-body problem and a harmonic oscillator. This allows us to prove that many of the known results for the restricted problem have generalizations for the reduced three-body problem.

For example, all the non-degenerate periodic solutions, generic bifurcations, Hamiltonian-Hopf bifurcations, bridges and natural centers known to exist in the restricted problem can be continued into the reduced three-body problem. The classic normalization calculations of Deprit and Deprit-Bartholomé show that there are two-dimensional KAM invariant tori near the Lagrange point in the restricted problem. With the above result this proves that there are three-dimensional KAM invariant tori near the Lagrange point in the reduced three-body problem.     

Optimal design of the damping set for the stabilization of the wave equation

We consider the problem of optimizing the shape and position of the damping set for the internal stabilization of the linear wave equation in RN, N=1,2. In a first theoretical part, we reformulate the problem into an equivalent non-convex vector variational one using a characterization of divergence-free vector fields. Then, by means of gradient Young measures, we obtain a relaxed formulation of the problem in which the original cost density is replaced by its constrained quasi-convexification. This implies that the new relaxed problem is well-posed in the sense that there exists a minimizer and, in addition, the infimum of the original problem coincides with the minimum of the relaxed one. In a second numerical part, we address the resolution of the relaxed problem using a first-order gradient descent method. We present some numerical experiments which highlight the influence of the over-damping phenomena and show that for large values of the damping potential the original problem has no minimizer. We then propose a penalization technique to recover the minimizing sequences of the original problem from the optimal solution of the relaxed one.     

On the complexity of the dominating induced matching problem in hereditary classes of graphs

The dominating induced matching problem, also known as efficient edge domination, is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This problem is known to be NP-complete. We study the computational complexity of the problem in special graph classes. In the present paper, we identify a critical class for this problem (i.e., a class lying on a “boundary” separating difficult instances of the problem from polynomially solvable ones) and derive a number of polynomial-time results. In particular, we develop polynomial-time algorithms to solve the problem for claw-free graphs and convex graphs.     

To the Solution of the Hilbert Problem with Infinite Index

In this paper, we obtain a generalization of the method of regularizing multipliers for the solution of the Hilbert boundary-value problem with finite index in the theory of analytic functions to the case of an infinite power-behaved index. This method is used to obtain a general solution of the homogeneous Hilbert problem for the half-plane, a solution that depends on the existence and the number of entire functions possessing mirror symmetry with respect to the real axis and satisfying some additional constraints related to the singularity characteristic of the index. To solve of the inhomogeneous problem, we essentially use a specially constructed solution of the homogeneous problem whereby we reduce the boundary condition of the Hilbert problem to a Dirichlet problem.     

On the determination of the potential function from given orbits

The paper deals with the problem of finding the field of force that generates a given (N ? 1)-parametric family of orbits for a mechanical system with N degrees of freedom. This problem is usually referred to as the inverse problem of dynamics. We study this problem in relation to the problems of celestial mechanics. We state and solve a generalization of the Dainelli and Joukovski problem and propose a new approach to solve the inverse Suslov’s problem. We apply the obtained results to generalize the theorem enunciated by Joukovski in 1890, solve the inverse Stäckel problem and solve the problem of constructing the potential-energy function U that is capable of generating a bi-parametric family of orbits for a particle in space. We determine the equations for the sought-for function U and show that on the basis of these equations we can define a system of two linear partial differential equations with respect to U which contains as a particular case the Szebehely equation. We solve completely a special case of the inverse dynamics problem of constructing U that generates a given family of conics known as Bertrand’s problem. At the end we establish the relation between Bertrand’s problem and the solutions to the Heun differential equation. We illustrate our results by several examples.     

Stability estimates for the solution to the problem of determining the kernel of a viscoelastic equation

For an integrodifferential equation corresponding to a two-dimensional viscoelastic problem, we study the problem of defining the spatial part of the kernel involved in the integral term of the equation. The support of the sought function is assumed to belong to a compact domain Ω. As information for solving this inverse problem, the traces of the solution to the direct Cauchy problem and its normal derivative are given for some finite time interval on the boundary of Ω. An important feature in the statement of the problem is the fact that the solution of the direct problem corresponds to the zero initial data and a force impulse in time localized on a fixed straight line disjoint with Ω. The main result of the article consists in obtaining a Lipschitz estimate for the conditional stability of the solution to the inverse problem under consideration.     

On the algorithm of the solution of the signorini problem

An algorithm is proposed for solving the Signorini problem /1/ in the formulation of a unilateral variational problem for the boundary functional in the zone of possible contact /2/. The algorithm is based on a dual formulation of Lagrange maximin problems for whose solution a decomposition approach is used in the following sense: a Ritz process in the basis functions that satisfy the linear constraint of the problem, the differential equation in the domain, is used in solving the minimum problem (with fixed Lagrange multipliers); the maximum problem is solved by the method of descent (a generalization of the Frank-Wolf method) under convexity constraints on the Lagrange multipliers. The algorithm constructed can be conisidered as a modification of the well-known algorithm to find the Udzawa-Arrow-Hurwitz saddle points /3, 4/. The convergence of the algorithm is investigated. A numerical analysis of the algorithm is performed in the example of a classical contact problem about the insertion of a stamp in an elastic half-plane under approximation of the contact boundary by isoparametric boundary elements. The comparative efficiency of the algorithm is associated with the reduction in the dimensionality of the boundary value problem being solved and the possibility of utilizing the calculation apparatus of the method of boundary elements to realize the solution.     

Bin covering algorithms in the second stage of the lot to order matching problem

We formulate the problem of effectively assigning semiconductor fabrication wafer lots to customer orders of various sizes, or the lot-to-order matching problem, as an integer programming problem. Our goal in this paper is to develop an efficient, practical method for solving this problem for various performance measures. Because of its complexity we decompose the problem into a knapsack problem coupled with a generalized bin-covering problem, and solve these subproblems sequentially using heuristic methods. We restrict our attention to solution methods for the less-common second subproblem, and analyze the performance of several heuristics using a data set representative of real situations in a semiconductor back-end. Based on this analysis, we show that these heuristics perform significantly better than current industrial practice in the context of the overall problem.     

Some duality relationships for the generalized Neyman-Pearson problem

In 1963, Kuhn presented a dual problem to a relatively well-known location problem, variously referred to as the generalized Fermat problem and the Steiner-Weber problem. The purpose of this paper is to point out how Kuhn's results can be adapted to provide a dual to the generalized Neyman-Pearson problem, a problem of fundamental interest in statistics, which has applications in control theory and a number of other areas. The Neyman-Pearson problem, termed the dual problem, is a constrained maximization problem and may be considered to be a calculus-of-variations analog to the bounded-variable problem of linear programming. When the dual problem has equality constraints, the primal problem is an unconstrained minimization problem. Duality results are also obtained for the case where the dual problem has inequality constraints.This work was partially supported by the National Science Foundation, Grant Nos. NSF-GK-1571 and NSF-GK-3038. The authors would like to acknowledge the very useful comments of one of the referees, which led to more direct and general proofs of Properties 2.3 and 2.6.     

A Note on the Relation between the Product Rate Variation (PRV) Problem and the Apportionment Problem

This note establishes a connection between two problems that appear in different contexts: the Product Rate Variation (PRV) problem (sequencing units in a mixed-model assembly line in order to maximize the regularity of the sequence with regard to the output of units) and the apportionment problem. This allows us to apply to the PRV problem the properties of the apportionment problem and known procedures for solving it, and suggests alternative approaches to the former problem.     

Thomas-Fermi近似问题求解

该文将Ｔｈｏｍａｓ Ｆｅｒｍｉ近似问题分解为一个带奇点的常微分方程边值问题和一个最优化问题，讨论了解的存在唯一性和解的性质，给出了Ｔｈｏｍａｓ Ｆｅｒｍｉ近似问题求解的具体步骤．     

Homogenization of boundary value problems in perforated domains with the third boundary condition and the resulting change in the character of the nonlinearity in the problem

We study the homogenization problem for the Poisson equation in a periodically perforated domain with a nonlinear boundary condition for the flux on the cavity boundaries. We show that, under certain relations on the problem scale, the homogenized equations may have different character of the nonlinearity. In each case considered, we obtain estimates for the convergence of solutions of the original problem to the solution of the homogenized problem in the corresponding Sobolev spaces.