运筹学线性规划在管理中的应用案例

第五章运筹学线性规划在管理中

的应用案例（总18页）-本页仅作为预览文档封面，使用时请删除本页-#x8＋x9＋x10＋x11x9＋x10＋x11＋x12x1，x2，x3，x4，x5，x6，x7，x8x9，x10，将该模型代入到线性规划求解模板得结果：其解为：xi=8,x2=l，X3=1，X4=0，X5=0，X6=0，X7=1，x8=4,Xg=5,Xud=1,X11=0,xi2=0最优值为332。在满足对职工需求的条件下，在10时新安排临时工8个；时新安排临时工1个；时新安排临时工1个；时新安排临时工1个；时新安排临时工4个；时新安排临时工5个；时新安排临时工1个。全天共安排21个临时工，其中18时以前安排的20人是连续上四小时班，19时安排的一人上3小时班。可使临时工的总成本最小为332元。如下表所示：时间段所需临时工安排上班人数实际上班人数剩余人数10:00-11:008888-8=011:00-12:009199-9=012:00-13:00911010-9=113:00-14:00701010-7=314:00-15:002022-2=015:00-16:001011-1=016:00-17:001111-1=017:00-18:005455-5=018:00-19:001051010-10=019:00-20:001111111-11=020:00-21:00601010-6=421:00-22:006066-6=0合计7521838灵敏度分析报告：2、这时付给临时工的工资总额为332元,一共需要安排83个临时工的班次。根据剩余变量的数字分析可知，可以让10时安排的8个人中留3人工作3小时，就可以将13-14时多余的3个工时省下来；同时17时安排的4个人工作3小时，也可将20时的4个工时省下来使得总成本更小。这时只有12-13时间段剩余1人，其它时间段都没有剩余的人员，所以总的班次只用76个，总费用将是76X4=304元。

设在11：00-12：00这段时间内有x3个班是3小时，x4个班是4小时；其他时段也类似。得线性规划数学模型：minz=12x1+12x3+12x5+12x7+12x9+12x11+12x13+12x15+12x17+12x19+8x21+4x23+16x2+16x4+16x6+16x8+16x10+16x12+16x14+16x16+16x18+12x20+8x22+4x24S．S．T x1＋x2x1＋x2＋x3＋x4x1＋x2＋x3＋x4＋x5＋x6x2＋x3＋x4＋x5＋x6＋x7＋x8x4＋x5＋x6＋x7＋x8＋x9＋x10x6＋x7＋x8＋x9＋x10＋x11＋x1214x8＋x9＋x10＋x11＋x12＋x13＋xx10＋x11＋x12＋x13＋x14＋x15＋x1614x12＋x13＋x14＋x15＋x16＋x17＋x18x14＋x15＋x16＋x17＋x18＋x19＋x20x16＋x17＋x18＋x19＋x20＋x21＋x22x18＋x19＋x20＋x21＋x22＋x23＋x24xi>0i=1,2,…,24将该模型代入到线性规划求解模板得结果：其解为：在满足对职工需求的条件下，10时安排8个临时工，其中3个3小时的，5个4小时的；11时新安排1个4小时的临时工；13时新安排1个3小时的临时工；16时新安排1个4小时的临时工；17时新安排4个3小时的临时工；18时新安排5个4小时的临时工；19时新安排1个3小时临时工。全天共安排21个临时工，可使临时工的总成本最小为300元。如下表所示：时间段所需临时工4小时班人数3小时班人数实际上班人数剩余人数10:0011:008538011:0012:009109012:0013:009009013:0014:007017014:0015:002002015:0016:001001016:0017:001101017:0018:005045018:0019:00105010019:0020:00110111020:0021:006006021:0022:0060060合计75129750这样能比第一种方案节省：332-300=32元。灵敏度分析报告：某咨询公司受厂商的委托对新上市的产品进行消费反映调查。被调查对象分为上班族和休闲族，而调查时间在周一至周五与双休日得到的结果大不相同。委托厂商与该公司签订的业务合同规定：（1）必须调查3000个消费对象；（2）周一至周五与双休日被调查的总人数相等；（3）至少要调查1200个上班族对象；（4）至少要调查800个休闲族对象。调查每个对象所需费用如下表：调查对象周一至周五调查双休日调查上班族3540休闲族25281、请建立该问题的线性规划数学模型，以确定在不同时间调查各种对象的人数，使得总的调查费用为最少。2、求解该模型，并对结果进行灵敏度分析。解：1、线性规划数学模型：min35x1+40x2+25x3+28x4.x1+x2+x3+x423000

x1-x2+x3-x4=0xx1-x2+x3-x4=0x1+々21200演+x42800x1，x2，x3，x420代入线性规划求解模板得结果：EhmI域性胡加横后[>lllrl$lH：llljlElLllilTlolplQtItnLj?J■F771I其调查方案如下表：调查对象周一至周五调查双休日调查上班族12000休闲族3001500按此方案的调查费用为最少：91500元。2、灵敏度分析报告：即：目标函数最优值为:91500变量最优解相差值x112000x202x33000x415000约束松弛/剩余变量对偶价格102030-10410000目标函数系数范围:变量下限当前值上限x1253537x23840无上限x3232535x4-252830常数项数范围:约束下限当前值上限124003000无上限2-6000300030120015004无下限8001800西兰物业公司承担了正大食品在全市92个零售点的肉类、蛋品和蔬菜的运送业务。运送业务要求每天4点钟开始从总部发货，送完货时间必须在7：30前结束（不考虑空车返回时间）。这92个零售点每天需要运送货物吨，其分布情况为：5公里以内为A区，有36个点，从总部到该区的时间为20分钟；10公里以内5公里以上的为B区，有26个点，从总部到该区的时间为40分钟；10公里以上的为C区，有30个点，从总部到该区的时间为60分钟；A区各点间运送时间5分钟；B区各点间运送时间10分钟；C区各点间运送时间20分钟；各区之间运送时间20分钟。每点卸货、验收时间为30分钟。本公司准备购买规格为2吨的运送车辆，每车购价5万元。请用线性规划方法确定每天的运送方案，使投入的购买车辆总费用为最少。1、解：本问题的目标是使投入的购买车辆总费用为最少，而实际上总的运输时间为最少时，也就确定了最少的车辆数量，本问题最少的运输时间为目标的得线性规划数学模型：minz=155x1+170x2+170x3+175x4+185x5+185x6+190x7+200x8+180x9+190x10+200x11+210x12.4X1+3X2+3X3+2X4+2X5+2%+X7+X8+x9+0x10+0x11+0x12»360x1+1x2+0x3+2x4+1x5+0x6+2x7+1x8+3x9+4x10+3x11+2x12226

0x1+0%2+1x3+0%4+1x5+2x6+x7+2x8+0x9+0x10+xn+2x12230代入线性规划求解模板得结果：即整理如下表：路线123456789101112结果0000015006200A433222111000B010210213432C001012120012运送时间155170170175185185190200180190200210最少的运输时间4235小时。需要车辆23台，最小的购车费用23*5=115万元。灵敏度分析报告：目标函数最优值为:4235变量最优解相差值x105x2010x30x405x50x6150x70x805x960x1020x110x1205约束松弛/剩余变量对偶价格102030-55目标函数系数范围:变量下限当前值上限x1150155无上限x2160170无上限x3170无上限x4170175无上限x5185无上限x675185190x7190无上限x8195200无上限x9180x10190x11200无上限x12205210无上限常数项数范围:约束下限当前值上限3036130362 18 26 无上限3 30 36这里从对偶价格可见，A区每增加一个点，需要增加投入分钟；B区每增加一个点，需要增加投入分钟；C区每增加一个点，需要增加投入55分钟。这完全符合实际。若直接用购车数量最少做为目标可将线性规划数学模型改为：12minz=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x124x1+3x2+3x3+2x4+2x5+2X6+x7+x8+X9+0X10+0X11+0X12»360x1+1x2+0x3+2x4+1x5+0x6+2x7+1x8+3x9+4x10+3x11+2x122260x1+0x2+1x3+0x4+1x5+2x6+x7+2x8+0x9+0x10+x11+2x12230代入线性规划求解模板得结果：路线123456789101112结果00001500000A433222111000B010210213432C001012120012运送时间155170170175185185190200180190200210即需要车辆23台，最小的购车费用23*5=115万元。但车辆台数为非整数，这是不合理的，但要去尾取整或四舍五入也都肯定不合理。所以对这类问题这种方法还是有局限性。好则线性规划有专门处理这类问题的方法 整数规划。若用整数规划得以下结果：路线123456789101112结果2000014000601A433222111000B010210213432C001012120012运送时间155170170175185185190200180190200210即需要车辆23台，最小的购车费用23*5=115万元。某公司生产A、B、C、D四种规格的电子产品，这四种产品可以分别在五个不同的生产车间单独制造，这五个车间单独制造一件产品所需要时间、各车间可提供的总可制造时间及每件产品的利润如下表：产品型号所需时间（分钟）单件利润（元）车间1车间2车间3车间4车间5A5642320B833418C62424D534230可提供的总时间2000018000160001400015000该公司销售人员提供信息：（1）产品A的销售数量不会超过1500件；（2）产品B的销售数量在500-900件之间；（3）产品C销售数量不会超过6000件；（4）产品D至少能销售800件，在此基础，生产多少能销售多少。请制定一个生产方案，使得该公司的总利润为最大。解：线性规划数学模型：MaxZ=20x1+18x2+24x3+30x45x1+8x2+5x4W200006x1+3x2+6x3W180004x1+2x3+3x4W160002x1+3x2+4x3+4x4W140003x1+4x2+2x4W15000x1W1500x2W900x22500

演W6000x42800x1、x1、x2、x3、x420用求解模型板求得结果：即：安排产品A、B、C、D的产量分别为1050、900、1500、800件，得最多的利润为97200元。灵敏度分析报告：目标函数最优值为:97200变量最优解相差值x110500x29000x31