實(shí)習(xí)報(bào)告 運(yùn)籌與優(yōu)化算法實(shí)現(xiàn)

成績(jī)徐州工程學(xué)院實(shí)習(xí)報(bào)告實(shí)習(xí)名稱 運(yùn)籌與優(yōu)化算法實(shí)現(xiàn)（運(yùn)籌學(xué)與控制論方向）學(xué) 院 數(shù)理學(xué)院專 業(yè)信息與計(jì)算科學(xué)班 級(jí) 學(xué)生姓名 學(xué) 號(hào) 實(shí)習(xí)地點(diǎn)科學(xué)計(jì)算與數(shù)學(xué)建模實(shí)驗(yàn)室指導(dǎo)教師 實(shí)習(xí)起止時(shí)間：2012年05月07日至2012年05月11日1、 實(shí)習(xí)目的和要求在了解“運(yùn)籌學(xué)及應(yīng)用”與“圖與網(wǎng)絡(luò)分析”基本的優(yōu)化模型的基礎(chǔ)上，理解其基本原理，掌握其基本的算法，會(huì)用這些模型與算法，用相關(guān)的軟件編寫程序，來解決有關(guān)的實(shí)際問題，達(dá)到對(duì)創(chuàng)新能力、實(shí)踐能力的培養(yǎng)要求。2、 實(shí)習(xí)計(jì)劃（1） 問題分析、查找相關(guān)文獻(xiàn)（第一天）（2） 模型建立（第二天）（3） 設(shè)計(jì)算法求解（第三天）（4） 算法的程序?qū)崿F(xiàn)并進(jìn)行結(jié)果分析（第四天）（5） 整理實(shí)習(xí)報(bào)告、實(shí)習(xí)日志等材料（第五天）3、 實(shí)習(xí)主要內(nèi)容（1）實(shí)習(xí)題目線材切割問題設(shè)能購買到的不同長(zhǎng)度的原線材有m種，長(zhǎng)度分別為L(zhǎng)1,...,Lm，這些原線材只是長(zhǎng)度不同，其它都相同。某工程中所要切割出的線材長(zhǎng)度分別為li,i=12...,n（這里li＜所有Li），對(duì)應(yīng)數(shù)量分別為Ni,i=12...,n。設(shè)計(jì)優(yōu)化計(jì)算方案，求出分別需要購買多少根不同長(zhǎng)度的原線材，并能給出切割方案及線材利用率?，F(xiàn)假設(shè)某裝修工程中需要對(duì)鋁合金線材進(jìn)行切割，工程能購買到的同一規(guī)格的鋁合金線材有二種長(zhǎng)度，一種長(zhǎng)度是8米，另一種是12米。現(xiàn)在假設(shè)要切割長(zhǎng)度和數(shù)量如下所示的鋁合金線材：

編號(hào)長(zhǎng)度（單位:米）數(shù)量（單位：根）16.209023.6012032.8013641.8531050.7521560.55320應(yīng)用所設(shè)計(jì)的計(jì)算方案，請(qǐng)問至少需要購買多少根8米和12米的線材，使浪費(fèi)的線材比較少，并給出切割方案和計(jì)算線材利用率（2）模型的建立建模分析：根據(jù)“全部用完，沒有剩余”的原則，將所有的方案列舉如下：注:設(shè)各個(gè)方案中使用長(zhǎng)度為8或12的材料分別為Xi（i=1,2,3???13）,詳細(xì)方案見表：根數(shù)長(zhǎng)度\123456789101112136.200100001000103.600000021020012.800121100002031.8540012020500000.75116402400021700.557001042456310使用的原材料1212128881212121281212損失0000000000000由上表可列出以下數(shù)學(xué)模型: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為非負(fù)整數(shù)模型的求解(含編程求解)編寫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系統(tǒng)中，從LINDO菜單下選用SOLVE命令，則可以得到如下結(jié)果：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結(jié)果分析本次計(jì)算用到53次迭代。材料浪費(fèi)率為0，即材料利用率為100%。③最優(yōu)解變量：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”給出最優(yōu)解中各變量(VARIABLE)的值:X1=62.000000；x2=27.000000;x3=55.000000;x8=93.000000;x4=x5=x6=x7=x9=x10=x11=x12=x13=0第三列，即“REDUCEDCOST”給出最優(yōu)單純形表中第0行中變量的系數(shù).其中基變量的reducedcost值應(yīng)為0,對(duì)于非基變量，相應(yīng)的reducedcost值表示當(dāng)該非基變量增加一個(gè)單位時(shí)目標(biāo)函數(shù)減少的量。本例中此值均為0。④分析結(jié)果的下半部分：ROWSLACKORSURPLUSDUALPRICES2)58.0000000.0000003)0.0000000.0000004)0.0000000.0000005)0.0000000.0000006)5.0000000.0000007)362.0000000.000000第二列，即“SLACKORSURPLUS"給出松馳變量的值：第3、4、5行松馳變量均為0,說明對(duì)于最優(yōu)解來講，兩個(gè)約束（第3、4、5行）均取等號(hào)。第三列，即“DUALPRICES"給出對(duì)偶價(jià)格的值：各行對(duì)偶價(jià)格均為0.00000006、最后結(jié)果：長(zhǎng)度為8米的根數(shù)為：0長(zhǎng)度為12米的根數(shù)為：62+27+55+93=237材料利用率為100%o4、實(shí)習(xí)總結(jié)本次課程設(shè)計(jì)的時(shí)間是1個(gè)星期，在這幾天里，首先是學(xué)習(xí)lindo軟件的使用方法。從簡(jiǎn)單到復(fù)雜，逐步掌握軟件的一些常用用法，熟悉它的工作界面，掌握一些基本的命令。到最后的實(shí)習(xí)報(bào)告設(shè)計(jì)上，在建摸這塊花了很長(zhǎng)的時(shí)間和精力，開始總是想不出很好的方案，不知道從哪里下手。