运筹学学报

Select

1. 前言

李敏, 吴晨晨, 徐大川

运筹学学报 2022, 26 (1): 0-0.

摘要（1892）

PDF（pc）（243KB）（217）

相关文章 | 多维度评价 | 评论（0）

Select

2. 小批量随机块坐标下降算法

胡佳, 郭田德, 韩丛英

运筹学学报 2022, 26 (1): 1-22. DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.001

摘要（2432）

HTML （408）

PDF（pc）（986KB）（420）

针对机器学习中广泛存在的一类问题：结构化随机优化问题（其中“结构化”是指问题的可行域具有块状结构，且目标函数的非光滑正则化部分在变量块之间是可分离的），我们研究了小批量随机块坐标下降算法（mSBD）。按照求解非复合问题和复合问题分别给出了基本的mSBD和它的变体，对于非复合问题，分析了算法在没有一致有界梯度方差假设情况下的收敛性质。而对于复合问题，在不需要通常的Lipschitz梯度连续性假设条件下得到了算法的收敛性。最后通过数值实验验证了mSBD的有效性。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

3. 电商生态系统四方演化博弈研究

王辛辛, 程郁琨, 田晓明, 许智琪, 陈瑾冕

运筹学学报 2022, 26 (1): 23-42. DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.002

摘要（2542）

HTML （29）

PDF（pc）（1491KB）（432）

受启发于近些年频繁曝出的消费者权益保护问题，为探析消费者行为对电商生态系统中其他群体策略选择的影响，本文基于演化博弈理论，考虑消费者的投诉行为，构建由政府、电商平台、商家以及消费者组成的四方演化博弈模型；讨论各方主体的策略选择，分析策略组合稳定点，并应用MATLAB工具进行仿真模拟实验。经上述研究，本文得出结论：消费者的投诉行为有利于促进政府严格监管、电商平台严格管理、商家诚信经营。由此，建议政府和电商平台充分发挥监督管理作用，以更好地保障消费者的合法权益，并遏制消费者的恶意投诉行为，从而实现电商生态系统的稳定可持续发展。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

4. 非负约束稀疏优化问题的一个等价性条件

吕亚星, 韩美佳, 黄子麟, 朱文兴

运筹学学报 2022, 26 (1): 43-59. DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.003

摘要（2217）

HTML （20）

PDF（pc）（874KB）（228）

加权l₁最小化是稀疏优化的主流方法之一。本文对带非负约束的l₀最小化问题与加权l₁最小化问题的解之间的关系进行了研究，给出了加权l₁最小化问题的约束矩阵和目标函数的系数是"s-权优"的定义，并通过该定义给出了加权l₁最小化问题的解是带非负约束的l₀最小化问题的解的条件。进一步，本文给出了"s-权优"的充分条件及其具体表示形式，并对其上下界进行了可计算的有效估计。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

5. 限制性多源点偏心距增广问题

李建平, 蔡力健, 李陈筠然, 潘鹏翔

运筹学学报 2022, 26 (1): 60-68. DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.004

摘要（2198）

HTML （14）

PDF（pc）（797KB）（180）

给定一个赋权图$G=（V，E；w，c）$以及图$G$的一个支撑子图$G_{1}=（V，E_{1}）$，这里源点集合$S=\{s_{1}，s_{2}，\cdots，s_{k}\}\subseteq V$，权重函数$w：E\rightarrow\mathbb{R}^{+}$，费用函数$c：E\setminus E_{1}\rightarrow\mathbb{Z}^{+}$和一个正整数$B$，本文考虑两类限制性多源点偏心距增广问题，具体叙述如下：（1）限制性多源点最小偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$，满足约束条件$c（E_{2}）$$\leq$$B$，目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最小值达到最小；（2）限制性多源点最大偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$，满足约束条件$c（E_{2}）$$\leq$$B$，目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

6. 经典一维装箱问题近似算法的研究进展

陈婳, 张国川

运筹学学报 2022, 26 (1): 69-84. DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.005

摘要（2643）

HTML （52）

PDF（pc）（946KB）（464）

自20世纪70年代开始，随着计算复杂性理论的建立，近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象，装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强，广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外，装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天，对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型，简述若干经典Fit算法的发展历程，分析基于线性规划松弛的近似方案的主要思路，总结当前的研究现状并对未来的研究提供一些参考建议。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

7. 带基数约束的次模+超模(BP)函数最大化问题的流算法

连月芳, 张真宁, 赵中睿, 堵丁柱

运筹学学报 2022, 26 (1): 85-98. DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.006

摘要（2559）

HTML （20）

PDF（pc）（928KB）（282）

本文研究在基数约束下具有单调性的次模+超模函数最大化问题的流模型。该问题在数据处理、机器学习和人工智能等方面都有广泛应用。借助于目标函数的收益递减率（$\gamma$），我们设计了单轮读取数据的过滤-流算法，并结合次模、超模函数的全局曲率（$\kappa^{g}$）得到算法的近似比为$\min\left\{\frac{（1-\varepsilon）\gamma}{2^{\gamma}}，1-\frac{\gamma}{2^{\gamma}（1-\kappa^{g}）^{2}}\right\}$。数值实验验证了过滤-流算法对BP最大化问题的有效性并且得出：次模函数和超模函数在同量级条件下，能保证在较少的时间内得到与贪婪算法相同的最优值。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

8. 带惩罚μ-相似Bregman散度k-均值问题的初始化算法

刘文杰, 张冬梅, 张鹏, 邹娟

运筹学学报 2022, 26 (1): 99-112. DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.007

摘要（2020）

HTML （11）

PDF（pc）（887KB）（159）

$k$-均值问题是聚类中的经典问题，亦是NP-难问题。如果允许数据点不聚类，而是支付惩罚费用，则引出带惩罚的$k$-均值问题。本文将带惩罚的$k$-均值问题从欧氏距离推广到更一般的$\mu$-相似Bregman散度，研究了带惩罚$\mu$-相似Bregman散度$k$-均值问题的初始化算法。本文给出的初始化算法，近似比与$\mu$和数据点惩罚最大值与最小值的比例$r$相关。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

9. 带惩罚的相同容量k-均值问题的局部搜索算法

剧嘉琛, 刘茜, 张昭, 周洋

运筹学学报 2022, 26 (1): 113-124. DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.008

摘要（2129）

HTML （223）

PDF（pc）（902KB）（174）

经典$k$-均值问题是一类应用广泛的聚类问题，它是指给定$\mathbb{R}^d$中观测点集合$D$和整数$k$，目的是在空间中寻找$k$个点作为中心集合$S$，使得集合$D$中的每个观测点到$S$中离它最近的中心的距离平方求和最小。这是个NP-难问题。经典$k$-均值问题有很多推广，本文研究的带惩罚的相同容量$k$-均值问题就是其中之一。与经典$k$-均值问题相比，惩罚性质是指每个观测点都给定惩罚费用，当某个观测点到最近中心的距离大于惩罚费用时，其对目标函数的贡献就用该观测点的惩罚费用来代替最近的距离的平方，相同容量约束要求每个中心至多连接$U$个观测点。针对这种问题，我们设计了局部搜索算法，该算法在至多选取$（3+\alpha）k$个中心的情况下，可以达到$\beta$-近似，其中，参数$\alpha>34$，$\beta>\frac{\alpha+34}{\alpha-34}$。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

10. 关于带运输的单机调度在线问题的研究

王银玲, 韩鑫, 邵欣欣

运筹学学报 2022, 26 (1): 125-133. DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.009

摘要（2225）

HTML （12）

PDF（pc）（779KB）（221）

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达，系统中有一台运输机，该运输机每次最多运输$k$个工件，每个工件需要先在单机上完成加工，然后再被运输机运往目的地，问题的优化目标为最小化完工时间，即所有工件被加工完并且运往目的地的时间最短。针对该问题，作者研究了工件满足一致性条件的模型，并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法，并且证明该算法是最优在线算法。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

11. 单机上带有可变前瞻区间的分批在线排序问题

王利博, 李文华, 余丹

运筹学学报 2022, 26 (1): 134-140. DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.010

摘要（2168）

HTML （11）

PDF（pc）（757KB）（199）

本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达，目标是最小化时间表长。在时刻$t$，在线算法能够预见到$（t，t+\Delta（t）]$内到达工件的信息，这里前瞻区间的长度$\Delta（t）=\beta p_{\max}（t）$并非定长，其中$p_{\max}（t）$表示在$t$时刻及之前到达工件的最大加工时长，$\beta\in（0，1）$是常数。本文对于工件加工时长的一般情形，给出了当 0<β≤1/6 时最好可能的在线算法；对于工件加工时长被限制在一个区间的情形，给出了当 0<β<1 时最好可能的在线算法。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

12. 服务台不可靠的重试排队系统均衡分析

张钰, 王金亭

运筹学学报 2022, 26 (2): 1-15. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.001

摘要（2647）

HTML （141）

PDF（pc）（1036KB）（244）

本文研究服务台不可靠的M/M/1常数率重试排队系统中顾客的均衡进队策略, 其中服务台在正常工作和空闲状态下以不同的速率发生故障。在该系统中, 服务台前没有等待空间, 如果到达的顾客发现服务台处于空闲状态, 该顾客可占用服务台开始服务。否则, 如果服务台处于忙碌状态, 顾客可以选择留下信息, 使得服务台在空闲时可以按顺序在重试空间中寻找之前留下信息的顾客进行服务。当服务台发生故障时, 正在被服务的顾客会发生丢失, 且系统拒绝新的顾客进入系统。根据系统提供给顾客的不同程度的信息, 研究队长可见和不可见两种信息情形下系统的稳态指标, 以及顾客基于收入-支出函数的均衡进队策略, 并建立单位时间内服务商的收益和社会福利函数。比较发现, 披露队长信息不一定能提高服务商收益和社会福利。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

13. 随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用

吕袈豪, 罗洪林, 杨泽华, 彭建文

运筹学学报 2022, 26 (2): 16-30. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.002

摘要（2711）

HTML （59）

PDF（pc）（895KB）（336）

针对具有多块可分结构的非凸优化问题提出了一类新的随机Bregman交替方向乘子法，在周期更新规则下, 证明了该算法的渐进收敛性; 在随机更新的规则下, 几乎确定的渐进收敛性得以证明。数值实验结果表明, 该算法可有效训练具有离散结构的支持向量机。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

14. 随机二阶锥二次规划逆问题的SAA方法

王博, 初丽, 张立卫, 张宏伟

运筹学学报 2022, 26 (2): 31-44. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.003

摘要（2742）

HTML （60）

PDF（pc）（829KB）（359）

本文讨论一类随机的二阶锥二次规划逆问题, 该模型是一个含有二阶锥互补约束的随机二次规划模型, 对解释部分实际问题有着一定的优势。为了求解该模型, 本文引入了随机抽样技术和互补约束光滑化近似技术, 得到问题的近似子问题。本文证明, 只要子问题的解是存在且收敛的, 则该极限以概率一是原问题的C-稳定点; 若严格互补条件和二阶必要性条件成立, 则该极限以概率1是原问题的M-稳定点。一个简单的数值实验验证了该算法具有一定的可行性。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

15. 双边配给问题的Shapley解及其在博物馆通票问题中的应用

宫豆豆, 徐根玖, 侯东爽

运筹学学报 2022, 26 (2): 45-54. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.004

摘要（2690）

HTML （17）

PDF（pc）（816KB）（268）

双边配给问题描述了现实生活中一类带有二部图结构的稀缺资源配置问题, 例如, 在自然灾害期间救援物资的配给; 电力和天然气等自然资源按需分配; 高校引进人才调配等。本文通过求解线性规划, 并从联盟边际贡献的角度出发定义了双边配给问题的一个Shapley解。之后, 通过合作对策模型和解的公理化方法说明新解的合理性。首先, 建立双边配给问题的合作对策模型, 论证了新解与双边配给合作对策的Shapley值一致; 其次, 证明了Shapley解是唯一满足优先一致性的有效配给方案。最后, 将Shapley解应用于博物馆通票问题的研究, 探讨了博物馆合作制定通票后所得单票和通票收益的分配方式。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

16. 工件的释放时间和加工时间具有一致性的单机在线排序问题研究

李文杰, 李钰晶, 刘海玲

运筹学学报 2022, 26 (2): 55-63. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.005

摘要（2642）

HTML （17）

PDF（pc）（835KB）（145）

工件的释放时间和加工时间具有一致性, 是指释放时间大的工件其加工时间不小于释放时间小的工件的加工时间, 即若$r_{i}\geq r_{j}$, 则$p_{i}\geq p_{j}$。本文在该一致性约束下, 研究最小化最大加权完工时间单机在线排序问题, 和最小化总加权完工时间单机在线排序问题, 并分别设计出$\frac{\sqrt{5}+1}{2}$-竞争的最好可能在线算法。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

17. 修正PRP共轭梯度方法求解无约束最优化问题

张慧玲, 赛·闹尔再, 吴晓云

运筹学学报 2022, 26 (2): 64-72. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.006

摘要（2953）

HTML （22）

PDF（pc）（823KB）（376）

基于著名的PRP共轭梯度方法，利用CG_DESCENT共轭梯度方法的结构，本文提出了一种求解大规模无约束最优化问题的修正PRP共轭梯度方法。该方法在每一步迭代中均能够产生一个充分下降的搜索方向，且独立于任何线搜索条件。在标准Wolfe线搜索条件下，证明了修正PRP共轭梯度方法的全局收敛性和线性收敛速度。数值结果展示了修正PRP方法对给定的测试问题是非常有效的。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

18. 工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

毕春燕, 万龙, 罗文昌

运筹学学报 2022, 26 (2): 73-82. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.007

摘要（2601）

HTML （12）

PDF（pc）（861KB）（214）

本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$时, 该算法近似比为3, 当接受工件个数小于$(m-1)$时, 该算法近似比为$(2+\rho)$, 其中$\rho$为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

19. 一种求解二次约束二次规划问题的自适应全局优化算法

黄小利, 高岳林, 张博, 刘霞

运筹学学报 2022, 26 (2): 83-100. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.008

摘要（2742）

HTML （14）

PDF（pc）（871KB）（293）

为了更好地解决二次约束二次规划问题(QCQP), 本文基于分支定界算法框架提出了自适应线性松弛技术, 在理论上证明了这种新的定界技术对于解决(QCQP)是可观的。文中分支操作采用条件二分法便于对矩形进行有效剖分; 通过缩减技术删除不包含全局最优解的部分区域, 以加快算法的收敛速度。最后, 通过数值结果表明提出的算法是有效可行的。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

20. 最短路博弈群体单调分配方案构造

陈泽融, 肖汉

运筹学学报 2022, 26 (2): 101-110. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.009

摘要（2725）

HTML （21）

PDF（pc）（864KB）（193）

群体单调分配方案(Population Monotonic Allocation Scheme, 后简称PMAS)是合作博弈的一类分配机制。在合作博弈中, PMAS为每一个子博弈提供一个满足群体单调性的核中的分配方案, 从而保证大联盟的动态稳定性。本文主要贡献为利用线性规划与对偶理论构造与求解一类基于最短路问题的合作博弈(最短路博弈)的PMAS。我们首先借助对偶理论, 利用组合方法为最短路博弈构造了一个基于平均分摊思想的PMAS。然后借鉴计算核仁的Maschler方案, 将PMAS的存在性问题转化为一个指数规模的线性规划的求解问题, 并通过巧妙的求解得到了与之前组合方法相同的最短路博弈的PMAS。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

21. 平面图的强边染色

卜月华, 张恒

运筹学学报 2022, 26 (2): 111-127. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.010

摘要（2702）

HTML （14）

PDF（pc）（1349KB）（188）

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)\geq5$, $\Delta(G)\geq6$且$5$-圈不相交的平面图的强边色数至多是$4\Delta(G)-1$。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

22. 求解张量随机互补问题的光滑牛顿算法

单锡泉, 李梅霞, 刘瑾瑜

运筹学学报 2022, 26 (2): 128-136. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.011

摘要（2678）

HTML （10）

PDF（pc）（785KB）（168）

近年来, 越来越多的人意识到随机互补问题在经济管理中具有十分重要的作用。有学者已将随机互补问题由矩阵推广到张量, 并提出了张量随机互补问题。本文通过引入一类光滑函数, 提出了求解张量随机互补问题的一种光滑牛顿算法, 并证明了算法的全局和局部收敛性, 最后通过数值实验验证了算法的有效性。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

23. k圈图的最大Laplace分离度

余桂东, 阮征, 舒阿秀

运筹学学报 2022, 26 (2): 137-142. DOI: 10.15960/j.cnki.issn.1007-6093.2022.02.012

摘要（2608）

HTML （10）

PDF（pc）（1098KB）（136）

设$ G $是一个$ n $阶$ k $圈图, $ k $圈图为边数等于顶点数加$ k-1 $的简单连通图。$ \mu_{1}(G) $、$ \mu_{2}(G) $分别记为图$ G $的Laplace矩阵的最大特征值和次大特征值, 图$ G $的Laplace分离度定义为$ S_{L}(G)=\mu_{1}(G)-\mu_{2}(G) $。本文研究了给定阶数的$ k $圈图的最大Laplace分离度, 并刻画了相应的极图, 其结果推广了已有当$ k=1, 2, 3 $时的结论。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

24. 布德施恩运筹策怀瑾握瑜滋蕙兰——庆祝姚恩瑜教授八十华诞

运筹学学报 2022, 26 (3): 0-0.

摘要（2000）

HTML （392）

PDF（pc）（1750KB）（496）

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

25. k-均值问题的差分隐私算法综述

袁藩, 徐大川, 张冬梅

运筹学学报 2022, 26 (3): 1-16. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.001

摘要（7581）

HTML （826）

PDF（pc）（993KB）（1128）

$k$-均值问题是机器学习和组合优化领域十分重要的问题。它是经典的NP-难问题, 被广泛的应用于数据挖掘、企业生产决策、图像处理、生物医疗科技等领域。随着时代的发展, 人们越来越注重于个人的隐私保护:在决策通常由人工智能算法做出的情况下, 如何保证尽可能多地从数据中挖掘更多信息，同时不泄露个人隐私。近十年来不断有专家学者研究探索带隐私保护的$k$-均值问题, 得到了许多具有理论指导意义和实际应用价值的结果, 本文主要介绍关于$k$-均值问题的差分隐私算法供读者参考。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

26. 以商圈为中心的O2O动态外卖配送路径优化模型与算法

周成昊, 吕博轩, 周翰宇, 鲁海燕

运筹学学报 2022, 26 (3): 17-30. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.002

摘要（7591）

HTML （526）

PDF（pc）（1042KB）（951）

针对线上到线下(Online to Offline，O2O) 外卖路径优化问题，综合考虑其动态配送需求、货物区分等特点以及时间窗、载货量等约束条件，将商圈看作配送中心，将快递员数量与快递员总行驶时间作为最小化目标，提出了以商圈为中心的O2O动态外卖配送路径优化模型。采用周期性处理新订单的方法将相应的快递员路径的动态调整问题转化为一系列静态TSP子问题，设计了一种分阶段启发式实时配送路径优化算法框架，并给出了一个具体算法和一个数值计算实例。在VRP通用算例的基础上，以商圈为中心生成测试算例，对本文算法进行仿真实验，并与其他算法比较。结果表明：本文算法能充分利用新订单附近的快递员进行配送，并优化其配送路径，有效减少了快递员数量与快递员总行驶时间。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

27. 一个基于张量火车分解的张量填充方法及在图像恢复中的应用

谢文蕙, 凌晨, 潘晨健

运筹学学报 2022, 26 (3): 31-43. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.003

摘要（7333）

HTML （65）

PDF（pc）（3899KB）（706）

低秩张量填充在数据恢复中有广泛应用, 基于张量火车(TT) 分解的张量填充模型在彩色图像和视频以及互联网数据恢复中应用效果良好。本文提出一个基于三阶张量TT分解的填充模型。在模型中, 引入稀疏正则项与时空正则项, 分别刻画核张量的稀疏性和数据固有的块相似性。根据问题的结构特点, 引入辅助变量将原模型等价转化成可分离形式, 并采用临近交替极小化(PAM) 与交替方向乘子法(ADMM) 相结合的方法求解模型。数值实验表明, 两正则项的引入有利于提高数据恢复的稳定性和实际效果, 所提出方法优于其他方法。在采样率较低或图像出现结构性缺失时, 其方法效果较为显著。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

28. 单位无穷范数下边权有界的最小支撑树逆最优值问题

张斌武, 关秀翠

运筹学学报 2022, 26 (3): 44-56. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.004

摘要（7130）

HTML （45）

PDF（pc）（888KB）（512）

研究了单位$l_{\infty}$范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$, 支撑树$T^0$, 下界向量$\bm{l}$, 上界向量$\bm{u}$及数值$K$, 寻求一个新的边权向量$\bm{\bar{w}}$满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$, 且$T^0$是在向量$\bm{\bar{w}}$下权值为$K$的一个最小支撑树, 目标是在单位$l_{\infty}$范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$的强多项式时间算法。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

29. 优先序约束的排序问题：基于最大匹配的近似算法

张安, 陈永, 陈光亭, 陈占文, 舒巧君, 林国辉

运筹学学报 2022, 26 (3): 57-74. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.005

摘要（2157）

HTML （296）

PDF（pc）（902KB）（181）

本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题，目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时，两类问题在一般优先图上都是强NP-困难的，而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界，并基于许可工件之间的最大匹配设计近似算法，其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题，我们在理论上证明了算法的近似比为$2-\frac 2m$，其中$m$是机器数目。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

30. 最小化碳排放的共享单车迁移问题

苏兵, WyattCarlson, 范佳彬, GAO Arthur, 邵艳君, 林国辉

运筹学学报 2022, 26 (3): 75-91. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.006

摘要（2194）

HTML （47）

PDF（pc）（1155KB）（303）

本文考虑共享单车迁移问题, 它可看作是经典旅行售货商问题的一个新颖变形, 不同的是其目标函数为最小化碳排放。其中, 碳排放利用单车负载与其行驶路程的乘积进行刻画。我们提出了两个启发式算法：贪心和基于TSP的算法, 每个算法的核心思想均是优先减少单车负载。从理论上证明算法的可行性并给出数据实验以验证算法的实际性能。数据实验结果表明贪心算法优于基于TSP的算法, 这为共享单车企业进行日常单车分配提供了理论依据。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

31. 两台同类机排序问题SPT算法的最坏情况比

龚铭炀, 谈之奕, 严羽洁

运筹学学报 2022, 26 (3): 92-108. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.007

摘要（2107）

HTML （13）

PDF（pc）（821KB）（179）

本文研究以工件总完工时间为目标函数的两台同类机排序问题, 给出了SPT算法以两台机器速度比为参数的最坏情况比, 使该算法的常数最坏情况比上界与下界的差距由0.430 5减小到0.014 7。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

32. 两台自私型机器上自私工件排序的PoA紧界

成夏炎, 何滢, 赵聪聪, 李荣珩

运筹学学报 2022, 26 (3): 109-119. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.008

摘要（2010）

HTML （13）

PDF（pc）（783KB）（99）

本文研究了两台自私型机器上有自私型工件的关于二元均衡的排序问题。对任意工件序列$L$, 证明了二元均衡排序的PoA的紧界为$\frac{8}{7}$。如果工件尺寸在区间$[1, r](r\ge1)$内, 得到了二元均衡排序的PoA的紧界为关于$r$的分段线性函数。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

33. 新产品供应链下考虑顾客体验效应的制造商渠道返利策略研究

徐春明, 吴晨晨, 原白云

运筹学学报 2022, 26 (3): 120-132. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.009

摘要（2174）

HTML （22）

PDF（pc）（2172KB）（237）

随着体验经济的到来和新产品市场的竞争, 如何针对顾客体验进行渠道建设和品牌推广就显得尤为重要。本文针对新产品供应链的环境, 考虑顾客的体验效应及零售商对此所做的体验投入, 利用效用理论构建了线上和线下消费者的需求函数, 在此基础上分别探讨了批发价格模式和渠道返利模式制造商占优的供应链的决策行为, 分析了供应链各决策主体均衡解的特征, 并对渠道返利前后供应链节点企业的最优决策进行了比较, 最后用数值例子分析了制造商的返利点、零售商的体验投入水平、顾客的体验效应、旅行成本以及购买意愿等对供应链最优绩效的影响。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

34. 工件具有任意尺寸的混合分批平行机排序问题的近似算法

王冬, 李刚刚, 罗文昌

运筹学学报 2022, 26 (3): 133-142. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.010

摘要（2067）

HTML （18）

PDF（pc）（840KB）（228）

本文考虑了工件具有任意尺寸且机器有容量限制的混合分批平行机排序问题。在该问题中, 一个待加工的工件集需在多台平行批处理机上进行加工。每个工件有它的加工时间和尺寸, 每台机器可以同时处理多个工件, 称为一个批, 只要这些工件尺寸之和不超过其容量; 一个批的加工时间等于该批中工件的最大加工时间和总加工时间的加权和; 目标函数是极小化最大完工时间。该问题包含一维装箱问题为其特殊情形, 为强NP-困难的。对此给出了一个$\left( {2 + 2\alpha+\alpha^{2}}\right)$-近似算法, 其中$\alpha$为给定的权重参数, 满足$0\leq\alpha\leq 1$。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

35. 一类一维在线单位聚类问题的随机近似算法

代宇波, 段懿红, 刘龙城, 王子豪

运筹学学报 2022, 26 (3): 143-150. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.011

摘要（2042）

HTML （10）

PDF（pc）（766KB）（114）

在给定的度量空间中, 单位聚类问题就是寻找最少的单位球来覆盖给定的所有点。这是一个众所周知的组合优化问题, 其在线版本为: 给定一个度量空间, 其中的n个点会一个接一个的到达任何可能的位置, 在点到达的时候必须给该点分配一个单位聚类, 而此时未来点的相关信息都是未知的, 问题的目标是最后使用的单位聚类数目最少。本文考虑的是带如下假设的一类一维在线单位聚类问题: 在相应离线问题的最优解中任意两个相邻聚类之间的距离都大于0.5。本文首先给出了两个在线算法和一些引理, 接着通过0.5的概率分别运行两个在线算法得到一个组合随机算法, 最后证明了这个组合随机算法的期望竞争比不超过1.5。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

36. 极大化提前完工总量平行机排序问题的LPT算法

周萍, 季敏, 蒋义伟

运筹学学报 2022, 26 (3): 151-156. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.012

摘要（2119）

HTML （14）

PDF（pc）（744KB）（185）

研究带有共同交货期的三台平行机排序问题。工件在加工过程中不允许中断, 目标是极大化所有工件的提前完工量, 即在交货期前所加工工件(或部分) 的总加工时长。由于该问题是NP-难问题, 本文应用经典LPT算法来解决该问题。我们证明了LPT算法求解该问题的最坏情况界至多为$\frac{15}{13}$, 并给出实例说明最坏情况界的下界为$\frac{27}{25}$。

图表 | 参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

37. 基于金融文本情绪挖掘的Black-Litterman投资组合模型研究——以东方财富股吧发帖文本和我国A股市场为例

徐维军, 黄静龙, 付志能, 张卫国

运筹学学报 2022, 26 (4): 1-14. DOI: 10.15960/j.cnki.issn.1007-6093.2022.04.001

摘要（2760）

HTML （101）

PDF（pc）（1076KB）（197）

互联网时代下, 越来越多投资者开始在网络社区, 特别是在金融投资类社区中发表自己的投资观点与看法, 由此产生的海量金融文本数据具有较高的研究价值, 如何将这些金融文本数据加以利用已成为时下金融投资领域的研究热点。本文探究了如何将东方财富股吧中的投资者发帖文本转化为对应的情绪指标, 并基于此形成投资者意见, 在Black-Litterman模型框架下构建考虑金融文本情绪信息的投资组合模型。具体来讲, 首先利用网络爬虫从东方财富股吧中获取富时中国A50成分股对应的股吧发帖文本数据, 并进行数据预处理, 随后运用词典法和朴素贝叶斯法分别提取出股吧发帖文本的情绪指标;进一步将情绪指标、股票收盘价和成交量三项指标作为特征变量, 使用回归随机森林算法对股票的未来收益率进行预测;最后将预测得到的未来收益率作为投资者观点, 并置于Black-Litterman模型中构建考虑金融文本情绪信息的投资组合模型。回测结果显示, 使用朴素贝叶斯法构建的基于金融文本情绪挖掘的投资组合模型有更好的绩效表现。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

38. 基于随机微分博弈的网约车监管问题研究

杨明歌, 孙璐璐, 梁小珍

运筹学学报 2022, 26 (4): 15-30. DOI: 10.15960/j.cnki.issn.1007-6093.2022.04.002

摘要（2699）

HTML （14）

PDF（pc）（991KB）（196）

将地方政府、网约车平台和司机看作一个监管系统, 探讨三方博弈视角下的网约车监管问题。在无中央政府补贴的分散式决策、有中央政府补贴的分散式决策、局部联盟决策和集中式决策下, 分别构建随机微分博弈模型, 研究地方政府和网约车平台的最优监管努力程度、网约车司机的最优服务努力程度、网约车商誉的期望和方差、系统成员和系统的最优效益。结果表明:与无中央政府补贴的分散式决策相比, 有中央政府补贴的分散式决策下, 地方政府和网约车平台的最优监管努力程度、网约车司机的最优服务努力程度、网约车商誉的期望和方差、系统成员和系统的最优效益均提高；与有中央政府补贴的分散式决策相比, 局部联盟决策下, 地方政府的最优监管努力程度不变, 网约车平台的最优监管努力程度、网约车司机的最优服务努力程度、网约车商誉的期望和方差、地方政府、局部联盟和系统的最优效益均提高；与局部联盟决策相比, 集中式决策下, 地方政府和网约车平台的最优监管努力程度、网约车司机的最优服务努力程度、网约车商誉的期望和方差、系统的最优效益均提高。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

39. 基于聚类的昂贵多目标优化代理辅助进化算法

白富生, 陈姣伶

运筹学学报 2022, 26 (4): 31-42. DOI: 10.15960/j.cnki.issn.1007-6093.2022.04.003

摘要（2842）

HTML （11）

PDF（pc）（921KB）（184）

针对目标函数估值昂贵的多目标优化问题, 提出了基于聚类的代理辅助进化算法。在MOEA/D算法的框架下, 对种群进行聚类, 并通过权重向量的邻域选出种群子集, 在子集上使用径向基插值函数辅助的差分进化算法得到新解, 对种群进行更新。在7个DTLZ标准测试问题上进行了数值实验, 计算结果表明本文提出的算法比新近提出的多目标邻域回归优化(MONRO)算法具有优势。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

40. 系统性尾部贝塔与市场崩盘风险的对冲:基于崩盘风险的“安全第一准则”投资组合均衡模型

凌爱凡, 朱佳磊, 唐乐, 蒋崇辉

运筹学学报 2022, 26 (4): 43-63. DOI: 10.15960/j.cnki.issn.1007-6093.2022.04.004

摘要（2755）

HTML （14）

PDF（pc）（1076KB）（170）

近年来随着市场震荡多变，我国A股市场频繁出现千股跌停的现象。如何在市场发生崩盘风险的情形下，预测风险资产的尾部风险，并有效对冲市场崩盘风险等问题引起了广泛的关注。为了回答这些问题，论文在传统“安全第一准则”投资组合模型中引入了市场发生崩盘风险的约束条件，在均衡情形下获得了具有市场崩盘风险的资产定价模型(Crash CAPM: CCAPM)，利用CCAPM中风险负载与传统的市场贝塔，论文构建了一个新的系统性尾部风险度量指标β^∆。利用1995—2018年期间我国A股市场日收益率数据进行实证检验发现，β^∆能够有效地捕捉到市场崩盘与繁荣时期，资产与市场的尾部关联性。特别地，在市场崩盘时期，β^∆与风险资产极端损失风险呈显著的正相关关系，高β^∆组合与低β^∆组合之差构建的投资组合，在市场崩盘时期，能够获得显著为正的尾部超额收益率，这为对冲市场崩盘提供了重要的依据。

参考文献 | 相关文章 | 多维度评价 | 评论（0）

2022年，第26卷