线性规划在工商管理中的应用new.pptx

《线性规划在工商管理中的应用new.pptx》由会员分享，可在线阅读，更多相关《线性规划在工商管理中的应用new.pptx（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1线性规划在工商管理中的应用线性规划在工商管理中的应用new1111人力资源分配的问题人力资源分配的问题人力资源分配的问题人力资源分配的问题 2 例1某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?第1页/共27页1111人力资源分配的问题人力资源分配的问题人力资源分配的问题人力资源分配的问题 解：设解：设 x xi i 表示第表示第i i班次时开始上班的司机和乘务人员数班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。这样

2、我们建立如下的数学模型。目标函数：目标函数：Min Min x x1 1+x x2 2+x x3 3+x x4 4+x x5 5+x x6 6 约束条件：约束条件：s.t.s.t.x x1 1+x x6 6 60 60 x x1 1+x x2 2 70 70 x x2 2+x x3 3 60 60 x x3 3+x x4 4 50 50 x x4 4+x x5 5 20 20 x x5 5+x x6 6 30 30 x x1 1,x x2 2,x x3 3,x x4 4,x x5 5,x x6 6 0 03第2页/共27页1111人力资源分配的问题人力资源分配的问题人力资源分配的问题人力资源分

3、配的问题 例例2 2一家中型的百货商场，它对售货员的需求经过一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作货人员每周工作5 5天，休息两天，并要求休息的两天是连天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？要，又使配备的售货人员的人数最少？4第3页/共27页1111人力资源分配的问题人力资源分配的问题人力资源分配的问题人力资源分配的问题 解：设解：设 x xi i(i=1,2

4、,(i=1,2,7),7)表示星期一至日开始休息的人数表示星期一至日开始休息的人数,这样我们建这样我们建立如下的数学模型。立如下的数学模型。目标函数：目标函数：Min Min x x1 1+x x2 2+x x3 3+x x4 4+x x5 5+x x6 6+x x7 7 约束条件：约束条件：s.t.s.t.x x1 1+x x2 2+x x3 3+x x4 4+x x5 5 28 28 x x2 2+x x3 3+x x4 4+x x5 5+x x6 6 15 15 x x3 3+x x4 4+x x5 5+x x6 6+x x7 7 24 24 x x4 4+x x5 5+x x6 6+x

5、 x7 7+x x1 1 25 25 x x5 5+x x6 6+x x7 7+x x1 1+x x2 2 19 19 x x6 6+x x7 7+x x1 1+x x2 2+x x3 3 31 31 x x7 7+x x1 1+x x2 2+x x3 3+x x4 4 28 28 x x1 1,x x2 2,x x3 3,x x4 4,x x5 5,x x6 6,x x7 7 0 05第4页/共27页1111人力资源分配的问题人力资源分配的问题人力资源分配的问题人力资源分配的问题往往一些服务行业的企业对人力资源的需求一周往往一些服务行业的企业对人力资源的需求一周内像例内像例2 2所描述的那样

6、变化，而每天的个时间段的所描述的那样变化，而每天的个时间段的需求又像例需求又像例1 1往往描述的那样变化，在保证工作人往往描述的那样变化，在保证工作人员每天工作员每天工作8h8h，每周休息两天的情况下，如何安，每周休息两天的情况下，如何安排能使人员的编制最小呢？排能使人员的编制最小呢？6第5页/共27页2222生产计划的问题生产计划的问题生产计划的问题生产计划的问题 例例3 3某公司面临一个是外包协作还是自行生产的问某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸

7、件可以外机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？中，由本公司铸造和由外包协作各应多少件？7第6页/共27页2222生产计划的问题生产计划的问题生产计划的问题生产计划的问题 解：设解：设 x x1 1,x x2 2,x x3 3 分别为三道工序都由本公司加工的甲

8、、乙、丙三种分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，产品的件数，x x4 4,x x5 5 分别为由外协铸造再由本公司加工和装配的甲、乙两分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。种产品的件数。求求 x xi i 的利润：利润的利润：利润 =售价售价 -各成本之和各成本之和 产品甲全部自制的利润产品甲全部自制的利润 =23-(3+2+3)=15=23-(3+2+3)=15 元元 产品甲铸造外协，其余自制的利润产品甲铸造外协，其余自制的利润 =23-(5+2+3)=13=23-(5+2+3)=13 元元 产品乙全部自制的利润产品乙全部自制的利润 =18-(5+1

9、+2)=10=18-(5+1+2)=10 元元 产品乙铸造外协，其余自制的利润产品乙铸造外协，其余自制的利润 =18-(6+1+2)=9=18-(6+1+2)=9 元元 产品丙的利润产品丙的利润 =16-(4+3+2)=7=16-(4+3+2)=7 元元 可得到可得到 x xi i （i=1,2,3,4,5i=1,2,3,4,5）的利润分别为的利润分别为 1515元、元、1010元、元、7 7元、元、1313元、元、9 9元。元。8第7页/共27页2222生产计划的问题生产计划的问题生产计划的问题生产计划的问题通过以上分析通过以上分析,可建立如下的数学模型可建立如下的数学模型:目标函数目标函数

10、：Max 15Max 15x x1 1+10+10 x x2 2+7+7x x3 3+13+13x x4 4+9+9x x5 5 约束条件约束条件：5 5x x1 1+10+10 x x2 2+7+7x x3 3 8000 8000 6 6x x1 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 09第8页/共27页2222生产计划的问题生

11、产计划的问题生产计划的问题生产计划的问题例例4 4永久机械厂生产永久机械厂生产、三种产品，均要经过三种产品，均要经过A A、B B两两 道工序加工。设有两种规格的设备道工序加工。设有两种规格的设备A A1 1、A A2 2能完成能完成 A A 工序；工序；有三种规格的设备有三种规格的设备B B1 1、B B2 2、B B3 3能完成能完成 B B 工序。工序。可在可在A A、B B的任何规格的设备上加工；的任何规格的设备上加工；可在任意规格的可在任意规格的A A设备上设备上加工，但对加工，但对B B工序，只能在工序，只能在B B1 1设备上加工；设备上加工；只能在只能在A A2 2与与B B2

12、 2设备上加工。数据如表。问：为使该厂获得最大利润，设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？应如何制定产品加工方案？10第9页/共27页2222生产计划的问题生产计划的问题生产计划的问题生产计划的问题解：设解：设 x xijkijk 表示第表示第 i i 种产品，在第种产品，在第 j j 种工序上的第种工序上的第 k k 种设备上加工的数量。建立如下的数学种设备上加工的数量。建立如下的数学模型模型:s.t.5s.t.5x x111111+10+10 x x211 211 6000 6000 （设备设备 A A1 1 ）7 7x x112112+9+9x x212

13、212+12+12x x312312 10000 10000 （设备设备 A A2 2 ）6 6x x121121+8+8x x221221 4000 4000 （设备设备 B B1 1 ）4 4x x122122 +11 +11x x322322 7000 7000 （设备设备 B B2 2 ）7 7x x123123 4000 4000 （设备设备 B B3 3 ）x x111111+x x112112-x x121121-x x122122-x x123123=0 =0（产品在产品在A A、B B工序加工的数量相等）工序加工的数量相等）x x211211+x x212212-x x221

14、221 =0 =0（产品在产品在A A、B B工序加工的数量相等）工序加工的数量相等）x x312 312 -x x322322 =0 =0（产品在产品在A A、B B工序加工的数量相等）工序加工的数量相等）x xijkijk 0 ,i=1,2,3;j=1,2;k=1,2,3 0 ,i=1,2,3;j=1,2;k=1,2,311第10页/共27页2222生产计划的问题生产计划的问题生产计划的问题生产计划的问题目标函数为计算利润最大化，利润的计算公式为：目标函数为计算利润最大化，利润的计算公式为：利润利润 =（销售单价（销售单价 -原料单价）原料单价）*产品件数产品件数 之和之和 -（每台时的设

15、备费用（每台时的设备费用*设备实际使用的总台时数）之和。设备实际使用的总台时数）之和。这样得到目标函数：这样得到目标函数：Max(1.25-0.25)(xMax(1.25-0.25)(x111111+x+x112112)+(2-0.35)(x)+(2-0.35)(x211211+x+x212212)+(2.80-0.5)x)+(2.80-0.5)x312312 300/6000(5x 300/6000(5x111111+10 x+10 x211211)-321/10000(7x)-321/10000(7x112112+9x+9x212212+12x+12x312312)-)-250/4000(

16、6x 250/4000(6x121121+8x+8x221221)-783/7000(4x)-783/7000(4x122122+11x+11x322322)-)-200/4000(7x200/4000(7x123123).).经整理可得：经整理可得：Max0.75Max0.75x x111111+0.7753+0.7753x x112112+1.15+1.15x x211211+1.3611+1.3611x x212212+1.9148+1.9148x x312312-0.375-0.375x x121121-0.50.5x x221221-0.4474-0.4474x x122122-1.

17、2304-1.2304x x322322-0.35-0.35x x12312312第11页/共27页3333套裁下料问题套裁下料问题套裁下料问题套裁下料问题 13 例5某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？解：共可设计下列8 种下料方案，见下表 设 x1,x2,x3,x4,x5,x6,x7,x8分别为上面 8 种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：Min x1+x2+x3+x4+x5+x6+x7+x8 约束条件：s.t.x1+2x2 +x4 +x6 100 2x3+2

18、x4+x5+x6+3x7 100 3x1+x2+2x3+3x4 +x6+4x8 100 x1,x2,x3,x4,x5,x6,x7,x8 0第12页/共27页3333套裁下料问题套裁下料问题套裁下料问题套裁下料问题n n若可能的下料方案太多，可以先设计出较好的几个下料方案。较好，首先要求每个方案下料后的料头较短；其次方案总体能裁下所有各种规格的圆钢，且不同方案有着不同的各种所需圆钢的比。这样套裁即使不是最优解，也是次优解，也能满足要求并达到省料目的。如我们用前5种下料方案进行求解，也可得到上述最优解。14第13页/共27页3333套裁下料问题套裁下料问题套裁下料问题套裁下料问题n n用用“管理运

19、筹学管理运筹学”软件计算得出最优下料方案：按方案软件计算得出最优下料方案：按方案1 1下料下料3030根；按方案根；按方案2 2下料下料1010根；按方案根；按方案4 4下料下料5050根。根。即即 x x1 1=30;=30;x x2 2=10=10；x x3 3=0=0；x x4 4=50=50；x x5 5=0=0；x x6 6=x=x7 7=x=x8 8=0=0 只需只需9090根原材料就可制造出根原材料就可制造出100100套钢架。套钢架。n n注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时

20、在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。是最优方案。如果用等于号，这一方案就不是可行解了。15第14页/共27页4444配料问题配料问题配料问题配料问题 16 例6某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如右表。问：该厂应如何安排生产，使利润收入为最大？解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑：对于甲：x11，x12，x13；对于乙：x21，x22，x23；对于丙：x31，

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

22、22+x x2323）+25+25（x x3131+x x3232+x x3333）-65-65（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 1个表中有：个表中有：x x11110.5(0.5(x x1111+x x1212

23、+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)17第16页/共27页4444配料问题配料问题配料问题配料问题 从第从第2 2个表中，生产甲乙丙的原材料不能超过原个表中，生产甲乙丙的原材料不能超过原材料的供应限额，故有材料的供应限额，故有 x x1111+x x2121+x x3131100100 x x1212+x x2222+x x3232100100 x x1313+x x232

24、3+x x33336060 通过整理，得到以下模型：通过整理，得到以下模型：18第17页/共27页4444配料问题配料问题配料问题配料问题例例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.

25、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 x2121+x x3131 100 (100 (供应量限制）供应量限制）x x1212+x x2222+x x3232 100 (

26、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)19第18页/共27页4444配料问题配料问题配料问题配料问题例例6 6（续）（续）此线性规划的计算机解为此线性规划的计算机解为x x1111=100=100，x x1212=50=50，x x1313=50=50，其余的，其余的x xij ij =0=0，也就是说每天只生产产品甲，也就是说每天只生产产品甲200kg200kg，分别需要用第，分别需要用第1 1种原料种原料100k

27、g100kg，第，第2 2种原料种原料50kg50kg，第，第3 3种原料种原料50kg50kg。20第19页/共27页4444配料问题配料问题配料问题配料问题 标准汽油标准汽油辛烷数辛烷数蒸汽压力蒸汽压力(g/cm2)库存量库存量(L)1107.57.1110-2380000293.011.38 10-2265200387.05.6910-24081004108.028.45 10-2130100飞机汽油飞机汽油辛烷数辛烷数蒸汽压力蒸汽压力(g/cm2)产量需求产量需求1不小于不小于91不大于不大于9.96 10-2越多越好越多越好2不小于不小于100不大于不大于9.96 10-2不少于不少

28、于25000021例7.汽油混合问题。一种汽油的特性可用两种指标描述，用“辛烷数”来定量描述其点火特性，用“蒸汽压力”来定量描述其挥发性。某炼油厂有1、2、3、4的4种标准汽油，其特性和库存量列于表4-8中，将这四种标准汽油混合，可得到标号为1，2的2种飞机汽油，这两种汽油的性能指标及产量需求列于表4-9中。问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号汽油满足需求，并使得1号汽油产量最高？表表4-8表表4-9第20页/共27页4444配料问题配料问题配料问题配料问题 22解：设xij为飞机汽油i中所用标准汽油j的数量(L)。目标函数为飞机汽油1的总产量：库存量约

29、束为：产量约束为飞机汽油2的产量：由物理中的分压定律，可得有关蒸汽压力的约束条件：同样可得有关辛烷数的约束条件为：第21页/共27页4444配料问题配料问题配料问题配料问题 23综上所述，得该问题的数学模型为：第22页/共27页4444配料问题配料问题配料问题配料问题 24由管理运筹学软件求解得：第23页/共27页5555投资问题投资问题投资问题投资问题 25例8某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万

30、元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。据测定每万元每次投资的风险指数如右表：问：问：1）应如何确定这些项目每年的投资额，使得第五年年末拥有资金的本利金额为最大？2）应如何确定这些项目每年的投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资的总的风险系数为最小？解：解：1 1）确定决策变量：连续投资问题 设 xij(i=15，j=14)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立

31、如下的决策变量：A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24第24页/共27页5555投资问题投资问题投资问题投资问题2 2 2 2）约束条件：）约束条件：）约束条件：）约束条件：第一年：第一年：A A当年末可收回投资，故第一年年初应把全部资金投出去，于是当年末可收回投资，故第一年年初应把全部资金投出去，于是 x x1111+x x12 12=200=200；第二年：第二年：B B次年末才可收回投资，故第二年年初有资金次年末才可收回投资，故第二年年初有资金1.1 1.1 x x1111，于是，于是 x x21 21+x x2222+x

32、x2424=1.1=1.1x x1111；第三年：年初有资金第三年：年初有资金 1.11.1x x2121+1.25+1.25x x1212，于是，于是 x x31 31+x x3232+x x3333=1.1=1.1x x2121+1.25+1.25x x1212；第四年：年初有资金第四年：年初有资金 1.11.1x x3131+1.25+1.25x x2222，于是，于是 x x41 41+x x4242=1.1=1.1x x3131+1.25+1.25x x2222；第五年：年初有资金第五年：年初有资金 1.11.1x x4141+1.25+1.25x x3232，于是，于是 x x51

33、 51=1.1=1.1x x4141+1.25+1.25x x3232；B B、C C、D D的投资限制：的投资限制：x xi2 i2 30(i=1 30(i=1、2 2、3 3、4)4)，x x3333 80 80，x x2424 100 100 3 3 3 3）目标函数及模型：）目标函数及模型：）目标函数及模型：）目标函数及模型：a)a)a)a)Max z=1.1Max 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 x22

34、22+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 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）26第2

35、5页/共27页Sb)b)b)b)所设变量与问题所设变量与问题a a相同，目标函数为风险最小，有相同，目标函数为风险最小，有 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 在问题在问题a a的约束条件中加上的约束条件中加上“第五年末拥有资金本利在第五年末拥有资金本利在330330万元万元”的条件，的条件，于是模型如下：于是模型如下：Min f=(Min f=(x x1111+x x2121+x x3131+x

36、 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 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 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）2755投资问题第26页/共27页