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

數(shù)學(xué)建模運(yùn)籌模型第一頁(yè)，共八十二頁(yè)，編輯于2023年，星期三線性規(guī)劃運(yùn)輸問(wèn)題指派問(wèn)題網(wǎng)絡(luò)優(yōu)化動(dòng)態(tài)規(guī)劃目錄

第二頁(yè)，共八十二頁(yè)，編輯于2023年，星期三例某工廠在計(jì)劃期內(nèi)要安排Ⅰ，Ⅱ兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A，B兩種原材料的消耗、資源的限制，如下表。問(wèn)題：工廠應(yīng)分別生產(chǎn)多少單位Ⅰ，Ⅱ產(chǎn)品才能使工廠獲利最多？

線性規(guī)劃第三頁(yè)，共八十二頁(yè)，編輯于2023年，星期三例下料問(wèn)題某工廠要做100套鋼架，每套用長(zhǎng)為2.9m，2.1m，1.5m的圓鋼各一根，已知原料每根長(zhǎng)7.4m。應(yīng)如何下料，可使所用原料最?。拷猓汗部稍O(shè)計(jì)下列5種下料方案線性規(guī)劃第四頁(yè)，共八十二頁(yè)，編輯于2023年，星期三第五頁(yè)，共八十二頁(yè)，編輯于2023年，星期三建模步驟：(1)確定決策變量：我們需要作出決策或者選擇的量，一般情況下，題目問(wèn)什么就設(shè)什么為決策變量。(2)找出約束條件：即決策變量受到的所有的約束。(3)寫(xiě)出目標(biāo)函數(shù)：即問(wèn)題所要達(dá)到的目標(biāo)，并明確是求max還是min。線性規(guī)劃第六頁(yè)，共八十二頁(yè)，編輯于2023年，星期三例混合配料問(wèn)題某糖果廠用原料1、2、3加工三種不同牌號(hào)的糖果甲、乙、丙。已知各種牌號(hào)糖果中原料1、2、3的含量、原料每月限用量、三種牌號(hào)糖果的加工費(fèi)及售價(jià)，如下表所示。該廠每月如何生產(chǎn)才能獲利最大？線性規(guī)劃第七頁(yè)，共八十二頁(yè)，編輯于2023年，星期三解：用i=1,2,3代表原料1,2,3,j=1,2,3代表糖果甲、乙、丙。Xij表示第j中產(chǎn)品中原料i的含量，則對(duì)于原料1：x11,x12,x13;對(duì)于原料2：x21,x22,x23;對(duì)于原料3：x31,x32,x33;對(duì)于甲：x11,x21,x31;對(duì)于乙：x12,x22,x32;對(duì)于丙：x13,x23,x33;目標(biāo)函數(shù)：利潤(rùn)最大，利潤(rùn)=收入-原料成本-加工費(fèi)約束條件：原料用量限制，含量限制線性規(guī)劃第八頁(yè)，共八十二頁(yè)，編輯于2023年，星期三線性規(guī)劃第九頁(yè)，共八十二頁(yè)，編輯于2023年，星期三求解方法：1.圖解法適合含有兩個(gè)決策變量的模型；

max z

=

x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8

x1≥0,x2≥0可行域目標(biāo)函數(shù)等值線最優(yōu)解64-860x1x2線性規(guī)劃第十頁(yè)，共八十二頁(yè)，編輯于2023年，星期三2.單純形法(人工變量法、對(duì)偶單純形法)軟件求解：lingo，lindo，MatlabMinf=0.4x1+1.5x2+x3+1.3x4S.t.0.3x1+3x2++1.5x4>=3200.5x1++2x3+x4>=2401.4x1++0.7x4>=420線性規(guī)劃第十一頁(yè)，共八十二頁(yè)，編輯于2023年，星期三

將某種物資從m個(gè)產(chǎn)地遇到n個(gè)銷地，每個(gè)產(chǎn)地都有一定的產(chǎn)量ai，i=1,2,……,m，每個(gè)銷地都對(duì)物資有一定的需求量bj,j=1,2,……,n。已知從第i個(gè)產(chǎn)地向第j個(gè)銷地運(yùn)送單位物資的運(yùn)價(jià)為cij，總產(chǎn)量等于總需求量()。如何調(diào)運(yùn)物資，才能使總運(yùn)費(fèi)最?。吭O(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，運(yùn)輸問(wèn)題第十二頁(yè)，共八十二頁(yè)，編輯于2023年，星期三

運(yùn)輸表：

(產(chǎn)銷平衡的運(yùn)輸問(wèn)題)求解方法：1.確定初始基本可行解（西北角法、最小元素法、vogal法）2.最優(yōu)性檢驗(yàn)；3.迭代求新的基本可行解。運(yùn)輸問(wèn)題第十三頁(yè)，共八十二頁(yè)，編輯于2023年，星期三例某食品公司下屬的三個(gè)食品廠A1、A2、A3生產(chǎn)食品，3個(gè)廠每月的生產(chǎn)能力分別為7噸、4噸、9噸，食品被運(yùn)到B1、B2、B3、B4四個(gè)銷售點(diǎn)，它們對(duì)方便食品的月需求量分別為3噸、6噸、5噸、6噸，運(yùn)輸表如下表，試制定最優(yōu)運(yùn)送方案。運(yùn)輸問(wèn)題第十四頁(yè)，共八十二頁(yè)，編輯于2023年，星期三解：1.確定初始基可行解最小元素法：運(yùn)輸問(wèn)題第十五頁(yè)，共八十二頁(yè)，編輯于2023年，星期三解：1.確定初始基可行解(最小元素法)初始基本可行解對(duì)應(yīng)的目標(biāo)函數(shù)值：f=3*4+10*3+1*3+2*1+4*6+5*3=86運(yùn)輸問(wèn)題第十六頁(yè)，共八十二頁(yè)，編輯于2023年，星期三解：2.最優(yōu)性檢驗(yàn)(1)位勢(shì)：

ui+vj=cij(i=1,2,……,m,j=1,2,……,n)其中cij為基本可行解中基變量對(duì)應(yīng)的單位運(yùn)價(jià)。注：m+n-1個(gè)方程，m+n個(gè)變量。(2)利用位勢(shì)求非基變量檢驗(yàn)數(shù)檢驗(yàn)數(shù)計(jì)算公式：

cij-ui-vj

(3)檢驗(yàn)數(shù)全都大于等于零時(shí)對(duì)應(yīng)的解為最優(yōu)解。運(yùn)輸問(wèn)題第十七頁(yè)，共八十二頁(yè)，編輯于2023年，星期三位勢(shì)：檢驗(yàn)數(shù)：運(yùn)輸問(wèn)題第十八頁(yè)，共八十二頁(yè)，編輯于2023年，星期三3.迭代求新基本可行解(1)負(fù)檢驗(yàn)數(shù)中最小者對(duì)應(yīng)的變量進(jìn)基；(2)在運(yùn)輸表中找一個(gè)包含進(jìn)基變量的閉回路，這個(gè)回路上其他頂點(diǎn)均為基變量。依次對(duì)閉回路的四個(gè)頂點(diǎn)標(biāo)號(hào)，將頂點(diǎn)分為奇點(diǎn)格和偶點(diǎn)格；(3)偶點(diǎn)格的最小值作為調(diào)整量，所有奇點(diǎn)格+調(diào)整量；偶點(diǎn)格-調(diào)整量，即一次迭代。(4)按位勢(shì)方程求新解對(duì)應(yīng)的位勢(shì)及檢驗(yàn)數(shù)，判別最優(yōu)性。運(yùn)輸問(wèn)題第十九頁(yè)，共八十二頁(yè)，編輯于2023年，星期三閉回路：

運(yùn)輸問(wèn)題第二十頁(yè)，共八十二頁(yè)，編輯于2023年，星期三迭代及新基本可行解的檢驗(yàn)數(shù)計(jì)算：

運(yùn)輸問(wèn)題第二十一頁(yè)，共八十二頁(yè)，編輯于2023年，星期三

產(chǎn)銷不平衡運(yùn)輸問(wèn)題：1.供大于求，引入虛擬銷售點(diǎn)，并假設(shè)它的需求量為供不應(yīng)求，引入虛擬的產(chǎn)地，并假設(shè)它的產(chǎn)量為由于虛擬銷地是不存在的，實(shí)際上這個(gè)差值是在產(chǎn)地貯存的，故從產(chǎn)地到虛擬銷地的單位運(yùn)價(jià)為0；同理，由于虛擬產(chǎn)地是不存在的，所以虛設(shè)的產(chǎn)地到各個(gè)銷地的單位運(yùn)價(jià)也為0.運(yùn)輸問(wèn)題第二十二頁(yè)，共八十二頁(yè)，編輯于2023年，星期三例2個(gè)化肥廠供應(yīng)3個(gè)地區(qū)的化肥，試決定運(yùn)費(fèi)最小的調(diào)運(yùn)方案。解：增加虛設(shè)的銷地B4，銷量為10，構(gòu)造產(chǎn)銷平衡的運(yùn)輸表。運(yùn)輸問(wèn)題第二十三頁(yè)，共八十二頁(yè)，編輯于2023年，星期三初始基可行解及其檢驗(yàn)數(shù)：迭代求新基本可行解：運(yùn)輸問(wèn)題第二十四頁(yè)，共八十二頁(yè)，編輯于2023年，星期三

n項(xiàng)任務(wù)，恰好有n個(gè)人承擔(dān)，由于每個(gè)人的專長(zhǎng)不同，完成各工作的效率不同，于是產(chǎn)生了應(yīng)指派哪個(gè)人去完成哪項(xiàng)，使得完成n項(xiàng)任務(wù)的總效率最高的問(wèn)題，這類問(wèn)題稱為指派問(wèn)題。例有一份說(shuō)明書(shū)，需要譯成英、日、德、俄四種文字，現(xiàn)有甲乙丙丁四個(gè)人，他們將說(shuō)明書(shū)譯成不同文字所需要的時(shí)間如下表所示，問(wèn)應(yīng)指派哪個(gè)人完成哪項(xiàng)工作，耗用的總時(shí)間最少？指派問(wèn)題第二十五頁(yè)，共八十二頁(yè)，編輯于2023年，星期三

一般地，有n項(xiàng)任務(wù)、n個(gè)完成人，第i人完成第j項(xiàng)任務(wù)的代價(jià)為cij(i,j=1,2,……,n),為了求得總代價(jià)最小的指派方案，引入0-1型變量xij,令

數(shù)學(xué)模型為

注：指派問(wèn)題是0-1整數(shù)規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例，其產(chǎn)地和銷地?cái)?shù)均為1，各產(chǎn)地產(chǎn)量和各銷地銷量均為1.指派問(wèn)題第二十六頁(yè)，共八十二頁(yè)，編輯于2023年，星期三指派問(wèn)題的求解方法：匈牙利法。匈牙利法基于下面的事實(shí)：如果系數(shù)矩陣的所有元素滿足：cij>=0，而其中有n個(gè)位于不同行不同列的一組0元素，則只要令對(duì)應(yīng)于這些0元素位置的xij=1，其余的xij=0，就得到最優(yōu)解。

如則

指派問(wèn)題第二十七頁(yè)，共八十二頁(yè)，編輯于2023年，星期三求解上例：

行變換得列變換得

畫(huà)出最少覆蓋0元素的直線，r=4=矩陣階數(shù)，則可以找到最優(yōu)解,所需最少時(shí)間=4+4+9+11=28

甲-俄語(yǔ)從而得到最優(yōu)指派：乙-日語(yǔ)丙-英語(yǔ)丁-德語(yǔ)指派問(wèn)題第二十八頁(yè)，共八十二頁(yè)，編輯于2023年，星期三例分配甲、乙、丙、丁四個(gè)人去完成A、B、C、D、E五項(xiàng)任務(wù)，每人完成各項(xiàng)任務(wù)的時(shí)間如下表所示，由于任務(wù)重，人手少，考慮以下兩種情況下的最優(yōu)分配方案，使得完成任務(wù)的總時(shí)間最少。(1)任務(wù)E必須完成，其他4項(xiàng)任務(wù)可選3項(xiàng)完成，但甲不能做A項(xiàng)工作；(2)其中有一人完成2項(xiàng)，其他人每人完成1項(xiàng)。解：這是一人數(shù)與任務(wù)數(shù)不等的指派問(wèn)題，若用匈牙利法求解，需作以下處理。指派問(wèn)題第二十九頁(yè)，共八十二頁(yè)，編輯于2023年，星期三(1)由于任務(wù)數(shù)大于人數(shù)，所以需要有一個(gè)虛擬的人，設(shè)為戊。因?yàn)楣ぷ鱁必須完成，故設(shè)戊完成E的時(shí)間為M(M為非常大的正數(shù))，即戊不能做工作E，其余的假想時(shí)間為0，建立的效率矩陣為：

采用匈牙利解法求解過(guò)程如下：

指派問(wèn)題第三十頁(yè)，共八十二頁(yè)，編輯于2023年，星期三(1)由于r=4<矩陣階數(shù)=5，需要調(diào)整0元素的分布。從該矩陣可看出，r=5=矩陣階數(shù)，因此能找到最優(yōu)指派方案。甲-B乙-D丙-E丁-A戊-C（戊為虛擬人，即任務(wù)C無(wú)人完成）最少的耗時(shí)數(shù)z=29+20+32+24=105指派問(wèn)題第三十一頁(yè)，共八十二頁(yè)，編輯于2023年，星期三(2)思路：方案1：甲，【甲】，乙，丙，丁方案2：甲，乙，【乙】，丙，丁方案3：甲，乙，丙，【丙】，丁方案4：甲，乙，丙，丁，【丁】方案5：甲，【甲】，乙，【乙】，丙，【丙】，丁，【丁】，工作A，B，C，D，E，虛擬工作F，G，H。這些方案較煩瑣，采用以下思路更為簡(jiǎn)便。設(shè)有虛擬人戊，他集五人的優(yōu)勢(shì)為一身，即戊的費(fèi)用是每人的最低，戊所做的工作即為此項(xiàng)工作的費(fèi)用最低者的工作，效率矩陣分配表為：指派問(wèn)題第三十二頁(yè)，共八十二頁(yè)，編輯于2023年，星期三采用匈牙利解法求解：對(duì)C3做0元素的最小直線覆蓋，得r=5=n。結(jié)果為

甲-B乙-D丙-E丁-A戊-C但戊為虛擬人，不能真做，它做C工作是借乙(此列最小時(shí)數(shù)26是C所創(chuàng)業(yè)績(jī))的優(yōu)勢(shì)，應(yīng)由乙來(lái)做，即乙做兩件工作：D、C。指派問(wèn)題第三十三頁(yè)，共八十二頁(yè)，編輯于2023年，星期三例最大收益的最優(yōu)分配問(wèn)題：有5名工人完成5項(xiàng)不同的任務(wù)收益如表所示：

求使總收益達(dá)到最高的任務(wù)分配方案。解：這是一個(gè)尋求總收益為最大值的極大化問(wèn)題，需要轉(zhuǎn)化為極小化問(wèn)題才能用匈牙利解法。收益矩陣B=（bij），設(shè)b=max{bij}，令cij=b-bij，C=（cij），以C為效率矩陣的極小化問(wèn)題即是原最大收益的極大化問(wèn)題轉(zhuǎn)化而來(lái)。指派問(wèn)題第三十四頁(yè)，共八十二頁(yè)，編輯于2023年，星期三b=max{bij}=19，令cij=19-bij，C=（cij），繼續(xù)對(duì)C矩陣采用匈牙利法求解，得到C的最優(yōu)分配方案為即甲-D乙-B丙-E丁-A戊-C，求得的最大總收益為74.指派問(wèn)題第三十五頁(yè)，共八十二頁(yè)，編輯于2023年，星期三237184566134105275934682網(wǎng)絡(luò)優(yōu)化最短路徑問(wèn)題：有一批貨物要從節(jié)點(diǎn)1運(yùn)送到節(jié)點(diǎn)8，這兩點(diǎn)間的通路如下圖，每條弧旁邊的數(shù)字表明該弧的長(zhǎng)度?？偮窂皆蕉?，運(yùn)費(fèi)越低，為節(jié)省運(yùn)輸費(fèi)用，應(yīng)該選擇怎樣的運(yùn)輸路線？求從1到8的最短路徑。第三十六頁(yè)，共八十二頁(yè)，編輯于2023年，星期三237184566134105275934682X={1},w1=0min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},w4=1w1=0w1=0第三十七頁(yè)，共八十二頁(yè)，編輯于2023年，星期三237184566134105275934682X={1,4}min{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=2第三十八頁(yè)，共八十二頁(yè)，編輯于2023年，星期三237184566134105275934682X={1,2,4}min{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=3第三十九頁(yè)，共八十二頁(yè)，編輯于2023年，星期三237184566134105275934682X={1,2,4,6}min{c23,c25,c47,c67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},w7=3w2=2w4=1w1=0w6=3w7=3第四十頁(yè)，共八十二頁(yè)，編輯于2023年，星期三237184566134105275934682X={1,2,4,6,7}min{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=6第四十一頁(yè)，共八十二頁(yè)，編輯于2023年，星期三237184566134105275934682X={1,2,4,6,7}min{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=8第四十二頁(yè)，共八十二頁(yè)，編輯于2023年，星期三237184566134105275934682X={1,2,3,4,6,7}min{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=10第四十三頁(yè)，共八十二頁(yè)，編輯于2023年，星期三237184566134105275934682X={1,2,3,4,6,7,8}1到10的最短路徑為{1，4，7，5，8}，長(zhǎng)度為10。w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10第四十四頁(yè)，共八十二頁(yè)，編輯于2023年，星期三網(wǎng)絡(luò)優(yōu)化最大流問(wèn)題：給出一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過(guò)每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。2354671ffu25=6u42=2u45=4u23=3u13=7u34=4u46=3u36=1u65=7u57=9u67=8u12=8第四十五頁(yè)，共八十二頁(yè)，編輯于2023年，星期三邊的容量和流量：容量uij，流量xij可行流：

滿足以下條件的流稱為可行流： 1、每一個(gè)節(jié)點(diǎn)流量平衡 2、0≤xij≤uij如果xij=uij，邊從i到j(luò)的方向是飽和的；如果xij<uij，邊從i到j(luò)的方向是不飽和的；網(wǎng)絡(luò)優(yōu)化21xij=5uij=5（1，2）是飽和的21xij=3uij=5（1，2）是不飽和的間隙為12=u12-x12=5-3=2第四十六頁(yè)，共八十二頁(yè)，編輯于2023年，星期三如果xij=0，邊從j到i的方向是飽和的

（2，1）是飽和的如果xij>0，邊從j到i的方向是不飽和的網(wǎng)絡(luò)優(yōu)化21xij=0uij=521xij=5uij=5（2，1）是不飽和的間隙為12=x12=5第四十七頁(yè)，共八十二頁(yè)，編輯于2023年，星期三給出一個(gè)初始的可行流xij=02354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0網(wǎng)絡(luò)優(yōu)化第四十八頁(yè)，共八十二頁(yè)，編輯于2023年，星期三2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0找到所有的不飽和邊，以及各邊可以調(diào)整流量的方向第四十九頁(yè)，共八十二頁(yè)，編輯于2023年，星期三2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0=3=1=8=8x=0找到一條從1到7的不飽和鏈鏈的間隙為：=min{8,3,1,8}=1調(diào)整鏈的流量：xij’=xij+第五十頁(yè)，共八十二頁(yè)，編輯于2023年，星期三2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=1x=1x=1x=1調(diào)整流量，f=1。繼續(xù)求出網(wǎng)絡(luò)的不飽和邊第五十一頁(yè)，共八十二頁(yè)，編輯于2023年，星期三2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=1x=1x=1x=1=1=6=9=7求出一條從1到7的不飽和鏈=min{7,1,6,9}=1,調(diào)整流量xij’=xij+1,f’=f+1=2第五十二頁(yè)，共八十二頁(yè)，編輯于2023年，星期三2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0x=0x=1x=0x=0x=0x=1x=1x=1x=1x=0調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊第五十三頁(yè)，共八十二頁(yè)，編輯于2023年，星期三2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0x=0x=1x=0x=0x=0x=1x=1x=1x=1x=0=5=8=7求出一條從1到7的不飽和鏈=min{7,5,8}=5,調(diào)整流量xij’=xij+5,f’=f+5=2+5=7第五十四頁(yè)，共八十二頁(yè)，編輯于2023年，星期三2354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=0x=1x=0x=0x=0x=6x=1x=1x=6x=0調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊第五十五頁(yè)，共八十二頁(yè)，編輯于2023年，星期三2354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=0x=1x=0x=0x=0x=6x=1x=1x=6x=0=4=4=3=6求出一條從1到7的不飽和鏈=min{6,7,4,3}=3,調(diào)整流量xij’=xij+3,f’=f+3=7+3=10第五十六頁(yè)，共八十二頁(yè)，編輯于2023年，星期三2354671f=10f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=3x=4x=3x=0x=0x=9x=1x=1x=6x=0調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊第五十七頁(yè)，共八十二頁(yè)，編輯于2023年，星期三2354671f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=3x=4x=3x=0x=0x=9x=1x=1x=6x=0f=10=1=3=7=3求出一條從1到7的不飽和鏈=min{3,1,3,7}=1,調(diào)整流量xij’=xij+1,f’=f+1=10+1=11第五十八頁(yè)，共八十二頁(yè)，編輯于2023年，星期三2354671f=11f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=4x=5x=3x=1x=0x=9x=2x=1x=6x=0調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊已找不到一條從1到7的不飽和鏈，從1開(kāi)始可以到達(dá)的節(jié)點(diǎn)為1，2，3第五十九頁(yè)，共八十二頁(yè)，編輯于2023年，星期三2354671f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=4x=5x=3x=1x=0x=9x=2x=1x=6x=0f=11已求得最大流最大流f=11，最小割集為（2,5）（3,4）（3,5）u25+u34+u35=6+4+1=11第六十頁(yè)，共八十二頁(yè)，編輯于2023年，星期三最短路問(wèn)題：給定一個(gè)運(yùn)輸網(wǎng)絡(luò)，兩點(diǎn)之間連線上的數(shù)字表示兩點(diǎn)之間的距離，試求一條從A到B的運(yùn)輸路線，使總距離最短。可將問(wèn)題分為四個(gè)階段：第一階段，從A到B；第二階段，從B到C；第三階段，從C到D；第四階段，從D到E。完全枚舉：3*3*2*1=24條。最優(yōu)解：A→B3→C2→D2→E動(dòng)態(tài)規(guī)劃第六十一頁(yè)，共八十二頁(yè)，編輯于2023年，星期三階段：將所給問(wèn)題的過(guò)程，按時(shí)間或空間特征分解成相互聯(lián)系的階段，以便按次序求每階段的解

k——描述階段的變量狀態(tài)：表示每個(gè)階段開(kāi)始時(shí)所處的自然狀況或條件，描述了研究問(wèn)題的狀況。

sk——狀態(tài)變量Sk——狀態(tài)集合S1={A},S2={B1,B2,B3},S3={C1,C2,C3},S4={D1,D2}

動(dòng)態(tài)規(guī)劃中狀態(tài)的性質(zhì)：無(wú)后效性，即如果某個(gè)階段狀態(tài)給定之后，則在這階段以后過(guò)程的發(fā)展不受這階段以前各階段狀態(tài)的影響。決策：指在某階段對(duì)可供選擇狀態(tài)的選擇，描述的變量稱為決策變量。

dk(sk)——決策變量Dk(sk)——允許決策集合D2(B1)={C1,C2,C3}動(dòng)態(tài)規(guī)劃第六十二頁(yè)，共八十二頁(yè)，編輯于2023年，星期三全過(guò)程策略：由所有各階段組成的決策函數(shù)序列,簡(jiǎn)稱策略。記為：P1,n(s1)或P1,n(s1)={d1(s1),d2(s2),……,dn(sn)}k子過(guò)程策略(后部子策略)：由k階段開(kāi)始到最后階段結(jié)束，組成的決策函數(shù)序列。Pk,n(sk)={dk(sk),dk+1(sk+1),……,dn(sn)}最優(yōu)策略：使整個(gè)問(wèn)題達(dá)到最優(yōu)效果的策略。P*1,n(A)={B3,C2,D2

,E}A→B3→C2→D2→E允許策略集：可供選擇策略的范圍，用P表示。動(dòng)態(tài)規(guī)劃方法就是要從允許策略集P中找出最優(yōu)策略P*k,n動(dòng)態(tài)規(guī)劃第六十三頁(yè)，共八十二頁(yè)，編輯于2023年，星期三狀態(tài)轉(zhuǎn)移方程：本階段狀態(tài)與上一階段狀態(tài)和上一階段決策的關(guān)系，用狀態(tài)轉(zhuǎn)移方程來(lái)表示。

sk+1=Tk(sk,dk)該方程描述了由第k階段到第k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，又稱為狀態(tài)轉(zhuǎn)移函數(shù)。sk+1=dk(sk)階段指標(biāo)：衡量某階段決策效益優(yōu)劣的策略指標(biāo)，如距離，成本，利潤(rùn)等。vk(sk,dk)指標(biāo)函數(shù)：衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)。Vk,n(sk,Pk,n)=Vk,n(sk,dk,sk+1,……,sn+1)動(dòng)態(tài)規(guī)劃第六十四頁(yè)，共八十二頁(yè)，編輯于2023年，星期三常見(jiàn)指標(biāo)函數(shù)形式(分離性，遞推關(guān)系)Vk,n(sk,Pk,n)=Vk,n(sk,dk,sk+1,……,sn+1)=Vk(sk,dk)+Vk+1(sk+1,Pk,n)Vk,n(sk,Pk,n)=Vk,n(sk,dk,sk+1,……,sn+1)=Vk(sk,dk)*Vk+1(sk+1,Pk,n)最優(yōu)指標(biāo)函數(shù):指標(biāo)函數(shù)的最優(yōu)值，fk(sk)表示從第k階段狀態(tài)sk開(kāi)始采用最優(yōu)策略P*k,n到過(guò)程終止時(shí)的最佳效益值。fk(sk)=optVk,n(sk,dk,sk+1,……,sn+1)f1(s1)表示從第1階段狀態(tài)s1采用最優(yōu)策略P*1,n到過(guò)程終止時(shí)的最佳效益值。動(dòng)態(tài)規(guī)劃第六十五頁(yè)，共八十二頁(yè)，編輯于2023年，星期三動(dòng)態(tài)規(guī)劃的基本思想：1.多階段決策過(guò)程劃分階段，恰當(dāng)?shù)倪x取狀態(tài)變量、決策變量和定義最優(yōu)指標(biāo)函數(shù)，從而將問(wèn)題化為一族同類型的子問(wèn)題逐個(gè)求解。2.求解時(shí)從邊界條件開(kāi)始，逆（或順）過(guò)程行進(jìn)方向，逐段遞推尋優(yōu)。3.既將當(dāng)前一段與未來(lái)各段分開(kāi)，又將當(dāng)前效益與未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法。如何建立動(dòng)態(tài)規(guī)劃模型：1.分析識(shí)別問(wèn)題的多階段特性，按時(shí)間或空間的先后順序適當(dāng)?shù)貏澐譂M足遞推關(guān)系的若干階段。2.確定狀態(tài)變量，滿足可知性和無(wú)后效性。一般為累計(jì)量和隨遞推過(guò)程變化的量。3.找到狀態(tài)轉(zhuǎn)移方程。4.正確確定基本方程。第六十六頁(yè)，共八十二頁(yè)，編輯于2023年，星期三基礎(chǔ)：最優(yōu)化定理作為整個(gè)過(guò)程的最優(yōu)策略具有如下性質(zhì)：不管在此最優(yōu)策略上的某個(gè)狀態(tài)以前的狀態(tài)和決策如何，對(duì)該狀態(tài)而言，以后所有的決策必定構(gòu)成最優(yōu)子策略。對(duì)最短路問(wèn)題而言,從最短路上任一點(diǎn)到終點(diǎn)的部分道路（最短路上的子路）也一定是從該點(diǎn)到終點(diǎn)的最短路。動(dòng)態(tài)規(guī)劃第六十七頁(yè)，共八十二頁(yè)，編輯于2023年，星期三從最后一段開(kāi)始計(jì)算，由后向前逐步推移至A點(diǎn)。第四階段，由D1到E只有一條線路，其長(zhǎng)度f(wàn)4(D1)=3，同理f4(D2)=4；第三階段，由Cj到Di均有兩種選擇，即第二階段，由Bj到Ci均有三種選擇，即動(dòng)態(tài)規(guī)劃第六十八頁(yè)，共八十二頁(yè)，編輯于2023年，星期三第一階段，由A到B，有三種選擇，即f1(A)=12，說(shuō)明從A到E的最短距離為12，最短路線的確定可按計(jì)算順序反推而得，即A-B3-C2-D2-E動(dòng)態(tài)規(guī)劃第六十九頁(yè)，共八十二頁(yè)，編輯于2023年，星期三一個(gè)著名的命題：一個(gè)串村走戶的賣貨郎，他從某個(gè)村莊出發(fā)，通過(guò)若干個(gè)村莊一次且僅一次，最后仍回到原出發(fā)的村莊，問(wèn)：應(yīng)如何選擇行走路線，能使得總的行程最短。設(shè)有n個(gè)城市，1,2,…,n。Dij表示從i城到j(luò)城的距離。規(guī)定推銷員是從城市1開(kāi)始的，設(shè)推銷員走到i城，記Ni＝{2,3,…,i-1,i+1,…,n}表示由1城到i城的中間城市集合。S表示到達(dá)i城中途所經(jīng)過(guò)的城市的集合，則有SNi1）選取（i,S）作為狀態(tài)變量，表示推銷員從城市1開(kāi)始走到i城，經(jīng)過(guò)若干個(gè)城市，構(gòu)成集合S。2）最優(yōu)值函數(shù)fk(i,S)為從城市1開(kāi)始經(jīng)過(guò)k個(gè)中間城市的S集到達(dá)i城的最短路線的距離。貨郎擔(dān)問(wèn)題（TSP問(wèn)題——travelingsalespersonproblem）第七十頁(yè)，共八十二頁(yè)，編輯于2023年，星期三3）遞推關(guān)系式：fk(i,S)=min[fk-1(j,S\{j})+Dji](k=1,2,…,n-1.i=2,3…,n.SNi)邊界條件：f0(i,?)=D1i4）

Pk(i,S)為最優(yōu)決策函數(shù)，表示從1城開(kāi)始經(jīng)k個(gè)中間城市到i城的最短路線上緊挨著i城前面的那個(gè)城市。例：當(dāng)推銷員從1城出發(fā)，經(jīng)過(guò)每個(gè)城市一次且僅一次，最后回到1城，問(wèn)按怎樣的路線走，使總的行程距離最短。（四個(gè)城市，其距離矩陣如下表）第七十一頁(yè)，共八十二頁(yè)，編輯于2023年，星期三5）由邊界條件可知：f0(i,?)=D1if0(2,?)=D12＝8，f0(3,?)=D13＝5，f0(4,?)=D14＝6當(dāng)k=1時(shí)，即從1城開(kāi)始，中間經(jīng)過(guò)一個(gè)城市到達(dá)i城的最短距離是：f1(2,{3})=f0(3,?)+D32＝5+9=14f1(2,{4})=f0(4,?)+D42＝6+7=13f1(3,{2})=f0(2,?)+D23＝8+8=16f1(3,{4})=f0(4,?)+D43＝6+8=14f1(4,{2})=f0(2,?)+D24＝8+5=13f1(4,{3})=f0(3,?)+D34＝5+5=101i1i第七十二頁(yè)，共八十二頁(yè)，編輯于2023年，星期三當(dāng)k=2時(shí)，即從1城開(kāi)始，中間經(jīng)過(guò)兩個(gè)城市到達(dá)i城的最短距離是：f2(2,{3,4})=min[f1(3,{4})+D32

f1(4,{3})+D42]=min[14+9,10+7]=17P2(2,{3,4})=41if2(3,{2,4})=min[f1(2,{4})+D23f1(4,{2})+D43]=min[13+8,13+8]=21P2(3,{2,4})=2或4f2(4,{3,2})=min[f1(3,{2})+D34f1(2,{3})+D24]=min[16+5,14+5]=19P2(4,{3,2})=2f1(3,{4})=14f1(4,{3})=10第七十三頁(yè)，共八十二頁(yè)，編輯于2023年，星期三當(dāng)k=3時(shí)，即從1城開(kāi)始，中間經(jīng)過(guò)三個(gè)城市到達(dá)1城的最短距離是：f