文档介绍：线性规划
Chapter 1 Linear Programming
本章内容提要
、线性规划的基本概念以及求解线性规划数学模型的基本算法——单纯形法.
学习本章要求掌握以下内容:
线性规划模型的结构
线性规划的标准形式,非标准形式转化为标准形式
:约束直线,可行半空间,可行解,可行域,凸集,极点,目标函数等值线,最优解
:基,基础解,基础可行解,基变量,非基变量,进基变量,离基变量,基变换
:基变量和目标函数用非基变量表出,检验数,选择进基变量的原则,确定离基变量的方法,主元,旋转运算
,单纯形表运算方法
初始基础可行解,两阶段法
退化的基础可行解
§ 运筹学和线性规划
运筹学
运筹学(Operations Research),英国组织了一批自然科学和工程科学的学者,和军队指挥员一起,、反潜艇作战研究等, Research,,这些研究方法不断发展完善,并逐步形成学科理论体系,其中一些主要的理论和方法包括:线性规划,网络流,整数规划,动态规划,非线性规划,排队论,决策分析,对策论,计算机模拟等
.这些理论和方法在经济管理领域也得到了广泛应用,Operations Research也转义成为“作业研究”.我国将Operations Research译成“运筹学”,非常贴切地将Operations Research这一英文术语所包含的作战研究和作业研究两方面的涵义都体现了出来.
现在,运筹学已经成为管理科学重要的基础理论和应用方法,是管理科学专业基本的必修课程之一.
线性规划
,应用领域十分广泛,包括生产计划,物资调运,资源优化配置,物料配方,任务分配,,目前用微型计算机就可以求解变量个数达106,约束个数达104的巨大规模的问题,并且计算时间也不太长.
线性规划问题最早是前苏联学者康德洛维奇(. Kantorovich)于1939年提出的,,美国空军的一个研究小组SCOOP(putation of Optimum Programs)在研究战时稀缺资源的最优化分配这一问题时,(),电子计算机研制成功,,线性规划和单纯形法受到数学家、经济学家和计算机工作者的重视,得到迅速发展,,美国国家标准局(NBS)、计算效率极高的线性规划软件MPS,,为线性规划的实际应用提供了强有力的工具.
在本章中,我们将介绍线性规划的基本概念,,可参阅有关文献及讲义后面的附录.
§ 线性规划问题
根据实际问题的要求,、.
生产计划问题
某工厂拥有A、B、C三种类型的设备,生产甲、乙、丙、,每件产品可以获得的利润以及三种设备可利用的时数如下表所示:
表 11
每件产品占用的
机时数(小时/件)
产品甲
产品乙
产品丙
产品丁
设备能力
(小时)
设备A

2000
设备B

8000
设备C

5000
利润(元/件)

用线性规划制订使总利润最大的生产计划.
设变量xi为第i种产品的生产件数(i=1,2,3,4),