第四讲线性规划在工商管理中的应用课件.ppt

1、第四章第四章 线性规划在工商管理中的应用线性规划在工商管理中的应用 1 1 人力资源分配的问题 2 2 生产计划的问题 3 3 套裁下料问题 4 4 配料问题 5 5 投资问题1 1人力资源分配的问题 例1某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?1 1人力资源分配的问题 解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Min x1+x2+x3+x4+x5+x6 约束条件：s.t.x1+x6

2、 60 x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 x1,x2,x3,x4,x5,x6 01 1人力资源分配的问题 例2一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六281 1人力资源分配的问题 解：设 xi(i=1,2,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。目标函数：M

3、in x1+x2+x3+x4+x5+x6+x7 约束条件：s.t.x1+x2+x3+x4+x5 28 x2+x3+x4+x5+x6 15 x3+x4+x5+x6+x7 24 x4+x5+x6+x7+x1 25 x5+x6+x7+x1+x2 19 x6+x7+x1+x2+x3 31 x7+x1+x2+x3+x4 28 x1,x2,x3,x4,x5,x6,x7 02 2生产计划的问题 例3某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公

4、司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？甲乙丙资 源 限 制铸 造 工 时(小 时/件)51078000机 加 工 工 时(小 时/件)64812000装 配 工 时(小 时/件)32210000自 产 铸 件 成 本(元/件)354外 协 铸 件 成 本(元/件)56-机 加 工 成 本(元/件)213装 配 成 本(元/件)322产 品 售 价(元/件)2318162 2生产计划的问题 解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5 分别为由外协铸造再由本公司加工和装配的甲

5、、乙两种产品的件数。求 xi 的利润：利润=售价-各成本之和 产品甲全部自制的利润 =23-(3+2+3)=15 产品甲铸造外协，其余自制的利润 =23-(5+2+3)=13 产品乙全部自制的利润 =18-(5+1+2)=10 产品乙铸造外协，其余自制的利润 =18-(6+1+2)=9 产品丙的利润 =16-(4+3+2)=7 可得到 xi（i=1,2,3,4,5）的利润分别为 15、10、7、13、9 元。2 2生产计划的问题通过以上分析,可建立如下的数学模型:目标函数：Max 15x1+10 x2+7x3+13x4+9x5 约束条件：5x1+10 x2+7x3 8000 6x1+4x2+8

6、x3+6x4+4x5 12000 3x1+2x2+2x3+3x4+2x5 10000 x1,x2,x3,x4,x5 02 2生产计划的问题例4永久机械厂生产、三种产品，均要经过A、B两 道工序加工。设有两种规格的设备A1、A2能完成 A 工序；有三种规格的设备B1、B2、B3能完成 B 工序。可在A、B的任何规格的设备上加工；可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；只能在A2与B2设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？产品单件工时 设备 设备的 有效台时 满负荷时的设备费用 A1 5 10 6000 300 A2 7 9 12 10000

7、 321 B1 6 8 4000 250 B2 4 11 7000 783 B3 7 4000 200 原料（元/件）0.25 0.35 0.50 售价（元/件）1.25 2.00 2.80 2 2生产计划的问题解：设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工的数量。建立如下的数学模型:s.t.5x111+10 x211 6000 （设备 A1）7x112+9x212+12x312 10000 （设备 A2）6x121+8x221 4000 （设备 B1）4x122 +11x322 7000 （设备 B2）7x123 4000 （设备 B3）x111+x112-x

8、121-x122-x123=0（产品在A、B工序加工的数量相等）x211+x212-x221 =0（产品在A、B工序加工的数量相等）x312 -x322 =0（产品在A、B工序加工的数量相等）xijk 0 ,i=1,2,3;j=1,2;k=1,2,32 2生产计划的问题目标函数为计算利润最大化，利润的计算公式为：利润=（销售单价-原料单价）*产品件数之和-（每台时的设备费用*设备实际使用的总台时数）之和。这样得到目标函数：Max(1.25-0.25)(x111+x112)+(2-0.35)x(2-0.35)x221221+(2.80-0.5)x312 300/6000(5x111+10 x21

9、1)-321/10000(7x112+9x212+12x312)-250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).经整理可得：Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x1233 3套裁下料问题套裁下料问题 3套裁下料问题4 4配料问题 例例6 6某工厂要用三种原料某工厂要用三种原料1 1、2 2、3 3混合调配出三种不同规混合调配出三种不同规格的产品甲、乙、丙，数据如

10、右表。问：该厂应如何安排格的产品甲、乙、丙，数据如右表。问：该厂应如何安排生产，使利润收入为最大？生产，使利润收入为最大？产品名称规格要求单价（元/kg）甲原材料1不少于50%，原材料2不超过25%50乙原材料1不少于25%，原材料2不超过50%35丙不限25原材料名称每天最多供应量单价（元/kg）11006521002536035 解：设解：设 xij 表示第表示第 i 种（甲、乙、丙）产品中原种（甲、乙、丙）产品中原料料 j 的含量。这样我们建立数学模型时，要考虑：的含量。这样我们建立数学模型时，要考虑：对于甲：对于甲：x11，x12，x13；对于乙：对于乙：x21，x22，x23；对于丙

11、：对于丙：x31，x32，x33；对于原料对于原料1：x11，x21，x31；对于原料对于原料2：x12，x22，x32；对于原料对于原料3：x13，x23，x33；目标函数：目标函数：利润最大，利润利润最大，利润=收入收入-原料支出原料支出 约束条件：约束条件：规格要求规格要求 4 个；个；供应量限制供应量限制 3 个。个。4 4配料问题利润利润=总收入总收入-总成本总成本=甲乙丙三种产品的销售单价甲乙丙三种产品的销售单价*产品数量产品数量-甲乙丙使甲乙丙使用的原料单价用的原料单价*原料数量，故有原料数量，故有目标函数目标函数Max 50Max 50（x x1111+x x1212+x x1

12、313）+35+35（x x2121+x x2222+x x2323）+25+25（x x3131+x x3232+x x3333）-6565（x x1111+x x2121+x x3131）-25-25（x x1212+x x2222+x x3232）-35-35（x x1313+x x2323+x x3333）=-15=-15x x1111+25+25x x1212+15+15x x1313-30-30 x x2121+10+10 x x2222-40-40 x x3131-10-10 x x3333 约束条件：约束条件：从第从第1个表中有：个表中有：x x11110.5(0.5(x x1

13、111+x x1212+x x1313)x x12120.25(0.25(x x1111+x x1212+x x1313)x x21210.25(0.25(x x2121+x x2222+x x2323)x x22220.5(0.5(x x2121+x x2222+x x2323)4 4配料问题 从第从第2个表中，生产甲乙丙的原材料不能超过原个表中，生产甲乙丙的原材料不能超过原材料的供应限额，故有材料的供应限额，故有 (x x1111+x x2121+x x3131)100)100 (x x1212+x x2222+x x3232)100)100 (x x1313+x x2323+x x333

14、3)60)60 通过整理，得到以下模型：通过整理，得到以下模型：4 4配料问题配料问题例例6 6（续）（续）目标函数：目标函数：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-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 x121

15、2-0.25-0.25x x1313 0 0（原材料（原材料2 2不超过不超过25%25%）0.75 0.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 x2121+x x3131 100 (100 (供应量限制）供应量限制）x x1212+x x2222+x x3232 100 (100 (供应量限制）供应量限制）x x131

16、3+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,34 4配料问题 例例7.7.汽油混合问题。一种汽油的特性可用两种指标汽油混合问题。一种汽油的特性可用两种指标描述，用描述，用“辛烷数辛烷数”来定量描述其点火特性，用来定量描述其点火特性，用“蒸汽压力蒸汽压力”来定量描述其挥发性。某炼油厂有来定量描述其挥发性。某炼油厂有1 1、2 2、3 3、4 4种标准汽油，其特性和库存量列于表种标准汽油，其特性和库存量列于表4-64-6中，中，将这四种标准汽油混合，可得到标号为将这四种标准汽油混

17、合，可得到标号为1 1，2 2的两种的两种飞机汽油，这两种汽油的性能指标及产量需求列于飞机汽油，这两种汽油的性能指标及产量需求列于表表4-74-7中。问应如何根据库存情况适量混合各种标准中。问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使汽油，既满足飞机汽油的性能指标，又使2 2号汽油满号汽油满足需求，并使得足需求，并使得1 1号汽油产量最高？号汽油产量最高？标准汽油标准汽油辛烷数辛烷数蒸汽压力蒸汽压力(g/cm2)库存量库存量(L)1107.57.1110-2380000293.011.38 10-2265200387.05.6910-24081004108.028.

18、45 10-2130100飞机汽油飞机汽油辛烷数辛烷数蒸汽压力蒸汽压力(g/cm2)产量需求产量需求1不小于不小于91不大于不大于9.96 10-2越多越好越多越好2不小于不小于100不大于不大于9.96 10-2不少于不少于250000表表4-6表表4-74 4配料问题 11121314xxxx解：设解：设x xijij为飞机汽油为飞机汽油i i中所用标准汽油中所用标准汽油j j的数量的数量(L)(L)。目标函数为飞机汽油目标函数为飞机汽油1 1的总产量：的总产量：库存量约束为：库存量约束为：1121122213231424380000265200408100130100 xxxxxxxx产

19、量约束为飞机汽油产量约束为飞机汽油2的产量：的产量：21222324250000 xxxx由物理中的分压定律，由物理中的分压定律，可得有关蒸汽压力的约束条件：可得有关蒸汽压力的约束条件：1njjjPVp v11121314212223242.851.424.2718.4902.851.424.2718.490 xxxxxxxx同样可得有关辛烷数的约束条同样可得有关辛烷数的约束条件为：件为：111213141112131416.52.04.017.007.57.013.08.00 xxxxxxxx214 4配料问题 综上所述，得该问题的数学模型为：综上所述，得该问题的数学模型为：11121314

20、2122232411211222132314241112131421222324111213142122max2500003800002652004081001301002.851.424.2718.4902.851.424.2718.49016.5241707.57xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx232413800,(1,2;1,2,3,4)ijxxxij224 4配料问题 由管理运筹学软件求解得：由管理运筹学软件求解得：111213141112131421222324max()933399.938261966.078265200315672.21990561.6

21、88118033.906092427.75839538.309xxxxxxxxxxxx235 5投资问题 例例8 8某部门现有资金某部门现有资金200200万元，今后五年内考虑给以下的项目投资。已知：万元，今后五年内考虑给以下的项目投资。已知：项目项目A A：从第一年到第五年每年年初都可投资，当年末能收回本：从第一年到第五年每年年初都可投资，当年末能收回本110%110%；项目项目B B：从第一年到第四年每年年初都可投资，次年末能收回本：从第一年到第四年每年年初都可投资，次年末能收回本125%125%，但规定每年最大投资额不能超过但规定每年最大投资额不能超过3030万元；项目万元；项目C C：

22、需在第三年年初投资，：需在第三年年初投资，第五年末能收回本利第五年末能收回本利140%140%，但规定最大投资额不能超过，但规定最大投资额不能超过8080万元；项目万元；项目D D：需在第二年年初投资，第五年末能收回本利需在第二年年初投资，第五年末能收回本利155%155%，但规定最大投资额不，但规定最大投资额不能超过能超过100100万元。据测定每万元每次投资的风险指数如下表：问：万元。据测定每万元每次投资的风险指数如下表：问：a a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？金额为最大？b b）应如

23、何确定这些项目的每年投资额，使得第五年年末拥有资金的本利）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在在330330万元的基础上使得其投资总的风险系数为最小？万元的基础上使得其投资总的风险系数为最小？项 目风 险 指 数（次/万 元）A1B3C4D5.5 解：解：1）确定决策变量：连续投资问题）确定决策变量：连续投资问题 设设 xij(i=15，j=14)表示第表示第 i 年初投年初投资于资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的项目的金额。这样我们建立如下的决策变量：金额。这样我们建立如下的决策变量：A x11 x21 x31 x41 x51 B x1

24、2 x22 x32 x42 C x33 D x242 2）约束条件：）约束条件：第一年：第一年：A A当年末可收回投资，故第一年年初应把全部资金投出去，于是当年末可收回投资，故第一年年初应把全部资金投出去，于是 x x1111+x x12 12=200=200；第二年：第二年：B B次年末才可收回投资，故第二年年初有资金次年末才可收回投资，故第二年年初有资金1.1 1.1 x x1111，于是，于是 x x21 21+x x2222+x x2424=1.1=1.1x x1111；第三年：年初有资金第三年：年初有资金 1.1 1.1x x2121+1.25+1.25x x1212，于是，于是 x

25、 x31 31+x x3232+x x3333=1.1=1.1x x2121+1.25+1.25x x1212；第四年：年初有资金第四年：年初有资金 1.1 1.1x x3131+1.25+1.25x x2222，于是，于是 x x41 41+x x4242=1.1=1.1x x3131+1.25+1.25x x2222；第五年：年初有资金第五年：年初有资金 1.1 1.1x x4141+1.25+1.25x x3232，于是，于是 x x51 51=1.1=1.1x x4141+1.25+1.25x x3232；B B、C C、D D的投资限制：的投资限制：x xi2 i2 30(i=1 3

26、0(i=1、2 2、3 3、4)4)，x x3333 80 80，x x2424 100 100 3 3）目标函数及模型：）目标函数及模型：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.

27、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 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）5 5投资问题b)b)所设变量与问题所设变量与问题a a相同，目标函数为风险最小，有相同，目标函数为风险最小，有 Min f=Min f=x x1111+x x2121+x x3131+x x4141+x x51

28、51+3(+3(x x1212+x x2222+x x3232+x x4242)+4)+4x x3333+5.5+5.5x x24 24 在问题在问题a a的约束条件中加上的约束条件中加上“第五年末拥有资金本利在第五年末拥有资金本利在330330万元万元”的条件，的条件，于是模型如下：于是模型如下：Min f=(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

29、=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+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

30、x3333+1.55+1.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）5 5投资问题其它应用 例例6：某厂在今后四个月内需租用仓库堆存货物。已知各：某厂在今后四个月内需租用仓库堆存货物。已知各 个月所需的仓库面积数如表个月所需的仓库面积数如表1所示。又知，当租借合同期所示。又知，当租借合同期 限越长时，场地租借费用享受的折扣优待越大，有关数限越长时，场地租借费用享受的折扣优待越大，有关数 据如表据如表2所示。租借仓库的合同每月初都可办理，每份合所示。租借仓库的合同每月初都可办理，每份合 同

31、应具体说明租借的场地面积数和租借期限。工厂在任同应具体说明租借的场地面积数和租借期限。工厂在任 何一个月初办理签约时，可签一份，也可同时签若干份何一个月初办理签约时，可签一份，也可同时签若干份 租借场地面积数和租借期限不同的合同。为使所付的场租借场地面积数和租借期限不同的合同。为使所付的场 地总租借费用最少，试建立一个线性规划模型。地总租借费用最少，试建立一个线性规划模型。例例7：厂址选择问题：厂址选择问题甲、乙、丙三地，每地都生产一定数量的原料，也消耗一定数甲、乙、丙三地，每地都生产一定数量的原料，也消耗一定数量的产品（如下表）。已知制成每吨产品需量的产品（如下表）。已知制成每吨产品需3吨原

32、料，各地之间吨原料，各地之间的距离为：甲的距离为：甲乙，乙，150千米；甲千米；甲丙，丙，100千米；乙千米；乙丙，丙，200千米。假定每万吨原料运输千米。假定每万吨原料运输1千米的运价为千米的运价为5000元，每万吨产品元，每万吨产品运输运输1千米的运价为千米的运价为6000元。由于地区差异，在不同地点设厂的元。由于地区差异，在不同地点设厂的生产费用也不同。试问究竟在哪些地方设厂，规模多大，才能生产费用也不同。试问究竟在哪些地方设厂，规模多大，才能使总费用最小？另外，由于其他条件限制，在乙处建厂的规模使总费用最小？另外，由于其他条件限制，在乙处建厂的规模（生产的产品数量）不能超过（生产的产品数量）不能超过5万吨。万吨。