2 线性规划与单纯形法

本章要求

□ 掌握线性规划的数学模型及建模步骤。

□ 掌握线性规划的图解法。

□ 认识线性规划的标准型及掌握转化为标准型的方法。

□ 掌握单纯形法与单纯形表；掌握人工变量方法的使用。

□ 会使用计算机软件求解线性规划。

□ 掌握线性规划一些常见的应用例子。

线性规划（Linear Programming）是运筹学中一个应用最为广泛的重要分支。自从1947年G.B.Dantzig提出了求解一般线性规划问题的有效方法——单纯形法（Simplex Method）之后，线性规划得到了较快的发展。由于线性规划的模型比较简单，理论与方法都比较成熟，又有很多供不同使用者使用的计算机软件，因此，线性规划在工业、农业、商业、交通运输业、军事、经济和管理等各领域中得到了广泛的应用。曾经有人做过调查，在世界500家大公司中，有85%的公司使用过线性规划解决经营管理中遇到的复杂问题。在经济管理活动中，人们经常利用线性规划模型求解有限资源的最优分配问题。随着电子计算机技术的迅速发展，线性规划将在经济管理中发挥越来越大的作用。

应该指出，近年来已出现了若干在理论上优越于单纯形法的算法，其中的Karmarkar算法及其变形在实际应用中也显示了巨大的潜力，尤其是对于大型问题。不过，并不能说新算法将要替代单纯形法，至少在可以预见的将来不会，沿用至今的单纯形法仍在继续发挥其积极作用。有兴趣的读者可参看有关参考文献（如本书参考文献3）。