2024年,第28卷

    按期号、起始页码排序
    Please wait a minute...
    选择: 显示/隐藏图片
    1. 求解一类线性等式约束凸优化问题的加速方法
    孟辛晴, 张文星
    运筹学学报(中英文)    2024, 28 (1): 1-17.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.001
    摘要281)   HTML11)    PDF(pc) (2761KB)(191)    收藏

    具有线性约束的凸优化问题是数学规划中的一类经典问题。本文将借助对偶理论, 研究求解一类具有线性等式约束的凸优化问题的加速算法。由于此类问题的对偶问题是一个具有两块可分离结构的凸优化问题, 我们基于Goldstein等人在加速交替方向乘子法方面的重要工作, 提出了一种在弱化条件下求解线性等式约束凸优化问题的加速方法。我们的方法与Goldstein等人的加速交替方向乘子法的不同之处为:1) 目标函数仅要求具有凸性(而不必强凸);2) 罚参数仅要求$\beta>0$(而不受目标函数的利普希茨常数、强单调系数的限制)。基于上述弱化的条件, 我们证明了所提的加速交替方向乘子法依然具有收敛性和O(1/k2)的收敛率。我们将条件弱化后的加速交替方向乘子法用于求解一个图像重建问题。数值实验结果表明, 条件弱化后的加速交替方向乘子法依然具有较好的数值效果。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    2. 单边相对光滑非凸-凹极小极大问题的镜像梯度算法
    徐洋, 王军霖, 徐姿
    运筹学学报(中英文)    2024, 28 (1): 18-28.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.002
    摘要226)   HTML7)    PDF(pc) (762KB)(110)    收藏

    本文提出了一种镜像梯度下降梯度上升算法来求解单边相对光滑的非凸-凹极小极大问题。在算法的每次迭代中, 我们采用镜像梯度下降步来更新相对光滑的变量, 采用梯度上升投影步来更新目标函数中光滑的变量。本文在理论上证明了算法收敛到$\varepsilon$-近似一阶稳定点的迭代复杂度是$\mathcal{O}\left( \varepsilon^{-4} \right)$

    参考文献 | 相关文章 | 多维度评价 | 评论0
    3. N策略的双阶段休假M/M/1排队系统驱动的流体模型性能分析
    王勋, 徐秀丽
    运筹学学报(中英文)    2024, 28 (1): 29-39.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.003
    摘要174)   HTML3)    PDF(pc) (796KB)(67)    收藏

    基于工厂订单装配系统的运行机制, 本文构建并分析了具有N策略和两种混合休假策略的M/M/1排队系统驱动的流体模型。首先对驱动系统进行描述, 将马尔可夫过程的无穷小生成元写成块状雅克比矩阵形式。引入库存量建立三维马尔可夫过程, 得到稳态下流体排队满足的微分方程组, 运用矩阵分析方法和Laplace变换(LT) 方法得出系统平稳库存量的数学表达式。进而运用Laplace-Stieltjes变换(LST) 导出稳态条件下缓冲器的平均库存量。最后, 利用数值分析, 给出参数变化对系统性能指标的影响。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    4. 部分服务台同步多重休假的排队库存系统
    叶子钦, 岳德权
    运筹学学报(中英文)    2024, 28 (1): 40-56.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.004
    摘要150)   HTML2)    PDF(pc) (841KB)(48)    收藏

    本文研究了$\left({s, S}\right)$ 库存策略的多服务台排队库存系统, 其中库存为空时有部分服务台同步多重休假, 休假时间服从指数分布。顾客到达为泊松过程, 每个服务台的服务时间和补货时间均服从指数分布。利用拟生灭过程和矩阵几何解法, 计算了系统稳态概率和一些性能指标, 并给出了系统单位时间的平均费用函数。最后, 通过数值算例分析了参数对费用函数的影响, 并得到最优库存策略和最优平均费用。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    5. 基于三方演化博弈的突发公共卫生事件应急响应及仿真研究
    柯小玲, 刘正娟, 郭海湘, 陈高胜, 郑谋军
    运筹学学报(中英文)    2024, 28 (1): 57-76.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.005
    摘要1177)   HTML7)    PDF(pc) (1889KB)(61)    收藏

    突发公共卫生事件中地方政府、社会组织与公众的相互配合、协同响应是及时高效进行应急管理的必然选择。本文以新型冠状病毒肺炎为背景, 考虑应急响应过程中多主体之间的相互影响与博弈关系, 基于有限理性假设, 构建地方政府、社会组织与公众三方博弈主体的演化博弈动态模型。然后, 运用演化博弈理论和Lyapunov判别法分析三方主体演化模型的均衡点和渐进稳定性, 得到在不同条件下三方主体的演化稳定策略。最后, 对突发公共卫生事件不同阶段的三方主体应急响应的博弈行为进行仿真分析, 探讨地方政府的补贴政策、奖惩措施以及社会组织成本对博弈各方策略选择的影响。研究结果表明: (1) 在突发公共卫生事件应急响应的不同阶段, 各主体的决策选择是动态演变的; (2) 地方政府的补贴政策、奖惩措施以及社会组织成本对于主体的应急响应行为作用明显; (3) 各主体的初始参与意愿强弱对突发公共卫生事件应急响应的影响效果显著。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    6. 基于矩不确定模糊集的分布鲁棒风险-回报优化模型研究
    李颖涵, 童小娇, 杨柳
    运筹学学报(中英文)    2024, 28 (1): 77-88.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.006
    摘要284)   HTML6)    PDF(pc) (797KB)(90)    收藏

    本文研究随机变量分布不确定下的风险-回报优化模型。针对传统的风险-回报三类典型问题和分布不确定性背景, 提出了更一般性条件下的分布鲁棒风险-回报优化新模型; 基于矩不确定集合和优化对偶理论, 化简复杂的新优化模型为常规结构的非线性优化问题。理论上证明了分布鲁棒风险-回报三类优化模型效率前沿的等价性。数值实验验证了理论分析的有效性。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    7. 带隐藏约束昂贵黑箱问题的自适应代理优化方法
    白富生, 兰秘
    运筹学学报(中英文)    2024, 28 (1): 89-100.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.007
    摘要184)   HTML1)    PDF(pc) (874KB)(49)    收藏

    针对带隐藏约束的昂贵黑箱全局优化问题, 提出采用自适应转换搜索策略的代理优化方法。在转换搜索子步中采用与已估值点个数相关的标准差在当前最优点附近通过随机扰动生成候选点, 以更好地平衡局部搜索和全局搜索。为更好地近似真实黑箱目标函数, 采用了自适应组合目标代理模型。在50个测试问题上进行了数值实验, 计算结果说明了所提算法的有效性。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    8. 天然气管网稳态运行优化模型的非线性界增强方法
    张晴, 陈亮, 艾文宝, 寇彩霞
    运筹学学报(中英文)    2024, 28 (1): 101-111.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.008
    摘要304)   HTML2)    PDF(pc) (873KB)(57)    收藏

    天然气管网稳态运行优化问题在提升能源使用效率、降低运行成本等多方面发挥着重要的作用。该问题由于网络结构复杂、规模大、非线性程度高, 所以建模成的混合整数非线性规划模型求解难度非常大。本文基于混合整数线性规划的界增强方法, 提出了适用于该问题结构的非线性界增强方法, 能够缩紧变量的上下界, 使得在线性化方法中更好地逼近原混合整数非线性规划模型。数值结果显示新的方法能够得到更优的可行解, 并且加快了天然气管网稳态运行优化问题的求解。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    9. 链图的距离特征值
    吕雪征, 马梦郁
    运筹学学报(中英文)    2024, 28 (1): 112-120.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.009
    摘要169)   HTML2)    PDF(pc) (716KB)(63)    收藏

    如果一个图G不包含2K2, C3C5作为导出子图, 称其为链图。在所有点数和边数给定的连通二部图中, 链图具有最大的谱半径, 这使得链图在图谱理论中占有一席之地。本文研究了连通链图距离特征值的分布情况。对于点数为n的连通链图G=G(t1, …, th; s1, …, sh), 我们证明了-2是G的重数为n-2h的距离特征值, 且Gh-1个距离特征值小于-2和h+1个距离特征值大于-2。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    10. 关于赋权非正则图的Aα特征值和特征向量
    何常香, 王文燕, 刘乐乐
    运筹学学报(中英文)    2024, 28 (1): 121-130.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.010
    摘要181)   HTML1)    PDF(pc) (710KB)(44)    收藏

    $G_\omega=(G, \omega)$是一个赋权图, 其邻接矩阵和赋权度对角矩阵分别$A(G_\omega)$$D(G_\omega)$。对于$\alpha\in[0, 1]$, $G_\omega$$A_\alpha$-矩阵为$ A_\alpha(G_\omega)=\alpha D(G_\omega)+(1-\alpha)A(G_\omega)$。对于连通赋权非正则图$G_\omega$, 给出了其关于$A_\alpha$-特征值的一些界, 并得到了$A_\alpha$-谱半径对应的特征向量中最大分量与最小分量比值的下界。

    参考文献 | 相关文章 | 多维度评价 | 评论0
    11. 可迹图的一些新充分条件
    余桂东, 刘珍珍, 王礼想, 李青
    运筹学学报(中英文)    2024, 28 (1): 131-140.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.011
    摘要169)   HTML2)    PDF(pc) (756KB)(64)    收藏

    设图$G$是一个简单连通图, $e(G)$$\mu(G)$$q(G)$分别为图$G$的边数、谱半径和无符号拉普拉斯谱半径。如果一个图含有一条包含所有顶点的路, 则这条路为哈密尔顿路, 称这个图为可迹图。本文主要研究利用$e(G)$$\mu(G)$$q(G)$分别给出图$G$是可迹图的一些新充分条件, 所得结果推广了已有的结论。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    12. 基于强乘积运算下图的广义和连通度指标上下界
    李志豪, 朱焱
    运筹学学报(中英文)    2024, 28 (1): 141-152.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.012
    摘要185)   HTML1)    PDF(pc) (742KB)(53)    收藏

    对于图$G$, 令$E(G)$表示$G$的边集, 令$V(G)$表示$G$的点集, $d_G(v)$表示$v$的度。对于边$e=uv$, 定义广义和连通度指标$\chi_\alpha(e)=(d_G(u)+d_G(v))^\alpha$, 其中$\alpha$为任一实数。本文先介绍了图的$S, R, Q, T$四种运算, 然后给出了四种运算下的强乘积, 并利用最大度最小度确定了其四种图的广义和连通度指标的上下界。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    13. 二维四角网格图的反馈数上界的改进
    苏雪丽, 李晓辉, 刘岩
    运筹学学报(中英文)    2024, 28 (1): 153-158.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.013
    摘要159)   HTML1)    PDF(pc) (1373KB)(52)    收藏

    $G=(V, E)$ 是简单图, 子集$F\subseteq V$。若由点集$V-F$ 导出的子图不含圈, 则称子集$F$ 是图$G$ 的反馈集。称反馈集的点数的最小值是图$G$ 的反馈数, 用$f(G)$ 表示,即,$f(G)=\min\{|F| : F$ 是图$G$ 的反馈集$\}$。Caragiannis等人给出了二维四角网格图反馈数的上界, 本文改进了其上界。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    14. 基于网络环境的若干组合优化博弈问题研究
    程郁琨, 韩鑫, 陈修杨, 张昭
    运筹学学报(中英文)    2024, 28 (2): 1-29.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.001
    摘要292)   HTML13)    PDF(pc) (1126KB)(252)    收藏

    随着互联网技术的飞速发展和社交网络的广泛普及, 大量现实问题可以模型化为基于网络环境的组合优化问题, 受到学术界和工业界的广泛关注。在这一过程中, 参与者通常受到个人利益的驱动, 采取策略性行动以实现自身效用的最大化。这种以“自利”为核心的行为模式, 不仅对其他参与者产生影响, 同时所有参与者的策略选择共同决定了社会福利整体目标的实现。在此背景下, 参与者之间的互动呈现出合作与竞争并存的复杂局面, 构成了组合优化博弈问题。本文旨在深入分析基于网络环境的三类具有挑战性的组合优化博弈问题: 网络上的公共品博弈、网络上的点覆盖博弈以及网络上的路由博弈。这三类问题不仅在组合优化和理论计算机科学领域占据着举足轻重的地位, 而且在管理科学与工程、经济学等多个交叉学科领域中也展现出广泛的应用前景。因此, 本文将系统性地介绍这三类组合优化博弈问题, 并对其最新的研究进展进行详细的梳理和深入的凝练, 以期为相关领域的研究者和实践者提供有价值的参考和启示。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    15. 基于消费者行为定价下制造商的网络渠道构建策略选择研究
    王滔
    运筹学学报(中英文)    2024, 28 (2): 30-46.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.002
    摘要230)   HTML2)    PDF(pc) (1128KB)(69)    收藏

    考虑网络销售环境下企业基于消费者行为定价(BBP) 现象愈发凸显的现实, 本文建立了由一个电商平台和一个制造商所组成的网络渠道决策模型, 分别分析了制造商自建网络直接渠道模式和进驻电商平台模式下的相关决策问题, 并对不同模式下的均衡决策进行了比较。结果发现, 制造商自建网络直接渠道模式下, 电商平台将为新顾客提供较老顾客更低的价格, 而制造商则会根据自建渠道成本和消费者的购物成本来区别对待新老顾客; 制造商进驻电商平台模式下, 制造商会为新顾客提供更优惠的价格, 电商平台对待新老顾客的策略受佣金率的影响。此外, 当佣金率较低且平台使用费适中, 或佣金率适中且平台使用费较低时可以使得电商平台吸引制造商进驻的同时制造商也愿意进驻电商平台。最后, 我们发现要使得制造商自建网络直接渠道能够实施BBP需保证其自建渠道时单位产品的销售成本足够小; 而要使得制造商进驻电商平台时能够实施BBP则需保证电商平台收取的佣金率和平台使用费较低。借鉴算例发现, 制造商进驻电商平台能获得较自建网络直接渠道更多的生产者剩余, 而消费者剩余的情况刚好相反; 只有当消费者购物成本较大且佣金率较高时, 制造商进驻电商平台才会获得较自建渠道情形更多的社会福利。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    16. 一类自适应梯度裁剪的差分隐私随机梯度下降算法
    张家棋, 李觉友
    运筹学学报(中英文)    2024, 28 (2): 47-57.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.003
    摘要256)   HTML9)    PDF(pc) (842KB)(168)    收藏

    梯度裁剪是一种防止梯度爆炸的有效方法, 但梯度裁剪参数的选取通常对训练模型的性能有较大的影响。为此, 本文针对标准的差分隐私随机梯度下降算法进行改进。首先, 提出一种自适应的梯度裁剪方法, 即在传统裁剪方法基础上利用分位数和指数平均策略对梯度裁剪参数进行自适应动态调整, 进而提出一类自适应梯度裁剪的差分隐私随机梯度下降算法。其次, 在非凸目标函数的情况下对提出的自适应算法给出收敛性分析和隐私性分析。最后, 在MNIST、Fasion-MNIST和IMDB数据集上进行数值仿真。其结果表明, 与传统梯度裁剪算法相比, 本文提出的自适应梯度裁剪算法显著提高了模型精度。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    17. 一带一路背景下基于加权Owen值的多层次合作分配策略
    于晓辉, 李武, 李汉章
    运筹学学报(中英文)    2024, 28 (2): 58-70.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.004
    摘要360)   HTML4)    PDF(pc) (805KB)(110)    收藏

    联盟结构合作对策一般涉及两个层次合作: 局中人先组成小联盟, 然后再以小联盟整体参与大联盟的合作。由于一带一路倡议中小联盟群体参与合作项目往往话语权有限, 容易处于收益分配的劣势, 从而影响参与合作项目的积极性, 因而有必要对联盟结构合作对策及其求解方法做进一步的研究。基于此, 我们首先构造一种能够考虑小联盟规模对合作影响的新求解方法——加权Owen值。然后, 基于联盟结构合作对策与加权Owen值刻画一带一路倡议下的多层次、复杂交叉的合作关系, 获得各个单位参与跨境合作项目可能的收益分配范围及性质。最后, 通过算例演示了联盟结构合作对策分配策略的计算方法。因此, 基于加权Owen值计算各个单位参与跨境合作项目可能的收益分配范围, 为跨境合作的大项目提供一定的决策依据。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    18. 工件权重带限制的最小化最大加权完工时间的单机在线排序问题
    徐娟年, 马冉, 韩雯雯, 张玉忠
    运筹学学报(中英文)    2024, 28 (2): 71-80.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.005
    摘要186)   HTML4)    PDF(pc) (2542KB)(60)    收藏

    本文考虑了最小化最大加权完工时间的单机在线排序问题, 要求工件的权重在工件加工时间一定范围之内且工件的权重和工件加工时间具有一致性, 即$ ap_j\leq w_j\leq bp_j (a\geq\frac{\sqrt{5}-1}{2}b, b\geq a)$且若$ w_i>w_j$$ p_i\geq p_j$, 如果$ w_i=w_j$$ p_i=p_j$。工件以时间在线的方式到达, 只有工件$ J_j$在达到释放时间$ r_j$后, 决策者才知晓工件的基本信息, 如加工时间$ p_j$和权重$ w_j$。对于此问题, 首先利用对手法证明了其下界为$ 1+\frac{b}{b+a}$, 随后给出了竞争比为$ 1+\frac{b}{b+a}$的最好可能的在线算法。特别地, 当$ a=\frac{\sqrt{5}-1}{2}b$时, 该算法的竞争比为$ \frac{\sqrt{5}+1}{2}$

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    19. 连续非单调变分不等式的一种惯性投影算法
    叶明露, 黄明
    运筹学学报(中英文)    2024, 28 (2): 81-92.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.006
    摘要180)   HTML4)    PDF(pc) (746KB)(82)    收藏

    一种求解非单调变分不等式问题的投影算法(IPA) 由Ye (2022) 提出。IPA无需变分不等式的映射具有任何的单调性, 仅在映射连续且对偶变分不等式解集非空的条件下得到了算法的全局收敛性。本文提出了惯性的IPA算法, 并在相同的假设下证明了新算法的全局收敛性。数值实验表明, 惯性方法能加速IPA。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    20. 基于拉格朗日松弛的产能共享讨价还价研究
    吴琼, 王长军
    运筹学学报(中英文)    2024, 28 (2): 93-102.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.007
    摘要227)   HTML2)    PDF(pc) (908KB)(84)    收藏

    以制造业产能共享为背景, 考虑自利的产能提供方与需求方诉求不一致和市场关系不对等因素, 采用Nash讨价还价理论研究共享产能分配策略。为此, 首先将传统调度模型与非对称Nash讨价还价模型相结合, 构建出本质为非线性整数规划的产能共享模型。继而, 设计了基于拉格朗日松弛的求解算法, 给出了产能共享的讨价还价分配结果。仿真分析表明, 本文方法在大部分情况下能够获得理想的讨价还价结果。当产能提供方目标为min-sum型, 其关注所有客户的自利且异质的时效要求, 其与客户方的冲突尤其显著; 随着其讨价还价能力的增强, 其改善是以牺牲客户时效要求为代价的。然而当其讨价还价能力再继续增加, 反而导致系统整体效益的波动。因此, 博弈各方需要保持合理的讨价还价强度。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    21. 基于多种保险业务和竞争的鲁棒最优再保险
    杨鹏
    运筹学学报(中英文)    2024, 28 (2): 103-116.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.008
    摘要156)   HTML3)    PDF(pc) (837KB)(54)    收藏

    本文基于均值-方差准则, 研究了一个保险公司与一个再保险公司之间竞争下的鲁棒最优再保险问题。保险公司经营$ n $种相依保险业务, 它对每种保险业务购买再保险来减少索赔风险。通过相对业绩, 本文量化了保险公司与再保险公司之间的竞争。保险公司的目标是, 在最坏市场情形下, 给定终端财富的均值时, 选择最优再保险策略使其面临的风险最小。通过应用随机控制和随机动态规划理论, 建立了Hamilton-Jacob-Bellman-Isaacs (HJBI)方程。进而, 通过求解HJBI方程, 并利用拉格朗日对偶理论, 本文得到了鲁棒最优再保险策略的解析解。最终, 通过数值实验解释了模型参数对鲁棒最优再保险策略和有效前沿的影响。研究结果可以指导保险公司在经营多种保险业务时, 采取最优再保险策略, 使其面临的风险最小。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    22. 定向距离函数的光滑化方法及其应用
    李鑫怡, 高英, 赵春杰
    运筹学学报(中英文)    2024, 28 (2): 117-130.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.009
    摘要190)   HTML20)    PDF(pc) (936KB)(76)    收藏

    本文考虑定向距离函数的光滑化表示及其应用。首先在已有的两种光滑化方法的基础上, 给出了这类特殊的非光滑函数的光滑化表示。作为特例, 在二维空间中, 给出该函数更具体的光滑化函数。最后利用定向距离函数的光滑化函数以及它在多目标优化问题标量化方法中的应用, 建立非光滑多目标优化问题的光滑标量化模型, 并给出了两者之间解集的关系。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    23. 基于Polyak步长的加速临近随机方差缩减算法
    王福胜, 史鲁玉
    运筹学学报(中英文)    2024, 28 (2): 131-142.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.010
    摘要174)   HTML7)    PDF(pc) (24485KB)(81)    收藏

    针对大规模机器学习中随机复合优化问题, 本文将加速临近随机方差缩减算法(Acc-Prox-SVRG)和Polyak步长方法相结合, 提出了一种新的加速临近随机方差缩减算法(Acc-Prox-SVRG-Polyak)。相比于已有算法, 新算法充分利用加速技术和Polyak步长的优越性, 提高了准确率。在通常的假定下论证了算法的收敛性, 并分析了复杂度。最后, 数值实验验证了新算法的有效性。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    24. 给定独立数的树的倒数度距离
    邢抱花, 孙旻昊, 余桂东
    运筹学学报(中英文)    2024, 28 (2): 143-150.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.011
    摘要158)   HTML0)    PDF(pc) (1242KB)(35)    收藏

    $G$是一个简单的无向连通图, $T_{n, \alpha}$是顶点数为$n$独立数为$\alpha$的所有树的集合。本文主要讨论了在集合$T_{n, \alpha}$中的最大倒数度距离, 并刻画了唯一对应的极图。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    25. 有向网络中最大容量支撑树形图扩容问题
    杨子兰, 朱娟萍, 杨宇
    运筹学学报(中英文)    2024, 28 (2): 151-158.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.012
    摘要180)   HTML0)    PDF(pc) (802KB)(87)    收藏

    针对有向网络中最大容量支撑树形图扩容问题(EMCSA), 由0-1背包问题出发归约出EMCSA问题的一个实例, 从而证明EMCSA问题是NP-困难的, 并且给出解决EMCSA问题的一个启发式算法。最后, 考虑EMCSA问题的一种特殊情况: 有向网络中最大容量支撑树形图的最少弧扩容问题(NEMCSA), 采用权重差最小换弧方法设计时间复杂度为$O(mn) $的多项式时间算法。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    26. 前言
    向淑文
    运筹学学报(中英文)    2024, 28 (3): 0-.  
    摘要190)      PDF(pc) (3219KB)(113)    收藏
    相关文章 | 多维度评价 | 评论0
    27. 共识博弈与区块链生态共识均衡
    袁先智
    运筹学学报(中英文)    2024, 28 (3): 1-26.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.03.001
    摘要331)   HTML12)    PDF(pc) (1323KB)(74)    收藏

    本文的目的是建立刻画区块链生态系统行为表现的“共识博弈”的一般框架, 并针对“矿池间隔博弈”的“共识均衡”的存在性进行刻画和解读。特别是通过引进共识博弈这个新概念作为出发点, 尽管区块链平台生态本身会受到诸如挖矿间隔等行为的干扰, 我们证明了在合理的激励机制下一般区块链平台的共识博弈均衡点的存在性, 从正面的角度回答了区块链生态本身发展是否稳定这个非常基本和核心的问题。这里, “间隔博弈”(不良) 行为出现所在的区块链生态是指基于 Nakamoto 在 2008 年提出的遵循按照最长主链建设的“工作量证明”作为基本的共识原则的挖矿平台。特别地, 本文首先在一般激励机制条件下, 基于区块链生态中的共识博弈框架, 在有挖矿间隔等不良行为出现的情况下, 建立了在一般激励相容机制条件下的共识均衡点的存在性结果和对应区块链生态能够持续运转的稳定性解读; 然后结合在“挖(币) 矿”工作中涉及到的工作费用、奖励机制和挖矿能力这三类描述激励机制的核心要素, 从挖矿工(组) 收益的角度, 针对不同嵌入场景对挖矿工(组) 的“间隔博弈行为”可能产生的影响进行了解读和分析。本文的理论结果和案例分析表明, 结合不同挖矿场景相合适的激励相容机制, 共识博弈(均衡) 这个概念可以在理论的层面(即, 不需要情景数据模拟结果的支持), 能够得到或形成针对不同场景下的挖矿行为的解释和解读。此外, 我们有理由期待和相信, 结合影响挖矿(组) 收益相关的要素因子, 共识博弈可以帮助我们构建对应的合适场景的激励相容机制, 通过刻画挖矿工(组) 出现的诸如“间隔行为”, “分叉链”, “矿池攻击”等(不良) 行为, 支撑数字经济的健康发展, 并对共识经济学基础理论的发展能够起到推进作用。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    28. 群体博弈理论的新进展
    杨辉
    运筹学学报(中英文)    2024, 28 (3): 27-45.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.03.002
    摘要464)   HTML7)    PDF(pc) (896KB)(125)    收藏

    群体博弈理论是近三十年来发展起来的博弈论的新方向, 源于1950年J. Nash在其博士学位论文中关于有限非合作博弈混合策略和平衡点的“Mass-Action”解释, 建立了由众多个体组成的群体及社会中, 个体的理性决策行为理论, 在社会学、生物学、经济学、管理学、信息科学等领域有广泛和深入的应用。本文介绍近年来群体博弈理论的研究成果及新进展, 探讨群体博弈理论的发展动向。

    参考文献 | 相关文章 | 多维度评价 | 评论0
    29. 群体追逃微分博弈
    高红伟, 孟斌斌, 刘剑, 戴照鹏
    运筹学学报(中英文)    2024, 28 (3): 46-62.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.03.003
    摘要367)   HTML4)    PDF(pc) (817KB)(126)    收藏

    本文以微分博弈和经典的追逃问题为主线, 对群体追逃微分博弈的历史发展脉络进行梳理。针对大规模群体追逃问题, 从平均场博弈视角出发, 阐释了强化学习技术的应用前景。提出探索解决逆向追逃微分博弈的观点, 可适用于水下无人舰艇、陆地机器人以及空中无人机集群等同类场景。区别于其他综述性文章, 作者对于俄罗斯以及苏联在本领域发展历史中代表性的学术流派给予了较多关注。

    参考文献 | 相关文章 | 多维度评价 | 评论0
    30. 效用可转移合作博弈的Shapley值公理化研究进展综述
    李文忠, 徐根玖
    运筹学学报(中英文)    2024, 28 (3): 63-80.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.03.004
    摘要302)   HTML0)    PDF(pc) (825KB)(75)    收藏

    随着全球经济融合和国际关系日益紧密, 合作共赢已然成为当今时代的核心趋势。合作博弈理论作为研究合作问题的有力工具, 主要探讨如何在参与者之间分配合作所产生的收益。Shapley值作为合作博弈中最重要的单值解之一, 具有重要研究意义与价值。本文将主要介绍目前Shapley值公理化的研究工作, 从可加性、均衡贡献性、边际性、公平性、简约一致性、相关一致性和一些特殊的参与者性的角度, 分别归纳整理了Shapley值基于这些性质的公理化研究结论。最后对未来研究进行了展望。

    参考文献 | 相关文章 | 多维度评价 | 评论0
    31. 池化、专业化和自主完成任务如何影响平均队列长度
    江厚元
    运筹学学报(中英文)    2024, 28 (3): 81-96.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.03.005
    摘要255)   HTML3)    PDF(pc) (1183KB)(50)    收藏

    在排队系统中, 池化、去池化/专业化和自主完成任务是典型的运营操作策略, 这些策略在医疗保健、电话服务中心和线上销售中有广泛应用。这些策略在不同的操作环境中可能有优劣之分。本文使用$M/M/1$$M/M/2$排队模型研究池化、专业化和自主完成任务对平均队列长度的影响。我们推导出$M/M/2$排队系统的平均队列长度的解析式。通过计算实例展示池化、专业化和自主完成任务如何影响平均队列长度的变化。最后, 本文提出了几个猜想。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    32. 相关私有信号对连续时间内部交易的影响
    周永辉, 肖凯
    运筹学学报(中英文)    2024, 28 (3): 97-107.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.03.006
    摘要233)   HTML0)    PDF(pc) (720KB)(59)    收藏

    本文研究了一个连续时间内部交易模型, 其中风险中性内部交易者拥有风险资产的两个不完全相关信号。利用条件期望理论和滤波理论, 首先, 本文建立了三个引理: 分别是正态相关性、等价定价和等价利润, 这三个引理能使得本文中非完全信息内部交易模型转换成完全信息的情形。其次, 本文研究了不完全相关的两个信号对由最优内部交易策略和市场半强有效性定价所组成的均衡的影响。研究表明, 在均衡状态下, (1)市场深度随时间变化是恒定的; (2)如果这两个相关私有信号的噪声不线性相关, 那么内部交易者的所有私人信息最终都会被纳入价格中, 但是风险资产的信息并不会完全被纳入价格中; (3)如果这两个相关私有信号的噪声线性相关, 那么内部交易者能够推断出风险资产的全部信息, 最终本文模型就转换成了内部交易者掌握风险资产全部信息的内部交易模型; (4)如果相关私有信号的噪声相同, 那么内部交易者的期望利润随着观察精度的降低会增加, 而随着观察精度越高, 内部交易者的期望利润也慢慢趋于0;(5)如果两个相关私有信号的噪声不线性相关, 那么在其中一个噪声信号固定的情况下, 内部交易者的期望利润是单峰的, 且相对于另一个相关噪声信号有唯一的最小值, 此外, 当相关私有信号的噪声变成0时, 内部交易者期望利润达到最大, 即内部交易者观察到了真实的风险资产。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    33. 基于Markov模型的低风速地区风力发电机预防性维护优化策略
    张大永, 王红蕾
    运筹学学报(中英文)    2024, 28 (3): 108-120.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.03.007
    摘要257)   HTML4)    PDF(pc) (1123KB)(89)    收藏

    在“3060”双碳战略目标下, 随着风电产业的迅速发展, 预防性维护已然成为提高风力发电机运行可靠性的重要手段。关于复杂环境下风力发电机的运行管理尚存在对退化状态认识不充分、维修策略不可靠等问题。本文以期望成本最小化为目的, 考虑风力发电机关键部件退化过程与多阶段预防性维护策略的关系, 构建基于Markov状态转移的多阶段预防性维护成本模型。首先, 依据设备衰退规律, 利用Markov链的转移概率对退化状态、维护策略进行刻画。其次, 引入可靠度、故障率、役龄因子计算多阶段预防性维护时长和故障时长; 再进一步考虑天气条件对维护成本模型的影响, 构建风力发电机在整个维护周期内的期望成本模型。最后, 利用数值分析对模型进行求解。结果表明, 实施最小、更换维护策略的期望成本占据了总维护成本的80%以上, 相比之下, 采取预防性维护优化策略的期望成本则低于总维护成本的20%, 故该策略可为低风速地区的风电企业提供有效的决策参考, 提高风力发电机的运行可靠性。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    34. 合作博弈两类组合解的社会可接受性
    孙攀飞, 孙浩
    运筹学学报(中英文)    2024, 28 (3): 121-131.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.03.008
    摘要280)   HTML4)    PDF(pc) (726KB)(91)    收藏

    如何寻求公平合理的分配方案(即博弈的解)是合作博弈的重要研究内容, 依据博弈参与者边际贡献的分配原则和考虑参与者内在联系的社会性分配原则被广泛应用于博弈解的定义。不同的博弈组合解往往同时体现了这两类分配原则。针对现有组合解中组合参数的外生性以及缺乏合理性解释的问题, 本文利用博弈解的社会可接受性, 主要研究了基于Shapley值、Solidarity值、ENSC值以及均分值的两类组合解, 给出了组合解中参数范围选取的充分(必要)条件, 阐明了不同社会可接受性之间的关系, 揭示了组合系数对博弈参与者行为的影响。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    35. 博弈论和经济学中均衡不存在的解读
    曹志刚, 宋瑾, 王思杰, 朱峰
    运筹学学报(中英文)    2024, 28 (3): 132-142.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.03.009
    摘要327)   HTML4)    PDF(pc) (872KB)(54)    收藏

    均衡概念的提炼和形式化是博弈论学科创立的标志, 博弈论的发展是围绕各种均衡概念的基本性质展开的。一般认为, 均衡不存在是一个负面结果, 均衡不存在研究就没法推进。对于经济学研究而言也是如此。本文通过文献中非合作博弈和完全竞争市场中的两个例子说明, 有时候可以对均衡不存在给出有价值的解释。第一个例子通过网络硬币匹配博弈研究时尚现象的演化, 均衡不存在用来解读时尚周期的出现。第二个例子介绍的是完全竞争劳动力市场中公司与工人间的匹配问题, 均衡不存在用来解读提前签约现象。我们还简要介绍了Shapley关于效用可转移合作博弈核心为空集的精彩解读。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    36. 具有加性耦合效用和连续统参与人博弈中的强Nash均衡
    杨哲
    运筹学学报(中英文)    2024, 28 (3): 143-152.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.03.010
    摘要272)   HTML2)    PDF(pc) (727KB)(61)    收藏

    本文将研究具有加性耦合效用和连续统参与人博弈中的强Nash均衡。我们首先证明具有加性耦合效用和有限参与人博弈中强Nash均衡的存在性。进一步, 对具有加性耦合效用和连续统参与人的博弈, 我们引入弱强Nash均衡的概念, 并证明它的存在性定理。本文发展了强Nash均衡的研究。

    参考文献 | 相关文章 | 多维度评价 | 评论0
    37. 不连续向量支付博弈α-核的存在性与稳定性
    宋奇庆, 池欣宜, 吴高宇, 孙铭璐
    运筹学学报(中英文)    2024, 28 (3): 153-164.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.03.011
    摘要330)   HTML4)    PDF(pc) (782KB)(114)    收藏

    本文研究了不连续向量支付博弈α-核的存在性和稳定性, 提出了向量支付博弈的联盟最小值条件和向量支付博弈的联盟C-安全性条件, 从而给出了保证不连续向量支付博弈α-核存在的两类充分条件, 进一步利用广义Hadmard良定性的引理, 证明了一类不连续向量支付博弈α-核的良定性。

    参考文献 | 相关文章 | 多维度评价 | 评论0
    38. 具有修正(p, N)-策略与单重休假的M/G/1排队分析
    罗彦君, 唐应辉
    运筹学学报(中英文)    2024, 28 (4): 1-17.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.04.001
    摘要338)   HTML5)    PDF(pc) (941KB)(48)    收藏

    本文考虑一个具有修正$(p, N)$-策略和单重休假的$M/G/1$排队系统, 其中修正$(p, N)$-策略是指当服务员的休假结束回到系统时, 如果系统中有顾客但顾客数少于$N$, 则服务员以概率$p(0 \le p \le 1)$启动服务, 以概率$(1-p)$不启动服务直到系统中的顾客数累积到$N$个。运用更新过程理论、全概率分解技术和Laplace变换工具, 我们讨论了系统队长的瞬态分布, 得到队长瞬态分布关于时间$t$的L变换表达式。然后使用洛必达法则, 通过直接运算得到队长稳态分布的递推公式, 同时获得稳态队长分布的概率母函数和平均队长的显示表达式。最后, 应用更新报酬定理给出系统在长期运行单位时间内的期望费用的显示表达式, 并通过数值实例讨论了使得系统期望费用最小的最优控制策略$N^*$, 以及休假时间为定长$T(T\geqslant 0)$时的二维最优控制策略$(N^*, T^*)$

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    39. 加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究
    李文杰, 杜智慧, 苏孟龙
    运筹学学报(中英文)    2024, 28 (4): 18-28.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.04.002
    摘要346)   HTML4)    PDF(pc) (766KB)(28)    收藏

    本文研究NDP约束下的最小化最大运输完工时间单机在线排序问题。这里的“NDP约束”是指当有工件到达时, 则空闲机器必须立刻选择工件加工, 即工件不能被强制推迟加工。本文讨论所有工件的加工时间与运输时间均具有一致性的排序模型, 即若工件$J_{i}$$J_{j}$的加工时间满足$p_{i}\geq p_{j}$, 则其运输时间满足$q_{i}\geq q_{j}$。我们首先给出NDP约束下该排序问题的下界为4/3, 其次设计出一个竞争比是1.382的在线算法。

    参考文献 | 相关文章 | 多维度评价 | 评论0
    40. 基于秩2矩阵近似的飞机起降多目标调度模型与算法研究
    徐博, 马卫民, 柯华, 张浩
    运筹学学报(中英文)    2024, 28 (4): 29-43.   DOI: 10.15960/j.cnki.issn.1007-6093.2024.04.003
    摘要395)   HTML2)    PDF(pc) (976KB)(29)    收藏

    飞机起降调度问题是当前机场运营的重要问题, 调度的一个难点在于调度效率提升需要空管发出大量复杂指令, 导致空管工作量骤升, 超负荷工作易引起人员疲劳产生决策失误和安全隐患。鉴于此构建了单跑道起降调度的多目标混合整数规划模型, 既提升跑道效率又避免过度增加空管工作量。设计了基于秩2矩阵近似的蚁群算法(RMA-AC)求解, 并与CPLEX和经典M-TPLP算法进行对比。数值仿真证实三种方法都优于当前航空系统广泛使用的FCFS算法; 新算法RMA-AC在跑道效率提升方面强于CPLEX, 在控制飞机位置总偏移量方面强于M-TPLP, 实现了平衡跑道效率和空管工作量。这些对于提高机场效率, 降低航空拥堵, 实现安全调度具有积极意义。

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