管理运筹学

工程技术学院《管理运筹学》上机报告姓名：李雪序号：13指导老师：彭艳0目录一、线性规划................................................................................................................1二、运输问题................................................................................................................4三、整数规划问题........................................................................................................5四、指派问题................................................................................................................5五、最短路问题............................................................................................................8六、最小生成树问题....................................................................................................9七、最大流问题..........................................................................................................10八、最小费用最大流问题..........................................................................................10九、存储论问题..........................................................................................................11十、关键路径..............................................................................................................141一、线性规划（一）2（1）minf=6X1+4X2约束条件：2X1+X2≥13X1+4X2≥3X1，X2≥0解：图1-1图1-22由图1-2可知，线性规划的最优解是通过三次迭代后产生的，图1-1可知，该线性规划的结果为X1=0.2，X2=0.6，目标函数的最优解为3.6，第一个约束条件的对偶价格为-2.4，第二个约束条件的对偶价格为-0.4。（2）maxz=4X1+8X2约束条件：2X1+2X2≤10-X1+X2≥8X1，X2≥0解：图2：线性规划（2）由图2可以看出，所求出的线性规划问题的最优解中有人工变量大于零，-3M+40＞0，所以次线性规划问题无可行解。（3）maxz=X1+X2约束条件：8X1+6X2≥244X1+6X2≥-122X2≥4X1，X2≥0解：3图3：线性规划（3）通过运筹学软件分析可得图3的结果，此线性规划问题为无界解。（4）maxz=3X1-2X2约束条件：X1+X2≤22X1+2X2≥4X1，X2≥0解：图4：计算过程图由图4可得知，此线性规划问题无可行解。4二、运输问题（一）某集团在全市拥有四个分公司，员工数分别为300人、300人、200人、200人，本着人性化管理理念，考虑为员工定制牛奶，先准备通过三家牛奶供应商为为各公司配送牛奶，三家公司可提供的配送量牛奶，三家公司可提供的配送量分别为500个、200个、400个，由于距离原因，相应的单位运价如下表所示，请问如何定制牛奶使总费用最小。表1：四家分公司单位运价表分公司供应商分公司1分公司2分公司3分公司4供应商10.30.70.60.4供应商20.20.40.30.2供应商30.40.30.80.5解：A1、A2、A3三个供应商的总配送量为1100个，B1、B2、B3、B4四个分公司的总需求量为1100个，总需求量等于总配送量，这是一个产销平衡问题设Xij表示从Ai配送牛奶到Bj的运输量（i=1、2、3，j=1、2、3、4），在运筹学软件中输入由题目所知的数据，由图1所示：图5：运筹学软件中得运费单价表图6：运输问题最优解图5得出的最优方案，X11=300，X12=0，X13=0，X21=0，X22=0，X23=200，X31=0，X32=300，X33=0，minf=320。三、整数规划问题（一）Maxz=3X1+2X2约束条件：2X1+3X2≤142X1+X2≤9X1，X2≥0，且X1为整数解：图7：整数规划最优解图此问题是求目标函数的最大值，求出的最优解，X1=1，X2=2，第一个约束条件的松弛变量为9，第二个约束条件的松弛变量为6，最优目标函数为5。四、指派问题（一）表2：4位工人完成各项工作所消耗的时间表ABCD甲20192028乙18242720丙26161518丁17202419（1）应指派哪个工人去完成哪项工作，可使消耗的时间为最少？（2）如果把（1）中的消耗时间数据看成创造效益的数据，那么如何指派，可使消耗时间工作工人6的总的效益最大？（3）如果在（1）中再增加一项工作E，甲乙丙丁4人完成工作E的时间分别为17,20,15,16分钟，那么应指派这4人干哪4项工作，使得这4人总的消耗时间为最少？（4）如果在（1）中在增加一个人戊，他们完成ABCD工作的时间分别为16，17，20，21分钟，这时应指派哪4人去干这4项工作，使得总消耗时间最少？解：（1）图8：（1）问题的最优值方案一：指派甲去完成B工作，乙去完成D工作，丙去完成C工作，丁去完成A工作，总的消耗时间为71分钟；方案二：指派甲去完成B工作，乙去完成A工作，丙去完成C工作，丁去完成D工作，总的消耗时间为71分钟。7（2）图9：（2）问题的最优解图指派甲去完成D工作，乙去完成B工作，丙去完成A工作，丁去完成C工作，可使得总的效益最大，值为102。（3）图10：（3）问题最优解图增加一项E工作后，指派甲去完成B工作，乙去完成A工作，丙去完成C工作，丁去完成E工作，这4人总的消耗时间为68分钟。8（4）图11：（4）问题最优解图方案一为指派甲去完成B工作，丙去完成C工作，丁去完成D工作，戊去完成A工作，甲、丙、丁、戊4人的总消耗时间为69分钟；方案二为指派乙去完成A工作，丙去完成C工作，丁去完成D工作，戊去完成B工作，乙、丙、丁、戊4人的总消耗时间为69分钟。五、最短路问题（一）某一配送中心要给一个快餐店送快餐原料，应按照什么路线送货才能使送货时间最短？解：9图12：最短路问题最优解图通过图12可以看出此问题的结果，此问题是始点为1，终点为2的无向图问题，从节点1到节点7的最短路为V1-V2-V3-V5-V7，所需时间为27分钟。六、最小生成树问题（一）设计一个输电网络，联通8个居名点，使得总输电线路的长度为最短。解：图13：第八题最优解10从节点1到节点8的最短路径为V1-V3-V4-V8，最短距离为11。七、最大流问题（一）求出最大流量。解：图14：最大流问题图通过对数据的录入，点击解决按钮后，可以得出最大流问题的最优解。计算过程为：①V1-V3-V6，流量为5千辆每小时；②V1-V4-V6，流量为6千辆每小时；③V1-V2-V5-V6，流量为6千辆每小时；④V1-V3-V4-V5-V6，流量为5千辆每小时，所以V1到V6的最大流为2万2千辆每小时。八、最小费用最大流问题（一）求最小费用最大流。解：11图15：最小费用最大流最小费用为39，最大流为5。计算过程为：①V1-V3-V5-V6，最大流为3，单位费用之和为6；②V1-V3-V2-V4-V6，最大流为1，单位费用之和为10；③V1-V2-V4-V6，最大流为5，单位费用之和为11，最小费用=3x6+1x10+11x1=39，最大流为①＜②＜③=5。九、存储论问题（一）假设某工厂需要外购某一个零件，年需求为4800件，单价为40元，每次的订购费用为350元，每个部位存储一年份的费用为每个部件的价格的25%，又假设每年有250个工作日，该部件需要提前5天订货（既订货后5天可送货到厂），不允许缺货，请求出：（1）经济订货批量；（2）再订货点（既当部件存储量降为多少时，应该再订货）；（3）两次订货所间隔的时间；（4）每年订货与存储的总费用。解：12图16：经济订货批量模型图（1）最优经济订货批量为580件。（2）当部件存储量降为96件时，应该再订货。（3）两次订货所间隔的时间为30天。（4）每年订货与存储的总费用为5796元。（二）某出版社要出版一本工具书，估计其每年的需求率为常量，每年需求18000套，每套的成本为150元。每年的存储成本率为18%，其每次生产准备费为1600元，印刷该书的设备生产率为每年30000套，假设该出版社每年250个工作日，要组织一次生产的准备时间为10天，请用不允许缺货的经济生产批量的模型，求出：（1）最优经济生产批量；（2）每年组织生产次数；（3）两次生产间隔时间；（4）每次生产所需时间；解：13图17：经济生产批量模型图（1）最优经济生产批量为2309套。（2）每年组织生产次数为8次。（3）两次生产间隔时间为32天。（4）每次生产所需时间（三）某旅游鞋专卖店，出售一种高质量品牌的旅游鞋，根据以往的统计，已知其需求率近似于常量为每年2000双，该专卖店每次订货费为300元，其进货价格是根据进货数量的不同而不同的，如表3所示，存储成本为20%，请求最小成本的订货批量，该专卖店以前每次订货量为500双，这种做法每年要比最小成本的订货批量要多花多少钱？表3：订货数量及每双价格订货数量每双价格\元0-99360100-199320200-299300300双或更多280解：14图18：经济订货批量折扣模型根据图可得出最小成本的订货批量为300双。每年订货成本为2000元，每年存储成本为8400元，最大存储水平为300双。十、关键路径（一）请计算出每个工序的最早开始时间，最晚开始时间，最早完成时间，最晚完成时间；找出关键工序；找出关键路线；并求出完成此工程项目所需最少时间。表4：各工序所需时间以及紧前工序表工序紧前工序所需时间/天a—2b—4ca,b5da,b4eb3fc2gd,c4解：15图19-1图19-2将数据输入图19-2，可以得出图19-2的结论：①表4：每个工序的最早开始时间，最晚开始时间，最早完成时间，最晚完成时间表工序数最早开始时间最晚开始时间最早完成时间为最晚完成时间为A0022B0044C45910D4488E4578F9101112G881212②关键工序为B、D、G；③关键路线B—D—G；④完成此工程项目所需最少时间为12天。