數(shù)學(xué)規(guī)劃問(wèn)題講座

1、(Linear Programming, LP)一. 線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型一、問(wèn)題提出一、問(wèn)題提出（生產(chǎn)計(jì)劃問(wèn)題）某企業(yè)利用（生產(chǎn)計(jì)劃問(wèn)題）某企業(yè)利用A、B、C三種資源，三種資源，在計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)在計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品資源的消耗、單位產(chǎn)品利潤(rùn)等數(shù)據(jù)如下表，問(wèn)如品資源的消耗、單位產(chǎn)品利潤(rùn)等數(shù)據(jù)如下表，問(wèn)如何安排生產(chǎn)計(jì)劃使企業(yè)利潤(rùn)最大？何安排生產(chǎn)計(jì)劃使企業(yè)利潤(rùn)最大？ 產(chǎn)產(chǎn) 品品資資 源源甲甲乙乙資源限制資源限制ABC120111300kg400kg250kg單位產(chǎn)品利潤(rùn)單位產(chǎn)品利潤(rùn)(元元/件件)50100n決策變量決策變量：x1、x2分別代表

2、甲、乙兩分別代表甲、乙兩種產(chǎn)品的生產(chǎn)數(shù)量。種產(chǎn)品的生產(chǎn)數(shù)量。目標(biāo)函數(shù)：max z=50 x1+100 x2約束條件： x1 + x2300 2x1 + x2400 x2250即有： max z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20稱之為上述問(wèn)題的線性規(guī)劃模型。二二、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式(Standard form)n規(guī)定如下形式的線性規(guī)劃數(shù)學(xué)模型為規(guī)定如下形式的線性規(guī)劃數(shù)學(xué)模型為L(zhǎng)P標(biāo)準(zhǔn)形式。標(biāo)準(zhǔn)形式。max z=c1x1+c2x2+cnxn 目標(biāo)函數(shù)目標(biāo)函數(shù) a11x1+a12x2+a1nxn= b1 a2

3、1x1+a22x2+a2nxn= b2 約束條件約束條件 am1x1+am2x2+amnxn= bm x1，x2，xn0n特點(diǎn)特點(diǎn)：Zmax；約束條件為等號(hào)；變量非負(fù)；約束條件為等號(hào)；變量非負(fù)；右端常數(shù)項(xiàng)大等于零。右端常數(shù)項(xiàng)大等于零。上述標(biāo)準(zhǔn)形式的線性規(guī)劃模型還可寫成如下一些形式上述標(biāo)準(zhǔn)形式的線性規(guī)劃模型還可寫成如下一些形式: :njjj=1nijjij=1jmaxz =c xa x = bi = 1, . ,mx0 j = 1, . ,n0njjj=1jm axz = cXp x= bxj = 1, . ,n(1)(2)0njjj=1jmaxz = cXp x = bxj = 1, . ,n

4、m axz = cXAX = bX0Xmaxz =cX R = X AX =b,X0R R (4) (3)(5) Integer (Linear )Programming,IP整數(shù)整數(shù)(線性線性)規(guī)劃規(guī)劃整整 數(shù)數(shù) 規(guī)規(guī) 劃劃n整數(shù)規(guī)劃問(wèn)題與模型整數(shù)規(guī)劃問(wèn)題與模型n應(yīng)用案例應(yīng)用案例線性整數(shù)規(guī)劃模型線性整數(shù)規(guī)劃模型n一般整數(shù)規(guī)劃模型一般整數(shù)規(guī)劃模型n0-1整數(shù)規(guī)劃模型整數(shù)規(guī)劃模型n混合整數(shù)規(guī)劃模型混合整數(shù)規(guī)劃模型一般整數(shù)規(guī)劃模型一般整數(shù)規(guī)劃模型 為整數(shù)為整數(shù)xxbAxtsxc, 0.min 0-1整數(shù)規(guī)劃模型整數(shù)規(guī)劃模型 nixbAxtsxci,.,2 , 1; 1 , 0.min 混合整數(shù)規(guī)劃

5、模型混合整數(shù)規(guī)劃模型pixxbAxtsxci,.,2 , 1,0. .min為整數(shù) 整數(shù)規(guī)劃問(wèn)題整數(shù)規(guī)劃問(wèn)題n實(shí)例實(shí)例應(yīng)用案例應(yīng)用案例n投資組合問(wèn)題投資組合問(wèn)題n旅游售貨員問(wèn)題旅游售貨員問(wèn)題n背包問(wèn)題背包問(wèn)題投資組合問(wèn)題投資組合問(wèn)題n背背 景景n實(shí)實(shí) 例例n模模 型型背背 景景n證券投資證券投資：把一定的資金投入到合適的：把一定的資金投入到合適的有價(jià)證券上以規(guī)避風(fēng)險(xiǎn)并獲得最大的利有價(jià)證券上以規(guī)避風(fēng)險(xiǎn)并獲得最大的利潤(rùn)。潤(rùn)。n項(xiàng)目投資項(xiàng)目投資：財(cái)團(tuán)或銀行把資金投入到若：財(cái)團(tuán)或銀行把資金投入到若干項(xiàng)目中以獲得中長(zhǎng)期的收益最大干項(xiàng)目中以獲得中長(zhǎng)期的收益最大。案案 例例n某財(cái)團(tuán)有某財(cái)團(tuán)有 萬(wàn)元的資金，經(jīng)

6、出其考察選中萬(wàn)元的資金，經(jīng)出其考察選中 個(gè)投資項(xiàng)目，每個(gè)項(xiàng)目只能投資一個(gè)。其個(gè)投資項(xiàng)目，每個(gè)項(xiàng)目只能投資一個(gè)。其中第中第 個(gè)項(xiàng)目需投資金額為個(gè)項(xiàng)目需投資金額為 萬(wàn)元，預(yù)計(jì)萬(wàn)元，預(yù)計(jì)5年后獲利年后獲利 （ ）萬(wàn)元，問(wèn)應(yīng)如何）萬(wàn)元，問(wèn)應(yīng)如何選擇項(xiàng)目使得選擇項(xiàng)目使得5年后總收益最大？年后總收益最大？Bnjcjbnj.,2 , 1j模模 型型n變量變量每個(gè)項(xiàng)目是否投資每個(gè)項(xiàng)目是否投資n約束約束總金額不超過(guò)限制總金額不超過(guò)限制n目標(biāo)目標(biāo)總收益最大總收益最大0 , 1 jxnj.,2 , 1 Bxbnjjj 1 njjjxc1max njxBxbtsxcjnjjjnjjj.,2 , 1; 0 , 1.ma

7、x11旅游售貨員問(wèn)題旅游售貨員問(wèn)題n背景背景n案例案例n模型模型背背 景景n旅游線路安排旅游線路安排 預(yù)定景點(diǎn)走且只走一次預(yù)定景點(diǎn)走且只走一次 路上時(shí)間最短路上時(shí)間最短n配送線路配送線路貨郎擔(dān)問(wèn)題貨郎擔(dān)問(wèn)題 送貨地到達(dá)一次送貨地到達(dá)一次 總路程最短總路程最短案案 例例n有一旅行團(tuán)從有一旅行團(tuán)從 出發(fā)要遍游城市出發(fā)要遍游城市 ，已知從，已知從 到到 的旅費(fèi)的旅費(fèi)為為 ，問(wèn)應(yīng)如何安排行程使總費(fèi)，問(wèn)應(yīng)如何安排行程使總費(fèi)用最小用最??？0vnvvv,.,21jvivijc模模 型型n變量變量是否從是否從i第個(gè)城市到第第個(gè)城市到第j個(gè)城市個(gè)城市n約束約束 每個(gè)城市只能到達(dá)一次、離開(kāi)一次每個(gè)城市只能到達(dá)一次

8、、離開(kāi)一次; 0 , 1ijxnjxnixniijnjij,.2 , 1; 1,.2 , 1; 100n避免出現(xiàn)斷裂避免出現(xiàn)斷裂 每個(gè)點(diǎn)給個(gè)位勢(shì)每個(gè)點(diǎn)給個(gè)位勢(shì) ui , , 除了初始點(diǎn)外要除了初始點(diǎn)外要求前點(diǎn)比后點(diǎn)大求前點(diǎn)比后點(diǎn)大n目標(biāo)目標(biāo)總費(fèi)用最小總費(fèi)用最小ijninjijxc00njnixnjinnxuunjxnixtsxcijijjiniijnjijijninjij,.,2 , 1,.,2 , 1, 0 , 11 ; 1,.,2 , 1; 1,.,2 , 1; 1. .min0000背包問(wèn)題背包問(wèn)題n背景背景n案例案例n模型模型背背 景景n郵遞包裹郵遞包裹 把形狀可變的包裹用盡量少的車輛

9、運(yùn)走把形狀可變的包裹用盡量少的車輛運(yùn)走n旅行背包旅行背包 容量一定的背包里裝盡可能的多的物品容量一定的背包里裝盡可能的多的物品實(shí)實(shí) 例例n某人出國(guó)留學(xué)打點(diǎn)行李，現(xiàn)有三個(gè)旅行包，容某人出國(guó)留學(xué)打點(diǎn)行李，現(xiàn)有三個(gè)旅行包，容積大小分別為積大小分別為1000毫升、毫升、1500毫升和毫升和2000毫毫升，根據(jù)需要列出需帶物品清單，其中一些物升，根據(jù)需要列出需帶物品清單，其中一些物品是必帶物品共有品是必帶物品共有7件，其體積大小分別為件，其體積大小分別為400、300、150、250、450、760、190、（單位毫升）。尚有（單位毫升）。尚有10件可帶可不帶物品，如件可帶可不帶物品，如果不帶將在目的地

10、購(gòu)買，通過(guò)網(wǎng)絡(luò)查詢可以得果不帶將在目的地購(gòu)買，通過(guò)網(wǎng)絡(luò)查詢可以得知其在目的地的價(jià)格（單位美元）。這些物品知其在目的地的價(jià)格（單位美元）。這些物品的容量及價(jià)格分別見(jiàn)下表，試給出一個(gè)合理的的容量及價(jià)格分別見(jiàn)下表，試給出一個(gè)合理的安排方案把物品放在三個(gè)旅行包里。安排方案把物品放在三個(gè)旅行包里。 物品物品12345678910體積體積200350500430320120700420250100價(jià)格價(jià)格1545100705075200902030問(wèn)題分析問(wèn)題分析n變量變量對(duì)每個(gè)物品要確定是否帶同時(shí)要確定對(duì)每個(gè)物品要確定是否帶同時(shí)要確定放在哪個(gè)包裹里，如果增加一個(gè)虛擬的包裹把放在哪個(gè)包裹里，如果增加一個(gè)虛

11、擬的包裹把不帶的物品放在里面，則問(wèn)題就轉(zhuǎn)化為確定每不帶的物品放在里面，則問(wèn)題就轉(zhuǎn)化為確定每個(gè)物品放在哪個(gè)包裹里。如果直接設(shè)變量為每個(gè)物品放在哪個(gè)包裹里。如果直接設(shè)變量為每個(gè)物品放在包裹的編號(hào)，則每個(gè)包裹所含物品個(gè)物品放在包裹的編號(hào)，則每個(gè)包裹所含物品的總?cè)萘烤秃茈y寫成變量的函數(shù)。為此我們?cè)O(shè)的總?cè)萘烤秃茈y寫成變量的函數(shù)。為此我們?cè)O(shè)變量為第變量為第i個(gè)物品是否放在第個(gè)物品是否放在第j個(gè)包裹個(gè)包裹中中3 , 2 , 1,17.,2 , 1; 0 , 1jixijn約束約束3 , 2 , 1;171jrxcjijii7.,2 , 1; 131ixjij17.,2 , 8; 131ixjij包裹容量限制

12、包裹容量限制必帶物品限制必帶物品限制選帶物品限制選帶物品限制n目標(biāo)函數(shù)目標(biāo)函數(shù)未帶物品購(gòu)買費(fèi)用最小未帶物品購(gòu)買費(fèi)用最小17.,2 , 8;131ixjij)1 (31178jijiixp模模 型型)1 (min31178jijiixp3 , 2 , 1;171jrxcjijii7.,2 , 1; 131ixjij17.,2 , 8; 131ixjij3 , 2 , 1,17.,2 , 1; 0 , 1jixij應(yīng)用案例分析應(yīng)用案例分析n人力資源分配問(wèn)題人力資源分配問(wèn)題n應(yīng)急設(shè)施選址問(wèn)題應(yīng)急設(shè)施選址問(wèn)題人力資源分配問(wèn)題人力資源分配問(wèn)題n某個(gè)中型百貨商場(chǎng)對(duì)售貨人員（周工某個(gè)中型百貨商場(chǎng)對(duì)售貨人員（

13、周工資資200元）的需求經(jīng)統(tǒng)計(jì)如下表元）的需求經(jīng)統(tǒng)計(jì)如下表 為了保證銷售人員充分休息，銷售人為了保證銷售人員充分休息，銷售人員每周工作員每周工作5天，休息天，休息2天。問(wèn)應(yīng)如何天。問(wèn)應(yīng)如何安排銷售人員的工作時(shí)間，使得所配安排銷售人員的工作時(shí)間，使得所配售貨人員的總費(fèi)用最??？售貨人員的總費(fèi)用最小？星期星期一一二二三三四四五五六六七七人數(shù)人數(shù) 12 15 12 14 16 18 19模型假設(shè)模型假設(shè)n每天工作每天工作8小時(shí)，不考慮夜班的情況；小時(shí)，不考慮夜班的情況；n每個(gè)人的休息時(shí)間為連續(xù)的兩天時(shí)每個(gè)人的休息時(shí)間為連續(xù)的兩天時(shí)間；間；n每天安排的人員數(shù)不得低于需求量，每天安排的人員數(shù)不得低于需求量

14、，但可以超過(guò)需求量但可以超過(guò)需求量問(wèn)題分析問(wèn)題分析因素因素 不可變因素不可變因素：需求量、休息時(shí)間、單位費(fèi)用；：需求量、休息時(shí)間、單位費(fèi)用； 可變因素可變因素：安排的人數(shù)、每人工作的時(shí)間、總費(fèi)用；：安排的人數(shù)、每人工作的時(shí)間、總費(fèi)用；方案方案 確定每天工作的人數(shù)，由于連續(xù)休息確定每天工作的人數(shù)，由于連續(xù)休息2天，當(dāng)確定每天，當(dāng)確定每個(gè)人開(kāi)始休息的時(shí)間就等于知道工作的時(shí)間，因而確定個(gè)人開(kāi)始休息的時(shí)間就等于知道工作的時(shí)間，因而確定每天開(kāi)始休息的人數(shù)就知道每天開(kāi)始工作的人數(shù)，從而每天開(kāi)始休息的人數(shù)就知道每天開(kāi)始工作的人數(shù)，從而求出每天工作的人數(shù)。求出每天工作的人數(shù)。變量變量 每天開(kāi)始休息的人數(shù)每天開(kāi)

15、始休息的人數(shù) 約束條件約束條件 1.每人休息時(shí)間每人休息時(shí)間2天，自然滿足。天，自然滿足。 7,.,2 , 1, ixi 2. 每天工作人數(shù)不低于需求量，第每天工作人數(shù)不低于需求量，第i天工作的人數(shù)天工作的人數(shù)就是從第就是從第i天往前數(shù)天往前數(shù)5天內(nèi)開(kāi)始工作的人數(shù)，所以有約束：天內(nèi)開(kāi)始工作的人數(shù)，所以有約束：1265432xxxxx 1576543xxxxx 1217654xxxxx 1421765xxxxx 1632176xxxxx 1843217xxxxx 1954321xxxxx 3.變量非負(fù)約束：變量非負(fù)約束：7,.,2 , 1, 0ixi 目標(biāo)函數(shù)目標(biāo)函數(shù)：總費(fèi)用最小，總費(fèi)用與使用的

16、總總費(fèi)用最小，總費(fèi)用與使用的總?cè)藬?shù)成正比。由于每個(gè)人必然在且僅在某一人數(shù)成正比。由于每個(gè)人必然在且僅在某一天開(kāi)始休息，所以總?cè)藬?shù)等于天開(kāi)始休息，所以總?cè)藬?shù)等于 71iix 模模 型型應(yīng)急選址問(wèn)題應(yīng)急選址問(wèn)題 某城市要在市區(qū)設(shè)置某城市要在市區(qū)設(shè)置k個(gè)應(yīng)急服務(wù)中心個(gè)應(yīng)急服務(wù)中心,經(jīng)過(guò)初步篩選確定了經(jīng)過(guò)初步篩選確定了m個(gè)備選地，現(xiàn)已個(gè)備選地，現(xiàn)已知共有知共有n個(gè)居民小區(qū)，各小區(qū)到個(gè)備選地個(gè)居民小區(qū)，各小區(qū)到個(gè)備選地的距離為的距離為 為了使為了使得各小區(qū)能及時(shí)得到應(yīng)急服務(wù)，要求各得各小區(qū)能及時(shí)得到應(yīng)急服務(wù)，要求各小區(qū)到最近的服務(wù)中心的距離盡可能的小區(qū)到最近的服務(wù)中心的距離盡可能的短，試給出中心選址方案

17、。短，試給出中心選址方案。,.,2 , 1,.,2 , 1,mjnidij 問(wèn)題分析問(wèn)題分析 該問(wèn)題與傳統(tǒng)的選址問(wèn)題的該問(wèn)題與傳統(tǒng)的選址問(wèn)題的主要區(qū)別主要區(qū)別在在于其目標(biāo)不再是要求費(fèi)用最小，而是要于其目標(biāo)不再是要求費(fèi)用最小，而是要求最長(zhǎng)距離最短。也就是離服務(wù)中心距求最長(zhǎng)距離最短。也就是離服務(wù)中心距離最遠(yuǎn)的小區(qū)離最近的服務(wù)中心距離最離最遠(yuǎn)的小區(qū)離最近的服務(wù)中心距離最小。小。 變量變量：當(dāng)中心的位置確定下來(lái)后，各?。寒?dāng)中心的位置確定下來(lái)后，各小區(qū)對(duì)應(yīng)的最近中心也就確定，所以真正區(qū)對(duì)應(yīng)的最近中心也就確定，所以真正的變量也就是小區(qū)的位置。設(shè)的變量也就是小區(qū)的位置。設(shè) ,.,2,1,1 ,0mjxj 問(wèn)

18、題分析問(wèn)題分析 為了便于說(shuō)明問(wèn)題引入間接變量，第為了便于說(shuō)明問(wèn)題引入間接變量，第i小區(qū)是否由第小區(qū)是否由第j個(gè)中心服務(wù)個(gè)中心服務(wù) 以及最遠(yuǎn)的距離以及最遠(yuǎn)的距離 約束條件約束條件 小區(qū)服務(wù)約束小區(qū)服務(wù)約束,.,2 , 1,.,2 , 1, 1 , 0mjniyij ,.,2 , 1,.,2 , 1,mjnixyjij ,.,2 , 1, 11niymjij , z問(wèn)問(wèn) 題題 分分 析析最遠(yuǎn)距離約束最遠(yuǎn)距離約束中心個(gè)數(shù)約束中心個(gè)數(shù)約束目標(biāo)函數(shù)目標(biāo)函數(shù)：最遠(yuǎn)距離：最遠(yuǎn)距離 最小最小mjnizydijij,.,2 , 1,.,2 , 1, z,1kxmjj 模模 型型0,.,2 , 1,.,2 , 1

19、, 1 , 0,.,2 , 1,.,2 , 1,.,2 , 1, 1,.,2 , 1,.,2 , 1,. .min11zmjniyxkxmjnizydniymjnixytszijjmjjijijmjijjij競(jìng)賽建模舉例飛行管理問(wèn)題飛行管理問(wèn)題一個(gè)飛行管理問(wèn)題 在約10000m高空的某邊長(zhǎng)160km的正方形區(qū)域內(nèi),經(jīng)常有若干架飛機(jī)作水平飛行,區(qū)域內(nèi)每架飛機(jī)的位置和速度向量均由計(jì)算機(jī)記錄其數(shù)據(jù),以便進(jìn)行飛行管理.當(dāng)一架欲進(jìn)入該區(qū)域的飛機(jī)到達(dá)邊界區(qū)域邊緣時(shí), 記錄其數(shù)據(jù)后,要立即 計(jì)算并判斷是否會(huì)與其區(qū)域內(nèi)的飛機(jī)發(fā)生碰撞.如果會(huì)碰撞 ,則應(yīng)計(jì)算如何調(diào)整各架(包括新進(jìn)入的)飛機(jī)飛行的方向角,以避免碰

20、撞.現(xiàn)假設(shè)條件如下: 1) 不碰撞的標(biāo)準(zhǔn)為任意兩架飛機(jī)的距離大于8km; 2)飛機(jī)飛行方向角調(diào)整的幅度不應(yīng)超過(guò)30度; 3)所有飛機(jī)飛行速度均為每小時(shí)為800km; 4)進(jìn)入該區(qū)域的飛機(jī)在到達(dá)區(qū)域邊緣時(shí),與區(qū)域內(nèi)飛機(jī)的距離應(yīng)在 60km以上; 5)最多考慮6架飛機(jī); 6)不必考慮飛機(jī)離開(kāi)此區(qū)域后的狀況;請(qǐng)你對(duì)這個(gè)避免碰撞的飛行管理問(wèn)題建立數(shù)學(xué)模型.列出計(jì)算步驟,對(duì)以下數(shù)據(jù)進(jìn)行計(jì)算(方向角誤差不超過(guò)0.01度),要求飛機(jī)飛行方向角調(diào)整的幅度盡量小 .設(shè)該區(qū)域4個(gè)頂點(diǎn)坐標(biāo)為(0,0),(160,0),(160,160),(0,160).記錄數(shù)據(jù)為: 飛機(jī)編號(hào) 橫坐標(biāo)x 縱坐標(biāo)y 方向角(度) 1

21、150 140 243 2 85 85 236 3 150 155 220.5 4 145 50 159 5 130 150 230 新進(jìn)入 0 0 52注: 方向角指飛行方向與x軸正向的夾角兩架飛機(jī)不碰撞的條件兩架飛機(jī)不碰撞的條件222)()()(tjttjtijyyxxtrii,sin,cos00iitiitivtyyvtxxi064)()(2trtfijij（0 t Tij） Ti為第為第i架飛機(jī)飛出區(qū)域的時(shí)刻架飛機(jī)飛出區(qū)域的時(shí)刻不碰撞條件不碰撞條件000),(iiiyxiii0 初始位置 時(shí)刻t飛機(jī)的位置兩架飛機(jī)的距離（平方）),min(jiijTTT 0000000000000000

22、0000tan,223tan,23,sin,tan,23tan,2,cos,tan,2tan,20,sin,tan,223tan,20,cosiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiixDyorxyifvyxyorxyDifvxxyDorxDyDifvxDxDyorxDyDifvxDT不必考慮在區(qū)域外的碰撞兩架飛機(jī)都在區(qū)域中的時(shí)間具體來(lái)看，第i架飛機(jī)在區(qū)域內(nèi)的時(shí)間飛機(jī)飛出區(qū)域的時(shí)刻飛機(jī)飛出區(qū)域的時(shí)刻.)(2ijijijijijczbztf整理： fij(t)的最小值 (- bij2 / 4 + cij ) ；此時(shí)其中： .2sin4*jiijijvbt不

23、碰撞條件的等價(jià)表述不碰撞條件的等價(jià)表述 最后，優(yōu)化模型為最后，優(yōu)化模型為 0*ijt若fij(t)大于等于肯定成立ijijTt *若fij(t)大于等于等價(jià)于0)(ijijTfijijTt *0若fij(t)大于等于等價(jià)于0)(*ijtfij, 042ijijcbLINGOLINGO求解求解283. 0800/2160/2maxvDT一個(gè)簡(jiǎn)化的數(shù)學(xué)模型一個(gè)簡(jiǎn)化的數(shù)學(xué)模型任何一架飛機(jī)在區(qū)域中停留最長(zhǎng)時(shí)間 放松到任兩架飛機(jī)在這段時(shí)間不碰撞甚至放松到任兩架飛機(jī)永遠(yuǎn)不碰撞000),(iiiyxiii0.61iiMin其他目標(biāo)調(diào)整后的方向角 總的調(diào)整量最小總的調(diào)整量最小 |max6,.,1iiMin最大

24、調(diào)整量最小最大調(diào)整量最小 初始位置與方向角基于相對(duì)運(yùn)動(dòng)觀點(diǎn)的模型)22sin(),22(cos(2sin2)2cos,2sin(2sin2)2cos2sin,2sin2sin(2)sinsin,coscos(jijijijijijijijijijiijijvvvvvvvvvijijr基于相對(duì)運(yùn)動(dòng)觀點(diǎn)的模型,8sin1ijijr于是 . 6 , 1,30, 6 , 1,)(. .21612ijijitsMiniijjiijii數(shù)學(xué)規(guī)劃模型 三三.圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析p圖的基本知識(shí)圖的基本知識(shí)p最短路徑問(wèn)題最短路徑問(wèn)題p網(wǎng)絡(luò)最大流問(wèn)題網(wǎng)絡(luò)最大流問(wèn)題p網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題引引 言

25、言AB圖8-1 a）CD圖8-1 b）ACDB例例 中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題（CPPChinese postman problem） 一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件。如一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件。如何為他（她）設(shè)計(jì)一條最短的投遞路線（從郵何為他（她）設(shè)計(jì)一條最短的投遞路線（從郵局出發(fā)，經(jīng)過(guò)投遞區(qū)內(nèi)每條街道至少一次，最局出發(fā)，經(jīng)過(guò)投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？由于這一問(wèn)題是我國(guó)管梅谷教后返回郵局）？由于這一問(wèn)題是我國(guó)管梅谷教授授19601960年首先提出的，所以國(guó)際上稱之為中國(guó)年首先提出的，所以國(guó)際上稱之為中國(guó)郵遞員問(wèn)題。郵遞員問(wèn)題。例例 旅行商問(wèn)題（哈密頓問(wèn)題）旅行商問(wèn)

26、題（哈密頓問(wèn)題）（TSPtraveling salesman problem） 一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計(jì)一條最短的旅行路線（從如何為他（她）設(shè)計(jì)一條最短的旅行路線（從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市恰好一次，最后返回駐地出發(fā)，經(jīng)過(guò)每個(gè)城市恰好一次，最后返回駐地）？這一問(wèn)題的研究歷史十分悠久，通常駐地）？這一問(wèn)題的研究歷史十分悠久，通常稱之為旅行商問(wèn)題。稱之為旅行商問(wèn)題。 圖論中常用點(diǎn)和點(diǎn)之間的線所構(gòu)成的圖論中常用點(diǎn)和點(diǎn)之間的線所構(gòu)成的圖，反映實(shí)際生產(chǎn)和生活中的某些特定對(duì)圖，反映實(shí)際生產(chǎn)和生活中的某些特定對(duì)象之間的特定關(guān)系。一般來(lái)說(shuō)，通常用

27、點(diǎn)象之間的特定關(guān)系。一般來(lái)說(shuō)，通常用點(diǎn)表示研究對(duì)象、用點(diǎn)與點(diǎn)之間的線表示研表示研究對(duì)象、用點(diǎn)與點(diǎn)之間的線表示研究對(duì)象之間的特定關(guān)系。究對(duì)象之間的特定關(guān)系。 在一般情況下，圖中的相對(duì)位置如何，在一般情況下，圖中的相對(duì)位置如何，點(diǎn)與點(diǎn)之間線的長(zhǎng)短曲直，對(duì)于反映研究點(diǎn)與點(diǎn)之間線的長(zhǎng)短曲直，對(duì)于反映研究對(duì)象之間的關(guān)系，顯的并不重要。對(duì)象之間的關(guān)系，顯的并不重要。 因此，圖論中的圖與幾何圖，工程圖因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上是不同的。等本質(zhì)上是不同的。 通常把點(diǎn)與點(diǎn)之間不帶箭頭的線叫做通常把點(diǎn)與點(diǎn)之間不帶箭頭的線叫做邊邊，帶箭，帶箭頭的線叫做頭的線叫做弧弧。 如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的，那

28、么，稱為為如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的，那么，稱為為無(wú)向圖無(wú)向圖，記作，記作G =(V，E)，其中，其中V V表示圖表示圖G的點(diǎn)集合的點(diǎn)集合，E表示圖表示圖G的邊集合。連接點(diǎn)的邊集合。連接點(diǎn)vi ,vjV的邊記作的邊記作 vi ,vj ，或者或者 vj ,vi 。 如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的，那么稱為它為如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的，那么稱為它為有向圖有向圖，記作，記作D =(V,A)，其中，其中V 表示有向圖表示有向圖D D的點(diǎn)集合，的點(diǎn)集合，A表示有向圖表示有向圖D D的弧集合。一條方向從的弧集合。一條方向從vi指向指向vj的弧，記的弧，記作作( (vi,vj) )。例如例如.下下圖是一

29、個(gè)無(wú)向圖圖是一個(gè)無(wú)向圖G=（V，E）其中其中V = v1,v2,v3,v4 E = v1,v2,v2,v1,v2,v3, v3,v4,v1,v4, v2,v4, v3,v3 v3v2v1v4下圖是一個(gè)有向圖下圖是一個(gè)有向圖D=（V，A）其中其中V = v1,v2,v3,v4,v5,v6,v7 A = (v1 ,v2),(v1 ,v3),(v3 ,v2), (v3 ,v4), (v2 ,v4),(v4 ,v5),(v4 ,v6),(v5 ,v3), (v5 ,v4),(v5 ,v6),(v6 ,v7)v7v5v3v4v2v1v61.1.最短路徑問(wèn)題最短路徑問(wèn)題 最短路徑問(wèn)題是圖論中十分重要的最優(yōu)

30、化問(wèn)題之一，它作為一個(gè)經(jīng)常被用到的基本工具，可以解決生產(chǎn)實(shí)際中的許多問(wèn)題，比如城市中的管道鋪設(shè)，線路安排，工廠布局，設(shè)備更新等等。也可以用于解決其它的最優(yōu)化問(wèn)題。最短路問(wèn)題一一、引例：、引例：如下圖中如下圖中V1：油田，：油田，V9：原油加工廠：原油加工廠求使從求使從V1到到V9總鋪路設(shè)管道最短方案?？備伮吩O(shè)管道最短方案。 V1V4V2V3V6V9V8V7V542466234442二、最短路算法二、最短路算法1、情況一： wij0(E.W.Dijkstra算法)原理：Bellman最優(yōu)性定理方法：圖上作業(yè)法（標(biāo)號(hào)法）標(biāo)號(hào)：對(duì)于點(diǎn),若已求出到vi的最短值，標(biāo)號(hào)（i,i) i ：表示到的最短路值

31、i:表示最短路中最后經(jīng)過(guò)的點(diǎn)標(biāo)號(hào)法步驟：1）給v1標(biāo)號(hào)(0, vs)2）把所有頂點(diǎn)分成兩部分,P：已標(biāo)號(hào)的點(diǎn)；T未標(biāo)號(hào)的點(diǎn)考慮與已標(biāo)號(hào)點(diǎn)相鄰的弧是存在這樣的弧（ vi ，vj ）, vi P, vj T若不存在，此問(wèn)題無(wú)解，否則轉(zhuǎn)3）3）選取未標(biāo)號(hào)中所有入線的起點(diǎn)與未標(biāo)號(hào)的點(diǎn)vj進(jìn)行計(jì)算:mini + wij= j并對(duì)其進(jìn)行標(biāo)號(hào)(j, vi)，重復(fù)2）2、情況二： wij0設(shè)從v1到vj(j=1,2,t)的最短路長(zhǎng)為p1jv1到vj無(wú)任何中間點(diǎn) p1j（1）= wijv1到vj中間最多經(jīng)過(guò)一個(gè)點(diǎn) p1j（2）= min p1j（1）+wijv1到vj中間最多經(jīng)過(guò)兩個(gè)點(diǎn) p1j（3）= min

32、p1j（2）+wij.v1到vj中間最多經(jīng)過(guò)t-2個(gè)點(diǎn) p1j（t-1）= min p1j（t-2）+wij終止原則：1）當(dāng)p1j（k）=p1j（k+1）可停止，最短路p1j*= p1j（k）2）當(dāng)p1j（t-1）= p1j（t-2）時(shí)，再多迭代一次p1j（t） ，若p1j（t） = p1j（t-1） ，則原問(wèn)題無(wú)解，存在負(fù)回路。 例： 求下圖所示有向圖中從v1到各點(diǎn)的最短路。v1v4v2v3v5v6v7v825-34674-23-1-342 wij d(t)(v1,vj) v1 v2 v3 v4 v5 v6 v7 v8v1v2 v3 v4v5v6v7v80 25-30 -2406400-3

33、0720320t=1 t=2 t=3 t=4 t=5 t=6025-3020-3611020-36615020-3361410020-336910020-336910說(shuō)明：表中空格處為說(shuō)明：表中空格處為+ 。例例 設(shè)備更新問(wèn)題設(shè)備更新問(wèn)題制訂一設(shè)備更新問(wèn)題，使得總費(fèi)用最小制訂一設(shè)備更新問(wèn)題，使得總費(fèi)用最小 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 購(gòu)買費(fèi)購(gòu)買費(fèi) 13 14 16 19 24 使用年數(shù)使用年數(shù) 0-1 1-2 2-3 3-4 4-5 維修費(fèi)維修費(fèi) 8 10 13 18 27 解設(shè)以vi(i=1,2,3,4,5)表示“第i年初購(gòu)進(jìn)一臺(tái)新設(shè)備”這種狀態(tài)，以v6表示“

34、第5年末”這種狀態(tài)；以弧(vi, vj)表示“第i年初購(gòu)置的一臺(tái)設(shè)備一直使用到第j年初”這一方案，以wij表示這一方案所需購(gòu)置費(fèi)和維護(hù)費(fèi)之和。v1v2v3v5v6v4214432228962316345244734273732(0，Vs)(0，V1)(31, V1)(44,V1)(62,V1)(78,V3)這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問(wèn)題就這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問(wèn)題就可歸結(jié)為從圖中找出一條從可歸結(jié)為從圖中找出一條從v1到到v6的最短路問(wèn)題。的最短路問(wèn)題。用用Dijkstra標(biāo)號(hào)法，求得最短路為標(biāo)號(hào)法，求得最短路為 v1v3v6 即第一年初購(gòu)置的設(shè)備使用到第三年初予以更新，

35、即第一年初購(gòu)置的設(shè)備使用到第三年初予以更新，然后一直使用到第五年末。這樣五年的總費(fèi)用最然后一直使用到第五年末。這樣五年的總費(fèi)用最少，為少，為78。 2.2.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題基本概念基本概念 定義定義 設(shè)賦權(quán)有向圖設(shè)賦權(quán)有向圖D=(V,A), 在在V中指定一中指定一個(gè)個(gè)發(fā)點(diǎn)發(fā)點(diǎn)vs和一個(gè)和一個(gè)收收點(diǎn)點(diǎn)vt , 其他的點(diǎn)叫做中間點(diǎn)。其他的點(diǎn)叫做中間點(diǎn)。對(duì)于對(duì)于D中的每一個(gè)弧中的每一個(gè)弧 (vi ,vj)A, 都有一個(gè)權(quán)都有一個(gè)權(quán) cij 叫做弧的叫做弧的容量容量。我們把這樣的圖。我們把這樣的圖 D 叫做一個(gè)網(wǎng)叫做一個(gè)網(wǎng)絡(luò)系統(tǒng)，簡(jiǎn)稱絡(luò)系統(tǒng)，簡(jiǎn)稱網(wǎng)絡(luò)網(wǎng)絡(luò)，記做，記做D =（V，

36、A，C）。）。2. 最大流問(wèn)題最大流問(wèn)題 如下是一運(yùn)輸網(wǎng)絡(luò)，弧上的數(shù)字表示每條弧如下是一運(yùn)輸網(wǎng)絡(luò)，弧上的數(shù)字表示每條弧上的容量，問(wèn)：該網(wǎng)絡(luò)的最大流量是多少？上的容量，問(wèn)：該網(wǎng)絡(luò)的最大流量是多少？vsv2v1v3v4vt432312234基本概念和基本定理基本概念和基本定理1、網(wǎng)絡(luò)與流定義1：給定一個(gè)有向圖D=(V,A),在V中有一個(gè)發(fā)點(diǎn)vs和一收點(diǎn)vt，其余的點(diǎn)為中間點(diǎn)。對(duì)于每一條弧(vi,vj),對(duì)應(yīng)有一個(gè)c(vi,vj)0,(cij)稱為弧的容量。這樣的有向圖稱為網(wǎng)絡(luò)。記為D=(V,A,C)。網(wǎng)絡(luò)的流：定義在弧集合A上的一個(gè)函數(shù)f=f(vi,vj)，稱f(vi,vj)為弧(vi,vj)上的

37、流量，簡(jiǎn)記fij 。2、可行流與最大流、可行流與最大流定義定義2 滿足下列條件的流稱為滿足下列條件的流稱為可行流可行流：1) 0 fijcij2)平衡條件：平衡條件：中間點(diǎn)中間點(diǎn) fij = fji(vi,vj) A(vj,vi) A發(fā)點(diǎn)發(fā)點(diǎn)vs fsj fjs=v(f)(vs,vj) A(vj,vs)A ftj fjt= v(f)(vt,vj)A收點(diǎn)收點(diǎn)vt，(vj,vt)A式中v(f)稱為這個(gè)可行流的流量，即發(fā)點(diǎn)的凈輸出量（或收點(diǎn)的凈輸入量）。3、增廣鏈增廣鏈 給定可行流f=fij，使fij=cij的弧稱為飽和弧，使fij0的弧稱為非零流弧。 若是網(wǎng)絡(luò)中連接發(fā)點(diǎn)vs和收點(diǎn)vt的一條鏈，定義

38、鏈的方向是從vs到vt，則鏈上的弧被分成兩類：前向?。夯〉姆较蚺c鏈的方向一致 全體+后向弧：弧的方向與鏈的方向相反 全體定義3 設(shè)f是一可行流，是從vs到vt的一條鏈，若滿足下列條件，則稱之為（關(guān)于流f的）一條增廣鏈： 在弧(vi,vj)+上，0fijcij 在弧(vi,vj)上，0fijcij步驟：2、 標(biāo)號(hào)過(guò)程1、選取一個(gè)可行流（可選擇零流弧） 從vs出發(fā)，在前向弧上(vi,vj) ，若fij0，則給vj標(biāo)號(hào)( vi,l(vj)，其中l(wèi)(vj)=minl(vi)，fji。尋找最大流的標(biāo)號(hào)法(Ford Fulkerson) 思想：從一可行流出發(fā)，檢查關(guān)于此流是否存在增廣鏈。若存在增廣鏈，則增

39、大流量，使此鏈變?yōu)榉窃鰪V鏈；這時(shí)再檢查是非還有增廣鏈，若還有，繼續(xù)調(diào)整，直至不存在增廣鏈為止。 3、若標(biāo)號(hào)延續(xù)到vt，表明得到一條從vs到vt的增廣鏈，轉(zhuǎn)入調(diào)整階段4，否則當(dāng)前流即為最大流。4、調(diào)整過(guò)程令調(diào)整量為= l(vt)令 fij+ (vi,vj)+ fij= fij (vi,vj) fij (vi,vj)去掉所有的標(biāo)號(hào)，對(duì)新的可行流f=fij，重新進(jìn)入標(biāo)號(hào)過(guò)程?？山Y(jié)合下圖理解其實(shí)際涵義?？山Y(jié)合下圖理解其實(shí)際涵義。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2) 在實(shí)際的網(wǎng)絡(luò)系統(tǒng)中，當(dāng)涉及到有關(guān)在實(shí)際的網(wǎng)絡(luò)系統(tǒng)中，當(dāng)涉及到

40、有關(guān)流的問(wèn)題的時(shí)候，我們往往不僅僅考慮的流的問(wèn)題的時(shí)候，我們往往不僅僅考慮的是流量，還經(jīng)常要考慮費(fèi)用的問(wèn)題。比如是流量，還經(jīng)常要考慮費(fèi)用的問(wèn)題。比如一個(gè)鐵路系統(tǒng)的運(yùn)輸網(wǎng)絡(luò)流，即要考慮網(wǎng)一個(gè)鐵路系統(tǒng)的運(yùn)輸網(wǎng)絡(luò)流，即要考慮網(wǎng)絡(luò)流的貨運(yùn)量最大，又要考慮總費(fèi)用最小。絡(luò)流的貨運(yùn)量最大，又要考慮總費(fèi)用最小。最小費(fèi)用最大流問(wèn)題就是要解決這一類問(wèn)最小費(fèi)用最大流問(wèn)題就是要解決這一類問(wèn)題。題。3.3.網(wǎng)絡(luò)系統(tǒng)的最小費(fèi)用最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最小費(fèi)用最大流問(wèn)題 設(shè)一個(gè)網(wǎng)絡(luò)D = (V1，A，C )，對(duì)于每一個(gè)弧(vi ,vj)A, 給定一個(gè)單位流量的費(fèi)用bij 0，網(wǎng)絡(luò)系統(tǒng)的最小費(fèi)用最大流問(wèn)題，是指要尋求一個(gè)最大流

41、f ，并且流的總費(fèi)用 b ( f ) = bij fij 達(dá)到最小。 （vi ,vj）A 在一個(gè)網(wǎng)絡(luò)D 中，當(dāng)沿可行流 f 的一條增廣鏈，以調(diào)整量=1改進(jìn) f ，得到的新可行流 f 的流量，有 v( f ) = v( f ) + 1， 此時(shí)總費(fèi)用 b( f ) 比 b( f ) 增加了 b(f)-b(f)=bij(fij-fij)- bij(fij-fij)= bij-bij + - + -將bij-bij叫做這條增廣鏈的費(fèi)用。 如果可行流在流量為如果可行流在流量為v(f)的所有可行流中的所有可行流中的費(fèi)用最小，并且是的費(fèi)用最小，并且是 關(guān)于關(guān)于f 的所有增廣鏈中的的所有增廣鏈中的費(fèi)用最小的增

42、廣鏈。那么沿增廣鏈費(fèi)用最小的增廣鏈。那么沿增廣鏈調(diào)整可行流調(diào)整可行流f，得到的新可行流，得到的新可行流f，也是流量為，也是流量為v(f)的所有的所有可行流中的最小費(fèi)用流?？尚辛髦械淖钚≠M(fèi)用流。 依次類推，當(dāng)依次類推，當(dāng)f是最大流時(shí)，就是所要求的是最大流時(shí)，就是所要求的最小費(fèi)用最大流。最小費(fèi)用最大流。 顯然，零流f =0是流量為0的最小費(fèi)用流。一般地，尋求最小費(fèi)用流，從零流f=0開(kāi)始。問(wèn)題是：如果已知f 是流量為 v ( f ) 的最小費(fèi)用流，那么就要去尋找關(guān)于f 的最小費(fèi)用增廣鏈。 重新構(gòu)造一個(gè)賦權(quán)有向圖重新構(gòu)造一個(gè)賦權(quán)有向圖M( f )，其頂點(diǎn)，其頂點(diǎn)是原網(wǎng)絡(luò)是原網(wǎng)絡(luò)D的頂點(diǎn)，而將的頂點(diǎn)，而將D中的每一條弧中的每一條弧(vi,vj)變變成兩個(gè)相反方向的?。ǔ蓛蓚€(gè)相反方向的?。╲i,v