中南大學(xué) 數(shù)學(xué)建模 lingo matlab 優(yōu)化建模論文 運輸問題的圖論優(yōu)化模型

運輸問題的圖論優(yōu)化模型摘要本文根據(jù)題設(shè)城市的道路情況和客戶需求情況，以客戶所在位置為節(jié)點，以客戶間所可以直接連通的道路為邊建立有向圖。建立了任意兩點間最短路徑長度和路徑的計算模型，建立了遍歷所有節(jié)點的最短路徑模型并做了模型分析和拓展討論。利用0-1規(guī)劃模型和上述兩個模型探索了分2輛有限容量汽車運輸?shù)目偮窂阶疃套顑?yōu)解。利用動態(tài)規(guī)劃模型和逼近算法及前述模型探討并實現(xiàn)了有限容量車的規(guī)劃問題，并對問題作了拓展性分析和模型評價。第一問我們考慮用最短路徑模型，首先用Matlab實現(xiàn)了Floyd算法，計算出了任意兩點的最短路線長度，并利用Floyd的原理通過正向追蹤法找出任意兩點的最短線路徑。用Pascal進(jìn)一步編寫程序?qū)崿F(xiàn)Floyd路徑，并匯總了中轉(zhuǎn)次數(shù)，發(fā)現(xiàn)全圖上有兩個路徑需要經(jīng)過兩點中轉(zhuǎn)才能獲得最短路徑，有一個路徑需要經(jīng)過三點中轉(zhuǎn)才能獲得最短路徑，其余各路徑至多只須經(jīng)過一點中轉(zhuǎn)即可獲得最短路徑。借鑒前面的Floyd最短路模型作為基礎(chǔ)，我們研究了最短運輸路徑問題，發(fā)現(xiàn)這是一個遍歷所有點的最短路徑問題，在經(jīng)典模型中沒有相關(guān)類似的描述。我們根據(jù)數(shù)據(jù)量作了評估，發(fā)現(xiàn)遍歷枚舉模型的時間復(fù)雜度為O(n3+n!)，對于只有10個節(jié)點的問題，這個時間復(fù)雜度可以在計算機(jī)1秒的運算內(nèi)解決，故采用Pascal編寫了一個枚舉程序，得到了最優(yōu)解。同時我們也探索了另外兩個模型，分別是“遍歷貪心次優(yōu)模型”和“插入逼近&遺傳算法近似最優(yōu)模型”（簡稱遍歷遺傳模型）。發(fā)現(xiàn)前者在無向圖中有較高概率得到最優(yōu)解，但隨著圖的復(fù)雜性和有向圖的引入，正確率降低，該模型計算的時間復(fù)雜度為O(n3+n2)。后者利用遺傳算法在比對足夠多次后我們用SPSS統(tǒng)計得到最優(yōu)解的概率趨于100%，針對本題我們設(shè)置的比對次數(shù)是1000,無法得到最優(yōu)解的概率小于10-30（參見4.3）,該模型計算的時間復(fù)雜度是O(n3+1000·n·n2)。我們可以發(fā)現(xiàn)對于10個節(jié)點以下問題用枚舉算法更優(yōu)，10個節(jié)點以上的問題需要考慮用近似算法去尋求最優(yōu)解更好。關(guān)于本文探討的圖，得到的最優(yōu)結(jié)果為最短路程225，且僅有一種方案。參考前述觀點，我們采取0-1規(guī)劃模型配合枚舉找到最優(yōu)解，若只考慮每個客戶都一次就拿到貨物，則0-1規(guī)劃的時間復(fù)雜度是O(2n)；若考慮同一個地點兩輛車可能各送一部分，0-1規(guī)劃的時間復(fù)雜度是O(22n)。經(jīng)過分析我們發(fā)現(xiàn)n<10的情況下，計算機(jī)可以在較短時間內(nèi)算得O(22n)，故我們用此方法得到了全局最優(yōu)解，總共有4種方案，2種方案每個客戶只需要收貨一次，兩車行駛的最短路程之和為280。關(guān)于出車問題安排，我們分了兩個步驟來建立模型，首先，我們證明發(fā)現(xiàn)派出的車盡量少，產(chǎn)生的費用才可能最優(yōu)（詳見7.2）。因此我們用動態(tài)規(guī)劃模型生成任意一種可行的使用最少車輛的方法（如7.3,7.4所述），然后再保證不超過總?cè)萘康臈l件下通過任意兩車轉(zhuǎn)移或者交換貨物，檢查對應(yīng)兩車所需要走的總路程是否有縮短，若縮短則保留，若無縮短則放棄修改，直到一次完整比較后未發(fā)生任何改變則說明已經(jīng)找到了最優(yōu)解，我們找到的最少總費用為655元。為了驗證算法，我們也嘗試構(gòu)造了一個枚舉模型，通過Pascal篩選可以裝下的方案發(fā)現(xiàn)，從10個貨物中選3個貨物總共有35種可行方案，從10個貨物中選2個貨物總共有43種可行方案。在用組合算法把方案匯總并作合理性判斷，然后比對得出最優(yōu)解。關(guān)鍵字：Floyd改進(jìn)模型遍歷貪心模型遍歷遺傳模型遍歷枚舉模型0-1規(guī)劃模型

問題重述快遞公司要為10個客戶配送貨物，10個客戶間的道路關(guān)系如附件一的鄰接矩陣所描述，現(xiàn)分別需要解決如下問題：1）接到臨時派遣通知時，迅速找到從當(dāng)前點到達(dá)目標(biāo)客戶的最短線路方案。（擬給出2號客戶到10號客戶間的最短路徑方法。）2）出發(fā)給所有客戶送貨物，并回到出發(fā)地的所走的最短線路方案。3）用兩輛容積是50的貨車送貨，十個地點所需要的貨量分別為8，13，6，9，7，15，10，5，12，9。給出方案確定兩輛貨車應(yīng)分別給哪幾個客戶配送貨物，按照什么樣的路線送，使路線合最短。送貨后貨車需要回到出發(fā)點。4）若用容積25的貨車運貨，每出一輛車的出車費為100元，運貨的價格為1元每公里（不考慮空車返回的費用），如何安排車輛才能使得運輸公司運貨的總費用最省。問題分析問題背景分析現(xiàn)代生活對于效率的要求越來越高，近幾年又提倡構(gòu)建節(jié)約型社會，因此如何高效、節(jié)約的選擇路線不僅僅是快遞公司所面臨的問題，同樣也是百姓出門所面臨的實際問題，本論文以快遞公司的運輸問題為例來描述算法，但算法同樣可以引申到社會實際生活中來，該問題具有很強(qiáng)的實際意義和價值。問題要求分析據(jù)題意，解決該問題關(guān)鍵在以下幾個方面：找到任意兩點間的最短路線長度及路徑。找到經(jīng)過一系列點的最短路徑長度及路徑。在運輸有限制的條件下，如何分配，使得車行總路程最短。在換算為費用問題的情況下，如何評估和分配，使得運輸總成本最低?；炯僭O(shè)附件一的鄰接矩陣的道路均可通行，不存在堵車、施工等問題。每次提貨地點都在客戶1所在的位置，但是給客戶1送貨仍需要占用貨車的空間。假設(shè)貨物可以分割。在用容量為50的貨車運輸時，客戶愿意分多次接受貨物。在用容量為25的貨車運輸是，客戶只愿意一次將貨物接受完全。符號說明n ：表示有個客戶；v ：每輛車的總承載量；i ：表示第個客戶； ：表示第個客戶所需的貨物量； ：表示個客戶分配車輛后的剩余車載量； ：表示將第個客戶的貨物分配給了車輛； ：表示每輛車裝完貨物后的剩余載重； ：表示第i輛車裝載的第j種貨物； ：表示第i個客戶。圖中表示節(jié)點。 ：表示第i個客戶到第j個客戶的路。圖中表示邊(弧)。 ：表示第i個客戶到第j個客戶的路程。圖中表示邊權(quán) ：表示0-1變量

模型的建立及求解建圖重述矩陣矩陣分析有向圖無向圖的判定首先我們發(fā)現(xiàn)圖并非關(guān)于i=j這條對角線對稱，故說明存在有e(i,j)e(j,i)，即兩點間的邊權(quán)值根據(jù)其方向不同可能不同。因此無向圖無法描述，只能用有向圖描述。出度入度不等V1的出度等于E[1,j]0且E[1,j](j[1,n])的點的個數(shù)。V1的入度等于E[1,j]0且E[i,1](i[1,n])的點的個數(shù)。顯然可發(fā)現(xiàn)有部分節(jié)點的出度與入度不相等，可以說明該有向圖的部分邊為單邊，可以理解為道路中的單行線。邊點分析矩陣中的每一個數(shù)值代表一條邊，故可知圖總共有64條邊，有10個頂點，故假若有算法可以使其進(jìn)行邊點轉(zhuǎn)換。則所生成的圖的點將達(dá)到64個，計算規(guī)?？赡芨螅瑥?fù)雜度可能更高。有向圖概覽根據(jù)鄰接矩陣我們制作出了該鄰接矩陣所描述的有向圖可以看出題目所述的圖相當(dāng)?shù)膹?fù)雜，因此我們采用（i,j,k）的方式描述邊權(quán)，即（i,j,k）的含義為Vi到Vj有一條邊，邊權(quán)為k。根據(jù)此圖我們可以進(jìn)一步驗證1.2的分析結(jié)果，此圖也為手工驗算程序的結(jié)果提供了方便。

Floyd模型解題思路及結(jié)果解題思路根據(jù)問題的描述該問要解決臨時接到通知時選擇一條道路到達(dá)目的地的方法，簡化來看這就是一個尋找從當(dāng)前點到目標(biāo)點的最短路問題。按照問題要求，我們需要給出有向圖中找到從V2到V10的最短路線的路徑。根據(jù)經(jīng)典問題求最短路徑的解法[1]，我們可以用dijkstra算法或者Floyd算法，dijkstra算法可以算出從某一點出發(fā)到其他所有點的最短路徑。Floyd算法可以一次性計算出任意兩點的最短路徑。通過綜合分析這道題目，為了進(jìn)一步擴(kuò)展得到任意兩點的最短路徑為后續(xù)問題做好基礎(chǔ)，我們選擇了用Floyd算法，直接算出任意兩點間的最短路長度和對應(yīng)路徑。結(jié)果經(jīng)過本模型可以算得最優(yōu)解：V2到V10的最短路徑是：2-->3-->8-->9-->10其總長度為：85Floyd算法描述Floyd算法計算最短路線的長度Floyd算法的優(yōu)勢是，它可以直接求出含負(fù)權(quán)的網(wǎng)絡(luò)中任意兩點之間的最短路，只是相對Dijkstra算法要稍微復(fù)雜些。Floyd計算的時間復(fù)雜度是O(n3)，空間復(fù)雜度是O(n2)令網(wǎng)絡(luò)N=（V，E，W）的權(quán)矩陣為其中權(quán)矩陣中的用N（i,j,m）表示頂點集合，導(dǎo)出的N的子網(wǎng)絡(luò)。特別的，N（i,j,0）表示由頂點集導(dǎo)出的N的子網(wǎng)絡(luò)。把網(wǎng)絡(luò)N（i,j,m）中最短路的長記為，則顯然有如下結(jié)論：（1）；（2）N（i,j,n）=N，因此為N中最短路的長；（3）N（i,j,m-1）是N（i,j,m）的子網(wǎng)絡(luò)，故；（4）N（i,m,n）=N（i,m,m-1）,N（m,j,m）=N（m,j,m-1）,所以，。Floyd算法計算最短路線的路徑為了求網(wǎng)絡(luò)N（i,j,m）中最短路的長同時求出N（i,j,m）中最短路路，引“進(jìn)后點標(biāo)號”。令表示路的第一條弧的箭頭的下標(biāo)，顯然，。若已經(jīng)知道，當(dāng)時，則；否則，。若，=k，則是D中最短路，從而的第一條弧即為的第二條弧，依次類推，可以得到上的所有弧。這種方法稱為正想追蹤法。Floyd的使用條件根據(jù)Floyd算法使用的條件發(fā)現(xiàn)：1）本題中網(wǎng)絡(luò)N=(V,E,W)不含負(fù)回路，則對一切i,j=1,2,…,n，滿足2）對于任意的i,j,m,不超過網(wǎng)絡(luò)N（i,j,m）中任何一條路的長。因此題目的所生成的有向圖可以使用Floyd算法。程序的Matlab實現(xiàn)及相關(guān)中間狀態(tài)W=程序步驟及說明輸入W矩陣(W同附件一)，存入a，當(dāng)兩點不能直接到達(dá)時及兩點之間的距離為時，這兩個點之間的距離描述為M，程序中賦值為10000。為記錄走過的路徑，建立一個初始為全零的與a矩陣同大小的path矩陣。開始floyd算法比較a(i,j)>a(i,k)+a(k,j)是否成立，若成立則將a(i,j)替換成a(i,k)+a(k,j)，與此同時路徑中代表從i出發(fā)到j(luò)的最短路徑需要經(jīng)過k來中介，因此path(i,j)=path(i,k);當(dāng)場經(jīng)過k,i,j[1,n]的所有情況后，原a被修正成了SSSP路徑即任意兩點間的最短路徑。而path(i,j)中的值則表達(dá)從i到j(luò)的最短路徑中，下一步該到那個點。程序核心代碼（MatLab）%floyd算法fork=1:10fori=1:10forj=1:10ifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=path(i,k);endendendend%輸出路線結(jié)果的過程i1=input('請輸入起點');i2=input('請輸入終點');disp(i1);whilei1~=i2%i1==i2說明已到達(dá)終點，停止探索，結(jié)束程序。i1=path(i1,i2);disp(i1);end;%完全代碼請參看附錄程序結(jié)果分析根據(jù)W矩陣，我們算得：最短路徑矩陣其中可看到a(2,10)=85,即2到10的最短路徑長度為85。路徑記錄矩陣我們在此演算從V2到V10路徑的計算過程：由path(2,3)=3可知從V2到V10得先經(jīng)過V3；由path(3,10)=8可知從V3到V10得先經(jīng)過V8;由path(8,10)=9說明V8到V10需要經(jīng)過V9,由path(9,10)=10，說明V9到V10可直接到達(dá)。故送貨員要在下完客戶2的貨然后要送貨給客戶10，所走的路徑是：V2V3V8V9V10（總長度為85）模型評價該問題直接采用了經(jīng)典算法Floyd算法，故算法可靠穩(wěn)定準(zhǔn)確，可以得到最優(yōu)解。利用該模型可以容易的計算出任意兩點間的最短路線長度及最短路線路徑。模型補充由于后面要解決的問題復(fù)雜性增高，因此我們用Pascal語言編寫了一個更便于人機(jī)交互和模型補充的程序。算法與前述類似，但稍有改進(jìn)。詳細(xì)代碼見附錄六：問題1的pascal程序（模型2）。遍歷貪心模型解題思路及結(jié)果解題思路分析這一問題，我們可以發(fā)現(xiàn)，這算個問題簡化描述，就是找一條最短路徑經(jīng)過所有的節(jié)點并返回，這一問題沒有經(jīng)典算法可以直接使用，因此只能夠造算法。假若要構(gòu)造時間復(fù)雜度盡可能低的算法，我們當(dāng)然首先想到了容易構(gòu)造出O(n2)為時間復(fù)雜度的貪心算法，此算法最終會遍歷所有的點，因此我們命名叫做便利貪心模型。貪心算法是不斷尋找局部最優(yōu)解進(jìn)而產(chǎn)生全局最優(yōu)解的算法，因此它需要各個局部都相對獨立，這樣才能得到全局最優(yōu)解，但是題述問題并不是一個局部獨立問題，因此使用便利貪心算法只能得到近似解。結(jié)果經(jīng)過后面多種算法運算比較，發(fā)現(xiàn)此算法在本題數(shù)據(jù)下得到的不是最優(yōu)解，只是近似解，路程總長度為240，而最優(yōu)解總長度為225，算法請參考4遍歷遺傳算法和5遍歷枚舉算法。次優(yōu)解得路徑是V1V5V7V5V2V3V4V8V9V6V9V10V1貪心算法所謂貪心算法是指，在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。[2]遍歷貪心算法假設(shè)現(xiàn)有一最短距離矩陣X=，按貪心算法，從第一個節(jié)點出發(fā)找到矩陣第一行不為零的最小數(shù)，然后轉(zhuǎn)入第i行找不為零的最小的數(shù)且j在前面不曾取入,重復(fù)這樣找下去，遍歷所有行。算法樣例1下面為說明貪心算法有一定的可行性我們以一個簡單的例子說明：圖3.1如圖3.1所示的網(wǎng)絡(luò)圖為一個負(fù)權(quán)的無向網(wǎng)絡(luò)圖，根據(jù)floyd算法可以得出該網(wǎng)絡(luò)圖任意兩點之間的最短距離構(gòu)成的矩陣為運用貪心算法算出的路徑及兩點間的最短距離如下所示最短路程為22；貪心過程如下：第一行找到非0，最小，且未到過的點為：2第一行找到非0，最小，且未到過的點為：3第一行找到非0，最小，且未到過的點為：4第一行找到非0，最小，且未到過的點為：5因此得到的路徑如圖3.2。112341513387圖3.2圖3.2并不是最終結(jié)果，只是遍歷時到達(dá)關(guān)鍵點的順序，關(guān)鍵點之間用最小路徑相連就得到了真正的遍歷路徑。如圖3.3：112351433113123552圖3.3算法樣例2但是貪心算法得出的是局部最優(yōu)解，整體最優(yōu)解不一定就會等于局部最優(yōu)解，如圖3.4所示的網(wǎng)絡(luò)圖為一個負(fù)權(quán)的無向網(wǎng)絡(luò)圖，根據(jù)floyd算法可以得出該網(wǎng)絡(luò)圖任意兩之間的最短距離矩陣為（圖3.4）運用貪心算法算出的路徑及兩點間的最短距離關(guān)鍵點如圖3.5所示總路線長：26112341515389圖3.5其路徑如圖3.6：112351433113143554圖3.6但上述結(jié)果事實證明不是最優(yōu)解，最優(yōu)解如圖3.7。11254331137545圖3.7根據(jù)圖3.7計算，總路線長：25故比貪心算法更優(yōu)，說明貪心算法有其局限性。程序的Pascal實現(xiàn)程序步驟及說明程序較為簡單，就是利用一個集合保存已經(jīng)走過的點，每次找到符合約束條件的點加進(jìn)集合，直到全部加進(jìn)。加入的順序就是關(guān)鍵序列的順序。在通過兩點最短路徑擴(kuò)充，就得到了所需路徑。程序核心代碼（Pascal）c[1]:=1;ci:=1;s:=0;whileci<ndobegink:=32760;fori:=1tondobeginm:=1;forj:=1tocidoifc[j]=ithenm:=0;if(b[c[ci],i]<>0)and(m=1)and(b[c[ci],i]<k)thenbegink:=b[c[ci],i];c[ci+1]:=i;end;end;inc(ci);s:=s+kend;s:=s+b[c[ci],1];模型評價此算法是非完美的，但時間復(fù)雜度較低，因此在數(shù)據(jù)量上千的情況時，不需要得到精確解，只需要有近似值時，可以用這種模型。遍歷遺傳模型解題思路及結(jié)果解題思路由于貪心算法的局限性，前文通過遍歷貪心模型得到的解并不一定是最優(yōu)解，接下來我們通過遍歷遺傳模型來求這個最短路程，并證明這樣得出的解一定是最優(yōu)解。結(jié)果結(jié)合遍歷遺傳算法與插入法得到從提貨點出發(fā)給10個客戶配送完貨物后再回到提貨點所行駛的最優(yōu)解路徑為V1V5V7V6V3V4V8V9V10V1最短行駛路程為225。插入法的描述插入法的核心思想就是，根據(jù)元素（送貨點）插入順序的不同，得到不同的排列，通過計算相鄰兩點間的最短距離并且累加求和，選擇路程最短的排列，然后不斷的把剩下的點按照之前的方法進(jìn)行插入，最終得到最優(yōu)的路徑。插入法的步驟對于第二個問題，我們已經(jīng)知道貨車的提貨點和客戶1(點)是在同一個地方，意思是貨車從1出發(fā)。 插入法的算法： 對于給定的插入排列（），開始路徑為road=-，。、開始插入，；比較每一種插入方式下的相鄰兩點最短路徑的總和，取其中的最小值，并且把原先的優(yōu)化路徑更改為road=-…--…-。、如果，那么停止，否則就繼續(xù)插入下一個點。插入法的范例說明對于一個這樣的兩點距離用鄰接矩陣的圖表示，求從開始出發(fā)，通過所有點且返回的最短路徑的問題，網(wǎng)絡(luò)圖如圖4.1所示：（其中表示兩個客戶之間無直接的路線到達(dá)）圖4.1利用Floyd算法，得到任意兩點之間的最短距離，如表4.1所示12345105638250739337045453406589560表4.1插入法的圖形表達(dá)如圖4.2：插入序列13245插入序列13245路徑131Stage2插入2插入21231路程151321路程18最優(yōu)路徑1231Stage3 插入4路徑1231插入414231路程1612431路程1512341路程21最優(yōu)路徑12431路徑11Stage1插入3插入3131顯然最優(yōu)路徑131Stage4插入5插入5152431路程27125431路程27124531路程22124351路程25最優(yōu)路徑124531路徑12431Stage5路徑124531由此我們我們對于13245這樣的插入順序列得到的最短路徑是22，其中最短的經(jīng)過實際路徑為1-3-4-2-4-5。4．3遺傳算法的描述遺傳算法的核心思想是模擬自然界生物進(jìn)化過程，采用人工進(jìn)化的方式對目標(biāo)空間進(jìn)行隨機(jī)化搜索。它將問題域中的可能解看作是群體的一個個體或染色體，并將每一個體編碼成符號串形式，模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程，對群體反復(fù)進(jìn)行基于遺傳學(xué)的操作（遺傳，交叉和變異），根據(jù)預(yù)定的目標(biāo)適應(yīng)度函數(shù)對每個個體進(jìn)行評價，依據(jù)適者生存，優(yōu)勝劣汰的進(jìn)化規(guī)則，不斷得到更優(yōu)的群體，同時以全局并行搜索方式來搜索優(yōu)化群體中的最優(yōu)個體，求得滿足要求的最優(yōu)解。4．3.1遺傳算法操作步驟1）編碼我們將每一個插入序列作為一個生命體，那么給其賦予一定的基因，這個過程叫做編碼初始群體的生成由于遺傳的需要，我們必須設(shè)定一些初始的生物群體，讓其作為生物繁殖的第一代，需要說明的是，初始群體的每個個體都是通過隨機(jī)方法產(chǎn)生的，這樣便可以保證生物的多樣性和競爭的公平性。適應(yīng)度評估檢測生物的進(jìn)化服從適者生存，優(yōu)勝劣汰的進(jìn)化規(guī)則，因此，我們必須規(guī)定什么樣的基因是“優(yōu)”的，什么樣的基因是“劣”的，在這里，我們認(rèn)為那些使得路程短的基因是優(yōu)的，而使路程長的基因是劣的。選擇接下來，我們便可以進(jìn)行優(yōu)勝劣汰的過程，這個過程在遺傳算法里叫做選擇。注意，選擇應(yīng)該是一個隨機(jī)的過程，基因差的生物體不一定會被淘汰，只是其被淘汰概率比較大罷了，這與自然界中的規(guī)律是相同的。因此，我們可以采取賭論的方式來進(jìn)行選擇。交叉操作接下來進(jìn)行交叉繁殖，隨機(jī)選出兩個生物體，讓其交換一部分基因，這樣便形成了兩個新的生物體，為第二代。變異生物界中不但存在著遺傳，同時還存在著變異，在這里我們也引入變異，使生物體的基因中的某一位以一定的概率發(fā)生變化，這樣引入適當(dāng)?shù)臄_動，能避免局部極值的問題。以上的算法便是最簡單的遺傳算法，通過以上步驟不斷地進(jìn)化，生物體的基因便逐漸地趨向最優(yōu)，最后便能得到我們想要的結(jié)果。流程圖如圖4.3所示編碼和初始群體形成編碼和初始群體形成適應(yīng)度的檢測評估選擇交叉變異圖4.34.3.2模型改進(jìn)根據(jù)插入法改進(jìn)模型，我們就可以對于這樣一個從提貨點出發(fā)給10個客戶配送完貨物后再回到提貨點所行使的盡可能短的行使路線的問題給出最優(yōu)解的答案。其中，最短行駛的距離是225。走過的實際路線為 1576348910214．4程序的Pascal實現(xiàn)及相關(guān)中間狀態(tài)4．4．1程序核心代碼（Pascal）forl:=1to1000dobegin//變異1000次s:=32760;randomize;fori:=1to100dobegin//突變頻率j:=round(random*(n-2))+2;k:=round(random*(n-2))+2;if(j>n)or(j<1)thenj:=n;if(k>n)or(k<1)thenk:=1;i1:=c[k];c[k]:=c[j];c[j]:=i1;end;d[1]:=1;f[1]:=1;f[2]:=1;fori:=ndownto2dobegin//開始嘗試插入法s:=32760;forj:=2ton-i+2dobegind:=f;m:=0;fork:=n-i+2downtojdobegind[k+1]:=d[k];end;d[j]:=c[i];fork:=1ton-i+2dobeginm:=m+b[d[k],d[k+1]];end;ifm<sthenbegins:=m;e:=d;end;end;f:=e;end;//比較插入法值的大小ifs<ssthenbeginss:=s;g:=f;end;end;模型評價與分析盡管插入遺傳的尋優(yōu)方式帶有一定的隨機(jī)性。但是當(dāng)我們對于所有插入順序序列得到的解用SPSS13進(jìn)行頻數(shù)統(tǒng)計，得到結(jié)果如下表4.2所示：FrequencyPercentValidPercentCumulativePercentValid225.002483230.0012234333.733.740.6235.008220822.722.763.2240.00260697.27.270.4245.00279077.77.778.1250.00283177.87.885.9255.003297260.00123313.43.498.4265.0036771.01.099.4270.001973.5.599.9275.00144.0.0100.0280.00101.0.0100.0Total362880100.0100.0表4.2發(fā)現(xiàn)最優(yōu)解出現(xiàn)的概率為6.8%。當(dāng)變異的次數(shù)達(dá)到43時，得不到最優(yōu)解的概率為0.048。根據(jù)概率論中小概率事件的定義，如果一個事件發(fā)生的概率小于0.05時，可以認(rèn)為這個事件不會發(fā)生。我們可以認(rèn)為，這個遍歷遺傳算法，有及其頑強(qiáng)的魯棒性，可以求到問題的最優(yōu)解。遍歷枚舉模型解題思路及結(jié)果解題思路同前兩模型要解決的問題一樣，這是一個找一條最短路徑經(jīng)過所有的節(jié)點并返回的模型。前兩個模型中一個是近似算法，一個是逼近最優(yōu)解算法，但都不能說100%得到最優(yōu)解。因此我們構(gòu)造出了這個遍歷枚舉模型。所謂枚舉，就是把所有的可能性都列出來，在做比較。若關(guān)鍵點包含有所有點，我們發(fā)現(xiàn)遍歷路徑的總長度只取決于關(guān)鍵點的順序。因此我們利用排列的模型不斷生成新的序列，并把產(chǎn)生序列作為關(guān)鍵序列，比對并計算，從而得到最優(yōu)解。n的排列數(shù)為n!,故用遍歷枚舉模型只能解出較少點數(shù)的圖。10個點正好為臨界值范圍內(nèi)，故本題可以利用此算法得到最優(yōu)解。結(jié)果最優(yōu)解總長度為225，與遍歷遺傳算法所得相同。最優(yōu)解得路徑是：V1V5V7V6V3V4V8V9V10V1枚舉算法描述枚舉算法是先設(shè)置一組初初狀態(tài)，通過特定的運算使其狀態(tài)發(fā)生改變，經(jīng)過有序的有限次數(shù)的改變，到達(dá)末狀態(tài)，此時經(jīng)過了所有狀態(tài)的算法。這種算法的優(yōu)越性在于可以根據(jù)程序需要做必要的剪枝操作以便簡化程序。遍歷枚舉算法如解題思路所述，利用排列的經(jīng)典算法產(chǎn)生序列，在利用程序?qū)㈥P(guān)鍵點擴(kuò)充成運輸路徑。比對路徑長度就可以的到最優(yōu)解。程序的Pascal實現(xiàn)及相關(guān)中間狀態(tài)程序核心代碼（Pascal）proceduresol;//計算最短路，比較是不是比前面的方案更優(yōu)，更優(yōu)的話則記錄下來。vari,j,k:integer;begink:=0;fori:=1ton-1dok:=k+b[plan[i],plan[i+1]];k:=k+b[plan[n],1];ifk<sthenbegins:=k;c:=plan;end;//main主程序部分的調(diào)用s:=32760;fori:=1tondoplan[i]:=i;sol;repeat//排列序列的生成經(jīng)典算法findi;ifi>1thenbeginfindj;change;ifplan[1]<>1thenbreak;sol;end;untili<=1;模型評價毫無疑問這個模型是既具有價值的，因為它是唯一個可以拿到最優(yōu)解的模型，因為它嘗試了所有的可行方案，但是由于時間復(fù)雜度很高，因此在點數(shù)很多的時候該算法無法算出結(jié)果。但該算法為近似解得算法改進(jìn)奠定了基礎(chǔ)。因此該算法的價值不容忽略。模型拓展該模型可以拓展加入比判斷，輸出最優(yōu)解的所有情況。因此經(jīng)過本模型計算后，我們可以放心大膽的說，最有序列有且只有一個，路程為225的這個解法是該圖遍歷點的路徑的最優(yōu)解。0-1規(guī)劃模型6．1解題思路及結(jié)果6．1．1解題思路0-1目標(biāo)規(guī)劃法是用來處理選型問題的多維性，其中自變量取值只能取0和1兩個值。我們可以通過0-1規(guī)劃模型為十個客戶的貨物分車裝載運輸。6．1．2結(jié)果兩輛小車分配所需運送的貨物后行駛的最短路線按卸貨順序有4種分配方式：方案1.卸貨位置:car1:17691car2:152348101實際路徑car1:V1→V7→V6→V9→V1car2:V1→V5→V2→V3→V4→V8→V9→V10→V1方案2.卸貨位置car1:17691car2:1523489101實際路徑car1:V1→V7→V6→V9→V1car2:V1→V5→V2→V3→V4→V8→V9→V10→V1方案3.卸貨位置car1:1769101car2:1523481實際路徑car1:V1→V7→V6→V9→V10→V1car2:V1→V5→V2→V3→V4→V8→V9→V1方案4.卸貨位置car1:1769101car2:15234891實際路徑car1:V1→V7→V6→V9→V10→V1car2:V1→V5→V2→V3→V4→V8→V9→V16．2建立模型6．2．1模型建立c假設(shè)第一輛車用十個0-1變量（j=1~10）來控制，第二輛車也用十個0-1變量（j=1~10）來控制。，其中i=1~2,j=1~10；因表示第j個客戶所需的貨物量，設(shè)函數(shù)dd(n,c1,c2,…,cn)為遍歷中不為0的結(jié)點的最短路徑長度。實現(xiàn)方法為前述3個模型。由此我們可以建立模型：minZ=dd(n,1x11,2x12,3x13,…,10x110)+dd(n,1x21,2x22,3x23,…,10x210)s.t.

s.t.6．2．3模型說明由條件可知不會同時為0，故只能兩個中一個為0，一個為1，或兩個都為1。1）當(dāng)=0，=1時，說明第j個客戶的貨物由第二輛車來運送；2）=1，=0時，說明第j個客戶的貨物由第一輛車來運送；3）=1，=1時，說明第j個客戶的貨物拆分為兩份，分別由第一輛車和第二輛車運送。重量判斷假若沒有貨物拆成兩份的情況，重量很好判斷，兩輛車分別小于等于25就是可以滿足的重量。在有貨物拆分的情況下，經(jīng)過分析發(fā)現(xiàn)，除了需要拆分的貨物外，其余貨物總合要小于25即重量會有合格的方案。程序?qū)崿F(xiàn)proceduremake_xl;//序列生成模塊vari,j,k:integer;begin//repeati:=n*2;whilexl[i]<>0dodec(i);ifi<1thenover:=true;xl[i]:=1;forj:=i+1ton*2doxl[j]:=0;forj:=1tondoifxl[j]=0thenxl[j+n]:=1;xl[1]:=1;xl[1+n]:=1;{k:=1;forj:=1tondoifxl[j]+xl[n+j]=0thenbegink:=0;break;end;}//if(xl[1]<>1)or(xl[1+n]<>1)thenk:=0;//until{(k=1)or}(over);end;functionkeyun:boolean;//超重判斷模塊vari,j,k,w1,w2:integer;pd:boolean;beginw1:=0;w2:=0;k:=0;pd:=true;fori:=1tondobeginif(c1[i]=1)and(c2[i]=0)thenw1:=w1+zl[i];if(c1[i]=0)and(c2[i]=1)thenw2:=w2+zl[i];if(c1[i]=1)and(c2[i]=1)thenk:=1;if(c1[i]=0)and(c2[i]=0)thenpd:=false;end;if(w1>50)or(w2>50)thenpd:=false;ifk=1thenif(w1=50)or(w2=50)thenpd:=false;keyun:=pd;end模型評價該模型巧妙利用0-1規(guī)劃的思想，具體問題具體分析，進(jìn)而將問題各種因素全部都考慮囊括在內(nèi)，是一個標(biāo)準(zhǔn)的完全算法。假若用戶不允許貨物拆分的話，那么可以把規(guī)劃的位數(shù)從20位縮小到10位，即兩輛車總有一輛送。動態(tài)規(guī)劃交換逼近模型解題思路及結(jié)果解題思路本文在前一問的基礎(chǔ)上，增加了出車的數(shù)量，故首先我們要判斷到底需要多少輛車，通過動態(tài)規(guī)劃的思想，我們發(fā)現(xiàn)最少要用4輛車。但究竟4輛車更優(yōu)還是5輛車更優(yōu)，我們給出了相關(guān)證明。證明發(fā)現(xiàn)4輛車的結(jié)果比5輛車的更優(yōu)，然后，我們在保證不超重地情況下，采取交換兩車物品判斷兩車所走的路徑是否更優(yōu)的逼近的方法，不斷逼近最優(yōu)值。當(dāng)一次完整的比對所有車后沒有發(fā)生變化，說明找到了最優(yōu)解。結(jié)果有兩組等價結(jié)果所需要價格為655元，方案分別為：方案1.卸貨位置car1:12car2:76car3:1034car4:589實際路徑car1:V1→V1→V5→V2car2:V1→V7→V6car3:V1→V9→V10→V3→V4car4:V1→V5→V8→V9方案2.卸貨位置car1:52car2:76car3:189ca4:1034實際路徑car1:V1→V5→V2car2:V1→V7→V6car3:V1→V1→V5→V8→V9\car4:V1→V9→V10→V3→V4相關(guān)證明反證法：假設(shè)開出5輛車，每輛車的載重均不超過25個單位，五輛車的總費用少于開出四輛車的總費用。由已知條件可知（i=1~10），四輛車中有兩輛裝有2個客戶的貨物，兩輛車裝有3個客戶的貨物。1） 因為從任意的客戶i到客戶j的運費均小于100，故增開第五輛車從提貨點直接為客戶j運送貨物能使前四輛車減少的費用小于100，而第五輛車的費用為100+顯然比100大，故增開第五輛車來運送一個客戶所需貨物會使總費用增大；2） 若5輛車每兩車個跑兩個客戶的方案比較復(fù)雜，因此用程序模擬發(fā)現(xiàn)，題設(shè)數(shù)據(jù)這樣能夠得到的最優(yōu)解是275的路程，在加上500的出車費用，最后等于775的價格。找出任意一種裝車送貨方案的動態(tài)規(guī)劃算法分配第一輛車時的表格如下：i12345678910Ai81369715105129Bi17411242165201133133131）、找到一個i，令Bi=min{Bj}，將i客戶貨物裝車；

2）、找尋k，令，若則將客戶k的貨物裝車，并令i=k并重復(fù)步驟2；若k=0，則該車貨物裝完。分配第二輛車時，將第一輛車已分配了的客戶的貨物去掉，將剩余的客戶的貨物按原來客戶序列重新排列，按第一輛車分配的方法重復(fù)。分配第三、第四輛車用類似方法，最終得出一種裝車送貨方案：第一輛車所需到達(dá)的點為1、3、6、7，貨物總量為24；第二輛車所需到達(dá)的點為2、5、8，貨物總量為25；第三輛車所需到達(dá)的點為4、6，貨物總量為24；第四輛車所需到達(dá)的點為9、10，貨物總量為21。簡化為表格表述如下：所需到達(dá)的點1、3、6、72、5、84、69、10客戶貨物組合86101375915129貨物總量24252421剩余載重1013調(diào)整裝車送貨方案，以得到更優(yōu)的裝車送貨方案1）、由上表可知，四輛車的剩余載重均不會超過客戶的最小貨物需求量，故本例中只能通過車輛之間貨物的交換才可能出現(xiàn)更多的裝車送貨方案。2）、尋找任意兩輛車中能夠交換的客戶的貨物并且仍然滿足4輛車不超過其載重的條件為表示第m輛車中的第n種貨物可以與第i輛車的第j種貨物交換。通過前面的模型計算出交換前后輛車路程的距離和，作比較，若交換后會導(dǎo)致路程減小，則保留交換后的狀態(tài)，完成交換，否則的話復(fù)原成交換前。最優(yōu)解的判斷條件7．4所述的調(diào)換方案在任意兩車間進(jìn)行，故第1輛車要嘗試與2、3、4輛車各物品交換，第2輛車要與3、4兩車各物品交換，第3輛車要與第4輛車各物品嘗試交換。我們管這樣經(jīng)過一次完整的交換過程叫做一個“完全交換嘗試”。假若經(jīng)過一個“完全交換嘗試”后，沒有發(fā)生一次交換，則說明當(dāng)前狀態(tài)已經(jīng)是最優(yōu)解。若發(fā)生過至少一次交換則需要重復(fù)做一次“完全交換嘗試”進(jìn)行判斷。程序的Pascal實現(xiàn)程序核心代碼（Pascal）//ii<-->jjforii:=1to3doforjj:=ii+1to4dofork:=1tocar[ii,0]doforl:=1tocar[jj,0]dobeginif(car[ii,-1]+zl[car[ii,k]]-zl[car[jj,l]]>=0)and(car[jj,-1]+zl[car[jj,l]]-zl[car[ii,k]]>=0)thenbegincar[ii,-1]:=car[ii,-1]+zl[car[ii,k]]-zl[car[jj,l]];car[jj,-1]:=car[jj,-1]+zl[car[jj,l]]-zl[car[ii,k]];m:=car[ii,k];car[ii,k]:=car[jj,l];car[jj,l]:=m;fillchar(dot,sizeof(dot),0);dot[1]:=1;fori1:=1tocar[ii,0]dodot[i1+1]:=car[ii,i1];car[ii,-2]:=qiongjubuhui(car[ii,0]+1);fillchar(dot,sizeof(dot),0);dot[1]:=1;fori1:=1tocar[jj,0]dodot[i1+1]:=car[jj,i1];car[jj,-2]:=qiongjubuhui(car[jj,0]+1);if(car[ii,-2]+car[jj,-2]<car2[ii,-2]+car2[jj,-2])thenbegincar2:=car;ok:=false;end;end;car:=car2;end;模型驗證通過編寫了一個組合序列生成器生成所有可能的10選3情況，和10選2情況，通過質(zhì)量要小于等于25的條件作為篩選，共篩選出78條。進(jìn)行78選4的方式的組合，并判斷是否能走遍所有的點，篩選出116條可行方案，對116條可行方案求值，發(fā)現(xiàn)結(jié)果與上述算法所得結(jié)果一致。（相關(guān)數(shù)據(jù)見附錄）。模型評價該模型相比校驗用的完全算法模型時間復(fù)雜度不高，但取得的值確實最優(yōu)的，具有較好的推廣價值。模型拓展特別注意到原文體中描述出車費用的計量方式是每輛車100元出車費，若深究此話含義，所得結(jié)果應(yīng)該是255+100=355為最優(yōu)解。因為空車返回不計價格，一輛車反復(fù)跑節(jié)省了出車費用，固使之最小。小結(jié)模型的分析已在各個部分作了說明，這里不再重述，由于比賽時間短暫，做了的很多工作未能詳述，再次簡要概括，相關(guān)數(shù)據(jù)附在附錄中。針對遺傳算法當(dāng)中的插入算法模型，為了校驗他的可靠性，專門編寫了全排列進(jìn)入黑箱，對黑箱的數(shù)據(jù)進(jìn)行SPSS的統(tǒng)計分析，得到最優(yōu)解的概率，從而確定了遺傳算法索要比對的次數(shù)級別。針對各個算法都有一些小的優(yōu)化和剪枝，比較瑣碎再此也不再詳述，詳細(xì)請參考附錄中的程序原文。

參考文獻(xiàn)[1]徐玖平等，運籌學(xué)，科學(xué)出版社，2006[2]網(wǎng)友資源，百度百科，/view/298415.htm[3]黃良文主編，統(tǒng)計學(xué)原理，北京：中國統(tǒng)計出版社，2000.6[4]楊位欽顧嵐著，時間序列分析與動態(tài)數(shù)據(jù)建模（修訂本），北京：北京理工大學(xué)出版社，1988[5]范金城，梅長林著，數(shù)據(jù)分析，科學(xué)出版社，2002[6]曹利國，吳耀斌，向期中等，信息學(xué)奧林匹克奧賽經(jīng)，2002[7]姜啟源謝金星葉俊等編，數(shù)學(xué)建模，北京：高等教育出版社，2003[8]孫祥等編，MATLAB7.0基礎(chǔ)教程，北京：清華大學(xué)出版社2005.5[9]劉汝佳等，算法藝術(shù)與信息學(xué)競賽，清華大學(xué)出版社，2004.1

附錄附錄一路徑的鄰接矩陣附錄二各客戶所需要的貨物量8，13，6，9，7，15，10，5，12，9附錄三題目的Floyd任意兩點之間的矩陣d（i，j）0405540255530555070500304535504555658555300155530502535554045150453050203050251545450351030405555503030350255035553025505010250304060304525203025300103020403040351525450203520102520403035300附錄四兩點i，j之間最短距離所經(jīng)過的路徑path（i，j）其中path（i，j）=j，表示i，j是直接到達(dá)。1544577599123356538942348678891334568889122457788107234767499153856788109534597899410104767891012335353910附錄五（i，j）表示從i出發(fā)到j(luò)停止一共要走幾個點1332232323212322334532123222342321223234223213223232223123232323221232332223212323323222122223233321附錄六相關(guān)程序問題1用Floyd算法的matlab實現(xiàn)程序clear;clc;M=10000;%不能直接到達(dá)是將距離賦值給Ma(1,:)=[0,50,M,40,25,M,30,M,50,M];a(2,:)=[50,0,30,M,35,50,M,60,M,M];a(3,:)=[M,30,0,15,M,30,50,25,M,60];a(4,:)=[40,M,15,0,45,30,55,20,40,65];a(5,:)=[25,15,M,45,0,60,10,30,M,55];a(6,:)=[M,50,30,30,60,0,25,55,35,M];a(7,:)=[30,M,50,M,10,25,0,30,45,60];a(8,:)=[M,60,25,20,30,55,30,0,10,M];a(9,:)=[20,M,M,40,M,15,25,45,0,20];a(10,:)=[35,20,10,45,20,M,60,M,30,0];%建立a矩陣path=zeros(length(a));%建立一個與矩陣a同大小的全零矩陣fori=1:10forj=1:10path(i,j)=j;%用path矩陣記錄走過的點endendfork=1:10fori=1:10forj=1:10ifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=path(i,k);%floyd算法endendendenda,pathi1=input('請輸入起點');i2=input('請輸入終點');disp(i1);whilei1~=i2i1=path(i1,i2);disp(i1);end;問題1的pascal程序（模型2）programfloyd;constmaxn=15;vari1,i2,i3,ss,i,j,k,l,s,m,n,ci:integer;a,b:array[1..maxn,1..maxn]ofinteger;path:array[1..maxn,1..maxn,0..maxn]ofinteger;plan,zl,c:array[1..maxn]ofinteger;f:text;r,total:integer;beginassign(f,'in.txt');reset(f);//assign(output,'out.txt');rewrite(output);readln(f,n,i1,k);fori:=1tondoread(f,zl[i]);readln(f);fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);fillchar(path,sizeof(path),0);//read//ifi1=1thenbeginfori:=1tondobeginforj:=1tondobeginread(f,a[i,j]);ifa[i,j]=0thenbeginpath[i,j,0]:=1;path[i,j,1]:=i;end;ifa[i,j]<>0thenbeginpath[i,j,0]:=2;path[i,j,1]:=i;path[i,j,2]:=j;end;end;readln(f);end;//end;b:=a;//runfork:=1tondofori:=1tondoforj:=1tondoif(b[i,k]<>-1)and(b[k,j]<>-1)and((b[i,k]+b[k,j]<b[i,j])or(b[i,j]=-1))thenbeginb[i,j]:=b[i,k]+b[k,j];path[i,j,0]:=path[i,k,0]+path[k,j,0]-1;form:=1topath[i,k,0]dopath[i,j,m]:=path[i,k,m];form:=1topath[k,j,0]dopath[i,j,m+path[i,k,0]-1]:=path[k,j,m];end;//printwriteln;writeln('---YuanShi---');fori:=1tondobeginforj:=1tondowrite(a[i,j]:5);writeln;end;writeln;writeln('----SSSP----');fori:=1tondobeginforj:=1tondowrite(b[i,j]:5);writeln;end;writeln;writeln('----PathN----');fori:=1tondobeginforj:=1tondowrite(path[i,j,0]:5);writeln;end;close(f);reset(input);//displaypathwhile(i1<>-1)dobeginreadln(i1,i2);fori:=1topath[i1,i2,0]-1dowrite(path[i1,i2,i],'-->');writeln(path[i1,i2,path[i1,i2,0]]);writeln(b[i1,i2]);end;end.問題二的pascal程序（模型3、4、5）programforyd;constmaxn=15;vari1,i2,i3,ss,i,j,k,l,s,m,n,ci:integer;a,b:array[1..maxn,1..maxn]ofinteger;zl,c,d,e,f,g,plan:array[1..maxn]ofinteger;ff:text;total:integer;over,show,stop:boolean;c1,c2:array[1..maxn]ofbyte;xl:array[0..2*maxn]ofbyte;procedurefindi;begini:=n;while(i>1)and(plan[i]<plan[i-1])dodec(i)end;procedurefindj;beginj:=n;while(plan[j]<=plan[i-1])dodec(j)end;procedurechange;vark,h:integer;begink:=plan[i-1];plan[i-1]:=plan[j];plan[j]:=k;fork:=ito(n+i)div2dobeginh:=plan[k];plan[k]:=plan[n+i-k];plan[n+i-k]:=h;end;end;proceduresol;vari,j,k:integer;begink:=0;fori:=1ton-1dok:=k+b[plan[i],plan[i+1]];k:=k+b[plan[n],1];ifk<sthenbegins:=k;c:=plan;end;{ifk=sthenbeginwriteln;writeln('---QiongJu---');writeln;write('1');fori:=2tondowrite('-->',plan[i]);writeln('-->1');writeln('Total:',k);end;}end;beginassign(input,'in.txt');reset(input);assign(output,'out.txt');rewrite(output);readln(n,i1,k);fori:=1tondoread(zl[i]);readln;fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);fillchar(c,sizeof(c),0);//readifi1=1thenbeginfori:=1tondobeginforj:=1tondoread(a[i,j]);readln;end;end;ifi1=2thenbeginfori:=1tondoforj:=1tondoifi<>jthena[i,j]:=-1elsea[i,j]:=0;i1:=0;whilei1<>-1dobeginreadln(i1,i2,i3);ifi1<>-1thenbegina[i1,i2]:=i3;ifk=1thena[i2,i1]:=i3;end;end;end;b:=a;//runfork:=1tondofori:=1tondoforj:=1tondoif(b[i,k]<>-1)and(b[k,j]<>-1)and((b[i,k]+b[k,j]<b[i,j])or(b[i,j]=-1))thenb[i,j]:=b[i,k]+b[k,j];//printwriteln;writeln('---YuanShi---');fori:=1tondobeginforj:=1tondowrite(a[i,j]:5);writeln;end;writeln;writeln('----SSSP----');fori:=1tondobeginforj:=1tondowrite(b[i,j]:5);writeln;end;//SSSP+Searchc[1]:=1;ci:=1;s:=0;whileci<ndobegink:=32760;fori:=1tondobeginm:=1;forj:=1tocidoifc[j]=ithenm:=0;if(b[c[ci],i]<>0)and(m=1)and(b[c[ci],i]<k)thenbegink:=b[c[ci],i];c[ci+1]:=i;end;end;inc(ci);s:=s+kend;s:=s+b[c[ci],1];writeln;writeln('---JinSiSuanFa---');writeln;write('1');fori:=2tondowrite('-->',c[i]);writeln('-->1');writeln('Total:',s);//xiuzhengYICHuanss:=32760;forl:=1to2000dobegins:=32760;randomize;fori:=1to100dobeginj:=round(random*(n-2))+2;k:=round(random*(n-2))+2;if(j>n)or(j<1)thenj:=n;if(k>n)or(k<1)thenk:=1;i1:=c[k];c[k]:=c[j];c[j]:=i1;end;d[1]:=1;f[1]:=1;f[2]:=1;fori:=ndownto2dobegins:=32760;forj:=2ton-i+2dobegind:=f;m:=0;fork:=n-i+2downtojdobegind[k+1]:=d[k];end;d[j]:=c[i];fork:=1ton-i+2dobeginm:=m+b[d[k],d[k+1]];end;ifm<sthenbegins:=m;e:=d;end;end;f:=e;end;ifs<ssthenbeginss:=s;g:=f;end;end;//s:=s+b[f[n],1];writeln;writeln('---YiChuanJinSiSuanFa---');writeln;write('1');fori:=2tondowrite('-->',g[i]);writeln('-->1');writeln('Total:',ss);//QiongJus:=32760;fori:=1tondoplan[i]:=i;sol;repeatfindi;ifi>1thenbeginfindj;change;ifplan[1]<>1thenbreak;sol;end;untili<=1;writeln;writeln('---QiongJu---');writeln;write('1');fori:=2tondowrite('-->',c[i]);writeln('-->1');writeln('Total:',s);close(input);close(output);end.問題三的pascal程序（模型6）programforyd;constmaxn=15;varcari1,cari2,i1,i2,i3,ss,i,j,k,l,s,m,n,ci:integer;a,b:array[1..maxn,1..maxn]ofinteger;dot,zl,c,d,e,f,g,plan:array[1..maxn]ofinteger;ff:text;total:integer;over,show,stop:boolean;c1,c2,car1,car2:array[1..maxn]ofinteger;xl:array[0..2*maxn]ofbyte;procedurefindi(n:integer);begini:=n;while(i>1)and(plan[i]<plan[i-1])dodec(i)end;procedurefindj(n:integer);beginj:=n;while(plan[j]<=plan[i-1])dodec(j)end;procedurechange(n:integer);vark,h:integer;begink:=plan[i-1];plan[i-1]:=plan[j];plan[j]:=k;fork:=ito(n+i)div2dobeginh:=plan[k];plan[k]:=plan[n+i-k];plan[n+i-k]:=h;end;end;proceduresol(n:integer);vari,j,k:integer;begink:=0;fori:=1ton-1dok:=k+b[dot[plan[i]],dot[plan[i+1]]];k:=k+b[dot[plan[n]],1];ifk<sthenbegins:=k;c:=plan;end;end;procedureqiongju(n:integer);begin//QiongJus:=32760;fori:=1tondoplan[i]:=i;sol(n);repeatfindi(n);ifi>1thenbeginfindj(n);change(n);ifplan[1]<>1thenbreak;sol(n);end;untili<=1;writeln;writeln('---QiongJu---');writeln;write('1');fori:=2tondowrite('-->',dot[c[i]]);writeln('-->1');writeln('Total:',s);end;proceduresolbuhui(n:integer);vari,j,k:integer;begink:=0;fori:=1ton-1dok:=k+b[dot[plan[i]],dot[plan[i+1]]];//k:=k+b[dot[plan[n]],1];ifk<sthenbegins:=k;c:=plan;end;end;procedureqiongjubuhui(n:integer);begin//QiongJus:=32760;fori:=1tondoplan[i]:=i;solbuhui(n);repeatfindi(n);ifi>1thenbeginfindj(n);change(n);ifplan[1]<>1thenbreak;solbuhui(n);end;untili<=1;ss:=s;//writeln;//writeln('---QiongJu---');//writeln;//write('1');//fori:=2tondowrite('-->',dot[c[i]]);//writeln('-->1');//writeln('Total:',s);end;procedureSSSPSearch(n:integer);begin//SSSP+Searchc[1]:=1;ci:=1;s:=0;whileci<ndobegink:=32760;fori:=1tondobeginm:=1;forj:=1tocidoifc[j]=ithenm:=0;if(b[c[ci],i]<>0)and(m=1)and(b[c[ci],i]<k)thenbegink:=b[c[ci],i];c[ci+1]:=i;end;end;inc(ci);s:=s+kend;s:=s+b[c[ci],1];writeln;writeln('---JinSiSuanFa---');writeln;write('1');fori:=2tondowrite('-->',c[i]);writeln('-->1');writeln('Total:',s);end;procedureyichuan(n:integer);//xiuzhengYICHuanbeginss:=32760;fori:=1tondoc[i]:=i;forl:=1to2000dobegins:=32760;randomize;fori:=1to100dobeginj:=round(random*(n-2))+2;k:=round(random*(n-2))+2;if(j>n)or(j<1)thenj:=n;if(k>n)or(k<1)thenk:=1;i1:=c[k];c[k]:=c[j];c[j]:=i1;end;d[1]:=1;f[1]:=1;f[2]:=1;fori:=ndownto2dobegins:=32760;forj:=2ton-i+2dobegind:=f;m:=0;fork:=n-i+2downtojdobegind[k+1]:=d[k];end;d[j]:=c[i];fork:=1ton-i+2dobeginm:=m+b[dot[d[k]],dot[d[k+1]]];end;ifm<sthenbegins:=m;e:=d;end;end;f:=e;end;ifs<ssthenbeginss:=s;g:=f;end;end;//s:=s+b[f[n],1];writeln;writeln('---YiChuanJinSiSuanFa---');writeln;write('1');fori:=2tondowrite('-->',dot[g[i]]);writeln('-->1');writeln('Total:',ss);end;procedureyichuanbuhui(n:integer);//xiuzhengYICHuanbeginss:=32760;fori:=1tondoc[i]:=i;forl:=1to1000dobegins:=32760;randomize;fori:=1to100dobeginj:=round(random*(n-2))+2;k:=round(random*(n-2))+2;if(j>n)or(j<1)thenj:=n;if(k>n)or(k<1)thenk:=1;i1:=c[k];c[k]:=c[j];c[j]:=i1;end;d[1]:=1;f[1]:=1;f[2]:=1;fori:=ndownto2dobegins:=32760;forj:=2ton-i+2dobegind:=f;m:=0;fork:=n-i+2downtojdobegind[k+1]:=d[k];end;d[j]:=c[i];fork:=1ton-i+1dobeginm:=m+b[dot[d[k]],dot[d[k+1]]];end;ifm<sthenbegins:=m;e:=d;end;end;f:=e;end;ifs<ssthenbeginss:=s;g:=f;end;end;//s:=s+b[f[n],1];//writeln;//writeln('---YiChuanBuHuiSuanFa---');//writeln;{write('1');fori:=2tondowrite('-->',dot[g[i]]);//writeln('-->1');writeln;writeln('Total:',ss);}end;functionkeyun:boolean;vari,j,k,w1,w2:integer;beginw1:=0;w2:=0;fori:=1tondobeginif(c1[i]=1)and(c2[i]=0)thenw1:=w1+zl[i];if(c1[i]=0)and(c2[i]=1)thenw2:=w2+zl[i];end;if(w1<=50)and(w2<=50)thenkeyun:=trueelsekeyun:=false;end;proceduremake_xl;vari,j,k:integer;begin//repeati:=n*2;whilexl[i]<>0dodec(i);ifi<1thenover:=true;xl[i]:=1;forj:=i+1ton*2doxl[j]:=0;forj:=1tondoifxl[j]=0thenxl[j+n]:=1;xl[1]:=1;xl[1+n]:=1;{k:=1;forj:=1tondoifxl[j]+xl[n+j]=0thenbegink:=0;break;end;}//if(xl[1]<>1)or(xl[1+n]<>1)thenk:=0;//until{(k=1)or}(over);end;proceduresol3;vari,j,k:integer;min,tmpmin:longint;beginfori:=1to2*ndoxl[ci]:=0;over:=false;xl[1]:=1;xl[1+n]:=1;min:=32760;whilenot(over)dobeginmake_xl;fori:=1tondobeginc1[i]:=xl[i];c2[i]:=xl[i+n];end;ifk