运筹学学报

李建荣

2013, 17(4): 1-10.

摘要 ( 1724 )

PDF (550KB) ( 2078 )

参考文献 | 相关文章 | 多维度评价

在双方市场中定义的博弈概念，可以使市场同方参与者的收益同时达到最大. 这种最优化存在的理论依据是选择匹配的稳定性. 用博弈论的分析与证明方法研究多对一双方匹配市场中的最优化. 在替代偏好和LAD(Law of Aggregate Demend)偏好下，证明由企业作选择的选择函数一定是个稳定匹配，由工人做选择的选择函数也是一个稳定匹配.

随机市场中均值-方差模型最优投资策略的时间不相容性及其修正

李刚, 陈志平

2013, 17(4): 11-23.

摘要 ( 1583 )

PDF (550KB) ( 688 )

参考文献 | 相关文章 | 多维度评价

由于方差算子在动态规划意义下不可分，导致随机市场中多期均值-方差模型的最优投资策略不满足时间相容性，即Bellman最优性原理. 为此，首先提出了随机市场中比Bellman最优性原理更弱的时间相容性，并证明在投资区间的任意中间时刻，当投资者的财富不超过某一给定的财富阈值时，最优投资策略满足弱时间相容性；当投资者的财富超过该阈值时，最优投资策略将不再是弱时间相容的，且导致投资者变为非理性，即他会同时极小化终期财富的均值和方差. 在这种情形下，通过放松自融资约束，对最优投资策略进行了修正，使得其满足：修正策略可使投资者回归理性；相对于终期财富，修正策略可以获得与最优投资策略相同的均值和方差. 在策略修正过程中，投资者可以从市场中获得一个严格正的现金流. 这些结果表明修正策略要优于原最优投资策略, 拓展了现有关于确定市场下多期均值-方差模型的求解以及策略时间相容性的结论.

控制系统生存核的逼近算法

陈征, 高岩

2013, 17(4): 24-32.

摘要 ( 1093 )

PDF (840KB) ( 609 )

参考文献 | 相关文章 | 多维度评价

生存核的计算是控制理论中的一个重要研究方向. 给出了一种计算一般离散控制系统生存核的新算法. 基于机器学习的方法，给出了逼近生存核的算法. 并在一定条件下，证明了此算法的收敛性. 此算法在一定程度上避免了计算量随控制空间的维数增长而指数增长的问题. 最后，给出具体的实际例子来说明算法的有效性.

考虑不完全检测的冲击模型最优维修策略

李玲, 成国庆

2013, 17(4): 33-42.

摘要 ( 1105 )

PDF (719KB) ( 549 )

参考文献 | 相关文章 | 多维度评价

针对制造系统中设备检测不完全的情形，研究基于不完全检测的冲击模型的周期检测、维修联合策略. 通过定期检测获知系统的劣化状态以进行必要的预防性维修. 在假设系统是退化的且有k个不同故障状态的条件下，以最小化系统运行成本为目标，以检测周期T、系统更换前故障次数$N$为联合决策变量，利用更新过程理论建立了系统平均费用率C(T,N)的数学模型，并且给出最优联合策略的数值算法. 最后借助数值例子演示了该模型，分析了检测水平对系统运行成本的影响.

基于动态规划的高阶隐马氏模型推广的Viterbi算法

叶飞, 王翼飞

2013, 17(4): 43-55.

摘要 ( 1650 )

PDF (696KB) ( 771 )

参考文献 | 相关文章 | 多维度评价

首先通过Hadar等价变换方法将高阶隐马氏模型转换为与之等价的一阶向量值隐马氏模型，然后利用动态规划原理建立了一阶向量值隐马氏模型的Viterbi算法，最后通过高阶隐马氏模型和一阶向量值隐马氏模型之间的等价关系建立了高阶隐马氏模型基于动态规划推广的Viterbi算法. 研究结果在一定程度上推广了几乎所有隐马氏模型文献中所涉及到的解码问题的Viterbi算法，从而进一步丰富和发展了高阶隐马氏模型的算法理论.

基于重新排序的退化工件最小化总延误时间问题

许小艳, 慕运动, 郝~~赟

2013, 17(4): 56-62.

摘要 ( 1148 )

PDF (590KB) ( 706 )

参考文献 | 相关文章 | 多维度评价

考虑了错位限制下的含有退化工件的重新排序问题，即工件的实际加工时间看作是工件开工时间的线性函数. 重新排序就是在原始工件已经按照某种规则使目标函数达到最优时有一新工件集到达，新工件的安排使得原始工件重新排序进而产生错位. 研究了最大序列错位和总序列错位限制下的退化工件最小化总延误时间问题，其最优排序的结构性质是使得原始工件集和新工件集中的工件是按加工率alpha_j非减的序列排列，基于此通过分阶段排序和动态规划方法给出了两个问题的多项式时间的最优算法.

具有等级约束的三台机排序问题的可中断在线算法

姚然, 陈光亭, 张安, 陈永

2013, 17(4): 63-68.

摘要 ( 1176 )

PDF (694KB) ( 592 )

参考文献 | 相关文章 | 多维度评价

研究具有等级约束的三台机在线排序问题. 机器和工件的等级数均为1或2，工件只能在等级数不超过自身等级的机器上加工，且加工允许中断，目标是极小化最大工件完工时间. 如果有两台机器等级为1，给出竞争比为3/2的在线算法，并证明算法是最好可能的；如果只有一台等级为1的机器，也给出竞争比为3/2的在线算法.

带投资约束且p不确定的推广p-中位问题

蒋建林, 李雪, ASSANI Saeed, 吴仆, 王璨璨

2013, 17(4): 69-79.

摘要 ( 1382 )

PDF (820KB) ( 665 )

参考文献 | 相关文章 | 多维度评价

p-中位问题是设施选址中的一个经典模型，在交通、物流等领域有着广泛应用. 在经典p-中位问题的基础上提出一种p不确定的推广p-中位问题，并且加上总投资约束，使得此推广模型更加实用. 针对此推广模型，提出三种启发式算法：简单启发式算法、变邻域搜索算法和改进的遗传算法. 数值实验结果表明变邻域搜索算法和改进的遗传算法在求解此推广模型时是有效的.

集值优化强有效解的广义二阶锥方向导数刻画

徐义红, 孙鑫, 汪涛

2013, 17(4): 80-86.

摘要 ( 1106 )

PDF (577KB) ( 761 )

参考文献 | 相关文章 | 多维度评价

在实赋范线性空间中考虑集值优化问题的强有效性. 借助Henig扩张锥和基泛函的性质，利用广义二阶锥方向相依导数，得到受约束于集值映射的优化问题，取得强有效元的二阶最优性必要条件. 当目标函数为近似锥-次类凸映射时, 利用强有效点的标量化定理，得到集值优化问题，取得强有效元的二阶充分条件.

一类特殊二次分配问题的线性化求解新方法

张惠珍, 魏欣, 马良

2013, 17(4): 87-95.

摘要 ( 1168 )

PDF (581KB) ( 641 )

参考文献 | 相关文章 | 多维度评价

许多抽象于实际的二次分配问题, 其流矩阵与距离矩阵中有很多零元素, 求解该类二次分配问题时, 可通过先行利用零元素的信息减小问题规模, 缩短计算时间. 以二次分配问题的线性化模型为基础, 提出了一种求解流矩阵与距离矩阵中同时存在大量零元素的二次分配问题新方法, 不仅从理论上证明了方法的可行性, 而且从实验的角度说明了该方法比以往方法更加优越.

工件按加工长度不增序到达的最小化最大流程在线分批排序

焦成文, 李文华

2013, 17(4): 96-102.

摘要 ( 1274 )

PDF (568KB) ( 629 )

参考文献 | 相关文章 | 多维度评价

研究单处理机工件按加工长度不增顺序到达的在线分批排序问题. 工件按时在线到达, 目标是最小化最大流程. 流程时间是指工件的完工时间与到达时间的差值, 它体现了工件在系统内的逗留时间. 对于批容量有界的情形, 给出了一个竞争比为$\frac{1+\sqrt{5}}{2}$的最好可能的在线算法; 对于批容量无界的情形, 给出了一个竞争比为$\sqrt{2}$的最好可能的在线算法.

几类积图的团染色数

单而芳, 叶婷婷

2013, 17(4): 103-108.

摘要 ( 1171 )

PDF (955KB) ( 932 )

参考文献 | 相关文章 | 多维度评价

设G=(V, E)为简单图, V和E分别表示图的点集和边集. 图G的一个k-团染色是指点集V到色集{1, 2,...,k}的一个映射, 使得G的每个至少含两个点的极大团都至少有两种颜色. 分别给出了任意两个图的团色数与它们通过笛卡尔积、Kronecker积、强直积或字典积运算后得到的积图的团色数之间的关系.

带时变生产成本的易变质经济批量模型的最优策略分析

柏庆国, 徐健腾, 张玉忠, 徐贤浩

2013, 17(4): 109-122.

摘要 ( 1443 )

PDF (577KB) ( 1401 )

参考文献 | 相关文章 | 多维度评价

考虑了具有时变生产成本的易变质产品经济批量模型. 有限计划期内，单位生产成本、生产率以及需求率假定为时间的连续函数，生产固定成本则具有遗忘效应现象. 当不允许缺货时，建立了以总成本最小为目标的混合整数优化模型并证明了此问题最优解的相关性质. 对于此问题的特殊情形，将成本函数中的离散型变量松弛为连续型变量, 通过分析其最优解的存在性及唯一性, 求解了此最优解，将其作为初始值设计了求取一般情形最优解的有效算法. 最后通过算例验证了理论结果的有效性.

分数k-因子临界图的条件

李巧, 刘岩

2013, 17(4): 123-130.

摘要 ( 1122 )

PDF (398KB) ( 579 )

参考文献 | 相关文章 | 多维度评价

设G是一个连通简单无向图，如果删去G的任意k个顶点后的图有分数完美匹配，则称G是分数k-因子临界图. 给出了G是分数k-因子临界图的韧度充分条件与度和充分条件，这些条件中的界是可达的，并给出G是分数k-因子临界图的一个关于分数匹配数的充分必要条件.

当期目录