數(shù)學(xué)建模運(yùn)籌模型課件

1、數(shù)學(xué)建模與運(yùn)籌模型數(shù)學(xué)建模與運(yùn)籌模型 線性規(guī)劃線性規(guī)劃 運(yùn)輸問題運(yùn)輸問題 指派問題指派問題 網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)優(yōu)化 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃目錄目錄 例例 某工廠在計(jì)劃期內(nèi)要安排某工廠在計(jì)劃期內(nèi)要安排，兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn) 單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A A，B B兩種原材料的消耗、資源的兩種原材料的消耗、資源的限制，如下表。問題：工廠應(yīng)分別生產(chǎn)多少單位限制，如下表。問題：工廠應(yīng)分別生產(chǎn)多少單位，產(chǎn)品產(chǎn)品才能使工廠獲利最多？才能使工廠獲利最多？ 線性規(guī)劃線性規(guī)劃例例 下料問題下料問題 某工廠要做某工廠要做100100套鋼架，每套用長為套鋼架，每套用長為2.9m

2、2.9m，2.1m2.1m，1.5m1.5m的圓鋼各一根，已知原料每根長的圓鋼各一根，已知原料每根長7.4m7.4m。應(yīng)如何下料，可使所用原料最??？。應(yīng)如何下料，可使所用原料最??？解：共可設(shè)計(jì)下列解：共可設(shè)計(jì)下列5 5種下料方案種下料方案線性規(guī)劃線性規(guī)劃建模步驟：建模步驟：(1)(1)確定決策變量：我們需要作出決策或者選擇的量，確定決策變量：我們需要作出決策或者選擇的量，一般情況下，題目問什么就設(shè)什么為決策變量。一般情況下，題目問什么就設(shè)什么為決策變量。(2)(2)找出約束條件：即決策變量受到的所有的約束。找出約束條件：即決策變量受到的所有的約束。(3)(3)寫出目標(biāo)函數(shù)：即問題所要達(dá)到的目標(biāo)

3、，并明確寫出目標(biāo)函數(shù)：即問題所要達(dá)到的目標(biāo)，并明確是求是求maxmax還是還是minmin。線性規(guī)劃線性規(guī)劃例例 混合配料問題混合配料問題 某糖果廠用原料某糖果廠用原料1 1、2 2、3 3加工三種加工三種不同牌號(hào)的糖果甲、乙、丙。已知各種牌號(hào)糖果中不同牌號(hào)的糖果甲、乙、丙。已知各種牌號(hào)糖果中原料原料1 1、2 2、3 3的含量、原料每月限用量、三種牌號(hào)的含量、原料每月限用量、三種牌號(hào)糖果的加工費(fèi)及售價(jià)，如下表所示。該廠每月如何糖果的加工費(fèi)及售價(jià)，如下表所示。該廠每月如何生產(chǎn)才能獲利最大？生產(chǎn)才能獲利最大？線性規(guī)劃線性規(guī)劃解：用解：用i=1,2,3i=1,2,3代表原料代表原料1,2,3, j

4、=1,2,31,2,3, j=1,2,3代表糖果甲、乙、丙。代表糖果甲、乙、丙。X Xijij表示第表示第j j中產(chǎn)品中原料中產(chǎn)品中原料i i的含量，則的含量，則 對(duì)于原料對(duì)于原料1 1： x x1111, x, x1212, x, x1313; ; 對(duì)于原料對(duì)于原料2 2： x x2121, x, x2222, x, x2323; ; 對(duì)于原料對(duì)于原料3 3： x x3131, x, x3232, x, x3333; ; 對(duì)于甲：對(duì)于甲： x x1111, x, x2121, x, x3131; ; 對(duì)于乙：對(duì)于乙： x x1212, x, x2222, x, x3232; ; 對(duì)于丙：對(duì)于

5、丙： x x1313, x, x2323, x, x3333; ; 目標(biāo)函數(shù)：利潤最大，利潤目標(biāo)函數(shù)：利潤最大，利潤= =收入收入- -原料成本原料成本- -加工費(fèi)加工費(fèi) 約束條件：原料用量限制，含量限制約束條件：原料用量限制，含量限制線性規(guī)劃線性規(guī)劃線性規(guī)劃線性規(guī)劃求解方法：求解方法：1.1.圖解法圖解法 適合含有兩個(gè)決策變量的模型；適合含有兩個(gè)決策變量的模型； max z = x1+3x2s.t. x1+ x26-x1+2x28x1 0, x20可行域目標(biāo)函數(shù)等值線最優(yōu)解64-860 x1x2線性規(guī)劃線性規(guī)劃2.2.單純形法單純形法( (人工變量法、對(duì)偶單純形法人工變量法、對(duì)偶單純形法)

6、)軟件求解：軟件求解：lingolingo，lindolindo，MatlabMatlabMin f= 0.4x1+1.5x2+x3+1.3x4 S.t. 0.3x1+3x2 + +1.5x4=320 0.5x1+ +2x3+x4 =240 1.4x1+ +0.7x4=420 線性規(guī)劃線性規(guī)劃 將某種物資從將某種物資從m m個(gè)產(chǎn)地遇到個(gè)產(chǎn)地遇到n n個(gè)銷地，每個(gè)產(chǎn)地都有一定個(gè)銷地，每個(gè)產(chǎn)地都有一定的產(chǎn)量的產(chǎn)量a ai i，i=1,2,mi=1,2,m，每個(gè)銷地都對(duì)物資有一定的需求，每個(gè)銷地都對(duì)物資有一定的需求量量b bj j,j=1,2,n,j=1,2,n。已知從第。已知從第i i個(gè)產(chǎn)地向第個(gè)

7、產(chǎn)地向第j j個(gè)銷地運(yùn)送單個(gè)銷地運(yùn)送單位物資的運(yùn)價(jià)為位物資的運(yùn)價(jià)為c cijij，總產(chǎn)量等于總需求量，總產(chǎn)量等于總需求量( )( )。如何調(diào)運(yùn)物資，才能使總運(yùn)費(fèi)最??？如何調(diào)運(yùn)物資，才能使總運(yùn)費(fèi)最??？ 設(shè)設(shè)x xijij為從產(chǎn)地為從產(chǎn)地A Ai i運(yùn)往銷地運(yùn)往銷地B Bj j的運(yùn)輸量，的運(yùn)輸量，運(yùn)輸問題運(yùn)輸問題11mnijijab 運(yùn)輸表：運(yùn)輸表： ( (產(chǎn)銷平衡的運(yùn)輸問題產(chǎn)銷平衡的運(yùn)輸問題) )求解方法：求解方法： 1.1.確定初始基本可行解（西北角法、最小元素法、確定初始基本可行解（西北角法、最小元素法、vogalvogal法）法） 2.2.最優(yōu)性檢驗(yàn)；最優(yōu)性檢驗(yàn)； 3.3.迭代求新的基本可

8、行解。迭代求新的基本可行解。運(yùn)輸問題運(yùn)輸問題例例 某食品公司下屬的三個(gè)食品廠某食品公司下屬的三個(gè)食品廠A1A1、A2A2、A3A3生產(chǎn)食品，生產(chǎn)食品，3 3個(gè)廠個(gè)廠每月的生產(chǎn)能力分別為每月的生產(chǎn)能力分別為7 7噸、噸、4 4噸、噸、9 9噸，食品被運(yùn)到噸，食品被運(yùn)到B1B1、B2B2、B3B3、B4B4四個(gè)銷售點(diǎn)，它們對(duì)方便食品的月需求量分別為四個(gè)銷售點(diǎn)，它們對(duì)方便食品的月需求量分別為3 3噸、噸、6 6噸、噸、5 5噸、噸、6 6噸，運(yùn)輸表如下表，試制定最優(yōu)運(yùn)送方案。噸，運(yùn)輸表如下表，試制定最優(yōu)運(yùn)送方案。運(yùn)輸問題運(yùn)輸問題解：解：1.1.確定初始基可行解確定初始基可行解 最小元素法：最小元素法

9、：運(yùn)輸問題運(yùn)輸問題解：解：1.1.確定初始基可行解確定初始基可行解( (最小元素法最小元素法) ) 初始基本可行解對(duì)應(yīng)的目標(biāo)函數(shù)值：初始基本可行解對(duì)應(yīng)的目標(biāo)函數(shù)值： f=3f=3* *4+104+10* *3+13+1* *3+23+2* *1+41+4* *6+56+5* *3=863=86運(yùn)輸問題運(yùn)輸問題解：解：2.2.最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn) (1)(1)位勢(shì)：位勢(shì)： u ui i+ +v vj j = =c cij ij (i=1,2,m,j=1,2,n)(i=1,2,m,j=1,2,n) 其中其中c cij ij 為基本可行解中基變量對(duì)應(yīng)的單位運(yùn)價(jià)。為基本可行解中基變量對(duì)應(yīng)的單位運(yùn)價(jià)。

10、注：注：m+n-1m+n-1個(gè)方程，個(gè)方程，m+nm+n個(gè)變量。個(gè)變量。 (2)(2)利用位勢(shì)求非基變量檢驗(yàn)數(shù)利用位勢(shì)求非基變量檢驗(yàn)數(shù) 檢驗(yàn)數(shù)計(jì)算公式：檢驗(yàn)數(shù)計(jì)算公式： c cij ij -u-ui i- -v vj j (3)(3)檢驗(yàn)數(shù)全都大于等于零時(shí)對(duì)應(yīng)的解為最優(yōu)解。檢驗(yàn)數(shù)全都大于等于零時(shí)對(duì)應(yīng)的解為最優(yōu)解。運(yùn)輸問題運(yùn)輸問題位勢(shì)：位勢(shì)：檢驗(yàn)數(shù)：檢驗(yàn)數(shù)：運(yùn)輸問題運(yùn)輸問題3.3.迭代求新基本可行解迭代求新基本可行解(1)(1)負(fù)檢驗(yàn)數(shù)中最小者對(duì)應(yīng)的變量進(jìn)基；負(fù)檢驗(yàn)數(shù)中最小者對(duì)應(yīng)的變量進(jìn)基；(2)(2)在運(yùn)輸表中找一個(gè)包含進(jìn)基變量的閉回路，這個(gè)回路上其在運(yùn)輸表中找一個(gè)包含進(jìn)基變量的閉回路，這個(gè)回

11、路上其他頂點(diǎn)均為基變量。依次對(duì)閉回路的四個(gè)頂點(diǎn)標(biāo)號(hào)，將頂他頂點(diǎn)均為基變量。依次對(duì)閉回路的四個(gè)頂點(diǎn)標(biāo)號(hào)，將頂點(diǎn)分為奇點(diǎn)格和偶點(diǎn)格；點(diǎn)分為奇點(diǎn)格和偶點(diǎn)格；(3)(3)偶點(diǎn)格的最小值作為調(diào)整量，所有奇點(diǎn)格偶點(diǎn)格的最小值作為調(diào)整量，所有奇點(diǎn)格+ +調(diào)整量；偶點(diǎn)調(diào)整量；偶點(diǎn)格格- -調(diào)整量，即一次迭代。調(diào)整量，即一次迭代。(4)(4)按位勢(shì)方程求新解對(duì)應(yīng)的位勢(shì)及檢驗(yàn)數(shù)，判別最優(yōu)性。按位勢(shì)方程求新解對(duì)應(yīng)的位勢(shì)及檢驗(yàn)數(shù)，判別最優(yōu)性。運(yùn)輸問題運(yùn)輸問題閉回路：閉回路： 運(yùn)輸問題運(yùn)輸問題迭代及新基本可行解的檢驗(yàn)數(shù)計(jì)算：迭代及新基本可行解的檢驗(yàn)數(shù)計(jì)算： 運(yùn)輸問題運(yùn)輸問題 產(chǎn)銷不平衡運(yùn)輸問題：產(chǎn)銷不平衡運(yùn)輸問題：1.

12、 1. 供大于求，引入虛擬銷售點(diǎn)，并假設(shè)它的需求量為供大于求，引入虛擬銷售點(diǎn)，并假設(shè)它的需求量為 供不應(yīng)求，引入虛擬的產(chǎn)地，并假設(shè)它的產(chǎn)量為供不應(yīng)求，引入虛擬的產(chǎn)地，并假設(shè)它的產(chǎn)量為 由于虛擬銷地是不存在的，實(shí)際上這個(gè)差值是在產(chǎn)地貯存由于虛擬銷地是不存在的，實(shí)際上這個(gè)差值是在產(chǎn)地貯存的，故從產(chǎn)地到虛擬銷地的單位運(yùn)價(jià)為的，故從產(chǎn)地到虛擬銷地的單位運(yùn)價(jià)為0 0； 同理，由于虛擬產(chǎn)地是不存在的，所以虛設(shè)的產(chǎn)地到各個(gè)同理，由于虛擬產(chǎn)地是不存在的，所以虛設(shè)的產(chǎn)地到各個(gè)銷地的單位運(yùn)價(jià)也為銷地的單位運(yùn)價(jià)也為0.0.11mnijijab運(yùn)輸問題運(yùn)輸問題11mnijijab11mnijijab11nmjijib

13、a例例 2 2個(gè)化肥廠供應(yīng)個(gè)化肥廠供應(yīng)3 3個(gè)地區(qū)的化肥，試決定運(yùn)費(fèi)最小的調(diào)運(yùn)方案。個(gè)地區(qū)的化肥，試決定運(yùn)費(fèi)最小的調(diào)運(yùn)方案。解：增加虛設(shè)的銷地解：增加虛設(shè)的銷地B4B4，銷量為，銷量為1010，構(gòu)造產(chǎn)銷平衡的運(yùn)輸表。，構(gòu)造產(chǎn)銷平衡的運(yùn)輸表。運(yùn)輸問題運(yùn)輸問題初始基可行解及其檢驗(yàn)數(shù)：初始基可行解及其檢驗(yàn)數(shù)：迭代求新基本可行解：迭代求新基本可行解：運(yùn)輸問題運(yùn)輸問題 n n項(xiàng)任務(wù)，恰好有項(xiàng)任務(wù)，恰好有n n個(gè)人承擔(dān)，由于每個(gè)人的專長不同，完個(gè)人承擔(dān)，由于每個(gè)人的專長不同，完成各工作的效率不同，于是產(chǎn)生了應(yīng)指派哪個(gè)人去完成哪項(xiàng)，成各工作的效率不同，于是產(chǎn)生了應(yīng)指派哪個(gè)人去完成哪項(xiàng)，使得完成使得完成n n

14、項(xiàng)任務(wù)的總效率最高的問題，這類問題稱為指派問項(xiàng)任務(wù)的總效率最高的問題，這類問題稱為指派問題。題。 例例 有一份說明書，需要譯成英、日、德、俄四種文字，現(xiàn)有有一份說明書，需要譯成英、日、德、俄四種文字，現(xiàn)有甲乙丙丁四個(gè)人，他們將說明書譯成不同文字所需要的時(shí)間甲乙丙丁四個(gè)人，他們將說明書譯成不同文字所需要的時(shí)間如下表所示，問應(yīng)指派哪個(gè)人完成哪項(xiàng)工作，耗用的總時(shí)間如下表所示，問應(yīng)指派哪個(gè)人完成哪項(xiàng)工作，耗用的總時(shí)間最少？最少？指派問題指派問題 一般地，有一般地，有n n項(xiàng)任務(wù)、項(xiàng)任務(wù)、n n個(gè)完成人，第個(gè)完成人，第i i人完成第人完成第j j項(xiàng)任務(wù)的項(xiàng)任務(wù)的代價(jià)為代價(jià)為c cijij( (i,j=1

15、,2,ni,j=1,2,n),),為了求得總代價(jià)最小的指派方案，為了求得總代價(jià)最小的指派方案，引入引入0-10-1型變量型變量x xij ij , ,令令 數(shù)學(xué)模型為數(shù)學(xué)模型為 注：指派問題是注：指派問題是0-10-1整數(shù)規(guī)劃的特例，也是運(yùn)輸問題的特例，整數(shù)規(guī)劃的特例，也是運(yùn)輸問題的特例，其產(chǎn)地和銷地?cái)?shù)均為其產(chǎn)地和銷地?cái)?shù)均為1 1，各產(chǎn)地產(chǎn)量和各銷地銷量均為，各產(chǎn)地產(chǎn)量和各銷地銷量均為1.1.指派問題指派問題 指派問題的求解方法：匈牙利法。指派問題的求解方法：匈牙利法。 匈牙利法基于下面的事實(shí)：如果系數(shù)矩陣的所有元素滿足：匈牙利法基于下面的事實(shí)：如果系數(shù)矩陣的所有元素滿足：c cijij=0=

16、0，而其中有，而其中有n n個(gè)位于不同行不同列的一組個(gè)位于不同行不同列的一組0 0元素，則只要元素，則只要令對(duì)應(yīng)于這些令對(duì)應(yīng)于這些0 0元素位置的元素位置的x xijij=1=1，其余的，其余的x xijij=0=0，就得到最優(yōu)，就得到最優(yōu)解。解。 如如 則則 指派問題指派問題求解上例：求解上例： 行變換得行變換得 列變換得列變換得 畫出最少覆蓋畫出最少覆蓋0 0元素的直線，元素的直線，r=4=r=4=矩陣階數(shù)，矩陣階數(shù)， 則可以找到最優(yōu)解則可以找到最優(yōu)解, ,所需最少時(shí)間所需最少時(shí)間=4+4+9+11=28=4+4+9+11=28 甲甲- -俄語俄語 從而得到最優(yōu)指派：乙從而得到最優(yōu)指派：乙

17、- -日語日語 丙丙- -英語英語 丁丁- -德語德語 指派問題指派問題例例 分配甲、乙、丙、丁四個(gè)人去完成分配甲、乙、丙、丁四個(gè)人去完成A A、B B、C C、D D、E E五項(xiàng)任務(wù)，五項(xiàng)任務(wù)，每人完成各項(xiàng)任務(wù)的時(shí)間如下表所示，由于任務(wù)重，人手少，每人完成各項(xiàng)任務(wù)的時(shí)間如下表所示，由于任務(wù)重，人手少，考慮以下兩種情況下的最優(yōu)分配方案，使得完成任務(wù)的總時(shí)考慮以下兩種情況下的最優(yōu)分配方案，使得完成任務(wù)的總時(shí)間最少。間最少。 (1)(1)任務(wù)任務(wù)E E必須完成，其他必須完成，其他4 4項(xiàng)任務(wù)可選項(xiàng)任務(wù)可選3 3項(xiàng)完成，但甲不能做項(xiàng)完成，但甲不能做A A項(xiàng)工作；項(xiàng)工作；(2)(2)其中有一人完成其中

18、有一人完成2 2項(xiàng)，其他人每人完成項(xiàng)，其他人每人完成1 1項(xiàng)。項(xiàng)。解：這是一人數(shù)與任務(wù)數(shù)不等的指派問題，若用匈牙利法求解，解：這是一人數(shù)與任務(wù)數(shù)不等的指派問題，若用匈牙利法求解，需作以下處理。需作以下處理。指派問題指派問題(1)(1)由于任務(wù)數(shù)大于人數(shù)，所以需要有一個(gè)虛擬的人，設(shè)為戊。由于任務(wù)數(shù)大于人數(shù)，所以需要有一個(gè)虛擬的人，設(shè)為戊。因?yàn)楣ぷ饕驗(yàn)楣ぷ鱁 E必須完成，故設(shè)戊完成必須完成，故設(shè)戊完成E E的時(shí)間為的時(shí)間為M(MM(M為非常大的正為非常大的正數(shù)數(shù)) )，即戊不能做工作，即戊不能做工作E E，其余的假想時(shí)間為，其余的假想時(shí)間為0 0，建立的效率矩，建立的效率矩陣為：陣為： 采用匈牙利

19、解法求解過程如下：采用匈牙利解法求解過程如下： 指派問題指派問題(1)(1)由于由于r=4r=4矩陣階數(shù)矩陣階數(shù)=5=5，需要調(diào)整，需要調(diào)整0 0元素的分布。元素的分布。 從該矩陣可看出，從該矩陣可看出，r=5=r=5=矩陣階數(shù)，因此能找到最優(yōu)指派方案。矩陣階數(shù)，因此能找到最優(yōu)指派方案。 甲甲-B-B 乙乙-D-D 丙丙-E-E 丁丁-A-A 戊戊-C-C（戊（戊 為虛擬人，即任務(wù)為虛擬人，即任務(wù)C C無人完成）無人完成） 最少的耗時(shí)數(shù)最少的耗時(shí)數(shù) z=29+20+32+24=105 z=29+20+32+24=105 指派問題指派問題(2)(2)思路：思路：方案方案1 1：甲，【甲】，乙，丙

20、，?。杭祝炯住?，乙，丙，丁方案方案2 2：甲，乙，【乙】，丙，?。杭祝?，【乙】，丙，丁方案方案3 3：甲，乙，丙，【丙】，?。杭?，乙，丙，【丙】，丁方案方案4 4：甲，乙，丙，丁，【丁】：甲，乙，丙，丁，【丁】方案方案5 5：甲，【甲】，乙，【乙】，丙，【丙】，丁，【丁】，：甲，【甲】，乙，【乙】，丙，【丙】，丁，【丁】，工作工作A A，B B，C C，D D，E E，虛擬工作，虛擬工作F F，G G，H H。這些方案較煩瑣，采用以下思路更為簡便。這些方案較煩瑣，采用以下思路更為簡便。設(shè)有虛擬人戊，他集五人的優(yōu)勢(shì)為一身，即戊的費(fèi)用是每人的設(shè)有虛擬人戊，他集五人的優(yōu)勢(shì)為一身，即戊的費(fèi)用是每人

21、的最低，戊所做的工作即為此項(xiàng)工作的費(fèi)用最低者的工作，效最低，戊所做的工作即為此項(xiàng)工作的費(fèi)用最低者的工作，效率矩陣分配表為：率矩陣分配表為：指派問題指派問題 采用匈牙利解法求解：采用匈牙利解法求解： 對(duì)對(duì)C C3 3做做0 0元素的最小直線覆蓋，得元素的最小直線覆蓋，得r=5=nr=5=n。結(jié)果為。結(jié)果為 甲甲-B -B 乙乙-D -D 丙丙-E -E 丁丁-A -A 戊戊-C-C 但戊為虛擬人，不能真做，它做但戊為虛擬人，不能真做，它做C C工作是借乙工作是借乙( (此列最小時(shí)數(shù)此列最小時(shí)數(shù)2626是是C C所創(chuàng)業(yè)所創(chuàng)業(yè)績績) )的優(yōu)勢(shì)，應(yīng)由乙來做，即乙做兩件工作：的優(yōu)勢(shì)，應(yīng)由乙來做，即乙做兩

22、件工作：D D、C C。 指派問題指派問題例例 最大收益的最優(yōu)分配問題：有最大收益的最優(yōu)分配問題：有5 5名工人完成名工人完成5 5項(xiàng)不同的任務(wù)收項(xiàng)不同的任務(wù)收 益如表所示：益如表所示： 求使總收益達(dá)到最高的任務(wù)分配方案。求使總收益達(dá)到最高的任務(wù)分配方案。 解：這是一個(gè)尋求總收益為最大值的極大化問題，需要轉(zhuǎn)化為解：這是一個(gè)尋求總收益為最大值的極大化問題，需要轉(zhuǎn)化為極小化問題才能用匈牙利解法。極小化問題才能用匈牙利解法。 收益矩陣收益矩陣B=B=（b bijij），設(shè)），設(shè)b=maxbb=maxbijij ，令，令c cijij=b-b=b-bijij ，C=C=（c cijij），），以以C

23、C為效率矩陣的極小化問題即是原最大收益的極大化問題轉(zhuǎn)為效率矩陣的極小化問題即是原最大收益的極大化問題轉(zhuǎn)化而來?；鴣?。 指派問題指派問題b=maxbb=maxbijij=19=19，令，令c cijij=19-b=19-bijij ，C=C=（c cijij），），繼續(xù)對(duì)繼續(xù)對(duì)C C矩陣采用匈牙利法求解，得到矩陣采用匈牙利法求解，得到C C的最優(yōu)分配方案為的最優(yōu)分配方案為即即 甲甲-D -D 乙乙-B -B 丙丙-E -E 丁丁-A -A 戊戊-C -C ，求得的最大總收益為，求得的最大總收益為74.74.指派問題指派問題237184566134105275934682網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)優(yōu)化最短路徑

24、問題：有一批貨物要從節(jié)點(diǎn)最短路徑問題：有一批貨物要從節(jié)點(diǎn)1運(yùn)送到節(jié)點(diǎn)運(yùn)送到節(jié)點(diǎn)8，這兩點(diǎn)間的，這兩點(diǎn)間的通路如下圖，每條弧旁邊的數(shù)字表明該弧的長度?？偮窂皆蕉?，通路如下圖，每條弧旁邊的數(shù)字表明該弧的長度?？偮窂皆蕉蹋\(yùn)費(fèi)越低，為節(jié)省運(yùn)輸費(fèi)用，應(yīng)該選擇怎樣的運(yùn)輸路線？運(yùn)費(fèi)越低，為節(jié)省運(yùn)輸費(fèi)用，應(yīng)該選擇怎樣的運(yùn)輸路線？求從求從1 1到到8 8的最短路徑。的最短路徑。237184566134105275934682X=1, w1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4, w4=1w1=0w1=023718456613410527593468

25、2X=1,4min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4, w2=2w1=0w4=1w2=2237184566134105275934682X=1,2,4min c16,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6, w6=3w2=2w4=1w1=0w6=3237184566134105275934682X=1,2,4,6min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7,

26、w7=3w2=2w4=1w1=0w6=3w7=3237184566134105275934682X=1,2,4,6,7min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7, w5=6w2=2w4=1w1=0w6=3w7=3w5=6237184566134105275934682X=1,2,4,6,7min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7, w3=8w2=2w4=1w1=0w6=3w7=3w5=6w3=82371

27、84566134105275934682X=1,2,3,4,6,7min c38,c58,c78=min 8+6,6+4,3+8=min 14,10,11=10X=1,2,3,4,5,6,7,8, w8=10w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10237184566134105275934682X=1,2,3,4,6,7,81到10的最短路徑為1，4，7，5，8，長度為10。w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)優(yōu)化最大流問題：給出一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之最大流問題：給出一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量

28、，在不超過每條弧的容量的前提下，求出從發(fā)點(diǎn)到收為容量，在不超過每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。點(diǎn)的最大流量。2354671ffu25=6u42=2u45=4u23=3u13=7u34=4u46=3u36=1u65=7u57=9u67=8u12=8邊的容量和流量：容量邊的容量和流量：容量u uijij，流量，流量x xijij可行流：可行流：滿足以下條件的流稱為可行流：滿足以下條件的流稱為可行流：1 1、每一個(gè)節(jié)點(diǎn)流量平衡、每一個(gè)節(jié)點(diǎn)流量平衡2 2、0 x0 xijij u uijij如果如果x xijij=u=uijij，邊從，邊從i i到到j(luò) j的方向是飽和的；的方向是飽和

29、的；如果如果x xijiju00，邊從，邊從j j到到i i的方向是不飽和的的方向是不飽和的網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)優(yōu)化21xij=0uij=521xij=5uij=5（2 2，1 1）是不飽和的）是不飽和的間隙為間隙為 1212=x=x1212=5=5給出一個(gè)初始的可行流給出一個(gè)初始的可行流x xijij=0=02354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)優(yōu)化2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u

30、=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0找到所有的不飽和邊，以及各邊可以調(diào)整流量的方向找到所有的不飽和邊，以及各邊可以調(diào)整流量的方向2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0=3=1=8=8x=0找到一條從找到一條從1 1到到7 7的不飽和鏈的不飽和鏈鏈的間隙為：鏈的間隙為： = min8,3,1,8=1 = min8,3,1,8=1調(diào)整鏈的流量：調(diào)整鏈的流量：xij=xij+ xij=xi

31、j+ 2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=1x=1x=1x=1調(diào)整流量，調(diào)整流量，f=1f=1。繼續(xù)求出網(wǎng)絡(luò)的不飽和邊。繼續(xù)求出網(wǎng)絡(luò)的不飽和邊2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=1x=1x=1x=1=1=6=9=7求出一條從求出一條從1 1到到7 7的不飽和鏈的不飽和鏈 = =min 7,1,6,9=1, min 7,1,6,9=1, 調(diào)

32、整流量調(diào)整流量 xij=xij+1xij=xij+1, f=f+1=2, f=f+1=22354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0 x=0 x=1x=0 x=0 x=0 x=1x=1x=1x=1x=0調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0 x=0 x=1x=0 x=0 x=0 x=1x=1x=1x=1x=0=5=8=7求出一條從求出一條從1到到7的不飽和鏈的不飽和鏈 = =min 7,5,8=

33、5, min 7,5,8=5, 調(diào)整流量調(diào)整流量 xij=xij+5xij=xij+5, f=f+5=2+5=7, f=f+5=2+5=72354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=0 x=1x=0 x=0 x=0 x=6x=1x=1x=6x=0調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊2354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=0 x=1x=0 x=0 x=0 x=6x=1x=1x=6x=0=4=4=3=6求出一條從求出一條從1

34、 1到到7 7的不飽和鏈的不飽和鏈 = =min 6,7,4,3=3, min 6,7,4,3=3, 調(diào)整流量調(diào)整流量 xij=xij+3xij=xij+3, , f=f+3=7+3=10f=f+3=7+3=102354671f=10f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=3x=4x=3x=0 x=0 x=9x=1x=1x=6x=0調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊2354671f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=3x=4x=3x=0 x=0 x

35、=9x=1x=1x=6x=0f=10=1=3=7=3求出一條從求出一條從1 1到到7 7的不飽和鏈的不飽和鏈 = =min 3,1,3,7=1, min 3,1,3,7=1, 調(diào)整流量調(diào)整流量 xij=xij+1xij=xij+1, , f=f+1=10+1=11f=f+1=10+1=112354671f=11f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=4x=5x=3x=1x=0 x=9x=2x=1x=6x=0調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊已找不到一條從已找不到一條從1 1到到7 7的不飽和鏈，從的不飽和鏈

36、，從1 1開始可以到達(dá)的節(jié)點(diǎn)為開始可以到達(dá)的節(jié)點(diǎn)為1 1，2 2，3 32354671f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=4x=5x=3x=1x=0 x=9x=2x=1x=6x=0f=11已求得最大流已求得最大流最大流f=11，最小割集為（2,5）（3,4）（3,5）u25+u34+u35=6+4+1=11最短路問題：最短路問題：給定一個(gè)運(yùn)輸網(wǎng)絡(luò)，兩點(diǎn)之間連線上的數(shù)字表示兩點(diǎn)之間的距離，試求一條給定一個(gè)運(yùn)輸網(wǎng)絡(luò)，兩點(diǎn)之間連線上的數(shù)字表示兩點(diǎn)之間的距離，試求一條從從A A到到B B的運(yùn)輸路線，使總距離最短。的運(yùn)輸路線，使總距離最短?？?/p>

37、將問題分為四個(gè)階段：第一階段，從可將問題分為四個(gè)階段：第一階段，從A A到到B B；第二階段，從；第二階段，從B B到到C C；第三階段，；第三階段，從從C C到到D D；第四階段，從；第四階段，從D D到到E E。完全枚舉：完全枚舉：3 3* *3 3* *2 2* *1=241=24條。條。最優(yōu)解：最優(yōu)解：A AB3 C2 D2 E動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃階段：階段：將所給問題的過程，按時(shí)間或空間特征分解成相互聯(lián)系的階段，將所給問題的過程，按時(shí)間或空間特征分解成相互聯(lián)系的階段，以便按次序求每階段的解以便按次序求每階段的解 k k描述階段的變量描述階段的變量狀態(tài)：狀態(tài)：表示每個(gè)階段表示每個(gè)階段開始時(shí)

38、開始時(shí)所處的自然狀況或條件，描述了研究問題的所處的自然狀況或條件，描述了研究問題的狀況。狀況。 s sk k狀態(tài)變量狀態(tài)變量 S Sk k狀態(tài)集合狀態(tài)集合 S S1 1=A,=A,S S2 2=B=B1 1,B,B2 2,B,B3 3,S S3 3=C=C1 1,C,C2 2,C,C3 3, S S4 4=D=D1 1,D,D2 2 動(dòng)態(tài)規(guī)劃中狀態(tài)的性質(zhì)：動(dòng)態(tài)規(guī)劃中狀態(tài)的性質(zhì)：無后效性無后效性，即如果某個(gè)階段狀態(tài)給定之后，則，即如果某個(gè)階段狀態(tài)給定之后，則在這階段以后過程的發(fā)展不受這階段以前各階段狀態(tài)的影響。在這階段以后過程的發(fā)展不受這階段以前各階段狀態(tài)的影響。決策：決策：指在某階段對(duì)可供選擇

39、狀態(tài)的選擇，描述的變量稱為決策變量。指在某階段對(duì)可供選擇狀態(tài)的選擇，描述的變量稱為決策變量。 d dk k( ( s sk k ) )決策變量決策變量 D Dk k( ( s sk k ) )允許決策集合允許決策集合 D D2 2(B(B1 1)=C)=C1 1,C,C2 2,C,C3 3 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 全過程策略：全過程策略：由所有各階段組成的決策函數(shù)序列由所有各階段組成的決策函數(shù)序列, ,簡稱簡稱策略策略。記為：記為： P P1,n1,n(s(s1 1) ) 或或P P1,n1,n(s(s1 1)=d)=d1 1(s(s1 1), d), d2 2(s(s2 2), d), dn n(

40、s(sn n) k k子過程策略子過程策略( (后部子策略后部子策略) )：由由k k階段開始到最后階段結(jié)束，階段開始到最后階段結(jié)束，組成的決策函數(shù)序列。組成的決策函數(shù)序列。 P Pk,nk,n(s(sk k)=d)=dk k(s(sk k), d), dk+1k+1(s(sk+1k+1), d), dn n(s(sn n) 最優(yōu)策略：最優(yōu)策略：使整個(gè)問題達(dá)到最優(yōu)效果的策略。使整個(gè)問題達(dá)到最優(yōu)效果的策略。 P P* *1,n1,n(A)=(A)=B3, ,C2, ,D2 , ,E A AB3 C2 D2 E 允許策略集：允許策略集：可供選擇策略的范圍，用可供選擇策略的范圍，用P P表示。表示。

41、 動(dòng)態(tài)規(guī)劃方法就是要從允許策略集動(dòng)態(tài)規(guī)劃方法就是要從允許策略集P P中找出最優(yōu)策略中找出最優(yōu)策略 P P* *k,nk,n動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： 本階段狀態(tài)與上一階段狀態(tài)和上一階段決策的關(guān)系，用狀態(tài)本階段狀態(tài)與上一階段狀態(tài)和上一階段決策的關(guān)系，用狀態(tài)轉(zhuǎn)移方程來表示。轉(zhuǎn)移方程來表示。 s sk+1k+1=T=Tk k(s(sk k,d,dk k) ) 該方程描述了由第該方程描述了由第k k階段到第階段到第k+1k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，又稱階段的狀態(tài)轉(zhuǎn)移規(guī)律，又稱為狀態(tài)轉(zhuǎn)移函數(shù)。為狀態(tài)轉(zhuǎn)移函數(shù)。 s sk+1k+1=d=dk k (s(sk k) ) 階段指標(biāo)：階段指標(biāo)：

42、衡量某階段決策效益優(yōu)劣的策略指標(biāo)，如距離，衡量某階段決策效益優(yōu)劣的策略指標(biāo)，如距離，成本，利潤等。成本，利潤等。 v vk k (s (sk k,d,dk k) ) 指標(biāo)函數(shù)：指標(biāo)函數(shù)：衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)。衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)。 V Vk,nk,n (s (sk k,P,Pk,nk,n)= V)= Vk,nk,n (s (sk k,d,dk k,s,sk+1k+1,s,sn+1 n+1 ) )動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 常見指標(biāo)函數(shù)形式常見指標(biāo)函數(shù)形式( (分離性，遞推關(guān)系分離性，遞推關(guān)系) ) V Vk,nk,n (s (sk k,P,Pk,nk,n)= V)= Vk,nk,n (s

43、 (sk k,d,dk k,s,sk+1k+1,s,sn+1 n+1 ) ) = V = Vk k (s (sk k,d,dk k )+ V)+ Vk+1k+1 (s (sk+1k+1, P, Pk,nk,n) ) V Vk,nk,n (s (sk k,P,Pk,nk,n)= V)= Vk,nk,n (s (sk k,d,dk k,s,sk+1k+1,s,sn+1 n+1 ) ) = V = Vk k (s (sk k,d,dk k ) )* * V Vk+1k+1 (s (sk+1k+1, P, Pk,nk,n) ) 最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù): :指標(biāo)函數(shù)的最優(yōu)值，指標(biāo)函數(shù)的最優(yōu)值，f fk

44、 k(s(sk k) )表示從第表示從第k k階段狀態(tài)階段狀態(tài)s sk k開始開始采用最優(yōu)策略采用最優(yōu)策略P P* *k,nk,n到過程終止時(shí)的到過程終止時(shí)的最佳效益值。最佳效益值。 f fk k(s(sk k)=opt V)=opt Vk,nk,n (s (sk k,d,dk k,s,sk+1k+1,s,sn+1 n+1 ) ) f f1 1(s(s1 1) )表示從第表示從第1 1階段狀態(tài)階段狀態(tài)s s1 1采用最優(yōu)策略采用最優(yōu)策略P P* *1,n1,n到過到過程終止時(shí)的最佳效益值。程終止時(shí)的最佳效益值。動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃的基本思想：動(dòng)態(tài)規(guī)劃的基本思想： 1. 1. 多階段決策過

45、程劃分階段，恰當(dāng)?shù)倪x取狀態(tài)變量、決策多階段決策過程劃分階段，恰當(dāng)?shù)倪x取狀態(tài)變量、決策變量和定義最優(yōu)指標(biāo)函數(shù)，從而將問題化為一族同類型的子變量和定義最優(yōu)指標(biāo)函數(shù)，從而將問題化為一族同類型的子問題逐個(gè)求解。問題逐個(gè)求解。 2. 2. 求解時(shí)從邊界條件開始，逆（或順）過程行進(jìn)方向，逐求解時(shí)從邊界條件開始，逆（或順）過程行進(jìn)方向，逐段遞推尋優(yōu)。段遞推尋優(yōu)。 3. 3. 既將當(dāng)前一段與未來各段分開，又將當(dāng)前效益與未來效既將當(dāng)前一段與未來各段分開，又將當(dāng)前效益與未來效益結(jié)合起來考慮的一種最優(yōu)化方法。益結(jié)合起來考慮的一種最優(yōu)化方法。 如何建立動(dòng)態(tài)規(guī)劃模型：如何建立動(dòng)態(tài)規(guī)劃模型： 1. 1. 分析識(shí)別問題的多

46、階段特性，按時(shí)間或空間的先后順序適分析識(shí)別問題的多階段特性，按時(shí)間或空間的先后順序適當(dāng)?shù)貏澐之?dāng)?shù)貏澐譂M足遞推關(guān)系滿足遞推關(guān)系的若干階段。的若干階段。 2. 2. 確定狀態(tài)變量，滿足確定狀態(tài)變量，滿足可知性可知性和和無后效性無后效性。一般為累計(jì)量和。一般為累計(jì)量和隨遞推過程變化的量。隨遞推過程變化的量。 3.3.找到狀態(tài)轉(zhuǎn)移方程。找到狀態(tài)轉(zhuǎn)移方程。 4.4.正確確定基本方程。正確確定基本方程。 基礎(chǔ)：基礎(chǔ)：最優(yōu)化定理最優(yōu)化定理 作為整個(gè)過程的最優(yōu)策略具有如下性質(zhì)：不管在此最優(yōu)策略作為整個(gè)過程的最優(yōu)策略具有如下性質(zhì)：不管在此最優(yōu)策略上的某個(gè)狀態(tài)以前的狀態(tài)和決策如何，對(duì)該狀態(tài)而言，以后上的某個(gè)狀態(tài)以

47、前的狀態(tài)和決策如何，對(duì)該狀態(tài)而言，以后所有的決策必定構(gòu)成最優(yōu)子策略。所有的決策必定構(gòu)成最優(yōu)子策略。 對(duì)最短路問題而言對(duì)最短路問題而言, ,從最短路上任一點(diǎn)到終點(diǎn)的部分道路從最短路上任一點(diǎn)到終點(diǎn)的部分道路（最短路上的子路）也一定是從該點(diǎn)到終點(diǎn)的最短路。（最短路上的子路）也一定是從該點(diǎn)到終點(diǎn)的最短路。動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃從最后一段開始計(jì)算，由后向前逐步推移至從最后一段開始計(jì)算，由后向前逐步推移至A A點(diǎn)。點(diǎn)。第四階段，由第四階段，由D D1 1到到E E只有一條線路，其長度只有一條線路，其長度f4(D1)=3，同理同理f4(D2)=4；第三階段，由第三階段，由C Cj j到到D Di i均有兩種選擇，

48、即均有兩種選擇，即第二階段，由第二階段，由B Bj j到到C Ci i均有三種選擇，即均有三種選擇，即動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃*114131112422141322*2242*31413313242()33()minmin6,()44()63()minmin7,()34()33()minmin6,()34C DfDf CDC DfDC DfDf CDC DfDC DfDf CDC DfD決策點(diǎn)為決策點(diǎn)為決策點(diǎn)為第一階段，由第一階段，由A A到到B B，有三種選擇，即，有三種選擇，即f f1 1(A)=12(A)=12，說明從，說明從A A到到E E的最短距離為的最短距離為1212，最短路線的確定可，最

49、短路線的確定可按計(jì)算順序反推而得，即按計(jì)算順序反推而得，即A-BA-B3 3-C-C2 2-D-D2 2-E-E1131*12322121333*2131*22322212233331313376()()(B )minmin11,47()66()36()()minmin9,27()46()()minBCf CBCf CfCBCf CB Cf CB Cf CfBCCB Cf CB Cf CBfB決策點(diǎn)為決策點(diǎn)為或者*32322333366()min9,27()56Cf CCB Cf C決策點(diǎn)為動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃12122213*3232 11()49()( )minmin12,()39ABfBAB

50、fBf ABABfB決策點(diǎn)為一個(gè)著名的命題：一個(gè)串村走戶的賣貨郎，他從某個(gè)村莊出一個(gè)著名的命題：一個(gè)串村走戶的賣貨郎，他從某個(gè)村莊出發(fā)，通過若干個(gè)村莊一次且僅一次，最后仍回到原出發(fā)的村莊發(fā)，通過若干個(gè)村莊一次且僅一次，最后仍回到原出發(fā)的村莊，問：應(yīng)如何選擇行走路線，能使得總的行程最短。，問：應(yīng)如何選擇行走路線，能使得總的行程最短。設(shè)有設(shè)有n個(gè)城市，個(gè)城市，1,2,n。Dij表示從表示從i城到城到j(luò)城的距離。城的距離。規(guī)定推銷員是從城市規(guī)定推銷員是從城市1開始的，設(shè)推銷員走到開始的，設(shè)推銷員走到i城，記城，記Ni2,3,i-1,i+1,n 表示由表示由1城到城到i城的中間城市集合。城的中間城市集

51、合。S表示到達(dá)表示到達(dá)i城中途所經(jīng)過的城市的集合，則有城中途所經(jīng)過的城市的集合，則有S Ni1）選?。┻x取（i,S）作為狀態(tài)變量）作為狀態(tài)變量，表示推銷員從城市，表示推銷員從城市1開始走到開始走到i城，經(jīng)過若干個(gè)城市，構(gòu)成集合城，經(jīng)過若干個(gè)城市，構(gòu)成集合S。2）最優(yōu)值函數(shù)最優(yōu)值函數(shù)fk(i,S)為從城市為從城市1開始經(jīng)過開始經(jīng)過k個(gè)中間城市的個(gè)中間城市的S集集到達(dá)到達(dá)i城的最短路線的距離。城的最短路線的距離。貨郎擔(dān)問題貨郎擔(dān)問題（TSP問題問題traveling salesperson problem）3）遞推關(guān)系式：遞推關(guān)系式：fk(i,S)=min fk-1(j,Sj)+Dji(k=1,2

52、, ,n-1. i=2,3,n. S Ni)邊界條件：邊界條件：f0(i,)= D1i4） Pk(i,S)為最優(yōu)決策函數(shù)為最優(yōu)決策函數(shù)，表示從1城開始經(jīng)k個(gè)中間城市到i城的最短路線上緊挨著i城前面的那個(gè)城市。距離距離1城城2城城3城城4城城1城城08562城城60853城城79054城城9780例：當(dāng)推銷員從例：當(dāng)推銷員從1城出發(fā)，經(jīng)過每個(gè)城市一次且僅城出發(fā)，經(jīng)過每個(gè)城市一次且僅一次，最后回到一次，最后回到1城，問按怎樣的路線走，使總的城，問按怎樣的路線走，使總的行程距離最短。（四個(gè)城市，其距離矩陣如下表）行程距離最短。（四個(gè)城市，其距離矩陣如下表）5）由邊界條件可知： f0(i,)= D1i

53、f0(2,)= D128，f0(3,)= D135，f0(4,)= D146當(dāng)當(dāng)k=1時(shí)時(shí)，即從1城開始，中間經(jīng)過一個(gè)城市到達(dá)i城的最短距離是：f1(2,3)= f0(3,)+ D325+9=14f1(2,4)= f0(4,)+ D426+7=13f1(3,2)= f0(2,)+ D238+8=16f1(3,4)= f0(4,)+ D436+8=14f1(4,2)= f0(2,)+ D248+5=13f1(4,3)= f0(3,)+ D345+5=101i1i距離距離1城 城2城 城3城 城4城 城1城 城08562城 城60853城 城79054城 城9780當(dāng)當(dāng)k=2時(shí)，時(shí)，即從1城開始，

54、中間經(jīng)過兩個(gè)城市到達(dá)i城的最短距離是：f2(2,3,4)=min f1(3, 4)+D32 f1(4, 3)+D42 = m i n 1 4 + 9 , 1 0 + 7 = 1 7 P2(2,3,4)=41i距離距離1城 城2城 城3城 城4城 城1城 城08562城 城60853城 城79054城 城9780f2(3,2,4)=min f1(2, 4)+D23 f1(4, 2)+D43 =min13+8 ,13+8=21 P2(3,2,4)=2或或4f2(4,3,2)=min f1(3, 2)+D34 f1(2, 3)+D24 =min16+5 ,14+5=19 P2(4,3,2)=2f1(

55、3,4)= 14f1(4,3)=10當(dāng)當(dāng)k=3時(shí)，時(shí)，即從1城開始，中間經(jīng)過三個(gè)城市到達(dá)1城的最短距離是：f3(1，2,3,4)=min f2(2, 3,4)+D21 f2(3, 4,2)+D31 f2(4, 3,2)+D41=min17+6 , 21+7, 19+9=23P3(1,2,3,4)=21由此可知，推銷員的最短行走路線為13421，最短總距離為23。 某種工作系統(tǒng)有幾個(gè)部件串聯(lián)組成，稱部件正常工某種工作系統(tǒng)有幾個(gè)部件串聯(lián)組成，稱部件正常工作的概率為該部件的可靠性，稱整個(gè)工作系統(tǒng)為正作的概率為該部件的可靠性，稱整個(gè)工作系統(tǒng)為正常工作的概率為系統(tǒng)的可靠性。常工作的概率為系統(tǒng)的可靠性。

56、在這種串聯(lián)系統(tǒng)中，只要有一個(gè)部件失靈，整個(gè)系在這種串聯(lián)系統(tǒng)中，只要有一個(gè)部件失靈，整個(gè)系統(tǒng)就不能正常工作。統(tǒng)就不能正常工作。 為了提高串聯(lián)系統(tǒng)工作的可靠性，可以給各個(gè)部件為了提高串聯(lián)系統(tǒng)工作的可靠性，可以給各個(gè)部件設(shè)置備用件，并設(shè)計(jì)備用件自動(dòng)投入裝置，一旦部設(shè)置備用件，并設(shè)計(jì)備用件自動(dòng)投入裝置，一旦部件損壞，則備用部件自動(dòng)投入運(yùn)行。顯然，備用件件損壞，則備用部件自動(dòng)投入運(yùn)行。顯然，備用件越多，部件工作的可靠性就越大。從而整個(gè)系統(tǒng)工越多，部件工作的可靠性就越大。從而整個(gè)系統(tǒng)工作可靠性就越大。作可靠性就越大。部件部件1部件部件2部件部件n復(fù)合系統(tǒng)工作可靠性問題復(fù)合系統(tǒng)工作可靠性問題 備用件越多，整個(gè)系統(tǒng)工作可靠性就越大。備用件越多，整個(gè)系統(tǒng)工作可靠性就越大。 但是備用件多