线性规划在工商管理中的管理运筹学.ppt

在建立数学模型并求解的同时，要结合实际应用！,运筹学的实质,求解运筹学问题的基本思路,一、建立运筹学问题数学模型 （第四章建模） 二、求运筹学问题的解 （第二章、第五章求解） 三、运筹学问题的灵敏度分析 （第六章结果分析）,例题,某厂生产甲、乙两种产品，要消耗A、B、C三种资源，已知每生产单位产品甲需要A 、B、C资源分别是3、2、0，生产单位产品乙需要A 、B、C资源分别是2、1、3， 资源A 、B、C的现有数量分别是65、40、75，甲、乙两种产品的单位利润分别是1500、2500，问如何安排生产计划，使得既能充分利用现有资源又使总利润最大 ？,x2,x1,解： 1确定决策变量： 设x1表示生产甲产品的数量；x2表示生产乙产品的数量 2确定目标函数：工厂的目标是总利润最大 z=1500x1+2500x2 3确定约束条件： 3x1+2x265（A资源的限制） 2x1+ x2 40（B资源的限制） 3x2 75（C资源的限制） 4变量取值限制： 一般情况，决策变量只取大于等于0的值（非负值） x1 0, x2 0,用max表示最大值，s.t.（subject to的简写）表示约束条件， 得到该问题的数学模型为： max Z=1500x1+2500x2 3x1+2x2 65 s.t. 2x1+ x2 40 3x2 75 x1, x2 0,目标函数,约束条件,决策变量,决策变量 目标函数 约束条件,运筹学数学模型三要素：,一、人力资源分配的问题 二、生产计划问题 三、套裁下料问题 四、配料问题 五、运输问题 六、投资问题,第四章 线性规划在工商管理中的应用,一、人力资源分配的问题,例1、某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如表所示，设司机和乘务人员分别在各时间段开始时上班，并连续工作八小时，问该公交线路应怎样安排司机和乘务人员，既能满足工作需要，又使配备司机和乘务人员的人数最少？,.解：设x i表示在第i个时期初开始工作的司机和乘务人员人数(i=1,2,6)，z表示所需的总人数，则根据题意，得到原问题的数学模型为:,例2、一家中型的百货商场对售货员的需求经过统计分析如表所示，为了保证售货员充分休息，要求售货员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货员的休息日期，既满足工作需要，又使配备的售货员的人数最少？,解：设x i表示在星期i开始休息的人数(i=1,2,7) ，z表示所需的总人数，则根据题意，得到原问题的数学模型为:,X1+x2+x3+x4+x528 x2+x3+x4+x5+X615 x3+x4+x5+X6+x724 s.t. x4+x5+ X6+x7+x125 x5+X6+x7+X1+x219 X6+x7+X1+x2+x331 x7+X1+x2+x3+x428 X1,x2,x3,x4,x5,x6,x70,二、生产计划问题,例3、某公司面临一个是外包协作还是自行生产的问题。该公司有甲、乙、丙三种产品，这三种产品都要经过铸造、机械加工和装配三道工序，甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须由本厂铸造才能保证质量，有关情况如表所示，公司中可利用的总工时为：铸造8000小时，机械加工12000小时和装配10000小时。为了获得最大利润，甲乙丙三种产品各应生产多少件？甲、乙两种产品的铸件有多少由本公司铸造？有多少为外包协作？,解：设x1,x2,x3分别表示三道工序都由本公司加工的甲、乙、丙三种产品的件数,x4,x5分别为由外包协作铸造再由本公司进行机械加工和装配的甲、乙两种产品的件数，则根据题意，得到原问题的数学模型为:,Maxz=23(x1+x4)+18(x2+x5)+16x3-3x1-5x2-4x3-5x4-6x5 -2(x1+x4)-(x2+x5)-3x3-3(x1+x4)-2(x2+x5)-2x3 5X1+10x2+7x38000 s.t. 6(x1+x4)+4(x2+x5)+8x3 12000 3(x1+x4)+2(x2+X5)+2x3 10000 X1,x2,x3,x4,x50,Maxz=15x1+10x2+7x3+13x4+9x5 5X1+10x2+7x38000 s.t. 6x1+ 4x2+8x3+6x4 +4x5 12000 3x1+2x2+2x3+3X4+2x5 10000 X1,x2,x3,x4,x50,整理得：,例4、永久机械厂生产甲、乙、丙三种产品，每种产品均要经过A、B两道加工工序。设该厂有两种规格的设备能完成工序A，它们以A1、A2表示；有三种规格的设备能完成工序B，它们以B1、B2、B3表示。产品甲可在工序A和B的任何规格的设备上加工；产品乙可在工序A的任何一种规格的设备上加工，但完成工序B时，只能在设备B1上加工；产品丙只能在设备A2与B2上加工。已知在各种设备上加工的单件工时、各种设备的有效台时如表所示。另外已知产品甲、乙、丙的原料单价分别为0.25元/件、0.35元/件和0.5元/件，销售单价分别为1.25元/件、2元/件和2.8元/件，要求制定最优的产品加工方案，使该厂利润最大。,解：根据题意，生产三种产品分别有如下几种方案： 甲：（A1,B1) , (A1,B2), (A1,B3), (A2,B1), (A2,B2), (A2,B3)六种方案 乙：（A1，B1），（A2，B1）两种方案 丙：（A2，B2）一种方案 令xi表示采用第i种方案进行加工的某种产品的数量(i=1,2,9),x1 x2 x3 x4 x5 x6,x7 x8,x9,Maxz= (1.25-0.25)(x1+x2+x3+x4+x5+x6)+(2-0.35)(x7+x8)+(2.8-0.5)x9 5(x1+x2+x3)+10x76000 7(x4+x5+x6)+9x8+12x9 10000 s.t. 6(x1+x4)+8x7 +8x8 4000 4(x2+x5)+11x97000 7(x3+x6) 4000 xi0 (i=1,2,9),整理得： Maxz= x1+x2+x3+x4+x5+x6 +1.35x7+1.65x8+2.3x9 5x1+5x2+5x3 +10x7 6000 7x4+7x5+7x6 +9x8+12x9 10000 s.t. 6x1 +6x4 +8x7 +8x8 4000 4x2 +4x5 +11x97000 7x3 +7x6 4000 xi0 (i=1,2,9),例5、永久机械厂生产甲、乙、丙三种产品，每种产品均要经过A、B两道加工工序。设该厂有两种规格的设备能完成工序A，它们以A1、A2表示；有三种规格的设备能完成工序B，它们以B1、B2、B3表示。产品甲可在工序A和B的任何规格的设备上加工；产品乙可在工序A的任何一种规格的设备上加工，但完成工序B时，只能在设备B1上加工；产品丙只能在设备A2与B2上加工。已知在各种设备上加工的单件工时、各种设备的有效台时以及满负荷操作时的设备费用如表所示。另外已知产品甲、乙、丙的原料单价分别为0.25元/件、0.35元/件和0.5元/件，销售单价分别为1.25元/件、2元/件和2.8元/件，要求制定最优的产品加工方案，使该厂利润最大。,解：根据题意，生产三种产品分别有如下几种方案： 甲：（A1,B1) , (A1,B2), (A1,B3), (A2,B1), (A2,B2), (A2,B3)六种方案 乙：（A1,B1），（A2，B1）两种方案 丙：（A2,B2）一种方案 xi表示采用第i种方案进行加工的某种产品的数量(i=1,2,9),x1 x2 x3 x4 x5 x6,x7 x8,x9,Maxz= x1+x2+x3+x4+x5+x6 +1.35x7+1.65x8+2.3x9 -300/6000(5x1+5x2+5x3 +10x7 ) -321/10000(7x4+7x5+7x6 +9x8+12x9 ) -250/4000(6x1+6x4+8x7 ) -783/7000(4x2 +4x5 +11x9 ) -200/4000(7x3 +7x6),约束条件不变,思考！,决策变量的另一种表示方法： 根据题意，生产三种产品分别有如下几种方案： 甲：（A1，B1) , (A1,B2), (A1,B3), (A2,B1), (A2,B2), (A2,B3)六种方案 乙：（A1，B1），（A2，B1）两种方案 丙：（A2，B2）一种方案 设i=1,2,3分别表示甲、乙、丙三种产品； j=1,2,.分别表示第j个方案； xij表示第i种产品采用第j个方案进行加工的产品的数量,x11 x12 x13 x14 x15 x16,x21 x22,x31,三、套裁下料问题,例6、 某工厂要做100套钢架，每套钢架需要长度分别为2.9m，2.1m和1.5m的圆钢各一根。已知原料每根长7.4m，问应该如何下料，可使所用原料最省？,解：做法一：截取法。 每根原材料中各截取一根组成一套，2.9+2.1+1.5=6.5 每根料头0.9m, 100根90m料头，浪费 做法二：套裁法。,x1 x2 x3 x4 x5,设xi (i=1,2,5)表示按照方案i下料的原材料的根数，则该问题的数学模型如下：,Minz=x1+x2+x3+x4+x5 x1+2x2+x4100 s.t. 2x3+2x4+x5100 3x1+x2+2x3+3x5100 x1,x2,x3,x4,x5 0,思考,1、约束条件用等于号如何？ 2、如果问如何下料，可使料头最少？,四、配料问题,例7、某化工厂根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特殊产品. 甲、乙两种原料都含有A、B、C三种化学成分，其含量（%）和单位成本以及按合同规定产品中三种化学成分的最低含量（%）限制如表所示. 问厂方应如何配制该产品，使得总成本达到最小？,解：(1) 确定决策变量： 设每单位该产品用x1单位甲原料和x2单位乙原料配制而成. (2) 所满足的约束条件 对化学成分A的要求：12 x1+ 3 x2 4 对化学成分B的要求：2 x1 + 3 x2 2 对化学成分C的要求：3 x1 + 15 x2 5 配料平衡条件：x1 + x2 = 1 (3) 明确目标函数：成本最小，即求 z = 3x1 + 2x2的最小值 (4)变量取值限制： x1，x2 0,记为 min z = 3x1 + 2x2 s.t. 12x1 + 3x2 4 2x1 + 3x2 2 3x1 + 15x2 5 x1 + x2 = 1 x1，x2 0,例8、某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，产品的规格要求、产品的单价、每天能供应的原材料数量及原材料单价如表所示，该厂应如何安排生产，才能使利润最大？,解：xij设表示第i种产品中原材料j的含量(i,j=1,2,3), 则三种产品的数量和原材料的数量分别是：,甲： x11+x12+x13 乙： x21+x22+x23 丙： x31+x32+x33 材料1： x11+x21+x31 材料2： x12+x22+x32 材料3： x13+x23+x33,根据题意，得到原问题的数学模型: Max z=50 (x11+x12+x13)+35 (x21+x22+x23)+25 (x31+x32+x33) -65(x11+x21+x31)-25 (x12+x22+x32)-35 (x13+x23+x33) x1150% (x11+x12+x13) x12 25%(x11+x12+x13) x2125%(x21+x22+x23) s.t. x22 50%(x21+x22+x23) x11+x21+x31100 x12+x22+x32 100 x13+x23+x33 60 xij0 (i,j=1,2,3),例9、汽油混合问题 教科书P49,五、 运输问题,例10、设某种物资有两个产地A1，A2，其产量分别为2000吨、1100吨，另有四个销地B1、B2、B3、B4需要该种物资，其需求量分别为1700吨、1100吨、200吨、100吨. 已知每吨运费如表所示，问如何调运，才能使总运费最省？,解：设xij表示由产地Ai运往销地Bj（i = 1,2；j = 1,2,3,4）的运量. 由于总产量与总需求量相等（产销平衡）,所以有约束条件： 对产地产量的约束 : x11 + x12 + x13 + x14 = 2000 x21 + x22 + x23 + x24 = 1100 对销地需求量的约束 : x11 + x21 = 1700 x12 + x13 = 1100 x13 + x23 = 200 x14 + x24 = 100 另外xij是运输量，应满足xij0（i = 1,2；j = 1,2,3,4） 目标函数为总运费最小: minZ = 21x11 + 25x12 + 7x13 + 15x14 + 51x21 + 51x22 + 37x23 + 15x24,所以运输问题的数学模型可记为,min z = 21x11 + 25x12 + 7x13 + 15x14 + 51x21 + 51x22 + 37x23 + 15x24 x11 + x12 + x13 + x14 = 2000 x21 + x22 + x23 + x24 = 1100 x11 + x21 = 1700 s.t. x12 + x22 = 1100 x13 + x23 = 200 x14 + x24 = 100 xij 0（i = 1,2；j = 1,2,3,4）.,六、投资问题,例11、某公司在今后四年内考虑以下四个投资项目选择问题： 项目甲：第二年初需投资，到第四年年末收回本利180%；