求解非减上模集函数最小值问题的近似算法及其性能保证

上模集函数的优化问题在组合优化问题中有广泛应用,许多组合优化问题,如设备选址问题、p-中心问题等都可化为上模集函数的优化问题.本文给出了求解非减上模集函数最小值问题的一种近似算法,并讨论了所给算法的性能保证.     

求解多维约束下下模函数最大值的改进贪婪算法

提出了多维约束下下模函数最大值问题,分析其在组合优化中的重要应用.此问题是NP-难的,故给出了求解该问题的改进贪婪算法.最后,从理论上证明了这一算法的时间复杂性和性能保证.说明该算法是多项式时间近似算法,同时也具有较好的性能保证.     

一道函数最值问题的典型错误

例 设a,b∈R且满足a2+ab+b2=1,求函数t=ab-a2-b2的最大值.……     

一道最值问题的两种求解策略

题目 如图1,已知｜OA^→｜=1,｜OB^→｜=√3,OA^→与OB^→的夹角为150°,点C是△AOB的外接圆上优弧AB上的一个动点,求OA^→·OC^→的最大值．     

带次模惩罚的优先设施选址问题的近似算法

研究带次模惩罚的优先设施选址问题, 每个顾客都有一定的服务水平要求, 开设的设施只有满足了顾客的服务水平要求, 才能为顾客提供服务, 没被服务的顾客对应一定的次模惩罚费用. 目标是使得开设费用、连接费用与次模惩罚费用之和最小. 给出该问题的整数规划、 线性规划松弛及其对偶规划. 基于原始对偶和贪婪增广技巧, 给出该问题的两个近似算法, 得到的近似比分别为3和2.375.     

求解函数最值问题的一种新思路

函数的最值问题是函数的核心知识,同时也是中学数学教学与研究的重点内容．本文介绍求解函数最值的一种新思路,其理论来源于最基础的数学知识——函数最值的定义,在解题方法上给我们提供了较新颖的思路,在解决某些函数最值问题上显得更简洁．     

多元函数最值的求解策略

在近几年的高考及各种测试试题中,多元函数的最值及其衍生问题频频出现,因为变量多、解析式复杂、方法技巧性强、题目灵活多变而具有较强的挑战性,成为最值问题中的一个难点,也是考查学生的数学素养和能力的一个热点.根据课程标准的要求,求多元函数的最值,总的策略是转化为一元函数或二元函数最值问题,转化的具体策略多种多样,本文对此进行了归纳和梳理.     

集值映射的Epi-导数及其应用

在本文里，集值映射的Epi-导数被引入，它可以认作是实值Lipschitz函数的Clarke-广义方向导数的推广，同时它的一些性质也被研究．进一步地，利用这个Epi-导数集值映射的次微分被定义并研究它的性质．作为其应用，我们给出了集值优化问题的一些(必要或充分)最优性条件．     

数形联袂求解函数问题

<正>华罗庚先生曾说过:"数与形本是相倚依,怎能分作两边飞,数缺形时少直觉,形少数时难入微,数形结合百般好,隔离分家万事休.切莫忘,几何代数统一体,永远联系,切莫分离!"在多年来的高考题中,数形结合应用广泛,在解方程和不等式、求函数的最值问题中,常有涉及.但由于数的逻辑性太强,在一些综合性较强的题目中,学生理解起来生涩难懂,望而却步,失分严重.本文中,笔者从以"形"助     

把握知识关联 问题求解自然——函数视角下数列问题的合理解答

函数思想是高中数学中几大重要数学思想之一,其贯穿于整个高中数学始终,数列问题也不例外,数列是定义在正整数集或其有限子集{1,2,3,…,n}上的函数,当自变量从小到大依次取值时,所得的函数值就构成一个数列.函数所具有的性质,如单调性、周期性、对称性等在某些数列中同样具有,如数列的通项公式an=f(n)(n∈N*),实质上就是函数的解析表达式,等差数列是定义在正整数集上的一次函数或常数函数;非常数等差     

一种非增值型凸二次双层规划的有效算法

主要研究了非增值型凸二次双层规划的一种有效求解算法。首先利用数学规划的对偶理论,将所求双层规划转化为一个下层只有一个无约束凸二次子规划的双层规划问题.然后根据两个双层规划的最优解和最优目标值之间的关系,提出一种简单有效的算法来解决非增值型凸二次双层规划问题.并通过数值算例的计算结果说明了该算法的可行性和有效性。     

威布尔更新函数的一个精确近似式

威布尔分布的更新函数有许多应用,如产品质保政策分析、维修决策优化和备件需求预测。威布尔更新函数没有解析表达式,这给求解各种涉及更新函数的优化问题带来不便。已有的威布尔更新函数近似式有一个共同的问题:其精度随威布尔形状参数的增大而减小。为克服这个问题,本文提出一个新的近似式,对于大的威布尔形状参数(>3.65),其相对误差比已有近似式的相对误差小得多。一个维修政策优化的数例例证其精确性和有用性。     

最小权点覆盖问题的一个近似算法

在点、边赋权的简单图中,关于最小权点覆盖问题,以经典的最短路算法-Dijkstra算法为基础,提出了一个求解该问题的近似算法.首先,在给定的赋权图中任选一点作为初始点,并给出允许集及相关定义.然后,利用经典的最短路算法-Dijkstra算法,求出初始点到允许集中各顶点的最短路径,并按照一定的原则选择近似最小权点覆盖集.最后,通过算例阐释了算法的实现过程的合理性及有效性.     

最小最大树划分的近似算法与最小和树划分的精确算法

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划分问题)．文中给出了最小最大树划分问题的强NP困难性证明,并给出了一个多项式时间算法,该算法是最小最大树划分问题的竞争比为p的近似算法,同时是最小和树划分问题的精确算法．     

NURBS曲线曲面拟合数据点的迭代算法

本文推广了文献[1]的结果,将文献[1]中关于B样条曲线曲面拟合数据点的迭代算法推广至有理形式,给出了无需求解方程组反求控制点及权因子即可得到拟合NURBS曲线曲面的迭代方法．该算法和文献[1]的算法本质上是统一的,而后者恰是前者的一种退化形式．文章还给出了收敛性证明以及一些定性分析．文末的数值实例说明该算法简单实用．     

凸多乘积问题的完全多项式时间近似算法

针对凸多乘积问题,提出一种求其全局最优解的近似算法.首先,通过引入参量获得一个等价问题,然后估计问题中每一乘积项的上下界,进而借助网格结点,获得一些凸规划问题,通过求解这些凸规划问题获得原问题的近似最优解.最后,给出了该算法的收敛性证明和计算复杂性分析.     

An Algorithm for Linear L1 Approximation of Continuous Functions

The problem of solving linear continuous L₁ approximation problemsis considered. An algorithm is given for approximation on aninterval of the real line, which is globally convergent, usuallyat a second-order rate. The method is illustrated by numericalexamples.     

随机容错设施布局问题的近似算法

在确定性的容错设施布局问题中, 给定顾客的集合和地址的集合. 在每个地址上可以开设任意数目的不同设施. 每个顾客j有连接需求r_j. 允许将顾客j连到同一地址的不同设施上. 目标是开设一些设施并将每个顾客j连到r_j个不同的设施上, 使得总开设费用和连接费用最小. 研究两阶段随机容错设施布局问题(SFTFP), 顾客的集合事先不知道, 但是具有有限多个场景并知道其概率分布. 每个场景指定需要服务的顾客的子集. 并且每个设施有两种类型的开设费用. 在第一阶段根据顾客的随机信息确定性地开设一些设施, 在第二阶段根据顾客的真实信息再增加开设一些设施．给出随机容错布局问题的线性整数规划和基于线性规划舍入的5-近似算法.