组合最优化一直在我们的现实世界和生活生产中发挥着至关重要的作用,从网络的最短路径选择到飞机航班的调度,再到金融市场的投资安排,无处不见到组合最优化问题的身影。如何建立合理的组合优化模型并寻找有效的算法历来被广大学者所注重和研究,目前已形成了一整套完备却又生机勃勃,向前发展的体系。掌握并梳理一些组合最优化的经典问题有助于学习和掌握组合最优化这门学科,并有助于解决问题以及设计实用可行的高效算法。本文主要研究以下三类组合最优化模型和算法：中国邮递员问题,带拒绝费用的排序问题,投资组合问题。本文考虑了中国邮递员问题在三种网络结构(无向图,有向图,混合图)中的求解方法及算法复杂性,通过T-joins与T-cuts概念,对问题的结构给予了清晰描述,指明了未来研究的方向。在上述三种网络结构中综述了与该问题紧密相关的判定欧拉图问题的充分必要条件。我们给出了一个定理,并自然形成了一个猜测,最后构造了一个最小反例来否定该猜测,为未来的相关研究扫清了障碍。带拒绝费用的排序问题是经典排序问题的一个推广,因而是NP-hard的,除非P=NP,否则我们不可能找到多项式时间算法求得其最优解。本文分析了问题,得到了一个组合近似算法,证明了该算法是求解带拒绝费用排序问题的2-近似算法,且是强多项式时间算法,我们还提供了紧的实例,表明我们的分析是最好可能的。为未来研究该类问题打下了一个良好的基础。组合最优化的思想、观点和方法还可以应用到投资领域。本文考虑了带约束条件的投资组合模型MV模型,然后通过添加细化条件,克服了经典MV模型中假设条件过于苛刻同时又不适用于应用于实际生活的缺点,更好地改进并完善了经典MV模型的应用。并结合中国证券市场的交易数据对新建立的多条件约束的MV模型进行验证分析,以此来说明新建的多条件约束MV模型更加的合理、有效、可靠,为投资者提供更加准确的方案选择。