《线性规划新》PPT课件.ppt

《《线性规划新》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划线性规划简介线性规划问题最早是前苏联学者康德洛维奇（L.V.Kantorovich）于1939年提出的，但他的工作当时并未广为人知。第二次世界大战中，美国空军的一个研究小组SCOOP（ScientificComputationofOptimumPrograms）在研究战时稀缺资源的最优化分配这一问题时，提出了线性规划问题。并且由丹泽（G.B.Dantzig）于1947年提出了求解线性规划问题的单纯形法。50年代初，电子计算机研制成功，较大规模的线性规划问题的计算已经成为可能。因此，线性规划和

2、单纯形法受到数学家、经济学家和计算机工作者的重视，得到迅速发展，很快发展成一门完整的学科并得到广泛的应用。1952年，美国国家标准局（NBS）在当时的SEAC电子计算机上首次实现单纯形算法。1976年IBM研制成功功能十分强大、计算效率极高的线性规划软件MPS，后来又发展成为更为完善的MPSX。这些软件的研制成功，为线性规划的实际应用提供了强有力的工具。随着计算机硬件和软件技术的发展，目前用微型计算机就可以求解变量个数达106，约束个数达104的巨大规模的问题，并且计算时间也不太长。线性规划问题根据

3、实际问题的要求，可以建立线性规划问题数学模型。线性规划问题由目标函数、约束条件以及变量的非负约束三部分组成。下面列举3种最常见的线性规划问题的类型。生产计划问题例1.1某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：每件产品占用的机时数（小时/件）产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.

4、05000利润（元/件）5.247.308.344.18设变量xi为第i种产品的生产件数（i＝1，2，3，4），目标函数z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型：这是一个典型的利润最大化的生产计划问题。其中max表示极大化（maximize），s.t.是subjectto的缩写。求解这个线性规划，可以得到最优解为：x1=294.12x2=1500x3=0x4=58.82（件）最大利润为z=12737.06（元）背包问题例1.2一只

5、背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：物品1物品2物品3重量（公斤/件）104120价值（元/件）177235要在背包中装入这三种物品各多少件，使背包中的物品价值最高。设装入物品1，物品2和物品3各为x1，x2，x3件，由于物品的件数必须是整数，因此背包问题的线性规划模型是一个整数规划问题：指派问题例1.3有n项任务由n个人去完成，每项任务交给一个人，每个人都有一项任务。由第i个人去做第j项任务的成本（或效益）为cij。求使总成本最小（或效益

6、最大）的分配方案。例如，有张、王、李、赵4位教师被分配教语文、数学、物理、化学4门课程，每位教师教一门课程，每门课程由一位老师教。根据这四位教师以往教课的情况，他们分别教这四门课程的平均成绩如下表：语文数学物理化学张92688576王82917763李83907465赵93618375四位教师每人只能教一门课，每一门课只能由一个教师来教。要确定哪一位教师上哪一门课，使四门课的平均成绩之和为最高。设xij（i=1,2,3,4；j=1,2,3,4）为第i个教师是否教第j门课，xij只能取值0或1，其意义

7、如下：变量xij与教师i以及课程j的关系如下：ij语文数学物理化学张x11x12x13x14王x21x22x23x24李x31x32x33x34赵x41x42x43x44maxz=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90x32+74x33+65x34+93x41+61x42+83x43+75x44s.t.x11+x12+x13+x14=1（1）x21+x22+x23+x24=1（2）x31+x32+x33+x34=1（3）x41

8、+x42+x43+x44=1（4）x11+x21+x31+x41=1（5）x12+x22+x32+x42=1（6）x13+x23+x33+x43=1（7）x14+x24+x34+x44=1（8）xij=0,1这个问题的变量只能取值0或1，这样的线性规划问题成为0－1规划。一般的指派问题线性规划模型如下：设：得到以下的线性规划模型：由以上3个例子，我们可以归纳出线性规划问题的一般形式：非线性规划简介规划问题：在约束条件下求目标函数的最优值点。规划问题包含3个组成要素:决