离散优化与连续优化的复杂性概念

问题的复杂性概念起源于离散的图灵计算机理论的研究,在离散优化问题的研究中被广泛的接受.近期连续优化领域的很多文章中提及NP难这个概念.从而来对比介绍离散优化和连续优化研究中这两个概念的差异.     

离散事件动态系统的周期配置

用极大代数描述的离散事件动态系统X(k)=X(k-1)A?U(k)B中,A的右上三角块标准形的全部A_i的特征值λ_i,1≤i≤ω称为周期.本文证明了:能用状态反馈U(k)=X(k-1)K在[λ_i,+∞)中任意配置周期(即配置“极点”)的充要条件是A,B有匹配的标准形;还给出了周期配置与能达性的关系及在FMS中的应用.     

一类离散事件动态系统极点分配的优化问题

应用极大代数作为数学工具,用系统矩阵的特征值法讨论了m × n-型离散事件动态系统极点分配的优化问题.给出了系统取得优化的条件.并证明了至少存在,n个具有最优极点分配的优化系统.     

基于离散变量的拓扑优化方法

单元敏度的不准确估计是离散拓扑优化算法数值不稳定的原因之一,特别是添加材料时,传统的敏度计算公式给出的估计误差较大,甚至有时估计符号都是错误的．为了克服这一问题,通过对弹性平衡增量方程的摄动分析构造了新的增量敏度估计公式．这一新的公式无论是添加材料还是删除材料都能较准确地估计出目标函数增量,它可以看作是通过非局部单元刚度阵对传统敏度分析公式的修正．以此为基础构建了一种基于离散变量的拓扑优化算法,它可以从任意单元上添加或删除材料以使目标函数减小,同时为避免优化过程中重新划分网格,采用了单元软杀策略以小刚度材料模拟空单元．这一方法的主要优点是简单,不需要太多的数学计算,特别有利于工程实际的应用．     

基于仿真优化算法的医院关键资源能力分派研究

图像检查设备是医院的瓶颈资源。医院管理者通常追求瓶颈资源的高利用率,导致患者需长时间等待才能进行检查。长时间的等待加剧了患者的焦虑情绪,也会给患者造成病情加重等隐患。考虑患者具有不同的目标等待时间,本文针对医疗关键资源能力分派问题,提出了双层嵌套的阈值策略。非紧急患者预约时,双层嵌套阈值考虑为将来到达的紧急患者预留一定量的能力。如果患者在目标等待时间内预约不成功,则离开医院,并对医院造成患者流失惩罚。目标函数是使患者总流失惩罚最小。本文用目标函数对嵌套阈值的偏导数作为最速梯度法下降方向,基于样本路径对该偏导数进行估计,并通过不断迭代得到最优阈值。数值实验中,与医院应用的传统阈值策略比较,结果显示,本文所提嵌套阈值策略能够有效降低因超过目标等待时间而流失的患者给医院带来的损失。     

离散事件动态系统研究中图论方法的某些应用

因为许多离散生产过程都可以用离散事件系统描述，所以离散事件动态系统有很强的实用背景，例如柔性制造系统，因此，受到国内外的广泛注意和重视，进行深入研究，已获得一些很重要的理论结果．本文试图用图论的观点和方法，对离散事件动态系统的某些重要结果予以注释和新的证明，并探讨图论在该领域研究中的进一步应用．     

离散事件动态系统的关键路径与扰动分析

具有存储器的串行生产线是一典型离故事件动态系统．本文在其极大代数上线性状态方程的基础上，定义了关键路径，并研究了关键路径的特性．通过关键路径，给出了其扰动分析方法．     

需求离散的变质性物品库存补充策略优化研究

研究了在不允许缺货情况下需求为离散的变质性物品的库存补充策略问题.在假定变质率为常数的情况下,建立了有限时域内变质性物品的补充策略模型,并给出了求最优补充策略的方法.     

基于Monte Carlo仿真的小概率事件评估算法稳定性研究

应用极值理论对小概率事件进行评估的过程中,运用仿真的方法突破了客观条件对评估样本数量的限制,样本选取数量与评估概率的关系以及极值风险评估算法稳定性是亟待讨论的理论难点问题.以飞行风险为研究对象,分析了对评估稳定性造成主要影响的随机性因素,建立了用于稳定性分析的综合考虑“物理特性”和“随机特性”的典型人-机系统仿真模型.根据仿真评估结果,归纳了评估概率随样本数量的变化规律和Monte Carlo仿真对评估稳定性的影响,提出了合理选取样本数量和评估次数的方法.研究内容可为提高小概率事件评估的稳定性、减小评估误差提供参考和借鉴.     

离散变量结构优化设计的组合算法*

本文首先给出了离散变量优化设计局部最优解的定义,然后提出了一种综合的组合算法.该算法采用分级优化的方法,第一级优化首先采用计算效率很高且经过随机抽样性能实验表明性能较高的启发式算法─—相对差商法,求解离散变量结构优化设计问题近似最优解 X ;第二级采用组合算法,在 X 的离散邻集内建立离散变量结构优化设计问题的(-1,0.1)规划模型,再进一步将其化为(0,1)规划模型,应用定界组合算法或相对差商法求解该(0,1)规划模型,求得局部最优解.解决了采用启发式算法无法判断近似最优解是否为局部最优解这一长期未得到解决的问题,提高了计算精度,同时,由于相对差商法的高效率与高精度,以上综合的组合算法的计算效率也还是较高的.     

Call Admission: A New Approach to Quality of Service

Quality of service guarantees are an important and much discussed aspect of ATM network design. However, there is no standard definition of quality of service. Moreover, some often-used criteria seem quite crude. We consider call admission to a bufferless ATM multiplexer with on/off sources. A new criterion for a guarantee on average cell loss is proposed. This criterion represents the quality of service from the point of view of the user, and is thus more reliable. We calculate the optimal policy that minimizes blocking subject to the guarantee, when there is only one type of user.The measure of cell-loss we propose is applicable to a wide range of models. It gives rise to a mathematical programming formulation, which we derive explicitly for our case.     

一类非线性奇异最优控制问题的离散解法

本文研究非线性奇异最优控制问题的离散解法。利用在每个“小”时间区间上的积分形式来刻画奇异最优控制的特征,并构造了求解问题的差分方程,同时建立预估、校正格式给出了最优控制近似解的计算方法。     

Dynamic Routing and Admission Control in High-Volume Service Systems: Asymptotic Analysis via Multi-Scale Fluid Limits

Motivated by applications in telephone call centers, we consider a service system model with m customer classes and r server pools. The model is one with doubly stochastic arrivals, which means that the m-vector λ of instantaneous arrival rates is allowed to vary both temporally and stochastically. Two levels of dynamic control are considered: customers may be either blocked or accepted at the time of their arrival, and then accepted customers of each class must be routed, either immediately upon acceptance or after some period of waiting, to a server pool that is qualified to handle that class. Customers who are made to wait before commencement of their service are liable to defect. The objective is to minimize the expected sum of blocking costs, waiting costs and defection costs over a fixed and finite planning horizon. We consider an asymptotic parameter regime in which (i) the arrival rates, service rates and defection rates are uniformly accelerated by a large factor κ, then (ii) arrival rates are increased by an additional factor g(κ), and the number of servers in each pool is increased by g(κ) as well. This produces a separation of time scales, justifying a pointwise stationary stochastic fluid approximation for our original system model. In the stochastic fluid approximation, optimal admission control and routing decisions are determined by a simple linear program that uses the current arrival rate vector λ as data. We explain how to implement the fluid model's optimal control policy in our original service system context, and prove that the proposed implementation is asymptotically optimal in the first-order sense. AMS subject classification: 60K30, 90B15, 90B36     

森林病虫害模型的数值模拟

讨论森林病虫害的离散模型.根据森林病虫害传播的特征,针对各分块区域之间已感病树不互相转移的情况,建立差分方程模型;讨论系统的平衡点,并对无病平衡点和地方病平衡点进行稳定性分析,得到地方病平衡点稳定的充分条件;用Matlab进行多种情况的数值模拟,验证了理论结果.     

A Novel Simulation Method for Binary Discrete Exponential Families,With Application to Social Networks

Stochastic models for finite binary vectors are widely used in sociology, with examples ranging from social influence models on dichotomous behaviors or attitudes to models for random graphs. Exact sampling for such models is difficult in the presence of dependence, leading to the use of Markov chain Monte Carlo (MCMC) as an approximation technique. While often effective, MCMC methods have variable execution time, and the quality of the resulting draws can be difficult to assess. Here, we present a novel alternative method for approximate sampling from binary discrete exponential families having fixed execution time and well-defined quality guarantees. We demonstrate the use of this sampling procedure in the context of random graph generation, with an application to the simulation of a large-scale social network using both geographical covariates and dyadic dependence mechanisms.     

Prioritized Composition With Exclusion and Generation for the Interaction and Control of Discrete Event Systems

Interaction of multiple discrete event systems (DESs) represented as automata are carried out using composition operations. These operations on automata enforce concurrency, wherein an event exists in the composed automaton if it exists in the participating states of the interacting automata possessing the event in their event set. Heymann generalized this by introducing event priorities, wherein an event exists in the composed automaton if it exists in the participating state of the interacting automata having priority over the event. For two interacting automata P and Q, while prioritized composition can model the P, Q, AND, and OR boolean interactions, it cannot model boolean interactions which require exclusivity of participation, namely, “exclusive P”, “exclusive Q”, “exclusive P or exclusive Q”, “exclusive P and exclusive Q”. In order to also model these additional interactions we propose a generalization of prioritized composition by introducing an exclusivity set besides the existing priority sets. The resulting composition is called prioritized composition with exclusion. We also introduce prioritized composition with exclusion and generation that allows for all sixteen boolean modes of interaction possible when two automata interact. This is done by the further introduction of a nor-generative set. This event set together with the two priority sets and an exclusivity set makes it possible to model eight additional boolean interactions which do not require either of the interacting automata to participate for the event to be enabled in the composed automaton. The applicability of these interactions to decentralized supervisory decision fusion and in composing the rules based model of systems has been illustrated.     

A visual programming system for defining behavior in simulation models of manufacturing systems

A visual programming system is described that allows the modeler full flexibility in defining the behavior of a manufacturing system simulation model. Decision-making behavior of objects in the simulation can be viewed by watching an animation of the system layout, viewing function block diagrams of rules that govern behavior, or noting the progress of an object in carrying out sequences of activities that are pictured as operation networks. Rules, elemental operations and operation networks are structured and associated with particular objects, groups of objects, and locations on the manufacturing system layout. The objective of this system is to reduce the time and expense required to construct and modify models, given that manufacturing system data have been collected.     

基于网络控制的供应链库存系统的稳定性分析

针对一类供应链库存系统,研究了系统的闭环稳定性问题.创新点在于通过引入网络控制的思想,把供应链库存系统建模成网络时滞控制系统.在网络诱导时滞的上下界和丢包率已知的前提下,通过网络控制器的设计,分析了供应链库存系统的稳定性,并利用自由权矩阵和Lyapunov稳定性理论,给出了供应链库存系统渐近稳定的充分条件,并通过数值仿真验证了所提控制方案的可行性和有效性.     

广义系统动态输出反馈控制设计的新方法

对于连续时间的广义系统,基于线性矩阵不等式(LMI),提出了动态输出反馈H_∞控制设计的新方法.给出了广义系统动态输出反馈H_∞控制存在的充分条件.通过求解线性矩阵不等式和矩阵方程实现控制的设计.所提出确定控制的方法是简洁和易于实现的.一个数值例子说明了提出方法的设计过程和控制的有效性.     

A Mathematical Programming Approach to Optimal Markovian Switching of Poisson Arrival Streams to Queueing Systems

Motivated by certain situations in manufacturing systems and communication networks, we look into the problem of maximizing the profit in a queueing system with linear reward and cost structure and having a choice of selecting the streams of Poisson arrivals according to an independent Markov chain. We view the system as a MMPP/GI/1 queue and seek to maximize the profits by optimally choosing the stationary probabilities of the modulating Markov chain. We consider two formulations of the optimization problem. The first one (which we call the PUT problem) seeks to maximize the profit per unit time whereas the second one considers the maximization of the profit per accepted customer (the PAC problem). In each of these formulations, we explore three separate problems. In the first one, the constraints come from bounding the utilization of an infinite capacity server; in the second one the constraints arise from bounding the mean queue length of the same queue; and in the third one the finite capacity of the buffer reflect as a set of constraints. In the problems bounding the utilization factor of the queue, the solutions are given by essentially linear programs, while the problems with mean queue length constraints are linear programs if the service is exponentially distributed. The problems modeling the finite capacity queue are non-convex programs for which global maxima can be found. There is a rich relationship between the solutions of the PUT and PAC problems. In particular, the PUT solutions always make the server work at a utilization factor that is no less than that of the PAC solutions.