文档介绍：第1章线性规划Chapter1LinearProgramming本章内容提要线性规划是运筹学的重要内容。本章介绍线性规划数学模型、线性规划的基本概念以及求解线性规划数学模型的基本算法——单纯形法。学习本章耍求掌握以下内容:■线性规划模型的结构■线性规划的标准形式,非标准形式转化为标准形式■线性规划的图解以及相应的概念。包括:约束直线,可行半空间,可行解,可行域,凸集,极点,ri标函数等值线,最优解线性规划的基本概念。包括:基,基础解,基础可行解,基变量,非基变量,进基变量,离基变量,基变换单纯形法原理。包括:基变量和目标函数用非基变屋表出,检验数,选择进基变量的原则,确定离基变量的方法,主元,旋转运算单纯形表。包括初始单纯形表的构成,单纯形表运算方法初始基础可行解,两阶段法退化的基础可行解§(OperationsResearch)是二I•世纪三十年代二次大战期间由于战争的盂要发展起来的一门学科。当时,英国组织了一批自然科学和工程科学的学者,和军队指挥员一起,研究大规模战争提出的一些问题。如轰炸战术的评价和改进、反潜艇作战研究等,研究结果在战争实践中取得了明显得效果。这些研究当时在英国称为0pcrationalResearch,直译为作战研究。战争结束以后,这些研究方法不断发展完善,并逐步形成学科理论体系,其中一些主要的理论和方法包括:线性规划,网络流,整数规划,动态规划,非线性规划,排队论,决策分析,对策论,计算机模拟等。这些理论和方法在经济管理领域也得到了广泛应用,OperationsResearch也转义成为“作业研究”。我国将OperationsResearch译成“运筹学”,非常贴切地将OperationsResearch这一英文术语所包含的作战研究和作业研究两方而的涵义都体现了出来。现在,运筹学已经成为管理科学重要的基础理论和应用方法,是管理科学专业基本的必修课程Z-。它的理论和算法已十分成熟,应用领域十分广泛,包括生产计划,物资调运,资源优化配置,物料配方,任务分配,经济规划等问题。随着计算机硬件和软件技术的发展,冃前用微型计算机就町以求解变量个数达1(A约束个数达104的巨大规模的问题,并且计算时间也不太长。线性规划问题最早是前苏联学者康德洛维奇()J'*1939年提出的,但他的工作当时并未广为人知。第二次世界大战中,美国空军的一个研究小组SCOOP(putationofOptimumPrograms)在研究战时稀缺资源的最优化分配这一问题时,提出了线性规划问题。并且由丹泽()于1947年提出了求解线性规划问题的单纯形法。单纯形法至今还是求解线性规划最有效的方法。50年代初,电子计算机研制成功,较大规模的线性规划问题的计算已经成为町能。因此,线性规划和单纯形法受到数学家、经济学家和计算机工作者的重视,得到迅速发展,很快发展成一门完整的学科并得到广泛的应用。1952年,美国国家标准局(NBS)在当时的SEAC电子计算机上首次实现单纯形算法。1976年IBM研制成功功能十分强大、计算效率极高的线性规划软件MPS,后来又发展成为更为完善的MPSXO这些软件的研制成功,为线性规划的实际应用提供了强有力的工具。在本章中,我们将介绍线性规划的基本概念,单纯形法的基本原理及线性规划在经济分析中的应用。对计算方法和计算机软件应用方面的问题,可参阅有关文献及讲义后面的附录。§,对以建立线性规划问题数学模型。线性规划问题市口标函数、约束条件以及变量的非负约束三部分组成。卜•面列举五种最常见的线性规划问题的类型。・1某工厂拥有A、B、C三种类型的设备,生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如卜•表所示:表1-1每件产品占川的机时数(小时/件)产品甲产品乙产品丙产品丁设备能力(小时).().()2000设备B5.()1.()().().()500()利润(元/件)」8用线性规划制订使总利润最大的仝产计划。设变量冷为笫i种产品的生产件数(i=l,2,3,4),目标函数z为相应的生产计划可以获得的总利润。在加工吋间以及利润与产晶产量成线性关系的假设下,可以建立如下的线性规划模型:maxz=5・24xi+++. ++24X3++++