搜索路径给定时的搜索对策问题及其应用

搜索路径给定时的最优搜索方案问题,也可以理解为是关于搜索者和目标的二人对策问题,主要讨论了当搜索路径给定时的单个搜索者和单个目标的搜索对策问题。首先根据问题的特点,利用动态规划和迭代的方法,确定关于目标逃逸路径混合策略的最优分区,证明该分区是多面体凸集;针对目标不同逃逸路径的分区,求出搜索者的最大期望收益,再将问题转化为二人有限零和对策,计算出搜索者的支付矩阵,确定最优搜索策略。最后结合海军护航行动,对我舰载直升机搜索小型海盗船进行分析和计算,说明搜索路径给定时的最优搜索对策对于双方的资源分配和提高搜索效率具有一定的应用价值。     

Single‐commodity stochastic network design under demand and topological uncertainties with insufficient data

Stochastic network design is fundamental to transportation and logistic problems in practice, yet faces new modeling and computational challenges resulted from heterogeneous sources of uncertainties and their unknown distributions given limited data. In this article, we design arcs in a network to optimize the cost of single‐commodity flows under random demand and arc disruptions. We minimize the network design cost plus cost associated with network performance under uncertainty evaluated by two schemes. The first scheme restricts demand and arc capacities in budgeted uncertainty sets and minimizes the worst‐case cost of supply generation and network flows for any possible realizations. The second scheme generates a finite set of samples from statistical information (e.g., moments) of data and minimizes the expected cost of supplies and flows, for which we bound the worst‐case cost using budgeted uncertainty sets. We develop cutting‐plane algorithms for solving the mixed‐integer nonlinear programming reformulations of the problem under the two schemes. We compare the computational efficacy of different approaches and analyze the results by testing diverse instances of random and real‐world networks. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 154–173, 2017     

基于粒子群优化的观测站部署算法

针对红外观测站部署问题,在研究观测站位置对定位精度影响的基础上,提出了基于粒子群优化的观测站部署算法。首先对ECEF坐标系下的CRLB矩阵进行推导;然后将观测站优化部署问题抽象为非线性规划模型,并将红外传感器联合定位的CRLB作为目标函数;最后采用粒子群优化算法求解该模型,避免了传统的非线性规划算法需要求解目标函数梯度的难题。结果表明,本文的部署算法具有一定的理论依据和工程意义;可以为实际红外观测站的静态部署和动态部署提供参考。     

The burglar problem with multiple options

We consider the burglar problem in which a burglar can either retire or choose among different types of burglaries, with each type having its own success probability and reward distribution. Some general structural results are established and, in the case of exponentially distributed reward distributions, a solution technique is presented. The burglar problem's relationship to a stochastic knapsack problem with a random exponentially distributed knapsack capacity is shown. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 359–364, 2014     

A branch‐and‐price approach for the stochastic generalized assignment problem

In this article, we address a stochastic generalized assignment machine scheduling problem in which the processing times of jobs are assumed to be random variables. We develop a branch‐and‐price (B&P) approach for solving this problem wherein the pricing problem is separable with respect to each machine, and has the structure of a multidimensional knapsack problem. In addition, we explore two other extensions of this method—one that utilizes a dual‐stabilization technique and another that incorporates an advanced‐start procedure to obtain an initial feasible solution. We compare the performance of these methods with that of the branch‐and‐cut (B&C) method within CPLEX. Our results show that all B&P‐based approaches perform better than the B&C method, with the best performance obtained for the B&P procedure that includes both the extensions aforementioned. We also utilize a Monte Carlo method within the B&P scheme, which affords the use of a small subset of scenarios at a time to estimate the “true” optimal objective function value. Our experimental investigation reveals that this approach readily yields solutions lying within 5% of optimality, while providing more than a 10‐fold savings in CPU times in comparison with the best of the other proposed B&P procedures. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 131–143, 2014     

基于可能性决策的敌对危机行动预测与仿真

可能性决策能较好地应对军事领域常常出现的概率难以获得,或者强调“出奇制胜”而有意规避概率风险的情形,是解决知识不完备情况下敌对行动预测的有力手段。从可能性理论基本公理体系出发,结合动态规划方法,提出并证明可能性决策的最优化定理,给出多步条件下可能性决策的实现算法,结合危机条件下敌对行动预测的范例和仿真分析,与传统概率风险决策进行比较,体现可能性决策的优越性,为该方法的推广应用创造条件。     

A three‐stage procurement optimization problem under uncertainty

This article examines a problem faced by a firm procuring a material input or good from a set of suppliers. The cost to procure the material from any given supplier is concave in the amount ordered from the supplier, up to a supplier‐specific capacity limit. This NP‐hard problem is further complicated by the observation that capacities are often uncertain in practice, due for instance to production shortages at the suppliers, or competition from other firms. We accommodate this uncertainty in a worst‐case (robust) fashion by modeling an adversarial entity (which we call the “follower”) with a limited procurement budget. The follower reduces supplier capacity to maximize the minimum cost required for our firm to procure its required goods. To guard against uncertainty, the firm can “protect” any supplier at a cost (e.g., by signing a contract with the supplier that guarantees supply availability, or investing in machine upgrades that guarantee the supplier's ability to produce goods at a desired level), ensuring that the anticipated capacity of that supplier will indeed be available. The problem we consider is thus a three‐stage game in which the firm first chooses which suppliers' capacities to protect, the follower acts next to reduce capacity from unprotected suppliers, and the firm then satisfies its demand using the remaining capacity. We formulate a three‐stage mixed‐integer program that is well‐suited to decomposition techniques and develop an effective cutting‐plane algorithm for its solution. The corresponding algorithmic approach solves a sequence of scaled and relaxed problem instances, which enables solving problems having much larger data values when compared to standard techniques. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

装备保障抽组力量物资装载模型

对装备保障抽组力量的物资装载问题进行了数学描述,建立了以实现全部物资尽量分散装载为目标,以同类物资集中装载、车辆承载物资总体积不超过车辆有效容积、车辆承载物资总重量不超过车辆标记载重量、物资必须装载且不被重复装载等为主要约束的数学模型,并进行了求解.最后通过实例解算验证了模型的有效性.     

基于改进动态规划的雷达弱小目标检测与跟踪

针对复杂背景下雷达弱小目标的检测和跟踪问题,提出了一种改进动态规划的检测前跟踪算法.该方法用多级检验判决方法代替常用的两级门限检测,并用传统跟踪技术进行目标位置状态估计,根据估计值与状态值的欧氏距离设计一个惩罚项来改进值函数.通过仿真验证,结果表明该方法能有效消除伪航迹,减小计算量,提高对雷达弱小目标的检测和跟踪性能.     

机器人力反馈依从控制器多机系统分布式程序设计的实现

本文介绍在机器人力反馈依从控制器多机系统中采用程序设计语言C 与分布式库函数相结合实现分布式程序设计的方法,论述了分布式库函数形式,支持分布式库函数设计的多机操作系统功能及其在设计过程中应予以重视的某些问题,并给出了分布式程序设计的一个简例。