【文章內(nèi)容簡(jiǎn)介】 an Waren 共同開發(fā)的GRG2（Generalized Reduced Gradient）非線性最優(yōu)化代碼. [15] Excel 的“規(guī)劃求解” 功能強(qiáng)大，它可以實(shí)現(xiàn)對(duì)有多個(gè)決策變量的線性規(guī)劃問題的求解，回避了用線性規(guī)劃專業(yè)軟件求解時(shí)對(duì)操作者的專業(yè)要求，同時(shí)也克服了筆算的缺點(diǎn)，其操作方法簡(jiǎn)單、方便、快捷，大大提高了計(jì)算的效率與準(zhǔn)確性。Excel 與專業(yè)軟件相比，有以下特點(diǎn)：Excel 軟件方便易學(xué)，大部分人都比較熟悉，容易掌握；能用表格簡(jiǎn)單直觀地體現(xiàn)數(shù)學(xué)模型；Excel 具有大量的內(nèi)建函數(shù)，通過設(shè)置參數(shù)，就能進(jìn)行復(fù)雜的計(jì)算，建模過程簡(jiǎn)單；15Excel 軟件具有強(qiáng)大的數(shù)據(jù)分析功能。Excel 求解的步驟如下： 創(chuàng)建表格圖 31 創(chuàng)建表格設(shè)置約束條件和目標(biāo)函數(shù)F7=SUM（B7:E7）F8=SUM（B8:E8）F7=SUM（B9:E9）B2=SUM（B7:B9）C2=SUM（C7:C9）D2=SUM（D7:D9）E2=SUM（E7:E9）16H12=SUMPRODUCT(B2:E4,B7:E9)圖 32 約束條件和目標(biāo)函數(shù) 設(shè)置規(guī)劃求解參數(shù)見圖 33圖 33 規(guī)劃求解參數(shù)規(guī)劃求解選項(xiàng)設(shè)置 圖 34 規(guī)劃求解選項(xiàng)圖17求解圖 35 規(guī)劃求解 結(jié)果圖 36 Excel 求解的結(jié)果由圖 36 計(jì)算結(jié)果可以知道，運(yùn)用 Excel 求解的結(jié)果和用表上作業(yè)法的結(jié)果是一樣的。 Lingo 求解Lingo 軟件是美國 Lindo 系統(tǒng)公司開發(fā)的一套用于求解最優(yōu)化問題的軟件包，Lingo 除了能用于求解線性規(guī)劃和二次規(guī)劃外，還可以用于非線性規(guī)劃求解以及一些線性和非線性方程（組）的求解等。Lingo 軟件的最大特色在于它允許優(yōu)化模型中的決策變量為整數(shù)，而且執(zhí)行速度快。Lingo 內(nèi)置了一種建立最優(yōu)化模型的語言，可以簡(jiǎn)便地表達(dá)大規(guī)模問題，利用 Lingo 高效的求解器可快速求解并分析結(jié)果。Lingo 軟件，線性優(yōu)化求解程序通常使用單純形法，單純形法雖然在實(shí)18際應(yīng)用中是最好最有效的方法，但對(duì)某些問題具有指數(shù)階的復(fù)雜性，所以為了能解大規(guī)模問題，Lingo 也提供了內(nèi)點(diǎn)算法備選。Lingo 軟件有快速建構(gòu)模型、輕松編輯數(shù)據(jù)、強(qiáng)大求解工具、交互式模型和建立完成應(yīng)用、豐富的文件支持等優(yōu)點(diǎn)。Lingo 代碼編寫如下：sets: wh/w1 w2 w3/:ai。 vd/v1 v2 v3 v4/:dj。 links(wh,vd):c,x。endsets data: ai=7,4,9。 dj=3,6,5,6。 c=3,11,3,10 1,9,2,8 7,4,10,5。 enddata min=@sum(links(i,j):c(i,j)*x(i,j))。 @for(wh(i):@sum(vd(j):x(i,j))=ai(i))。 @for(vd(j):@sum(wh(i):x(i,j))=dj(j))。end運(yùn)行的結(jié)果如下：圖 37 總運(yùn)費(fèi)19圖 38 運(yùn)輸方案圖 39 內(nèi)存和時(shí)間耗費(fèi)由圖 37 至圖 39 可知，運(yùn)用 Lingo 求解的結(jié)果和用表上作業(yè)法的結(jié)果是一樣的，該模型的運(yùn)行過程不用 1 秒，內(nèi)存 20K。 Matlab 求解Matlab 是 20 世 紀(jì) 70 年 代 ， 美 國 新 墨 西 哥 大 學(xué) 計(jì) 算 機(jī) 科 學(xué) 系 主 任Cleve Moler 為 了 減 輕 學(xué) 生 編 程 的 負(fù) 擔(dān) ， 用 FORTRAN 編 寫 而 成 的 的 。 到20 世 紀(jì) 90 年 代 ， Matlab 已 成 為 國 際 控 制 界 的 標(biāo) 準(zhǔn) 計(jì) 算 軟 件 。Matlab 的 基 本 數(shù) 據(jù) 單 位 是 矩 陣 ， 它 的 指 令 表 達(dá) 式 與 數(shù) 學(xué) 、 工 程 中 常 用的 形 式 十 分 相 似 ， 故 用 Matlab 來 解 算 問 題 要 比 用 C， FORTRAN 等 語 言完 成 相 同 的 事 情 簡(jiǎn) 捷 得 多 ， 并 且 mathwork 也 吸 收 了 像 Maple 等 軟 件 的 優(yōu)點(diǎn) ,使 Matlab 成 為 一 個(gè) 強(qiáng) 大 的 數(shù) 學(xué) 軟 件 。Matlab 代碼編寫如下：tic。f=[3 11 3 10 1 9 2 8 7 4 10 5]。t=f’。ff=reshape(t,3*4,1)。20a=zeros(3,12)。for j=0:2a(j+1,4*j+1:4*(j+1))=1。endb=zeros(4,12)。for t=1:4for p=0:2 b(t,4*p+t)=1。endendAeq=[a。b]。Beq=[7 4 9 3 6 5 6]。lb=zeros(12,1)。[x,fval,exitflag,output,lambda]=linprog(ff,[],[],Aeq,Beq,lb)x=round(x)。 % 對(duì) x 取整.B=reshape(x,4,3)。 % 把 b 調(diào)為矩陣.B’toc。運(yùn)行結(jié)果：圖 310 調(diào)運(yùn)方案圖 311 總運(yùn)費(fèi)Elapsed time is 秒結(jié)果跟預(yù)想的一樣總運(yùn)費(fèi) 85 元，調(diào)運(yùn)方案也是一樣的。21 小結(jié)由上述對(duì)運(yùn)輸問題的求解過程和結(jié)果，可以得出以下結(jié)論：不論是用表上作業(yè)法求解，還是工具求解，其求解的結(jié)果是一樣的，總運(yùn)費(fèi)都是 85 元，調(diào)運(yùn)方案也是一樣。在整個(gè)求解過程中，雖然表上作業(yè)法很簡(jiǎn)單，無需懂得電腦操作，不過在求解時(shí)從初始方案的確定到最優(yōu)解的檢驗(yàn)，最后進(jìn)行調(diào)運(yùn)方案的調(diào)整，這一過程消費(fèi)大量時(shí)間，不像運(yùn)用工具求解那樣快捷。三個(gè)不同軟件進(jìn)行求解時(shí)，Excel 求解是不用進(jìn)行代碼編寫的，無需考慮算法和函數(shù)，只需進(jìn)行表格創(chuàng)建和參數(shù)設(shè)置，簡(jiǎn)單方便，直觀易用。而 Lingo 和 Matlab 是要進(jìn)行代碼編寫的，而且運(yùn)用的代碼算法和函數(shù)不一樣，相對(duì)于 Matlab，Lingo 的代碼比較簡(jiǎn)單，運(yùn)用到的函數(shù)就三個(gè)，不像Matlab，要考慮循環(huán)迭代問題。Excel、Lingo 和 Matlab 在求解過程中，Excel 不能進(jìn)行運(yùn)行時(shí)間的耗費(fèi)和內(nèi)存占用的測(cè)算，Lingo 在運(yùn)行結(jié)果中直接的出，直觀方便。而 Matlab則要用命令進(jìn)行，而且通過命令 tic 和 toc 只能得出時(shí)間耗費(fèi)，內(nèi)存的占用要通過任務(wù)管理器才能測(cè)算出來，不過在進(jìn)行上述案例求解時(shí)都是十分迅速的，總計(jì)都不到 1 秒，當(dāng)然在這樣一個(gè)簡(jiǎn)單的模型中其結(jié)果和速度是很難找出差別的，所以要采用一個(gè)更大規(guī)模，更復(fù)雜的模型再一一進(jìn)行求解，找出差別。22第四章 大型運(yùn)輸問題案例求解與運(yùn)輸問題的應(yīng)用 大型運(yùn)輸問題實(shí)例由于在上一章的例子中，數(shù)學(xué)模型較小，在用計(jì)算機(jī)求解時(shí)的結(jié)果沒有可比性，所以根據(jù)需要，本文中自擬了一個(gè)廣西某化肥廠產(chǎn)銷案例，案例中設(shè)計(jì)了 14 個(gè)產(chǎn)地和 91 個(gè)銷地，運(yùn)價(jià) c 主要依據(jù)兩點(diǎn)之間的距離來確定，得出了運(yùn)輸模型見附表 1：對(duì)廣西某化肥廠產(chǎn)銷案例分別用三個(gè)軟件采用上述方法進(jìn)行求解，得出結(jié)果進(jìn)行分析比較。運(yùn)行的環(huán)境：系統(tǒng)：Microsoft Windows XP Professional內(nèi)存：1Gb硬件內(nèi)存:160G虛擬光驅(qū)：DAEMON Tools 大型運(yùn)輸問題的 Excel 求解方法步驟同第三章的一樣，運(yùn)行結(jié)果如下： 圖 41 參數(shù)設(shè)計(jì)23圖 42 運(yùn)行結(jié)果運(yùn)用同樣的方法對(duì)案例進(jìn)行求解，得出的結(jié)果是“可變單元格過多” ，如上圖所示，說明該模型的規(guī)模對(duì)于 Excel 來說是過大的，處理不了。 大型運(yùn)輸問題的 Lingo 求解根據(jù)數(shù)模編寫代碼：sets: wh/wh1..wh91/:ai。 vd/vd1..vd14/:dj。 links(wh,vd):c,x。endsets data:ai=… ！銷量 dj=…！產(chǎn)量 c=…！運(yùn)價(jià) ?。? 由于數(shù)據(jù)較大，故省略.enddata min=@sum(links(i,j):c(i,j)*x(i,j))。 @for(wh(i): @sum(vd(j):x(i,j))=ai(i))。 @for(vd(j): @sum(wh(i):x(i,j))=dj(j))。end運(yùn)行結(jié)果：圖43 總運(yùn)費(fèi)24圖 44 調(diào)運(yùn)方案25圖 45 性能顯示Lingo 在進(jìn)行求解時(shí)是非常迅速的，整個(gè)過程運(yùn)行的計(jì)算時(shí)間花費(fèi)不到 1 秒，計(jì)算機(jī)內(nèi)存使用量是 282K,總迭代求解 395 次。模型運(yùn)行結(jié)果得總運(yùn)費(fèi)：。 大型運(yùn)輸問題的 Matlab 求解代碼編寫tic。f=[…]。 % 由于數(shù)據(jù)較大，故不顯示.t=f39。ff=reshape(t,91*14,1)。 a=zeros(91,1274)。for j=0:90 a(j+1,14*j+1:14*(j+1))=1。endb=zeros(14,1274)。for t=1:14 for p=0:90 b(t,14*p+t)=1。 endendAeq=[a。b]。 Beq=[…]。 % 由于數(shù)據(jù)較大，故不顯示 .lb=zeros(1274,1)。[x,fval,exitflag,output,lambda]=linprog(ff,[],[],Aeq,Beq,lb)b=reshape(x,14,91)。b39。toc。26運(yùn)行結(jié)果：圖 46 總運(yùn)費(fèi)圖 47 調(diào)運(yùn)方案Elapsed time is seconds.27CPU 使用占 12%，P F 使 用 率 為 479MB，見圖 48圖 48 內(nèi)存占用圖從用 Matlab 求解的結(jié)果可以看出，該模型的總運(yùn)費(fèi)是 44764， 結(jié)果分析 有三個(gè)軟件進(jìn)行求解的過程和結(jié)果可以明顯的比較出他們之間的差別： 在用 Excel 求解中出現(xiàn)了 “可變單元格過多” 的提示，而運(yùn)行終止，說明該模型的規(guī)模對(duì)于 Excel 來說是過大的，這就體現(xiàn)了專業(yè)軟件和非專業(yè)軟件的差別，在求解小型的數(shù)學(xué)模型時(shí)，在結(jié)果和運(yùn)算耗費(fèi)上是幾乎沒有差別的，但在求解較大型的數(shù)學(xué)模型時(shí)，其差別就十分明顯。 而在運(yùn)用 Lingo 和 Matlab 求解較大型的模型時(shí)的結(jié)果和耗時(shí)是幾乎沒有差別的，由運(yùn)行結(jié)果可以知道，他們求出方案的總運(yùn)費(fèi)都是一樣，都是44764，而且運(yùn)輸方案也是一樣。在執(zhí)行命令時(shí)所花費(fèi)的時(shí)間都不到 1 秒，速度非?？?，不同的是其所占用的內(nèi)存，Lingo 是 282K，而 Matlab 所占用的是內(nèi)存的 12%，即 1GB12%=，這比 Lingo 大得多。說明對(duì)于那種專門求解數(shù)學(xué)規(guī)劃問題的軟件來說，在求解的功能和機(jī)能是差不多的。 運(yùn)輸問題的應(yīng)用從上一節(jié)中可以知道使用工具對(duì)比較大型的運(yùn)輸問題進(jìn)行求解是非常28快的，而且求解簡(jiǎn)單。在現(xiàn)實(shí)生活中完全符合產(chǎn)銷平衡的運(yùn)輸問題的所有條件的情況是很少的，而是經(jīng)常出現(xiàn)一些特征類似但有一個(gè)或幾個(gè)特征卻不符合的問題，常見的情況有：產(chǎn)銷不平衡、最大化目標(biāo)、路線容量或路線最小量、不可接受的路線。因?yàn)檫\(yùn)輸問題都會(huì)有最優(yōu)解，所以把這些問題轉(zhuǎn)化成運(yùn)輸問題的數(shù)學(xué)模型，再進(jìn)行求解，就可以把問題解決，現(xiàn)在介紹幾種比較常見的問題。生產(chǎn)和儲(chǔ)存問題某工廠按合同規(guī)定當(dāng)年每季度分別提供 某產(chǎn)品，已知該廠各季的生jb產(chǎn)力為 及生產(chǎn)的單位成本 。又如果生產(chǎn)出來的產(chǎn)品當(dāng)季不交貨，單位iaijc產(chǎn)品每積壓一季度的儲(chǔ)存和維護(hù)費(fèi)等費(fèi)用為 d，要在完成合同的情況下，作出使該廠全年生產(chǎn)費(fèi)用最小的決策。若設(shè) 為第 季度生產(chǎn)的用于第 季度交貨的數(shù)量，又第 季度生產(chǎn)的ijxi j i用于第 季度交貨的單位實(shí)際成本為 應(yīng)該是該季度單位成本 加上儲(chǔ)存和維j 39。ijcijc護(hù)費(fèi)等費(fèi)用為 d，所以得出數(shù)學(xué)模型： （）???????????0min414141ijijijjiijijij39。xbaxxz顯然這是一個(gè)產(chǎn)大于銷的運(yùn)輸問題模型。航運(yùn)調(diào)度問題已知某航運(yùn)公司的航班情況見表 41，又知道每條船每次裝卸時(shí)間各需1 天，則該公司應(yīng)怎樣在滿足所有航線的運(yùn)貨要求分配船只使得用船只最少。表 41 某航運(yùn)公司的航班情況航線 起點(diǎn) 終點(diǎn) 每天航班數(shù)291 E D 32 B C 23 A F 14 D B 1表 42 兩港口之間的航行天數(shù)A B C D E FA 1 2 14 7 7B 1 0 3 13 8 8C 2 3 0 15 5 5D 14 15 13 0 17 20E 7 8 5 17 0 3F 7 8 5 20 3 0在求解中該公司所需要配備的船只分為兩種：第一種：載貨航程需要的周轉(zhuǎn)船只數(shù)航線 1 從 E 到 D，航行過程中需要的船只數(shù)為（17+2）3=57，同理，其他 3 天航行所需的船只分別為：B 到 C， （3+2）2=10；A 到 F， （7+2）1=9； D 到 B， （13+2） 1=15，則共需 57+10+9+15=91 條。第二種：空船調(diào)運(yùn)需要的周轉(zhuǎn)船只數(shù)這時(shí)就體現(xiàn)到運(yùn)輸問題的作用了，問題變?yōu)閺?C，D ，F(xiàn) 三個(gè)港口運(yùn)輸空船到 A，B，E 三個(gè)港口，要求其效率最高，則建立模型如表 43，這就是一個(gè)運(yùn)輸問題中的產(chǎn)銷平