可增加号源策略下高需求门诊的能力配置问题

可增加号源策略,即在额定能力全部约满的情况下,医生可增加额外能力提供给仍有需求的患者.本文以面向预约患者和现场患者的高需求门诊为研究对象,考虑患者爽约不确定性对由额外能力产生的医生超负荷工作量的影响.联合决策额外挂号数量(简称加号数)和分配给预约患者的额定挂号数量,以使净收益期望最大.在理论上推导出额外挂号数量的阈值表达式,并证明当超过相应阈值后,净收益期望是额外挂号数量的单峰函数,其最优解可在有限解空间内决策.基于模型性质设计了求解全局联合最优解的双层枚举算法.实验结果表明,算法具有求解高效性;额外挂号数量(加号数)随爽约概率的增大而增加,受额定挂号数量的影响不大;加号策略有效增强了分配给预约患者的额定挂号数量面对爽约概率变化下的稳定性.     

多医生环境考虑患者爽约的门诊预约决策方法

针对多个医生医疗环境下具有提前预约和当天预约两类预约患者的门诊预约问题,在考虑提前预约患者可能存在爽约行为的情形下,提出了一种用于决定是否接受提前预约患者的预约请求的门诊预约决策方法.文中首先以医院的期望收益最大作为决策目标,建立了患者存在爽约行为的医疗预约问题的马尔可夫过程模型;然后基于所建立模型的特征,证明了对于任意的提前预约时段,均存在对应于每个医生的提前预约患者的最优预约数量的上界,且此上界随着患者爽约概率的增加而增加,随着预约所有医生的患者总数的增加而减小;进一步地,给出了该门诊预约问题的一种预约决策方法以及确定该方法的精确算法;最后,通过数值实验说明了本文所提出的决策方法的适用性和有效性.     

基于异质患者行为特征的动态门诊预约策略

针对服务时间不同的异质患者,研究患者动态到达且存在取消预约和爽约行为的门诊预约策略。假设患者行为依赖于其类型,以最大化期望利润为目标,采用超订的方式应对患者取消预约和爽约行为,当患者发出预约请求时需要立刻决定是否接受该患者。建立动态规划模型刻画患者的预约过程,利用逆推法进行求解以获得最优动态预约策略;通过近似方法降低模型的状态空间维度,并设计启发式算法求解状态向量不依赖于患者类型的动态预约策略。最后,基于蒙特卡洛模拟对启发式算法和动态规划结果进行比较,验证启发式算法的有效性,并分析参数变动对最终结果的影响。     

考虑延期交货、转包和非减库存能力约束的单产品批量模型

研究了一个非减库存能力约束下的允许延期交货和转包的单产品动态批量问题.引入子计划概念,通过先求解所有可能的子计划,再基于动态规划搜索子计划的最优组合,得到问题的最优解.给出了所有子计划的通用数学描述,并通过松弛正生产量约束将子计划的计算分成两个子问题;依据子问题和子计划最优解的性质,设计了求解子问题和重新集结松弛约束的多项式算法;在此基础上提出了一个复杂性为O(T4)的求解整个规划问题的多项式动态规划算法,这里T是规划时段上的周期数.最后通过数值试验测试了该算法的性能.     

能力受限批量问题的启发式算法与CPLEX仿真优化

能力受限批量问题多数都是NP-hard问题,解决方法之一就是构造启发式算法获取尽量接近最优解的可行解。目前多数文献通过大规模计算分析来评价启发式算法的性能,但是这种评价方式只能表明该算法针对特定实例的适应性。利用商业优化软件求解同一实例并与算法计算结果进行对比分析,可以体现算法的有效性。针对一种运输能力外包且费用时变的多产品动态经济批量问题,建立混合整数规划模型,通过约束松弛与模型分解,设计出一个基于拉格朗日松弛理论的启发式算法进行模型求解。大量随机实验计算结果以及CPLEX仿真优化结果对比分析表明,在某些实例情况下,启发式算法获取的最优值与CPLEX获取的相当,但是求解时间要明显优于CPLEX,因此选择启发式算法求解此类实例是较优的。     

用多目标进化算法求解二层规划双目标模型

传统单目标二层规划模型得到的最优解往往无法使上下级双方都满意.为此,通过在上层规划中同时考虑下级的目标函数,建立了原问题的上层为双目标规划的一个新模型.上下级可通过协商在该模型的Pareto-最优解集中找到双方满意解.对此模型设计了求解的多目标进化算法,用传统优化算法求解下层规划的单目标问题,而对上层的双目标规划问题则采用基于NSGA-Ⅱ的多目标进化算法求解.数值试验表明我们所提出的算法是有效的.     

基于拉格朗日松弛的手术中心调度算法

为了有效提高手术中心的利用率,降低医院的成本,提高病人满意度,本文提出了基于拉格朗日松弛的手术中心调度算法.首先对问题域进行了描述,以最小化手术中心相关成本和最大化病人满意度为目标,建立数学规划模型.在此基础上,建立可行调度解策略,结合手术中心特有的约束条件,提出基于拉格朗日松弛的手术中心调度方法,并用分枝定界求解子问题.最后,设计不同问题规模的实验,对算法性能进行了评价和对比分析,实验表明,该算法能在可接受的计算时间内得到较好的近优解.     

单机订单接受与加工调度问题的拉格朗日松弛算法

针对不同类型订单加工切换时机器需要准备时间的实际生产情况，研究了单机订单接受与加工调度优化决策问题，旨在最大化企业净收益。鉴于研究问题的强NP难属性，设计了基于拉格朗日松弛理论的启发式算法。首先，该算法通过加入相邻订单相异性约束以提高松弛解质量；其次，应用动态规划递推公式求解拉格朗日松弛问题；最后，利用问题的优化性质并基于贪婪规则构造原问题可行解。不同规模问题的实验结果表明，该算法能在合理计算时间内得到满意的近优解。     

飞行员全动模拟机复训问题求解

针对无训练资源约束的飞行员全动模拟机复训问题,构建双目标整数规划模型对问题进行刻画,通过构造网络流、二部图和加权路等一系列网络规划模型,将原问题转化为最小费用最大流和最长路求解问题,并设计多项式启发式算法对问题进行求解,证明所得解为原问题的非劣解. 最后,实证说明了模型和算法的有效性.     

寻找费用下降最大的闭合回路的算法

针对求解运输问题的经典算法,即闭合回路法和位势法,在寻找费用下降最大的闭合回路时,检验数求解计算量庞大的缺点,通过引入运输问题的检测矩阵及检测量,给出了一种求解运输问题的新算法。该算法对检测矩阵使用匈牙利法及元素求和得到最优解,从而得出最优运输方案。与经典的闭合回路法和位势法相比,在大规模的运输问题上,或基可行解出现退化的运输问题上,新算法更适合求解运输问题。     

卫星网络时隙分配算法与路由规划优化

星间链路的应用在增加网络连通性和提升网络性能方面是至关重要的。然而, 对于大规模、高动态的卫星网络, 实时的星间链路设计和路由规划变得非常有挑战性。为了克服这个难点, 本文研究了动态卫星网络中的时隙分配与路由规划问题, 并将其建模为一个整数线性规划问题。为了降低问题求解的复杂度, 该问题被近似地分解为两个独立的子问题, 包括时隙分配问题与路由规划问题。第一个子问题仍然是一个整数规划问题, 本文结合匹配理论与拉格朗日松弛方法设计了一个低复杂度但是高效的求解算法。然后, 针对第二个子问题, 考虑业务的优先级, 设计了一个低花费的路由算法。最后, 仿真结果验证了方法的可行性与有效性。     

A branch-and-cut approach to portfolio selection with marginal risk control in a linear conic programming framework

Marginal risk represents the risk contribution of an individual asset to the risk of the entire portfolio In this paper, we investigate the portfolio selection problem with direct marginal risk control in a linear conic programming framework. ＇The optimization model involved is a nonconvex quadratically constrained quadratic programming （QCQP） problem. We first transform the QCQP problem into a linear conic programming problem, and then approximate the problem by semidefinite programming （SDP） relaxation problems over some subrectangles. In order to improve the lower bounds obtained from the SDP relaxation problems, linear and quadratic polar cuts are introduced for designing a branch-and-cut algorithm, that may yield an e -optimal global solution （with respect to feasibility and optimality） in a finite number of iterations. By exploring the special structure of the SDP relaxation problems, an adaptive branch-and-cut rule is employed to speed up the computation. The proposed algorithm is tested and compared with a known method in the literature for portfolio selection problems with hundreds of assets and tens of marginal risk control constraints.     

基于航班到达时间窗约束的空域资源分配问题

为解决拥挤空域的资源分配问题,针对航班对计划到达时间变动范围的接受程度不同,定义了航班的延误成本函数,建立了一个基于航班有限到达时间窗的0-1整数规划模型,实现空域资源的最优分配,并开发了以匈牙利算法为核心的程序用于模型求解.以某机场运行数据为例进行仿真实验,结果表明,本文模型的最优解较先到先服务策略(FCFS)的分配结果能降低航班延误成本116％,并且其分配方案能满足每个航班可接受的到达时间窗约束.     

D运输问题

提出一类要求货物尽量在某一给定时间以前如数运抵目的地的运输问题。这是一类含离散目标约束的目标规划问题，我们把它称为D运输问题。建立D运输问题的数学模型，引入可实施解、最优解、解对预警时间的偏差等概念，给出D运输问题的求解方法和一个计算例子。     

蚁群算法进行连续参数优化的新途径

提出用蚁群算法进行连续参数优化的一种方法 .该方法对解的每一个分量的可能的取值组成一个动态的候选组 ,并对候选组中的每一个值记录其信息量 .在蚁群算法的每一次迭代中 ,首先根据信息量选择解分量的初值 ,然后使用交叉、变异操作来确定解的值 .以非线性规划问题为例所进行的计算结果表明 ,该方法比使用遗传算法具有更好的收敛速度和稳定性 ,克服了蚁群算法不太适合求解连续参数优化问题的缺陷 .     

求解二层线性规划问题的混合粒子群算法

结合粒子群优化方法和单纯形法为二层线性规划构造了一个混合粒子群优化算法.算法具有两层结构,其中粒子群算法用以求解上层规划问题,单纯形法用以求解下层规划问题.设计的粒子群在上层决策变量的可行城内搜索最优解,同时通过单纯形法求解下层规划问题得到每个粒子相应的下层规划问题的解.算法通过初始种群可行化,以及步长控制、不可行粒子淘汰等技巧避免了使用罚函数处理约束带来的困难,提高了粒子群优化算法的计算性能.最后,我们给出算法的数值例子并对该算法的计算性能加以分析.     

A LAGRANGIAN RELAXATION APPROACH FOR SUPPLY CHAIN PLANNING WITH ORDER／SETUP COSTS AND CAPACITY CONSTRAINTS

A heuristic approach is developed for supply chain planning modeled as multi-item multi-levelcapacitated lot sizing problems. The heuristic combines Lagrangian relaxation(LR) with local search.Different from existing LR approaches that relax capacity constraints and/or inventory balanceconstraints, our approach only relaxes the technical constraints that each 0-1 setup variable must takevalue 1 if its corresponding continuous variable is positive. The relaxed problem is approximatelysolved by using the simplex algorithm for linear programming, while Lagrange multipliers are updatedby using a surrogate subgradient method that ensures the convergence of the dual problem in case ofthe approximate resolution of the relaxed problem. At each iteration, a feasible solution of the originalproblem is constructed from the solution of the relaxed problem. The feasible solution is furtherimproved by a local search that changes the values of two setup variables at each time. By taking theadvantages of a special stru