运筹学实验报告.doc

运筹学实验报告 学院： 安全与环境工程 姓名： 许俊国 学号： 1350940219 专业： 物流工程 班级： 物流1302班 实验时间： 5月8日、 5月9日 5月13日、5月14日 5月20日、5月21日湖南工学院安全与环境工程学院2015年5月实验一 线性规划一、 实验目的1、理解线性规划的概念。2、对于一个问题，能够建立基本的线性规划模型。3、会运用Excel解决线性规划电子表格模型。二、 实验内容线性规划的一大应用适用于联邦航空公司的工作人员排程，为每年节省开支超过600万美元。联邦航空公司正准备增加其中心机场的往来航班，因此需要雇佣更多的客户服务代理商，但是不知道到底要雇用多少数量的代理商。管理层意识到在向公司的客户提供令人满意的服务水平的同时必须进行成本控制，因此，必须寻找成本与收益之间合意的平衡。于是，要求管理团队研究如何规划人员才能以最小的成本提供令人满意的服务。分析研究新的航班时间表，以确定一天之中不同时段为实现客户满意水平必须工作的代理商数目。在表1.2的最后一栏显示了这些数目，其中第一列给出对应的时段。表中的其它数据反映了公司与客户服务代理商协会所定协议上的一项规定，这一规定要求每一代理商工作8小时为一班，各班的时间安排如下：轮班1：6:00AM2:00PM轮班2：8:00AM4:00PM轮班3：中午8:00PM轮班4：4:00PM午夜轮班5：10:00PM6:00AM表中打勾的部分表示这段时间是有相应轮班的。因为轮班之间的重要程度有差异，所以协议中工资也因轮班所处的时间而不同。每一轮班对代理商的补偿（包括收益）如最低行所示。问题就是，在最低行数据的基础上，确定将多少代理商分派到一天之中的各个轮班中去，以使得人员费用最小，同时，必须保证最后一栏中所要求的服务水平的实现。表1.1 联邦航空公司人员排程问题的数据轮班的时段时段 1 2 3 4 5 最少需要代理商的数量6:00AM8:00AM 488:00AM10:00AM 7910:00AM中午 65中午2:00PM 872:00PM4:00PM 644:00PM6:00PM 736:00PM8:00PM 828:00PM10:00PM 4310:00PM午夜 52午夜6:00AM 15每个代理商的每日成本 170 160 175 180 195三、实验步骤（1）明确实验目的：科学规划人员以最小的成本提供令人满意的服务。（2）分析题目，定义决策变量：由题意可得，本题有五个决策变量，即：轮班1需要的人数：X1轮班2所需要的人数：X2轮班3需要的人数：X3轮班4所需要的人数：X4轮班5所需要的人数：X5（3）根据决策变量写出模型目标：总成本=170X1+160X2+175X3+180X4+195X5（4）根据决策变量写出约束条件：约束条件1： （轮次1在6:00AM8:00AM时间段需要代理商的数量）（要求的最少人数）所以 X148约束条件2： （轮次1、轮次2在8:00AM10:00AM时间段需要代理商的数量）（要求的最少人数）所以 X1+X279约束条件3： （轮次1、轮次2、在10:00AM中午时间段需要代理商的数量）（要求的最少人数）所以 X1+X265约束条件4： （轮次1、轮次2、轮次3在中午2:00PM时间段需要代理商的数量）（要求的最少人数）所以 X1+X287约束条件5： （轮次2、轮次3在 2:00PM4:00PM时间段需要代理商的数量）（要求的最少人数）所以 X2+X364约束条件6： （轮次3、轮次4在 4:00PM6:00PM时间段需要代理商的数量）（要求的最少人数）所以 X3+X473约束条件7： （轮次3、轮次4在6:00PM8:00PM 时间段需要代理商的数量）（要求的最少人数）所以 X3+X482约束条件8： （轮次4在8:00PM10:00PM时间段需要代理商的数量）（要求的最少人数）所以 X443约束条件9： （轮次4、轮次5在10:00PM午夜时间段需要代理商的数量）（要求的最少人数）所以 X4+X552约束条件10： （轮次5在午夜6:00AM时间段需要代理商的数量）（要求的最少人数）所以 X515其它约束条件：人员成本不能是负值，所以 X1、X2、X3、X4、X50（5）依上所述，建立数学模型：Min Z=170X1+160X2+175X3+180X4+195X5 s.t X148 X1+X279 X1+X265 X1+X287 X2+X364 X3+X473 X3+X482 X443 X4+X552 X515 X1，X2，X3,X4，X50（6）在工作表中建模：在excel表格中依次输入每个时间段最少需要代理商人员数量、时间段、每个轮次各个时间段安排的代理商人员人数。图1.1.1代理商人员数量、时间段、，每个轮次安排的代理商人员数（7）选择单元格，在表中确定决策变量。图1.1.2确定决策变量（8）选择单元格，输入公式，确定目标函数的值。图1.1.3确定目标函数（9）选择单元格输入公式sumproduct，计算每个约束条件两边的值.图1.1.4用函数sumproduct求解约束条件两边的值（10）进行规划求解图1.1.5规划求解参数（11）得出答案：图1.1.6得出最少成本四、实验结果根据求的结果，轮班1应该指派48个代理商人员，轮班2应该指派31个代理商人员，轮班3应该指派39个代理商人员，轮班4应该指派43个代理商人员，轮班5应该指派15个代理商人员。此时，最小规划成本为30610元。实验二 线性规划一、 实验目的1、理解指派问题的特点。2、对于一个指派问题，能够建立电子表格模型。3、会运用Excel求解电子表格模型。二、实验内容塞尔默公司的营销经理将要主持召开一年一度的有营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他雇用了四个临时工（安、伊恩、琼、肖恩），每一个人负责完成下面的一项任务：书面陈述的文字处理；制作口头和书面陈述的电脑图；会议材料的准备，包括书面材料的抄写和组织；处理与会者的提前和当场注册报名；现在他需要确定要将哪一项任务指派个哪一个人。虽然这四个临时工都有完成这四项任务所需的基本能力，但是在他们完成每一项任务时所表现出来的有效程度是有很大差异的。表2.3显示了每一个人完成每一项任务所用的时间（单位：小时）。最右一列给出了以每个人能力为基础的小时薪水。表2.1 塞尔默公司问题的数据临时工 每一项任务所需要的时间（小时） 每小时工资 文字处理 绘图 材料准备 记录安 35 41 27 40 14伊恩 47 45 32 51 12琼 39 56 36 43 13肖恩 32 51 25 46 15 三、实验步骤（1）明确题目目的：本题目的对人员进行合理安排，使所耗费的资本最少。（2）分析题目，定义决策变量：该指派问题是一个特殊的可以用线性规划方程的运输问题。给每个节点都赋予约束条件，并对每个弧都赋予一个参数。在运输问题中，使用双下标决策可变量。X11代表项目临时工（安）和任务1，X12代表项目临时工（安）和任务2，依次类推。所以，将福尔指派问题的决策可变量定义如下： 1表示临时工是，任务是 0其他情况这里=1，2，3，4；j=1，2，3,4使用表2.3中的符号和完成时间数据，我们得出了完成时间表达式：安完成指派共用时间:35X11+41X12+27X13+40X14伊恩完成指派共用时间:47X21+45X22+32X23+51X24琼完成指派共用时间:39X31+56X32+36X33+43X34肖恩完成指派共用时间:32X41+51X42+25X43+46X444个临时工完成时间的总和将提供完成4个指派任务所需要的时间总和。因此，目标函数如下： 35X11+41X12+27X13+40 X14+47X21+45X22+32X23+51X24+39X31+56X32+36X33+43X34+32X41+51X42+25X43+46X44（3）根据决策变量写出约束条件：指派问题约束反映的情况如下：每个临时工被赋予一项任务，并且每项任务被赋予一个临时工。这些约束条件如下：安的指派：X11 + X12 + X13 + X14 = 1伊恩的指派：X21 + X22 + X23 + X24 = 1琼的指派：X31 + X32 + X33 + X34 = 1肖恩的指派：X41 + X4 2+ X43 + X44 = 1文字处理：X11 + X21 X31 X41 = 1绘图：X12 + X22 + X31 + X42 = 1材料准备：X13 + X23 + X33 + X43 = 1记录：X14 + X24 + X34 + X44 = 1（4）根据步骤（2）（3）写出模型目标函数，并建立数学模型：Min Z = 35X11+41 X12+27 X13+40 X14+47X21+45X22+32X23+51X24+39X31+56X32+36X33+43X34+32X41+51X42+25X43+46X44s.t： X11 + X12 + X13 + X14 = 1 X21 + X22 + X23 + X24 = 1 X31 + X32 + X33 + X34 = 1 X41 + X4 2+ X43 + X44 = 1 X11 + X21 X31 X41 = 1 X12 + X22 + X31 + X42 = 1 X13 + X23 + X33 + X43 = 1 X14 + X24 + X34 + X44 = 1 =1，2，3，4；j=1，2，3,4（5）在工作表中建模：根据题意，在excel表格中输入相应的数据：图2.1.1在表中输入与题目相关的数据（6）在excel中确定决策变量的位置，利用sumproduct函数进行求解:图2.1.2确定决策变量，并输入sumproduct函数（7）在规划求解中输入约束条件：图2.1.3规划求解参数（8）求解，得出答案：图2.1.4求解得出最少薪资四、实验结果根据excel表格求解：所以安排安从事材料准备工作，伊恩从事绘图工作，琼从事记录工作，肖恩从事文字处理工作，有最小薪资成本为1957元。实验三 线性规划一、实验目的1、理解网络最优化问题的特点和实质。2、对于一个最短路问题，能够建立电子表格模型。3、会运用Excel求解电子表格模型。二、 实验内容3.1里特城（Littletown）是一个农村的小镇。它的消防队要为包括许多农场社区在内的大片地区提供服务。在这个地区里有很多的路，从消防站到任何一个社区都有很多条路线。因为时间是到达火灾发生点的主要因素，所以消防队队长希望实现能够确定从消防站到每个农场社区的最短路。下图标示了连接消防站和其中一个农场社区的道路系统，图中包含了每条路的英里数。你能够找到从消防站到这个农场社区的最短路线吗？ 8AF 6 4BD 3 1 6 3 农场社区G 4 6消防站 6 E 5 3 5C 2 2 H 4 7 4 7图3.3中里特城的消防站和某一农场社区间的道路系统，其中，A，B，H是交叉口，每条路旁边的数字表示单位为英里的距离。三、实验步骤（1）根据题意，在excel表格中输入题中相关数据：图3.1.1在EXCEL表