优化运输与线性规划：利用优秀非基本可行解求解

"这篇论文探讨了如何通过使用优秀的非基本可行解来求解运输问题和线性规划问题的最优解。作者R.R.K. Sharma在印度理工学院的工业与管理工程系工作。文章中提到了Sharma和Sharma以及Sharma和Prasad先前的研究成果，这些成果为解决运输问题提供了高效的启发式算法。Sharma和Sharma的方法能在O(c * n^2)的时间内给出优秀的对偶解，而Sharma和Prasad则基于此给出了O(n^3)复杂度的启发式方法，用于得到运输问题的良好原始解，通常是非基本可行解。接着，论文提出利用Sharma和Prasad的方法获取的优秀基本可行解，结合网络单纯形法，能够在最坏情况下以O(n^3 * log(n))的时间复杂度找到运输问题的最优解。 在论文的第二部分，作者关注于线性规划问题。他们介绍了一个简单的启发式程序，该程序能从Karmarkar的工作出发，在O(n^5.5)的时间复杂度内得到线性规划问题的良好非基本可行解。这个过程与之前文献[4]中的方法有显著区别。Karmarkar的算法是多项式时间内的，而此论文中提供的方法则能从Karmarkar的解开始，生成线性规划问题的良好基础可行解(BFS)。 这篇论文为运输问题和线性规划问题的求解提供了一种新的途径，即利用已有的优秀非基本可行解作为起点，通过优化算法进一步寻找最优解。这种方法不仅提高了求解效率，也丰富了现有的求解策略。" 该论文的重点在于： 1. **运输问题的优化**：通过Sharma和Sharma的高效启发式算法获取优秀的对偶解，再由Sharma和Prasad的方法得到非基本可行的原始解。这些解可以作为网络单纯形法的输入，以更快地找到最优解。 2. **线性规划问题的新方法**：基于Karmarkar算法生成的非基本可行解，设计了一个新的启发式程序，能够生成线性规划问题的良好基础可行解，且时间复杂度优于传统的算法。 3. **时间复杂度的改进**：论文中的方法减少了计算时间，对于运输问题，复杂度从O(n^3 * log(n))降低，而对于线性规划问题，提出了在O(n^5.5)时间内得到良好解的方案。 4. **算法的应用价值**：这些优化方法对于实际操作研究中的运输和线性规划问题具有重要意义，因为它们能够快速找到接近或最优的解，尤其在处理大规模问题时，效率的提升更为显著。