第七章线性规划新.ppt

线性规划线性规划简介线性规划问题最早是前苏联学者康德洛维奇( . Kantorovich )于 1939 年提出的,但他的工作当时并未广为人知。第二次世界大战中,美国空军的一个研究小组 SCOOP ( Scientific Computation of Optimum Programs )在研究战时稀缺资源的最优化分配这一问题时,提出了线性规划问题。并且由丹泽( )于 1947 年提出了求解线性规划问题的单纯形法。 50 年代初,电子计算机研制成功,较大规模的线性规划问题的计算已经成为可能。因此,线性规划和单纯形法受到数学家、经济学家和计算机工作者的重视,得到迅速发展,很快发展成一门完整的学科并得到广泛的应用。 1952 年,美国国家标准局( NBS )在当时的 SEAC 电子计算机上首次实现单纯形算法。 1976 年 IBM 研制成功功能十分强大、计算效率极高的线性规划软件 MPS ,后来又发展成为更为完善的 MPSX 。这些软件的研制成功,为线性规划的实际应用提供了强有力的工具。随着计算机硬件和软件技术的发展,目前用微型计算机就可以求解变量个数达 106 ,约束个数达 104 的巨大规模的问题,并且计算时间也不太长。线性规划问题根据实际问题的要求,可以建立线性规划问题数学模型。线性规划问题由目标函数、约束条件以及变量的非负约束三部分组成。下面列举 3种最常见的线性规划问题的类型。生产计划问题?例 某工厂拥有 A、B、C三种类型的设备, 生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示: 利润(元/件) 5000 设备 C 8000 设备 B 2000 设备 A 设备能力(小时) 产品丁产品丙产品乙产品甲每件产品占用的机时数(小时/件) 设变量 xi为第 i种产品的生产件数( i=1,2,3,4), 目标函数 z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下,可以建立如下的线性规划模型: 这是一个典型的利润最大化的生产计划问题。其中 max 表示极大化( maximize ), .是 subject to的缩写。求解这个线性规划,可以得到最优解为: x1= x2=1500 x3=0 x4= (件) 最大利润为 z= (元) 背包问题例 一只背包最大装载重量为 50 公斤。现有三种物品, 每种物品数量无限。每种物品每件的重量、价值如下表所示: 35 72 17 价值(元/件) 20 41 10 重量(公斤/件) 物品 3物品 2物品 1 要在背包中装入这三种物品各多少件,使背包中的物品价值最高。设装入物品 1,物品 2和物品 3各为 x1 ,x2 ,x3 件,由于物品的件数必须是整数,因此背包问题的线性规划模型是一个整数规划问题: 指派问题例 有n项任务由 n个人去完成,每项任务交给一个人,每个人都有一项任务。由第 i个人去做第 j项任务的成本(或效益)为 cij。求使总成本最小(或效益最大)的分配方案。例如,有张、王、李、赵 4位教师被分配教语文、数学、物理、化学 4门课程,每位教师教一门课程, 每门课程由一位老师教。根据这四位教师以往教课的情况,他们分别教这四门课程的平均成绩如下表: 75 83 61 93 赵 65 74 90 83 李 63 77 91 82 王 76 85 68 92 张化学物理数学语文