当期目录

2024年 第28卷 第2期    刊出日期：2024-06-15

上一期    下一期

 

基于网络环境的若干组合优化博弈问题研究

程郁琨, 韩鑫, 陈修杨, 张昭

2024, 28(2):  1-29.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.001

摘要 ( 289 )   HTML ( 13)   PDF (1125KB) ( 252 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

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

基于消费者行为定价下制造商的网络渠道构建策略选择研究

王滔

2024, 28(2):  30-46.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.002

摘要 ( 229 )   HTML ( 2)   PDF (1128KB) ( 68 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

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

一类自适应梯度裁剪的差分隐私随机梯度下降算法

张家棋, 李觉友

2024, 28(2):  47-57.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.003

摘要 ( 253 )   HTML ( 9)   PDF (842KB) ( 168 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

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

一带一路背景下基于加权Owen值的多层次合作分配策略

于晓辉, 李武, 李汉章

2024, 28(2):  58-70.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.004

摘要 ( 359 )   HTML ( 4)   PDF (805KB) ( 109 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

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

工件权重带限制的最小化最大加权完工时间的单机在线排序问题

徐娟年, 马冉, 韩雯雯, 张玉忠

2024, 28(2):  71-80.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.005

摘要 ( 183 )   HTML ( 4)   PDF (2542KB) ( 59 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

本文考虑了最小化最大加权完工时间的单机在线排序问题, 要求工件的权重在工件加工时间一定范围之内且工件的权重和工件加工时间具有一致性, 即$ 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}$。

连续非单调变分不等式的一种惯性投影算法

叶明露, 黄明

2024, 28(2):  81-92.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.006

摘要 ( 176 )   HTML ( 4)   PDF (746KB) ( 80 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

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

基于拉格朗日松弛的产能共享讨价还价研究

吴琼, 王长军

2024, 28(2):  93-102.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.007

摘要 ( 221 )   HTML ( 2)   PDF (908KB) ( 84 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

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

基于多种保险业务和竞争的鲁棒最优再保险

杨鹏

2024, 28(2):  103-116.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.008

摘要 ( 149 )   HTML ( 3)   PDF (837KB) ( 54 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

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

定向距离函数的光滑化方法及其应用

李鑫怡, 高英, 赵春杰

2024, 28(2):  117-130.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.009

摘要 ( 187 )   HTML ( 20)   PDF (936KB) ( 76 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

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

基于Polyak步长的加速临近随机方差缩减算法

王福胜, 史鲁玉

2024, 28(2):  131-142.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.010

摘要 ( 170 )   HTML ( 7)   PDF (24485KB) ( 78 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

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

给定独立数的树的倒数度距离

邢抱花, 孙旻昊, 余桂东

2024, 28(2):  143-150.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.011

摘要 ( 157 )   HTML ( 0)   PDF (1242KB) ( 35 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

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

有向网络中最大容量支撑树形图扩容问题

杨子兰, 朱娟萍, 杨宇

2024, 28(2):  151-158.  doi:10.15960/j.cnki.issn.1007-6093.2024.02.012

摘要 ( 179 )   HTML ( 0)   PDF (802KB) ( 87 )  

数据和表 | 参考文献 | 相关文章 | 多维度评价

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