本文比较系统地研究了带预算的单商品在线定价问题,主要涉及近似算法设计与竞争比分析。对不同情景下的在线定价问题,设计了相应的近似算法并给出了它们的竞争比。带预算的单商品在线定价问题是指卖家有一定量的可分商品卖给用户,当一个用户到达时,卖家要根据用户的预算和出价等信息做出决定:给出当前用户的商品单价和分配的商品数量,目标函数是最大化卖家收入。带预算的单商品在线定价问题可运用于计算机带宽分配、云资源等领域,贴近实际,同时这些问题有着重要的理论意义。全文共分为五章,前一章主要介绍了与算法设计相关的概念及预备知识,总结了定价问题的相关研究现状及其模型。第二章研究了最大出价已知时,带公共预算的在线定价问题。对此问题设计出近似算法和分析算法的竞争比。当B≤m/[log h]+1时,竞争比为2;当m/[log h]+1<B<hm时,竞争比为max{O(log(Blog H)),O(log h};当B≥hm时,竞争比为O(log h)。第三章研究了最大出价能够提前知道时,带两类不同预算的在线定价问题。针对此问题设计出了近似算法。讨论了不同的预算大小对算法竞争比的影响。当B1<B2≤m/[log h]+1时,竞争比是2;当B1≤m/[log h]+1<hm ≤ B2时,竞争比是O(h([log h]+ 1));当B1≤m/[log h]+1<B2<hm时,竞争比是O(([log h]+1)+B2/B1);当m/[log h]+1<B1<2<hm时,竞争比为max{O(B2/B1 log(B1logh)),O(log h)};当m/[log h]+1<B1<hm ≤ B2时,竞争比是O(h(logh+ 1));当 hm<B1<B2 时,竞争比为O(log h)。第四章研究了最大出价不能提前知道时,带预算的商品在线定价问题,采用了不同于前面两章的价格形式进行分层,从而设计算法和分析算法的竞争比:当B≤m,竞争比是2h2/(?);当B>m,竞争比是max{O(B1/(?)),O(h3/(?))}。论文的最后部分是对此类问题的总结,讨论相关问题的进一步研究方向,尤其是把单商品问题推广到多种类商品。