运筹学学报

杨光惠, 杨辉, 向淑文

2016, 20(4): 1-10. doi:10.15960/j.cnki.issn.1007-6093.2016.04.001

摘要 ( 789 )

PDF (536KB) ( 534 )

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

主要研究有限理性下参数最优化问题解的稳定性. 即在两类扰动即目标函数及可行集二者, 目标函数、可行集及参数三者分别同时发生扰动的情形下, 对参数最优化问题引入一个抽象的理性函数, 分别建立了参数最优化问题的有限理性模型M, 运用``通有''的方法, 得到了上述两种扰动情形下相应的有限理性模型M的结构稳定性及对\varepsilon-平衡(解)的鲁棒性, 即有限理性下绝大多数的参数最优化问题的解都是稳定的, 并以一个例子说明所得的稳定性结果均是正确的.

一种求解弹性l_2-l_q正则化问题的算法

张勇, 叶万洲

2016, 20(4): 11-20. doi:10.15960/j.cnki.issn.1007-6093.2016.04.002

摘要 ( 1220 )

PDF (872KB) ( 454 )

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

给出了一种求解弹性l_{2}-l_{q}正则化问题的迭代重新加权l_{1}极小化算法, 并证明了由该算法产生的迭代序列是有界且渐进正则的. 对于任何有理数q\in(0,1), 基于一个代数的方法, 进一步证明了迭代重新加权l_{1}极小化算法收敛到弹性l_{2}-l_{q}(0<q<1)正则化问题的稳定点. 最后, 通过稀疏信号恢复的数值实例验证了算法的有效性.

集值映射的一种锥凸性及标量化

李飞, 唐莉萍, 杨新民

2016, 20(4): 21-29. doi:10.15960/j.cnki.issn.1007-6093.2015.04.003

摘要 ( 1327 )

PDF (472KB) ( 511 )

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

在一种集合偏序关系下提出了集值映射的标量锥拟凸概念, 讨论了它与各种锥凸性的关系. 然后对恰当锥拟凸性得到了某种水平集意义下的刻画. 同时建立了集值映射的各种锥凸性通过实值单调增加凸函数表示的标量化复合法则. 最后给出了利用Gerstewitz泛函表示的对集值映射的锥拟凸性的标量化刻画.

优化交货期窗口的两阶段供应链排序问题

张玉忠, 张龙

2016, 20(4): 30-38. doi:10.15960/j.cnki.issn.1007-6093.2016.04.004

摘要 ( 1005 )

PDF (526KB) ( 495 )

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

研究一类优化交货期窗口的两阶段供应链排序问题. 优化交货期窗口是指交货期窗口的开始与结束时刻是决策变量, 不是输入常量. 两阶段是指工件先加工, 后运输: 加工阶段是一台加工机器逐个加工工件；运输阶段是无限台车辆分批运输完工的工件. 工件的开始运输时刻与完工时刻之差定义为工件的储存时间, 且有相应的储存费用. 若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻, 则有相应的提前(延误)惩罚费用. 目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和. 针对单位时间的延误惩罚费用不超过单位时间的储存费用、单位时间的储存费用不超过单位时间的提前惩罚费用的情形, 给出了时间复杂性为O(n^{8})的动态规划算法.

通胀风险下基于HARA效用的DC型养老金计划

常浩, 王春峰, 房振明

2016, 20(4): 39-51. doi:10.15960/j.cnki.issn.1007-6093.2016.04.005

摘要 ( 955 )

PDF (609KB) ( 333 )

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

通货膨胀是养老基金管理过程中最直接最重要的影响因素之一. 假设通胀风险由服从几何布朗运动的物价指数来度量, 且瞬时期望通货膨胀率由Ornstein-Uhlenbeck过程来驱动. 金融市场由n+1种可连续交易的风险资产所构成, 养老基金管理者期望研究和解决通胀风险环境下DC型养老基金在累积阶段的最优投资策略问题, 以最大化终端真实财富过程的期望效用. 双曲绝对风险厌恶(HARA)效用函数具有一般的效用框架, 包含幂效用、指数效用和对数效用作为特例. 假设投资者对风险的偏好程度满足HARA效用, 运用随机最优控制理论和Legendre变换方法得到了最优投资策略的显式表达式.

一类带有MaxEMin评判的补偿型随机规划算法

张艳丽, 马新顺

2016, 20(4): 52-60. doi:10.15960/j.cnki.issn.1007-6093.2016.04.006

摘要 ( 1021 )

PDF (564KB) ( 534 )

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

补偿型随机规划一般假定随机变量的概率分布具有完备信息, 但实际情况往往只能获得部分信息. 针对离散概率具有一类线性部分信息条件而建立了带有MaxEMin评判的两阶段随机规划模型, 借助二次规划和对偶分解方法得到了可行性切割和最优切割, 给出了基于L-型的求解算法, 并证明了算法的收敛性. 通过数值实验表明了算法的有效性.

带有退化效应和序列相关运输时间的排序问题

苗翠霞, 邹娟

2016, 20(4): 61-68. doi:10.15960/j.cnki.issn.1007-6093.2016.04.007

摘要 ( 668 )

PDF (536KB) ( 418 )

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

考虑带有退化效应和序列相关运输时间的单机排序问题. 工件的加工时间是其开工时间的简单线性增加函数. 当机器单个加工工件时, 极小化最大完工时间、(加权)总完工时间和总延迟问题被证明是多项式可解的, EDD序对于极小化最大延迟问题不是最优排序, 另外, 就交货期和退化率一致情形给出了一最优算法. 当机器可分批加工工件时, 分别就极小化最大完工时间和加权总完工时间问题提出了多项式时间最优算法.

机器带不可用时间限制的简单线性恶化供应链排序问题

范静, 鲁习文

2016, 20(4): 69-76. doi:10.15960/j.cnki.issn.1007-6093.2016.04.008

摘要 ( 931 )

PDF (527KB) ( 501 )

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

研究的单机供应链排序问题中, 机器有一个不可用时间限制, 工件的加工时间与恶化率及其开工时间有关, 且工件的加工不可恢复. 一个或多个完工工件可组成一个发送批由车辆发送给客户, 且在机器不可用时间限制之前完工的工件必须在限制开始之时或之前完成发送. 问题的目标是最小化总发送时间与总发送费用之和. 证明问题是NP-难的, 提出了伪多项式时间的动态规划算法. 进一步, 在确定问题目标函数值的上界及下界之后, 设计了一个完全多项式时间近似方案(FPTAS).

定向图的斜 Randi\'{c} 能量

郭立峰, 王力工

2016, 20(4): 77-84. doi:10.15960/j.cnki.issn.1007-6093.2016.04.009

摘要 ( 920 )

PDF (505KB) ( 358 )

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

图G是一个简单无向图, G^\sigma 是图 G 在定向 \sigma 下的定向图, G 被称作 G^\sigma 的基础图. 定向图G^\sigma 的斜 Randi\'{c} 矩阵是实对称n\times n矩阵
R_{s}(G^\sigma)=[(r_s)_{ij}]. 如果(v_{i},v_{j})是G^\sigma 的弧, 那么(r_s)_{ij}=(d_id_j)^{-\frac{1}{2}} 且(r_s)_{ji}=-(d_id_j)^{-\frac{1}{2}}, 否则(r_s)_{ij}=(r_s)_{ji}=0. 定向图G^\sigma 的斜Randi\'{c}~能量RE_s(G^\sigma)是指R_{s}(G^\sigma) 的所有特征值的绝对值的和. 首先刻画了定向图G^\sigma 的斜Randi\'{c}矩阵R_{s}(G^\sigma)的特征多项式的系数. 然后给出了定向图G^\sigma 的斜Randi\'{c}能量RE_s(G^\sigma) 的积分表达式. 之后给出了RE_s(G^\sigma) 的上界. 最后计算了定向圈的斜~Randi\'{c}~能量RE_s(G^\sigma).

非单调带参数Perry-Shanno无记忆拟牛顿法的收敛性

杭丹, 颜世建

2016, 20(4): 85-92. doi:10.15960/j.cnki.issn.1007-6093.2016.04.010

摘要 ( 979 )

PDF (526KB) ( 354 )

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

给出了一种非单调带参数的Perry-Shanno无记忆拟牛顿法, 对于目标函数为凸函数, 在参数满足适当范围的情况下, 证明了算法的全局收敛性.

带有运输且加工具有灵活性的无等待流水作业排序问题

仲维亚, 马晓茹

2016, 20(4): 93-101. doi:10.15960/j.cnki.issn.1007-6093.2016.04.011

摘要 ( 733 )

PDF (770KB) ( 415 )

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

研究一类带有运输且加工具有灵活性的两阶段无等待流水作业排序问题, 其中每阶段只有一台机器, 每个工件有两道工序需要依次在两台机器上加工, 工件在两台机器上的加工及两道工序之间不允许等待. 给出两种近似算法, 并分别分析其最坏情况界. 第一种算法是排列排序, 证明了最坏情况界不超过5/2; 第二种算法将工件按照两道工序加工时间之和的递增顺序排序, 证明其最坏情况界不超过2. 最后, 通过数值模拟比较算法的性能. 对问题中各参数取不同值的情况, 分别生成若干个实例, 用算法得到的解与最优解的下界作比值, 通过分析这些比值的最大值、最小值和平均值来比较上述两个算法的性能.

两伪币的搜索问题

武晓辉, 李胜家

2016, 20(4): 102-108. doi:10.15960/j.cnki.issn.1007-6093.2016.04.012

摘要 ( 758 )

PDF (1777KB) ( 620 )

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

考虑两伪币的搜索问题: 给定外观相同的n个硬币, 其中有两个比较重的伪币, 通过等臂天平在尽可能少的称量次数下去找出两个伪币. L^{(2)}(n)为最坏情况下找到两伪币的最小称量步数. 对于任意的 n\geq2, 满足\lceil \log_3\binom{n}{2}\rceil \leq L^{(2)}(n)\leq\lceil \log_3\binom{n}{2}\rceil+1. 猜想信息理论下界均可达. 通过一个新的方法扩大了满足信息理论下界的n的取值范围.

可转包两台流水作业机排序的近似算法

陈光亭, 陈蕾, 张安, 陈永

2016, 20(4): 109-114. doi:10.15960/j.cnki.issn.1007-6093.2016.04.013

摘要 ( 786 )

PDF (517KB) ( 409 )

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

研究可转包的两台流水作业机排序问题, 目标是极小化最大完工时间和总外包费用之和. 首先给出最坏情况界为2的近似算法, 接着对工件满足有序化约束的情形给出最坏情况界为\frac{3}{2}的改进算法, 以上算法界均为紧界.

一个特殊6点图Q与nK_{1}, P_{n}及C_{n}的联图交叉数

周志东, 李龙

2016, 20(4): 115-126. doi:10.15960/j.cnki.issn.1007-6093.2016.04.014

摘要 ( 785 )

PDF (1127KB) ( 326 )

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

图的交叉数是图的一个重要参数，研究图的交叉数问题是拓扑图论中的前沿难题. 确定图的交叉数是~NP-难问题, 因为其难度, 能够确定交叉数的图类很少. 通过圆盘画法途径, 确定了一个特殊6点图与n个孤立点nK_{1}, 路P_{n}及圈C_{n}的联图的交叉数分别是cr(Q+nK_{1})=Z(6,n)+2\lfloor\frac{n}{2} \rfloor, cr(Q+P_{n})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor+1及cr(Q+C_{n})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor+3.

当期目录