组合拍卖，是允许竞标者将多个异质商品组合起来进行捆绑竞价的多物品拍卖方式。由于组合拍卖能给予竞标者极大的自由，能够激发竞标者的参与热情，并能有效地提高资源配置效率，同时增加拍卖收益和社会效益，所以，随着互联网的发展、商品交易的多样化，组合拍卖越来越引起人们的兴趣，成为网上拍卖理论和应用研究的热点问题之一。组合拍卖虽然具有很强的优势，但同时它也提出了大量的问题和挑战。其中，组合拍卖区别于非组合拍卖的一个明显特征就是组合拍卖中的计算复杂性，即组合拍卖的竞胜标确定问题。竞胜标求解已经被证明是一个NPC问题，其计算复杂性与拍卖效率之间的矛盾一直是影响组合拍卖广泛应用的主要障碍。障碍在实际问题中，可以被克服、降低或者避免。虽然克服不可避免的计算困难是很重要的能力，但是，若能利用组合拍卖问题的内在特性，采用合适的方法，依托组合拍卖的优势去降低或者避免其中的计算困难，则是最佳方法，也是有效解决WDP，促进组合拍卖在实际中广泛应用的至关重要问题之一。为了找到解决WDP的有效方法及全面了解WDP的研究现状，本文以“ISIWeb of Knowledge”为平台，以“winner determination problem”为关键词进行了文献搜索，对找出的删选后的101篇文献的全部摘要和部分正文进行了阅读分析，发现学者们虽然都认识到组合拍卖中实际商品的组合空间要比理论上的小得多，但是在WDP算法研究上，大多都是基于理论上如何战胜WDP的计算复杂性，而不是采用一些技巧，真正从商品实际可能出现的组合空间出发，从组合拍卖设计的优势出发，降低或者避免WDP的计算障碍。这种基于理论的要求，从各种角度包括人为限定投标空间或标的结构，对WDP进行求解的方法，由于和实际问题有不可近似性，所以影响了该理论在实际中的应用。但是这些也证明了，如果能根据组合拍卖实际问题特性，采用合适的方法，是一定可以有效解决WDP的。所以本文以降低或者避免WDP计算复杂性，进行定性与定量相结合的角度出发，以自动求解WDP为目的，定性分析商品的实际特征，采用可拓学中的物元模型，对商品的基本组合特征进行形式化表示，然后以投标语言表达其内在逻辑关系为基础，建立WDP的量化模型。接着，应用量性融合的NP难问题的可构造技术——有穷损害优先法构造WDP的求解过程，试图为WDP的解决寻找一个新的突破口，提供一个新的求解思路。首先，本文通过可拓理论，对商品及竞标人、投标行为等进行了定性分析和描述，并构建了相应的物元模型，真正表达出商品间的协同价值和竞标人偏好。根据物元模型对商品特性的描述，以具有协同价值的属性为依据，通过关联函数，构造了商品间实际可能发生的组合空间。其次，基于LGB投标语言，将定性分析得到的商品描述的物理模型转换为相应的逻辑模型，便于对WDP的定量分析及应用计算机进行存储与检索，以实现对WDP的自动求解。由于不同的投标结构对WDP算法的复杂度有很大影响，而树形结构已经被证明，在限定标的组合情况下，可以在多项式时间内求得最优解。因此针对上述的商品组合情况，构建其树形拓扑结构图及相应的搜索过程。接着，应用定性与定量方法相结合的有穷损害优先法，研究WDP的不可解度，并构造了其相对可计算性，使其可以在小于等于s步的计算时间内发现一个可计算集，在这个集合中找到每一个满足要求的有效商品组合，直至最终所找到的商品组合能够尽可能地使目标函数最大化为止。然后，本文采用了斯坦福大学开发的组合拍卖模拟测试数据平台，进行了实验验证，结果表明本文的算法是有效的。最后，为了更好地说明本文的思想与算法的可行性，采用了哈尔滨工业大学的一个科研项目数据，生产实际中组合拍卖的应用——医药采购招标的案例进行了分析，将依据本文方法的求解结果与实际已经发生的结果进行了比较，结果表明，二者的最终结果——获胜供应商及商品组合标的在很大程度相吻合，说明本文的思想虽然还需要进一步研究改进，但却可以在实际中有效应用，并且是能够促进组合拍卖在实践中广泛应用的有效途径之一。