《研究方法论学习.pptx》由会员分享，可在线阅读，更多相关《研究方法论学习.pptx（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 占线问题和竞争策略n现代社会的特征：信息多变与不完全部分已知当前决策信息决策问题全部已知当前决策信息已知未来信息全部知或一无所知未来信息有限预第1页/共44页2 占线优化方法通常是在一定的已知（静态）条件下寻求最优方案或在一定的假设下寻求统计意义上的最优方案。决策者对未来因素的变化有限预知甚至一无所知情形下,该方法可以给出较好的方案,使之与最优方案的差异（比值）总在一定的比例之内。静态优化方法n两类问题：离线问题（offline）占线问题(online)n决策方法：占线问题和竞争策略第2页/共44页3 1966年，Graham第一次提出用竞争分析方法解决并行机器调度问题，提出一个简单的确定
2、性贪婪算法；1983年，R.Tarjan在 Data Structure and Network Algorithms 中所讨论的Amotized的方法，就是占线问题与竞争策略的萌芽；近年来，在计算机理论科学、管理科学等领域，占线问题与竞争策略的研究均取得了较好的理论和实践成果，如经典的k-服务器猜想，雪橇租赁问题，及目前研究热点物流与金融中的占线问题等。占线问题和竞争策略第3页/共44页4 考虑一个最小费用问题P，为P 的输入序列n 是对占线问题P 所设计应对策略A下对应于输入R的费用.策略A只能在获知第i时期的输入后给出第i时期的输出 n 为问题P所对应的离线问题在确定输入 R 下的最优解
3、 如果 成立n 称为策略A的竞争比(competitive ratio).为与输入序 列无关的常数。占线问题和竞争策略占线问题和竞争策略第4页/共44页5 1.A.Borodin and R.El-Yaniv,Online computation and competitive analysis M.Cambridge University Press,1998.2.A.Fiat and G.J.Woeginger,Online Algorithms:The State of the ArtM.Spring-Verlag,Berlin Heidelberg Germany,1998.3.D.D
4、.Sleator and R.E.Tarjan.Amortized efficiency of list update and paging rules.Comm.ACM,28(2):202-208,1985.4.4.堵丁柱堵丁柱,k,k车服务问题与竞争算法车服务问题与竞争算法,数学的实践与认识数学的实践与认识,.4:36-40,.4:36-40,1991.1991.5.R.M.Karp,On-line Algorithms Versus Off-line Algorithms:How Much is it Worth to Know the Future?,International Com
5、puter Science Institute Technical Report TR-92-044,Berkeley,CA,1992.6.P.Keskinocak,R.Ravi.,S.Tayur.Scheduling and Reliable Lead-Time Quotation for Orders with Availability Intervals and Lead-Time Sensitive Revenues.Management Science,47,2:264-279,2001参考书目和文章第5页/共44页6 经济管理中的占线问题经济管理中的占线问题 经经济济管管理理中中的
6、的占占线线问问题题 物流管理中的物流管理中的占线问题占线问题 金融管理中的金融管理中的占线问题占线问题 运运输输 选选址址 库库存存道路交通堵塞问题道路交通堵塞问题 车辆调度问题车辆调度问题物流中心选择问题物流中心选择问题 投投资资 理理财财 金融租赁问题金融租赁问题 证券投资问题证券投资问题 优惠卡购买问题优惠卡购买问题 库存管理问题库存管理问题 订单加工处理问题订单加工处理问题第6页/共44页7 网络网络GG中，其个顶点均为服务对象，随时可能提出服务要求，现有中，其个顶点均为服务对象，随时可能提出服务要求，现有个车辆个车辆(服务器服务器)按需求的先后顺序来往服务于个顶点之间。假定按需求的先
7、后顺序来往服务于个顶点之间。假定个车辆的初始位置已固定。个车辆的初始位置已固定。考虑如下两个问题：考虑如下两个问题：（1 1）事先给出一个要求服务的顶点序列，问如何调动车辆使得全）事先给出一个要求服务的顶点序列，问如何调动车辆使得全部车辆所走的总路程最小？部车辆所走的总路程最小？（2 2）如果要求是在服务过程中一个接一个收到的，这样每一时刻）如果要求是在服务过程中一个接一个收到的，这样每一时刻只能知道在这之前的要求和服务过程。问如何调动车辆使得总路程只能知道在这之前的要求和服务过程。问如何调动车辆使得总路程最小？最小？需求无法预知的车辆调度问题CBA12 S1 S2第7页/共44页8 假 定：
8、一个需求发生的顶点序列 策 略：就近策略、公平策略 就近策略：由距离服务需求最近的车辆提供服务 公平策略：让每辆车的行驶里程差不多 CBA12 S1 S2需求无法预知的车辆调度问题第8页/共44页9 n就近策略：一辆车会在A和B之间移动m-1次，当m比较大时，最优方案则是把B移至A，然后C点移至B;这样就近服务的运行里程与最优值的比值为 （m-1）/3,随着m 增大，比值增大，因此，就近策略不是竞争算法。需求无法预知的车辆调度问题第9页/共44页10 n公平策略（BAL）设n=k+1，对于每一个车辆 si以及该车辆运行的路程Di，服务需求r，移动 si 使得 最小。在服务需求为n=k+1的任意
9、度量空间内，BAL策略是k竞争的。但是，在nk+1的度量空间中，BAL是非竞争策略。需求无法预知的车辆调度问题第10页/共44页11 n例例，n=4，k2，初始位置c、d。服务需求 最优的策略为：先将c处的车辆调到b处，移动距离为M，然后两个车辆在每次响应服务需求时，都只需移动m。Mabcdm需求无法预知的车辆调度问题第11页/共44页12 n n出租车调度问题出租车调度问题 和和k-k-车辆（服务器）调度问题不同的是，此时的需求为车辆（服务器）调度问题不同的是，此时的需求为（a ai i,b bi i），），表示需要从表示需要从a ai i点搭出租车去点搭出租车去b bi i点。点。n n基
10、本假设：基本假设：i)i)图图GG是连通的是连通的;ii)ii)当新的服务要求出现时当新的服务要求出现时,k k辆出租车均处于闲置状态辆出租车均处于闲置状态;需求无法预知的车辆调度问题第12页/共44页13 n出租车调度问题n占线策略：复位策略n竞争比结果：如果对于k-车辆调度问题存在竞争比2k-1的占线策略，那么对于k-出租车调度问题的复位策略具有竞争比 2k+1。需求无法预知的车辆调度问题第13页/共44页14 n出租车调度与个体收益问题 在一个出租车市场上，由政府设定出租车的数量和收费标准，k辆出租车在一个有限交通网络上按照统一价格进行竞争性载客服务。网络上每一个乘客需求为 r(ai,b
11、i),即在ai有一顾客要求乘出租车到 bi,ai出现的时间、出现的位置和 r(ai,bi)的行驶距离不确定。需求无法预知的车辆调度问题第14页/共44页15 n出租车调度与个体收益问题n出租车完成r(ai,bi)后可按计价规则收费，在空载行驶和等待服务需求到来的时间段无收益，并需支付一定费用。n问题：假设不考虑每一辆出租车的固定费用，问题是如何度量出租车在时间段T上的收益，其个体运营方案对其收益将产生怎样的影响？需求无法预知的车辆调度问题第15页/共44页16 n n 出租车时间价格函数出租车时间价格函数 to,tw,tv分别表示载客、等待和空载时间 时间段T分割成许多小的时间区间 t,则出租
12、车在每一个 t内的时间价格是不一样的需求无法预知的车辆调度问题第16页/共44页17 n n 出租车时间价格曲线出租车时间价格曲线图图1 1 政府定价下的出租车时间价格曲线政府定价下的出租车时间价格曲线载客等待空载起步价正常运价阶段空驶补偿阶段需求无法预知的车辆调度问题第17页/共44页18 车辆在交通网络上由出发地欲抵达目的地。在出发前，决策者综合考虑交通网络中各个路段的状况，选择了一条有效的行驶路径。但是，在车辆沿着这条路径的行驶过程中，可能遇到一系列的道路堵塞。由于信息获取手段的有限，决策者不可预知或只能有限预知即将遇到堵塞的信息，那么，当决策者获知某个堵塞发生的相关信息时，决策者应当制
13、定怎样的行进策略？不同策略的执行效果如何？OD?道路突发性堵塞路径选择问题第18页/共44页19 模型构造：遭遇k个堵塞边时用策略A将货物从O点 运到D点的总费用 ：相应的离线最优费用基本假设：1）去掉堵塞边后图G仍是连通的；2）只有当运输车走到堵塞边的起点后，才能发现该边 发生堵塞而不能通过；3）堵塞边一旦产生，这个边将永远被堵塞。道路突发性堵塞路径选择问题第19页/共44页20 贪婪策略（A A）复位策略（B B）竞争比2 2k k1 1不能改进，是一般网络上的堵塞不可 恢复问题策略竞争比的下界。道路突发性堵塞路径选择问题一般网络上不可恢复问题的应对策略第20页/共44页21 一般网络上不
14、可恢复堵塞问题贪婪策略最坏情形道路突发性堵塞路径选择问题第21页/共44页22 问题1 1：为什么贪婪策略竞争比显著高于复位策略，然 而从日常经验来说，人们却往往采用贪婪策略?问题2 2：采用贪婪策略是否具有一定合理性呢？对一般网络上堵塞不可恢复问题贪婪策略的思考道路突发性堵塞路径选择问题第22页/共44页23 令r1,r2,.,rk表示 k 个堵塞边，其中 li表示从堵塞边ri的起点到终点D的距离(r1,.,ri-1已经堵塞)li表示从堵塞边ri的起点到终点D的可行距离则 且有对于贪婪策略对于贪婪策略A A A A，应有下面不等式成立：应有下面不等式成立：道路突发性堵塞路径选择问题对一般网络
15、上堵塞不可恢复问题贪婪策略的思考第23页/共44页24 日常生活中的贪婪策略道路突发性堵塞路径选择问题第24页/共44页25 城市交通网络结构 方格网络西安市新城区局部地图西安市新城区局部地图巴塞罗那城区局部地图巴塞罗那城区局部地图道路突发性堵塞路径选择问题第25页/共44页26 城市交通网络结构 环形放射式网络上海市区局部地图上海市区局部地图道路突发性堵塞路径选择问题第26页/共44页27 城市交通网络结构混合式网络（方格与环形混合）上海市区局部地图上海市区局部地图道路突发性堵塞路径选择问题第27页/共44页28 城市交通网络结构自由式（山区等没有一定的几何形状）重庆市区局部地图重庆市区局部
16、地图道路突发性堵塞路径选择问题第28页/共44页29 方格网式，环形放射式，自由式和混合式网络模型环形放射式环形放射式环形放射式环形放射式方格网式方格网式方格网式方格网式混合式混合式混合式混合式自由式自由式自由式自由式n交通网络的分类方式：道路突发性堵塞路径选择问题第29页/共44页30 道路突发性堵塞路径选择问题 目的地为 时方向贪婪策略路径示意图方向贪婪策略特殊网络上不可恢复堵塞问题贪婪策略最坏情形第30页/共44页31 道路突发性堵塞路径选择问题 目的地为 时多选择贪婪策略点 可达示意图多选择贪婪策略特殊网络上不可恢复堵塞问题贪婪策略最坏情形第31页/共44页32 n 物流配送网络由多个
17、配送中心组成，配送中心数量随着未来需求的变化而增加，因此网络建设需逐步分阶段完成。即在前阶段已建好的配送中心基础上，需要增加若干个配送中心，问题是在不同的建设阶段应如何对物流配送中心进行选址，使得在网络内对服务需求的运输费用尽可能地小。物流配送中心选址问题第32页/共44页33 物流配送中心选址问题nA,B,C,D的需求量为n任两点间的距离为 d(A,B)=d(A,C)=d(B,C)=30 d(D,A)=d(D,B)=d(D,C)=1n目标函数：min W（I）d ;I=A,B,C,D30ABC1113030D 假设某个城市的道路网络如下图所示，可供选择的物流配送中心地址为A,B,C,D第33
18、页/共44页34 方案一：1.第1个中心，建设在D点2.建设3个中心时，只能建设在 A，B，Dcost(D)=300=opt1cost(A,B,D)=100=100opt330ABC1113030D物流配送中心选址问题第34页/共44页35 ABCD130113030方案二：1.第1个中心，建设在A点2.建设3个中心时，建设在 A，B，Ccost(A)600120opt1 cost(A,B,C)=1=opt3从全局来看，方案二要优于方案一。物流配送中心选址问题第35页/共44页36 n n顾客数量不确定顾客数量不确定n n调和策略（调和策略（Harmonic StrategyHarmonic
19、Strategy）如果知道顾客数量的上限如果知道顾客数量的上限MM和下限和下限m,m,则可以则可以 给出一个调和策略给出一个调和策略HS,HS,即每天准备即每天准备 个顾客所需的即可个顾客所需的即可.n n可证明该策略的竞争比为可证明该策略的竞争比为n n调和平均数：调和平均数：库存管理问题第36页/共44页37 n n订单加工排序问题描述：订单加工排序问题描述：供货方对于不断到达的客户订单，根据其加工长供货方对于不断到达的客户订单，根据其加工长度、完工收益、交货日期等因素决策加工次序，使得度、完工收益、交货日期等因素决策加工次序，使得某种成本（总完工时间、延误订单总个数）尽可能地某种成本（总
20、完工时间、延误订单总个数）尽可能地小或者收益（完工订单个数、完工总收益）尽可能地小或者收益（完工订单个数、完工总收益）尽可能地大。大。n n常用的加工策略：常用的加工策略：FCFS FCFS（先到先服务）（先到先服务）EDF EDF（最早交货时间优先）（最早交货时间优先）SPT SPT（最短加工时间优先）（最短加工时间优先）WSPT WSPT（带权（带权SPTSPT：按：按wi/piwi/pi递减次序）递减次序）订单加工问题第37页/共44页38 n n雪橇租赁问题描述：雪橇租赁问题描述：滑雪爱好者去滑雪，他要么租用要么购买滑雪滑雪爱好者去滑雪，他要么租用要么购买滑雪工具。设工具。设t t为滑
21、雪者实际的租赁次数，每次租金为为滑雪者实际的租赁次数，每次租金为p p，如果购买，其价格为如果购买，其价格为c c。滑雪者在不清楚未来滑滑雪者在不清楚未来滑雪次数雪次数n n的情况下，如何决策以使所花费用尽可能地的情况下，如何决策以使所花费用尽可能地少？少？n nKarp Karp 提出最优的占线策略：提出最优的占线策略：租赁到租赁到k k1 1次次(k=c/pk=c/p)，然后购买。然后购买。其竞争比为其竞争比为2-1/2-1/k k.金融租赁问题第38页/共44页39 n n雪橇租赁策略设计雪橇租赁策略设计 OnlineOnline：前前k k1 1次一直租用，次一直租用，之后如果继续需要
22、则之后如果继续需要则立即购买立即购买(k=1,2,k=1,2,.).)。1 1）nnk k1 1时，时，online online 和和offlineoffline 产生同样的成本，只租不买。产生同样的成本，只租不买。2 2）n kn k1 1时，时，offlineoffline则立即购买该设备，而则立即购买该设备，而onlineonline等到等到k k1 1天才买。天才买。金融租赁问题第39页/共44页40 n n 外汇兑换交易描述外汇兑换交易描述 M M=汇率的上界汇率的上界 m m=汇率的下界汇率的下界 M/mM/m （变动比率）（变动比率）n n=交易阶段数交易阶段数n n 根根据据
23、已已知知条条件件的的不不同同，单单方方向向外外汇汇兑兑换换问问题题可可以以分为四个不同的类型：分为四个不同的类型：类型类型 1 1 1 1：MM，mm，和和n n已知；已知；类型类型 2 2 2 2：MM，mm已知已知n n未知；未知；类型类型 3 3 3 3：和和n n已知；已知；类型类型 4 4 4 4：已知已知n n未知。未知。证券投资问题第40页/共44页41 n n基于风险的外汇兑换策略基于风险的外汇兑换策略（Threat-based StrategyThreat-based Strategy）（）（El-YanivEl-Yaniv）规则规则1 1 1 1：只有在当前的汇率为最大值时
24、才考虑将部：只有在当前的汇率为最大值时才考虑将部分美元兑换成日元；分美元兑换成日元；规则规则2 2 2 2：每次将美元兑换成日元时，只兑换最少数：每次将美元兑换成日元时，只兑换最少数目的美元，使得即使以后的汇率一直保持最低时目的美元，使得即使以后的汇率一直保持最低时仍能保证竞争比为仍能保证竞争比为r r r r。证券投资问题第41页/共44页42 证券投资问题n n股票交易策略股票交易策略n n收益预期收益预期n n风险承受度风险承受度n n持有时间持有时间影响因素：影响因素：第42页/共44页43 n n 优惠卡购买问题：优惠卡购买问题：欧欧洲洲铁铁路路公公司司发发行行一一种种火火车车票票打
25、打折折的的优优惠惠卡卡，设设购购买买优优惠惠卡卡的的成成本本为为C,C,有有效效期期为为T,T,折折扣扣率率为为，旅旅行行者者在在不不清清楚楚未未来来旅旅行行需需求求的的情情况况下下，如如何何决决策策以以使使所所花花费费用用尽尽可可能能少少？n n Fleischer Fleischer提出最优的占线策略：提出最优的占线策略：当当S(S(购卡前所花费的总成本购卡前所花费的总成本)等于等于C/(1-C/(1-)时时,购买优惠购买优惠卡，并持有该卡至有效期结束。卡，并持有该卡至有效期结束。该策略竞争比为该策略竞争比为2-2-。例，例，C=240C=240元元,5050,T T1 1年，选择在临近年，选择在临近480480元的时机元的时机进行购买。进行购买。优惠卡购买问题第43页/共44页44 感谢您的观看！第44页/共44页