2 线性规划与单纯形法

本章要求

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

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

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

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

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

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

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

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