30第十四章運(yùn)籌學(xué)中的啟發(fā)式方法課件

第十四章

運(yùn)籌學(xué)中的啟發(fā)式方法OperationalResearch(OR)運(yùn)籌學(xué)中的啟發(fā)式方法啟發(fā)式方法的概念應(yīng)用問題舉例啟發(fā)式方法的概念一、啟發(fā)式方法的提出良性結(jié)構(gòu)的問題：?jiǎn)栴}的結(jié)構(gòu)比較清晰，所含各元素之間的關(guān)系明確，邊界清楚，容易為人們所認(rèn)識(shí)，能夠比較方便地通過建模和使用一定的算法求得解決。概括地說良性結(jié)構(gòu)問題具有以下特征：(1)能建立起反映該問題性質(zhì)的一種“可接受”模型，與問題有關(guān)的主要信息可納入模型之中。(2)模型所需要的數(shù)據(jù)能夠得到。(3)有判定解的可行性和最優(yōu)性(或滿意性)的明確準(zhǔn)則。(4)模型可解，能擬定出求解模型的程序性步驟，而且得出的解能反映解決問題的可行方案。(5)求解工作所需的計(jì)算量不過大，所需費(fèi)用不過多。啟發(fā)式方法的提出在解決非良性結(jié)構(gòu)的問題時(shí)，保持問題的本來(lái)面目，建立基本符合問題實(shí)際情況的非標(biāo)準(zhǔn)模型。由于模型涉及因素多，結(jié)構(gòu)復(fù)雜，而與傳統(tǒng)的標(biāo)準(zhǔn)模型相去甚遠(yuǎn)，難以套用已有的標(biāo)準(zhǔn)算法，為得到可用的近似解，分析人員必須運(yùn)用自己的感知和洞察力，從與其有關(guān)而較基本的模型及算法中尋求其中的聯(lián)系，從中得到啟發(fā)，去發(fā)現(xiàn)和構(gòu)想可用于解決該問題的思路和途徑，人們稱這種方法為啟發(fā)式方法，用這種方法建立的算法為啟發(fā)式算法。啟發(fā)式方法的特點(diǎn)啟發(fā)式方法有下述優(yōu)點(diǎn)：計(jì)算步驟簡(jiǎn)單，易于實(shí)施。(2)常不需要高深和復(fù)雜的理論知識(shí)，因而可由未經(jīng)高級(jí)訓(xùn)練的人員實(shí)現(xiàn)。(3)與應(yīng)用優(yōu)化方法相比，?？梢詼p少大量的計(jì)算工作量，從而顯著節(jié)約開支和節(jié)省時(shí)間。(4)易于將定量分析與定性分析相結(jié)合。啟發(fā)式方法的策略三、啟發(fā)式方法的策略1.逐步構(gòu)解策略2.分解合成策略3.改進(jìn)策略4.搜索學(xué)習(xí)策略運(yùn)籌學(xué)中的啟發(fā)式方法啟發(fā)式方法的概念應(yīng)用問題舉例應(yīng)用問題舉例一、多個(gè)工件在設(shè)備上加工的排序問題問題描述：在A、B兩臺(tái)設(shè)備上順序加工n個(gè)工件(工件j=1,2,…,n)時(shí)，應(yīng)如何排列這些工件的順序，才能使總加工時(shí)間(從在A上開始加工第一個(gè)工件起到在B上加工完最后一個(gè)工件止)盡可能短。此處要求每個(gè)工件都先在A上加工，然后再在B上加工。例1

下表中列出了6個(gè)工件分別在設(shè)備A和B上的加工時(shí)間Aj（min）和Bj(min),所有工件都先在A上加工，再在B上加工。要求確定使總加工時(shí)間最短的工件加工順序。應(yīng)用問題舉例解由于B1=B2，A1<A2，故將工件1排在前面進(jìn)行加工所需的總加工時(shí)間較少?，F(xiàn)再看工件2和工件3，由于A2=A3,B3<B2,故將工件3排在工件2的后面加工所需的總加工時(shí)間較少。123456A306060208090B707050603040工件設(shè)備應(yīng)用問題舉例考慮工件1和工件2：應(yīng)用問題舉例考慮工件2和工件3：應(yīng)用問題舉例多工件在兩臺(tái)設(shè)備上加工排序的啟發(fā)式迭代步驟如下：(1)令i=1,k=0。(2)找出最小加工時(shí)間：tr=min{A1,A2,…,An,B1,B2,…,Bn}(14.1)(3)若tr=Aj，則將工件j安排為第i個(gè)加工工件，并置i：=i+1;若tr=Bj，則把工件j安排為第(n-k)個(gè)加工工件，并置k：=k+1。(4)將Aj和Bj從式(14.1)表示的工件加工時(shí)間表中刪去，即不再考慮已排好加工順序的工件j。(5)返回步驟(2)，直至式(14.1)中的工件加工時(shí)間表變成空集。應(yīng)用問題舉例用迭代步驟求解例1：已知：n=6，開始迭代時(shí)i=1,k=0。由式(14.1)，tr=20=A4,故將工件4排為第1，刪去A4和B4，并置i=1+1=2。此時(shí)tr=30=A1=B5,將工件1排為第2，工件5排為第6(n-k=6-0=6)，刪去A1,B1,A5和B5,置i=2+1=3，k=0+1=1。如此繼續(xù)，可得所有6個(gè)工件的加工順序?yàn)椋?→1→2→3→6→5總加工時(shí)間等于370分鐘，具體情況參見：應(yīng)用問題舉例旅行售貨員問題(TSP|travelingsalesmanproblem)指的是：一個(gè)售貨員從某一城市出發(fā)，訪問n個(gè)城市(去售貨)各一次且僅一次，然后回到原城市，問他走什么樣的路線才能使走過的總路程最短(或旅行費(fèi)用最低)。這個(gè)問題就是尋求總權(quán)最小的哈密爾頓(Hamilton)回路問題。到目前為止，對(duì)TSP問題還沒有提出多項(xiàng)式算法，對(duì)于較大的這種問題(例如n大于40)常需借助于啟發(fā)式算法求解。二、旅行售貨員(旅行商)問題應(yīng)用問題舉例1.C\|W節(jié)約算法迭代步驟如下：選取基點(diǎn)，例如選取點(diǎn)1為基點(diǎn)。將基點(diǎn)與其他各點(diǎn)連接，得到n-1條子回路1→j→1(j=2,3,…,n)。(2)對(duì)不違背限制條件的所有可連接點(diǎn)對(duì)(i,j)計(jì)算節(jié)約值(i,j不為基點(diǎn))s(i,j)=c1i+c1j-cij(3)將所有s(i,j)按其值由大到小排列。(4)按s(i,j)的上述順序，逐個(gè)考察其端點(diǎn)i和j，若滿足以下條件，就將弧(i,j)插入到旅行線路中。其條件是：①點(diǎn)i和點(diǎn)j不在一條線路上;②點(diǎn)i和點(diǎn)j均與基點(diǎn)相鄰。(5)返回步驟(4)，直至考察完所有可插入弧(i,j)為止。應(yīng)用問題舉例例2

用C-W節(jié)約算法求解下述旅行售貨員問題，已知訪問點(diǎn)的位置如圖中所示。應(yīng)用問題舉例解

（1）先按圖中給出的數(shù)據(jù)計(jì)算各點(diǎn)之間的歐氏距離c(i,j)，計(jì)算結(jié)果列入距離表中。因假設(shè)cij=cji,故各元素的值以主對(duì)角線為對(duì)稱。ABCDEFGA014.1424.7023.7119.2417.0313.00B14.14013.0423.7115.8113.0410.44C24.7013.04020.1012.6511.6613.45D23.7123.7120.1008.2510.7713.60E19.2415.8112.658.2502.836.71F17.0313.0411.6610.772.8304.12G13.0010.4413.4513.606.714.120至從應(yīng)用問題舉例（2）取A為基點(diǎn)，構(gòu)成初始旅行線路圖。應(yīng)用問題舉例（3）計(jì)算將弧(i,j)(i,j≠A)插入到線路中時(shí)引起的路程節(jié)約值，并由大到小排列，如下表：序號(hào)弧節(jié)約值序號(hào)弧節(jié)約值1(D,E)34.709(E,G)25.532(E,F)33.4410(C,G)24.253(C,E)31.2911(D,G)23.114(C,F)30.0712(B,F)18.135(D,F)29.9713(B,E)17.576(C,D)28.3114(B,G)16.707(F,G)25.9115(B,D)14.148(B,C)25.80應(yīng)用問題舉例（4）依節(jié)約值從大到小的次序，對(duì)每條弧加以考察，看是否應(yīng)將其插入線路中去。若將其插入，就要對(duì)線路作相應(yīng)的改變。序號(hào)弧線路及說明插入該弧的節(jié)約值0A→B→A,A→C→A,A→D→A,A→E→A,A→F→A,A→G→A1(D,E)A→B→A,A→C→A,A→D→E→A,A→F→A,A→G→A34.702(E,F)A→B→A,A→C→A,A→D→E→F→A,A→G→A33.443(C,E)E點(diǎn)與基點(diǎn)A不相鄰，不插入04(C,F)A→B→A,A→D→E→F→C→A,A→G→A30.075,6(D,F)(C,D)這些點(diǎn)已在同一條線路上07(F,G)F點(diǎn)與基點(diǎn)A不相鄰，不插入08(B,C)A→D→E→F→C→B→A,A→G→A25.89,10(E,G)(C,G)E點(diǎn)、C點(diǎn)與基點(diǎn)A不相鄰，不插入011(D,G)A→G→D→E→F→C→B→A23.11應(yīng)用問題舉例當(dāng)插入弧(D，G)之后，線路已包含所有要訪問的點(diǎn)，算法終止。用該方法得到的線路是：A→G→D→E→F→C→B→A該線路的總長(zhǎng)度：z=2×(14.14+24.70+23.71+19.24+17.03+13.00)-(34.70+33.44+30.07+25.80+23.11)=76.52應(yīng)用問題舉例2.幾何法基于對(duì)各訪問點(diǎn)構(gòu)成的幾何圖形的分析，以此確定初始線路和不在初始線路上的各點(diǎn)的插入順序和插入位置。根據(jù)一般幾何觀察可知，最短訪問線路應(yīng)具有以下直觀性質(zhì)：(1)線路自身不相交；(2)各段線路應(yīng)處于由所有訪問點(diǎn)形成的凸包上或其凸包內(nèi)部(這里所說的凸包(convexhull)是包含所有訪問點(diǎn)的最小凸集)。應(yīng)用問題舉例求解旅行售貨員問題的迭代步驟：找出由欲訪問各點(diǎn)構(gòu)成的凸包。(2)在凸包上的點(diǎn)，按其出現(xiàn)的自然順序訪問(不要使訪問線路自交)，從而形成一初始訪問線路。(3)將不在初始訪問線路上的各個(gè)點(diǎn)I(位于凸包內(nèi)的訪問點(diǎn))，與已在訪問線路上的所有點(diǎn)相連。設(shè)P與Q為已在訪問線路上的任兩個(gè)相鄰點(diǎn)，∠P0I0Q0為所有∠PIQ角度中的最大者，則將I0插入到P0和Q0之間。(4)重復(fù)進(jìn)行步驟(3)，每次在訪問線路上增加一個(gè)新點(diǎn)，直至所有欲訪問點(diǎn)都被引入到訪問線路中為止。這時(shí)就構(gòu)成了一條哈密爾頓回路。應(yīng)用問題舉例用幾何法求解例2：應(yīng)用問題舉例三、車輛調(diào)度問題(vehicleschedulingproblem，簡(jiǎn)記為VSP)所謂VSP問題，一般指的是：對(duì)一系列發(fā)貨點(diǎn)和收貨點(diǎn)，組織調(diào)用一定的車輛，安排適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足指定的約束條件下(例如：貨物的需求量與發(fā)貨量，交發(fā)貨時(shí)間，車輛可載量限制，行駛里程限制，行駛時(shí)間限制等)，力爭(zhēng)實(shí)現(xiàn)一定的目標(biāo)(如車輛空駛總里程最短，運(yùn)輸總費(fèi)用最低，車輛按一定時(shí)間到達(dá)，使用的車輛數(shù)最小等)。應(yīng)用問題舉例問題說明設(shè)某運(yùn)輸企業(yè)要完成的貨運(yùn)業(yè)務(wù)(例如指某一天或某半天)有m項(xiàng)：A1,A2,…,Am,其貨運(yùn)量分別是g1,g2,…,gm,完成各項(xiàng)運(yùn)輸業(yè)務(wù)所需的車輛數(shù)(根據(jù)貨物類型和車輛狀況而定)分別為a1,a2,…,am;此外，該企業(yè)有n個(gè)車場(chǎng)可以使用，即可從車場(chǎng)Am+1,Am+2,…,Am+n發(fā)出空車和接收空車，這些車場(chǎng)與各貨運(yùn)業(yè)務(wù)的發(fā)貨點(diǎn)和收貨點(diǎn)位于同一個(gè)連通道路網(wǎng)上，各車場(chǎng)可派出的空車數(shù)分別是bm+1,bm+2,…,bm+n,可接收的空車數(shù)分別是bm+1′,bm+2′,…,bm+n′。應(yīng)用問題舉例2.數(shù)學(xué)模型按照每項(xiàng)運(yùn)輸業(yè)務(wù)的要求將貨物由發(fā)貨點(diǎn)運(yùn)送到收貨點(diǎn)，這顯然均為重車行駛，且必須完成，在分析使總空駛里程極小化這一問題時(shí)，它的安排對(duì)目標(biāo)函數(shù)值不產(chǎn)生影響，可不予考慮。因此，可將每一項(xiàng)貨運(yùn)業(yè)務(wù)工作i,即從其發(fā)貨點(diǎn)i′將貨物運(yùn)送到收貨點(diǎn)i″，看成一個(gè)壓縮了的點(diǎn)——重載點(diǎn)i。應(yīng)用問題舉例設(shè)由點(diǎn)i發(fā)往點(diǎn)j(i,j為車場(chǎng)或重載點(diǎn))的空車數(shù)為xij，其空駛里程為cij,則使總空駛里程極小化的空車調(diào)度問題的數(shù)學(xué)模型可描述如下：i=1,2,...,mi=m+1,m+2,...m+nj=1,2,...,mj=m+1,m+2,...m+n其中ai(aj)為：Q為一輛車的可載量。應(yīng)用問題舉例運(yùn)輸問題式的運(yùn)輸表如表所示。表中將重載點(diǎn)和車場(chǎng)分開，形成了4個(gè)區(qū)域：C—C，C—F，F(xiàn)—C和F—F應(yīng)用問題舉例3.算法首先僅考慮重載點(diǎn)部分：i=1,2,...mj=1,2,...m應(yīng)用問題舉例(1)解的擴(kuò)展對(duì)解X(0)中的每一個(gè)非零分量xij(0)>0(i,j=1,2,…,m)，計(jì)算其中：i=m+1,...,m+nj=m+1,...,m+n應(yīng)用問題舉例算出的δij值為按下述方法調(diào)整xij(0)

一個(gè)單位引起的空駛里程增加量。若δij來(lái)自k行和l列(k,l∈［m+1,m+n］),則把xij(0)

擴(kuò)展至xkj

(0)和xil(0),這時(shí)，將xij(0)、xkj(0)

和xil(0)

三個(gè)變量的值分別調(diào)整為：解的這種擴(kuò)展工作按δij的大小，由小到大依次進(jìn)行，直至找出要求的可