二次分配问题的大洪水算法求解

大洪水算法是一种求解组合优化问题的独特方法,该方法通过模拟洪水上涨的过程来达到求解一些组合优化难题的目的.本文运用该方法求解二次分配问题(QAP),设计了相应的算法程序,并对QAPLIB(二次分配基准问题库)中的算例进行了实验测试,结果表明,大洪水算法可以快速有效地求得二次分配问题的优化解,是求解二次分配问题的一个新的较好方案.     

一种基于匈牙利算法的二次分配问题求解方法

二次分配问题(Quadratic assignment problem,QAP)属于NP-hard组合优化难题.二次分配问题的线性化及下界计算方法,是求解二次分配问题的重要途径.以Frieze-Yadegar线性化模型和Gilmore-Lawler下界为基础,详细论述了二次分配问题线性化模型的结构特征,并分析了Gilmore-Lawler下界值往往远离目标函数最优值的原因.在此基础上,提出一种基于匈牙利算法的二次分配问题对偶上升下界求解法.通过求解QAPLIB中的部分实例,说明了方法的有效和可行性.     

可转移效用下的动态模糊联盟的广义核心解

利用模糊数学相关理论,对具有可转移效用的模糊合作对策进行了研究.采用调整相应系数的方法给出了此类对策的广义核心解和广义稳定集的概念,讨论了它们之间的关系.提出一种新的分配方案—不将联盟总收益分配给所有局中人,而保留一部分从而实现收益的再分配.该成果解决了对策传统解在现实应用中的局限性,特别是对现实生活中的资源再分配问题具有一定的参考和应用价值.     

带赔偿的云计算服务拍卖机制研究

云计算提供了按需获取、按使用付费的IT资源获取模式,由于存在大量的云计算服务提供商,以市场化的形式来组织云计算资源的分配与获取是一种合理的方式.以面向市场的云计算服务架构为基础,研究了云计算用户和服务提供商之间的匹配问题.采用拍卖方式实现具体的匹配过程,并将服务失败时的赔偿问题纳入考虑,结合服务提供商的违约率提出了两种带赔偿的云计算服务拍卖机制一在逆向一级密封拍卖上增加赔偿因子,分析了其二人博弈和多人博弈的均衡;同时,研究了服务权再分配对该机制的影响.     

多因素指派模型全局优化问题研究

基于多因素资源优化分配问题的不确定性,建立基于区间数型下的不确定多因素指派模型,给出模型建立的理论依据与全局优化算法,拓展区间数型多因素指派模型,解决了不确定条件下多因素资源优化分配问题.考虑多因素影响,基于任务完成效率,以5类任务多因素分配问题为例,获得了指派模型全局优化的解.为不确定条件下资源优化分配问题的研究拓宽了决策途径.     

求解二次分配问题的拉格朗日松弛新方法

以改进的拉格朗日松弛(Lagrangian relaxation,LR)方法和二次分配问题(quadratic assignment problem,QAP)的线性化模型为基础,给出了求解QAP的拉格朗日松弛新方法,这为有效求解QAP提供了一种新的解决方案.通过求解二次分配基准问题库(QAPLIB)中的实际算例,从实验的角度说明了拉格朗日松弛新方法求解QAP的可行性及存在的不足之处,并对今后进一步的研究工作指明了方向.     

推出冲突避免的机场停机位分配问题

为了科学合理地利用机场停机位资源,克服现有模型对飞机进出机位安全性的考虑不足,研究兼顾运行安全和运行效率的机场停机位分配问题.首先分析了飞机在停机坪中的运行过程,提出以主动避免方式来解除飞机进出机位过程中的冲突,从而将具有潜在冲突的飞机对的机位分配作为约束条件,建立了一类推出冲突避免的停机位分配模型.然后对目标函数和约束条件进行分析和简化,将模型转化为线性模型来求解.算例仿真结果验证了该模型的有效性,表明所提出的主动避免冲突方法是能兼顾运行安全和效率的一种有效方法.     

基于网络DEA的共享投入与(非)期望产出的两部门并行系统效率评价——以中国道路运输业为例

研究了一类典型并行系统的效率评价问题:1)决策单元由两个并行的子单元组成;2)两个子单元之间存在部分共享投入资源的同时,也共同产生(非)期望产出,且我们无法明显区别该资源及(非)期望产出在不同子单元之间的分配比例.分别基于固定和可变规模收益,文章在分析决策单元整体效率及内部子单元效率的基础上,提出一种能同时确定系统整体效率及内部子单元效率的评价方法,该方法能够在评价系统效率的同时,实现共享资源与(非)期望产出的有效分配.最后,以中国道路交通运输业为实例对所提方法进行了说明.     

基于统一价格拍卖的初始排污权分配方法

针对初始排污权总量分配的实际问题,基于统一价格拍卖的思想提出了一种具有激励性的可变总量的分配方法,分别给出了排污企业对称和排污企业非对称两种情形下的线性均衡报价策略,并证明了该方法的可行性和有效性,从而为建设排污权分配和交易制度提供了理论依据和方法参考.     

具有资源约束的工期指派排序问题

研究在资源有限情况下,工件加工具有学习效应和凸资源依赖的单机排序问题,其中工件的实际加工时间与正常的加工时间,工件所排位置,学习因子及资源分配量都有关,为资源消耗量的一个凸函数.在模型中,讨论了两种情形::共同交货期(CON),共同松弛交货期(SLK).目标为确定工件的排序,资源分配和工件的工期,使得工件的提前、延误、工期费用的总和最小.在分配资源量有限情况下,证明了这两个问题都是多项式时间可解的,并给出了相应的算法.     

Reconstruction of boundary regimes in the inverse problem of thermal convection of a high-viscosity fluid

A problem of reconstruction of boundary regimes in a model for free convection of a high-viscosity fluid is considered. A variational method and a quasi-inversion method are suggested for solving the problem in question. The variational method is based on the reduction of the original inverse problem to some equivalent variational minimum problem for an appropriate objective functional and solving this problem by a gradient method. When realizing the gradient method for finding a minimizing element of the objective functional, an iterative process actually reducing the original problem to a series of direct well-posed problems is organized. For the quasi-inversion method, the original differential model is modified by means of introducing special additional differential terms of higher order with small parameters as coefficients. The new perturbed problem is well-posed; this allows one to solve this problem by standard methods. An appropriate choice of small parameters gives an opportunity to obtain acceptable qualitative and quantitative results in solving the inverse problem. A comparison of the methods suggested for solving the inverse problem is made with the use of model examples.     

Revision of distance minimization method for ranking of fuzzy numbers

Asady and Zendehnam employed “distance minimization” to ranking fuzzy numbers in Ref [1]. Then Abbasbandy and Hajjari in [2] found a problem of its. To overcome it problem, they proposed magnitude method to ranking fuzzy numbers. Unfortunately, their method can not to overcome this problem. In this paper, we want to indicate this problem and then propose a revise method of distance minimization method which can avoid problem for ranking fuzzy numbers. Since the revised method is based on the distance minimization method, it is easy to rank fuzzy numbers in a way similar to the original method.     

应用迭代法求解一类非线性问题

本文应用迭代法求解一类有限维非线性问题,该方法是求解线性问题的雅可比迭代法在非线性问题上的推广,且此迭代方法具有几何收敛性质.     

A stabilization method for solution of a parametric multicriteria equilibrium programming problem

A multicriteria equilibrium programming problem comprising a mathematical programming problem as a particular case, a multicriteria Pareto-point search problem, a minimization problem with equilibrium selection of the feasible set, etc., is considered. It is assumed that the initial data are known only approximately. In view of the fact that the considered problem is generally unstable with respect to the input data, a regularization method, which is a generalization of the Tikhonov stabilization method, is proposed. Conditions for matching the method parameters to the error in the input data are presented. The convergence of this method is analyzed.     

A Riemannian variant of the Fletcher–Reeves conjugate gradient method for stochastic inverse eigenvalue problems with partial eigendata

In this paper, we focus on the stochastic inverse eigenvalue problem with partial eigendata of constructing a stochastic matrix from the prescribed partial eigendata. A Riemannian variant of the Fletcher–Reeves conjugate gradient method is proposed for solving a general unconstrained minimization problem on a Riemannian manifold, and the corresponding global convergence is established under some assumptions. Then, we reformulate the inverse problem as a nonlinear least squares problem over a matrix oblique manifold, and the application of the proposed geometric method to the nonlinear least squares problem is investigated. The proposed geometric method is also applied to the case of prescribed entries and the case of column stochastic matrix. Finally, some numerical tests are reported to illustrate that the proposed geometric method is effective for solving the inverse problem.     

Scenario decomposition of risk-averse multistage stochastic programming problems

For a risk-averse multistage stochastic optimization problem with a finite scenario tree, we introduce a new scenario decomposition method and we prove its convergence. The main idea of the method is to construct a family of risk-neutral approximations of the problem. The method is applied to a risk-averse inventory and assembly problem. In addition, we develop a partially regularized bundle method for nonsmooth optimization.     

Identification of a time-dependent source term for a time fractional diffusion problem

In this paper, we study an inverse problem of identifying a time-dependent term of an unknown source for a time fractional diffusion equation using nonlocal measurement data. Firstly, we establish the conditional stability for this inverse problem. Then two regularization methods are proposed to for reconstructing the time-dependent source term from noisy measurements. The first method is an integral equation method which formulates the inverse source problem into an integral equation of the second kind; and a prior convergence rate of regularized solutions is derived with a suitable choice strategy of regularization parameters. The second method is a standard Tikhonov regularization method and formulates the inverse source problem as a minimizing problem of the Tikhonov functional. Based on the superposition principle and the technique of finite-element interpolation, a numerical scheme is proposed to implement the second regularization method. One- and two-dimensional examples are carried out to verify efficiency and stability of the second regularization method.     

Quasi-one-dimensional method for the two-dimensional inverse problem of magnetotelluric sounding

The article presents a quasi-one-dimensional method for solving the inverse problem of electromagnetic sounding. The quasi-one-dimensional method is an iteration process that in each iteration solves a parametric one-dimensional inverse problem and a two-dimensional direct problem. The solution results of these problems are applied to update the input values for the parametric one-dimensional inverse problem in the next iteration. The method has been implemented for a two-dimensional inverse problem of magnetotelluric sounding in a quasi-layered medium.     

Finite element methods of an operator splitting applied to population balance equations

In population balance equations, the distribution of the entities depends not only on space and time but also on their own properties referred to as internal coordinates. The operator splitting method is used to transform the whole time-dependent problem into two unsteady subproblems of a smaller complexity. The first subproblem is a time-dependent convection-diffusion problem while the second one is a transient transport problem with pure advection. We use the backward Euler method to discretize the subproblems in time. Since the first problem is convection-dominated, the local projection method is applied as stabilization in space. The transport problem in the one-dimensional internal coordinate is solved by a discontinuous Galerkin method. The unconditional stability of the method will be presented. Optimal error estimates are given. Numerical tests confirm the theoretical results.     

有资格限制的指派问题的求解方法

在实际的指派工作中，常会遇到某个人有没有资格去承担某项工作的问题，因此，本建立了有资格限制的指派问题的数学模型。在此数学模型中，将效益矩阵转化为判定矩阵，由此给出了判定此种指派问题是否有解的方法；在有解的情况下，进一步将效益矩阵转化为求解矩阵，从而将有资格限制的指派问题化为传统的指派问题来求解。最后给出了一个数值例子来说明这样的处理方法是有效的。