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