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

成绩徐州工程学院实习报告实习名称 运筹与优化算法实现（运筹学与控制论方向）学 院 数理学院专 业信息与计算科学班 级 学生姓名 学 号 实习地点科学计算与数学建模实验室指导教师 实习起止时间：2012年05月07日至2012年05月11日1、 实习目的和要求在了解“运筹学及应用”与“图与网络分析”基本的优化模型的基础上，理解其基本原理，掌握其基本的算法，会用这些模型与算法，用相关的软件编写程序，来解决有关的实际问题，达到对创新能力、实践能力的培养要求。2、 实习计划（1） 问题分析、查找相关文献（第一天）（2） 模型建立（第二天）（3） 设计算法求解（第三天）（4） 算法的程序实现并进行结果分析（第四天）（5） 整理实习报告、实习日志等材料（第五天）3、 实习主要内容（1）实习题目线材切割问题设能购买到的不同长度的原线材有m种，长度分别为L1,...,Lm，这些原线材只是长度不同，其它都相同。某工程中所要切割出的线材长度分别为li,i=12...,n（这里li＜所有Li），对应数量分别为Ni,i=12...,n。设计优化计算方案，求出分别需要购买多少根不同长度的原线材，并能给出切割方案及线材利用率。现假设某装修工程中需要对铝合金线材进行切割，工程能购买到的同一规格的铝合金线材有二种长度，一种长度是8米，另一种是12米。现在假设要切割长度和数量如下所示的铝合金线材：

编号长度（单位:米）数量（单位：根）16.209023.6012032.8013641.8531050.7521560.55320应用所设计的计算方案，请问至少需要购买多少根8米和12米的线材，使浪费的线材比较少，并给出切割方案和计算线材利用率（2）模型的建立建模分析：根据“全部用完，没有剩余”的原则，将所有的方案列举如下：注:设各个方案中使用长度为8或12的材料分别为Xi（i=1,2,3・・・13）,详细方案见表：根数长度\123456789101112136.200100001000103.600000021020012.800121100002031.8540012020500000.75116402400021700.557001042456310使用的原材料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>=320IX1、X2……X13为非负整数模型的求解(含编程求解)编写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>=320ENDGINX1GINX2GINX3GINX4GINX5GINX6GINX7GINX8GINX9GINX10GINX11GINX12GINX13在WINDOWS版的LINDO系统中，从LINDO菜单下选用SOLVE命令，则可以得到如下结果：SETX2TO<= 27AT1,BND=0.0000E+00TWIN=0.0000E+0043

SET X11TO<= 0AT2,BND=0.0000E+00TWIN=0.0000E+0045SETX4TO<= 41AT3,BND=0.0000E+00TWIN=0.0000E+0050SETX4TO<= 0AT4,BND=0.0000E+00TWIN=0.0000E+0053NEWINTEGERSOLUTIONOF0.000000000E+00ATBRANCH 8PIVOT53BOUNDONOPTIMUM:0.0000000E+00DELETEX4ATLEVEL4DELETEX4ATLEVEL 3DELETEX11ATLEVEL2DELETEX2ATLEVEL 1ENUMERATIONCOMPLETE.BRANCHES= 8PIVOTS= 53LASTINTEGERSOLUTIONISTHEBESTFOUNDRE-INSTALLINGBESTSOLUTION...OBJECTIVEFUNCTIONVALUE1)0.0000000E+00VARIABLE VALUEREDUCEDCOSTX162.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.000000ROWSLACKORSURPLUSDUALPRICES2)58.0000000.0000003)0.0000000.0000004)0.0000000.0000005)0.0000000.000000

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