《哈工大2019运筹学上机实验报告.docx》由会员分享，可在线阅读，更多相关《哈工大2019运筹学上机实验报告.docx（11页珍藏版）》请在三一办公上搜索。
1、运筹学实验一、实验目的1）了解Excel的基本功能，熟悉界面，掌握基本的操作命令；2）熟悉Matlab编程环境，了解Matlab的基本功能，掌握基本的编程语言；3）用Excel和Matlab求解话务排班线性规划问题。二、实验器材1）PC 机：20 台。2）Microsoft Excel软件（具备规划求解工具模块）：20用户。3）Matlab软件（具备优化工具箱）：20用户。三、实验内容：1.用Excel和Matlab完成下列话务排班问题。工作时间点6点6-9H 912点 12-15点 1518点 1821 点点最低需 求人数（人）8515202523181U薪水（元）2G30232220202
2、224某寻呼公司雇佣了多名话务员工作，他们每天工作3节，每节3小时，每节开始时间为 午夜、凌晨3点钟、凌晨6点钟，上午9点、中午12点，下午3点、6点、9点，为方便话 务员上下班，管理层安排每位话务员每天连续工作3节，根据调查，对于不同的时间，由于 业务量不同，需要的话务员的人数也不相同，公司付的薪水也不相同，有关数据如下表所 示。问：如何安排话务员才能保证服务人数，又使总成本最低？实验步骤如下：1）建立话务排班问题的线性规划模型。2）根据线性规划模型在Excel电子表格中建立清晰的模型描述。3）使用线性规划模块完成求解。4）根据线性规划模型建立符合Matlab中linprog函数要求的线性规
3、划模型。5）对linprog函数中各参数进行赋值。6）调用linprog函数完成求解。2.用Excel和Matlab完成下列转运问题。A1、A2两煤矿产的煤运往B1、B2、B3三个城市销售，各煤矿的供应量、各城市的需B27560300300B38580306000需求量（t）00100150180问：如何安排各城市与城市之间、各煤矿与煤矿之间、各煤矿与城市之间的运输量，使 得总的运输成本最低？实验步骤如下：1）建立转运问题的线性规划模型。2）根据线性规划模型在Excel电子表格中建立清晰的模型描述。3）使用线性规划模块完成求解。4）根据线性规划模型建立符合Matlab中linprog函数要求的
4、线性规划模型。5）对linprog函数中各参数进行赋值。6）调用linprog函数完成求解。3.用Excel和Matlab完成下列公司选址问题。某销售公司打算通过在武汉或长春设立分公司（也许在两个城市都设分公司）增加市场 份额，管理层同时也计划在新设分公司的城市最多建一个配送中心，当然也可以不建配送中 心。经过计算，每种选择对公司收益的净现值列于下表的第四列、第五列中记录了每种选择 所需的费用，总的预算费用不得超过20万元。决策编号问题决策变量净现值（万所需资金（万1是否在长春设分公司？x118122是否在武汉设分公司？x21063是否在长春建配送中心？x312104是否在物产建配送中心x48
5、4问：如何决策才能使总的净现值最大？实验步骤如下：1）建立公司选址问题的0-1整数规划数学模型。2）根据规划模型在Excel电子表格中建立清晰的模型描述。3）使用规划工具模块完成求解。4）根据规划模型建立符合Matlab中bintprog函数要求的0-1整数规划模型。5）对bintprog函数中各参数进行赋值。6）调用bintprog函数完成求解。三.问题求解：1. 话务排班问题1）数学模型：在此题中，用X表示每个时间段开始上班的人数，设0-3点开始上班的人数为X1，依次推 至X8。分别用A-H来代表每个时间段的总人数。Z表示总共需要支付的薪水。则目标函数 为Z的最小值。Z=28A+30B+2
6、8C+22D+20E+20F+22G+24H即：Z=84*X1+80*X2+70*X3+62*X4+62*X5+66*X6+72*X7+80*X8ST:X1+X7+X8 = 8X1+X2+X8 = 6X1+X2+X3 = 15X2+X3+X4 = 20X3+X4+X5 = 25X4+X5+X6 = 23X5+X6+X7 = 18X6+X7+X8 = 10Xi = 0。=1,2,3,4,5,6,7,8)且 X 均为整数2) EXCEL 求解：将上述线性规划问题代入到EXCEL中进行求解。首先，建立其规划求解的基本模型：图1.规划求解界面ABCDEFGH1JKLM实验一.话务排班线性规划问题XIX
7、2X3X4X5X6X7xa合计约束0-3100000110-83-6110000010-66-9111000000-159-12011100000-2012-15001110000-2515-19000111000 =2310-21000011100 =1S21-0000001110 =10单位成本S4807062626672800最优解00000000第J列插入的为sumproduct函数。Ji=sumproduct(Bi:Ii,B12:I12) ( i=311)求解操作如图二所示：图2.求解操作参数设置对于求解运算的高级属性，我们使用系统默认设置。最后进行求解，解得如下结果：O Offic
8、e更新 若要保持使用最新安全更新、修复和改进，请选择“检查更新 :X 5众ABCDEFGHIJKLM:11121314151 G实验一 .话务排班线性规划问题XIX2X3X4X5X6X7X8合计约束0-31000Q0118 =S3-6110000016二66-91110000015-159-120111000020 =2012-15Q0111Q0026二2515-180001110023-2318-21000Q111013 =1921-00000011110-10单位成本B4807062626672802864最优解42998640图3.规划求解结果求得一组最优解。下面我们用matlab再次求
9、解一遍，以验证解的合理性。3)Matlab求解：首先建立目标方程，此处需要将A-H转化成其对应的X。minZ=84*X1+80*X2+70*X3+62*X4+62*X5+66*X6+72*X7+80*X8线性约束方程组同上，此处不再赘述。利用Matlab中的linprog函数求解上述问题的代码为：c=84;80;70;62;62;66;72;80;A=-1 0 0 0 0 0 -1 -1;-1 -1 0 0 0 0 0 -1;-1 -1 -1 0 0 0 0 0;0 -1 -1 -1 0 0 0 0;0 0 -1 -1 -1 0 0 0;0 0 0 -1 -1 -1 0 0;0 0 0 0 -
10、1 -1 -1 0;0 0 0 0 0 -1 -1 -1;b=-8;-6;-15;-20;-25;-23;-18;-10;lb=0;0;0;0;0;0;0;0;x, fval=linprog(c,A,b,lb);注意其中的矩阵参数应是方程组在标准情况下的参数。得到的解如图所示：图4. Matlab解出的人员分配图5. Matlab解出的成本最小值4）.结果分析：对于上述两种不同软件的求解，我们不难发现他们最终的计算都指向了相同的结果。综 合以上计算结果我们不难得到最终方案：5 、卜 w JXABCDEFGH11实验一话务排班最佳方案2时段0-33-66-99-1212-1515-1818-21
11、21-03开始上班人数429986404总最小成本286456图6.最佳话务排班方案 至此，本题得以全部解决。2. 转运问题1）数学模型：此问题为典型的转运问题，其产销平衡，但是与通常情况不同的是本题不存在严格意义上的 产地和销地，且其运费具有方向性，因此我们对产地和销地进行不区分对待，为方便统一用 15五个数字代替。两地之间的运货量用Xij表示。由于i=j时，Xij没有意义，故可以将 25*5的矩阵化简为20*4的矩阵。规定货物运出为正，运进为负。设Z为最小运输成本。则 有：Z=45X12+90X13+60X54ST:X12+X13+X14+X15-X21-X31-X41-X51=200X2
12、1+X23+X24+X25-X12-X32-X42-X52=230 X31+X32+X34+X35-X13-X23-X43-X53=-100 X41+X42+X43+X45-X14-X24-X34-X54=-150 X51+X52+X53+X54-X15-X25-X35-X45=-180 Xij=0则可得到下列求解模型：EM：.等线5正文）2 ”A，=二%M动换行常规密引曾冏着:：的.界帖贴 次坟士 B二三三三姮日合并后居由 圭 % 0。 展4o 条件格式套用蜜率 插入 倒除 格式 ；嗦和恃讥衷格格式 样式7消洋 弗选O OHice更新若要保持使用最新安全更新、修复和改进，请选择检查更新检查更
13、新 T29： X 5 AABCDEFGHIJKLMNOPQRSYUVWX实脸二转话句魅X12X13X14XI5X21X23X24X25X31X32X34X35X41X42X43X45X51XS2X53X54合计XI1111-1000-1000-t000-10000200X2-100011110-1000-1000-1000230X30-1000-100111100-1000-100-100X400-1000-1000-101111000-10-150X5000-1000-1000-1000-111110-10045907095503065759555457075603030B580306000
14、00000000000000000005图7. excel转运模型2) excel 求解：将上述转运模型代入excel求解，求解步骤与实验一相同，此处不再赘述。经过规划求解后得到如图所示解：甄，I -二 J n LISWL*, W 田-ii_r 囹顼充牯贴 KMT B I U - V 5* V A ,-合并后居口 苜涉 % 。 ，明 条件格式 套用 单元格 插入 倒除 格式 格式 Abuu .u表格格式 样式/清徐O Office更新 若要保持使用最新安全更新、修复和改进，请选择检查更新检查更新W22:A&CEFGH1JKLMN0PQRSTuVWX1实箜二转远瓦炫2X12X13X14XI5X2
15、1X23X24X25X31X32X35X41X4.2X43X45X51X52X53X54会计3XI1t11-1000-1000-1000-1000网。20C4X2-100011110-1000-1000-10023C5X30-1000-100111100-1000-10-100-100X400-1000-1000-101111000-1-150-15C7X5000-1000-1000-1000-11111-190-1808单位或志45907095508065759555457075603030B53060325009最火解0501500050018G0000000000001Q11121314
16、151-61718图8.转运问题规划求解得到的解为：X13=50，X14=150，X23=50，X25=180，Z=32500即：A1B1 50t / A1B2 150t / A2B1 50t / A2B3 50tZmin=32500 元。下面我们用Matlab再次求解一遍，以验证模型和求解的正确性。3). Matlab 求解根据之前的数学模型，我们建立出了相应的线性方程组。Z=45X12+90X13+. . . 60X54于是，目标函数的系数矩阵为 c=45;90;70;95;50;80;65;75;95;55;45;70;75;60;30;30;85;80;30;60 又因为约束条件为：X
17、12+X13+X14+X15-X21-X31-X41-X51=200X21+X23+X24+X25-X12-X32-X42-X52=230X31+X32+X34+X35-X13-X23-X43-X53=-100X41+X42+X43+X45-X14-X24-X34-X54=-150X51+X52+X53+X54-X15-X25-X35-X45=-180故 A=0, b=0;Aeq=1 1 1 1 -1 0 0 0 -1 0 0 0 -1 0 0 0 -1 0 0 0;-1 0 0 0 1 1 1 1 0 -1 0 0 0 -1 0 0 0 -1 0 0;0 -1 0 0 0 - 1 0 0 1
18、 1 1 1 0 0 -1 0 0 0 -1 0;0 0 -1 0 0 0 -1 0 0 0 -1 0 1 1 1 1 0 0 0 -1;0 0 0 -1 0 0 0 -1 0 0 0 -1 0 0 0 -1 1 1 1 1beq=200;230;-100;-150;-180lb=0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0由此可得其Matlab求解代码为：c=45;90;70;95;50;80;65;75;95;55;45;70;75;60;30;30;85;80;30;60;Aeq=1 1 1 1 -1 0 0 0 -1 0 0 0 -1 0 0 0 -1
19、 0 0 0;-1 0 0 0 1 1 1 1 0 -1 0 0 0 -1 0 0 0 -1 0 0;0 -1 0 0 0 - 1 0 0 1 1 1 1 0 0 -1 0 0 0 -1 0;0 0 -1 0 0 0 -1 0 0 0 -1 0 1 1 1 1 0 0 0 -1;0 0 0 -1 0 0 0 -1 0 0 0 -1 0 0 0 -1 1 1 1 1;beq=200;230;-100;-150;-180;lb=0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;x,fval=linprog(c,Aeq,beq,lb);运行上述代码，得到的解为：,s 卜
20、 mazhipeng 卜 Documents 卜 MATLABK Variables - xx x fval田20x1 double123456ework.m19.0945e-102SO. 00003ISO.000044.4026e-09S4.2745e-10650.000071.0274e-0Sa160.000091.5224e-10102.165 房 10114.40fi5e-10124.04851。n131.9242e-10142.4202c-10152.9743e-09162.69fi7e-0917i.seese-io181.7S0ee-1019fi.2456e-10203.4319e
21、-1021卜 mazhipeng Documents MATLABmework.inS Variables - fval1 J xfval 精田 1x1 double12345613.2500e+04234567图9.转运问题Matlab求解由上述求解结果可知，excel和Matlab求解结果相同。4).结果分析对于上述问题的求解，我们可以看出上述两种方法得到了同一个解。故问题最后的答案 为：从A1往B1运送50吨，A1往B2运送150吨，A2往B1运送50吨，A2往B3运送180 吨。总最小运费为32500元。3. 公司选址0-1整数规划问题1).数学模型：公司选址问题属于0-1整数规划问题
22、。此题中有四个决策变量，分别用0,1代表他们的状态。设Z为总净现值，则此题要求Z的最大值：maxZ=18X1+10X2+12X3+8X4ST:12X1+6X2+10X3+4X4=1X1-X3=0X2-X4=0Xi 0,12). Excel 求解：将上述函数及其约束代入excel中求解，其初始模型描述为:D11； X V* AABCDEFGH1实验三.公司选址0-1整数规划问题2XIX2X3X4总计3净现值181012804成本1261040二205最优解000060789图10. Excel 0-1规划模型描述对于上述模型，与前两题有一点不同之处为我们在B6单元格里插入的为sum(b5:c5)
23、。对上述模型进行求解，求解操作如图所示：图11. 0-1规划求解操作但是，此题中值得注意的是，我们在0-1整数求解时，应将设置选项里的忽略整数约束这一 栏取消勾选，以确保其求解的正确性。（系统可能默认忽略整数约束）。图12. 0-1整数规划时的运算设置G11ABCDEFGH1实验三.公司选址0-1整数规划问题2XIX2X3X4总计3净现值1810128284成本12610418二205最优解110062789m最终，我们求得的结果如图所示:Q Office图13. 0-1整数规划求解结果最终得到的结果为在长春和武汉建立分公司，不建配送中心。最大净现值为28万元，符合 上述优化条件，我们用Mat
24、lab再次检验一遍。3). Matlab 求解：根据上述优化条件，我们将其化为标准型：maxZ=18Xi+10X2+12X3+8X4ST:12X1+6X2+10X3+4X4=20-X1-X2+0+0=-1-X1+0+X3+0=00-X2+0+X4=0Xi 0,1由此可得matlab求解代码为：c=18;10;12;8;A=12 6 10 4;-1 -1 0 0;-1 0 1 0;0 -1 0 1;b=20;-1;0;0;x=bintprog(c,A,b);运行发现在Matlab2014b之后bintprog函数已经被移除，转而使用intlinprog函数取代。其代码为：c=18;10;12;8
25、;i=1,2,3,4;A=12 6 10 4;-1 -1 0 0;-1 0 1 0;0 -1 0 1;b=20;-1;0;0;lb=zeros(4,1);ub=ones(4,1);x,fval=intlinprog(c,i,A,b,lb,ub);运行结果如图所示：司, / * Users mazhipeng Documents MATLAB器i Variables - fvalX 篱123456712&234homework.m图12. Matlab 0-1整数规划结果fval田 lxl double4).结果分析：结果为在长春和武汉建立分公司，不建配送中心。最大净现值为28万元。四. 同类问
26、题分析在上述三个问题中，我们求解时均应将其转化为标准形式。话务排班问题，主要核心便是 多元线性整数规划问题。其自变量取值往往是大于等于0的整数，在excel和Matlab中均有 对应的求解函数。对于类似的题目，例如人力资源分配问题，集装箱装箱问题等涉及到整数 最优化问题时，都可以参照上述方法。对于转运问题，其实质仍然与排班问题相似，不过转 运问题有时具有方向性，因此需要注意变量的正负性问题，与此相类似的还有航线规划问题 等。同时。在0-1整数规划中，新使用的intlinprog函数本质上就是整数规划问题，我们可 以通过添加约束矩阵来将其转化为0-1规划问题。五. 工具特点及方便性分析相较于手工求解，机器求解在计算有关大规模矩阵的时候有着不可比拟的优越性，无论是计 算速度还是精确度都要远远超过人力。对于这两种软件，Excel模型直观明了，但是输入单 元格较多，设置参数多，过程较复杂，而matlab有编程的意思，采用专门的操作语言，界 面不够清晰明了，但是功能强大，输入快捷，运算迅速。Excel可用于求解变量较少，较为简 单的模型，多用于日常使用，matlab则是比较专业的软件，适用于较为复杂的问题求解。
