运筹学第二章续.ppt

《运筹学第二章续.ppt》由会员分享，可在线阅读，更多相关《运筹学第二章续.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3.4 3.4 线性规划的应用线性规划的应用一、人力资源安排的问题一、人力资源安排的问题 例例1 1某昼夜服务的公交线路每天各时间段内所需司某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：机和乘务人员数如下：设司机和乘务人员分别在各时间段一起先时上班，并设司机和乘务人员分别在各时间段一起先时上班，并连续工作八小时，问该公交线路怎样支配司机和乘务连续工作八小时，问该公交线路怎样支配司机和乘务人员，既能满足工作须要，又配备最少司机和乘务人人员，既能满足工作须要，又配备最少司机和乘务人员员?解：设解：设 xi xi 表示第表示第i i班次时起先上班的司班次时起先上班的司机和乘务人员数机和

2、乘务人员数,这样我们建立如下的数这样我们建立如下的数学模型。学模型。Min Z=x1+x2+x3+x4+Min Z=x1+x2+x3+x4+x5+x6 x5+x6 s.t.x1+x6 60 s.t.x1+x6 60 x1+x2 70 x1+x2 70 x2+x3 60 x2+x3 60 x3+x4 50 x3+x4 50 x4+x5 20 x4+x5 20 x5+x6 30 x5+x6 30 x1,x2,x3,x4,x5,x6 0 x1,x2,x3,x4,x5,x6 0例例2 2某商场是个中型的百货商场，它对售货员的某商场是个中型的百货商场，它对售货员的需求经过统计分析如下表，为了保证售货人员

3、充需求经过统计分析如下表，为了保证售货人员充分休息，售货人员每周工作分休息，售货人员每周工作 5 5 天，休息两天，并天，休息两天，并要求休息的两天是连续的。问应当如何支配售货要求休息的两天是连续的。问应当如何支配售货人员的作息，既满足工作须要，又使配备的售货人员的作息，既满足工作须要，又使配备的售货人员的人数最少？人员的人数最少？解：设解：设 xi(i=1-7)xi(i=1-7)表示星期一至日起先休息表示星期一至日起先休息的人数的人数,这样我们建立如下的数学模型。这样我们建立如下的数学模型。Min Z=x1+x2+x3+x4+x5+x6+x7 Min Z=x1+x2+x3+x4+x5+x6+

4、x7 s.t.x1+x2+x3+x4+x5 28s.t.x1+x2+x3+x4+x5 28 x2+x3+x4+x5+x6 15 x2+x3+x4+x5+x6 15 x3+x4+x5+x6+x7 24 x3+x4+x5+x6+x7 24 x4+x5+x6+x7+x1 25 x4+x5+x6+x7+x1 25 x5+x6+x7+x1+x2 19 x5+x6+x7+x1+x2 19 x6+x7+x1+x2+x3 31 x6+x7+x1+x2+x3 31 x7+x1+x2+x3+x4 28 x7+x1+x2+x3+x4 28 x1,x2,x3,x4,x5,x6,x7 0 x1,x2,x3,x4,x5,

5、x6,x7 0二、生产支配的问题二、生产支配的问题 例例3 3明兴公司生产甲、乙、丙三种产品，都须要明兴公司生产甲、乙、丙三种产品，都须要经过铸造、机加工和装配三个车间。甲、乙两种产品经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必的铸件可以外包协作，亦可以自行生产，但产品丙必需本厂铸造才能保证质量。数据如下表。问：公司为需本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包？甲、乙两种产品的铸造中，由本公司铸造和由外包协

6、作各应多少件？协作各应多少件？解：设解：设 x x1 1,x x2 2,x x3 3 分别为三道工序都由本公司加工的分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，甲、乙、丙三种产品的件数，x x4 4,x x5 5 分别为由外协铸分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。造再由本公司加工和装配的甲、乙两种产品的件数。Max Z=15Max Z=15x x1 1+10+10 x x2 2+7+7x x3 3+13+13x x4 4+9+9x x5 5 s.t.5 s.t.5x x1 1+10+10 x x2 2+7+7x x3 3 8000 8000 6 6x x1

7、1+4+4x x2 2+8+8x x3 3+6+6x x4 4+4+4x x5 5 12000 12000 3 3x x1 1+2+2x x2 2+2+2x x3 3+3+3x x4 4+2+2x x5 5 10000 10000 x x1 1,x x2 2,x x3 3,x x4 4,x x5 5 0 0 例4某厂生产、三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成 A 工序；有三种规格的设备B1、B2、B3能完成 B 工序。可在A、B的任何规格的设备上加工；可在随意规格的A设备上加工，但对B工序，只能在B1设备上加工；只能在A2与B2设备上加工；数据如下表。问：为

8、使该厂获得最大利润，应如何制定产品加工方案？产品有2种加工方案，即 ，加工数量用 表示；产品只有一种加工方案，加工数量等于 。则建立如下线性规划模型Max Z=(1.25-0.25)+(2.0-0.35)+(2.80-0.50)s.t.三、合理下料问题三、合理下料问题 例例5 5某工厂要做某工厂要做100100套钢架，每套套钢架，每套钢架用长为钢架用长为2.9 m,2.1 m,1.5 m2.9 m,2.1 m,1.5 m的圆钢的圆钢各一根。已知原料每根长各一根。已知原料每根长7.4 m7.4 m，现考，现考虑应如何下料，可使所用原料最省？虑应如何下料，可使所用原料最省？解：设计下列解：设计下列

9、8 8种下料方案种下料方案方案方案1 1方案方案2 2方案方案3 3方案方案4 4方案方案5 5方案方案6 6方案方案7 7方案方案8 82.92.92 21 11 11 10 00 00 00 02.12.10 02 21 10 03 32 21 10 01.5 1.5 1 10 01 13 30 02 23 34 4合计合计7.37.37.17.16.56.57.47.46.36.37.27.26.66.66.06.0剩余料头剩余料头0.10.10.30.30.90.90 01.11.10.20.20.80.81.41.4 例例6 6：某医院有一批长度为：某医院有一批长度为1515分米的胶

10、皮管原分米的胶皮管原料。为了作输液管、止血带和听诊器胶管，须要料。为了作输液管、止血带和听诊器胶管，须要截成长度分别为截成长度分别为5.75.7分米，分米，4.24.2分米和分米和3.13.1分米的短分米的短管各管各100100根，根，100100根和根和200200根。试问应如何支配截发，根。试问应如何支配截发，所用的胶管原材的总根数最少，而且每根料头不所用的胶管原材的总根数最少，而且每根料头不能超过能超过2 2分米？分米？四、配料问题四、配料问题 例例7 7某工厂要用三种原料某工厂要用三种原料1 1、2 2、3 3混合调混合调配出三种不同规格的产品甲、乙、丙，数据配出三种不同规格的产品甲、

11、乙、丙，数据如右表。问：该厂应如何支配生产，使利润如右表。问：该厂应如何支配生产，使利润收入为最大？收入为最大？解：设解：设 x xijij 表示第表示第 i i 种（甲、乙、丙）产品中原料种（甲、乙、丙）产品中原料 j j 的含量。这样我们建立数学模型时，要考虑：的含量。这样我们建立数学模型时，要考虑：对于甲：对于甲：x x1111，x x1212，x x1313；对于乙：对于乙：x x2121，x x2222，x x2323；对于丙：对于丙：x x3131，x x3232，x x3333；对于原料对于原料1 1：x x1111，x x2121，x x3131；对于原料对于原料2 2：x x

12、1212，x x2222，x x3232；对于原料对于原料3 3：x x1313，x x2323，x x3333；目标函数：目标函数：利润最大，利润利润最大，利润 =收入收入 -原料支出原料支出 约束条件：约束条件：规格要求规格要求 4 4 个；个；供应量限制供应量限制 3 3 个。个。目标函数：目标函数：Max z=-15Max z=-15x x1111+25+25x x1212+15+15x x1313-30-30 x x2121+10+10 x x2222-40-40 x x3131-10-10 x x3333 约束条件：约束条件：s.t.0.5 s.t.0.5 x x1111-0.5-

13、0.5 x x12 12-0.5-0.5 x x1313 0 0（原材料（原材料1 1不少于不少于50%50%）-0.25-0.25x x1111+0.75+0.75x x1212-0.25-0.25x x1313 0 0（原材料（原材料2 2不超过不超过25%25%）0.750.75x x2121-0.25-0.25x x2222-0.25-0.25x x2323 0 0（原材料（原材料1 1不少于不少于25%25%）-0.5-0.5 x x2121+0.5+0.5 x x2222-0.5 -0.5 x x2323 0 0（原材料（原材料2 2不超过不超过50%50%）x x1111+x x

14、2121+x x3131 100 (100 (供应量限制）供应量限制）x x1212+x x2222+x x3232 100 (100 (供应量限制）供应量限制）x x1313+x x2323+x x3333 60 (60 (供应量限制）供应量限制）x xijij 0 ,i=1,2,3;j=1,2,3 0 ,i=1,2,3;j=1,2,3 例例8.8.某糖果厂用原料某糖果厂用原料A A，B B，C C加工成三种不同牌加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中号的糖果甲、乙、丙。已知各种牌号糖果中A A，B B，C C的含量，原料成本，各种原料每月的限制用量，三的含量，原料成本，各种

15、原料每月的限制用量，三种牌号糖果的单位加工费及售价如表所示。种牌号糖果的单位加工费及售价如表所示。甲甲 乙乙 丙丙原料成本原料成本/元元/KG每月限制用量每月限制用量/KGABC60%15%20%50%60%2.001.501.00200025001200加工加工费费（元（元/kg）0.50 0.40 0.30售价（元售价（元/kg）3.40 2.85 2.25问该厂每月生产这三种牌号各多少问该厂每月生产这三种牌号各多少kgkg，使得到的利，使得到的利润为最大？试建立这个问题的线性规划数学模型。润为最大？试建立这个问题的线性规划数学模型。五、投资问题 例9某部门现有资金200万元，今后五年内考

16、虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利 110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利 140%，但规定最大投资额不能超过80万元；项目D：需在其次年年初投资，第五年末能收回本利 155%，但规定最大投资额不能超过100万元；问：a）应如何确定这些项目的每年投资额，使得第五 年年末拥有资金的本利金额为最大？据测定每万元每次投资的风险指数为：据测定每万元每次投资的风险指数为：项目项目 A A 为为 1 1，项目，项目 B B 为为 3

17、3，项目项目 C C 为为 4 4，项目，项目 D D 为为 5.55.5b b）应如何确定这些项目的每年投资额，使应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在得第五年年末拥有资金的本利在 330 330 万元万元的基础上使得其投资总的风险系数为最小的基础上使得其投资总的风险系数为最小？解：确定决策变量：连续投资问题解：确定决策变量：连续投资问题 设设 x xij ij(i=1-5(i=1-5，j=1j=1、2 2、3 3、4)4)表示第表示第 i i 年初投资于年初投资于A(j=1)A(j=1)、B(j=2)B(j=2)、C(j=3)C(j=3)、D(j=4)D(j=4)项

18、目的金额。项目的金额。a)Max z=1.1a)Max z=1.1x x5151+1.25+1.25x x4242+1.4+1.4x x33 33+1.55+1.55x x24 24 s.t.s.t.x x1111+x x12 12=200=200 x x21 21+x x2222+x x2424=1.1=1.1x x1111；x x31 31+x x3232+x x3333=1.1=1.1x x2121+1.25+1.25x x1212；x x41 41+x x4242=1.1=1.1x x3131+1.25+1.25x x2222；x x51 51=1.1=1.1x x4141+1.25+

19、1.25x x3232；x xi2 i2 30(I=1 30(I=1、2 2、3 3、4)4)，x x3333 80 80，x x2424 100 100 x xijij 0 (i=1 0 (i=1、2 2、3 3、4 4、5 5；j=1j=1、2 2、3 3、4 4）b)Min f=(b)Min f=(x x1111+x x2121+x x3131+x x4141+x x5151)+3()+3(x x1212+x x2222+x x3232+x x4242)+4)+4x x3333+5.5+5.5x x24 24 s.t.s.t.x x1111+x x12 12=200=200 x x21

20、21+x x2222+x x2424 1.11.1x x1111；x x31 31+x x3232+x x3333 1.1 1.1x x2121+1.25+1.25x x1212；x x41 41+x x4242 1.1 1.1x x3131+1.25+1.25x x2222；x x51 51 1.1 1.1x x4141+1.25+1.25x x3232；x xi2 i2 30(I=1 30(I=1、2 2、3 3、4)4)，x x3333 80 80，x x2424 100 100 1.1 1.1x x51 51+1.25+1.25x x4242+1.4+1.4x x3333+1.55+1

21、.55x x2424 330 330 x xijij 0 (i=1 0 (i=1、2 2、3 3、4 4、5 5；j=1j=1、2 2、3 3、4 4）例例10.10.某人有一笔某人有一笔3030万元的资金，在今后的三年内有以下万元的资金，在今后的三年内有以下投资项目：投资项目：（1 1）三年内的每年年初均可投资，每年获利为投资额的）三年内的每年年初均可投资，每年获利为投资额的20%20%，其本利可一起用于下一年的投资；，其本利可一起用于下一年的投资；（2 2）只允许第一年年初投入，其次年末可收回，本利合计）只允许第一年年初投入，其次年末可收回，本利合计为投资额的为投资额的150%150%，但

22、此类投资额不超过，但此类投资额不超过1515万元；万元；（3 3）于三年内其次年初允许投资，可于第三年末收回，本）于三年内其次年初允许投资，可于第三年末收回，本利合计为投资额的利合计为投资额的160%160%，这类投资限额，这类投资限额2020万元；万元；（4 4）于三年内的第三年初允许投资，一年回收，可获利）于三年内的第三年初允许投资，一年回收，可获利40%40%，投资限额为，投资限额为1010万元。万元。试为该人确定一个使第三年末本利和为最大的投资支配。试为该人确定一个使第三年末本利和为最大的投资支配。解：设为第年初投放到项目的资金数，其数学模型为六、生产存储问题六、生产存储问题例例11：

23、某厂签订了：某厂签订了5种产品（种产品（i=1,5)上半年的上半年的交货合同。已知各产品在第交货合同。已知各产品在第j月（月（j=1,6)的合的合同交货量同交货量 该月售价该月售价 、成本价、成本价 及生产一件及生产一件时所需工时时所需工时 。该厂第。该厂第 j 月的正常生产工时为月的正常生产工时为 ，但必要时可加班生产，第，但必要时可加班生产，第j月允许得最多加班工月允许得最多加班工时不超过时不超过 ，并且加班时间内生产出来的产品每，并且加班时间内生产出来的产品每件成本增加额外费用件成本增加额外费用 元。若生产出来的产品元。若生产出来的产品当月不交货，每件库存当月不交货，每件库存1个月交存贮

24、费个月交存贮费 元。试元。试为该厂设计一个保证完成合同交货，又使上半年为该厂设计一个保证完成合同交货，又使上半年预期盈利总额为最大的生产支配支配。预期盈利总额为最大的生产支配支配。其次章学习要求其次章学习要求一、熟悉线性规划的模型结构一、熟悉线性规划的模型结构 会将一般形式转化成标准形式会将一般形式转化成标准形式二、驾驭主要概念二、驾驭主要概念 可行解、可行域、最优解、最优值、基、可行解、可行域、最优解、最优值、基、基本解、基本可行解、可行基基本解、基本可行解、可行基三、会用图解法、单纯形法求解线性规划问题三、会用图解法、单纯形法求解线性规划问题四、会建立简洁线性规划问题的数学模型四、会建立简洁线性规划问题的数学模型