贪婪策略在占线订单加工问题中的竞争分析

根据实际生产中订单收益随加工长度变化的一般规律,建立了占线订单加工模型,构建一种贪婪策略并分析它在本模型中的竞争性能。具体证明它在中断订单有、无惩罚两种情形下的竞争比,并讨论了模型中收益函数的参数对竞争比结果的影响。

占线试销产品的配送问题与竞争策略

本文提出和研究了占线试销产品的配送问题P。设计了两种竞争策略,证明采用贪婪策略,竞争比为2+2λ.n-kk;采用公平策略,竞争比为(1+λ)(1+「log(nk)﹁),其中n为初始时货物的数量,k为提出供货需求的经销商数,λ为离厂家最远和最近的经销商的距离比。随后又分析并得出该问题的退化型—问题P1的结果。最后,对这两种竞争策略的优劣进行了比较。

成对需求占线服务器问题及公平原则策略

针对在对称度量空间上多服务需求的k—服务器占线问题,研究问题空间为k+2(度量空间上有k+2个顶点,但只有k个服务器)时的一个特例:即在任意时刻都同时有两个服务需求提出。建立了该问题的数学模型,给出了公平原则策略,该策略能使得任意两个服务器完成服务后花费费用之差不大于某个固定常数;进行了相应的策略分析和竞争比的证明,并同工作函数策略进行了比较。

基于价格可变的占线优惠卡问题及其竞争分析

优惠卡问题是租赁问题的一个推广,已往的研究都是考虑只存在一种优惠活动的情况,并给出最优的单阀值购买策略。在本文中,则考虑更接近实际的情况,即存在多种优惠活动的问题,给出了当所有优惠卡价格在有界范围内的双阀值购买策略,分别给出了其竞争比上下界。最后,通过数值分析说明优惠卡价格和折扣率对消费者购买策略和竞争比的影响。

有限预知信息的集装箱搬卸占线问题

提出了有限预知信息的集装箱搬卸占线问题,即每一个服务请求到达时预先知道后续一部分请求信息的占线问题。建立并分析相应的数学模型,针对模型中预知信息的特征提出了贪婪移位策略。运用最坏情形分析方法研究了贪婪移位策略的竞争性能,证明其具有竞争比:(b+w-2)/w。

占线决策问题及竞争分析方法

基于近年来理论计算机科学领域的热点研究方向——占线算法与竞争分析理论,将相关概念引入经济管理决策问题当中,比较分析处理占线经济管理决策问题的竞争分析方法与传统Bayesian优化方法的区别以及后者的缺陷,构建利用占线算法及其竞争分析方法研究占线经济管理决策问题的理论框架,指出在进行占线分析时应注意的要点及分析方法,最后以两个实例加以说明。

一类占线融资租赁问题的最优竞争策略与风险补偿模型

运用占线算法与竞争分析方法,研究了资产所有权在一定的租赁时间后转移给承租人的融资租赁问题的最优竞争策略与风险补偿模型。首先给出了该问题的最优离线解;然后,根据约定的租赁时限与购买价格及租赁费用的大小关系,分别给出了3种情形的占线策略及相应的竞争比分析;最后,在AL-BINALI提出的占线风险补偿分析框架下,给出了2种预期形式及相应最优占线收益策略。

基于有限信息的占线设备更新问题及其竞争策略

传统的占线优化理论分析假设对未来信息一无所知,根据过去和现在的信息进行决策。然而,在现实中有些信息是可以通过统计数据来估计得出或者通过实验方式获得,因此在本文中放松该假设,知道未来的部分信息。比如在汽车更新决策中,未来可能投入市场的汽车更新的某些重要参数(如购买成本和行驶成本)可以通过上述方法获得,决策者该如何决策何时更新汽车?优化目标是使竞争比最小,即汽车更新的占线成本和离线成本的比值最小。另外,汽车类大宗设备退出市场时还具有一定的残值,可以通过二手车市场交易来回收部分成本,因此本文将折旧因子引入了模型,给出了一个占线参数策略,得出了相应的竞争比,证明了折旧因子的引入改善了竞争比。

占线顶点覆盖问题的结构性下界

在实际顶点覆盖选址过程中,经常会遇到如下的情形:在需要服务的边的个数未知的前提下,决策者需要决定在哪里建立初始的设施(或设施集),同时还要求,当新的设施建立后,前面已经建立的设施不能被删除.以往一般建立的模型和算法都是针对静态选址而言的,这里需要的是满足上述约束的动态选址模型.考虑了占线顶点覆盖问题,给出了一个不需要任何复杂性假设条件下的结构性的下界结果,并通过对一个限制性条件下的占线顶点覆盖问题给出算法并证明竞争性能比结果说明了所作的下界分析是紧的,同时证明了所给出的算法在非多项式时间内是最优的.

非线性指数回购合同约束的占线租赁问题

考虑到设备的使用寿命通常呈现出更一般的非线性衰减,本文以非线性指数价格函数为回购合同约束建立了占线租赁决策模型,并得到了模型的最优竞争策略。首先分别对指数非线性回购合同进行数学刻画并讨论了其相关的一些性质。其次对存在旧货市场的离线租赁问题进行最优分析,进而提出该问题的占线租赁策略,并运用竞争分析方法从理论上完美证明了该策略的最优性。与经典的占线租赁模型比较发现,其竞争比小于Karp"雪橇租赁"模型中最优策略的竞争比。另外,本文提出的具有回购合同约束的占线租赁模型是对已有研究仅考虑新货市场进行扩展突破,即考虑了允许旧货市场的存在,是对现有占线租赁模型库的一个有益补充。

一条路上的占线可恢复加拿大旅行者问题混合策略

针对旅行者在行走过程中遇到某一或一系列无法预知的堵塞事件的可恢复加拿大旅行者问题,考虑堵塞只发生在一条特殊路径上且堵塞可恢复的情形,提出了以一定概率分布对等待与迂回策略进行选择的混合策略,并讨论了无偏好和有偏好混合策略以及相应策略下的竞争性能比。

基于系统最优策略的占线交通流量分配

针对n次连续的交通需求依次到达出发点选择路径到目的地去的问题,本文从占线与竞争策略的角度出发,研究流量是任意可分的情形下交通流量分配,采用系统最优策略分配交通需求,即每次分配流量后都能使得当前网络上所有用户花费费用总和最小。借助于变分不等式对系统最优策略进行了竞争分析,特别地,当路阻函数是系数非负的线性函数时,证明该策略是4-竞争的;当路阻函数是系数非负、度数至多是d的多项式函数时,该策略是(d+)d+1-竞争的,同时给出系统最优策略竞争比的下界是5/3。

路段权重不确定时占线选择路径

用户打算从出发地s去目的地d,针对路段上的权重无法准确预知就必须做出决策,选择出行路径去目的地的问题。从占线与竞争策略的角度出发进行考虑,设计了最大权最小策略及贪婪策略选择路径,假设路段上的实际权重ωe和最大权重Te满足关系式ωe≥αTe的情形下,证明了这两个策略的竞争比都是1/α,并证明了这两个策略都是最优策略,其中α∈[0,1]。