第七章线性规划新.ppt

线性规划
线性规划简介
线性规划问题最早是前苏联学者康德洛维奇(. Kantorovich)于1939年提出的,但他的工作当时并未广为人知。
第二次世界大战中,美国空军的一个研究小组SCOOP(putation of Optimum Programs)在研究战时稀缺资源的最优化分配这一问题时,提出了线性规划问题。并且由丹泽()于1947年提出了求解线性规划问题的单纯形法。
50年代初,电子计算机研制成功,较大规模的线性规划问题的计算已经成为可能。因此,线性规划和单纯形法受到数学家、经济学家和计算机工作者的重视,得到迅速发展,很快发展成一门完整的学科并得到广泛的应用。
1952年,美国国家标准局(NBS)在当时的SEAC电子计算机上首次实现单纯形算法。
1976年IBM研制成功功能十分强大、计算效率极高的线性规划软件MPS,后来又发展成为更为完善的MPSX。这些软件的研制成功,为线性规划的实际应用提供了强有力的工具。
随着计算机硬件和软件技术的发展,目前用微型计算机就可以求解变量个数达106,约束个数达104的巨大规模的问题,并且计算时间也不太长。
线性规划问题
根据实际问题的要求,可以建立线性规划问题数学模型。线性规划问题由目标函数、约束条件以及变量的非负约束三部分组成。下面列举3种最常见的线性规划问题的类型。
生产计划问题
某工厂拥有A、B、C三种类型的设备,生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示:
每件产品占用的
机时数(小时/件)
产品甲
产品乙
产品丙
产品丁
设备能力
(小时)
设备A




2000
设备B




8000
设备C




5000
利润(元/件)




设变量xi为第i种产品的生产件数(i=1,2,3,4),目标函数z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下,可以建立如下的线性规划模型:
这是一个典型的利润最大化的生产计划问题。其中max表示极大化(maximize), to的缩写。求解这个线性规划,可以得到最优解为:
x1= x2=1500
x3=0 x4= (件)
最大利润为
z=(元)
背包问题
一只背包最大装载重量为50公斤。现有三种物品,每种物品数量无限。每种物品每件的重量、价值如下表所示:
物品1
物品2
物品3
重量(公斤/件)
10
41
20
价值(元/件)
17
72
35
要在背包中装入这三种物品各多少件,使背包中的物品价值最高。
设装入物品1,物品2和物品3各为x1,x2,x3件,由于物品的件数必须是整数,因此背包问题的线性规划模型是一个整数规划问题:
指派问题
有n项任务由n个人去完成,每项任务交给一个人,每个人都有一项任务。由第i个人去做第j项任务的成本(或效益)为cij。求使总成本最小(或效益最大)的分配方案。
例如,有张、王、李、赵4位教师被分配教语文、数学、物理、化学4门课程,每位教师教一门课程,每门课程由一位老师教。根据这四位教师以往教课的情况,他们分别教这四门课程的平均成绩如下表:
语文
数学
物理
化学
张
92
68
85
76
王
82
91
77
63
李
83
90
74
65
赵
93
61
83
75