组合优化是运筹学的一个重要研究分支,包含很多经典问题,如排序问题、网络流问题、背包问题、装箱问题等。每个组合优化问题都有各自的参数,如排序问题中工件的加工时间、背包问题中物品的权重和价值、装箱问题中物品的大小等。在传统的组合优化研究中,这些参数一般独立于问题的决策,由外部环境预先给定。在实际的应用中,决定这些参数往往也是一个需要优化的问题,例如参数需要满足一些资源的约束或满足一定的供求关系。本文研究一些线性约束下的经典组合优化问题,即组合优化问题的参数需要满足一些线性约束,因此也是决策的一部分。本文研究的问题包括线性约束下的排序问题、线性约束下的背包问题、线性约束下的装箱问题等。这些问题具有全新的结构,在实际生活中有广泛的应用场景,蕴含着丰富的研究内容,但文献中却很少有相关的研究。本文首先给出了这些线性约束下的组合优化问题的具体模型,提供它们的研究动机和实际背景。很多线性约束下的组合优化问题,都能自然地表示成一些复杂的数学规划问题,如混合双线性规划问题。一般而言,这些数学规划问题都是十分困难的,不容易直接应用它们的结论去求解本文研究的问题。利用线性规划和组合优化的技术,本文分析这些问题的计算复杂性和提出相应的算法。本文通过研究发现,有一些原来困难的组合优化问题,例如平行机排序问题、装箱问题等,其线性约束下的问题在某些情况下,如约束的个数并不多时是多项式可解的;也有一些原来可解的组合优化问题,例如不含负权的最短路问题等,其线性约束下的问题一般情况下是困难和难以近似的。本文主要的创新点总结如下:1.根据实际应用需要,提出了线性约束下的组合优化问题的概念,并建立了一系列线性约束下的经典组合优化问题。2.探索线性约束下的组合优化问题的结构与性质,并建立它们与线性规划、经典组合优化问题的联系。3.分析这些问题在不同情形下的计算复杂性,并设计相应的多项式时间算法或近似算法。