《单纯形解线性规划问题及其编程实现》由会员分享，可在线阅读，更多相关《单纯形解线性规划问题及其编程实现（3页珍藏版）》请在装配图网上搜索。
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书初稿，为线性规划建立数学模型及解法奠定基础,自此开始，线性规划经过不断的应用和发展，在工业、农业生产管理，交通运输的指挥调度，资源开发，商业和银行等领域得到广泛应用，显著提高了企业的经济效益。随着生产规模的扩大和经济事务变得日益繁杂，对线性规划提出了更多的理论要求，又促使这门学科迅速发展和完善。线性规划不断发展，适用领域不断拓宽，从解决技术问题的最优化设计，到工业、农业、商业、交通运输业、军事、经济计划及管理等领域都发生着作用，已成为现代科学管理的重要基础理论。例如，在生产管理和经济活动中，经
10、常遇到这些问题，如生产计划问题，即如何合理利用有限的人、财、物等资源，以便得到最好的经济效果；材料利用问题，即如何下料使用材最少；配料问题，即在原料供应量的限制下如何获取最大利润；劳动力安排问题，即如何用最少的劳动力来满足工作的需要；运输问题，即如何制定调运方案，使总运费最小；投资问题，即从投资项目中选取方案，使投资回报最大等等。对于这些问题，都能建立相应的线性规划模型。事实上，线性规划就是利用数学为工具，来研究在1定条件下，如何实现目标最优化。解线性规划问题目前最常见的方法有两种，图解法和单纯形法。然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。在电子计算机高速发展的今天，我们希望找到更适用和更快捷的解决线性规划问题的途径，并用计算机来实现。这就是本文要解决的课题。
单纯形解线性规划问题及其编程实现
