本文引入了一种新的休假策略, 研究在该策略下带有损失销售和(s, S)库存策略的排队库存系统。当库存为空时, 服务员开始工作休假, 工作休假期间, 若补货成功, 服务员立刻开始正常服务顾客; 当工作休假结束时, 若库存仍为空, 服务员开始多重休假过程, 否则转为正常工作状态。利用马尔可夫过程方法对此系统进行稳态分析, 得到该策略下排队库存系统的稳态分布, 进而获得系统的一些稳态性能指标以及系统的平均费用函数。通过数值分析研究系统参数对最优策略和最优费用的影响。
设$\mathcal{H}$是一个图族。$\mathcal{H}$的平面Turán数, 记为$\text{ex}_{\mathcal{P}}(n,\mathcal{H})$, 表示不包含$\mathcal{H}$中任一个图的n阶平面图的最大边数。本文研究图的特定子图-三角块的划分, 在该划分基础上对每个三角块对图G的顶点、边和面的贡献计数。结合平面图的结构特性并通过双向计数和归纳技巧得到如下结果: 设G是禁用$\{C_5,C_6\}$的连通n阶平面图, 如果$n \geq 14$, 则$e(G)\leq\frac{30n-84}{13}$。在此基础上, 构造了无穷多个达到该界值的极图。
自填充函数算法被提出以来, 参数被视为制约算法效率的主要因素, 因此构造无参数的填充函数显得极为重要。为了提高算法效率, 本文构造了一类新的无参数的填充打洞函数, 分析并讨论了该函数的性质。基于新的填充打洞函数, 提出了一个新的全局优化算法, 并对算法进行了数值实验, 数值实验结果表明该算法可行且有效。
本文研究广义弱混合向量拟平衡问题的逼近定理和通有收敛性。首先利用Fan-Knaster-Kuratowski-Mazurkiewicz (Fan-KKM) 引理给出了广义弱混合向量拟平衡问题解的存在性定理。然后基于Simon的有限理性理论, 在较弱的条件下给出了广义弱混合向量拟平衡问题的一个逼近定理。最后运用Fort定理, 证明了在Baire分类意义下广义弱混合向量拟平衡问题的解具有通有收敛的结果。
设A和B是两个集合, A和B的对称差是由$A\cup B$中所有不属于$A\cap B$的元素组成的一个集合, 记为$A\Delta B$。若一个超图不含有三条互不相同的边A, B, C使得$A\Delta B\subset C$, 则称该超图是一个可消去超图。一个3-一致可消去超图同时不含$F_4=\{abc, abd, bcd\}$和$F_5=\{abc, abd, cde\}$作为子超图。Bollobás (1974) 给出了3-一致可消去超图的最大边数, 并得出平衡的完全3-部3-一致超图是唯一达到最大边数的3-一致可消去超图。Keevash和Mubayi (2004) 进一步确定了平衡的完全3-部3-一致超图是唯一不含$F_5$作为子超图且边数达到最大的3-一致超图。设$\mathcal{H}$是一个超图, W是顶点集$V(\mathcal{H})$的一个非空子集。如果超图$\mathcal{H}$中的任意一条边只包含W中的一个顶点, 则称W是超图$\mathcal{H}$的一个独立横贯。在本文中, 我们得到了具有独立横贯的3-一致可消去超图p-谱半径的最大值。进一步, 我们证明了当p>2时, 平衡的完全3-部3-一致超图是唯一具有独立横贯且p-谱半径达到最大的3-一致可消去超图。
本文研究了单机上两代理串行分批排序问题, 分批时的每批加工时间有容量限制, 并且每批有一个分批费用, 该费用为常数, 且工件加工不可中断。对两个问题进行了考虑: 一个问题是在其中一个代理的最大完工时间与分批费用之和不超过某一阈值的前提下, 最小化另一个代理的总完工时间与分批费用之和; 另一个问题是在其中一个代理的总完工时间与分批费用之和不超过某一阈值的条件下, 最小化另一个代理的总完工时间与分批费用之和。这两个问题都是NP困难的, 对第一个问题给出了(2, 3/2)-近似算法。对第二个问题, 设计了渐近近似比为(2, 2)的近似算法。
标量化方法是多目标优化问题研究的基本内容之一。本文首先对广义Tchebycheff范数的性质进行研究, 获得了其在非负象限上的严格单调性等结果。进一步, 利用广义Tchebycheff范数的这些性质研究了多目标优化问题弱有效解、有效解、严有效解和真有效解的两类标量化结果。同时也指出, 在目标函数的凸性假设下, 本文研究的标量化与加权标量化等价。
稀疏正则化模型在信号和图像处理等反问题中有很广泛的应用。本文主要研究线性最小二乘$\ell_0$极小化问题的快速求解方法。外推向前向后分裂算法是最流行的求解方法之一。根据$\ell_0$正则化问题和该算法的特点, 我们将快速收敛的拟牛顿方法合理地应用于外推步中, 进而提出了一种分块变尺度外推算法, 并证明了其收敛性行为。我们在理论上证明了其快速性: 该方法具有线性收敛率, 甚至超线性收敛率。最后, 我们也通过数值实验展示了本文算法的有效性和快速性。
填充函数法是一种用于寻找无约束优化问题全局最优解的确定性方法, 这种方法的核心技术是构造填充函数, 使得迭代过程不断跳出当前的局部极小点。目前见到的填充函数一般都含有参数, 而参数的选取对算法的计算效果影响较大。本文利用填充函数的定义, 具体构造出一个新的无参数填充函数, 由此提出了新的全局优化无参数填充函数方法, 数值实验表明, 该方法是可行的和有效的, 具有更好的全局寻优能力。
超图平衡二划分是超大规模集成电路物理设计的重要一环。Kernighan-Lin算法和Fiduccia-Mattheyses算法等迭代优化算法是求解该NP-困难问题的常用方法。然而, 这些算法具有以下缺点: 一是对于较差的初始解, 算法容易陷入局部最优。二是由于平衡条件的约束, 顶点的移动受到诸多限制。针对上述问题, 本文将超图平衡二划分问题转化为0-1规划问题, 并设计了求解该问题的离散迭代算法, 在一定程度上克服了传统的迭代算法受平衡条件与初始解约束的缺点。在ISPD98电路划分测试样例上, 本文的算法取得了比Fiduccia-Mattheyses算法质量更高的解。在20次随机实验中, 本文的平均割边数比Fiduccia-Mattheyses算法少13.2%。将本文的结果作为Fiduccia-Mattheyses算法的初始解作进一步优化, 所产生的平均割边数比Fiduccia-Mattheyses算法少30.1%。不仅如此, 本文的算法还可以嵌入到多级划分算法框架中, 取得的平均割边数比multilevel partitioning (MLPart) 少3.6%。
本文以制造系统为背景, 提出一个在服务启动$N$-策略控制下具有检修策略和不同到达率的M/G/1排队模型。首先运用更新过程理论、全概率分解技术和拉普拉斯变换, 研究系统在任意时刻$t$队长的瞬态性质, 得到了瞬态队长分布关于时间$t$的拉普拉斯变换表达式。然后在瞬态分析的基础上, 使用洛必达法则得到队长稳态分布的递推表达式。最后, 在建立费用模型下, 应用更新报酬定理, 得到系统在长期运行下单位时间内的期望费用表达式, 并通过数值实例讨论了系统启动服务的最优控制策略和最优检修策略。
对图G的支撑树T, 其形心是指这样的顶点v, 使得$T-v$的最大分枝具有尽可能少的顶点, 这个分枝的顶点数称为T的形心分枝度量。最小分枝支撑树问题是寻求G的支撑树T, 使得T的形心分枝度量为最小, 这个最小值称为图G的分枝指数。在通信网络设计中, 其实际意义是使从交换中心(形心)引出的所有分枝的负荷尽可能均衡。我们在2022年提出这种新型的选址问题, 并给出基本的理论结果。本文将加深对理论与算法的研究。首先证明此问题的加权形式即使对平面图也是NP-困难的。然后对一些重要的特殊图类, 如多面体图、超立方体、乘积图$K_m\times K_n$和二部图的补图等, 分别给出这些图类分枝指数的精确值, 并得到一个启发式算法。
图G的一个正常k-染色是G的一个k色点染色, 使得任两个相邻的顶点都异色。平图G的一个多色k-染色是G的一个k色点染色, 使得每个面出现k种不同的颜色。面f的度数是f上顶点的个数, 用$g(f)$来表示, 令$g(G)=\min\left\{g(f)|f\in F(G)\right\}$, 其中$F(G)$是平图G所有面的集合。显然, 若平图G存在多色k-染色, 则$k\leq g(G)$。Horev等人(2012)证明了3-正则二部简单平图是正常多色4-可染的。在本文中, 我们推广了上述结果, 证明了对于最大度是3的连通二部简单平图G, 若$g(G)\geq 5$, 则G是正常多色4-可染的。条件$g(G)\geq 5$是紧的, 因为存在$g(G)=4$最大度是3的连通二部简单平图G不能正常多色4-染色。
本文考虑一类完全非凸的复合优化问题, 其目标函数由如下两部分组成: 关于全局变量不可分的连续可微非凸函数, 与两个关于独立变量的正常下半连续非凸函数。本文提出一种求解该问题的新型黄金比率邻近交替线性化极小化算法。在Kurdyka-Lojasiewicz (简记KL)性质假设下, 证明了由算法产生的迭代序列收敛到问题的稳定点。最后将新算法应用于求解稀疏信号恢复问题, 数值实验验证了新算法的有效性与优越性。
研究带有碳排放成本和计件维护情形的单机调度问题。每完成若干个工件需进行一次维护活动, 机器在加工工件和维护活动时会产生相应的碳排放量。分别针对极小化最大完工时间和总完工时间两个目标函数, 建立了极小化加工成本和碳排放成本之和的调度模型。证明了该问题可转化为指派问题并给出了时间复杂度为$O(n^4)$的多项式时间算法。
本文创新性地将设施选址博弈与装箱问题相结合, 定义了一类新的设施选址装箱博弈问题。与经典模型不同, 我们首次分析了物品在访问设施后仍需进一步接受服务的情形, 并将优化目标设定为最小化所有物品的访问距离与所需装箱总数之和。在此模型中, 物品是博弈参与者, 各自拥有位置信息和尺寸信息。首先, 我们研究了物品尺寸为私有信息的情形, 物品的费用由装箱成本分摊。针对此情形下的纯装箱博弈和选址装箱博弈, 我们分别设计了具有策略证明性(防策略) 的机制, 其近似比分别介于[1.691, 2]和[5/3, 7/4] 之间。其次, 针对物品尺寸信息与位置信息均为私有信息且相互关联的更复杂情形, 我们考虑物品费用即为访问设施的实际距离。在此设定下, 我们设计了三个策略证明机制, 并分别严格证明了它们的近似比上下界：第一个机制为[47/35, 11/8], 第二个为[45/34, 1.7], 第三个为[11/9, 10/9]。本研究拓展了设施选址博弈的理论框架, 提出的机制设计方法能够有效处理物品访问设施距离优化与其后续装箱服务资源优化协同的问题, 并在参与者拥有私有信息且可能策略行事的复杂环境下, 保证方案的防策略性和近似效率。
广义混合拟变分不等式(GMQVI) 是变分不等式的推广。变分不等式及其推广模型被广泛地应用在经济学、交通、最优控制等领域。基于广义投影算子的相关性质和GMQVI解的特征, 在一定的单调性和紧性假设下, 本文在自反Banach空间中给出了问题(GMQVI) 的正则化间隙函数, 并由此构造了D-间隙函数。同时利用这些间隙函数, 得到了基于正则化间隙函数的局部误差界, 和利用D-间隙函数及正则项刻画的全局误差界。
由于信息稀缺性、服务系统的不确定性以及顾客认知能力的有限性, 顾客很难准确估计接受服务后的预期效用, 进而做出理性决策。本文利用Logit选择模型描述有限理性顾客的策略行为, 基于排队博弈理论, 在几乎不可见和完全不可见两种信息水平下分析多重休假M/M/1排队系统中的顾客决策、机构利润与社会福利, 并通过数值算例对比不同信息水平下顾客有限理性水平对机构最优利润和社会福利的影响。结果表明, 在两种信息水平下, 有限理性顾客的均衡策略存在且唯一; 存在唯一最优价格, 使得机构利润最大化; 存在唯一最优价格, 使得社会福利最大化; 随着平均休假时间缩短, 顾客更愿意加入系统, 机构可以获得更多利润, 社会福利也会提高。此外, 在完全不可见情况下, 社会福利关于顾客有限理性水平的变化规律依赖服务价格, 是顾客有限理性水平的单峰函数; 存在一个特定有限理性水平, 使得机构利润和社会福利同时最大化。
如何促进人类社会中的合作和良性竞争, 一直是经济学和管理学中的核心问题。传统研究大多基于经典博弈论方法, 通过纳什均衡分析设计管理机制, 但是现实中人们的行为往往会背离均衡。近年来, 从实验和实证数据出发, 综合博弈论和行为经济学方法研究合作和竞争行为已经成为经济和管理学主流方向之一。本文将首先简要介绍数据驱动的人类行为和机制设计主要研究方法, 包括博弈论、行为经济学、心理学和神经科学等。接下来从影响合作和竞争行为的内在因素、外在因素和制度因素三个维度, 总结数据驱动的人类合作和竞争问题的研究动态。最后, 本文列出了一些当前研究中存在的挑战性问题。
设$G$是具有$n$个顶点的简单连通图。Gallai于1966年提出关于图的路分解猜想: 每个$n$阶简单连通图$G$都可以被分解为至多$\left\lceil\frac{n}{2}\right\rceil$条路。在本文中, 我们利用算法证明了Gallai猜想对于完全二部图$K_{n_1, n_2}$成立, 这里1≤n2 < n1且n1是奇数。结合Constantinou和Ellinas (2018)的结果, 我们证明了对于任意的完全二部图, Gallai猜想成立。
1968年，Vizing提出猜想:如果图$G$是$\Delta$-临界图, 则其独立数$\alpha (G)$满足$\alpha (G)\leqslant\dfrac{n}{2}$。这一猜想至今仍未解决。本文对于不含$度点的最大度较小的临界图, 证明当最大度$\Delta\in\{3, 4, 5, 6\}$时, 独立数$\alpha (G)\leqslant\dfrac{7\Delta-6}{12\Delta-6}|V|$;当$\Delta\in\{7, 8, 9\}$时, 独立数$\alpha (G)\leqslant\dfrac{4\Delta-3}{7\Delta-3}|V|$。
令图G是一个连通图。当$ 2\leqslant k\leqslant n-1$时, 图G的Steiner k-hyper Wiener指标定义为$ {\rm SWW}_{k}(G)=\frac{1}{2}\sum_{S\subseteq V (G), |S|=k}d_{G}(S)+\frac{1}{2}\sum_{S\subseteq V (G), |S|=k}d_{G}(S)^{2}$, 其中$ d_{G}(S)$表示图G中S的Steiner距离, 即连通图G中包含点集S的最小连通子图的边数。本文中我们确定了连图和字典积图的Steiner k-hyper Wiener指标的表达式, 给出了笛卡尔积图, 聚类图和冠状图的Steiner k-hyper Wiener指标的下限。
为了预测分子的物理、化学性质和生物活性, 科学家们提出了许多拓扑指数。调和指数是著名的Randić指数的一种变形形式, 研究表明该指数能有效地预测化合物的物理化学性质。对具有固定控制数的树的调和指数进行了研究, 通过分析具有固定控制数的树的结构, 利用数学归纳法, 给出了具有固定控制数的树的调和指数的最大值和最小值, 并刻画了达到最值的树。
设$S\subseteq V$是一个初始着色顶点子集, 它的所有顶点都着黑色, $S$中的每个顶点称为$S$-着色, $G$中所有其他未着色的顶点称为$S$-未着色。若一个着黑色的顶点$v$恰好只有一个未着色的邻点$u$, 则$v$强迫顶点$u$着黑色, 这样的过程称为强迫过程。如果从一个初始顶点集$S$出发, 逐步运用强迫过程直到$G$中所有的顶点都变成黑色, 则称这个初始集$S$为$G$的零强迫集(强迫集)。$G$的零强迫集的最小基数用$F (G)$表示, 称为$G$的零强迫数。如果$S$在$G$中的导出子图$G[S]$不包含孤立顶点, 则强迫集$S$称为$G$的全强迫集, 全强迫集的最小基数用$F_t (G)$表示, 称为$G$的全强迫数。注意到零强迫数和全强迫数有如下关系, $F (G)\leq F_t (G)\leq 2F (G)$。刻画满足$F (G)＝F_t (G)$或者$2F (G)＝F_t (G)$的图$G$是有意义的。基于此, 本文在单圈图上刻画了满足$F (G)＝F_t (G)$的所有图$G$。此外, 本文研究了给定匹配数为$k$的单圈图$G$的零强迫数的上界, 即$F (G)\leq n-k$, 等号成立当且仅当$G\cong C_4, A_0$。此外, 当$G\not\cong C_4, A_0$时, 本文刻画了使得$F (G)=n-k-1$的所有图$G$。
对于一个$k$一致超图$H=(V, E)$, 设$B (H)$是它的关联矩阵且$\mathcal{Q}(H)=B (H) B (H)^{\top}$是它的无符号拉普拉斯矩阵。$H$的无符号拉普拉斯谱半径是$\mathcal{Q}(H)$的所有特征值的模的最大值。设$\mathcal{H}^n_{k, r}$是具有$n$个点和$r$个悬挂点的连通$k$一致超图的图类。在$\mathcal{H}^n_{k, r}$中, 对于$n-r\geq k$和某些$n-r\in[k-1]$的情形, 本文刻画了具有最大无符号拉普拉斯谱半径的极值超图。
交替方向法作为求解矩阵补全问题的经典方法之一, 具有能够将一个极小化问题分解成多个规模更小、更容易求解的子问题的优势, 近年来在图像处理和数据分析等领域备受青睐。本文采用交替方向法的框架, 结合惯性策略, 提出了一种求解矩阵补全问题的惯性加速交替方向法。新算法在每步迭代中, 对于其中一部分变量利用交替方向法的前两次迭代点外推得到新一步的迭代点, 从而提高计算效率。本文在合理的假设条件下, 证明了新算法的收敛性。最后, 通过随机矩阵补全的数值实验及图像修复的实例验证了新算法的有效性和可行性。
本文对两类顾客且有灾难到达的全故障流体模型进行经济学分析, 灾难到达会清空系统迫使顾客离开。假设到达的顾客根据“收益-成本”效用函数决定是否进入。构建线性微分方程组, 在完全可见和几乎可见两种信息水平下利用矩阵分析法得出个体止步阈值和单位时间内的社会收益函数, 最后通过数值算例讨论参数对于社会收益的影响。
本文研究了一类带多次机器维护的单机随机排序问题, 其中所有工件有相同的加工时间和工期, 且工期为一个随机变量, 问题目标是确定工作间的数目及每个工作间中加工的工件数, 在此基础上使得总误工数期望最小。针对工期服从指数分布, 维护时间函数为凹函数的情况, 基于函数性质和指数分布的特点讨论了最优排序需要满足的一些性质, 给出该问题的最优排序; 针对工期服从均匀分布, 维护时间函数为线性函数的情况, 给出了一个最优算法。
本文在目标收益计划(TBPs)下考虑了具有违约风险和模型不确定性的最优投资和收益支付问题。养老金可以投资到无风险资产, 价格服从Heston模型的股票和违约债券。特别地, TBPs成员的工资是随机的。利用随机最优控制方法, 分别推导出了违约后和违约前的鲁棒最优策略和相应的值函数。此外, 还考虑了模糊中性情况下的最优策略。最后给出数值分析来说明参数对最优策略的影响, 从而为养老金管理者提供了有效的决策依据。
本文以追逃博弈问题的经典模型之一——“homicidal chauffeur”博弈为基础, 考察汽车转弯时受滑动摩擦力影响的博弈问题的捕获区域。经典“homicidal chauffeur”博弈是基于足够粗糙的地面这一理想假设对汽车转弯时的速度进行处理的。然而在现实运动中, 地面粗糙程度不同会对转弯时汽车的速度造成不同的影响。本文建立模型对追逃过程中汽车速度给出全新的刻画, 求解最优策略, 分析与经典“homicidal chauffeur”博弈相比捕获区域的变化并阐述原因, 主要结论可用于陆地追逃、空战格斗等现实场景。
