離散最優(yōu)化模型課件

離散問題是整數(shù)規(guī)劃、組合數(shù)學(xué)圖論、網(wǎng)絡(luò)流等許多學(xué)科討論和研究的對(duì)象，這類問題在生產(chǎn)調(diào)度、交通控制、物流、管理科學(xué)和社會(huì)科學(xué)等有著廣泛的用途。在我們歷年的數(shù)模的競賽中，離散問題是很重要的一個(gè)方面。如“鎖具裝箱”，“災(zāi)情巡視路線”等等，本身就是個(gè)典型的離散問題；也有的問題里包含著離散的子問題，如“車輛安排問題”，是個(gè)受到整數(shù)的約束的優(yōu)化問題。近幾年的“乘公交，看奧運(yùn)”，“體能測試時(shí)間安排”，“地面搜索”,“NBA賽程的分析與評(píng)價(jià)”,“眼科病床的合理安排”,“會(huì)議籌備”等等都屬于離散型問題。shumo華中農(nóng)業(yè)大學(xué)李治因此，在準(zhǔn)備數(shù)模競賽的過程中，有必要認(rèn)真的研究如何提高建立離散模型的質(zhì)量。下面就離散優(yōu)化問題，介紹一下常見模型、算法及如何進(jìn)行算法分析等。shumo華中農(nóng)業(yè)大學(xué)李治建立規(guī)劃模型的要點(diǎn)與技巧一、準(zhǔn)確理解題意二、選擇適當(dāng)?shù)臎Q策變量要點(diǎn)：

通過仔細(xì)讀題，弄清楚我們最終要解決的問題是什么?是單目標(biāo)問題還是多目標(biāo)問題？已知條件有哪些？為了簡化與解決問題，需要做哪些必要的基本假設(shè)？

需要優(yōu)化的目標(biāo)是由哪些因素決定的？適當(dāng)引入決策變量來表示這些因素。shumo華中農(nóng)業(yè)大學(xué)李治三、設(shè)法用決策變量表示目標(biāo)函數(shù)四、仔細(xì)分析約束條件通常引入的決策變量有0-1變量，整數(shù)變量等。

在用決策變量表示目標(biāo)函數(shù)時(shí)，有時(shí)需要引入中間變量，有時(shí)要利用取整函數(shù)、符號(hào)函數(shù)、絕對(duì)值函數(shù)等等。

決策變量滿足的約束主要有兩方面：一是自身應(yīng)有的約束，如非負(fù)約束、取整約束等等；二是題目要求及客觀實(shí)際的約束，這種約束又可分為“硬約束”與“軟約束”。shumo華中農(nóng)業(yè)大學(xué)李治一、多目標(biāo)問題的妥協(xié)二、非線性規(guī)劃的線性化三、復(fù)雜規(guī)劃問題的拆分值得注意的技巧：有時(shí)可將復(fù)雜的問題分成一系列較為簡單的子問題求解線性加權(quán)法；理想點(diǎn)法，極大極小法等有時(shí)通過引入人工變量可將非線性規(guī)劃問題線性化shumo華中農(nóng)業(yè)大學(xué)李治一常見離散優(yōu)化模型涉及整數(shù)規(guī)劃、0-1規(guī)劃、組合優(yōu)化和圖論等：如競賽中常涉及的有下料問題；指派問題、選址問題、裝箱問題、背包問題、最短路問題、TSP（旅行商）問題等。離散優(yōu)化研究那些含有有限個(gè)可行解的、日常生活中大量存在的問題，一個(gè)重要而普遍的應(yīng)用領(lǐng)域就是考慮如何有效利用稀缺資源來提高生產(chǎn)力等。shumo華中農(nóng)業(yè)大學(xué)李治例1現(xiàn)要做100套鋼架,用長為2.9m、2.1m和1.5m的元鋼各一根,已知原料長7.4m,問如何下料,使用的原材料最省?分析:下料方式：最?。?.所用剛架根數(shù)最少；2.余料最少下料問題離散優(yōu)化模型shumo華中農(nóng)業(yè)大學(xué)李治原料截成所需長度的根數(shù)下料方法ⅠⅡⅢⅣⅤⅥⅦⅧ所需根長2.9m211100002.1m021032101.5m10130234剩余料頭0.10.30.901.10.20.81.4離散優(yōu)化模型shumo華中農(nóng)業(yè)大學(xué)李治離散優(yōu)化模型寫出模型后可以直接用LINGO求解shumo華中農(nóng)業(yè)大學(xué)李治model:Title

鋼管下料;

Min=0.1*x1+0.3*x2+0.9*x3+0*x4+1.1*x5+0.2*x6+0.8*x7+1.4*x8;2*x1+x2+x3+x4>100;2*x2+3*x3+3*x5+2*x6+x7>100;x1+x3+3*x4+

2*x6+3*x7+

4*x8>100;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);endshumo華中農(nóng)業(yè)大學(xué)李治

例2

設(shè)有n件工作B1,B2,…Bn,分派給n人A1,A2,…An去做,每人只做一件工作且每件工作只派一個(gè)人去做,設(shè)Ai完成Bj的工時(shí)為cij,問應(yīng)如何分派才能完成全部工作的總工時(shí)最少.每件工作只派1人每個(gè)人只做1件工作指派問題離散優(yōu)化模型shumo華中農(nóng)業(yè)大學(xué)李治如求6個(gè)人做6項(xiàng)工作的最優(yōu)指派，收益情況如下表。指派問題人工作1工作2工作3工作4工作5工作61201516547217153312863912181630134128112719145—7102110326———61113shumo華中農(nóng)業(yè)大學(xué)李治指派問題model:title指派問題;sets:flight/1..6/;assign(flight,flight):c,x;endsetsdata:c=20151654717153312869121816301312811271914-99710211032-99-99-9961113;enddata人工作1工作2工作3工作4工作5工作61201516547217153312863912181630134128112719145—7102110326———61113max=sum(assign:c*x);for(flight(i):sum(flight(j):x(i,j))=1;sum(flight(j):x(j,i))=1);for(assign:bin(x));endshumo華中農(nóng)業(yè)大學(xué)李治選址問題離散優(yōu)化模型shumo華中農(nóng)業(yè)大學(xué)李治裝箱問題(binpacking

problem)裝箱問題在工業(yè)生產(chǎn)及日常生活中有廣泛的用途，其應(yīng)用在實(shí)際生活中無處不在，貨物裝運(yùn)，服裝裁剪，以及我們計(jì)算機(jī)科學(xué)中的存儲(chǔ)分配、共享資源調(diào)度、文件存儲(chǔ)都是裝箱問題在實(shí)際應(yīng)用中的體現(xiàn)。所以具有重要的研究價(jià)值。當(dāng)你裝一個(gè)箱子時(shí)，你會(huì)發(fā)現(xiàn)要使箱子盡可能裝滿不是一件很容易的事，你往往需要做些調(diào)整。從理論上講，裝箱問題是一個(gè)很難的組合優(yōu)化問題，即使用計(jì)算機(jī)也是不容易解決的。離散優(yōu)化模型shumo華中農(nóng)業(yè)大學(xué)李治設(shè)有編號(hào)為1、…、n的n種物品，體積分別為v1、v2、…、vn。將這n種物品裝到容量都為V的若干箱子里(更一般的裝箱問題還可以要求容量不是相同的)。約定這n種物品的體積均不超過V，即對(duì)于1≤i≤n，有0＜vi≤V。不同的裝箱方案所需要的箱子數(shù)目可能不同。成功裝載是指能把所有物品都裝入箱子。最優(yōu)裝載是指使用最少箱子的成功裝載。

裝箱問題的描述shumo華中農(nóng)業(yè)大學(xué)李治裝箱問題的數(shù)學(xué)表示如下(0-1規(guī)劃模型)：s.t.yi=1表示箱子i裝入物品，反之表示箱子i空著xij=1表示物品j裝入箱子i

，反之表示物品j未放入箱子ishumo華中農(nóng)業(yè)大學(xué)李治例4已知30個(gè)物品,其中6個(gè)長0.51m，6個(gè)長0.27m，6個(gè)長0.26m，余下12個(gè)長0.23m，箱子長為1m，問最少需多少個(gè)箱子才能把30個(gè)物品全部裝進(jìn)箱子。裝箱問題的LINGO軟件求解離散優(yōu)化模型shumo華中農(nóng)業(yè)大學(xué)李治model:sets:WP/w1..w30/:W;XZ/v1..v30/:Y;LINKS(WP,XZ):X;ENDSETSDATA:W=0.51,0.51,0.51,0.51,0.51,0.51,0.27,0.27,0.27,0.27,0.27,0.27,0.26,0.26,0.26,0.26,0.26,0.26,0.23,0.23,0.23,0.23,0.23,0.23,0.23,0.23,0.23,0.23,0.23,0.23;ENDDATAMIN=SUM(XZ(I):Y(I));C=1;!C是箱子長度;for(XZ:bin(y));!限制Y是0-1變量;for(LINKS:bin(X));!限制X是0-1變量;for(WP(I):sum(XZ(J):X(I,J))=1);!每個(gè)物品只能放入一個(gè)箱子;for(XZ(J):SUM(WP(I):W(I)*X(I,J))<=C*Y(J));!每個(gè)箱子內(nèi)物品的總長度不超過箱子;end離散優(yōu)化模型shumo華中農(nóng)業(yè)大學(xué)李治裝箱問題的分類 一維裝箱問題更多的是帶約束的裝箱問題， 如二維裝箱問題（條形裝箱問題、剪裁 問題）、三維裝箱問題、變?nèi)菅b箱問題、 有色裝箱問題、對(duì)偶裝箱問題等。 在競賽中應(yīng)注意區(qū)分和鑒別離散優(yōu)化模型shumo華中農(nóng)業(yè)大學(xué)李治有N件物品和一個(gè)容量為W的背包。第j件物品的價(jià)值是，體積是。求將哪些物品裝入背包可在滿足背包容量允許的前提下使價(jià)值總和最大。背包問題在經(jīng)濟(jì)管理、資源分配、投資決策、裝載設(shè)計(jì)等領(lǐng)域有著重要的應(yīng)用價(jià)值。一維0/1背包問題shumo華中農(nóng)業(yè)大學(xué)李治設(shè)為二進(jìn)制變量，如果物品j被放入背包，則，否則。背包問題的數(shù)學(xué)模型描述如下：

離散優(yōu)化模型shumo華中農(nóng)業(yè)大學(xué)李治例5：“超市大贏家”提供了50種商品作為獎(jiǎng)品供中獎(jiǎng)?lì)櫩瓦x擇,車的容量為1000dm3,獎(jiǎng)品i占用的空間為widm3,價(jià)值為vi

元,具體的數(shù)據(jù)如下:vi={220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1}wi={80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1}。離散優(yōu)化模型shumo華中農(nóng)業(yè)大學(xué)李治model:sets:goods/w1..w50/:w,c,x;

endsetsdata:c=220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1;w=80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1;capacity=1000;!容量;enddatamax=sum(goods(j):c(j)*x(j));for(goods:bin(x));!限制x是0-1變量;sum(goods(J):w(j)*x(j))<capacity;p=sum(goods(J):x(j));!所裝物品總件數(shù);z=sum(goods(J):w(j)*x(j));!所裝物品總體積;endshumo華中農(nóng)業(yè)大學(xué)李治最短路問題與TSP問題這兩個(gè)問題是圖論中與優(yōu)化有關(guān)的常見問題，即使不專門考察，在競賽中經(jīng)常也會(huì)以不同形式涉及。如00年鋼管運(yùn)輸與98年災(zāi)情巡視07年“乘公交、看奧運(yùn)”shumo華中農(nóng)業(yè)大學(xué)李治

設(shè)一個(gè)帶權(quán)的圖G=(V,E)表示一交通運(yùn)輸網(wǎng)絡(luò)，以圖的各個(gè)頂點(diǎn)V代表一些城市，圖的各條邊E表示城市之間的交通運(yùn)輸路線，每條邊的權(quán)值則表示此路線的長度或表示沿此路線運(yùn)輸所需花費(fèi)的時(shí)間或運(yùn)費(fèi)等。運(yùn)輸路線往往是有方向性的，例如汽車運(yùn)輸有時(shí)會(huì)遇到單行路,而且不同的方向所花費(fèi)的時(shí)間或尺價(jià)可能不同，例如汽車的上山和下山、水路的順?biāo)湍嫠ㄙM(fèi)的時(shí)間或代價(jià)就不相同，所以交通運(yùn)輸網(wǎng)絡(luò)一般是有向圖，所謂最短路徑問題指的是：如果從圖中某頂點(diǎn)出發(fā)(此點(diǎn)稱為源點(diǎn)),經(jīng)圖的邊到達(dá)另一頂點(diǎn)（稱之為目的點(diǎn)）的路徑不止一條，如何找到一條路徑使沿此路徑上各邊的權(quán)值之和為最小。最短路問題(Shortestpath)shumo華中農(nóng)業(yè)大學(xué)李治例6在公路網(wǎng)中，司機(jī)希望找到一條從城市S到T的最短路，如何選擇行使路線，使所經(jīng)過的路程最短。單源最短路問題

shumo華中農(nóng)業(yè)大學(xué)李治model:SETS:CITIES/S,A1,A2,A3,B1,B2,C1,C2,T/:L;!屬性L(i)表示城市S到城市i的最優(yōu)行駛路線的路長;ROADS(CITIES,CITIES)/

!派生集合ROADS表示的是網(wǎng)絡(luò)中的道路（?。?S,A1S,A2S,A3 !由于并非所有城市間都有道路直接連接，所以將弧具體列出;A1,B1A1,B2A2,B1A2,B2A3,B1A3,B2B1,C1B1,C2B2,C1B2,C2C1,TC2,T/:D; !屬性D(i,j)是城市i到j(luò)的直接距離（已知）;ENDSETSDATA:D=633658674678956;L=0,,,,,,,,;

!因?yàn)長(S)=0;ENDDATA

FOR(CITIES(i)|i#GT#index(S):

!這行中"index(S)"可以直接寫成"1";L(i)=MIN(ROADS(j,i):L(j)+D(j,i)););!這就是前面寫出的最短路關(guān)系式;end定義稀疏集合方法：枚舉法CITIES（i）中的i指元素在集合中的位置順序，index(S)即:index(CITIES，S),S在CITIES中的索引值。沒有目標(biāo)函數(shù)是允許的shumo華中農(nóng)業(yè)大學(xué)李治旅行推銷員問題（TravelSalesmanProblemorTSP問題）

設(shè)有A、B、C、D、E五個(gè)城市(n=5)之間路程如下距離矩陣W給出。假設(shè)一個(gè)推銷員想從城市A出發(fā)，問是否存在一個(gè)行程安排，使得他能不重復(fù)地遍歷所有城市后回到這個(gè)城市，而且所走路程最少。shumo華中農(nóng)業(yè)大學(xué)李治哈密爾頓回路問題這樣找從一點(diǎn)出發(fā)不重復(fù)地走過所有的結(jié)點(diǎn)，最后又回到原出發(fā)點(diǎn)的路徑的問題，在圖論中稱為“哈密爾頓回路問題”“哈密爾頓回路問題”與“歐拉回路問題”的不同點(diǎn)“哈密爾頓回路問題”是訪問每個(gè)結(jié)點(diǎn)一次，而“歐拉回路問題”是訪問每條邊一次。對(duì)圖G是否存在“歐拉回路”，歐拉已給出充分必要條件，而對(duì)圖G是否存在“哈密爾頓回路”至今仍未找到滿足該問題的充分必要條件。歐拉回路問題也稱為“中國郵遞員問題”。中國數(shù)學(xué)家管梅谷于1960年首先研究并給出算法。shumo華中農(nóng)業(yè)大學(xué)李治TSP問題的數(shù)學(xué)表示如下（0-1規(guī)劃模型）：s.t.源至少有一條邊連接到其它點(diǎn)xij決策變量，xij=1表示連接除源以外，每個(gè)點(diǎn)只有一條邊進(jìn)入shumo華中農(nóng)業(yè)大學(xué)李治增加一個(gè)標(biāo)號(hào)的水平變量（level）來構(gòu)造所選的邊不構(gòu)成子回路的約束條件（即只能有整體回路），這是TSP問題的一個(gè)充分條件。任何含有子回路的路線都必不滿足該約束條件（不管ui）如何取值；全體不含子回路的整體回路都可以滿足該約束條件（只要ui取適當(dāng)值）shumo華中農(nóng)業(yè)大學(xué)李治證明：任何含有子回路的路線都必不滿足該約束條件（不管ui）如何取值；全體不含子回路的整體回路都可以滿足該約束條件（只要ui取適當(dāng)值）反證：假設(shè)存在子回路，則至少有兩個(gè)子回路，必然至少有一個(gè)子回路不含源點(diǎn)1，例如子回路4-5-6-4，把下標(biāo)代入，有把這三個(gè)不等式加起來得到這是矛盾的，故假設(shè)不成立，而對(duì)整體回路，而附加約束中j≥2,不包含起點(diǎn)1，故不會(huì)發(fā)生矛盾。對(duì)整體回路，只要level(i)取適當(dāng)值，都可以滿足該約束。shumo華中農(nóng)業(yè)大學(xué)李治例7已知六個(gè)城市之間的距離矩陣，求從1出發(fā)回到1的TSP路線。D=070245484223961196

702032410932136764

454324011372180798

84210931137016161857

239621362180161602900

1196764798185729000;shumo華中農(nóng)業(yè)大學(xué)李治model:sets:city/1..6/:u;link(city,city):dist,x;endsetsdata:dist=070245484223961196702032410932136764454324011372180798842109311370161618572396213621801616029001196764798185729000;enddatan=size(city);min=sum(link:dist*x);for(city(k):sum(city(i)|i#ne#k:x(i,k))=1;sum(city(j)|j#ne#k:x(k,j))=1);for(city(i):for(city(j)|j#gt#1#and#i#ne#j:u(i)-u(j)+n*x(i,j)<=n-1));for(link:bin(x));endshumo華中農(nóng)業(yè)大學(xué)李治問題的分析藍(lán)色代表預(yù)計(jì)選Mevo的人數(shù)，紅色代表各街區(qū)總?cè)藬?shù)例8：（08年華中聯(lián)賽）選區(qū)方案shumo華中農(nóng)業(yè)大學(xué)李治shumo華中農(nóng)業(yè)大學(xué)李治shumo華中農(nóng)業(yè)大學(xué)李治將首都的地圖看作一張無向圖，若街區(qū)是相鄰街區(qū)，該街區(qū)間有邊相連。得到其鄰接矩陣W：11111111111111111111111111111111111111111111111111shumo華中農(nóng)業(yè)大學(xué)李治見程序shumo華中農(nóng)業(yè)大學(xué)李治二離散最優(yōu)化問題的求解雖然理論上講這些離散優(yōu)化問題最優(yōu)解可以通過枚舉得到，但事實(shí)是不可能的，因?yàn)閷?duì)于實(shí)際問題，可行解數(shù)量可能特別巨大。許多離散優(yōu)化問題是經(jīng)典的NP難解問題，這意味著該類問題往往不存在在多項(xiàng)式時(shí)間內(nèi)求得精確解的算法（如果P≠NP）,因此對(duì)離散優(yōu)化問題的算法的研究指的往往是對(duì)其近似算法的研究，所謂近似算法即該算法可以求得與精確解接近的結(jié)果,但不一定得到精確解。shumo華中農(nóng)業(yè)大學(xué)李治離散最優(yōu)化問題的求解1、回溯法2、貪婪算法3、分支定界4、動(dòng)態(tài)規(guī)劃回溯法：一般當(dāng)問題規(guī)模較小時(shí)用回溯法能有效求解,但當(dāng)問題規(guī)模較大時(shí)其求解時(shí)間耗費(fèi)非常巨大。離散最優(yōu)化問題的求解shumo華中農(nóng)業(yè)大學(xué)李治以裝箱問題為例，若將n種物品的集合分劃成n個(gè)或小于n個(gè)物品的所有子集全部窮舉出來，最優(yōu)解當(dāng)然可以找到。但所有可能劃分的總數(shù)太大。對(duì)適當(dāng)大的n，找出所有可能的劃分要花費(fèi)的時(shí)間是無法承受的。為此，可以采用非常簡單的近似算法，即貪婪法。該算法依次將物品放到它第一個(gè)能放進(jìn)去的箱子中，該算法雖不能保證找到最優(yōu)解，但還是能找到非常好的解。2、貪婪算法（貪心法）shumo華中農(nóng)業(yè)大學(xué)李治貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況。貪婪算法并不能保證最優(yōu)，然而，卻是一種具有直覺的傾向且一般情況下結(jié)果總是非常接近最優(yōu)值。它利用的規(guī)則就是在實(shí)際環(huán)境中人工所采用的規(guī)則。算法并不保證得到最優(yōu)結(jié)果，但通常所得結(jié)果與最優(yōu)解相差無幾，這種算法也稱為啟發(fā)式方法（heuristics)。貪婪算法shumo華中農(nóng)業(yè)大學(xué)李治例如平時(shí)購物找錢時(shí)，為使找回的零錢的硬幣數(shù)最少，不考慮找零錢的所有各種發(fā)表方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當(dāng)不足大面值幣種的金額時(shí)才去考慮下一種較小面值的幣種。這就是在使用貪婪法。這種方法在這里總是最優(yōu)，是因?yàn)殂y行對(duì)其發(fā)行的硬幣種類和硬幣面值的巧妙安排。如只有面值分別為1、5和11單位的硬幣，而希望找回總額為15單位的硬幣。按貪婪算法，應(yīng)找1個(gè)11單位面值的硬幣和4個(gè)1單位面值的硬幣，共找回5個(gè)硬幣。但最優(yōu)的解應(yīng)是3個(gè)5單位面值的硬幣。

貪婪算法shumo華中農(nóng)業(yè)大學(xué)李治在貪婪算法（greedymethod）中采用逐步構(gòu)造最優(yōu)解的方法。在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。決策一旦作出，就不可再更改。作出貪婪決策的依據(jù)稱為貪婪準(zhǔn)則（greedycriterion）。

貪婪算法shumo華中農(nóng)業(yè)大學(xué)李治裝箱問題的求解——貪婪算法

NF(NextFit－下次適應(yīng))算法：按照物體給定的順序裝箱：把物品wi放到它第一個(gè)能放進(jìn)去的箱子中。Bj是具有最大下標(biāo)的使用過的箱子，若wi的長度不大于Bj的剩余長度，則把wi放入Bj，否則把wi放入一個(gè)新的箱子Bj+1，且Bj在以后的裝箱中不再使用。最后循環(huán)shumo華中農(nóng)業(yè)大學(xué)李治FF(First

Fit－首次適應(yīng))算法：按照物體給定的順序裝箱：把物品wi放到第一個(gè)箱子中。B1B2…Bj是當(dāng)前已經(jīng)使用過的箱子，在這些箱子中找一個(gè)長度不小于wi且下標(biāo)最小的箱子,將放入wi，如果不存在這樣的箱子,則另開一個(gè)新箱子Bj+1,將wi放入Bj+1中。裝箱問題的求解——貪婪算法

shumo華中農(nóng)業(yè)大學(xué)李治在線算法：如果一個(gè)近似裝箱算法在執(zhí)行過程中，每當(dāng)一個(gè)物品到達(dá)時(shí)，就立刻決定把該物品放入哪個(gè)箱子中，而不管后序物品如何，這種算法就被稱為在線算法。下次適應(yīng)算法、首次適應(yīng)算法等都是在線算法，其時(shí)間復(fù)雜度都為O(n)。以上算法都稱為在線適應(yīng)算法，適應(yīng)算法的特點(diǎn)是當(dāng)處理當(dāng)前物品，如果有已經(jīng)打開的箱子中能夠放下這個(gè)物品，則不打開新的箱子。裝箱問題的求解——貪婪算法

shumo華中農(nóng)業(yè)大學(xué)李治不失一般性，對(duì)n件物品的體積按從大到小排好序，即有v1≥v2≥…≥vn，然后按排序結(jié)果對(duì)物品重新編號(hào)即可。降序首次適應(yīng)算法（FFD）:先將物體按長度從大到小排序,然后按FF算法對(duì)物體裝箱.離線算法：如果算法在開始裝箱之前，已經(jīng)預(yù)先得到了所有物品的信息而一次性的確定裝箱策略，這種算法就被稱為離線算法。降序首次適應(yīng)算法和降序最佳適應(yīng)算法是兩個(gè)重要的離線算法。這里的降序首次適應(yīng)算法就是一種貪婪算法。裝箱問題的求解——貪婪算法

shumo華中農(nóng)業(yè)大學(xué)李治FFD算法：{輸入箱子的容積；

輸入物品種數(shù)n；

按體積從大到小順序，輸入各物品的體積；

預(yù)置已用箱子為空；

預(yù)置已用箱子計(jì)數(shù)器box_count為0；

for(i=0;i<n;i++){從已用的第一只箱子開始順序?qū)ふ夷芊湃胛锲穒的箱子j；

if（已用箱子都不能再放物品i）

{另用一個(gè)箱子，并將物品i放入該箱子；

box_count++；}

else

將物品i放入箱子j；

}}裝箱問題的求解——貪婪算法

shumo華中農(nóng)業(yè)大學(xué)李治例9：利用FFD算法完成下題:設(shè)有6種物品，它們的體積分別為：60、45、35、20、20和20單位體積，箱子的容積為100個(gè)單位體積。裝箱問題的求解——貪婪算法

shumo華中農(nóng)業(yè)大學(xué)李治例10:多處理器調(diào)度問題

設(shè)有n個(gè)獨(dú)立的作業(yè){1,2,…,n}，由m臺(tái)相同的機(jī)器進(jìn)行加工處理。作業(yè)i所需的處理時(shí)間為ti?，F(xiàn)約定，任何作業(yè)可以在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。任何作業(yè)不能拆分成更小的子作業(yè)。多機(jī)調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。[分析]這個(gè)問題可以看成裝箱問題，也是NP完全問題。對(duì)于這一類問題，用貪婪選擇策略有時(shí)可以設(shè)計(jì)出較好的近似算法。采用最長處理時(shí)間作業(yè)優(yōu)先的貪婪選擇策略可以設(shè)計(jì)出解多處理器調(diào)度問題的較好的近似算法。按此策略，當(dāng)n≤m時(shí)，我們只要將機(jī)器i的[0,ti]時(shí)間區(qū)間分配給作業(yè)i即可。當(dāng)n＞m時(shí)，我們首先將n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理器。裝箱問題的求解——貪婪算法

shumo華中農(nóng)業(yè)大學(xué)李治

例如，設(shè)7個(gè)獨(dú)立作業(yè){1,2,3,4,5,6,7}由3臺(tái)機(jī)器M1,M2,和M3來加工處理。各作業(yè)所需的處理時(shí)間分別為{2,14,4,16,6,5,3}。按貪婪算法產(chǎn)生的作業(yè)調(diào)度如圖所示，所需的加工時(shí)間為17。當(dāng)n＞m時(shí)，因此算法所需的計(jì)算時(shí)間復(fù)雜度為O(nlogn)。裝箱問題的求解——貪婪算法

shumo華中農(nóng)業(yè)大學(xué)李治例如,一個(gè)軟件開發(fā)小組要在規(guī)定時(shí)間內(nèi)完成一項(xiàng)任務(wù),系統(tǒng)分析員把任務(wù)劃分成各個(gè)子任務(wù).由于每個(gè)子任務(wù)要求的花費(fèi)程序員的時(shí)間不同,不合理的分派將導(dǎo)致各程序員貽誤工期.這就是一個(gè)多處理器調(diào)度問題的應(yīng)用。裝箱問題的求解——貪婪算法

shumo華中農(nóng)業(yè)大學(xué)李治續(xù)例5：問題自身的特性決定了該問題運(yùn)用貪婪算法可以得到最優(yōu)解或較優(yōu)解。通常這里有三種貪婪準(zhǔn)則:1、價(jià)值貪婪準(zhǔn)則：從剩余的物品中，選出可以裝入背包的價(jià)值最大的物品，利用這種規(guī)則，價(jià)值最大的物品首先被裝入（假設(shè)有足夠容量），然后是下一個(gè)價(jià)值最大的物品，如此繼續(xù)下去，這種策略不能保證得到最優(yōu)解。2、質(zhì)量貪婪準(zhǔn)則：從剩下的物品中選擇可裝入背包的重量最小的物品，在一般情況下也不一定能得到最優(yōu)解。3、價(jià)值密度貪婪準(zhǔn)則：從剩余物品中選擇可裝入包的cj/wj值最大的物品，即按cj/wj非遞增的次序裝入物品，只要正被考慮的物品裝得進(jìn)就裝入背包，這種策略可能會(huì)得到最優(yōu)解。背包問題的求解——貪婪算法shumo華中農(nóng)業(yè)大學(xué)李治(1)輸入物品個(gè)數(shù)n,背包的容量limitW,每個(gè)物品的重量wj和價(jià)值cj。(2)對(duì)物品按單位價(jià)值從大到小排序。(3)將排序后的物品依次裝入背包。對(duì)于當(dāng)前物品j,若背包剩余可裝重量大于或等于wj,則將物品j裝入背包,繼續(xù)考慮下一個(gè)物品j+1,重復(fù)步驟3,否則得到問題的解,輸出。算法流程注：1、算法主要的運(yùn)算時(shí)間是用來對(duì)n個(gè)元素進(jìn)行排序，故其復(fù)雜性是O（nlogn）。2、對(duì)于解決0/1背包問題，總得來講，動(dòng)態(tài)規(guī)劃比貪婪算法要好些，可以得到最優(yōu)解。背包問題的求解——貪婪算法shumo華中農(nóng)業(yè)大學(xué)李治一維0/1背包問題方法的改進(jìn)：設(shè)有n=8個(gè)體積分別為54，45，43，29，23，21，14，1的物體和一個(gè)容積為C=110的背包，問選擇哪幾個(gè)物體裝入背包可以使其裝的最滿。如直接用貪婪算法，將物體由大到小順次裝入背包，到裝不下時(shí)再逐個(gè)試裝更小的一些，直至試到最小的一個(gè)或裝滿為止。按此處所給數(shù)據(jù)，先裝入54和45兩個(gè)，容積尚余11，最后只能再裝入體積為1的一個(gè)，總體積達(dá)到100，并不算太滿。此方法的好處是節(jié)省時(shí)間，主要的運(yùn)算時(shí)間是用來對(duì)n個(gè)元素進(jìn)行排序。背包問題的求解——貪婪算法shumo華中農(nóng)業(yè)大學(xué)李治如果對(duì)上述算法作一些改進(jìn)，可得到更好的結(jié)果。先從n個(gè)物體中試著取j個(gè)總體積不超過C的裝入背包，剩下的(n-j)個(gè)物體則利用貪婪算法盡量往里裝。此j值從零開始逐漸增加，反復(fù)進(jìn)行試探，直至j達(dá)到某預(yù)先給定的常數(shù)k(0<k<n)，最后從這些結(jié)果中取其最好的一個(gè)。如果在試探中能得到一個(gè)完全裝滿的方案，則此過程就可提前結(jié)束。因?yàn)閺膎個(gè)物體中取出j個(gè)共有種方案，此值隨著j的增加而增加較快，但可以證明此改進(jìn)算法的復(fù)雜性為O（knk+1）,因k是常數(shù)，故仍為多項(xiàng)式界的算法。背包問題的求解——貪婪算法shumo華中農(nóng)業(yè)大學(xué)李治按本例所給數(shù)值，取j=0時(shí)，因就是前述普通貪婪算法，已經(jīng)得到100的結(jié)果；取j=1時(shí)，共有8種方案，當(dāng)用29或23先裝入時(shí)，可得到54+29+23+1=107的更好結(jié)果；取j=2時(shí)，共有28種方案，其中有能將背包完全裝滿的結(jié)果（43+23+29+14+1=110）。故知此問題當(dāng)取k≥2時(shí)就可得到最優(yōu)解。背包問題的求解——貪婪算法shumo華中農(nóng)業(yè)大學(xué)李治由于是5個(gè)城市，環(huán)繞一圈為5條邊，貪婪方法求解此問題的過程是從最小邊開始，依此從小到大取邊加入到回路邊集中，但在將1條邊加入時(shí)不能使1頂點(diǎn)的度數(shù)超過3，也不能形成小回路。

旅行商問題的求解——貪婪算法將城市間的距離從小到大排列有：d24(1),d13(2),d15(2),d25(3),d45(6),d35(9),d34(9),d12(14),d14(16),d23(25)。shumo華中農(nóng)業(yè)大學(xué)李治d24(1)；d24(1)+d13(2)；d24(1)+d13(2)+d15(2)；d24(1)+d13(2)+d15(2)+d25(3)；d24(1)+d13(2)+d15(2)+d25(3)+[d45(6)]；（下標(biāo)中5出現(xiàn)了3次,頂點(diǎn)5有三條邊相連,d45(6)放棄）d24(1)+d13(2)+d15(2)+d25(3)+[d35(9)]；（下標(biāo)中5出現(xiàn)了3次,頂點(diǎn)5有三條邊相連,d34(6)放棄）d24(1)+d13(2)+d15(2)+d25(3)+d34(9)。得到一條回路：v1→v3→v4→v2→v5→v1是最佳的回路。旅行商問題的求解——貪婪算法shumo華中農(nóng)業(yè)大學(xué)李治例11

設(shè)有六個(gè)城市，其坐標(biāo)分別為a(0,0),b:(4,3),c:(1,7),d:(15,7),e(15,4),f:(18,0)。如下圖所示：旅行商問題的求解——貪婪算法shumo華中農(nóng)業(yè)大學(xué)李治6座城市間的距離矩陣為：旅行商問題的求解——貪婪算法shumo華中農(nóng)業(yè)大學(xué)李治

求解：先將任兩城市間的連線距離按從小到大的次序排列，然后從中逐個(gè)選擇。但有兩種情況的連線應(yīng)舍棄：

(1)使任一城市的度數(shù)（連線數(shù)）超過2的連線必須舍棄；

(2)在得到經(jīng)過所有點(diǎn)的回路前就形成小回路的連線必須舍棄。距離按從小到大的次序排列:Dde(3),Dab(5),Dbc(5),Def(5),Dae(7.07),Ddf(7.62),Dbe(11.01),Dbd(11.7),Ded(14),Dbf(14.32),Dce(14.32),Dae(15.52),Dad(16.55),Daf(18.38),Def(18.38)旅行商問題的求解——貪婪算法shumo華中農(nóng)業(yè)大學(xué)李治

按貪婪算法原則，其選擇過程如下：Dde；Dde+Dab；Dde+Dab+Dbc；Dde+Dab+Dbc+Def；Dde+Dab+Dbc+Def+[Dae]；(形成小回路，舍棄)Dde+Dab+Dbc+Def+[Ddf]；(形成小回路，舍棄)Dde+Dab+Dbc+Def+[Dbe]；(b頂點(diǎn)度數(shù)超過2，舍棄)Dde+Dab+Dbc+Def+[Dbd]；(b頂點(diǎn)度數(shù)超過2，舍棄)Dde+Dab+Dbc+Def+Dcd；Dde+Dab+Dbc+Def+Dcd+[Dbf]；(b頂點(diǎn)度數(shù)超過2，舍棄)Dde+Dab+Dbc+Def+Dcd+[Dce]；(c、e頂點(diǎn)度數(shù)超過2，舍棄)Dde+Dab+Dbc+Def+Dcd+[Dae]；(e頂點(diǎn)度數(shù)超過2，舍棄)Dde+Dab+Dbc+Def+Dcd+[Dae]；(e頂點(diǎn)度數(shù)超過2，舍棄)Dde+Dab+Dbc+Def+Dcd+[Dad]；(d頂點(diǎn)度數(shù)超過2，舍棄)Dde+Dab+Dbc+Def+Dcd+Daf；得到1條回路shumo華中農(nóng)業(yè)大學(xué)李治最后得到的回路如圖（a）的結(jié)果，總長度為50。旅行商問題的求解——貪婪算法shumo華中農(nóng)業(yè)大學(xué)李治不過，這不是此問題的最優(yōu)解，此問題的最優(yōu)解為下圖所示的路徑(可以用分枝定界等方法求得)，總長度為48.39。用貪婪方法得到的結(jié)果同最優(yōu)解相比只多了3.3%。旅行商問題的求解——貪婪算法shumo華中農(nóng)業(yè)大學(xué)李治背包問題的求解——分支定界例12假定我們有四種物品要裝包，限重10，各樣?xùn)|西價(jià)值為c={1,3,5,9},單重為w={2,3,4,7}。我們用分支定界法求解背包問題，首先對(duì)物品按單位價(jià)值從大到小編號(hào)

，使得模型為：shumo華中農(nóng)業(yè)大學(xué)李治背包問題的搜索樹是這樣定義的，第i層的結(jié)點(diǎn)到它的子結(jié)點(diǎn)的弧表示第i種物品裝包的數(shù)量，一個(gè)子結(jié)點(diǎn)表示一種選擇。此問題的樹中，第一層有兩個(gè)分支，第二、三、四層分別有三、四、六個(gè)分支。x1={0,1},x2={0,1,2},x3={0,1,2,3},x4={0,1,2,3,4,5}重量和值標(biāo)在相應(yīng)的結(jié)點(diǎn)上。如果a）它的重量超過限重，或b）它的值不大于當(dāng)前最好的可行值，那么，停止從這個(gè)結(jié)點(diǎn)向下搜索，砍去這條分支；回溯到后繼一個(gè)結(jié)點(diǎn)。結(jié)點(diǎn)(x1,x2,…,xk)的重量是，而它的值為shumo華中農(nóng)業(yè)大學(xué)李治shumo華中農(nóng)業(yè)大學(xué)李治動(dòng)態(tài)規(guī)劃求下面加權(quán)有向圖中從A到G的最短路：shumo華中農(nóng)業(yè)大學(xué)李治最優(yōu)化原理一個(gè)最優(yōu)策略具有這樣的性質(zhì)，即不論初始狀態(tài)與初始策略如何，對(duì)于先前決策所造成的狀態(tài)而言，下余所有決策必構(gòu)成最優(yōu)決策。shumo華中農(nóng)業(yè)大學(xué)李治最短路徑的圖上計(jì)算AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766583338422213335526643(18)(16)(13)(13)(10)(9)(12)(7)(6)(8)(7)(5)(9)(4)(3)shumo華中農(nóng)業(yè)大學(xué)李治解：(1)、分支定界法(2)、貪婪法(3)、DP方法比較15比較47次48

加法138次AB2C4D3E2F2G21加法28豐富了計(jì)算結(jié)果shumo華中農(nóng)業(yè)大學(xué)李治基本概念與基本方程(1)階段：k＝1，2，…，6n=6(2)狀態(tài)變量：Sk－第k階段所處的位置狀態(tài)集合如S2:(B1,B2)(3)決策變量uk

：在第k段Sk狀態(tài)時(shí)決定選取的下一段的某點(diǎn)(4)狀態(tài)轉(zhuǎn)移方程：Sk＋1

＝ukshumo華中農(nóng)業(yè)大學(xué)李治(6)階段效益：

d(Sk，uk)為第k段，采取策略u(píng)k到下一狀態(tài)的距離(5)最優(yōu)指標(biāo)函數(shù)：fk(Sk)：第k段，在Sk狀態(tài)時(shí)到終點(diǎn)G的最短距離shumo華中農(nóng)業(yè)大學(xué)李治k＝6，f6(F1)＝4f6(F2)＝3k＝5d(E1F1)+f6(F1)f5(E1)＝mind(E1F2)+f6(F2)3+4＝min=7u5(E1)=F1

5+3shumo華中農(nóng)業(yè)大學(xué)李治同理f5(E2)＝5u5(E2)＝F2

f5(E3)＝9u5(E3)＝F2k＝4d(D1E1)+f5(E1)f4(D1)＝mind(D1E2)+f5(E2)2+7＝min=7u4(D1)=E2

2+5shumo華中農(nóng)業(yè)大學(xué)李治同理f4(D2)＝6u4(D2)＝E2

f4(D3)＝8u4(D3)＝E2K=3……shumo華中農(nóng)業(yè)大學(xué)李治k＝1d(A

B1)+f2(B1)f1(A)＝mind(A

B2)+f2(B2)5+13＝min=18u1(A)=B1

3+16shumo華中農(nóng)業(yè)大學(xué)李治(三)基本方程fk(Sk)＝min{d(Skuk)+fk+1(Sk+1)}k=6,…1f7(S7)＝0或fk(Sk)＝min{d(Skuk)+fk+1(Sk+1)}k=5,…1f6(S6)＝min{d(S6u6)}shumo華中農(nóng)業(yè)大學(xué)李治Dijkstra于1959年提出了解決最短路問題的一般算法，此算法可按邊的權(quán)值由小到大的次序，通過貪婪選擇，逐步得到由給定源點(diǎn)到圖的其余各點(diǎn)間的最短路徑。其基本作法是，設(shè)置一個(gè)頂點(diǎn)集合S，一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度已知。初始時(shí)，S中僅含有源。設(shè)vi是G的某一個(gè)頂點(diǎn)，我們把從源到vi且中間只經(jīng)過S中頂點(diǎn)的路稱為從源到vi的路徑，并用數(shù)組dist來記錄當(dāng)前S中每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短路徑長度。最短路問題的求解shumo華中農(nóng)業(yè)大學(xué)李治①賦初值.給v0以P標(biāo)號(hào)，記P(v0)＝0，其余各點(diǎn)vi以T標(biāo)號(hào),T(vi)＝a(v0

,vi)，并將vi的父點(diǎn)設(shè)為v0，記錄u=v0,S={u},轉(zhuǎn)向②.②更新所有的T標(biāo)號(hào)和其父點(diǎn).

v∈V\S,如果T(v)>P(u)+a(u,v),則令T(v)=P(u)+a(u,v),并重新記錄v的父點(diǎn)為u,轉(zhuǎn)向③.③給出下一個(gè)P標(biāo)號(hào)并更新記錄u和S.設(shè)T(v*

)=min{T(v),v∈V\S},給v*以P標(biāo)號(hào),P(v*)=T(v*

),重新記錄u=v*,S=S+{u},轉(zhuǎn)向④.④終止判斷.若V\S非空,轉(zhuǎn)向②;否則終止.求賦權(quán)圖中單源最短路的Dijkstra算法：shumo華中農(nóng)業(yè)大學(xué)李治Dijkstra算法的幾點(diǎn)說明：①算法具有終止性.對(duì)一個(gè)p,q圖G來說,只要p步迭代,就可以求出v0到其它各點(diǎn)的最短路.若只求