非齐次边值问题解的存在性

研究非齐次边界条件下,含有p—Laplacian算子的微分方程解的存在性,应用上下解方法,得到边值问题可解性的充分条件．     

Use of completely reduced matrices in solving transportation problems with fixed charges

This paper shows how completely reduced matrices can be used in obtaining exact or approximate solutions to transportation problems with fixed charges. It does not treat methods for obtaining reduced matrices, which are available elsewhere, but it does discuss the problem of obtaining a completely reduced matrix, and then a general parametric solution to the primal problem, from any particular solution. Methods for obtaining particular solutions with determinacies of maximum order (solutions for the constant fixed charges problem) are then presented. The paper terminates with a discussion of methods which are useful in obtaining approximations to solutions of fixed charges problems with charges not constant.     

零扰动下一类RN 上临界增长的椭圆方程正解的存在性

本文讨论了N维欧氏空间R~N上一类临界增长的拟线性椭圆型方程—div(|Du|~(p-2)Du)+k(x)u~)p-1)=K(x)U~(p-1),u∈W~(1,p)(R~N)∩L~p(R~N)的正解的存在性。其中4≤p~2≤N,p=Np/(N—p)。在微分几何与物理学等领域起重要作用的Yamabe问题就是其特例(p=2)。本文运用集中紧引理,证明了问题的正解的存在性。     

The enumeration of all efficient solutions for a linear multiple-objective transportation problem

An algorithm is presented by which the set of all efficient solutions for a linear multiple-objective transportation problem can be enumerated. First the algorithm determines an initial efficient basic solution. In a second step all efficient basic solutions are enumerated. Finally, the set of all efficient solutions is constructed as a union of a minimal number of convex sets of efficient solutions. The algorithm is illustrated by a numerical example.     

A heuristic routine for solving large loading problems

The loading problem involves the optimal allocation of n objects, each having a specified weight and value, to m boxes, each of specified capacity. While special cases of these problems can be solved with relative ease, the general problem having variable item weights and box sizes can become very difficult to solve. This paper presents a heuristic procedure for solving large loading problems of the more general type. The procedure uses a surrogate procedure for reducing the original problem to a simpler knapsack problem, the solution of which is then employed in searching for feasible solutions to the original problem. The procedure is easy to apply, and is capable of identifying optimal solutions if they are found.     

Coordinated scheduling of customer orders for quick response

The scheduling problem addressed in this paper concerns a manufacturer who produces a variety of product types and operates in a make‐to‐order environment. Each customer order consists of known quantities of the different product types, and must be delivered as a single shipment. Periodically the manufacturer schedules the accumulated and unscheduled customer orders. Instances of this problem occur across industries in manufacturing as well as in service environments. In this paper we show that the problem of minimizing the weighted sum of customer order delivery times is unary NP‐hard. We characterize the optimal schedule, solve several special cases of the problem, derive tight lower bounds, and propose several heuristic solutions. We report the results of a set of computational experiments to evaluate the lower bounding procedures and the heuristics, and to determine optimal solutions. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

三维静磁场Lipschitz区域上Robin问题广义解的存在与唯一性

近年来,电磁场边值问题的数值解法取得了飞速的发展．由于电磁场边值问题是一类非线性偏微分方程,研究解的存在性、唯一性具有较大的困难．前人已讨论了B-H间的几个基本不等式,并由之证明了三雏静磁场带零边值问题广义解的存在与唯一性,作者也曾利用给出的B-H间的不等式证明了三维静磁场Neumann问题和二维时变场第一边值初值问题广义解的存在与唯一性．由于在一般区域讨论存在困难,作者利用Sobolev空间理论及单调算子理论证明了三雏静磁场Lipschitz区域上Robin问题广义解的存在与唯一性．     

面向多最优解组合优化问题的决策求解算法

针对具有固定物品总和、多最优解特征的组合优化问题,以固定总和实数子集问题和购买鸡翅问题为例,给出了这类多最优解组合优化问题的形式化表示。在分析枚举等经典算法基础上,提出了基于整数状态表示和实数状态表示的0-1决策递归搜索多最优解动态规划算法。针对该算法在最优解数量较大时,时间复杂度趋向O(mⁿ)的问题,提出了基于相同决策路径合并和基于0-x决策的两种改进算法。实验中两种改进算法的计算时间基本符合与O(nb+nm)的正比关系,表明对于这类多最优解组合优化问题具有良好的求解性能。     

An exact solution approach for the time-dependent traveling-salesman problem

We present an algorithm for solving the time-dependent traveling-salesman problem (TDTSP), a generalization of the classical traveling salesman problem in which the cost of travel between two cities depends on the distance between the cities and the position of the transition in the tour. The algorithm is derived by applying Benders decomposition to a mixed-integer linear programming formulation for the problem. We identify trivial TDTSPs for which a standard implementation of the algorithm requires an exponential number of iterations to converge. This motivates the development of an efficient, network-flow-based method for finding Pareto-optimal dual solutions of a highly degenerate subproblem. Preliminary computational experience demonstrates that the use of these Pareto-optimal solutions has a dramatic impact on the performance of the algorithm. © 1996 John Wiley & Sons, Inc.     

Flow shop scheduling with earliness,tardiness, and intermediate inventory holding costs

We consider the problem of scheduling customer orders in a flow shop with the objective of minimizing the sum of tardiness, earliness (finished goods inventory holding), and intermediate (work‐in‐process) inventory holding costs. We formulate this problem as an integer program, and based on approximate solutions to two different, but closely related, Dantzig‐Wolfe reformulations, we develop heuristics to minimize the total cost. We exploit the duality between Dantzig‐Wolfe reformulation and Lagrangian relaxation to enhance our heuristics. This combined approach enables us to develop two different lower bounds on the optimal integer solution, together with intuitive approaches for obtaining near‐optimal feasible integer solutions. To the best of our knowledge, this is the first paper that applies column generation to a scheduling problem with different types of strongly ????‐hard pricing problems which are solved heuristically. The computational study demonstrates that our algorithms have a significant speed advantage over alternate methods, yield good lower bounds, and generate near‐optimal feasible integer solutions for problem instances with many machines and a realistically large number of jobs. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

New results on rendezvous search on the interval

In a rendezvous search problem, two players are placed in a network and must try to meet each other in the least possible expected time. We look at rendezvous search on a discrete interval in which the players are initially placed using independent draws (usually assumed to be from the same distribution). Some optimal solutions are known if this distribution is uniform, and also for certain other special types of distribution. In this article, we present two new results. First, we characterize the complete set of solutions for the uniform case, showing that all optimal strategies must have two specific properties (namely, of being swept and strictly geodesic). Second, we relate search strategies on the interval to proper binary trees, and use this correspondence to derive a recurrence relation for solutions to the symmetric rendezvous problem for any initial distribution. This relation allows us to solve any such problem computationally by dynamic programming. Finally, some ideas for future research are discussed. © Wiley Periodicals, Inc. Naval Research Logistics 60: 454–467, 2013     

Split delivery routing

This article examines a relaxed version of the generic vehicle routing problem. In this version, a delivery to a demand point can be split between any number of vehicles. In spite of this relaxation the problem remains computationally hard. Since only small instances of the vehicle routing problem are known to be solved using exact methods, the vehicle route construction for this problem version is approached using heuristic rules. The main contribution of this article to the existing body of literature on vehicle routing issues in (a) is presenting a new vehicle routing problem amenable to practical applications, and (b) demonstrating the potential for cost savings over similar “traditional” vehicle routing when implementing the model and solutions presented here. The solution scheme allowing for split deliveries is compared with a solution in which no split deliveries are allowed. The comparison is conducted on six sets of 30 problems each for problems of size 75, 115, and 150 demand points (all together 540 problems). For very small demands (up to 10% of vehicle's capacity) no significant difference in solutions is evident for both solution schemes. For the other five problem sets for which point demand exceeds 10% of vehicle's capacity, very significant cost savings are realized when allowing split deliveries. The savings are significant both in the total distance and the number of vehicles required. The vehicles' routes constructed by our procedure tend to cover cohesive geographical zones and retain some properties of optimal solutions.     

一种飞行器在线实时航迹规划算法

针对飞行器在线航迹规划问题展开研究,提出了一种实时航迹搜索算法。该方法将飞行器的运动与航迹搜索结合在一起,可以有效地调节搜索的时间,满足在线实时应用的要求。通过在限定的时间内扩大寻优范围,该算法可以有效地避免不可行区域,并使生成的航迹更加优化。实验结果表明,算法能有效地处理各种航迹约束,实时地生成满意的三维航迹。     

Note: The economic manufacturing lot-sizing problem with imperfect production processes: Bounds and optimal solutions

In this paper, we consider the economic production quantity problem in the presence of imperfect processes. In the literature, the time to shift from the in-control state to the out-of-control state is assumed to be exponentially distributed. In this study, we consider general time to shift distributions and provide distribution-based and distribution-free bounds on the optimal cost. For the exponential case, we compare the optimal solutions to approximate solutions proposed in the literature. A numerical example is used to illustrate the analysis presented and to conduct a sensitivity analysis in order to see the effect of the input parameters on the various solutions to the problem. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 423–433, 1998     

基于状态观测器的混沌系统鲁棒同步设计

研究了在有界干扰情况下一类非线性反馈混沌系统的鲁棒同步状态观测器设计问题。基于Sylvester矩阵方程的参数化解,将非线性反馈混沌系统的鲁棒同步状态观测器设计问题转化为带有约束条件的优化问题,通过解决该优化问题得到鲁棒同步状态观测器的增益矩阵,从而达到了干扰信号解耦目的。数值算例及其仿真结果表明:该非线性反馈混沌系统的鲁棒同步状态观测器的设计方法是简单有效的。     

An adaptive dynamic programming algorithm for a stochastic multiproduct batch dispatch problem

We address the problem of dispatching a vehicle with different product classes. There is a common dispatch cost, but holding costs that vary by product class. The problem exhibits multidimensional state, outcome and action spaces, and as a result is computationally intractable using either discrete dynamic programming methods, or even as a deterministic integer program. We prove a key structural property for the decision function, and exploit this property in the development of continuous value function approximations that form the basis of an approximate dispatch rule. Comparisons on single product‐class problems, where optimal solutions are available, demonstrate solutions that are within a few percent of optimal. The algorithm is then applied to a problem with 100 product classes, and comparisons against a carefully tuned myopic heuristic demonstrate significant improvements. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 742–769, 2003.     

Continuous quality production and machine maintenance

This paper formulates a problem of continuous quality production and maintenance of a machine. Quality is assumed to be a known function of the machine's (Markov diffusion process) degradation states. Applications to a specific quality function are used to obtain analytical solutions to an open-loop and feedback stochastic control maintenance problem.     

An n-step, 2-variable search algorithm for the component placement problem

The component placement problem is a specialization of the quadratic assignment problem that has been extensively studied for a decade and which is of considerable practical value. Recently, interest in component placement algorithms has risen primarily as a result of increased activity in the field of computer-aided design automation. This paper deals with the methodology of component placement and is based on the results of considerable operational experience. A tutorial presentation of tree search placement algorithms is provided, and an improved placement procedure is described which is demonstrated to be effective in generating near optimal solutions to the component placement problem. These solutions are completely reproducible and are obtained at an acceptable expenditure of computational resources. An additional objective is an assessment of performance of the class of near optimal algorithms. In particular, the question- how close to optimal are the near optimal solutions- is examined.     

Scheduling of depalletizing and truck loading operations in a food distribution system

This paper studies a scheduling problem arising in a beef distribution system where pallets of various types of beef products in the warehouse are first depalletized and then individual cases are loaded via conveyors to the trucks which deliver beef products to various customers. Given each customer's demand for each type of beef, the problem is to find a depalletizing and truck loading schedule that fills all the demands at a minimum total cost. We first show that the general problem where there are multiple trucks and each truck covers multiple customers is strongly NP‐hard. Then we propose polynomial‐time algorithms for the case where there are multiple trucks, each covering only one customer, and the case where there is only one truck covering multiple customers. We also develop an optimal dynamic programming algorithm and a heuristic for solving the general problem. By comparing to the optimal solutions generated by the dynamic programming algorithm, the heuristic is shown to be capable of generating near optimal solutions quickly. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

A generalized euclidean procedure for integer linear programs

This paper investigates a new procedure for solving the general-variable pure integer linear programming problem. A simple transformation converts the problem to one of constructing nonnegative integer solutions to a system of linear diophantine equations. Rubin's sequential algorithm, an extension of the classic Euclidean algorithm, is used to find an integer solution to this system of equations. Two new theorems are proved on the properties of integer solutions to linear systems. This permits a modified Fourier-Motzkin elimination method to be used to construct a nonnegative integer solution. An experimental computer code was developed for the algorithm to solve some test problems selected from the literature. The computational results, though limited, are encouraging when compared with the Gomory all-integer algorithm.