该文主要研究求解网络优化中的整数规划、背包、线性规划等问题的新算法及其高效并行算法.针对求解线性规划松弛算法在选取松弛变量时存在的不足,提出了线性规划问题有最优解的一个必要条件,将该必要条件应用于线性规划松弛算法中松弛变量的选取上,对松弛算法进行了改进.在此基础上,提出了一种基于Cluster结构的并行松弛算法,与线性规划同类并行算法对比,该算法具有更好的并行性和求解效率.最近,有学者提出了一种算法,它适于求解约束个数很多但变量个数较少的线性规划问题.该文根据其在数据和操作上各个步骤的相关性,将该算法在主从式消息传递接口环境下并行化,设计了一个求解该类问题的并行算法,理论分析和实验结果表明本算法具有良好的并行性和可扩展性.整数规划是离散算法和NP问题研究中的核心问题之一,如何提高实际应用中大规模整数规划问题的求解效率具有十分重要的理论和实际意义.利用二分网格作为几何工具,将传统二分搜索推广应用到整数规划问题的可行域中,提出一种求解整数规划的新算法.该算法不仅能够克服分枝限界算法和割平面算法求解系数呈指数增长的整数规划实例时存在的实质性困难,而且其高可并行性可望为一般大规模整数规划的精确求解提供新的可选方案.将该算法的设计思想用于求解与整数规划有密切关系的无界背包问题,得到一种求解该问题的新算法.新算法对于固定物品数背包实例的求解时间仅为问题输入规模L的线性函数,这一结果表明新算法明显改进了动态规划和分枝限界算法的相关性能.并行计算是解决等式背包问题的有效方法之一.该文深入研究了背包问题并行算法的研究现状,在指出相关文献一个主要结论错误的基础上,利用分治方法,首次提出了背包问题基于CREW模型的成本最优并行算法.然后,分析了基于CREW最优算法中可能存在的共享冲突,借鉴无存取冲突最优并行归并算法,进一步提出了背包问题基于EREW模型的成本最优并行算法,解决了算法中各处理机对共享存储器的存取冲突.