大数据时代下，海量实时数据为高效、科学的决策带来了困难，传统的运筹学方法在处理这些问题时十分困难。大数据背景下的决策问题多是NP难的，难以在多项式时间内给出问题的精确解。在面临难解问题的实例时，决策者通常会考虑如下问题:欲求得该问题实例的精确解，大概需要多少计算时间？如果时间有限且有精度要求，选择怎样的近似算法可以在满足精度要求下尽快求解？欲尽快得到一个满意的可行方案应选取怎样的启发式算法？若能预先通过某种快速而有效的方法给出计算该实例的计算成本，决策者便可以预知求解该问题需要多少计算代价，以便权衡计算精度与求解代价，做出最满意的决策。通过对组合优化问题的有效计算性和有效计算机制的研究，预测出决策分析时待求解问题的计算代价，对于大数据背景下决策科学的研究具有重要的理论和应用价值。　　如何实现组合优化问题的有效计算是运筹学和计算机科学共同关注的新的研究方向，同时也是大数据时代下的热点问题。当一个问题被证明是NP难的，意味着人们应该放弃寻求该问题的有效算法，要么尽可能地改进穷举搜索法，要么在允许的时间内找到一个满意解—用近似算法或者启发式算法。而面对一个问题实例来说，学者还未探讨过该实例是否具有特殊的数学结构因而不具有指数级别的计算复杂度，即便该问题是NP难的。未进行理论分析就接受一个近似的答案显然是不明智的。虽然某些NP难问题已被挖掘出了一定数量的多项式时间可解的特例，由于特例要求的条件过于严格，并不具备实用性。因此亟需新的理论或方法对问题实例的数学结构进行分析，并对计算代价做出预测。　　本文基于如何在求解难解问题实例前便可预测到该实例所需的计算代价这一基本问题，提出了有效计算性的主要思想，从三个组合优化问题特殊的数学结构出发，利用数学的方法演绎如何实现有效计算性，分析了求解难解问题实例的计算代价依赖于实例结构的机理，构建了结合用户需求的有效计算机制，为如何分析处理难解问题提供了新视角。主要研究内容包括:　　(1)N车探险问题的有效计算性。由N车探险问题最优解所需的必要条件出发，找到影响解空间大小的关键因素，定义实例数学结构中团的概念，研究最优解与实例中团结构的对应关系。结合针对团的精确算法，给出N车探险问题任意实例在不同团下的合理计算成本，建立N车探险问题有效计算性的理论框架。　　(2)航空器排列问题的有效计算性。研究与N车探险问题数学结构相近的航空器排列问题—N车探险问题是航空器排列问题的特例，给出航空器排列中团的概念，建立N车探险问题最优解与航空器排列问题最优解之间的联系，通过对N车探险问题实例的合理计算成本的估计预测出航空器排列问题实例的合理计算成本，建立了航空器排列问题的有效计算机制。　　(3)一类单机排序问题的有效计算性。将一类难解的单机排序问题作为有效计算性在其他组合优化问题的推广，给出这类单机排序问题的团的定义，通过探究最优解与团之间的联系，预测该问题任意实例的合理计算成本，最后建立了单机排序问题的有效计算机制。　　本文的主要创新点是:　　(1)针对难解问题如何实现有效计算性提出了合理计算成本的概念，在此基础上首次构建出有效计算性的理论框架。本文回答了如何结合用户需求，使得在求解难解问题实例前便可预测到待计算实例求解所需的计算代价这一基本问题，给出了分析难解问题实例合理计算成本的模式，为决策者做出最满意的决策提供有效的决策支持。　　(2)分别对N车探险问题、航空器排列问题的多项式可解的特例进行了推广。在N车探险问题和航空器排列问题的多项式可解的特例中，条件要求十分严格，绝大多数类型的实例不满足充分条件的要求。本文找到影响计算复杂度的关键指标，放松了条件中严格的假设，提出了团的概念，进而找到了团与最优解之间的联系，使得对N车探险问题、航空器排列问题的任意实例可以根据分团情况降低解空间的规模。　　(3)分别对N车探险问题、航空器排列问题设计了根据特定实例的计算复杂度以及时间约束、精度需求来判断计算成本的模式，并将该模式应用在一类单机排序问题上。分别对这三个难解问题不同实例在多项式时间内分析其计算复杂度，设计了在给定的计算时间和精度约束下对具体实例进行有效计算的机制。该方法为这类难解的组合优化问题提供了新的处理模式。