运筹学-1、线性规划

《运筹学-1、线性规划》由会员分享，可在线阅读，更多相关《运筹学-1、线性规划（191页珍藏版）》请在文档大全上搜索。

1、1运筹学运筹学Operations Research2 运筹学运筹学是一门应用科学是一门应用科学 ，它广泛应用现有的，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据门问题，为决策者选择最优决策提供定量依据。 运筹学作为一门新兴的学科是在第二次世界大运筹学作为一门新兴的学科是在第二次世界大战期间出现的战期间出现的 。当时英美成立了名为当时英美成立了名为“运作研究运作研究” ( Oprtational Research)小组，通过科学方法的运用小组，通过科学方法的运用成功地解决了许多非常复杂的战略和战术问

2、题。成功地解决了许多非常复杂的战略和战术问题。3 例如如何合理运用雷达有效地对付德国空袭；例如如何合理运用雷达有效地对付德国空袭；对商船队如何进行编队护航，在船队遭受德国潜艇对商船队如何进行编队护航，在船队遭受德国潜艇攻击时使船队损失最少；反潜深水炸弹在各种情况攻击时使船队损失最少；反潜深水炸弹在各种情况下如何调整其爆炸深度，才能增加对德国潜艇的杀下如何调整其爆炸深度，才能增加对德国潜艇的杀伤力等伤力等 ；军队营养物质供应问题。；军队营养物质供应问题。 运筹学课程的一般内容有：运筹学课程的一般内容有：线性规划、整数规线性规划、整数规划、非线性规划、动态规划、图与网络分析、排队划、非线性规划、动

3、态规划、图与网络分析、排队论、对策论、存贮论、决策论等。论、对策论、存贮论、决策论等。4线性规划线性规划56 例例1: :( (生产计划问题生产计划问题) )某工厂生产某工厂生产 I I、IIII 两种产两种产品品。每件产品的单位利润，所消耗的两种材料数、每件产品的单位利润，所消耗的两种材料数、设备工时及这两种材料、设备工时的限额如下表：设备工时及这两种材料、设备工时的限额如下表： I IIIII资源限量资源限量 设备设备材料材料A A材料材料B B1402048台时台时16kg12kg 利润利润23712121212max2328416.412,0Zxxxxxstxx x解：解：设设 x1、

4、x2分别表示两种产品的产量，那么该问分别表示两种产品的产量，那么该问题的数学模型可以表示为：题的数学模型可以表示为：8第第i 种资源的拥有量为种资源的拥有量为bi ;i=1,2,m ,生产一个单位第生产一个单位第j种产品需要消耗第种产品需要消耗第i 种资源的数量为种资源的数量为aij;第第j种产品的利润（单价种产品的利润（单价,产值）为产值）为cj 。j =1,2,n。上述问题推广到一般情况：上述问题推广到一般情况：有有m种不同资源（例如原材料，动力资源，资金，劳力种不同资源（例如原材料，动力资源，资金，劳力等）可以用来生产等）可以用来生产n种不同产品。假设有关的数据为：种不同产品。假设有关的

5、数据为：设设x1、x2、xn 分别表示分别表示n种产品的产量，则其数种产品的产量，则其数学模型为：学模型为：91 12211 11221121 1222221 12212max.,0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xbsta xaxaxbx xx10 例例2： (配料问题配料问题) 一饲养场饲养动物出售，每只一饲养场饲养动物出售，每只动物每天至少需要动物每天至少需要700克蛋白质克蛋白质， 30克矿物质，克矿物质，100毫克维生素。现有四种饲料可供选用，各种饲料每公毫克维生素。现有四种饲料可供选用，各种饲料每公斤营养成分含量及单价如下表所示；斤

6、营养成分含量及单价如下表所示； 饲料饲料营养成分营养成分 需要量需要量蛋白质蛋白质3 2 1 5700克克矿物质矿物质1 0.5 0.2 230克克维生素维生素0.5 1 0.3 2.5100毫克毫克单价单价(元元/公公斤斤)0.8 1.2 0.6 2 四种饲料各采购多少，才能使总费用最小？四种饲料各采购多少，才能使总费用最小？11 解：解：设设 x1、x2、 x3、 x4分别表示四种饲料的采分别表示四种饲料的采购量，那么该问题的数学模型可以表示为：购量，那么该问题的数学模型可以表示为：12341234123412341234min0.81.20.623257000.50.2230.0.50.

7、32.5100,0Zxxxxxxxxxxxxstxxxxx x x x12上述模型推广到一般情况为：上述模型推广到一般情况为：每只动物每天至少需要每只动物每天至少需要有有m种不同种不同营养成分营养成分bi；有有n种饲料可供选用，每公斤种饲料可供选用，每公斤第第j种种饲料所含饲料所含第第i种种营营养成分量为养成分量为aij;第第j种种饲料的单价饲料的单价为为cj 。i=1,2,m， j=1,2,n。设设x1、x2、xn 分别表示分别表示n种种饲料饲料的采购量，则其的采购量，则其数学模型为：数学模型为：如何采购才能使总费用最小？如何采购才能使总费用最小？131 12211 11221121 122

8、2221 12212min.,0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xbsta xaxaxbx xx14 例例3：（运输问题）运输问题）设有两个砖厂设有两个砖厂A1 、A2 ，产，产量分别为量分别为23万块、万块、27万块，现将其产品联合供应三万块，现将其产品联合供应三个施工现场个施工现场B1 、 B2 、 B3 ，其需要量分别为，其需要量分别为17万万块、块、18万块、万块、15万块。各产地到各施工现场的单位万块。各产地到各施工现场的单位运价如下表：运价如下表：问如何调运才能使总运费最省？问如何调运才能使总运费最省？ 现场现场砖厂砖厂 B1 B2

9、 B3A15147A2618915解：解：设设xijij表示从砖厂表示从砖厂A Ai运往现场运往现场B Bj j的数量的数量 ( (i=1=1，2;j=1,22;j=1,2，3),3),则其数学模型如下：则其数学模型如下：111213212223111213212223112112221323min51476189232717.18150(1,2,1,2,3)ijZxxxxxxxxxxxxxxstxxxxxij1617 1 12211 11221121 1222221 12212max(min).( , ).( , ).( , ),.,0nnnnnnmmmnnmnZc xc xc xa xa

10、xa xba xa xa xba xaxaxbx xx 18 例例4： （投资问题（投资问题 ） 某投资公司在第一年初有某投资公司在第一年初有100万元资金，每年都有如下的投资方案可供考虑采万元资金，每年都有如下的投资方案可供考虑采纳：纳：“假使第一年投入一笔资金，第二年又继续投入假使第一年投入一笔资金，第二年又继续投入此资金的此资金的50%，那么到第三年就可回收第一年投入资，那么到第三年就可回收第一年投入资金的两倍金额金的两倍金额” 。投资公司要设法决定最优的投资策。投资公司要设法决定最优的投资策略使第六年所掌握的资金最多。略使第六年所掌握的资金最多。解：解：设设x1为第一年的投资为第一年的

11、投资; x2为为 第一年的保留资金；第一年的保留资金；100 ：21 xx则设设x3为第二年新的投资；为第二年新的投资； x4为第二年的保留资金；为第二年的保留资金；2431)2( ：xxxx则19设x5为第三年新的投资；为第三年新的投资；x6为第三年的保留资金；为第三年的保留资金；146532)2( ：xxxxx则368752)2( ：xxxxx则设设x7为第四年新的投资；第四年的保留资金为为第四年新的投资；第四年的保留资金为x8；设设x9为第五年的保留资金：第五年不再进行新的投资，因为第五年的保留资金：第五年不再进行新的投资，因为这笔投资要到第七年才能回收。为这笔投资要到第七年才能回收。