运筹学学报（中英文）

刘文烨, 岳德权

2025, 29(4): 1-13. doi:10.15960/j.cnki.issn.1007-6093.2025.04.001

摘要 ( 9 )

PDF (662KB) ( 3 )

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

本文研究了具有服务员工作休假的M/M/1 生产库存系统, 当系统中顾客数为零时服务员开始多重工作休假。基于$(s,S)$ 库存策略, 建立系统中顾客数、库存水平、服务员状态和生产状态的四维 Markov 过程。利用拟生灭过程理论得出了系统稳态条件, 进而求出了系统稳态性能指标和系统费用函数, 分析了系统各项参数对性能指标和库存策略的影响, 对比分析了不同工作休假服务率下的最优库存策略和最优费用。

考虑人员不可用及工件带退化效应的单机排序问题

李大伟, 李刚刚

2025, 29(4): 14-26. doi:10.15960/j.cnki.issn.1007-6093.2025.04.002

摘要 ( 8 )

PDF (602KB) ( 2 )

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

本文主要研究人员不可用及工件带退化效应的单机排序问题, 目标是极小化工件的加权总完工时间。与机器有不可用时间限制的排序问题不同, 工件可以在人员不可用的时间段内加工, 但是不能在这个时间段内开工也不能在这个时间段内完工。我们首先证明当存在两个人员不可用的时间段时, 这个问题不存在最坏情形性能比为常数的多项式时间近似算法, 除非P=NP。当只存在一个人员不可用的时间段时, 我们给出一个伪多项式时间算法和一个完全多项式时间近似方案(FPTAS)。

广义约束条件下矩阵方程AXB+CYD=E最佳逼近解的迭代算法

杨家稳, 孙合明

2025, 29(4): 27-47. doi:10.15960/j.cnki.issn.1007-6093.2025.04.003

摘要 ( 10 )

PDF (692KB) ( 3 )

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

为了求在广义约束$GX=H, \ WY=U$条件下矩阵方程$AXB+CYD=E$的最佳逼近解, 提出了一种迭代算法。该算法思路是首先分别求出目标函数$F(X,Y)={{\left\| E-AXB-CYD \right\|}^{2}}$ 在矩阵$X,\ Y$处的梯度; 然后将负梯度分别投影到凸约束集中得到${g}_{X}$和${g}_{Y}$;最后按照共轭梯度法思想,基于${{g}_{X}}$和${{g}_{Y}}$在可行域上再构建搜索方向${{d}_{X}}$和${{d}_{Y}}$。理论表明对于任给一个满足广义约束的一类特殊初始矩阵对$({{X}^{(1)}},{{Y}^{(1)}})$,算法能够在有限迭代步内得到约束条件下矩阵方程$AXB+CYD=E$的极小范数最小二乘解。另外通过求矩阵方程$A\tilde{X}B+C\tilde{Y}D=\tilde{E}$ 的极小范数最小二乘解可得给定逼近矩阵对$\left( \bar{X},\,\bar{Y} \right)$的最佳逼近解,其中$\tilde{E}=E-A\bar{X}B-C\bar{Y}D$。数值例子表明该算法不仅可以解决广义约束条件下矩阵方程的最佳逼近解,也可以解决特殊约束条件下方程的最佳逼近解。

边界防御多人追逃微分博弈模型

苏昂, 王磊, 党志清, 游志航, 高红伟

2025, 29(4): 48-60. doi:10.15960/j.cnki.issn.1007-6093.2025.04.004

摘要 ( 16 )

PDF (1706KB) ( 3 )

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

保护边界安全一直以来是一个热点问题, 边界线形状的复杂多变增加了边界防御问题研究的复杂性。本文通过对边界防御场景的刻画, 将问题转化为追逃微分博弈问题, 进而求解出此博弈中局中人的最优策略, 并给出切实可行的算法。本文运用简单运动刻画局中人的运动, 运用二次曲线的一般方程形式刻画边界形状, 定义支付函数为捕获点到边界的距离。通过几何方法对问题进行研究, 得到了圆形边界情形下更加简洁的值函数形式, 并构造出局中人的最优策略。在圆形边界的基础上, 进一步得到针对二次曲线边界情形下的通用算法。最后对模型进行从定量到定性、从二维到三维、从多追一到多追多的完善, 并通过数值仿真验证了结论与算法的正确性。

锥约束优化问题的精确罚逼近

池倩倩, 周育英

2025, 29(4): 61-71. doi:10.15960/j.cnki.issn.1007-6093.2025.04.005

摘要 ( 10 )

PDF (536KB) ( 3 )

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

本文利用罚逼近的方法研究在完备度量空间中的锥约束优化问题。在不需要假设目标函数强制及约束函数为凸函数的情况下, 利用一类$\mu$函数的性质、Ekeland 变分原理以及一些新的技巧, 证明存在一个罚因子,其对应的无约束罚问题存在近似解,从而得到原锥约束优化问题近似解的存在性。

弱半E-凸规划问题的最优性条件

王小芳, 梁治安, 高彩霞

2025, 29(4): 72-82. doi:10.15960/j.cnki.issn.1007-6093.2025.04.006

摘要 ( 10 )

PDF (554KB) ( 4 )

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

本文引入了一类新的广义凸函数: 弱半$E$-凸函数, 建立了其对应的弱半$E$-凸规划问题; 讨论了弱半$E$-凸规划问题的解的性质, 并给出弱半$E$-凸规划问题的最优性条件。

带有交货期的一类柔性流水车间调度问题的合作博弈

孙文娟, 宫华, 许可, 申爱红

2025, 29(4): 83-93. doi:10.15960/j.cnki.issn.1007-6093.2025.04.007

摘要 ( 5 )

PDF (660KB) ( 2 )

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

本文利用合作博弈理论研究了带有交货期的一类柔性流水车间调度问题。具有初始调度顺序的工件需要依次经过多道工序加工,每道工序有多台同速并行机。工件所属客户的成本为工件完工时间的线性加权与拖期惩罚费用之和。考虑到客户可以通过合作结成联盟,并在联盟内重新调度以节省成本, 以客户为博弈方,以联盟最大成本节省为特征函数建立合作博弈模型。通过分析合作博弈性质,寻求合理的成本节省分配方法以降低客户成本。当工件的加工时间与工序相关且具有公共交货期时,证明了合作博弈为凸博弈, $\beta$ 规则和Shapley值均能得到一个核心分配, 并且给出了Shapley值的一种简单计算形式。数值算例验证了合作博弈模型的性质及成本分配方法的合理性。

生成线性森林的极值问题

季雪, 康丽英, 薛益赛

2025, 29(4): 94-102. doi:10.15960/j.cnki.issn.1007-6093.2025.04.008

摘要 ( 7 )

PDF (560KB) ( 2 )

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

设$\mathcal{F}$ 是一个图族, 如果$G$ 不包含$\mathcal{F}$ 中的任意一个图作为子图, 则称$G$ 是禁用图族$\mathcal{F}$ 的。禁用图族$\mathcal{F}$ 的$n$ 阶图所能达到的最大边数称为$\mathcal{F}$ 的Turán 数, 记作$ex(n,\mathcal{F})$。线性森林是指连通分支都是路或孤立点的图。设$\mathcal{L}_{n,k}'$ 是一个除图$P_{k+1}\cup(n-k-1)K_1$ 外, 包含其他所有边数为$k$ 的$n$ 阶线性森林组成的图族。本文给出了$\mathcal{L}_{n,k}'$ 的Turán 数和对应的极值图。进一步我们给出了禁用$\mathcal{L}_{n,k}'$ 的$n$ 阶图的谱半径的最大值和对应的极值图。

具有前瞻区间和不相容工件族的两台流水车间在线排序问题

夏倩, 张新功

2025, 29(4): 103-111. doi:10.15960/j.cnki.issn.1007-6093.2025.04.009

摘要 ( 3 )

PDF (603KB) ( 2 )

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

本文研究两台单位流水作业上, 具有前瞻区间的两个不相容工件族无界批处理的在线排序问题。单位流水车间问题是指任何工件在每台机器上的加工长度均为$1$, 工件按时到达, 目标是最小化最大完工时间。具有前瞻区间是指在时刻$t$, 在线算法能预见$(t,t+\beta]$区间内到达工件的信息。不可相容工件族是指属于不同工件族的工件不能安排在同一批加工。本文提供了一个竞争比为$1+\alpha$的在线算法$A_1(\beta)$, 其中$\alpha=\displaystyle\frac{\sqrt{\beta^{2}-8 \beta+28}-(\beta+2)}{6}$$(\displaystyle\frac{\sqrt{21}-3}{6}<\alpha\leqslant \displaystyle\frac{\sqrt{7}-1}{3})$是方程$3 \alpha^{2}+(\beta+2) \alpha+\beta-2=0$ 的一个正根, 这里$0 \leqslant \beta<1$。

群体博弈的弱Nash平衡与演化分析

汤卫, 王春, 杨光惠, 皮进修

2025, 29(4): 112-120. doi:10.15960/j.cnki.issn.1007-6093.2025.04.010

摘要 ( 3 )

PDF (763KB) ( 1 )

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

在博弈的策略转移过程中, 如果局中人会获得策略转移成本,那么一些局中人的最优回应策略可能没有最大化支付。对此,本文在群体博弈模型下引入更一般的策略转移成本函数, 对弱Nash平衡概念进行改进, 新的弱 Nash 平衡包含 Nash 平衡集。此外, 我们在2×2 对称矩阵博弈诱导的单群体博弈下, 通过复制动力学得到了弱Nash 平衡稳定性, 并进行了仿真实验。结果表明,相比未考虑策略转移成本的情形, 演化稳定状态有所增加。

二阶分裂算法及其应用

谭子琳, 罗洪林

2025, 29(4): 121-140. doi:10.15960/j.cnki.issn.1007-6093.2025.04.011

摘要 ( 5 )

PDF (853KB) ( 1 )

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

本文针对一类大规模可分非凸优化问题,结合三次正则化和信赖域方法求解子问题, 同时利用非精确Hessian信息提出二阶分裂算法, 证明了算法的全局收敛性,并刻画了算法的复杂度$O\left( {{\varepsilon ^{ - 2}}}\right)$。应用该算法求解机器学习中的一类非凸二元分类问题,数值实验结果验证了算法的有效性。

针对炼油厂系统性运营优化问题的混合分布递归及分支定界算法

孙鑫, 葛冬冬, 付德生, 魏志伟, 董丰莲, 潘师畅

2025, 29(4): 141-158. doi:10.15960/j.cnki.issn.1007-6093.2025.04.012

摘要 ( 6 )

PDF (735KB) ( 2 )

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

炼油厂运营优化问题是原油产业链中非常重要的问题, 在学术界和工业界都有非常多的研究和应用。一般而言, 炼油厂优化问题会被建模为混合非线性整数规划问题(MINLP)。由于原油品种和相关产品繁多并且加工装置复杂多样, 所以变量维度较大。并且在具体的加工过程中涉及物料物性变化和加工规则, 从而产生非凸非线性和整数约束, 使得问题求解难度变大。目前学术界研究主要针对小规模问题或者运营流程的子系统进行建模求解, 并且求解方法集中在使用商用求解器, 如GAMS环境中的BARON、DICOPT等。本文针对炼厂优化的MINLP提出了一种混合分布递归和分支定界算法(Hybrid-DRBB), 分别对非线性约束和整数约束进行松弛和求解, 从而得到原问题的近似最优解。在实际的工业场景大规模数据中, 本文的算法速度被证实优于直接调用求解器的建模求解方式。

线性乘积和规划问题的基于D.C.松弛的分支定界算法

张博, 王红雨, 高岳林

2025, 29(4): 159-174. doi:10.15960/j.cnki.issn.1007-6093.2025.04.013

摘要 ( 3 )

PDF (603KB) ( 1 )

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

线性乘积和规划已出现在工程实践和管理科学等领域, 是一类NP-难问题。针对该问题目标函数的特殊结构, 将其重构为一个D.C. (difference ofconvex functions) 规划问题。再利用凹函数的凸包络, 构造出了一种D.C.松弛问题, 并将其分解为两个凸子问题。然后将该D.C. 松弛与超矩形的标准二分法相结合, 设计了新的分支定界算法, 并分析了其理论收敛性和计算复杂度。最后, 借助大量数值实验验证了该算法的有效性。

非精确广义不定邻近交替方向乘子法的收敛性分析

宋瑞, 王依冉, 吴中明

2025, 29(4): 175-190. doi:10.15960/j.cnki.issn.1007-6093.2025.04.014

摘要 ( 4 )

PDF (1341KB) ( 1 )

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

交替方向乘子法(ADMM)及其变种广泛应用于求解实际问题,但其有效性极大地依赖于子问题的求解。本文提出一类求解带线性约束可分凸优化问题的非精确广义不定邻近ADMM,其中一个子问题运用基于相对误差的非精确准则近似求解,该准则只涉及简单的调节参数; 另一个子问题引入不定邻近项。新算法继承了相对误差非精确准则和不定邻近项的优势,能有效提高适用性和求解效率。基于变分不等式框架, 分析了算法的收敛性。通过求解图像恢复问题, 验证了新算法的有效性。

修理设备可更换且修理工多重休假的机器维修模型等待时间分布函数研究

吴文青, 徐海文, 余玅妙, 郑克龙

2025, 29(4): 191-204. doi:10.15960/j.cnki.issn.1007-6093.2025.04.015

摘要 ( 5 )

PDF (821KB) ( 1 )

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

本文研究修理设备可更换, 且修理工多重休假的机器维修模型中, 故障机器的等待时间分布函数, 其中机器的工作时间和修理时间均服从负指数分布。利用吸收时间的马氏链过程、位相型分布和拉普拉斯--斯蒂尔切斯变换, 推导出了任意故障机器的等待时间分布函数及其平均等待时间的表达式。在此基础上, 讨论了故障机器等待时间分布函数随时间的变化情况, 并给出了相应的数值计算结果。

一类非负张量的谱半径的上界及其应用

王缘, 朱忠熏, 谭连生, 杨禹

2025, 29(4): 205-218. doi:10.15960/j.cnki.issn.1007-6093.2025.04.016

摘要 ( 4 )

PDF (571KB) ( 1 )

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

基于一类新的非负张量, 我们首先得到了一些与这类张量相关的组合恒等式。并利用这些组合恒等式, 得到了该类张量谱半径的紧上界及其对应的极值条件。最后作为应用, 得到了一些其他一般超图谱半径的紧上界, 并对其极值结构进行了刻画。

基于时间尺度变换的一类微生物批式流加发酵混杂切换系统的最优控制

王佳, 黄誉之, 叶剑雄

2025, 29(4): 219-230. doi:10.15960/j.cnki.issn.1007-6093.2025.04.017

摘要 ( 3 )

PDF (1360KB) ( 1 )

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

本文研究了一类微生物批式流加发酵生产1,3-丙二醇(1,3-PD) 的过程优化问题。该生物过程本质上可刻画为一个同时具有自治切换和受控切换的混杂切换系统。本文通过时间尺度变换, 将受控切换时刻映射到固定时刻, 得到一系列具有自治切换的子系统；然后, 以甘油流加时刻和发酵终端时刻为控制变量, 以终端时刻1,3-PD 生产强度最大化为目标函数, 建立最优控制模型, 利用约束转换技术处理连续状态不等式约束；最后, 构造一个竞争粒子群算法求解所提出的最优控制问题, 并比较了不同控制子周期长度下的最优控制结果。数值结果表明, 在减少甘油切换次数的情况下, 通过选取适当的甘油流加时长, 1,3-PD 生产强度也可以达到较高的水平。

考虑订单类型和准备时间的批处理机在线调度模型研究

靳凯媛, 郑斐峰, 刘明

2025, 29(4): 231-240. doi:10.15960/j.cnki.issn.1007-6093.2025.04.018

摘要 ( 5 )

PDF (736KB) ( 2 )

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

本文探讨了批容量有限的一类批处理机在线调度问题。在订单实时释放的场景下, 针对订单具有不同类型、同类型订单才能组批、不同类型订单批次之间需要既定准备时间、批处理时长依赖于订单类型的调度模型, 以最大化总完工收益为优化目标, 着重考察了两种加工情形。对于单台批处理机的在线模型, 证明了问题的竞争比下界为$1+w$, 其中$w$ 表示批次的最大完工收益。同时, 设计了考虑准备时间的在线算法, 并运用最坏情形分析法证明了其竞争比等于下界, 表明该算法具有最优竞争性。对于两台平行批处理机的情形, 提出了一个竞争比为$1+2\sqrt{w}$ 的在线算法。

给定直径的超树的第二大无符号拉普拉斯半径

余桂东, 袁慧, 谢欣宇

2025, 29(4): 241-248. doi:10.15960/j.cnki.issn.1007-6093.2025.04.019

摘要 ( 3 )

PDF (565KB) ( 1 )

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

谱极值与极图是当今图谱理论研究的热点问题,学者们非常关注研究图的谱半径达到最大或者最小值所对应的极图。本文刻画了直径为$4$ 的超树的第二大无符号拉普拉斯谱半径的极图。设$\mathbb{S}(m, 4, k)$ 是指有$m$ 条边直径为4 的$k$一致超树的集合, $S_3(m, 4, k)$ 是由直径为4的疏松路$v_1e_1v_2e_2v_3e_3v_4e_4v_5$ 在顶点$v_4$ 处悬挂$m-4$条边得到的$k$ 一致超树。本文首先介绍了超图中边扰动的定义以及相关定理。然后, 根据边扰动等方法,研究得出$S_3(m, 4, k)$ 是$\mathbb{S}(m, 4, k)$中无符号拉普拉斯谱半径达到第二大的图。

提前完工总量最大化问题的LPT算法

孙瑞卿, 张芮, 兰艳, 李伟东

2025, 29(4): 249-254. doi:10.15960/j.cnki.issn.1007-6093.2025.04.020

摘要 ( 7 )

PDF (505KB) ( 3 )

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

本文给定一个工件集和一个机器集, 将每一个工件分配给机器加工, 不允许中断。提前完工总量最大化问题试图寻找一个最佳调度方案, 使得所有工件的提前完工总量尽可能地大, 这里工件的提前完工量是指交货期前工件的已加工时长。本文证明了经典的LPT 算法的最坏情况界至多为1.207。

当期目录