线性规划在管理中的应用

1第四章线性规划在工商管理中的应用§4.1人力资源分配的问题§4.2生产计划的问题§4.3套裁下料问题§4.4配料问题§4.5投资问题2§4.1人力资源分配的问题

例1．某昼夜服务的公交线路,每天各班次所需司机和乘务人员数如下：设：司机和乘务人员分别在某时间段一开始时上班，并连续工作8小时，问该公交线路怎样安排司机和乘务人员，既能完成工作，且雇佣的司机和乘务人员总数最少?班次时间所需人数16：00——10：0060210：00——14：0070314：00——18：0060418：00——22：0050522：00——2：002062：00——6：00303

例1求解思路1、目标函数：任务已定，求每天上班总人数之和最小。要用最少的人力资源完成规定的乘运任务。1234566:0010:0014:0018:0022:002:0060人70人60人50人20人30人3、约束条件：每两个班次人数之和不少于bi2、决策变量(Xi)：需要决策是各个班次的上班人数。已知在第i时间段（当班）次工作的人数应包括第i-1班次时开始上班的人员数和第i班次时开始上班的人数。4例1LP模型

解：设xi

表示第i班次时开始上班的司机和乘务人员数.

可建立如下的数学模型。目标函数：Minf=x1+x2+x3+x4+x5+x6

约束条件：s.t.x6+x1≥60(6点到10所需人数）

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30x1,x2,x3,x4,x5,x6≥0用软件的最优解：x1=50，x2=20，x3=50，x4=0，x5=20，x6=105

例2．某中型的百货商场，它对售货员的需求经过统计分析如下表所示。时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六28§4.1

人力资源分配的问题注意，为了保证售货员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问:应该如何安排售货员的作息，既满足工作需要，又使所需总售货员的人数最少？6例2求解思路目标函数：总雇员最少(等价于轮休雇员总人数最少)决策变量：周内每天休班的人数（Xi)约束条件：凡不休班的售货员都上班以满足岗位的需要7例2数学模型

Minf=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≥28x1,x2,x3,x4,x5,x6,x7≥0最优解：X=（12，0，11，5，0，8，0）,

MinZ=36人解：设xi(i=1,2,…,7)表示星期一至日开始休息的人数,可建立如下的数学模型。目标函数：时间所需售货员数星期日28星期一15星期二24星期三25星期四19星期五31星期六28约束条件见41页图4-18§4.2

生产计划的问题

例3．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？甲乙丙资源限制铸造工时(小时/件)51078000机加工工时(小时/件)64812000装配工时(小时/件)32210000自产铸件成本(元/件)354外协铸件成本(元/件)56--机加工成本(元/件)213装配成本(元/件)322产品售价(元/件)2318169甲乙丙资源限制铸造工时(小时/件)51078000机加工工时(小时/件)64812000装配工时(小时/件)32210000自产铸件成本(元/件)354外协铸件成本(元/件)56--机加工成本(元/件)213装配成本(元/件)322产品售价(元/件)231816例3求解思路设x1,x2,x3

分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，并设x4,x5

分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。1、求目标函数系数Ci(不同产品的利润)利润=售价-各项成本X1的系数:甲产品全部自制的利润C1=23--33-2=1510甲乙丙资源限制铸造工时(小时/件)51078000机加工工时(小时/件)64812000装配工时(小时/件)32210000自产铸件成本(元/件)354外协铸件成本(元/件)56--机加工成本(元/件)213装配成本(元/件)322产品售价(元/件)231816X4的系数:甲产品铸造外协其余自制的利润C4=23-(5+2+3)=1311同理得：得:xi

（i=1,2,3,4,5）的利润分别为15、10、7、13、9元X3:丙产品的利润C3=16-(4+3+2)=7X2:乙产品全部自制的利润C2=18-(5+1+2)=10X5:乙产品铸造外协其余自制的利润C5=18-(6+1+2)=912例3数学模型通过以上分析,可建立如下的数学模型:目标函数：Max15x1+10x2+7x3+13x4+9x5

约束条件：5x1+10x2+7x3≤8000(铸造工时)

（机加工工时）

6x1+4x2+8x3+6x4+4x5≤12000（装配工时）

3x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0优化结果见教材第43页，maxZ=29400,x1=1600，X5=600，其它：Xi=013§4.2

生产计划的问题

工序设备不同产品每件需要工时设备的有效台时满负荷时的设备费用ⅠⅡⅢA2791210000321BB1684000250B24117000783B374000200原料（元/件）0.250.350.50售价（元/件）1.252.002.80问：为使该厂获得最大利润，应如何制定产品加工方案？产品Ⅰ可在A、B的任何规格的设备上加工；Ⅱ可在任意规格的A设备上加工，但对B工序则只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工。有关数据如表：例4．某机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B两道工序加工。设备A1、A2能完成A工序；B1、B2、B3设备能完成B工序。14决策变量：各类产品生产数量(同一产品因在不同的工序设备上加工工时消耗不同视作不同产品类型）；因为要考虑到工序以及设备类型的约束，不妨用Xijk表示不同品种、工序、设备生的产量。工序设备产品类型ⅠⅡⅢAA1X111X211X311A2X112X212X312BB1X121X221X321B2X122X222X322B3X123X223X323原料（元/件）0.250.350.50售价（元/件）1.252.002.80一、设置决策变量：工序设备产品，每件需工时ⅠⅡⅢAA1510A27912BB168B2411B37原料（元/件）0.250.350.50售价（元/件）1.252.002.80求解155x111+10x211≤6000（设备A1

）

7x112+9x212+12x312≤10000（设备A2

）

6x121+8x221≤4000（设备B1

）

4x122+11x322≤7000（设备B2

）

7x123≤4000（设备B3

）

x111+x112-x121-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,3二、设置约束方程（各类工序、设备约束）当设xijk

表示第i种产品，在第j种工序上的第k种设备上加工的数量时。可建立如下约束方程:16

由于目标函数是求利润最大化，所以目标函数中系数计算公式为：

利润=Σ[(销售单价-原料单价）*该种类产品件数]-Σ(每台时的设备费用*设备实际使用的总台时数）这样可写出如下目标函数：MaxZ=[(1.25-0.25)(x111+x112)+(2-0.35)x221+(2.80-0.5)x312]

–300/6000(5x111+10x211)-321/10000(7x112+9x212+12x312)-250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).（注意x111+x112-x121-x122-x123=0等）经整理可得：

MaxZ=0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123三、目标函数：不同产品类型与纯利润乘积之和最大产品Ⅰ在第一工序A的总产量,经过A、B两道工序的量与经过A工序的量相等？产品Ⅱ全部经B工序第一种设备17Z=Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121

-0.5x221-0.4475x122-1.2304x322-0.35x123s.t.5x111+10x211≤6000（设备A1

）

7x112+9x212+12x312≤10000（设备A2

）

6x121+8x221≤4000（设备B1

）

4x122+11x322≤7000（设备B2

）

7x123≤4000（设备B3

）

x111+x112-x121-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,3计算结果见教材P45例4完整模型18§4.3

套裁下料问题

例5．某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？方案1方案2方案3方案4方案52.9m/根120102.1m/根002211.5m/根31203合计7.47.37.27.16.6料头剩余（m)00.10.20.30.8解题思路：套裁下料问题，关键是预设计下料方案不妨设计下列5种下料方案，见表4-519设x1,x2,x3,x4,x5分别为上面5种方案下料的原材料根数。这样我们建立如下的数学模型。

目标函数：Minf=x1+x2+x3+x4+x5

约束条件：s.t.x1+2x2+x4≥100(长2.9m的不少于100)2x3+2x4+x5≥100(长为2.1m的需求量)3x1+x2+2x3+3x5≥100(1.5m需求量)x1,x2,x3,x4,x5≥0例5求解思路20用“管理运筹学”软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。即x1=30;x2=10；

x3=0；

x4=50；

x5=0；只需90根原材料就可制造出100套钢架。注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。套裁下料问题求解结果21§4.4

配料问题

例6-1．某工厂要用三种原料（编号为1、2、3，表4-7）混合调配出三种不同规格的产品（甲、乙、丙），数据如表4-6。品名规格要求单价（元/kg）甲用1号原材料不少于50%，2号原材料不超过25%50乙用1号原材料不少于25%，2号原材料不超过50%35丙用料比例不限25原材料名称每天最多供应量（Kg）单价（元/kg）1号100652号100253号6035表4-6表4-7问：该厂应如何安排生产，使利润收入为最大？22

设xij

表示第i种产品（甲、乙、丙）中，第j原料的含有量。因此，不同规格产品的产量可由相应的决策变量之和求出：甲产量：x1.=x11+x12+x13；∵甲产品的总量为其构成的3种原料用量之和，同理：

乙产量：x2.=

x21+x22+x23；丙产量：x3.=

x31+x32+x33；因为，某种原料的用量为相关产品含该种原料量之和：原料1用量：x.1=x11+x21+x31；（各相关决策变量含第1种原料量的和）原料2用量：x.2=x12+x22+x32；原料3用量：x.3=x13+x23+x33；

例6-1求解思路规格要求约束4个；供应量限制约束3个。目标函数：利润最大，（利润=总收入–总原料支出）约束条件：23例6-1数学模型MaxZ=（50x1.+35x2.+25x3.）-

（65x.1+25x.2+35x.3

）=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

见表4-6中要求规格约束：x11≥0.5x1.x12≤0.25x1.x21≥0.25x2.x22≤0.5x2.st.品名规格要求单价（元/kg）甲原材料1不少于50%，原材料2不超过25%50乙原材料1不少于25%，原材料2不超过50%35丙不限25目标函数:利润=产品销售单价*产品数量之和-原料单价*原料量之和。即：24(x11+x21+x31)≤100(x12+x22+x32)≤100(x13+x23+x33)≤60原材料名称每天最多供应量kg单价（元/kg）1号100652号100253号6035生产甲乙丙的原材料不能超过原材料的供应限额因此还应有以下约束：原料供应约束：因为25例6-1完整LP模型目标函数：Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

s.t.0.5x11-0.5x12-0.5x13≥0（原材料1不少于50%）

-0.25x11+0.75x12-0.25x13≤0（原材料2不超过25%）

0.75x21-0.25x22-0.25x23≥0（原材料1不少于25%）

-0.5x21+0.5x22-0.5x23≤0（原材料2不超过50%）

x11+x21+x31≤100(供应量限制）

x12+x22+x32≤100(供应量限制）

x13+x23+x33≤60(供应量限制）

xij≥0,i=1,2,3;j=1,2,3计算结果见P48，-3

某公司长期饲养某种动物，已知这些动物的生长对饲料中的蛋白质、矿物质、维生素这三种营养成分特别敏感，每个动物每天至少需要蛋白质70g、矿物质3g、维生素10mg，该公司能买到五种不同的饲料原料，每种原料

每公斤所含的上述成分及成本如下表所示，试为公司制定相应的饲料配方，以满足动物生长的营养需要，并使所用原料的总成本最低。配料问题例6-2原料蛋白质（g）矿物质（g）维生素（mg）10.30.10.05220.050.1310.020.0240.60.20.251.80.050.08饲料原料12345成本（元）0.20.70.40.30.5设Xi为混合饲料中所含的第i种原料的量（决策变量）例6-2求解思路1、设置决策变量：3、确定约束条件：因每个动物每天至少需要蛋白质70g、矿物质3g、维生素10mg，所以应满足如下的约束条件：2、确定目标函数

x1,…x5≥0St.例6-2LP完整模型29汽油混合问题。汽油的特性可用两种指标描述，一般用“辛烷数”来定量描述其点火特性，用“蒸汽压力”来定量描述其挥发性。某炼油厂有1、2、3、4种标准汽油，其特性和库存量列于表4-8中。标准汽油辛烷数蒸汽压力(g/cm2)库存量(L)1107.57.11×10-2380000293.011.38×10-2265200387.05.69×10-24081004108.028.45×10-2130100表4-8

例7.配料问题（续）30若将这四种标准汽油混合可得到标号为1，2的两种飞机用汽油，这两种汽油的性能指标及产量需求列于表4-9中。问题：应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号汽油满足需求，并使得1号汽油产量最高？飞机汽油辛烷数蒸汽压力(g/cm2)产量需求L1不小于91不大于9.96×10-2越多越好2不小于100不大于9.96×10-2不少于250000表4-9例7续31例7求解思路解：设xij

为第i种飞机汽油用第j标准汽油的数量(L)。1、库存约束：2号飞机汽油产量3蒸汽压力的约束:混合气体的压强容积的乘积=各组成气体压强与容积乘积之和目标函数（求1号飞机汽油的总产量最大）（1号标准汽油库存）（2号标准汽油库存）由此可写出不同混合汽油的压力的约束条件：MaxZ=St.2、产量约束：32同样可得有关辛烷数的约束条件为：对两个压力约束经条件整理后为：1号飞机汽油气体压强≤9.96*10-2，因此有：[(7.11*x11+11.38*x12+5.69*x13+28.45*x14)*10-2]/(x11+x12+x13+x14)]≤9.96*10-2同理可列出2号飞机汽油的压力约束：33例7数学完整模型

34例7求解结果

由管理运筹学软件求解得：35§4.5

投资问题问题：1、应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？

D项目：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；例8．某部门现有资金200万元，今后五年内考虑给以下的项目投资：项目风险指数（每次投资1万元）A1B3C4D5.5问题2、应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？另：据测定每万元每次投资的风险指数如下表37设xij(i=1～5，j=1～4)表示第i年初投资于j=1(A)、j=2(B)、j=3(C)、j=4(D)项目的金额。这样可写出如下的1）决策变量：

Ax11

x21

x31

x41

x51

(x1)(x2)…

Bx12x22

x32

x42

…

Cx33

(x10)

Dx24解：1、连续投资问题例8求解思路38第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是x11+x12=200；第二年：B次年末才可收回投资，故第二年年初有资金1.1x11，于是x21+x22+x24=1.1x11；第三年：年初有资金1.1x21+1.25x12，于是x31+x32+x33=1.1x21+1.25x12；第四年：年初有资金1.1x31+1.25x22，于是x41+x42=1.1x31+1.25x22；第五年：年初有资金1.1x41+1.25x32，于是x51=1.1