组合优化问题是运筹学中的一个重要分支,随着实践的不断发展,越来越多的新问题利用它的古典模型求解不再合适,比如最短路问题、最小费用流问题、运输问题等.因而需要对原来的古典模型进行改进,构造出新的组和优化模型,并为之设计算法.该文研究了组合优化问题中具有特殊限制的最短路问题、最小费用流问题和运输问题,共分为六章:第一章绪论,首先介绍了组合优化问题的统一形式,由于现代大多数组合优化问题都是NP-hard的,因此我们接着介绍了NP-hard问题几种常见的处理方法,最后介绍了与该文有关的三类经典组合优化问题的模型及算法.第二章研究随机时间依赖网络上的最短路问题.在确定性网络中,最短路问题已经被深入地研究,并被证明有着广泛的用途.在这些问题中,所有边的长度都是常数,目标是寻找一条路,使其经过的边的总长度最小,Dijkstra在文献[25]中给出了一个时间复杂性为O(n<2>)的多项式算法.第三章研究了一类带费用约束的紧急运输问题.第一节首先介绍了紧急运输问题的研究历史现状.1941年Hitchcock[10]建立了基本的运输问题模型.第四章研究了连续时间网络上的最小费用流问题.第一节首先介绍了连续时间网络上的最小费用流问题的历史及现状.1957年,Ford和Fulkerson最早提出了最大流问题[18,19],1961年,Fulkerson又单独研究了最小费用流问题[20].自此,网络流问题分为最大流和最小费用流两个分支.第五章研究了无容量限制的最小费用流问题.第六章研究了带容量限制的最小费用流问题.在第五章考虑了无容量限制的带固定费用的最小费用流问题后,作者认为在很多情况下,运输量将会大于网络中边上的容量限制,因此该文在这里研究了带容量线制的既有固定费用又有可变费用的最小费用流问题.