免费下载
网站简介

找论文变得更简单!

帮找论文

当前位置:

重点论文网    理科论文    数学与应用数学论文    线性规划理论的发展概况介绍
创建时间:01-29

线性规划理论的发展概况介绍

目 录


摘要………………………………………………………………………………………………1

前言………………………………………………………………………………………………2

正文

1 线性规划理论的产生及其发展背景……………………………………………………… 3
2 线性规划问题及其数学模型………………………………………………………………3
3 线性规划问题的基本解法及其优缺点……………………………………………………6
3.1图解法及其几何意义……………………………………………………6
3.2 单纯形法……………………………………………………………………7
3.3  单纯形表……………………………………………………………………………12
3.4 人工变量法…………………………………………………………………………… 14
3.4.1 两阶段法……………………………………………………………………………14
3.4.2 大M法…………………………………………………………………………… 14
3.5 改进单纯形法………………………………………………………………………… 15
3.6 对偶单纯形法………………………………………………………………………… 18
4  线性规划的应用领域和主要发展方向…………………………………………………… 21
5  结束语 ………………………………………………………………………………………22

参考文献…………………………………………………………………………………………23

致   谢………………………………………………………………………………………24


线性规划理论的发展概况介绍
 

摘要:本文初步阐述了线性规划产生的历史背景,发展概况,从线性规划问题问题出发,建立相应的数学模型,进而对线性规划有了更理性、更深层的认识.介绍了图解法﹑单纯形法﹑人工变量法﹑对偶单纯形法几种基本解法及其优、缺点,以及对几种基本方法的改进.以科学发展观的立场看线性规划在全球化过程中的巨大推动作用,特别是在合理配置资源方面所发挥的作用
关键词:目标函数;价值系数;右端向量;可行区域。


Linear programming and its development survey
 

Abstract:This paper analyzes the characteristics of the linear programming historical background, the development of the profile from the linear programming problem issue. corresponding mathematical model, and linear programming to a more rational, more profound understanding. Introduced a graphical method ﹑ simplex method ﹑ artificial variable ﹑ dual simplex method and the solution of several basic advantages and disadvantages. Some of the basic methods of improvement. To the concept of scientific development standpoint of linear programming in the process of globalization the tremendous impetus, In particular, the rational distribution of resources has played a role .
Keywords:objective function ,cost coefficient, right-hand-side vector,feasible region.
 
前  言


线性规划作为运筹学的一个基本分支,其作用已为越来越多的各界人士所重视。这里不防引用美国科学、工程和公共事务政策委员会数学组1983年在一份报告中所写的一段话:“我们必须说明数学规划所发生的影响,线性规划是为解决二次世界大战中的后勤供应问题而产生的。单纯形方法的提出及其在初期成功的应用,使的能用线性规划解决的问题类型先是缓慢地,但接着就是急速地增加。线性规划成为几乎所有的商业活动、工业生产和军事行动的一个组成部分。由于在设计和操作过程中应用了线性规划,已经节省了亿万美元。”正因为如此,线性规划目前已成为各高等学校的运筹学系、应用数学系、管理科学系、系统工程系、经济系及计算机科学系中普遍开设的一门基础课。
最近十多年来,线性规划无论是在深度还是在广度方面都又取得了重大进展,已至在国际运筹学界近来又出现了一股“线性规划热”。遗憾的是,线性规划的一些最新成果在国内很少得到反映与介绍。希望本文对“线性规划”的初学者而言将会有一定的帮助,由于本人经验与学识原因,文中错误和缺点在所难免,诚请读者批评指正。
 
1  线性规划理论的产生及其发展背景
总体上看,线性规划理论发端于1914年F.W.兰切斯特的战斗方程,发展于20世纪第二次世界大战中的军事应用(制定雷达使用的策略,攻击潜艇策略,舰艇躲避飞机攻击策略等),完善于二战后期(武器系统设计的优化、武器事业的配系优化、战术与战略部署的优化等).成熟于冷战时期.线性规划理论构成了军事运筹学的基础,不仅在军事领域获得了广泛的应用,同时也在经济决策领域、科学研究及其他领域都获得了普遍的应用.
历史上,有两个人对线性规划理论作出了重要贡献.
其一是前苏联数学家康托洛维奇.他是线性规划的先驱者.他在1938年就给出了像寻求用8种型号的机床完成5种类型产品加工的最合理运行计划这样问题的数学处理,1939年发表《生产组织与计划中的数学方法》,是最早的线性规划著作,他提出了类似于线性规划的数学模型,并给出了“乘数解法”的求解方法,该方法是针对解决工业企业中的生产组织与计划问题提出的.但是,由于当时并未受到苏联政府的重视,一直没有得到推广运用.1960年,康托洛维奇再次发表了《最佳资源利用的经济》一书,受到了国内外的普遍重视,为此,康托洛维奇获得了诺贝尔奖金.
其二是美国的丹捷格.他也独立地发展了线性规划理论,线性规划这一名称就是他首次使用的.特别丹捷格设计了一种叫单纯形法的算法,作为求解线性规划问题的计算工具.
之后线性规划理论和方法在全世界(特别是在发达国家)得到了普遍的应用,在军事、工业、农业、自然科学、社会科学等各个领域.线性规划理论读发挥了巨大的历史性作用.
    
2    线性规划问题及其数学模型
2.1线性规划问题
线性规划问题就是在一组线性的等式或不等式的约束之下,求一个线性函数的最大值或最小值的问题。如下形式的问题叫作线性规划问题:
 
约束条件                            
 
 
 
这里, 称为目标函数,记为 ,其中 称为价值系数,  称为价值向量, 为求解的变量,由系数 组成的矩阵
 
称为约束矩阵,列向量 称为右端向量,条件 称为非负约束。本文中约束条件记为 一个向量 满足约束条件,称为可行解或可行点,所有可行点组成的集合称为可行区域,记为 .
对于一个 问题,下面三种情况必占其一:一是 ,这时我们说该问题无解或者不可行;二是 ,但目标函数在 上无界,这时就说该问题无界;三是 且目标函数有有限的最优解,这时就说该问题有最优解。求解 问题就是判断该问题属于哪一种情况,当问题有最优解时,还需要在可行区域中找出目标函数达到最小(或最大)的点,也就是最优解,以及目标函数的最优解。
   如果采用矩阵和向量的形式,则上述线性规划也可以表示成
 
 
 
记 ,其中   ,则上述问题也记为
 
 

最新论文

网站导航

热门论文