单纯形解线性规划问题及其编程实现

1、单纯形解线性规划问题及其编程实现 目    录摘要 1前言 21 线性规划问题及其数学模型 31.1 问题提出 31.2 模型建立 31.3 线性规划模型的几种形式 41.3.1 1般形式 41.3.2 标准形式 41.3.3 1般形式化标准形式 52 线性规划问题解的概念 73 单纯形法解线性规划问题 83.1 单纯形法的基本思路 83.2 普通单纯形法原理 83.3 单纯形表 93.4 单纯形法的进1步讨论大m法 

2、;123.5 单纯形法的程序实现 143.5.1 算法描述 143.5.2 程序实现 154 结论 17参考文献 18致谢 19附录 20摘  要线性规划是运筹学中数学规划的基础部分，是运筹学中兴起较早并且应用广泛的1个部分。事实上，线性规划就是用数学为工具，来研究1定条件下，如何实现目标最优化。本文以经济生活中1个常见的实例为依据，建立线性规划模型，通过引入普通单纯形法，依次迭代并判断，逐步逼近，最后得到最优解。然后，介绍了求解1般线性规划问题的大m单纯形法（简称大m法），并举1例说明大m法的基本思路：通过添加人

3、工变量使得标准化后的系数矩阵1定含有单位矩阵，从而得到1组基变量和初始基本可行解。由于人工变量是人为添加的，为了不改变原问题，在目标函数中消去人工变量，并将人工变量由初始的基变量化成非基变量，使之取值为0，然后用普通单纯形法求解。最后，本文还实现了用大m单纯形法的程序解线性规划问题。关键字：线性规划；单纯形法；大m法。abstractthe linear programming is a fundamental part of mathematical programming in the operations research . it is also an early-emerging a

4、nd an extensively-applied part in the operations research . in fact , the linear programming uses mathematics as the tool and studies how to achieve the goal optimization under certain conditions . this paper took a common example in economic life as the basis , and established a linear programming

5、model , through introducing the ordinary simplex method , iterated and judged in turn , then approached gradually and at last got the optimal solution . later , this article illustrated the big m simplex method ( the i.e. big m method ), which could solve the general linear programming problems and

6、developed simultaneously an example to explain the basic mentality of the big m method . then , the essay added some artificial variables in order that the standardized coefficient matrix include a unitary matrix from which a group of base variables and the initial basic feasible solution could be o

7、btained very easily . because the artificial variables was the artificial addendum , in order not to change the original question , this paper eliminated the artificial variables in the objective function , and turned the artificial variables from the initial base variables to the non-base variables

8、 whose value is zero , then , use the ordinary simplex method to get the solution . finally , this article realized to solve the linear programming problems in the procedure of the big m simplex method .   keywords ：linear programming ; simplex method ; big m method . 前言20世纪30年代末，苏联数学

9、家康特罗维奇研究交通运输及机械加工等部门的生产管理工作，于1939年写了生产组织与计划中的数学方法1书初稿，为线性规划建立数学模型及解法奠定基础,自此开始，线性规划经过不断的应用和发展，在工业、农业生产管理，交通运输的指挥调度，资源开发，商业和银行等领域得到广泛应用，显著提高了企业的经济效益。随着生产规模的扩大和经济事务变得日益繁杂，对线性规划提出了更多的理论要求，又促使这门学科迅速发展和完善。线性规划不断发展，适用领域不断拓宽，从解决技术问题的最优化设计，到工业、农业、商业、交通运输业、军事、经济计划及管理等领域都发生着作用，已成为现代科学管理的重要基础理论。例如，在生产管理和经济活动中，经常遇到这些问题，如生产计划问题，即如何合理利用有限的人、财、物等资源，以便得到最好的经济效果；材料利用问题，即如何下料使用材最少；配料问题，即在原料供应量的限制下如何获取最大利润；劳动力安排问题，即如何用最少的劳动力来满足工作的需要；运输问题，即如何制定调运方案，使总运费最小；投资问题，即从投资项目中选取方案，使投资回报最大等等。对于这些问题，都能建立相应的线性规划模型。事实上，线性规划