研究方法论(5)

1、研究方法，讲座5:繁忙的问题和竞争战略，Xi理工大学经济管理学院，2。繁忙问题和竞争战略，3。繁忙问题和竞争战略，4。1966年，格雷厄姆首次提出了一种竞争分析方法来解决并行机调度问题，并提出了一种简单的确定性贪婪算法。1983年，塔尔詹在数据结构和网络算法中讨论了阿莫蒂泽的方法，即繁忙问题和竞争策略的萌芽。近年来，在计算机理论科学和管理科学领域，对繁忙问题和竞争战略的研究取得了很好的理论和实践成果，如经典的k-服务器猜想、雪橇租赁问题、物流和金融中的繁忙问题等，都是当前的研究热点。繁忙问题和竞争战略，5、繁忙问题和竞争战略，6，1.a .博罗迪南达。亚尼夫，在线计算机与竞争分析M。剑桥大学出

2、版社，1998.2 .Spring-Verlag，BerlinHeidelbergGermany，germand，1998.3.D.D. SLEATORAND .E. TARJAN。简明更新和分页规则的非易失性。美国计算机制造商协会，28 (2) :202-208，1985.4。堵丁柱，K-汽车服务问题和竞争算法，数学实践和理解，4:36-40，1991.5，R.M .卡普，在线算法用户离线算法3360未来有多少网络？international computerscienceininstitutetetechnicalreporttr-92-044，Berkeley，CA，1992.6.P.K

3、eskinocak，R.Ravi，S . tayur . schedulingandreliablelead-time quotationfororderswithavailabilityintervalsandlead-timesensitiveevenues .管理科学，47，2:264-279，2001，书目和文章，7，经济管理中的繁忙问题，经济管理中的繁忙问题，物流管理中的繁忙问题，财务管理中的繁忙问题，运输，选址，库存，道路交通拥挤，车辆调度，物流中心选择，投资，财务管理，金融租赁，证券投资，折扣卡购买等。在网络G中，N个顶点都是服务对象，服务需求可以随时提出。现有的K个车辆(服务器

4、)按照需求的顺序为N个顶点服务。假设K辆车的初始位置是固定的。考虑以下两个问题：(1)预先给出一系列需要服务的顶点，并询问如何调动车辆以最小化所有车辆行驶的总距离？(2)如果在服务过程中一个接一个地接收到需求，那么只有在此之前的需求和服务过程才能时刻被知道。如何调动车辆以最小化总距离？需求不可预测的车辆调度问题，9，假设：需求不可预测的顶点序列策略：最近策略，公平策略最近策略：由最接近服务需求的车辆提供的服务公平策略：使每辆车辆具有相同的里程数、C、B、A、1、2、S1S2，需求不可预测的车辆调度问题，10，最近策略：车辆将在A和B之间移动m-1次，当M较大时，最优计划是将B移动到A，然后将点

5、C移动到B；这样，最近服务的行驶里程与最佳值的比率为(m-1)/3。随着m的增加，比率也增加。因此，最近策略不是竞争算法。对于每个车辆si和车辆行驶的距离di，服务需求r和移动si被最小化。在服务需求为n=k 1的任何度量空间中，BAL策略都是k竞争的。然而，在nk 1的测量空间中，BAL是一种非竞争战略。需求不可预测的车辆调度问题，12种情况，n=4，k=2，初始位置C，d。服务需求的最佳策略是首先将移动距离为M的车辆从C转移到B，然后两个车辆每次响应服务需求时只需要移动M。需求是(ai，bi)，这表明需要从ai点到bi点打车。基本假设：1)图g是连通的；二)当出现新的服务需求时，所有K出租

6、车都处于闲置状态；需求不可预测的车辆调度问题，14，出租车调度问题繁忙策略：重置策略竞争比结果：如果k-车辆调度问题存在竞争比2k- 1的繁忙策略，则k-出租车调度问题的重置策略具有竞争比2k-1。15.出租车调度和出租车市场的个人收入。政府规定出租车的数量和收费标准。在有限的交通网络中，出租车以统一的价格提供有竞争力的客运服务。网络上每个乘客的需求是r(ai，bi)，也就是说，ai中的用户需要乘出租车去bi。r(ai，bi)行进的时间、位置和距离是不确定的。出租车调度和个人收入问题出租车可以在完成r(ai，bi)后根据定价规则收费。空载驾驶和等待服务需求到达期间没有收入，必须支付一定的费用。

7、问题：假设没有考虑每辆出租车的固定费用，问题是如何衡量出租车在时间段T内的收入，以及其个人运营计划将如何影响其收入？需求不可预测的车辆调度问题，17，需求不可预测的车辆调度问题，18，出租车时间价格曲线，需求不可预测的车辆调度问题，19，交通网络上从起点到达目的地的车辆。出发前，决策者综合考虑各路段的交通状况，选择一条有效的路线。然而，在车辆沿着这条路线行驶的过程中，他们可能会遇到一系列的道路堵塞。由于获取信息的手段有限，决策者无法预测或只能预测即将到来的堵塞的信息，所以当决策者了解到关于堵塞发生的相关信息时，决策者应该制定什么样的出行策略？不同的策略有多有效？O，D，道路突然拥堵路径选择问题

8、，20，模型构建：当遇到k条拥堵边时，使用策略a从o点到d点运输货物的总成本：相应的离线最优成本基本假设：1)移除拥堵边后，图g仍然是连通的；2)只有当运输车辆到达被阻挡边缘的起点时，才能发现边缘被阻挡并且不能通过；3)一旦出现堵塞边缘，该边缘将被永远堵塞。贪婪策略(a)重置策略(b) 2K 1的竞争比不能提高，这是一般网络上不可逆拥塞问题的竞争比的下界。道路突发拥挤路径选择问题，一般网络不可恢复问题的应对策略，22，一般网络不可恢复拥挤问题贪婪策略最坏情况，道路突发拥挤路径选择问题，23，问题1:为什么贪婪策略的竞争比率明显高于重置策略，但从日常经验来看，人们经常使用贪婪策略？问题2:采取贪

9、婪策略合理吗？思考一般网络上不可恢复的拥塞问题的贪婪策略，道路上突然拥塞的路径选择，24，道路上突然拥塞的路径选择，思考一般网络上不可恢复的拥塞问题的贪婪策略，25，日常生活中的贪婪策略，道路上突然拥塞的路径选择，26，城市交通网络结构的网格网络，Xi an新城区的局部地图， 巴塞罗那城区局部地图，道路突发拥堵路径选择问题，27，城市交通网络结构环形放射状网络，上海市区局部地图，道路突发拥堵路径选择问题，28，城市交通网络结构混合网络(网格和环形混合)，上海市区局部地图，道路突发拥堵路径选择问题，29，城市交通网络结构自由式(山区等不具有一定几何形状)，重庆市区局部地图， 突发道路拥堵的路径选

10、择问题，30，突发道路拥堵的路径选择问题，31，突发道路拥堵的路径选择问题，32，突发道路拥堵的路径选择问题，目的地是一个图表，显示当做出多个选择时可以到达贪婪策略点，贪婪策略是特殊网络上不可恢复拥堵的贪婪策略的最坏情况，33，物流配送网络由多个配送中心组成，配送中心的数量随着未来需求的变化而增加，因此网络建设需要逐步完成。 也就是说，在前一阶段已经建立的配送中心的基础上，需要增加几个配送中心。问题是如何在不同的建设阶段对物流配送中心进行定位，以使网络中服务需求的运输成本最小化。物流配送中心选址问题，34，物流配送中心选址问题，A，B，C，D需求任意两点之间的距离是d (a，b)=d (a，c

11、)=d (b，c)=30d (d，a)=d (d，b)=d (d，c)=1目标函数：minW(I)D；I=A、B、C、D，假设一个城市的道路网络如下图所示，可选物流配送中心的地址为A、B、C、D、35、方案1: 1。第一个中心建在d 2点。当建立三个中心时，只有A，b，d，成本(d)=300=opt1成本(a，b，d)=100=100opt3，物流配送中心选址问题，36，A，b，c，d，1，30，1，1，30，计划2: 1。第一个中心建在a 2点。当三个中心建成后，就整体情况而言，计划2比计划1更好。物流配送中心选址问题，37，客户数量不确定性协调策略(HarmonicStrategy)如果知

12、道客户数量的上限m和下限m，就可以给出一个协调策略HS，也就是说，你需要每天准备一个客户。可以证明，这种策略的竞争比例是和谐平均的，库存管理问题，38，订单处理排序问题描述：供应商对于到达的客户订单，根据其处理时间长度，完成收入，交货日期等因素，决定处理订单，使一些成本(总完成时间，总延迟订单数)尽可能小，或收入(完成订单数，总完成收入)尽可能大。常见的处理策略：先来先服务(FCFS)，最早交货时间(EDF)，最短处理时间(SPT)，WSPT(加权SPT:按wi/pi降序排列)，订单处理问题，39，雪橇租赁问题描述：一个滑雪爱好者去滑雪，他要么租，要么买滑雪工具。假设滑雪者的实际租金是多少，每

13、个租金是p，如果购买的话，价格是c。如果不知道未来滑雪旅行的次数，滑雪者如何决定尽可能少花钱？卡普提出了最佳繁忙策略：租赁到k-1倍(k=c/p)，然后购买。其竞争比为2-1/k，融资租赁问题，40，雪橇租赁策略设计在线：第一次k-1次租赁所有时间，然后在必要时立即购买(k=1，2，)。1)当n k-1时，线上和线下产生相同的成本，只有租金而没有购买。2)当NK-1可用时，离线将立即购买该设备，而在线将等到K-1购买。金融租赁问题41外汇交易描述M=汇率上限m=汇率下限=m/m(变化率)n=交易级数根据已知条件，单向外汇交易问题可分为四种不同类型：类型1: m，M，n已知；类型2: m，m已知n未知；类型3: 和n已知；类型4: 已知n未知。证券投资问题，42，基于风险的外汇策略(三基策略)(El-yaniv)规则1:只有当当前汇率为最大值时，一些美元才能兑换成日元；规则2:每次美元兑换成日元时，只有少量的美元被兑换，因此即使汇率保持最低，竞争比率R也可以得到保证。证券投资