论文部分内容阅读
本文介绍了格基理论的主要原理与它的一些实际应用，然后把格基约化理论应用到运输问题的求解上来.运输问题实际上就是求解满足一定约束条件的线性方程组A·x=b，一般情况下，这是一个NP-问题。
本文首先通过LLL约化算法求得没有约束情况下满足方程组的基解，然后用分枝定界算法在满足约束条件的解空间中进一步找到使运输费用最小的解向量.用格基约化理论求解运输问题解空间的算法复杂度为多项式次时间。
文章中还给出了用格基理论求解运输问题的一个实例。