购买价格递减的在线租赁问题策略设计

运用在线问题与竞争分析的方法研究了购买价格递减的在线租赁问题。通过揭示相关费用函数的性质,先后给出了最优离线策略以及在线策略。通过竞争比分析,证明了我们给出的在线策略是该问题唯一最优策略,而且该策略的竞争比随购买价格的优惠率的增加呈严格递减趋势。竞争分析结果表明考虑购买价格递减因素能够改进在线策略的竞争比从而提高决策效率。     

价格数量折扣下多阶段报童问题的在线策略

价格数量折扣可以提高订购量, 是库存决策中的一个重要因素. 特别地, 当订购量达到一定水平时, 价格折扣才会发生. 应用理论计算机科学兴起的弱集成算法, 研究具有这种价格数量折扣的多阶段报童问题的在线策略. 弱集成算法是一种在线序列决策算法, 其主要特点是不对未来输入做任何统计假设, 克服了报童问题研究中需要对需求做概率假设的困难. 主要将弱集成算法应用到固定订购量的专家策略, 给出了价格数量折扣下多阶段报童问题的具体在线策略;得到了该在线策略相对于最优专家策略的理论保证. 进一步将回收价值和缺货损失费引入, 给出了推广的在线策略及其理论结果. 最后应用数值算例说明了给出的在线策略具有较好的竞争性能.     

Competitive analysis of online inventory problem with interrelated prices

This paper investigates the online inventory problem with interrelated prices in which a decision of when and how much to replenish must be made in an online fashion even without concrete knowledge of future prices.Four new online models with different price correlations are proposed in this paper,which are the linear-decrease model,the log-decrease model,the logarithmic model and the exponential model.For the first two models,the online algorithms are developed,and as the performance measure of online algorithm,the upper and lower bounds of competitive ratios of the algorithms are derived respectively.For the exponential and logarithmic models,the online algorithms are proposed by the solution of linear programming and the corresponding competitive ratios are analyzed,respectively.Additionally,the algorithm designed for the exponential model is optimal,and the algorithm for the logarithmic model is optimal only under some certain conditions.Moreover,some numerical examples illustrate that the algorithms based on the dprice-conservative strategy are more suitable when the purchase price fluctuates relatively flat.     

Competitive online algorithms for resource allocation over the positive semidefinite cone

We consider a new and general online resource allocation problem, where the goal is to maximize a function of a positive semidefinite (PSD) matrix with a scalar budget constraint. The problem data arrives online, and the algorithm needs to make an irrevocable decision at each step. Of particular interest are classic experiment design problems in the online setting, with the algorithm deciding whether to allocate budget to each experiment as new experiments become available sequentially. We analyze two greedy primal-dual algorithms and provide bounds on their competitive ratios. Our analysis relies on a smooth surrogate of the objective function that needs to satisfy a new diminishing returns (PSD-DR) property (that its gradient is order-reversing with respect to the PSD cone). Using the representation for monotone maps on the PSD cone given by Löwner’s theorem, we obtain a convex parametrization of the family of functions satisfying PSD-DR. We then formulate a convex optimization problem to directly optimize our competitive ratio bound over this set. This design problem can be solved offline before the data start arriving. The online algorithm that uses the designed smoothing is tailored to the given cost function, and enjoys a competitive ratio at least as good as our optimized bound. We provide examples of computing the smooth surrogate for D-optimal and A-optimal experiment design, and demonstrate the performance of the custom-designed algorithm.     

Estimating intermediate price transitions in online auctions

This paper discusses a statistical model regarding intermediate price transitions of online auctions. The objective was to characterize the stochastic process by which prices of online auctions evolve and to estimate conditional intermediate price transition probabilities given current price, elapsed auction time, number of competing auctions, and calendar time. Conditions to ensure monotone price transitions in the current price and number of competing auctions are discussed and empirically validated. In particular, we show that over discrete periods, the intermediate price transitions are increasing in the current price, decreasing in the number of ongoing auctions at a diminishing rate, and decreasing over time. These results provide managerial insight into the effect of how online auctions are released and overlap. The proposed model is based on the framework of generalized linear models using a zero‐inflated gamma distribution. Empirical analysis and parameter estimation is based on data from eBay auctions conducted by Dell. Copyright © 2011 John Wiley & Sons, Ltd.     

三次Hermite插值方法在证券投资分析中的应用

利用三次Hermite插值公式给出了寻找曲线之间相似程度的算法,对于给定股票的任意一段曲线形状,文章利用该算法找出走势与之相似的股票,将原来只能寻找股价曲线满足特定形状(如W底)的股票的方法进行了推广,对于证券投资者来说是一个有效的工具.同时文章将相似算法应用于利用某只股票的历史走势来预测该股票价格的将来走势,具有有效的投资指导意义.实验证明,文章给出的算法是行之有效的.     

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

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

Optimal Prioritized Infeasibility Handling in Model Predictive Control: Parametric Preemptive Multiobjective Linear Programming Approach

All practical implementations of model-based predictive control (MPC) require a means to recover from infeasibility. We propose a strategy designed for linear state-space MPC with prioritized constraints. It relaxes optimally an infeasible MPC optimization problem into a feasible one by solving a single-objective linear program (LP) online in addition to the standard online MPC optimization problem at each sample. By optimal, it is meant that the violation of a lower prioritized constraint cannot be made less without increasing the violation of a higher prioritized constraint. The problem of computing optimal constraint violations is naturally formulated as a parametric preemptive multiobjective LP. By extending well-known results from parametric LP, the preemptive multiobjective LP is reformulated into an equivalent standard single-objective LP. An efficient algorithm for offline design of this LP is given, and the algorithm is illustrated on an example.     

基于网络顾客行为意向的物流服务供应链定价策略

就一个运营网络购物的供应链,分析物流服务需求方和服务提供方的定价和服务水平决策等问题。在成本共担优化模型中考虑基于顾客购买行为意向的产品需求函数,进而分别给出非合作、准合作和完全合作模式下供应链企业决策间的关系,以及网购顾客重购概率对最优定价策略的影响。结论有:证明三种合作模式下双方最优策略的存在性及存在条件;给出最优产品定价策略和服务定价策略间的数量关系,并证明其与网购顾客行为意向有关。数值分析表明,最优定价策略随服务水平和网购顾客重购概率的变化趋势受成本共担系数的影响;较小的成本分摊系数使最优产品定价随着服务水平和网购顾客重购概率的变化幅度增大。     

在线Logistic回归

针对连续数据流分类问题,基于在线学习理论,提出一种在线logistic回归算法.研究带有正则项的在线logistic回归,提出了在线logistic-l2回归模型,并给出了理论界估计.最终实验结果表明,随着在线迭代次数的增加,提出的模型与算法能够达到离线预测的分类结果.本文工作为处理海量流数据分类问题提供了一种新的有效方法.     

Extensions to online delay management on a single train line: new bounds for delay minimization and profit maximization

We present extensions to the Online Delay Management Problem on a Single Train Line. While a train travels along the line, it learns at each station how many of the passengers wanting to board the train have a delay of δ. If the train does not wait for them, they get delayed even more since they have to wait for the next train. Otherwise, the train waits and those passengers who were on time are delayed by δ. The problem consists in deciding when to wait in order to minimize the total delay of all passengers on the train line. We provide an improved lower bound on the competitive ratio of any deterministic online algorithm solving the problem using game tree evaluation. For the extension of the original model to two possible passenger delays δ ₁ and δ ₂, we present a 3-competitive deterministic online algorithm. Moreover, we study an objective function modeling the refund system of the German national railway company, which pays passengers with a delay of at least Δ a part of their ticket price back. In this setting, the aim is to maximize the profit. We show that there cannot be a deterministic competitive online algorithm for this problem and present a 2-competitive randomized algorithm.     

Optimizing capacity,pricing and location decisions on a congested network with balking

In this paper, we consider the problem of making simultaneous decisions on the location, service rate (capacity) and the price of providing service for facilities on a network. We assume that the demand for service from each node of the network follows a Poisson process. The demand is assumed to depend on both price and distance. All facilities are assumed to charge the same price and customers wishing to obtain service choose a facility according to a Multinomial Logit function. Upon arrival to a facility, customers may join the system after observing the number of people in the queue. Service time at each facility is assumed to be exponentially distributed. We first present several structural results. Then, we propose an algorithm to obtain the optimal service rate and an approximate optimal price at each facility. We also develop a heuristic algorithm to find the locations of the facilities based on the tabu search method. We demonstrate the efficiency of the algorithms numerically.     

Retailer’s optimal pricing and lot-sizing policies for deteriorating items with partial backlogging

Pricing is a major strategy for a retailer to obtain its maximum profit. Therefore, in this paper, we establish an economic order quantity model for a retailer to determine its optimal selling price, replenishment number and replenishment schedule with partial backlogging. We first prove that the optimal replenishment schedule not only exists but also is unique, for any given selling price. Next, we show that the total profit is a concave function of p when the replenishment number and schedule are given. We then provide a simple algorithm to find the optimal selling price, replenishment number and replenishment timing for the proposed model. Finally, we use a couple of numerical examples to illustrate the algorithm.     

A dynamic quantity discount lot size model with resales

This paper deals with a dynamic lot size problem in which the unit purchasing price depends on the quantity of an order and resale of the excess is possible at the end of each period. We assume an all units discount system with a single price break point. Investigation of the properties of an optimal solution allows us to develop a dynamic programming algorithm. A problem example is solved to illustrate the algorithm.     

基于高斯分布的在线采购机制设计及竞争分析

依附于互联网电子商务的在线采购拍卖交易, 对传统的贝叶斯离线拍卖理论提出新的挑战, 因为面对不同时间点的投标, 采购电商必须即可决策出是否中标以及购买价格。鉴于此, 对于诸如石油、煤、粮食等无限可分商品的电子采购, 本文基于投标具有高斯分布特征设计了一种激励相容的在线采购策略, 演绎出在线采购的数学模型, 利用Runge-Kutta数值算法, 通过Matlab编程求解出采购电商在线定价策略的需求曲线及其对应的竞争比, 最后, 利用数值模拟, 将在线采购机制策略与纯竞争分析得到的在线采购策略比较, 结果显示利用了高斯分布信息的在线采购策略的竞争性能由于利用了投标的统计信息而得到了提高。     

碳交易机制下考虑制造商竞争的供应链协调研究

在碳交易机制背景下考虑普通制造商和低碳制造商存在竞争的情形,分别构建集中和分散模式下的供应链决策模型并对减排率以及产品销售价格进行求解。针对分散决策造成的供应链利润损失情况,采用Shapley值法对供应链进行协调,并给出契约协调机制。最后通过算例分析了Shapley值法的有效性,并对碳交易价格和消费者价格敏感性进行灵敏度分析。研究表明:Shapley值法的引入提高了供应链成员以及供应链的总利润,实现了供应链协调;碳交易机制的实施减少了碳排放总量,但较高的碳交易价格会降低供应链利润;消费者价格敏感性的增加使得普通制造商、低碳制造商、零售商以及供应链整体利润均降低。     

Scheduling with unexpected machine breakdowns

We investigate an online version of a basic scheduling problem where a set of jobs has to be scheduled on a number of identical machines so as to minimize the makespan. The job processing times are known in advance and preemption of jobs is allowed. Machines are non-continuously available, i.e., they can break down and recover at arbitrary time instances not known in advance. New machines may be added as well. Thus machine availabilities change online. We first show that no online algorithm can construct optimal schedules. We also show that no online algorithm can achieve a bounded competitive ratio if there may be time intervals where no machine is available. Then we present an online algorithm that constructs schedules with an optimal makespan of C_max^OPT if a lookahead of one is given, i.e., the algorithm always knows the next point in time when the set of available machines changes. Finally, we give an online algorithm without lookahead that constructs schedules with a nearly optimal makespan of C_max^OPT+, for any >0, if at any time at least one machine is available. Our results demonstrate that not knowing machine availabilities in advance is of little harm.     

基于电子优惠券投放和服务创新的线上线下渠道竞争分析

基于豪泰林模型分析具有渠道偏好的线上网络渠道和线下实体渠道市场竞争格局及其博弈关系,构建线上网络渠道投放电子优惠券、线下实体渠道服务创新的渠道竞争模型,剖析优惠券和服务创新对市场份额、定价及利润的影响,并给出具有市场进入时序的渠道退出边界。研究发现:市场缺额情形凭借高价获得较小市场份额下的较高利润,而市场重叠情形的低价策略在较大市场份额下获得较小利润。当服务创新足以支撑实体渠道要价时,其可获得较高利润,守住混合偏好市场;投放电子优惠券的让价方式可增大网络渠道的调价空间,且存在最优电子优惠券面值使网络渠道获得期望收益,夺得混合偏好市场。     

反向拍卖的一种在线定价策略及竞争分析

本文讨论了网络环境下从众多投标的供应商那里选择一家供应商来购进所需商品的反向拍卖,提出了一种考虑了买家起始价格和最高忍耐价格的在线定价策略,该在线定价策略利用了市场的价格信息,克服了由单一定价造成的完不成采购任务或不必要的成本浪费等缺陷,对该在线定价策略进行了竞争分析并得到了最优的竞争比。最后,通过实例说明本文提出的在线定价策略的可操作性。     

Online Point Location in Planar Arrangements and Its Applications

Recently, Har-Peled [HP2] presented a new randomized technique for online construction of the zone of a curve in a planar arrangement of arcs. In this paper we present several applications of this technique, which yield improved solutions to a variety of problems. These applications include: (i) an efficient mechanism for performing online point-location queries in an arrangement of arcs; (ii) an efficient algorithm for computing an approximation to the minimum weight Steiner tree of a set of points, where the weight is the number of intersections between the tree edges and a given collection of arcs; (iii) a subquadratic algorithm for cutting a set of pseudo-parabolas into pseudo-segments; (iv) an algorithm for cutting a set of line segments (``rods') in 3-space to eliminate all cycles in the vertical depth order; and (v) a near-optimal algorithm for reporting all bichromatic intersections between a set R of red arcs and a set B of blue arcs, where the unions of the arcs in each set are both connected. Received December 22, 1999, and in revised form August 25, 2000. Online publication May 11, 2001.