時(shí)序和路徑規(guī)劃.ppt

第五章 時(shí)序和路徑規(guī)劃,應(yīng)用運(yùn)籌學(xué),浙江大學(xué)管理學(xué)院 杜紅 博士 副教授,第五章 時(shí)序和路徑規(guī)劃,時(shí)序規(guī)劃 最小樹問題 通過一個(gè)網(wǎng)絡(luò)的最短路徑 通過一個(gè)網(wǎng)絡(luò)的最大流量,工作的時(shí)序規(guī)劃,時(shí)序順序時(shí)間 時(shí)序規(guī)劃 多項(xiàng)任務(wù)等待同一人或物處理，每項(xiàng)任務(wù)的單獨(dú)完成的時(shí)間確定，且沒有先后關(guān)系（緊前、緊后）。怎樣安排各項(xiàng)任務(wù)的順序，使總效率最高？ 系統(tǒng)時(shí)間加工時(shí)間排隊(duì)時(shí)間,工作的時(shí)序規(guī)劃,時(shí)序規(guī)劃原則目標(biāo) 到達(dá)時(shí)間先進(jìn)先出 最小富裕時(shí)間（到期時(shí)間加工時(shí)間） 最接近完成者優(yōu)先 在完成之前最少的機(jī)器開關(guān)次數(shù) 下一工作最短的排隊(duì) 關(guān)鍵比例最低 最重要的優(yōu)先 加工工序之間的轉(zhuǎn)換成本最低 加工時(shí)間最短者優(yōu)先 最先到期的工作優(yōu)先,工作的時(shí)序規(guī)劃,平均排隊(duì)（等待）時(shí)間最短問題 加工時(shí)間最短者優(yōu)先 （相同時(shí)間的可任意安排） 平均延誤時(shí)間最短問題 最先到期的工作優(yōu)先 例51：教材 P105 實(shí)例5.3,工作的時(shí)序規(guī)劃,例52：教材 P106 實(shí)例5.4 平均排隊(duì)時(shí)間最短：加工時(shí)間短者優(yōu)先 A G C H E B F D 加工時(shí)間 2 2 3 3 4 5 7 8 等待時(shí)間 0 2 4 7 10 14 19 26 總等待時(shí)間：82 平均等待時(shí)間：10.25,工作的時(shí)序規(guī)劃,平均延誤時(shí)間最短：最先到期者優(yōu)先 G B C A E F D H 到期時(shí)間 2 7 8 13 14 20 30 36 加工時(shí)間 2 5 3 2 4 7 8 3 開始時(shí)間 0 2 7 10 12 16 23 31 完工時(shí)間 2 7 10 12 16 23 31 34 延誤時(shí)間 0 0 2 0 2 3 1 0 總延誤時(shí)間：8 平均延誤時(shí)間：1,工作的時(shí)序規(guī)劃,延誤的工作項(xiàng)數(shù)最少 先按先到期者優(yōu)先的原則排初次次序 如果沒有延誤的工作，則是最優(yōu)解。 如果有延誤的工作，則找出其中的一項(xiàng)，找出到此項(xiàng)工作之前（包括該項(xiàng)）加工時(shí)間最長(zhǎng)的一項(xiàng)，并將之抽去，重新安排時(shí)間，如果已沒有延誤的工作，則將被抽取的這一項(xiàng)放置最后；如仍有被延誤的工作，則再重復(fù)這一步。,工作的時(shí)序規(guī)劃,按先到期者優(yōu)先原則安排的初次次序?yàn)椋?G B C A E F D H 到期時(shí)間 2 7 8 13 14 20 30 36 加工時(shí)間 2 5 3 2 4 7 8 3 完工時(shí)間 2 7 10 12 16 23 31 34 延誤時(shí)間 0 0 2 0 2 3 1 0 找出一項(xiàng)延誤的工作是 C ；C 之前（包括 C）加工時(shí)間最長(zhǎng)的是 B, 抽去 B 后，重新安排時(shí)間：,工作的時(shí)序規(guī)劃,抽去工作 B 后的次序安排： G C A E F D H 到期時(shí)間 2 8 13 14 20 30 36 加工時(shí)間 2 3 2 4 7 8 3 開始時(shí)間 0 2 5 7 11 18 26 完工時(shí)間 2 5 7 11 18 26 29 延誤時(shí)間 0 0 0 0 0 0 0,B 7 5 29 34 27,工作的時(shí)序規(guī)劃,時(shí)序規(guī)劃擴(kuò)展： 兩臺(tái)順序機(jī)器完成一批工作 每項(xiàng)工作在機(jī)器1和機(jī)器2上的加工時(shí)間不一樣，如何使系統(tǒng)效率最高？,3,2,1,4,機(jī)器1,機(jī)器2,工作,工作的時(shí)序規(guī)劃,約翰遜原則 找出各臺(tái)機(jī)器上加工時(shí)間最短的一項(xiàng)工作， 如果在機(jī)器1上，這項(xiàng)工作最先做； 如果在機(jī)器2上，這項(xiàng)工作最后做； 不斷重復(fù)，從兩端往內(nèi)排。相同時(shí)間可任選一個(gè)，一般先安排機(jī)器1上工作。,工作的時(shí)序規(guī)劃,例53：教材P110 實(shí)例5.6 工作： A B C D E F G 機(jī)器1： 2 5 10 8 4 12 9 機(jī)器2： 14 7 3 10 5 6 6 順序： 1開始： 0 2 6 11 19 31 40 1完成： 2 6 11 19 31 40 50 2開始： 2 16 21 28 38 44 50 2完成： 16 21 28 38 44 50 53,A,C,E,B,D,G,F,最小樹問題,圖及相關(guān)的概念 圖：點(diǎn)及點(diǎn)與點(diǎn)之間的連線（箭線：有向圖）構(gòu)成 邊與?。簝牲c(diǎn)之間連線為邊或?。€）如： 1-2，4-6 鏈與路：任意兩點(diǎn)之間的點(diǎn)與邊（?。┙M成了一條鏈（路）。 如：1-2-4-6 圈與回路：鏈（路）的兩端為同一點(diǎn)則形成一個(gè)圈（回路）。 如：1-2-3 連通圖：任意兩點(diǎn)之間至少有一條鏈，沒有孤立點(diǎn)。 網(wǎng)絡(luò)：一個(gè)有向圖的弧有某種“流轉(zhuǎn)物”流動(dòng)時(shí)的圖稱為網(wǎng)絡(luò) 權(quán)：邊或弧的權(quán)數(shù)，表示邊或弧性質(zhì)或數(shù)量。,最小樹問題,樹的概念 連通圖，但沒有圈為樹。由所有節(jié)點(diǎn)(N)和相應(yīng)的邊(N-1)組成。,最小樹問題,最小樹 一個(gè)網(wǎng)絡(luò)中有很多樹，其中邊的長(zhǎng)度（權(quán)數(shù)）之和為最小的樹為最小樹。 最小樹的獲取破圈法 從圖中任取一個(gè)圈，去掉該圈的一條最大邊，將此圈破去，然后重復(fù)破圈，直至無圈為止。,最小樹問題,1,6,3,4,5,2,7,4,3,2,3,2,4,5,1,7,2,6,7,4,例54：求以下圖的最小樹,通過一個(gè)網(wǎng)絡(luò)的最短路徑,問題 在一個(gè)網(wǎng)絡(luò)中，給定一個(gè)始點(diǎn)Vs，和一個(gè)終點(diǎn)Vt，求Vs 到Vt的一條路，使路長(zhǎng)最短。 求解 能劃分階段的，可采用動(dòng)態(tài)規(guī)劃方法。 不能分階段的，采用狄克斯屈方法。,通過一個(gè)網(wǎng)絡(luò)的最短路徑,狄克斯屈（Dijstra）方法 開始節(jié)點(diǎn)標(biāo)永久標(biāo)記0,S,其余為臨時(shí)標(biāo)記T,- 找出與開始節(jié)點(diǎn)相鄰的所有節(jié)點(diǎn)，為每一個(gè)設(shè)標(biāo)記L,1，其中L值最小的節(jié)點(diǎn)標(biāo)記右上角標(biāo)上*，使之成為永久標(biāo)志。L為兩節(jié)點(diǎn)間距離，1表示始于第一節(jié)點(diǎn) 從新的永久標(biāo)志開始，找出從此節(jié)點(diǎn)出發(fā)可到達(dá)的所有節(jié)點(diǎn)，計(jì)算這些節(jié)點(diǎn)的最短距離（現(xiàn)有距離和經(jīng)新的永久標(biāo)志到達(dá)的距離的小的一個(gè)值），保持、新設(shè)或更改這些節(jié)點(diǎn)的標(biāo)志為 最短距離，最短路徑上前一節(jié)點(diǎn)標(biāo)號(hào)，比較圖中所有沒有*的標(biāo)記（臨時(shí)性標(biāo)記），找出距離最短的一個(gè)節(jié)點(diǎn)，使之成為永久性標(biāo)記。重復(fù)這一步，直到所有的節(jié)點(diǎn)都成為永久性標(biāo)志為止。,通過一個(gè)網(wǎng)絡(luò)的最短路徑,k,i,j,Di ,m,Lij,Dj,k,從i-j時(shí)： 如果Di+LijDj,則不改變j的標(biāo)記； 如果Di+LijDj，則改為Di+Lij,i,通過一個(gè)網(wǎng)絡(luò)的最短路徑,例55 狄克斯屈方法 ：教材P131 實(shí)例5.12,35,4,1,4,3,2,6,5,7,20,15,10,6,8,24,10,8,20,11,0,S,21,3,25,3,44,2,T,-,T,-,T,-,T,-,T,-,T,-,20,1,15,1,41,6,*,*,*,*,*,*,通過一個(gè)網(wǎng)絡(luò)的最短路徑,從起始點(diǎn)到每一點(diǎn)的最短距離為： 節(jié)點(diǎn) 最短距離 路徑 2 20 12 3 15 13 4 25 134 5 35 1345 6 21 136 7 41 1367,最短路徑問題的應(yīng)用,例56：設(shè)備更新問題 某廠使用一種設(shè)備，每年年初設(shè)備科需要對(duì)該設(shè)備的更新與否作出決策。若購(gòu)置新設(shè)備，就要支付購(gòu)置費(fèi)；如果繼續(xù)使用則需要支付維修費(fèi)，設(shè)備使用的年數(shù)越長(zhǎng)，每年所需的維修費(fèi)越多。現(xiàn)若第一年年初購(gòu)置了一臺(tái)新設(shè)備，問在5年內(nèi)如何制定設(shè)備更新計(jì)劃，以便使新設(shè)備購(gòu)置費(fèi)和維修費(fèi)的總費(fèi)用最??？已知設(shè)備在5年內(nèi)各年年初的價(jià)格及設(shè)備使用不同年數(shù)的維修費(fèi)如下：,最短路徑問題的應(yīng)用,例56：設(shè)備更新問題 把求總費(fèi)用最小問題化為最短路徑問題。用點(diǎn) i (i=1,2,3,4,5)表示第 i 年買進(jìn)一臺(tái)新設(shè)備。增設(shè)一點(diǎn) 6 表示第五年末。從i點(diǎn)到i+1, 6 各畫一條弧，弧（i , j）表示在第 i 年買進(jìn)的設(shè)備一直使用到第 j 年年初（第 j 1年年末）。求1點(diǎn)到6點(diǎn)的最短路徑。路徑的權(quán)數(shù)為購(gòu)買和維修費(fèi)用。 ?。╥ , j）的權(quán)數(shù)為第i年的購(gòu)置費(fèi)ai從第i年使用至第j-1年末的維修費(fèi)之和。 從第i年使用至第j-1年末的維修費(fèi)：b1+bj-i （使用壽命為j-i年） 如：（24）權(quán)數(shù)為：a2+b1+b2=1156=22 具體權(quán)數(shù)計(jì)算結(jié)果如下：,通過一個(gè)網(wǎng)絡(luò)的最短路徑,例56 設(shè)備更新問題 ： 使用Dijstra算法，上述問題最短路為1-3-6或1-4-6 即：第1、3年年初購(gòu)買設(shè)備，或第1、4年年初購(gòu)買設(shè)備 五年最佳總費(fèi)用為53。,1,3,2,5,4,6,16,22,17,18,23,30,59,41,17,30,16,23,41,31,22,作業(yè)題：,某地7個(gè)村鎮(zhèn)之間現(xiàn)有交通距離如圖 求：1)從村1到其余各村的最短距離？ 2)如要沿路架設(shè)電話線，如何使總長(zhǎng)度最小同時(shí)又使每個(gè)村都能安裝上電話？,1,6,3,4,5,2,7,12,11,10,15,12,10,25,16,17,15,26,7,24,通過一個(gè)網(wǎng)絡(luò)的最大流量,最大流量問題 在一定條件下，使網(wǎng)絡(luò)系統(tǒng)中從開始點(diǎn)到結(jié)束點(diǎn)之間的某種物資流的流量達(dá)到最大的問題。限制條件是每一條邊的最大通過能力（流量）不等。但有多條路 最大流量求解 線性規(guī)劃方法 福特富爾克遜標(biāo)號(hào)法（“分步流動(dòng)”）,最大流量的線性規(guī)劃模型,例57：有下列石油運(yùn)輸管道圖。某公司欲采用這個(gè)網(wǎng)絡(luò)圖從1地向銷地7運(yùn)送原油，弧的容量Cij（萬升/時(shí)）已給定（因管道直徑的變化，Cij不完全相同）。問如何安排輸送，方能使每小時(shí)運(yùn)送的原油最多？,最大流量的線性規(guī)劃模型,設(shè)弧（i,j）上的流量為Fij, 總流量為F. 目標(biāo)函數(shù)：MAX F=F12+F14 約束條件： 流入流出; FijCij; Fij0 2點(diǎn)：F12=F23+F25; 4點(diǎn)：F14=F43+F46+F47 3點(diǎn)：F23+F43=F35+F36; 5點(diǎn) ：F25+F35F57 6點(diǎn)：F36+F46F67 ; 7點(diǎn)：F47+F57+F67=F12+F14 解：F12=5;F14=5;F23=2;F25=3;F43=2;F46=1;F47=2;F35=2 F36=2;F57=5;F67=3 最大流量F10,3,4,2,6,5,7,6,2,3,2,1,2,5,6,4,3,2,1,思考題：最小費(fèi)用最大流,如果?。╥,j）上的單位流量費(fèi)用為Bij (百元/萬升）。 圖中每一條弧的權(quán)數(shù)前一位為流量限制Cij，后一位為單位費(fèi)Bij。 怎樣運(yùn)送才能使運(yùn)送最多的石油并使總的費(fèi)用最?。?提示：先求得最大F值；再求總流量為F時(shí)使總費(fèi)用最小的方案。 進(jìn)一步思考：求最小費(fèi)用問題。 如何求每小時(shí)運(yùn)送6萬升原油的最小費(fèi)用？,3,4,2,6,5,7,6,3,2,5,3,2,2,3,1,3,2,8,5,7,6,6,4,4,3,4,2,4,1,最大流量的標(biāo)注法,標(biāo)記：流入節(jié)點(diǎn)的流量，該流量的來源節(jié)點(diǎn)，第一個(gè)節(jié)點(diǎn)標(biāo)記，S。 選取已有標(biāo)記的一個(gè)節(jié)點(diǎn)，找出從此節(jié)點(diǎn)能直接到達(dá)的一個(gè)節(jié)點(diǎn)，確定到達(dá)節(jié)點(diǎn)的最大流量，相應(yīng)地標(biāo)上標(biāo)記。重復(fù)這一步，盡快到達(dá)終點(diǎn)，得到一條從起點(diǎn)到終點(diǎn)的路徑，此路徑的最大流量為流入終點(diǎn)的流量。將此路徑上的每一邊的流動(dòng)能力減去此流量。再?gòu)钠鹗脊?jié)點(diǎn)開始，按新的流動(dòng)能力，重新進(jìn)行標(biāo)號(hào)，找出新的一條途徑和流量，重復(fù)進(jìn)行下去，直到把所有可能的路徑全部找到為止，全部路徑的流量和即為通過該網(wǎng)絡(luò)的最大流量。,最大流量的標(biāo)注法,i,j,Fi,K,Fj,i,mij,Fj=min(Fi,mij),K,最大流量的標(biāo)注法,例59：教材P135 實(shí)例5.14,1,4,2,3,6,5,7,18,2,10,7,6,8,10,18,9,16,10,S,10,1,7,2,6,2,6,5,6,5,18,1,得到了第一條線路的最大流量：1257，流量為 6,最大流量的標(biāo)注法,將1257通過能力減去6，重新標(biāo)號(hào),S,7,2,7,4,3,5,12,1,得到了第二條線路的最大流量：12457，流量為 3,最大流量的標(biāo)注法,將12457通過能力減去3，重新標(biāo)號(hào),S,8,6,得到了第三條線路的最大流量：1367，流量