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

单纯形解线性规划问题及其编程实现 目    录摘要 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法 123.5 单纯形法的程序实现 143.5.1 算法描述 143.5.2 程序实现 154 结论 17参考文献 18致谢 19附录 20摘  要线性规划是运筹学中数学规划的基础部分，是运筹学中兴起较早并且应用广泛的1个部分。事实上，线性规划就是用数学为工具，来研究1定条件下，如何实现目标最优化。本文以经济生活中1个常见的实例为依据，建立线性规划模型，通过引入普通单纯形法，依次迭代并判断，逐步逼近，最后得到最优解。然后，介绍了求解1般线性规划问题的大M单纯形法（简称大M法），并举1例说明大M法的基本思路：通过添加人工变量使得标准化后的系数矩阵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 and 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 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 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 obtained 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 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年代末，苏联数学家康特罗维奇研究交通运输及机械加工等部门的生产管理工作，于1939年写了生产组织与计划中的数学方法1书初稿，为线性规划建立数学模型及解法奠定基础,自此开始，线性规划经过不断的应用和发展，在工业、农业生产管理，交通运输的指挥调度，资源开发，商业和银行等领域得到广泛应用，显著提高了企业的经济效益。随着生产规模的扩大和经济事务变得日益繁杂，对线性规划提出了更多的理论要求，又促使这门学科迅速发展和完善。线性规划不断发展，适用领域不断拓宽，从解决技术问题的最优化设计，到工业、农业、商业、交通运输业、军事、经济计划及管理等领域都发生着作用，已成为现代科学管理的重要基础理论。例如，在生产管理和经济活动中，经常遇到这些问题，如生产计划问题，即如何合理利用有限的人、财、物等资源，以便得到最好的经济效果；材料利用问题，即如何下料使用材最少；配料问题，即在原料供应量的限制下如何获取最大利润；劳动力安排问题，即如何用最少的劳动力来满足工作的需要；运输问题，即如何制定调运方案，使总运费最小；投资问题，即从投资项目中选取方案，使投资回报最大等等。对于这些问题，都能建立相应的线性规划模型。事实上，线性规划就是利用数学为工具，来研究在1定条件下，如何实现目标最优化。解线性规划问题目前最常见的方法有两种，图解法和单纯形法。然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。在电子计算机高速发展的今天，我们希望找到更适用和更快捷的解决线性规划问题的途径，并用计算机来实现。这就是本文要解决的课题。