论文部分内容阅读
排序是一类重要的组合最优化问题。本文主要讨论了离散型、连续型、离散与连续混合型三种最优资源分配与排序问题，对每种问题都给出了相应的多项式算法及算例分析。
第二章讨论了形如P<,m>|res sh，p<,j>=1|C<,max>离散型多资源排序问题，这一问题等价于一类整数规划问题，得到了一个求解基本向量的分枝定界算法。
第三章研究了形如的连续型问题的算法及其算法复杂性，同时证明了由此所求出的资源分配u<*>确系最优资源分配。
第四章研究了形如：的离散与连续混合型排序问题，给出了最优排序和最优资源分配的定义，讨论并证明了寻求其最优资源分配的多项式算法。