当期目录

2020年 第24卷 第3期    刊出日期：2020-09-15

上一期    下一期

低秩稀疏矩阵优化问题的模型与算法

潘少华, 文再文

2020, 24(3):  1-26.  doi:10.15960/j.cnki.issn.1007-6093.2020.03.001

摘要 ( 1201 )   PDF (907KB) ( 478 )  

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

低秩稀疏矩阵优化问题是一类带有组合性质的非凸非光滑优化问题.由于零模与秩函数的重要性和特殊性，这类NP-难矩阵优化问题的模型与算法研究在过去十几年里取得了长足发展。本文从稀疏矩阵优化问题、低秩矩阵优化问题、低秩加稀疏矩阵优化问题、以及低秩张量优化问题四个方面来综述其研究现状；其中，对稀疏矩阵优化问题，主要以稀疏逆协方差矩阵估计和列稀疏矩阵优化问题为典例进行概述，而对低秩矩阵优化问题，主要从凸松弛和因子分解法两个角度来概述秩约束优化和秩（正则）极小化问题的模型与算法研究。最后，总结了低秩稀疏矩阵优化研究中的一些关键与挑战问题，并提出了一些可以探讨的问题。

动态传播率模型及其在疫情分析中的应用

胡云鹤, 刘艳云, 吴凌霄, 王杰, 孔京, 张一, 戴彧虹, 杨周旺

2020, 24(3):  27-42.  doi:10.15960/j.cnki.issn.1007-6093.2020.03.002

摘要 ( 964 )   PDF (5551KB) ( 231 )  

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

应用数据驱动的动态传播率来代替基本传染数$R_0$，在全国和省市两个层面上研究COVID-19疫情发展的特点和趋势。首先，基于动态增长率建立传染病常微分方程，推导得出动态传播率模型。其次，选择幂函数作为动态传播率的拟合函数，以3天作为最优滑窗期，对各地拐点进行了估计。最后，通过动态模型对各地不同程度尾声开始的起点进行了预测，并在13个省市间进行9个疫情相关指标的对比分析。结果显示，各地动态传播率在经过短暂的波动后均稳步下降，疫情得到有效控制；估计的拐点主要集中在2月中旬，而预测的尾声都将在3月底之前到来；同时，各地疫情发展特点和趋势、防控措施力度和效果存在一定差异。

新冠肺炎疫情条件下的企业复工复产优化规划方法

郑宇军, 吴晨昕, 陈恩富, 卢雪琴, 张敏霞

2020, 24(3):  43-56.  doi:10.15960/j.cnki.issn.1007-6093.2020.03.003

摘要 ( 947 )   PDF (1832KB) ( 408 )  

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

新冠病毒肺炎疫情对整个经济社会发展造成了很大冲击，如何在不放松疫情防控的前提下科学规划企业复工复产，这是地方政府面临的一个重要挑战。基于浙江省在统筹疫情防控和经济社会发展工作中的有关经验，本文建立了一个疫情条件下企业复工复产规划问题的整数规划模型，其目的是要在不违反疫情传播风险等约束下，从大批申请企业中选择一部分批准复工复产并安排优先顺序，以尽可能满足社会对相关产业产能的需求。为有效求解该问题，本文提出了一个改进的禁忌搜索算法，它使用贪心策略来构造一个初始解，并不断通过可变规模的邻域搜索来探寻更优的解，在多个地区企业复工复产规划问题实例上的计算结果验证了该算法的效率。

两台恒速机上的MapReduce排序算法研究

姜晓燕, 帅天平

2020, 24(3):  57-66.  doi:10.15960/j.cnki.issn.1007-6093.2020.03.004

摘要 ( 687 )   PDF (1348KB) ( 111 )  

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

研究源自于MapReduce系统的一类排序问题。给定两台恒速机和一组按列表到达的工件，每个工件包含两类任务：Map Task和Reduce Task。假设Map任务和Reduce任务都是不可中断的，Map任务可以并行处理，即可以任意分割成若干小的任务并在两台机器上同时处理，而Reduce任务只可以在单台机器上处理。一旦工件到达，必须为其指派机器和开工时间，目标是使得最后完工时间最小。对LSc算法的竞争比进行了分析，得到其一般情形下的竞争比当$s\geq（1+\sqrt{5}）/2$时为$1+1/s$，否则为$1+s/（s+1）$。而当每个工件$J_j$都满足其Map任务总长大于等于Reduce任务总长时，其竞争比当$s\geq（1+\sqrt{3}）/2$时不超过$1+1/（2s）$，否则为不超过$1+s/（2s+1）$。

集装箱码头桥机调度问题基于完工时间下界的算法

陆书翔, 吕长虹, 秦涛

2020, 24(3):  67-76.  doi:10.15960/j.cnki.issn.1007-6093.2020.03.005

摘要 ( 1048 )   PDF (939KB) ( 529 )  

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

关注单船桥机调度问题，指出了单船桥机的闲置会影响码头整体的运作效率。以单个集装箱为任务单位，考虑桥机移动时间、安全距离等约束，建立了最小化桥机完工时间和闲置时间的多目标规划模型。基于完工时间下界的两种不同情况：以重点贝位工作量确定和以平均工作量确定，分别设计了基于邻域搜索的启发式算法和基于贪心策略的“分割贝位”算法，并且证明了在以平均工作量确定下界的情况中该算法不会导致桥机闲置。不同规模、不同下界类型的算例表明：提出的模型与算法得到的桥机调度计划更适合实际生产作业，能够有效地逼近完工时间下界，算法运行速度较现有的研究有显著的提高。

不确定彩排时长下节目调度的鲁棒优化

仲维亚, 施益媚

2020, 24(3):  77-86.  doi:10.15960/j.cnki.issn.1007-6093.2020.03.006

摘要 ( 959 )   PDF (699KB) ( 145 )  

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

实际节目彩排调度中，节目的表演时长受内外因素影响，具有不确定性。为了合理调度所有节目，控制演员的空闲时间，使得演员的总等待成本最小，采用了鲁棒优化方法进行研究。首先，建立了节目彩排调度的确定型模型；进一步，考虑节目表演时长的不确定性，采用有界区间描述节目表演时长并考虑决策者风险偏好，在确定型模型的基础上构建区间型两阶段鲁棒优化模型；接着，将鲁棒优化模型转化为0-1混合线性规划模型；最后，采用Matlab进行数值实验，结果表明决策者越偏好规避风险，演员的总等待成本越大。

均值-CVaR零售商的供应链服务决策及协调契约

禹海波, 那娜, 唐中君

2020, 24(3):  87-100.  doi:10.15960/j.cnki.issn.1007-6093.2020.03.007

摘要 ( 789 )   PDF (794KB) ( 139 )  

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

研究零售商具有风险偏好行为下，同时考虑价格、质量和服务水平的供应链联合决策问题。运用均值-CVaR准则来刻画零售商风险偏好行为，它包括风险厌恶、风险中性和风险追求，同时具有损失规避的特性。首先得到供应链集中系统、制造商提供服务（模型$\mbox{I}$）和零售商提供服务（模型$\mbox{II}$）下的最优决策和最优利润（期望效用）。其次，证明了成本共担契约在零售商风险厌恶时可以实现供应链协调.第三，对模型$\mbox{I}$和模型$\mbox{II}$协调后的最优利润（期望效用）进行比较，证明两种模型下制造商利润相同，而与模型$\mbox{I}$相比，模型$\mbox{II}$下零售商获得更多的期望效用。最后，数值例子证明了得到的研究结果。

随机利率环境下一类跳扩散相依风险资产的最优投资策略

孙景云, 郭精军

2020, 24(3):  101-114.  doi:10.15960/j.cnki.issn.1007-6093.2020.03.008

摘要 ( 738 )   PDF (2897KB) ( 154 )  

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

考虑了随机利率环境下基于连续时间的动态最优资产配置问题。假设市场利率满足一个均值回复的随机过程，且金融市场由一个零息债券和两个价格受到共同冲击的相依性风险资产所构成。在均值-方差目标准则之下，利用随机最优控制理论和Lagrange对偶原理获得了有效投资策略以及相应有效边界的解析式。最后通过数值算例，分析了有效策略及有效边界对相关参数的敏感性，并验证了相关理论结果。

基于DC规划方法的稀疏临近支持向量机

杨琳希, 李国权

2020, 24(3):  115-126.  doi:10.15960/j.cnki.issn.1007-6093.2020.03.009

摘要 ( 830 )   PDF (3334KB) ( 221 )  

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

为了提高临近支持向量机（PSVM）的数值表现，在PSVM的模型中引入了$\ell_0$-范数正则项，提出了稀疏临近支持向量机模型（SPSVM），从而提高分类器的特征选择能力。然而带有$\ell_0$-范数正则项的问题往往是NP-难问题，为了克服这一问题，采用非凸连续函数近似$\ell_0$-范数，并通过适当的DC分解将问题转化成DC规划问题进行求解，同时还讨论了算法的收敛性。数值实验结果表明不论是在仿真数据还是在实际数据中，所提出的方法是比较有效稳定的。

广义黏性逼近方法及其应用

郭科, 王涛, 张有才

2020, 24(3):  127-140.  doi:10.15960/j.cnki.issn.1007-6093.2020.03.010

摘要 ( 833 )   PDF (674KB) ( 79 )  

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

黏性逼近方法在非扩张映射不动点问题的研究中扮演着重要的角色。提出了一类广义黏性逼近方法，在一定条件下，证明了该算法的收敛性.作为应用，将所得的收敛性结果应用于求解约束凸优化问题与双层优化问题。

一种新的修正SR1更新公式及其算法收敛性

何阿肆, 张圣贵

2020, 24(3):  141-153.  doi:10.15960/j.cnki.issn.1007-6093.2020.03.011

摘要 ( 790 )   PDF (735KB) ( 111 )  

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

SR1更新公式对比其他的拟牛顿更新公式，会更加简单且每次迭代需要更少的计算量。但是一般SR1更新公式的收敛性质是在一致线性无关这一很强的条件下证明的。基于前人的研究成果，提出了一种新的修正SR1公式，并分别证明了其在一致线性无关和没有一致线性无关这两个条件下的局部收敛性，最后通过数值实验验证了提出的更新公式的有效性，以及所作出假设的合理性。根据实验数据显示，在某些条件下基于所提出更新公式的拟牛顿算法会比基于传统的SR1更新公式的算法收敛效果更好一些。

最大度大于等于7的平面图的线性荫度

陈洪玲, 王慧娟, 孙凤艳, 薛娟, 高红伟

2020, 24(3):  154-160.  doi:10.15960/j.cnki.issn.1007-6093.2020.03.012

摘要 ( 698 )   PDF (610KB) ( 133 )  

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

图的染色问题在组合优化、计算机科学和Hessians矩阵的网络计算等方面具有非常重要的应用。其中图的染色中有一种重要的染色——线性荫度，它是一种非正常的边染色，即在简单无向图中，它的边可以分割成线性森林的最小数量。研究最大度$\bigtriangleup（G）\geq7$的平面图$G$的线性荫度，证明了对于两个固定的整数$i$，$j\in\{5，6，7\}$，如果图$G$中不存在相邻的含弦$i$，$j$-圈，则图$G$的线性荫度为$\lceil\frac\bigtriangleup2\rceil$。

哈密尔顿平面图最小平衡二部划分的上界

陈涛

2020, 24(3):  161-166.  doi:10.15960/j.cnki.issn.1007-6093.2020.03.013

摘要 ( 873 )   PDF (553KB) ( 126 )  

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

设$G（V，E）$是一个图，$V_{1}，V_{2}$是$V$的一个二部划分，用$e（V_{1}，V_{2}）$表示一条边的两个端点在不同划分里边的总数目，当$||V_{1}|-|V_{2}||\leq 1$时，称$V_{1}，V_{2}$是$V$的一个平衡二部划分。最小平衡二部划分是指寻找$G（V，E）$的一个平衡二部划分使得$e（V_{1}，V_{2}）$最小。对于哈密尔顿平面图$G（V，E）$，研究了当Perfect-内部三角形最大边函数值与最小边函数值之差为$d$时，$e（V_{1}，V_{2}）$最小值的上界与$d$之间的关系。