运筹学试验报告侯小洁-1

运筹学实验报告学院：安全与环境工程学院姓名：侯小洁学号：1350940109专业：物流工程班级：1301班实验时间：5月6、8日5月13、15日5月20、22日湖南工学院安全与环境工程学院2015年5月实验一线性规划一、实验目的1、理解线性规划的概念。2、对于一个问题，能够建立基本的线性规划模型。3、会运用Excel解决线性规划电子表格模型。二、实验内容线性规划的一大应用适用于联邦航空公司的工作人员排程，为每年节省开支超过600万美元。联邦航空公司正准备增加其中心机场的往来航班，因此需要雇佣更多的客户服务代理商，但是不知道到底要雇用多少数量的代理商。管理层意识到在向公司的客户提供令人满意的服务水平的同时必须进行成本控制，因此，必须寻找成本与收益之间合意的平衡。于是，要求管理团队研究如何规划人员才能以最小的成本提供令人满意的服务。分析研究新的航班时间表，以确定一天之中不同时段为实现客户满意水平必须工作的代理商数目。在表1.1最后一栏显示了这些数目，其中第一列给出对应的时段。表中的其它数据反映了公司与客户服务代理商协会所定协议上的一项规定，这一规定要求每一代理商工作8小时为一班，各班的时间安排如下：轮班1：6:00AM～2:00PM轮班2：8:00AM～4:00PM轮班3：中午～8:00PM轮班4：4:00PM～午夜轮班5：10:00PM～6:00AM表中打勾的部分表示这段时间是有相应轮班的。因为轮班之间的重要程度有差异，所以协议中工资也因轮班所处的时间而不同。每一轮班对代理商的补偿（包括收益）如最低行所示。问题就是，在最低行数据的基础上，确定将多少代理商分派到一天之中的各个轮班中去，以使得人员费用最小，同时，必须保证最后一栏中所要求的服务水平的实现表1.1联邦航空公司人员排程问题的数据轮班的时段时段12345最少需要代理商的数量6:00AM～8:00AM√488:00AM～10:00AM√√7910:00AM～中午√√65中午～2:00PM√√√872:00PM～4:00PM√√644:00PM～6:00PM√√736:00PM～8:00PM√√828:00PM～10:00PM√4310:00PM～午夜√√52午夜～6:00AM√15每个代理商的每日170160175180195成本实验要求:（1）如何规划人员才能以最小的成本提供令人满意的服务？（2）根据实验内容自行设计模型，求解最优方案。三、实验步骤(1)联邦航空公司问题的数学表述将问题的目标以及约束条件转化成为一组数学关系，这一过程通常称为数学模型。完整的数学模型如下：令Xi=分配到轮班i的代理商（其中i=1,2,3,4,5）,MinZ=170S1+160S2+175S3+180S4+195S5约束条件：6:00AM～8:00AM总的代理商数：X1≧488:00AM～10:00AM总的代理商数：X1+X2≧7910:00AM～中午总的代理商数：X1+X2≧65中午～2:00PM总的代理商数：X1+X2+X3≧872:00PM～4:00PM总的代理商数：X2+X4≧644:00PM～6:00PM总的代理商数；X3+X4≧736:00PM～8:00PM总的代理商数：X3+X4≧828:00PM～10:00PM总的代理商数：X4≧4310:00PM～午夜总的代理商数：X4+X5≧52午夜～6:00AM总的代理商数：X5≧15(2)在工作表中建模在一个工作表中建立线性规划模型，包括以下步骤：第一步在工作表的顶部输入数据。单元格B5:F14表示各时段中有无相应轮班。单元格G5:G14表示每个时段最少需要代理商的数量。单元格B15:F15表示每个代理商的每日成本。第二步确定每个决策变量所对应的可变单元格的位置。可变单元格B19:F19表示1-5个时段的代理商数量。第三步选择单元格输入公式，找到目标函数的值。单元格B20:=SUMPRODUCT(B15:F15,B19:F19)第四步选择一个单元格输入公式，计算每个约束条件左边的值。单元格B23:=SUMPRODUCT(B5:F5,B19:F19)单元格B24:=SUMPRODUCT(B6:F6,B19:F19)单元格B25:=SUMPRODUCT(B7:F7,B19:F19)单元格B26:=SUMPRODUCT(B8:F8,B19:F19)单元格B27:=SUMPRODUCT(B9:F9,B19:F19)单元格B28:=SUMPRODUCT(B10:F10,B19:F19)单元格B29:=SUMPRODUCT(B11:F11,B19:F19)单元格B30:=SUMPRODUCT(B12:F12,B19:F19)单元格B31:=SUMPRODUCT(B13:F13,B19:F19)单元格B32:=SUMPRODUCT(B14:F14,B19:F19)第五步选择一个单元格输入公式，计算每个约束条件右边的值。对于这个模型中的4个条件，使单元格D23:=G5单元格D24:=G6单元格D25:=G7单元格D26:=G8单元格D27:=G9单元格D28:=G10单元格D29:=G11单元格D30:=G12单元格D31:=G13单元格D32:=G14（3）使用Excel求解第一步在数据菜单中选择Solver（规划求解），如图1.1。图1.1问题模型第二步当出现规划求解参数对话框（如图1.2）时，设置目标单元格B20，并选中最小值,使得求解的目标最小化。图1.2规划求解参数第三步在可变单元格中输入B19:F19。第四步添加约束对话框用来具体化所有的函数约束。点击“添加”按钮来实现，会弹出添加约束对话框,如图1.3图1.3约束结束对话框在单元格引用位置中输入B23:B32；在约束值框中输入D23:D32；中间符号选≧；第五步点击“选项”按钮弹出如图1.4所示的对话框，在对话框中细化求解选项，最重要的是“采用线性模型”和“假定非负”选项，其他为默认值。点击确定回到规划求解参数对话框。图1.4规划求解选项框第六步点击规划求解参数对话框中的“求解”按钮，开始对问题求解。几秒钟之后（对于一个小型问题），就会显示运行结果，本题得到一个最优解，如图1.5。求解模型之后，Solver（规划求解）用最优值代替了可变单元格中的初始值。图1.6完整模型四、实验结果如图1.6是电子表格的最优解，最优解为:6:00AM～8:00AM轮班人数为48；8:00AM～10:00AM轮班人数为79；10:00AM～中午轮班人数为79；中午～2:00PM轮班人数为118；2:00PM～4:00PM轮班人数为70；4:00PM～6:00PM轮班人数为82；6:00PM～8:00PM轮班人数为82；8:00PM～10:00PM轮班人数为43；10:00PM～午夜轮班人数为58；午夜～6:00AM轮班人数为15；最低成本为30610元。实验二指派问题一、实验目的（1）理解指派问题的特点。（2）对于一个指派问题，能够建立电子表格模型。（3）会运用Excel求解电子表格模型。二、实验内容塞尔默公司的营销经理将要主持召开一年一度的有营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他雇用了四个临时工（安、伊恩、琼、肖恩），每一个人负责完成下面的一项任务：书面陈述的文字处理；制作口头和书面陈述的电脑图；会议材料的准备，包括书面材料的抄写和组织；处理与会者的提前和当场注册报名；现在他需要确定要将哪一项任务指派个哪一个人。虽然这四个临时工都有完成这四项任务所需的基本能力，但是在他们完成每一项任务时所表现出来的有效程度是有很大差异的。表2.1示了每一个人完成每一项任务所用的时间（单位：小时）。最右一列给出了以每个人能力为基础的小时薪水。表2.1塞尔默公司问题的数据临时工每一项任务所需要的时间（小时）每小时工资文字处理绘图材料准备记录安3541274014伊恩4745325112琼3956364313肖恩3251254615实验要求：（1）塞尔默公司最优的指派方案。（2）根据实验内容自行设计模型，求解最优方案。（3）完成并提交实验报告。三、实验步骤（1）塞尔默公司指派问题的数学表述设xij表示每个临时工完成一项任务的时间；i表示临时工（1安；2伊恩；3琼；4肖恩）；j表示任务（1文字处理；2绘图；3材料准备；4记录）。所以，将福尔指派问题的决策可变量定义如下1表示临时工是i，任务是jx11=0其他情况这里i=1，2，3，4；j=1，2，3，4。安完成指派所用的时间=x11+x12+x13+x14伊恩完成指派所用的时间=x21+x22+x23+x24琼完成指派所用的时间=x31+x32+x33+x34肖恩完成指派所用的时间=x41+x42+x43+x444个临时工完成时间总和将提供完成4个指派所需要的时间。因此，目标函数如下：最小化x11+x12+x13+x14+x21+x22+x23+x24+x31+x32+x33+x34+x41+x42+x43+x44指派问题约束反映的情况如下：每个临时工将赋予一个任务，并且每个任务须被赋予一个临时工。这些约束条件如下：x11+x12+x13+x14安的指派x21+x22+x23+x24伊恩的指派x31+x32+x33+x34琼的指派x41+x42+x43+x44肖恩的指派x11+x21+x31+x41文字处理x12+x22+x32+x42绘图x13+x23+x33+x43材料准备x14+x24+x34+x44记录注意：每个节点都有一个约束条件。因为此处的临时工与任务的数量相等，所以所有的约束条件都可以写成等式。（2）在工作表中建立模型第一步：输入目标函数在B9单元格输入公式=SUMPRODUCT(B4:E4*F4*B13:E13+B5:E5*F5*B14:E14+B6:E6*F6*B15:E15+B7:E7*F7*B16:E16)说明完成所有任务最少的工资为1957。第二步：输入决策可变量单元格B13:E16。第三步:输入约束条件：左侧值F13:F16单元格包含了每个人分配的任务的左侧值约束条件，B17:E17包含了每个任务分配的人数的左侧值约束条件。单元格F13=SUM（求和)（B13:E13)（复制到F14:F16)单元格B17=SUM（求和)（B13:B16)（复制到C17:E17)右侧值H13:H16单元格为右侧值为每个人分配的任务的约束条件，B19:E19为右侧值每个任务分配人数约束条件，所有右侧值单元格的价值都为1（3）使用Excel求解在菜单的“数据”中选择“规划求解”，在对话框中的“规划求解参数”中输入正确的信息，如图2.1所示。图2.1规划求解参数然后选择“选项”。在图2.2中，具体说明“采用线性模型”，“假设非负”的选择。图2.2规划求解选项框四、实验结果实验结果如图2.3图2.3完整模型最优解为：分配安去做材料准备任务；分配伊恩去做绘图任务；分配琼去做记录任务；分配肖恩去做文字处理任务；雇佣临时工的最少工资为1937元。实验三网络最优化--最短路问题一、实验目的（1）理解网络最优化问题的特点和实质。（2）对于一个最短路问题，能够建立电子表格模型。（3）会运用Excel求解电子表格模型。二、实验内容莎拉刚刚高中毕业。在毕业典礼上，他的父母给了她21000美元的汽车基金帮助她购买并保养一辆使用了三年的二手车，以供她上大学使用。由于开车费用和维修费用随着汽车的老化而飞速上涨，所以莎拉的父母告诉她在接下来的三个夏天里，她也可以一次或几次折价将她的汽车置换为其它使用了三年的二手车。如果她觉得这样做可以使它的总净成本最小的话，他们会同意她这样做的。他们也告诉莎拉，在四年后，他们会送给她一辆新车作为大学毕业的礼物。所以莎拉到那时肯定要计划把旧车折价卖出。下表3.1给出了每个时期莎拉购买一辆使用了三年的二手车的相关数据。例如，如果她两年后折价卖掉自己的车，那么在三年级时她就对下一辆车有一年的所有权，其他情况以此类推。表3.1莎拉每个时期购买一辆使用了三年的二手车的数据购买价格拥有年份的开车和保养的费用（美元）最后一年卖出的价值（美