运筹学-线性规划

《运筹学-线性规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第1章线性规划Chapter1LinearProgramming本章内容提要线性规划是运筹学的重要内容。本章介绍线性规划数学模型、线性规划的基本概念以及求解线性规划数学模型的基本算法一一单纯形法。学习本章要求掌握以下内容：■线性规划模型的结构■线性规划的标准形式，非标准形式转化为标准形式■线性规划的图解以及相应的概念。包括：约束直线，可行半空间，可行解,可行域，凸集，极点，目标函数等值线，最优解■线性规划的基本概念。包括：基，基础解，基础可行解，基变量，非基变量，进基变量，离基变量，基变换■单纯形法原理。包括：基变量和目标函数用非基变量表出，检验数，选择进基变量的原则，确定离

2、基变量的方法，主元，旋转运算■单纯形表。包括初始单纯形表的构成，单纯形表运算方法■初始基础可行解，两阶段法■退化的基础可行解§1.1运筹学和线性规划l.i.i运筹学运筹学(OperationsResearch)是二十世纪三十年代二次大战期间由于战争的需要发展起来的一门学科。当时，英国组织了一批自然科学和工程科学的学者，和军队指挥员一起，研究大规模战争提出的一些问题。如轰炸战术的评价和改进、反潜艇作战研究等，研究结果在战争实践中取得了明显得效果。这些研究当时在英国称为0perationalResearch,直译为作战研究。战争结束以后，这些研究方法不断发展完善，并逐步形成学科理

3、论体系，其中一些主要的理论和方法包括：线性规划，网络流，整数规划，动态规划，非线性规划，排队论，决策分析，对策论，计算机模拟等。这些理论和方法在经济管理领域也得到了广泛应用，OperationsResearch也转义成为“作业研究”。我国将OperationsResearch译成“运筹学”，非常贴切地将OperationsResearch这一英文术语所包含的作战研究和作业研允两方而的涵义都体现了出来。现在，运筹学己经成为管理科学重耍的基础理论和应用方法，是管理科学专业基本的必修课程之一。1.1.2线性规划线性规划是运筹学中最重要的一种系统优化方法。它的理论和算法已十分成熟,应

4、用领域十分广泛，包括-生产计划，物资调运，资源优化配置，物料配方，任务分配，经济规划等问题。随着计算机硬件和软件技术的发展，IT前用微型计算机就可以求解变量个数达1(A约束个数达IO"的巨大规模的问题，并且计算时间也不太长。线性规划问题最早是前苏联学者康德洛维奇(L.V.Kantorovich)T*1939年提出的，但他的工作当时并未广为人知。第二次世界大战中，美国空军的一个研究小组SCOOP(ScientificComputationofOptimumPrograms)在研允战时稀缺资源的最优化分配这一问题时，提出了线性规划问题。并且由丹泽(GB.Dantzig)于1947

5、年提出了求解线性规划问题的单纯形法。单纯形法至今述是求解线性规划最有效的方法。50年代初，电子计算机研制成功，较大规模的线性规划问题的计算己经成为可能。因此，线性规划和单纯形法受到数学家、经济学家和计算机工作者的重视，得到迅速发展，很快发展成一门完整的学科并得到广泛的应用。1952年，美国国家标准局(NBS)在当时的SEAC电子计算机上首次实现单纯形算法。1976年IBM研制成功功能十分强大、计算效率极高的线性规划软件MPS,后来又发展成为更为完善的MPSXo这些软件的研制成功，为线性规划的实际应用提供了强有力的工具。在本章中，我们将介绍线性规划的基本概念，单纯形法的基本原理

6、及线性规划在经济分析中的应用。对计算方法和计算机软件应用方面的问题，可参阅有关文献及讲义后面的附录。§1.2线性规划问题根据实际问题的要求，可以建立线性规划问题数学模型。线性规划问题由目标函数、约束条件以及变量的非负约束三部分组成。下面列举五种最常见的线性规划问题的类型。1.2.1生产计划问题例1・1某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：表1-1每件产品占用的机时数（小时/件）产品甲产品乙产品内产品丁设备能力（小时）设备A1.51.02.41.02000设

7、备B5.01.03.5800()设备C1.53.03.51.0500()利润（元/件）5.247.308.344.18用线性规划制订使总利润最大的生产计划。设变量冶为第i种产品的生产件数（i=l,2,3,4）,目标函数z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型：maxz=5.24xi+7.30x2+8.34x3+4.18x4忖标函数s.t.1.5xi+1.0X2+2.4X3+1.0X4W20001.0X[+5.0x2+1.OX3+3.5