实习报告 运筹与优化算法实现

1、成绩徐州工程学院实习报告实 习名称运筹与优化算法实现（运筹学与控制论方向）学院数理学院专业 信息与计算科学班级学生姓名学号实习地点 科学计算与数学建模实验室指导教师实习起止时间：2012年05月07日至2012年05月11日1、实习目的和要求在了解“运筹学及应用”与“图与网络分析”基本的优化模型的 基础上，理解其基本原理，掌握其基本的算法，会用这些模型与算法， 用相关的软件编写程序，来解决有关的实际问题，达到对创新能力、 实践能力的培养要求。2、实习计划（1）问题分析、查找相关文献（第一天）（2）模型建立（第二天）（3）设计算法求解（第三天）（4）算法的程序实现并进行结果分析（第四天）（5）整

2、理实习报告、实习日志等材料（第五天）3、实习主要内容（1）实习题目线材切割问题设能购买到的不同长度的原线材有m种，长度分别为L1,.,Lm， 这些原线材只是长度不同，其它都相同。某工程中所要切割出的线材 长度分别为li,i = 12.,n（这里li 所有Li），对应数量分别为 Ni,i = 12.,n。设计优化计算方案，求出分别需要购买多少根不同长 度的原线材，并能给出切割方案及线材利用率。现假设某装修工程中需要对铝合金线材进行切割，工程能购买到 的同一规格的铝合金线材有二种长度，一种长度是8米，另一种是 12米。现在假设要切割长度和数量如下所示的铝合金线材：编号长度（单位:米）数量（单位：根

3、）16.209023.6012032.8013641.8531050.7521560.55320应用所设计的计算方案，请问至少需要购买多少根8米和12米的线材，使浪费的线材比较少，并给出切割方案和计算线材利用率（2）模型的建立建模分析：根据“全部用完，没有剩余”的原则，将所有的方案列举如下：注:设各个方案中使用长度为8或12的材料分别为Xi（i=1,2,313）,详细方案见表：根数 长度123456789101112136.200100001000103.600000021020012.800121100002031.8540012020500000.75116402400021700.557

4、001042456310使用的原 材料1212128881212121281212损失0000000000000由上表可列出以下数学模型:MINZ=0X1+0X2+0X3+0X4+0X5+0X6+0X7+0X8+0X9+0X10+0X11+0X12+0X13广 X3+X8+X12=90X2+2X7+X8+2X10=1203X2+X3+2X4+X5+X6+2X11=1365X1+X4+2X5+2X7+4X9=3104X3+2X5+4X6+X9+2X10+X11+7X12+16X13=2155X1+X4+4X6+2X7+4X8+7X9+6X10+3X11+X12=320I X1、X2X13为非负整

5、数模型的求解(含编程求解)编写LINDO代码如下MIN0X1+0X2+0X3+0X4+0X5+0X6+0X7+0X8+0X9+0X10+0X11+0X12+0X13STX3+X8+X12=90X2+2X7+X8+2X10=1203X2+X3+2X4+X5+X6+2X11=1365X1+X4+2X5+2X7+4X9=3104X3+2X5+4X6+X9+2X10+X11+7X12+16X13=2155X1+X4+4X6+2X7+4X8+7X9+6X10+3X11+X12=320ENDGIN X1GIN X2GIN X3GIN X4GIN X5GIN X6GIN X7GIN X8GIN X9GIN

6、X10GIN X11GIN X12GIN X13在 WINDOWS版的LINDO系统中，从LINDO菜单下选用SOLVE命令，则可以得到如下结果：SET X2 TO =27 AT 1, BND= 0.0000E+00 TWIN= 0.0000E+0043SETX11 TO =0 AT 2, BND= 0.0000E+00 TWIN= 0.0000E+0045SETX4 TO =41 AT 3, BND= 0.0000E+00 TWIN= 0.0000E+0050SETX4 TO =0 AT 4, BND= 0.0000E+00 TWIN= 0.0000E+0053NEW INTEGER SOL

7、UTION OF 0.000000000E+00 AT BRANCH8PIVOT53BOUND ON OPTIMUM: 0.0000000E+00DELETEX4 AT LEVEL 4DELETEX4 AT LEVEL3DELETEX11 AT LEVEL 2DELETEX2 AT LEVEL1ENUMERATION COMPLETE. BRANCHES=8 PIVOTS=53LAST INTEGER SOLUTION IS THE BEST FOUNDRE-INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION VALUE1)0.0000000E+00VARI

8、ABLEVALUEREDUCED COSTX162.0000000.000000X227.0000000.000000X355.0000000.000000X40.0000000.000000X50.0000000.000000X60.0000000.000000X70.0000000.000000X893.0000000.000000X90.0000000.000000X100.0000000.000000X110.0000000.000000X120.0000000.000000X130.0000000.000000ROW SLACK OR SURPLUSDUAL PRICES2)58.0

9、000000.0000003)0.0000000.0000004)0.0000000.0000005)0.0000000.0000006)5.0000000.0000007)362.0000000.000000NO. ITERATIONS= 53BRANCHES= 8 DETERM.= 1.000E0结果分析本次计算用到53次迭代。材料浪费率为0，即材料利用率为100%。最优解变量：VARIABLE VALUEREDUCED COSTX162.0000000.000000X227.0000000.000000X355.0000000.000000X40.0000000.000000X50.00

10、00000.000000X60.0000000.000000X70.0000000.000000X893.0000000.000000X90.0000000.000000X100.0000000.000000X110.0000000.000000X120.0000000.000000X130.0000000. 000000第二列，即“VALUE”给出最优解中各变量(VARIABLE)的值:X1 = 62.000000； x2=27.000000;x3=55.000000; x8=93.000000; x4=x5=x6=x7=x9=x10=x11=x12=x13=0第三列，即“REDUCED C

11、OST”给出最优单纯形表中第0行中变量的系数.其中基变量的reduced cost值应为0,对于非基变 量，相应的reduced cost值表示当该非基变量增加一个单 位时目标函数减少的量。本例中此值均为0。分析结果的下半部分：ROWSLACK OR SURPLUSDUAL PRICES2)58.0000000.0000003)0.0000000.0000004)0.0000000.0000005)0.0000000.0000006)5.0000000.0000007)362.0000000.000000第二列，即“SLACK OR SURPLUS给出松驰变量的值：第3、4、5行松驰变量均为0,说明对于最优解来讲，两个约束（第3、 4、5行）均取等号。第三列，即“DUAL PRICES给出对偶价格的值：各行对偶价格均为 0.00000006、最后结果：长度为8米的根数为：0长度为12米的根数为：62+27+55+93=237材料利用率为100% o4、实习总结本次课程设计的时间是1个星期，在这几天里，首先是学习lindo 软件的使用方法。从简单到复杂，逐步掌握软件的一些常用用法，熟 悉它的工作界面，掌握一些基本的命令。到最后的实习报告设计上， 在建摸这块花了很长的时间和精力，开始总是想不出很好的方案，不 知道从哪里下手。在软件的