运筹学实验报告

《运筹学实验报告》由会员分享，可在线阅读，更多相关《运筹学实验报告（16页珍藏版）》请在装配图网上搜索。

1、运筹学实验报告学院：安全与环境工程姓名：学号：专业：物流工程班级：物流1302班实验时间：5月8日、5月9日5月13日、5月14日5月20日、5月21日湖南工学院安全与环境工程学院2015年5月实验一线性规划一、实验目的1、理解线性规划的概念。2、对于一个问题，能够建立基本的线性规划模型。3、会运用Excel解决线性规划电子表格模型。二、实验内容线性规划的一大应用适用于联邦航空公司的工作人员排程，为每年节省开支超过600 万美元。联邦航空公司正准备增加其中心机场的往来航班，因此需要雇佣更多的客户服务代理 商，但是不知道到底要雇用多少数量的代理商。管理层意识到在向公司的客户提供令人满 意的服务水

2、平的同时必须进行成本控制，因此，必须寻找成本与收益之间合意的平衡。于 是，要求管理团队研究如何规划人员才能以最小的成本提供令人满意的服务。分析研究新的航班时间表，以确定一天之中不同时段为实现客户满意水平必须工作的 代理商数目。在表1.2的最后一栏显示了这些数目，其中第一列给出对应的时段。表中的 其它数据反映了公司与客户服务代理商协会所定协议上的一项规定，这一规定要求每一代 理商工作8小时为一班，各班的时间安排如下：轮班 1： 6:00AM2:00PM轮班 2： 8:00AM4:00PM轮班3：中午8:00PM轮班4： 4:00PM午夜轮班 5： 10:00PM6:00AM表中打勾的部分表示这段

3、时间是有相应轮班的。因为轮班之间的重要程度有差异，所 以协议中工资也因轮班所处的时间而不同。每一轮班对代理商的补偿（包括收益）如最低 行所示。问题就是，在最低行数据的基础上，确定将多少代理商分派到一天之中的各个轮 班中去，以使得人员费用最小，同时，必须保证最后一栏中所要求的服务水平的实现。表1.1联邦航空公司人员排程问题的数据轮班的时段时段12345最少需要代理商的数量6:00AM8:00AMV488:00AM10:00AMVV17910:00 AM中午VV65中午2:00PMVVV872:00PM4:00PMVV644:00PM6:00PMVV1 736:00PM8:00PMVV828:00

4、PM10:00PMV1 4310:00PM午夜VV52午夜6:00AMV1 15每个代理商的每日成本170160175180195三、实验步骤（1）明确实验目的：科学规划人员以最小的成本提供令人满意的服务。（2）分析题目，定义决策变量：由题意可得，本题有五个决策变量，艮即轮班1需要的人数：X轮班2所需要的人数：X2轮班3需要的人数：X3轮班4所需要的人数：X4轮班5所需要的人数：X55（3）根据决策变量写出模型目标：总成本=170Xi+160X2+175X3+180X4+195X5（4）根据决策变量写出约束条件：约束条件1：（轮次1在6:00AM8:00AM时间段需要代理商的数量）M （要求的

5、最少人数）所以XM48约束条件2：（轮次1、轮次2在8:00AM10:00AM时间段需要代理商的数量）M（要求的最少人数）所以 XJX2M79约束条件3：（轮次1、轮次2、在10:00AM中午时间段需要代理商的数量）M（要求的最少 人数）所以 XjX2M65约束条件4：（轮次1、轮次2、轮次3在中午2:00PM时间段需要代理商的数量）M（要求的 最少人数）所以 XjX2M87约束条件5：（轮次2、轮次3在2:00PM4:00PM时间段需要代理商的数量）M（要求的最少 人数）所以 X2+X3M64约束条件6：（轮次3、轮次4在4:00PM6:00PM时间段需要代理商的数量）M（要求的最少 人数）

6、所以 X3+X4M73约束条件7：（轮次3、轮次4在6:00PM8:00PM时间段需要代理商的数量）M（要求的最少 人数）所以 X3+X4M82约束条件8：（轮次4在8:00PM10:00PM时间段需要代理商的数量）M（要求的最少人数）所以X4M43约束条件9：（轮次4、轮次5在10:00PM午夜时间段需要代理商的数量）M（要求的最少人 数）所以 X4+X5M52约束条件10：(轮次5在午夜6:00AM时间段需要代理商的数量)M(要求的最少人数)所以X5M15其它约束条件：人员成本不能是负值，所以 X1 x2 X3 x4 x5建0、(5) 依上所述，建立数学模型:Min Z=170Xi+160

7、X2+175X3+180X4+195X5s.t XM48XjXqgX+X2M65XJX*?X2+X3 = 64X3+X4M73Xf*X4EX4+X5 = 52X5=15X1，X2, X3，X4, #0(6) 在工作表中建模:在excel表格中依次输入每个时间段最少需要代理商人员数量、时间段、每个轮次各 个时间段安排的代理商人员人数。时段123S成贸害亶代理荷的散扯6：anAH-Si ODAJI1U488；UDAK-1U；UU?J(L10079mWijAM-中午11Q口0&E中牛一N. OQFM111OU87Z. OOFM4：OQFJIO11O0644:CiuPMB:uCiPMO011073Gi

8、OOPM-StOuPM0011nS3SSOOFM-IQSQPFM0UU1043Lu：ijUPM午夜O0011B2午在G:LiUAiO0011E，项割饱辱同弓出.17016017K1S0L9E(7) 选择单元格，在表中确定决策变量。轮班的时段时m12345蹑少需夔 代螺商的 散酸6：iji：iAN-S： 00 AN1000非1100a7310 = 0 0 AM 一中午1100065：r-2r OOPI1110aSTZj 0uPH-4：00PN0110064!IXiPM-&:ODPH011Q736 ; D0PW-8;0DPM011082B：00E=N-10iJ0FH0010习3to ； aoFM-

9、 一午夜0011S2牛帝6:00 AM1：100115E个代理向的甚日成卫1701601751 so19E模型轮L 轮土 花轮4 轮$决篥度里图1.1.2确定决策变量(8) 选择单元格，输入公式，确定目标函数的值。轮斑的时段日段123最.少栾，要代理育的妙6;QOAJl-g3 OOAJI10045S;QUAJ-1O;OOAJ110T91 Q ; aOAJI一中午110&5中午Tc JOFli11137% 0OFWl-4;OOPH011&44:0QPN-e ; OOFWl001T36;0QPN-3 ; OOFNl00132S;QUFH-1O;OOPII00D43io：iapN午夜00015N午夜

10、一一&;0 OAJI0001155.有的辱日赚1701GD17E180195模型轮1轮m轮甘决集变涅：最少成本c11图1.1.3确定目标函数(9) 选择单元格输入公式sumproduct，计算每个约束条件两边的值.-轮L轮3决策变量最少成木约条柴件轮班安排6 : OOAJit-S, OOjUiIFaF：riOAM-l ii : iiiIAHJ1.0 ： 6如T一中午0中午一!2, O0PMd2= noPM-4 : nnpM4 : 口（3FM一州-00PM06 -OOP1L-S ;：0OPM7aS:DOPM-LO : OOPM1 o：oopm-p牛夜：.口口心最少需要代理面的裁里4S7965S7

11、G47382435215图1.1.4用函数sumproduct求解约束条件两边的值(10) 进行规划求解规别 承峰鼻as谩HE曰诉：CIJfSihAS大fJS 31 O :as小ffi hit曰标仙：Qlaisi赠距F克早元脩： 虫b虫ie:ipiis通由勺克：C11Jw I -使无如未正演为非免散 g 谄撵市ftS方法：皿I 沌蚣隹裁有厂丘术斛力法通并龚美罪垛馨翻篥圈精瑙覆霆翳皂蜀噩引挈“ 为湘注规:剧术呷可皿您择*电敖性烦剧引金鄙生fit cn-i=tt.A.X-fT： IX用站冲. 京新g 点闻图1.1.5规划求解参数(11) 得出答案:模型轮L轮!2决策变量4G3J最少成本30&10约

12、束条件轮班安排6 :OOATrt-S； 00 AK438：f2pAr.-io：6oAn73li5: 口口心一中午79中午一口：OOFM1LS2. O0PM-4OOFM704:OOFM-6:0OPM26 :U0FM-8: OOPII322:0OPM-LO:O0FTrt431 0回皿一午夜说午夜一吕：门口邸15轮W39轮443最少斋姿代理商的数量宓7965FJ7647382435215图1.1.6得出最少成本四、实验结果根据求的结果，轮班1应该指派48个代理商人员，轮班2应该指派31个代理商人员，轮班3应该指派39个代理商人员，轮班4应该指派43个代理商人员，轮班5应该指派15 个代理商人员。此时

13、，最小规划成本为30610元。一、实验目的1、理解指派问题的特点。2、对于一个指派问题，能够建立电子表格模型。3、会运用Excel求解电子表格模型。二、实验内容塞尔默公司的营销经理将要主持召开一年一度的有营销区域经理以及销售人员参加 的销售协商会议。为了更好地安排这次会议，他雇用了四个临时工（安、伊恩、琼、肖恩）， 每一个人负责完成下面的一项任务：书面陈述的文字处理；制作口头和书面陈述的电脑图；会议材料的准备，包括书面材料的抄写和组织；处理与会者的提前和当场注册报名；现在他需要确定要将哪一项任务指派个哪一个人。虽然这四个临时工都有完成这四项任务所需的基本能力，但是在他们完成每一项任务 时所表现

14、出来的有效程度是有很大差异的。表2.3显示了每一个人完成每一项任务所用的 时间（单位：小时）。最右一列给出了以每个人能力为基础的小时薪水。表2.1塞尔默公司问题的数据临时工每一项任务所需要的时间（小时）每小时工资文字处理绘图材料准备记录安3541274014伊恩4745325112琼3956364313肖恩3251254615三、实验步骤（1）明确题目目的：本题目的对人员进行合理安排，使所耗费的资本最少。（2）分析题目，定义决策变量：该指派问题是一个特殊的可以用线性规划方程的运 输问题。给每个节点都赋予约束条件，并对每个弧都赋予一个参数。在运输问题中，使用 双下标决策可变量。x11代表项目临时

15、工（安）和任务1，x12代表项目临时工（安）和任务 2，依次类推。所以，将福尔指派问题的决策可变量定义如下：厂1表示临时工是i，任务是jI 0其他情况这里i =1, 2, 3, 4； j=1, 2, 3,4使用表2.3中的符号和完成时间数据，我们得出了完成时间表达式:安完成指派共用时间:35X11+41X12+27X13+40X14伊恩完成指派共用时间:47X21+45X22+32X23+51X24琼完成指派共用时间:39X31+56X32+36X33+43 X34肖恩完成指派共用时间:32X41+51X42+25 X43+46X444个临时工完成时间的总和将提供完成4个指派任务所需要的时间总

16、和。因此，目标函数如下：35X11 +41X27X40 XM+47X1 +45X/32X”+51X,4+39Xq1 +56+36Xq+43X4+ 11121314212223243132333432X41+51X42+25X43+46X44（3）根据决策变量写出约束条件：指派问题约束反映的情况如下：每个临时工被赋 予一项任务，并且每项任务被赋予一个临时工。这些约束条件如下：安的指派：x11 + x12 + x13 + x14 = 1伊恩的指派：x21 + x22 + x23 + X24 = 1琼的指派：x31 + x32 + x33 + X34 = 1肖恩的指派：x41 + X4 2+ x43

17、 + X44 = 1文字处理：x11 + x21 x31 x41 = 1绘图：品 + X22 + X31 + X42 = 1材料准备：孔+易+ X33 + X43 = 1记录：Xm + X24 + X34 + X44 = 1（4）根据步骤（2）（3）写出模型目标函数，并建立数学模型：A J -1 n 7 一 2RY -I-/11 Y -I- Q 7 Y -|-/I fl Y ZL7Y -i-ZLRY -i- Q Q V -i-R Y 2QY -l-RGY-I-/IR YMill Z = 35X+41 X 9+2 7 X q+40 X A+4/X1 +45X9+32Xq+51X A+39X1 +

18、56X9+36q+43XqA 111213142122232431323334+32X41+51X42+25X43+46X44s.t： X11+X12+X13+X14=1X21+X22+X23+X24=1X31+X32+X33+X34=1X41+X4 2+X43+X44=1 X11+X21X31 X41=1X12+X22+X31+X42=1X13+X23+X33+X43=1X14+X24+X34+X44=1 i 二：L,2,3,4；j = 1，2,3,4(5) 在工作表中建模：根据题意，在excel表格中输入相应的数据:文字姓理材辑雇寄记录瓣小时工盗安35Z；4011141414伊屈1715:

19、绍.51121212琼395 Pi4313131313肖感3251穿i4615151515最少成奉盟时工所需时间文字处理材料淮窗记工合计安1伊盛1琼11合计=1111图2.1.1在表中输入与题目相关的数据(6) 在excel中确定决策变量的位置，利用sumproduct函数进行求解:文字处理绘剧村料准备记录岳小时T资安354-12740i_1 -14L414伊照+ 7453?.1212123F：56361331313.肯恩3251S54615151515最少成本临时工所誓时间文字汕理绘图材牯准备记录合计安010101肯恩01言计000D=11LL(7) 在规划求解中输入约束条件:图2.1.3规

20、划求解参数(8) 求解，得出答案:文宇姓理绘圈材料准备记录每小时工资受35112740141414伊恩474532511212121F3956364313131313肖恩32512546诟151515昴少薪资1957临时工谕要时俱文字处理绘图材料准缶记录合计安D10D1=1伊恩100D1=1D项011=1肖恩00101=1合计111=1111图2.1.4求解得出最少薪资四、实验结果根据excel表格求解：所以安排安从事材料准备工作，伊恩从事绘图工作，琼从事记录工作，肖恩从事文字处理工作，有最小薪资成本为1957元。实验三线性规划一、实验目的1、理解网络最优化问题的特点和实质。2、对于一个最短路

21、问题，能够建立电子表格模型。3、会运用Excel求解电子表格模型。二、实验内容3.1里特城(Littletown)是一个农村的小镇。它的消防队要为包括许多农场社区 在内的大片地区提供服务。在这个地区里有很多的路，从消防站到任何一个社区都 有很多条路线。因为时间是到达火灾发生点的主要因素，所以消防队队长希望实现 能够确定从消防站到每个农场社区的最短路。下图标示了连接消防站和其中一个农 场社区的道路系统，图中包含了每条路的英里数。你能够找到从消防站到这个农场 社区的最短路线吗？图3.3中里特城的消防站和某一农场社区间的道路系统，其中，A，B，H是交叉口，每条路旁边的数字表示单位为英里的距离。三、实

22、验步骤（1）根据题意，在excel表格中输入题中相关数据:r.e傩塑Far DmToTiirieHe Fl aa-wriu.pp 1 留/口 isinEHnd.泻防站A3B6消防法CdAD&AE1BA1BD|1，E5C2E2E7FS日3E3EF6EG5&日GS衣妇F3夜场社区6H2G2布场杜也7图3.1.1在EXCEL表中输入题中相关数据（2）确定决策变量：在OnRoute这一列中确定决策变量C39： C62STr珞横738FroirraToTNodesNet FlowSupp-1 jr/D 石 mstrnd治防站A3W治防站B口 L泊昉站C日日AD03AB习理EALBDd布EE：507Bc2

23、8cBZ39cE?5QDF8占LDES1152E：D3.：EF654EG55EEH日56FG3S7F庆坊让区d58GF3S9c50GHZ6LHG26ZH.衣本壮区7图3.1.2确定决策变量（3）确定目标函数Total Time：FromToQriKoii-i-t ejiTimeEfolQE3：Not FlawSlipup 1 y/D HmEMnid消防站A3消昉站6消防洱，4A6A1B1B4EESEZC2c7DSD3E3E611 1EGSE4F3F农场初4GF3G布.成土国：6CH2HC2H农场壮E：TTotalT ime（4）在Net Flow这一列中用sumif函数确定约束条件:图3.1.

24、4 Net Flow列确定约束条件（5）进行规划求解：图3.1.5规划求解参数（6）求出结果:Far omToT:i ehKlaTdLwE： F1 wSuBpI yXDiesrsaurj d消防站A13消防站L1八IF站B06u消防站C0a00岳DQ6Q0AE11lj：BA.01uBDa40CiBE：i5nB口02Q0CB02在场社叵-1-1cE：ClTDFQBDE03HD03EF16EGQ5HHQaFa03F14GKCl3a06aH0ZHGQEH07Totci 1T i me19四、实验结果所以可以得出最优的路线应该是：消防站 一 A B 一 E F 一 农场社区因此该路线的最短用时：3+1+5+6+4=19