首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 62 毫秒
1.
对一般网络上的占线中心选址问题及其竞争算法进行了研究.文献[6]证明了该问题的竞争比下界是(n-2△e+√(n-22△e2+4(n-1)/2(n-1)) ,其中△e是所给空间最大的相对距离,并证明了该问题不存在常数竞争比的竞争算法.本文给出了一个多项式时间的竞争算法,并证明该算法的竞争比为△e△w,其中△w是所给空间点间的最大相对权重.所得结论不仅对于理论上占线中心选址问题的竞争算法的设计与分析,还是对于实际中的选址决策,都具有一定的指导意义.  相似文献   

2.
基于在建立的设施的个数未知的前提下需要决定如何建立初始设施集,同时要求,当新的设施集建立后,前面已经建立的设施不能被删除的实际选址约束条件下,从占线理论出发考虑了待选址个数不确定的动态选址问题.设计了一个多项式时间的竞争算法,证明了该算法具有的竞争比,该竞争比结果优于已有的结果.  相似文献   

3.
具有建设成本的占线中心选址问题及其竞争算法设计   总被引:1,自引:1,他引:0  
研究待选址个数不确定的动态选址问题. 在实际选址过程中,经常会在全部需要建立的设施个数未知的前提下,决定在哪里建立初始的设施(或设施集),同时要求,当增加建立设施时,已经建立的设施不能被删除.此外,基于实际,待建立的设施间的初始建设成本是不同的. 建立了满足上述约束的占线选址动态模型,并给出一个竞争算法,最后证明该算法具有常数的竞争比.  相似文献   

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

5.
研究的是订单需求信息不确定条件下的按订单生产(make-to-order,MTO)模式企业的生产决策问题.这类企业单批产品的固定启动生产成本较高,企业允许延期交货,但需要承受延期惩罚费用.因此本文研究在需求订单到达序列信息不确定的条件下,决策怎么安排生产使得总固定启动生产费用和延期费用最优的生产决策问题.考虑了占线生产模型,首先证明该问题的竞争比下界是3.随后受证明的启发,研究仅针对两类产品的问题,给出了一个新的占线生产策略并证明竞争比为3,因此说明所做的下界分析是紧的,同时证明了所给出针对两类产品的问题的占线策略是最优的.  相似文献   

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

7.
研究的是价格不确定条件下的原材料采购问题.在实际的原材料采购决策中,经常会遇到如下情形:特定时间内某原材料的价格随时间的变动具有不可预期性,同时该原材料具有固定的需求消耗.为了最小化采购费用,我们需要在满足需求的条件下确定在什么时间,以什么价格以及采购多少的决策问题.以往的研究一般都是假设采购价格是随机波动的,而实际情况中价格常常是不可随机观测的.本文从占线理论出发考虑了原材料占线采购问题,设计了一个竞争策略,证明了相应的竞争比,该竞争比结果优于已有结果.  相似文献   

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

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

10.
共享平台任务分配过程中,经常会遇到如下的情形:在用户未来需求任务序列(到达时刻、开始时刻和持续时间等)未知的条件下,决策者需要决定如何将当前需求合理分配给现有服务器使得平台收益最大.平台上服务器具有数量限制,同时要求用户需求一旦被分配就不可更改.以往研究建立的模型一般都是针对静态任务分配而言的,但实际需要的是满足上述约束的动态任务分配模型.以最大化共享平台收益为目标建立了占线共享平台任务分配模型,其中收益不仅包含了抽成比例,而且包含了固定收益.利用Yao原则给出了问题的竞争比的下界结果,该下界不需要任何复杂性假设条件,因此,是结构性下界.  相似文献   

11.
提出并研究限制信息条件下基于时间窗的占线装一卸货问题。客户在提出服务请求时只指定需要承运的货物的装载地,而没有提供目的地信息,服务车只有在到达装载地之后才知道目的地的具体位置,如现实中的出租车调度和电梯调度等问题。就两种度量空间对限制信息条件下带时间窗的占线装一卸货问题进行了分析,分别给出了两种竞争策略及其竞争比结果,并得到了针对该问题的任何确定型算法的竞争比下界。  相似文献   

12.
在线租赁问题的随机性竞争策略   总被引:1,自引:0,他引:1  
在线算法与竞争分析是研究信息不确定决策问题的一种新工具,应用该方法研究在线租赁问题是近年来国内外的一个研究热点.在前人研究基础上,采用博弈论中Nash均衡的混和策略思想并运用竞争分析理论中常用的敌手分析法,针对离线人具有遗忘性竞争对手的特点首先讨论了不存在市场利率情形下在线租赁决策的随机性竞争策略,指出在线人在有限维策略空间内(其维数为设备购买价格与设备租赁费用的比值)必定存在着最优的随机性Nash混和竞争策略,随后将该结果进一步扩展到了存在市场利率情形时的随机性Nash混和竞争策略.另外,通过数值对比分析,发现市场利率的引入使得策略的竞争性能得到显著改善,并且随着市场利率的增大其随机性Nash混和竞争策略的竞争比越小,即投资者若考虑到资金的收益及市场风险因素后将会采取更加谨慎稳健的投资策略.  相似文献   

13.
网络广告竞价中的在线拍卖及其竞争策略   总被引:5,自引:0,他引:5  
张娥  郑斐峰  汪应洛 《系统工程》2005,23(6):115-118
对网络广告位置拍卖的一种在线模型及其竞争策略进行了研究。建立了投标人数已知和未知的两种在线拍卖模型,并分别设计了竞争比为(2+1).(Φ+1-1)和2Φ-1的确定性在线策略,其中Φ为投标者对拍卖物品投标价上下界的比值。  相似文献   

14.
对于带时间窗的局内车辆调度问题,以往文献的研究都是关于k=1的单车调度,其开放式情形下最好的竞争比为4。针对该问题本文进行了开放式情形下多辆丰(k≥2)调度的研究分析,设计了解决试问题的竞争算法,并证明了其竞争比为3.5。同时本文分析了该问题的一种特殊情形——单车调度问题,可证明其竞争比为3.优于已有结果。  相似文献   

15.
连续网络上的占线可恢复加拿大旅行者问题   总被引:6,自引:0,他引:6  
苏兵  徐寅峰 《系统工程》2004,22(8):10-13
针对堵塞完全在无法预知的情况下一个个出现,且堵塞恢复时间信息可以获取的占线可恢复加拿大旅行者问题,给出连续网络上的等待策略和移动策略以及相应策略下的竞争比,并对两种策略的执行效果进行分析和比较。  相似文献   

16.
单向可替代报童问题的最优在线订货策略   总被引:1,自引:0,他引:1  
针对需求信息未知的情形,建立了单周期具有单向可替代性的两产品在线订货报童模型,设计了有效的在线订货策略并进行竞争分析,给出了该问题的最优竞争比以及对应的最优订货量。最后通过对相关算例的分析,表明本文所设计的在线策略具有合理性和有效性。  相似文献   

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

18.
有限预知信息的可恢复加拿大旅行者问题   总被引:2,自引:0,他引:2  
加拿大旅行者问题是指旅行者针对行走过程中遭遇的突发性道路堵塞,如何设计一个有效路径选择策略,使得旅行者从出发地抵达目的地的行走时间尽可能地少的问题。从占线问题与竞争策略的角度讨论有限预知信息情形下的可恢复加拿大旅行者问题,给出决策者在车辆到达一交叉口时可以获取后一交叉口的关联路段是否堵塞及堵塞恢复时间情形下的等待策略和贪婪策略,以及相应策略下的竞争比,并与不可预知信息情形下问题的策略进行了比较。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号