运筹学学报

Select

1. 基于迭代投影的梯度硬阈值追踪算法

陈薪蓓, 朱明康, 陈建利

运筹学学报 2019, 23 (1): 1-14. DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.001

摘要（763）

PDF（pc）（5439KB）（534）

梯度硬阈值追踪算法是求解稀疏优化问题的有效算法之一.考虑到算法中投影对最优解的影响，提出一种比贪婪策略更好的投影算法是很有必要的.针对一般的稀疏约束优化问题，利用整数规划提出一种迭代投影策略，将梯度投影算法中的投影作为一个子问题求解.通过迭代求解该子问题得到投影的指标集，并以此继续求解原问题，以提高梯度硬阈值追踪算法的计算效果.证明了算法的收敛性，并通过数值实例验证了算法的有效性.

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

Select

2. 求解全局最优问题的多重点样本水平值估计的相对熵算法

周心怡, 汪可, 邬冬华, 汪晨

运筹学学报 2019, 23 (1): 15-27. DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.002

摘要（1073）

PDF（pc）（668KB）（296）

研究有界闭箱约束下的全局最优化问题，利用相对熵及广义方差函数方程的最大根与全局最小值之间的等价关系，设计求解全局最优值的积分型水平值估计算法.对采用重点样本采样技巧产生的函数值按一定规则进行聚类，从而在各聚类中产生的若干新重点样本，结合相对熵算法，构造出多重点样本进行全局搜索的新算法.该算法的优点在于每次迭代选用当前较好的函数值信息，以达到随机搜索到更好的函数值信息.同时多重点样本可有利挖掘出更好的全局信息.一系列的数值实验表明该算法是非常有效的.

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

Select

3. 求解带箱子集约束的非光滑全局优化问题的填充函数方法

王伟祥, 尚有林, 王朵

运筹学学报 2019, 23 (1): 28-34. DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.003

摘要（1087）

PDF（pc）（553KB）（264）

提出了一个求解带箱子集约束的非光滑全局优化问题的填充函数方法.构造的填充函数只包含一个参数，且此参数在迭代过程中容易调节.分析了填充函数的理论性质，在此基础上设计了填充函数算法.数值计算验证了该算法的有效性.

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

Select

4. 拟凸多目标优化问题近似解的最优性条件

陈瑞婷, 徐智会, 高英

运筹学学报 2019, 23 (1): 35-44. DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.004

摘要（865）

PDF（pc）（626KB）（447）

研究了拟凸多目标优化问题近似弱有效解、近似有效解的最优性条件.首先，在已有拟凸函数次微分的基础上引进4种近似次微分的概念，并给出它们之间的关系.然后，将4种近似次微分的概念应用到拟凸多目标优化问题中，给出了拟凸多目标优化问题近似弱有效解和近似有效解的充分条件和必要条件，并给出实例加以说明.

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

Select

5. 变序结构局部弱非控点的二阶刻画

徐义红, 梅芳

运筹学学报 2019, 23 (1): 45-52. DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.005

摘要（703）

PDF（pc）（437KB）（1835）

引进了一种二阶切导数，借助该切导数给出了变序结构集值优化问题取得局部弱非控点的二阶最优性必要条件.在某种特殊情况下，给出了一阶最优性条件.通过修正的Dubovitskij-Miljutin切锥导出的约束规格，给出了两个集值映射之和的二阶相依切导数的关系式，进一步得到目标函数与变锥函数的二阶相依切导数分开形式的最优性必要条件.

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

Select

6. 基于块循环矩阵的对称张量的最佳秩-1逼近

徐娇娇, 杨志霞, 蒋耀林

运筹学学报 2019, 23 (1): 53-60. DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.006

摘要（1050）

PDF（pc）（517KB）（217）

对称张量的最佳秩-1问题是张量研究中非常重要的部分.首先，基于三阶张量的块循环矩阵，提出了求解对称张量最佳秩-1逼近问题的一个新方法.其次，针对求解对称张量的最佳秩-1逼近方法，给出了对称张量的最佳秩-1逼近不变性的一个充要条件，以及逼近误差上界的估计.最后，数值算例表明了上述方法的可行性和误差上界的正确性.

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

Select

7. 带有固定区间的单机双代理可中断总误工问题

陈秋宏, 张新功

运筹学学报 2019, 23 (1): 61-71. DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.007

摘要（732）

PDF（pc）（550KB）（243）

研究带有固定区间的两个代理单机排序问题.第一个代理工件可中断，且工件到达时间与工期满足一致关系，目标函数为最小化总误工.第二个代理工件被安排在固定时间窗口.目标是寻找一个排序，使得满足第二个代理目标可行情况下，第一个代理目标函数值最小.在固定区间等于加工时间的情况下，利用分块原则，提出了一个伪多项式时间动态规划算法，并给出了固定区间大于加工时间情况下的时间复杂度分析.

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

Select

8. 新单圈图H(p,tK_1,m)的拉普拉斯谱刻画

孙秋实, 杨筱韵, 王力工, 李希赫, 王朋超

运筹学学报 2019, 23 (1): 72-80. DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.008

摘要（1011）

PDF（pc）（559KB）（1249）

设图H（p，tK_1，m）是一个顶点数为p+mt的连通单圈图，它是由圈C_p的依次相邻的t（1 ≤ t ≤ p）个顶点的每一个顶点分别与星K_1，m的中心重合而得到的单圈图.现证明单圈图H（p，p K_1，5），H（p，（p-1）K_1，4）是由它们的拉普拉斯谱确定的，并证明了当p为偶数时，单圈图H（p，2K_1，4），H（p，（p-2）K_1，4），H（p，（p-3）K_1，4）也是由它们的拉普拉斯谱确定的.

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

Select

9. 三圈图的无符号拉普拉斯谱半径

陈媛媛, 王国平

运筹学学报 2019, 23 (1): 81-89. DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.009

摘要（1268）

PDF（pc）（867KB）（298）

假设图G的点集是V（G）={v₁，v₂，…，v_n}，用d_{v_i}（G）表示图G中点v_i的度，令A（G）表示G的邻接矩阵，D（G）是对角线上元素等于d_{v_i}（G）的n×n对角矩阵，Q（G）=D（G）+A（G）是G的无符号拉普拉斯矩阵，Q（G）的最大特征值是G的无符号拉普拉斯谱半径.现确定了所有点数为n的三圈图中无符号拉普拉斯谱半径最大的图的结构.

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

Select

10. 补图具有悬挂点且连通的图的最小特征值

余桂东, 孙威, 芦兴庭

运筹学学报 2019, 23 (1): 90-96. DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.010

摘要（692）

PDF（pc）（1051KB）（233）

图的最小特征值定义为图的邻接矩阵的最小特征值，它是刻画图的结构性质的重要参数.在给定阶数且补图为具有悬挂点的连通图的图类中，刻画了最小特征值达极小的唯一图，并给出了这类图最小特征值的下界.

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

Select

11. 单圈图生成的凯莱图UG_n在PMC模型和MM^*模型下的1好邻诊断度

任佳敏, 冯伟, 赵凌琪, 王世英, 吉日木图

运筹学学报 2019, 23 (1): 97-103. DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.011

摘要（839）

PDF（pc）（628KB）（259）

多处理系统的诊断度是一个重要的研究课题.一种新的系统故障诊断方法称为g好邻诊断度，它是限制每个无故障点至少包含g个无故障的邻点.单圈图生成的凯莱图UG_n作为一种极好的互联网络拓扑结构有许多好的性质.现证明了当n ≥ 4时，单圈图生成的凯莱图UG_n在PMC模型下的1好邻诊断度是2n-1；当n ≥ 5时，UG_n在MM^*模型下的1好邻诊断度是2n-1.

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

Select

12. 不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界

陈宏宇, 谭香

运筹学学报 2019, 23 (1): 104-110. DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.012

摘要（913）

PDF（pc）（541KB）（287）

图G的一个边分解是指将G分解成子图G₁，G₂，…，G_m使得E（G）=E（G₁）∪ E（G₂）∪…∪ E（G_m），且对于i≠j，E（G_i）∩E（G_j）=∅.一个线性k-森林是指每个分支都是长度最多为k的路的图.图G的线性k-荫度la_k（G）是使得G可以边分解为m个线性k-森林的最小整数m.显然，la₁（G）是G的边色数χ'（G）；la_∞（G）表示每条分支路是无限长度时的情况，即通常所说的G的线性荫度la（G）.利用权转移的方法研究平面图的线性2-荫度la₂（G）.设G是不含有5-圈和相邻4-圈的平面图，证明了若G连通且δ（G）≥ 2，则G包含一条边xy使得d（x）+d（y）≤ 8或包含一个2-交错圈.根据这一结果得到其线性2-荫度的上界为?△/2?+4.

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

Select

13. 工件满足一致性的同类机在线分批排序问题

彭南南, 张玉忠, 柏庆国, 王成飞

运筹学学报 2019, 23 (1): 111-118. DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.013

摘要（855）

PDF（pc）（590KB）（309）

研究了工件满足一致性，批容量无界的两台同类机在线分批排序问题，目标为极小化工件的最大完工时间和极小化工件的最大流程时间，三元素法分别表示为Q₂|r_i < r_j⇒ p_i ≤ p_j，B=∞，on-line|C_max，Q₂|r_i < r_j⇒ p_i ≥ p_j，B=∞，on-line|F_max.不失一般性，假设第一台机器速度为1，第二台机器速度为s，s ≥ 1.对于上述两类问题设计了一个在线算法，并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α，这里α为α²+sα-1=0的正根，特别地，当s=1时，该算法的竞争比不超过1.618.对第二类排序问题，该在线算法的竞争比不超过1+1/α.

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

Select

14. 不确定性自私路由模型的理论和应用

刁卓

运筹学学报 2019, 23 (1): 119-126. DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.014

摘要（594）

PDF（pc）（668KB）（273）

为了更加准确地描述现实生活中的交通情况，以经典的自私路由模型为基础，在边的费用函数上引入不确定性，从而定义了具有不确定性的自私路由模型.对于不确定性自私路由模型，采用三种费用衡量标准，风险厌恶型（保守型）、风险折衷型（理智型）、风险偏好型（乐观型），分别对应着不同人群在现实中的选择.进而定义了在不同衡量标准下所形成的稳定策略，即纳什均衡策略，并且证明了在任何一种衡量标准下，纳什均衡策略总是存在并且本质是唯一的.接着对三种费用衡量标准下的纳什均衡费用进行了比较，发现了一种反直观的现象：风险厌恶型（保守型）衡量标准下的纳什均衡费用可能严格低于风险偏好型（乐观型）衡量标准下的纳什均衡费用，即有可能会出现高风险低回报，低风险高回报的情况，这与经济学中高风险高回报，低风险低回报的原则是相违背的.以此为基础，进而提出了一种自私路由风险性悖论，并证明了这种自私路由风险回报悖论本质上是传统布雷斯悖论的推广.最后，刻画出了不会发生自私路由风险回报悖论的网络结构，证明了一个单对始终点网络不会发生自私路由风险回报悖论当且仅当它是序列-平行网络.

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

Select

15. 具有Min(N,D,V)-策略控制的M/G/1排队系统

罗乐, 唐应辉

运筹学学报 2019, 23 (2): 1-16. DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.001

摘要（968）

PDF（pc）（2405KB）（184）

研究服务员具有多重休假和系统采取MinMin（N,D,V）-策略控制的M/G/1排队系统，运用全概率分解技术和拉普拉斯变换工具，研究了系统队长的瞬态分布和稳态分布，得到了队长瞬态分布的拉普拉斯变换的表达式和稳态队长分布的递推表达式，同时给出了稳态队长的随机分解结果和附加队长分布的显示表达式.进一步讨论了当N→∞，或D→∞，或p{V=∞}=1，或p{V=0}=1的一些特殊情况.最后，在建立系统费用结构模型的基础上，导出了系统长期单位时间的期望费用的显示表达式，并通过数值实例不但确定了使得系统在长期单位时间内的期望费用最小的联合控制策略（N^*，D^*），而且与单一的最优N^*-控制策略和D^*-控制策略进行了比较.

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

Select

16. 求解非光滑方程组的三次正则化方法

苗小楠, 顾剑, 肖现涛

运筹学学报 2019, 23 (2): 17-30. DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.002

摘要（1143）

PDF（pc）（583KB）（202）

考虑求解非光滑方程组的三次正则化方法及其收敛性分析.利用信赖域方法的技巧，保证该方法是全局收敛的.在子问题非精确求解和BD正则性条件成立的前提下，分析了非光滑三次正则化方法的局部收敛速度.最后，数值实验结果验证了该算法的有效性.

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

Select

17. 图的区间边着色的收缩图方法

陶艳亮, 黄琼湘, 陈琳

运筹学学报 2019, 23 (2): 31-43. DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.003

摘要（1086）

PDF（pc）（1678KB）（140）

图G的一个用了颜色1，2，…，t的边着色称为区间t-着色，如果所有t种颜色都被用到，并且关联于G的同一个顶点的边上的颜色是各不相同的，且这些颜色构成了一个连续的整数区间.G称作是可区间着色的，如果对某个正整数t，G有一个区间t-着色.所有可区间着色的图构成的集合记作N.对图G∈N，使得G有一个区间t-着色的t的最小值和最大值分别记作w（G）和W（G）.现给出了图的区间着色的收缩图方法.利用此方法，我们对双圈图G∈N，证明了w（G）=△（G）或△（G）+1，并且完全确定了w（G）=△（G）及w（G）=△（G）+1的双圈图类.

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

Select

18. 基于Stein-Stein波动率和动态VaR约束下DC型养老基金的最优投资策略

孙景云, 田丽娜, 陈峥

运筹学学报 2019, 23 (2): 44-56. DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.004

摘要（929）

PDF（pc）（2552KB）（159）

研究了确定缴费型养老基金在退休前累积阶段的最优资产配置问题.假设养老基金管理者将养老基金投资于由一个无风险资产和一个价格过程满足Stein-Stein随机波动率模型的风险资产所构成的金融市场.利用随机最优控制方法，以最大化退休时刻养老基金账户相对财富的期望效用为目标，分别获得了无约束情形和受动态VaR（Value at Risk）约束情形下该养老基金的最优投资策略，并获得相应最优值函数的解析表达形式.最后通过数值算例对相关理论结果进行数值验证并考察了最优投资策略关于相关参数的敏感性.

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

Select

19. 基于PH服务的工作休假排队的流体模型

王慧宁, 徐秀丽

运筹学学报 2019, 23 (2): 57-66. DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.005

摘要（1208）

PDF（pc）（939KB）（122）

研究了带有单重工作休假的M/PH/1排队系统驱动的流体模型.首先，通过拟生灭过程和矩阵几何解法分别得到无穷小生成元和驱动过程的稳态队长分布.其次，建立并分析流体模型，根据平衡方程给出流体模型的稳态联合分布函数满足的矩阵微分方程组，利用Laplace变换（LT）和Laplace-Stieltjes变换（LST）的方法，推导出平稳缓冲器（库）容量的空库概率表达式和稳态条件下的缓冲器（库）容量的均值表达式.最后，给出模型在移动自组织网络（Ad Hoc）中的应用，并通过数值例子讨论系统参数对系统性能指标的影响.

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

Select

20. 工件具有子工件工期的排序问题

仲维亚, 杨若瑶

运筹学学报 2019, 23 (2): 67-74. DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.006

摘要（1074）

PDF（pc）（500KB）（137）

研究了工件具有子工件工期的排序问题.需要在一台单机上加工若干个给定的工件.每个工件由若干个子工件组成，每个子工件都有各自的工期.只有当工件的每个子工件都按时完成，才能称该工件是按时完工工件，否则，称该工件产生延误.目标是最大化按时完工的工件个数.证明当每个工件都被分成两个子工件时，该问题是NP-难的，而且不存在完全多项式时间近似方案（fully polynomialtime approximation scheme，简记为FPTAS）.提出两个启发式算法，利用数值模拟比较它们的性能，并且将这两个启发式算法的解与最优解的上界进行比较.

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

Select

21. 中国高考招生匹配市场中的算法设计及公平激励机制

李建荣

运筹学学报 2019, 23 (2): 75-85. DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.007

摘要（1147）

PDF（pc）（575KB）（2034）

用匹配博弈的方法，研究中国高考招生市场的算法设计及公平激励机制.基于高考招生程序，构建高考招生匹配算法，证明该算法的可行性.证明一个稳定匹配，可以由一个纳什均衡策略经高考招生算法生成，但反之不一定成立.证明一个稳定匹配一定是公平的，反之不一定成立.构建拒绝-接受算法，证明该算法是一个稳定的、策略防御的匹配机制，因而是一个公平的激励机制.

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

Select

22. 求解稀疏逻辑回归问题的嵌套BB算法的分裂增广拉格朗日算法

梁仁莉, 白延琴

运筹学学报 2019, 23 (2): 86-94. DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.008

摘要（756）

PDF（pc）（873KB）（166）

逻辑回归是经典的分类方法，广泛应用于数据挖掘、机器学习和计算机视觉.现研究带有l₀模约束的逻辑回归问题.这类问题广泛用于分类问题中的特征提取，且一般是NP-难的.为了求解这类问题，提出了嵌套BB（Barzilai and Borwein）算法的分裂增广拉格朗日算法（SALM-BB）.该算法在迭代中交替地求解一个无约束凸优化问题和一个带l₀模约束的二次优化问题.然后借助BB算法求解无约束凸优化问题.通过简单的等价变形直接得到带l₀模约束二次优化问题的精确解，并且给出了算法的收敛性定理.最后通过数值实验来测试SALM-BB算法对稀疏逻辑回归问题的计算精确性.数据来源包括真实的UCI数据和模拟数据.数值实验表明，相对于一阶算法SLEP，SALM-BB能够得到更低的平均逻辑损失和错分率.

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

Select

23. 均衡约束数学规划问题的一类广义Mond-Weir型对偶理论

高雷阜, 闫婷婷

运筹学学报 2019, 23 (2): 95-103. DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.009

摘要（860）

PDF（pc）（483KB）（154）

针对均衡约束数学规划模型难以满足约束规范及难于求解的问题，基于Mond和Weir提出的标准非线性规划的对偶形式，利用其S稳定性，建立了均衡约束数学规划问题的一类广义Mond-Weir型对偶，从而为求解均衡约束优化问题提供了一种新的方法.在Hanson-Mond广义凸性条件下，利用次线性函数，分别提出了弱对偶性、强对偶性和严格逆对偶性定理，并给出了相应证明.该对偶化方法的推广为研究均衡约束数学规划问题的解提供了理论依据.

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

Select

24. 最大匹配的路变换图

刘岩, 雷梦霞, 黄晓娴

运筹学学报 2019, 23 (2): 104-112. DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.010

摘要（491）

PDF（pc）（860KB）（178）

图G的最大匹配的路变换图NM（G）是这样一个图，它以G的最大匹配为顶点，如果两个最大匹配M₁与M₂的对称差导出的图是一条路（长度没有限制），那么M₁和M₂在NM（G）中相邻.研究了这个变换图的连通性，分别得到了这个变换图是一个完全图或一棵树或一个圈的充要条件.

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

Select

25. 6-圈至多含一弦平面图的线性荫度

罗朝阳, 孙林

运筹学学报 2019, 23 (2): 113-119. DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.011

摘要（504）

PDF（pc）（599KB）（111）

线性森林是指每个连通分支都是路的图.图G的线性荫度la（G）等于将其边分解为k个边不交的线性森林的最小整数k.文中利用权转移方法证明了，若G是一个最大度大于等于7且每个6-圈至多含一条弦的平面图，则la（G）=「△（G）/2」.

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

Select

26. 极大限制边连通超图的两个充分条件

裴建峰, 林上为

运筹学学报 2019, 23 (2): 120-126. DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.012

摘要（1840）

PDF（pc）（622KB）（142）

图的限制边连通度是经典边连通度的推广，可用于精确度量网络的容错性.极大限制边连通图是使限制边连通度达到最优的一类图.首先将图的限制边连通度和最小边度的概念推广到r一致线性超图H，证明当H的最小度δ（H）≥r+1时，H的最小边度ξ（H）是它的限制边连通度，λ'（H）的一个上界，并将满足ξ（H）=λ'（H）的H称为极大限制边连通超图，然后证明n个顶点的r一致线性超图H如果满足δ（H）≥n-1/2（r-1）+（r-1），则它是极大限制边连通的，最后证明直径为2，围长至少为4的一致线性超图是极大限制边连通的.所得结论是图中相关结果的推广.

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

Select

27. 负载均衡问题

张国川, 陈林

运筹学学报 2019, 23 (3): 1-14. DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.001

摘要（1812）

PDF（pc）（668KB）（640）

自Ron Graham20世纪60年代发表第一篇负载均衡算法的论文以来，平行机排序作为组合优化近似算法理论的首个问题引起了学界的广泛兴趣，其本身研究的不断深化也一路见证了该领域的发展历程.介绍负载均衡问题的来龙去脉，特别是作者所在团队在相关问题的研究进展，从算法和复杂性不同的视角分析经典问题的计算本质，并对未来的研究提出一些建议.

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

Select

28. 一类多商品设施选址问题的基于线性松弛解的启发式方法

杨沐明, 黄亚魁, 戴彧虹

运筹学学报 2019, 23 (3): 15-26. DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.002

摘要（1865）

PDF（pc）（4129KB）（805）

多商品设施选址问题是众多设施选址问题中一类重要而困难的问题.在这一问题中，顾客的需求可能包含不止一种商品.对于大规模问题，成熟的商业求解器往往不能在满意的时间内找到高质量的可行解.研究了无容量限制的单货源多商品设施选址问题的一般形式，并给出了应用于此类问题的两个启发式方法.这两个方法基于原选址问题的线性规划松弛问题的最优解，分别通过求解紧问题和邻域搜索的方式给出了原问题的一个可行上界.理论分析指出所提方法可以实施于任意可行问题的实例.数值结果表明所提方法可以显著地提高求解器求解此类设施选址问题的求解效率.

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

Select

29. 选择性维护决策的研究进展与挑战

陈一明, 姜涛, 刘宇

运筹学学报 2019, 23 (3): 27-46. DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.003

摘要（1612）

PDF（pc）（2853KB）（370）

在工业生产和军事领域中，生产设备或技术装备往往要求连续执行多个任务，并且在任务间隔期内需要对系统中老化或失效的部件进行维护以确保完成后续任务.然而，由于受有限的成本、时间、设备及人员等维护资源的限制，在任务间隔期内难以修复系统中的所有组成部件，决策者只能有策略地选择部分部件进行维护，从而最大程度地确保完成后续任务，这类维护决策问题被称为选择性维护.现主要介绍选择性维护决策的基本模型和特点，并从系统建模、维护程度、资源约束与资源消耗、任务特性与应用环境、优化算法五个方面综述国内外关于选择性维护决策的研究进展和发展动态，并讨论其发展趋势和挑战.

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

Select

30. 无线通信系统设计中的两个优化问题和相关优化方法

刘亚锋

运筹学学报 2019, 23 (3): 47-62. DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.004

摘要（1160）

PDF（pc）（1384KB）（383）

无线通信系统设计中的许多问题可建模为优化问题.一方面，这些优化问题常常具有高度的非线性性，一般情况下难于求解；另一方面，它们又有自身的特殊结构，例如隐含的凸性、可分性等.利用优化的方法结合问题的特殊结构求解和处理无线通信系统设计问题是近年来学术界研究的热点.本文重点讨论无线通信系统设计中的两个优化问题和相关优化方法，包括多用户干扰信道最大最小准则下的联合传输/接收波束成形设计和多输入多输出（Multi-Input Multi-Output，MIMO）检测问题，主要介绍现代优化技术结合问题的特殊结构在求解和处理上述两个问题的最新进展.

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

Select

31. 高阶优化算法分析简介

朱喜华, 常青青, 江波

运筹学学报 2019, 23 (3): 63-76. DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.005

摘要（1223）

PDF（pc）（638KB）（297）

高阶优化算法是利用目标函数的高阶导数信息进行优化的算法，是最优化领域中的一个新兴的研究方向.高阶算法具有更低的迭代复杂度，但是需要求解一个更难的子问题.主要介绍三种高阶算法，分别为求解凸问题的高阶加速张量算法和A-HPE框架下的最优张量算法，以及求解非凸问题的ARp算法.同时也介绍了怎样求解高阶算法的子问题.希望通过对高阶算法的介绍，引起更多学者的关注与重视.

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

Select

32. 图与超图中的彩色匹配综述

李瞳, 王光辉, 周文玲

运筹学学报 2019, 23 (3): 77-90. DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.006

摘要（1060）

PDF（pc）（732KB）（410）

超图H=（V，E）是一个二元组（V，E），其中超边集E中的元素是点集V的非空子集.因此图是一种特殊的超图，超图也可以看作是一般图的推广.特别地，如果超边集E中的元素均是点集V的k元子集，则称该超图为k-一致的.通常情况下，为叙述简便，我们也会将超边简称为边.图（超图）中的匹配是指图（超图）中互不相交的边的集合.对于图（超图）中的彩色匹配，有两种定义方式：一为染色图（超图）中互不相交且颜色不同的边的集合；二为顶点集均为[n]的多个染色图（超图）所构成的集族中互不相交且颜色均不同的边的集合，且每条边均来自集族中不同的图（超图）.现主要介绍了图与超图中关于彩色匹配的相关结果.

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

Select

33. 交通网络下的多厂商两阶段随机非合作博弈问题——基于随机变分不等式

侯丽娜, 孙海琳

运筹学学报 2019, 23 (3): 91-108. DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.007

摘要（1384）

PDF（pc）（2975KB）（357）

研究集生产、运输和销售为一体的多个制造商在随机市场环境下的两阶段随机非合作博弈问题.首先，建立了该两阶段随机非合作博弈问题的模型，然后将其转化为两阶段随机变分不等式（Stochastic VariationalInequality，简称SVI）.在温和的假设条件下，证明了该问题存在均衡解，并通过Progressive Hedging Method（简称PHM）进行求解.最后，通过改变模型中随机变量的分布和成本参数，分析与研究厂商的市场行为.

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

Select

34. 最优传输理论在图像处理中的应用

马丽涛, 边伟

运筹学学报 2019, 23 (3): 109-125. DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.008

摘要（1892）

PDF（pc）（2991KB）（565）

最优传输问题是寻找概率测度间的最优传输变换的一类特殊的优化问题，近年来在众多领域得到了广泛的关注.针对传统最优传输问题存在的计算量过大、正则性缺失等问题，学者们提出了多种改进的最优传输模型和算法，用于处理实际中的各种问题.简述最优传输问题的基本理论和方法，介绍Wasserstein距离的概念及其衍生出的Wasserstein重心，探讨离散化最优传输模型及其在正则化等方面的改进，讨论求解最优传输问题的算法进展，综述Wasserstein距离在图像处理领域的简单应用，并展望有待进一步研究的工作.

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

Select

35. 在线时间序列搜索的风险补偿模型

张文明, 程永席, 茹少峰

运筹学学报 2019, 23 (3): 126-134. DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.009

摘要（1128）

PDF（pc）（3268KB）（170）

对于在线时间序列搜索问题，在假设对未来信息有一定的预期下，提出了在线时间序列搜索的风险补偿模型，进一步研究了模型的求解，给出了模型的一个最优策略，并通过数值计算讨论了最优策略的补偿函数随参数变化规律.数值实验结果表明，随着风险容忍度的增大与预期区间下限的增大，补偿函数均增大且趋于收敛；随着预期概率的增大与预期区间上限的减少，补偿函数分别增大.研究结果丰富了在线时间序列搜索的理论且具有实际应用价值.

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

Select

36. 多块交替方向乘子法不收敛反例的几点注记

陈彩华

运筹学学报 2019, 23 (3): 135-140. DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.010

摘要（1387）

PDF（pc）（469KB）（356）

近年来，多块交替方向乘子法被广泛地应用在信号处理、图像处理、机器学习、工程计算等各个领域中，然而它的收敛性一直是一个悬而未决的公开问题；直至2016年，陈彩华等人给出了一个三维线性方程组构成的反例说明多块交替方向乘子法是可能发散的.结合陈等人的结果，现讨论了与此相关的三个问题：1）反例之所以发散是否由于初始点选择不够好?2）反例的发散是否因为它的可行域是单点集?3）是否能够在对偶变量更新中引入某一与问题无关的步长γ∈（0，1]使得小步长的交替方向乘子法变形收敛?从理论上对前两个问题给出了否定的回答，证明当初始点随机选取时，存在可行域不是单点集的例子，使得多块交替方向乘子法求解该问题时以概率1发散；从数值上否定了第三个问题，说明即使步长γ=10^-8，多块交替方向乘子法也可能发散.

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

Select

37. 从数值最优化方法到学习最优化方法

郭田德, 韩丛英

运筹学学报 2019, 23 (4): 1-12. DOI: 10.15960/j.cnki.issn.1007-6093.2019.04.001

摘要（6638）

PDF（pc）（802KB）（1516）

传统最优化问题的求解方法主要是以梯度法为基础的数值最优化方法，它是解析与数值计算相结合的迭代求解方法，是一种基于固定模式的最优化方法.算法的迭代过程实质上是对迭代点进行非线性变换的过程，该非线性变换是通过一系列方向和步长来实现.对于最优化问题的每一个实例，都需要从头到尾执行整个算法，计算复杂度是固定的.一旦算法被程序实现，算法的效率（计算精度和复杂度）就被固定.人工智能解决问题的方法都具有学习功能.随着人工智能，特别是深度学习的兴起，学习类方法在一些领域取得了巨大的成功，如图像识别（特别是人脸识别、车牌识别、手写字符识别等）、网络攻击防范、自然语言处理、自动驾驶、金融、医疗等.本文从新的视角研究传统的数值最优化方法和智能优化方法，分析其特点，由此引出学习最优化方法，并对它们进行了对比，提出了学习最优化方法的设计思路.最后，以组合最优化为例，对该类方法的设计原理进行阐述.

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

Select

38. 风险相依下再保险双方的联合最优再保险问题

黄娅, 王京, 周杰明, 邓迎春

运筹学学报 2019, 23 (4): 13-33. DOI: 10.15960/j.cnki.issn.1007-6093.2019.04.002

摘要（928）

PDF（pc）（1728KB）（193）

结合保险人和再保险人的共同利益，研究了具有两类相依险种风险模型下的最优再保险问题.假定再保险公司采用方差保费原理收取保费，利用复合Poisson模型和扩散逼近模型两种方式去刻画保险公司和再保险公司的资本盈余过程，在期望效用最大准则下，证明了最优再保险策略的存在性和唯一性，通过求解Hamilton-Jacobi-Bellman（HJB）方程，得到了两种模型下相应的最优再保险策略及值函数的明晰解答，并给出了数值算例及分析.

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

Select

39. 具有包容关系的结构异质DEA效率评价方法

陈磊, 王应明

运筹学学报 2019, 23 (4): 34-44. DOI: 10.15960/j.cnki.issn.1007-6093.2019.04.003

摘要（1097）

PDF（pc）（1009KB）（167）

指标结构同质是数据包络分析（DEA）方法的基本假设之一；然而，现实问题的复杂性使得该假设常常难以完全被满足.针对具有包容关系的产出结构异质问题，通过解析决策单元（DMU）之间生产结构的内在关系来构建一种分阶段的DEA效率评价方法.该方法充分考虑了不同结构DMU的主观偏好，较好地规避了传统DEA方法在结构异质DMU效率评价过程中的不公平性.随后，该方法分别被拓展至投入结构异质和多重结构异质的情境中.最后，通过两个算例来说明本文方法的有效性与实用性.

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

Select

40. 基于时隙ALOHA协议的数据传输二人随机博弈模型

薛娟, 高红伟, 姜辉, 周允旭

运筹学学报 2019, 23 (4): 45-58. DOI: 10.15960/j.cnki.issn.1007-6093.2019.04.004

摘要（959）

PDF（pc）（703KB）（129）

在一个给定的拓扑网络中研究关于数据传输的二人随机博弈模型.两个局中人（源节点）试图通过一个公共节点向目的节点传输随机数据包，这些数据包被分为重要的数据包和不重要的数据包两类，假设每个局中人都有一个用于存储数据包的有限容量的缓冲器.通过构造数据传输的成本分摊和奖励体系，把这种动态的冲突控制过程建模为具有有限状态集合的随机博弈，研究局中人在这种随机博弈模型下的非合作以及合作行为.在非合作情形下，给出纳什均衡的求解算法；在合作情形下，选择Shapley值作为局中人支付总和的分配方案，并讨论其子博弈一致性，提出使得Shapley值为子博弈一致的分配补偿程序.

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

2019年，第23卷