NHAPTER 1 第1章 线性规划及单纯形法 学习目标与要求 1.掌握线性规划的有关概念，会化非标准型线性规划为标准型线性规划。 2.初步建立数学模型的概念。 3.掌握求解线性规划的单纯形法并会用MATLAB求解线性规划问题。 1.1线性规划问题及其标准型 线性规划(Linear Programming,LP)是运筹学中一个基础而重要的分支。很多其他 运筹学问题的求解都以线性规划问题为基础。线性规划开创性的工作可以追溯到1939年 苏联数学家、经济学家康托洛维奇(L.V.Kantorovich,1912-1986)的著作《生产组织 和计划中的数学方法》。他把资源最优利用这一传统的经济学问题，由定性研究和一般 的定量分析推进到现实计量阶段，对于在企业范围内如何科学地组织生产和在国民经济 范围内怎样最优地利用资源等问题做出了独创性的研究。此外，美国经济学家库普曼斯 (T.C.Koopmans)和美国数学家丹兹格(G.B.Dantzig)在线性规划的发展历史中也作 出了开创性的卓越贡献。前者在第二次世界大战期间重新独立地研究了运输问题，后者 则发明了20世纪最伟大的算法之一，即用于求解线性规划问题的单纯形法。从理论上来 说，单纯形法不是多项式时间算法，而后来出现的椭球算法和内点算法才是求解线性规 划问题的多项式时间算法，但在实际计算中，特别是对中小规模的线性规划问题，单纯形 法的表现仍然很好。因此，对于现在学习运筹学的人来说，单纯形法仍然是必须掌握的算1.1 线性规划问题及其标准型 线性规划 (Linear Programming, LP) 是运筹学中一个基础而重要的分支。很多其他 运筹学问题的求解都以线性规划问题为基础。线性规划开创性的工作可以追溯到 1939 年 苏联数学家、经济学家康托洛维奇 (L. V. Kantorovich, 1912—1986) 的著作《生产组织 和计划中的数学方法》。他把资源最优利用这一传统的经济学问题，由定性研究和一般 的定量分析推进到现实计量阶段，对于在企业范围内如何科学地组织生产和在国民经济 范围内怎样最优地利用资源等问题做出了独创性的研究。此外，美国经济学家库普曼斯 (T. C. Koopmans) 和美国数学家丹兹格 (G. B. Dantzig) 在线性规划的发展历史中也作 出了开创性的卓越贡献。前者在第二次世界大战期间重新独立地研究了运输问题，后者 则发明了 20 世纪最伟大的算法之一，即用于求解线性规划问题的单纯形法。从理论上来 说，单纯形法不是多项式时间算法，而后来出现的椭球算法和内点算法才是求解线性规 划问题的多项式时间算法，但在实际计算中，特别是对中小规模的线性规划问题，单纯形 法的表现仍然很好。因此，对于现在学习运筹学的人来说，单纯形法仍然是必须掌握的算