线性优化在工商管理中的应用.xls

一一. .人人力力资资源源分分配配问问题题 例1. 某白夜班营运公交线路,在各个时间段需要的人数入下表所示,为了满足工作安排,又能使配备的 人数最少方案(人员上班时间每班次连续8小时) 表(一) 版次 需要人数时间 段 所需人数 未知数 规划求解 结果 安排上班时间段人 数(补充显示) 16:00-10:0060x1456:00-14:00 210:00-14:0070x22510:00-18:00 314:00-18:0060x33514:00-22:00 418:00-22:0050x41518:00-2:00 522:00-2:0020x51522:00-6:00 同时考虑到23:00后到凌晨 6:00算夜班,要开夜班费用 的,也要最少才合适啊62:00-6:0030x6152:00-10:00 解: step1 解题 由于题目没有明确班次的分配问题,假设班次如下分配 关键在于看未知数怎么设 由于人们喜欢这种安排班次上班工作,所以造成人员浪费,nnd怎么就不可以 10:00上班到下午18:00呢?或者下午15:00上班到晚上23:00呢?主要在这里 是考虑这种思维,不能解出来也没有什么价值的结果,显然是不能这样分配 上班时间与人数的 6:00-14:00第1班 14:00-22:00第2班 22:00-6:00第3班 问问题题是是每每次次上上班班8 8小小时时计计, ,每每次次需需求求按按照照4 4小小时时计计算算, ,如如果果搞搞成成2 2小小小小时时或或者者1 1小小时时计计那那不不是是问问题题更更大大 . .如如果果按按照照上上面面假假设设思思维维的的话话, ,我我们们安安排排的的人人数数就就是是6:00-14:00,6:00-14:00,只只能能取取最最大大人人数数7070人人,14:00-,14:00- 22:0022:00取取最最大大人人数数6060人人,22:00-6:00,22:00-6:00取取最最大大人人数数3030人人, ,合合计计人人数数70+60+30=16070+60+30=160人人, ,真真是是那那样样子子的的话话, , 按按照照优优化化的的结结果果150150人人, ,多多余余1010人人的的工工资资你你开开啊啊! step2 系统变量,找出系统变量 设各个时间段上班的人数如(表一)未知数所示 step3 目标函数 min z=x1+x2+x3+x4+x5+x6 step4 约束条件 xi0大于零非负约束(i表示1-6的序号) xi整数人员整数约束(因为人数不能为小数) x6+x160 假定相近时间段为一个班次 x1+x270 假定相近时间段为一个班次 x2+x360 假定相近时间段为一个班次 x3+x450 假定相近时间段为一个班次 x4+x520 假定相近时间段为一个班次 x5+x630 假定相近时间段为一个班次 step5 把所有的目标函数与约束条件,表示为“规划求解“所需要的数学格式,并求解 min z150 6060 7070 6060 5050 3020 3030 说明:以上黄色的部分为我们优化的结果, s.t. s.t. 同理规划 一个车间200人,工作量增加多少%后增开夜 班比较合适? 条件:1600元/人.月,社保等其他支出200元/ 人.月,平时加班按照1.5倍计算,周六周日按照2 倍计算,不考虑其他国家法定假日问题,且一般 能保住工人每月加班在60hour以上,且夜班要开 夜班工资10元/天.人,按照每月上班21.75来计 算一月正常上班时间,其余时间可以安排加班, 但是每周最少要休息一天,每月按照30天进行计 算. 例2. 有一家中等规模的百货商场,经过统计分析每天的人员需求如下表(二)所示,为了保证售货员有 足够的休息时间且,休息的2天是连续的,既能满足工作需求,又要使人数最少的最优安排方案 表(二) 星期 所需售货员人 数 未知数 规划求解 结果 星期一15y110 星期二24y20 星期三25y39 星期四19y43 星期五31y50 星期六28y66 星期日28y76 解: step1 解题 人员安排休息的时间可以错开,比如5人,星期一二休息,7人星期三四休息 step2 系统变量 按照表(二)未知数设定为yi为星期i开始休息的人 加强理解 的词,没 有实际意 义 x1是,星期1开始休息的,星期1开始休息的意思是,休息星期1,2 x2是,星期2开始休息的,星期2开始休息的意思是,休息星期2,3 x3是,星期3开始休息的,星期3开始休息的意思是,休息星期3,4 x4是,星期4开始休息的,星期4开始休息的意思是,休息星期4,5 x5是,星期5开始休息的,星期5开始休息的意思是,休息星期5,6 x6是,星期6开始休息的,星期6开始休息的意思是,休息星期6,7 x7是,星期7开始休息的,星期7开始休息的意思是,休息星期7,1 step3 目标函数 min z=y1+y2+y3+y4+y6+y6+y7 step4 约束变量 y2+y3+y4+y5+y6 15星期2,3,4,5,6开始休息的人星期1就该上班了吧 y3+y4+y5+y6+y7 24星期3,4,5,6,7开始休息的人星期2就该上班了吧 y4+y5+y6+y7+y1 25同理不写下面的文字 y5+y6+y7+y1+y2 19 y6+y7+y1+y2+y3 31 y7+y1+y2+y3+y4 28 y1+y2+y3+y4+y5 28 yi0 yi整数 step5 把所有的目标函数与约束条件,表示为“规划求解“所需要的数学格式,并求解 min z34 18 15 24 24 25 25 22 19 31 31 28 28 28 28 二二. .生生产产计计划划问问题题 s.t. s.t. 例3 某公司面临一个是外包还是自行生产的问题,该公司生产甲乙丙三种产品,分别要经过铸造 机械加工装配三道工序,甲乙2种产品的铸件可以外包,也可以自行生产,但是丙产品不能外包, 自己铸造才能保证品质,有下面的职员可以利用, 铸造工时8000小时,机加工工时12000小时,装配工时10000小时,为了获得最大利润,甲乙丙分别 生产多少件,甲乙有多少可以外包铸造,多少自己本公司铸造. 表(三) 工时与成本甲乙丙 每件铸造工时5107 每件机加工时648 每件装配工时322 自己铸造成本354 外包铸造成本56 - 机加成本213 装配成本322 每件售价231816 解: step1 解题 这就是一个利润最大化问题,这里没有指出利润是多少,需要自己计算现有条件下的利润是多少 为了方便我们把利润计算在未知数的表格里面 step2 系统变量 类型甲-本厂乙-本厂丁-本厂甲-外发乙-外发 产品利润15107139 未知数z1z2z3z4z5 规划结果1600000600 step3 目标函数 max z= 15z1+10z2+7z3+13z4+9z5 step4 约束条件 zi0大于零约束(i是1-5) zi整数件数为整数约束 5z1+10z2+7z38000铸造工时约束 6(z1+z4)+4(z2+z5)+8z312000机加工时约束 3(z1+z4)+2(z2+z5)+2z310000装配工时约束 step5 把目标函数与余数条件转化为,“规划求解“所要求的数学公式表达式,并求解 max z=29400 80008000 1200012000 600010000 例4 永久机械厂能生产甲乙丙三种产品,每种产品均要经过ab两道工序,a有两种规格的机器a1.a2 b有三种规格的机器b1.b2.b3,产品甲可以在ab的任何机型上加工,产品乙可以在a上任意规格做, 由于丙的工 艺要求不能 外发 s.t. s.t. 但在b的时候只能b1,产品丙只能在a2.b2上加工,产品的工时与利润如下表所示,要求制定最优 产品加工方案,使该厂利润最大 表(四) 设备 产品单件工时(小时/件) 设备的有效 台时(小时) 满负荷时 设备费用 (元) 甲乙丙 a a15106000 a2791210000 b b1684000 b24117000 b374000 原料费(元/件)0.250.350.5 单价(元/件)1.2522.8 利润11.652.3 解 step1 解题 题目要求是最大利润,但是这个题有点绕,包含在题目中,有很多种配比生产的方法,我们要计算 每一种方案适合的数量才能导致利润最优化(为了方便我们在未知数中间体现) 同样没有利润值,要计算出来表(四)蓝色单元格 step2 系统变量 产品描述生产方案 未知数规划结果 甲 甲产品可以在 ab任何机器上 加工 a1,b1u10 a1,b2u2664 a1,b3u3536 a2,b1u40 a2,b2u5195 a2,b3u635 乙 乙在a任意,但 b只能在b1 a1,b1u70 a2,b1u8500 丙丙只在a2,b2a2,b2u9324 step3 目标函数 max z= 1*(u1+u2u+u3u+u4u+u5+u6)+1.63*(u7+u8)+2.3*u9 step4 约束条件 ui0 ui整数 5*(u1+u2+u3)+10*u7 6000 a1机器约束 7*(u4+u5+u6)+9*u8+12*u9 10000 a2机器约束 6*(u1+u4)+8*(u7+u8) 4000 b1机器约束 4*(u2+u5)+11*u9 7000 b2机器约束 7*(u3+u6) 4000 b3机器约束 step5 把约束条件转化成“规划求解“数字格式并求解 max z=3000.2 6000 6000 9998 10000 4000 4000 7000 7000 39974000 三三. .套套裁裁下下料料问问题题 例6 某工厂要做500套钢架,每套刚架分别需要2.9m,2.1m,1.5m的圆钢各一条,已知每根原料长度为 7.4m,问该如何下料,最省 s.t. s.t. 解: step1 解题 使用料最省的另外表达方式是什么呢?一种是使用的原料根数最少,应外一种理解是抛弃的废 料最少,也许很多时候是一样,也有不一样的时候 我们要确定分析方向,这2种分别进行计算 长度案1案2案3案4案5案6案7案8 2.91211 2.122113 1.5312314 使用总长7.47.37.27.16.66.56.36 原料长7.47.47.47.47.47.47.47.4 废料长00.10.20.30.80.91.11.4 未知数s1s2s3s4s5s6s7s8 求解值401601101400000 step2 系统变量 按照上面的几种方案分别设置未知数为s1-8 step3 目标函数 min z2= s1+s2+s3+s4+s5+s6+s7+s8根数最少 step4 约束条件 si整数 si0 s1+2s2+s4+s6 =500 2s3+2s4+s5+s6+3s7 =500 3s1+s2+2s3+3s5+s6+4s8 =500 step5 把约束条件/目标函数转化为“规划求解“格式 min z2=450废料80 500 =500 500 =500 500 =500 另外一种以废料最少为目标进行优化 长度案1案2案3案4案5案6案7案8 2.91211 2.122113 1.5312314 废料长00.10.20.30.80.91.11.4 求解值77123731770000 step2 系统变量 按照上面的几种方案分别设置未知数为s1-8 step3 目标函数 min z2= suproduct(c240:j240,c242:j242)废料最少 step5 把约束条件/目标函数转化为“规划求解“格式 min z2=80根数450 500 =500 500 =500 500 =500 所以,在同样的问题,不一样的考虑的时候,会得到的结果与方案也是不一定一样的,也许有差别的 故而我们需要多方位多角度的进行考虑 虽然同样的结果但是也有不同的开裁方案, 四四. .配配料料问问题题 例7 某化工厂根据一项合同要为用户生产一种用甲乙两种原材料混合配比而成的特殊产品,甲乙两种 原材料分别含有abc三种化学成分,请含量如下图,厂房如何配比这种产品是成本最少? s.t. s.t. s.t. 化化学学成成分分 原 原料料 甲乙 产品成分 最低含量 a1234 b232 c3155 单位成本32 求a-e的最短距离 经过节点进出之和目标 ab121a1 =1 ab240b10 =0 b1c131b20 =0 b1c230c10 =0 b1c310c20 =0 b2c120c30 =0 b2c230d10 =0 b2c310d20 =0 c1d130d30 =0 c1d290d40 =0 c1d320e-1 =-1 c1d411 c2d130 c2d210 c2d340目标函数9 c2d4