運籌與優(yōu)化模型PPT課件

1、1目標(biāo)函數(shù) 21127maxxxf約束條件 3605921 xx2005421 xx30010321xx. 0, 021xx其中( , )為決策向量， 1x2x滿足約束條件的( , )稱為可行決策。 1x2x 線性規(guī)劃問題就是指目標(biāo)函數(shù)為諸決策變量的線性函數(shù)，給定的條件可用諸決策變量的線性等式或不等式表示的決策問題。線性規(guī)劃求解的有效方法是單純形法（進(jìn)一步了解可參考有關(guān)書籍），當(dāng)然簡單的問題也可用圖解法。第1頁/共97頁2如用圖解法求解例1： 由約束條件決定的可行域如圖陰影所示， 目標(biāo)函數(shù)的等值線向右上方移動時其值增大，在到達(dá)點 時f取得最大值； 2Q第2頁/共97頁3當(dāng) =20, =24時，

2、即產(chǎn)品A生產(chǎn)20t，產(chǎn)品B生產(chǎn)24t時，生產(chǎn)方案最優(yōu)。 1x2x其最大利潤為：7201224428千元例2：某兩個煤廠 . ，每月進(jìn)煤數(shù)量分別為60t和100t聯(lián)合供應(yīng)3個居民區(qū) 。3個居民區(qū)每月對煤的需求量依次分別為50t,70t,40t，煤廠 離3個居民區(qū) 的距離依次為10km,5km,6km，煤廠 離3個居民區(qū) 的距離依次分別為4km,8km,12km，問如何分配供煤量使得運輸費（即tkm）達(dá)到最小？1A2A321,BBB321,BBB2A321,BBB1A第3頁/共97頁4 解：設(shè) 表示 (i=1.2)煤廠提供給 （居民區(qū)的煤量； ijxiAjBf表示總運輸費此問題歸結(jié)為： 23222

3、113121112846510minxxxxxxfts.60131211xxx100232221xxx502111 xx702212 xx402313 xx, 3 , 2 , 1, 2 , 1, 0jixij第4頁/共97頁5一般線性規(guī)劃問題的數(shù)學(xué)表達(dá)式： nnxcxcxcf2211max(min) s.t 11212111),(bxaxaxann22222121),(bxaxaxannmnmnmmbxaxaxa),(22110,21nxxx第5頁/共97頁6例3：生產(chǎn)組織與計劃問題 設(shè)有m種資源，第i(i=1,2,m)種資源的現(xiàn)存量為 ，現(xiàn)要生產(chǎn)n種產(chǎn)品，已知生產(chǎn)j(j=1,2,n)種產(chǎn)品時

4、，每單位產(chǎn)品需要第i種資源量為 ，而每單位j種產(chǎn)品可得利潤 ，問如何組織生產(chǎn)才能使利潤最大？ ibijajc 解：用 表示生產(chǎn)第j(j=1,2,n)種產(chǎn)品的計劃數(shù)， jx上述問題可歸結(jié)為如下的數(shù)學(xué)問題： njjjxc1maxts.mibxainjjij2 . 11njxj2 . 10第6頁/共97頁7 二、整數(shù)規(guī)劃模型對于線性規(guī)劃： njxmibxaxcfjnjijijnjjj2 , 102 , 1min11 決策變量是連續(xù)變量，最優(yōu)解可能是小數(shù)或分?jǐn)?shù)。 第7頁/共97頁8 但是在許多實際問題中，往往要求所得的解為整數(shù)，例如投資項目的選擇、機器的臺數(shù)、完成工作的人數(shù)、裝貨的車數(shù)等，分?jǐn)?shù)和小數(shù)的

5、答案就沒有現(xiàn)實意義了。 在現(xiàn)性規(guī)劃中，若限制 (j=1,2,n)是非負(fù)整數(shù)，則這種線性規(guī)劃問題稱為整數(shù)規(guī)劃問題。 jx為整數(shù)為整數(shù)如如212112121,0,115851215maxxxxxxxxxxf第8頁/共97頁9 例4：分配問題 假設(shè)某工廠用m臺機床加工n種零件。在一個生產(chǎn)周期內(nèi)，第i(i=1,2,m)臺機床只能工作 個機時，而第j(j=1,2,n)種零件必須完成 個，又第i臺機床加工第j種零件所需機時和成本分別為 （機時個）和 （元個）。問在這個生產(chǎn)周期內(nèi)怎樣安排各機床的生產(chǎn)任務(wù)，才能使得既完成加工任務(wù)，又使總的加工成本最少？ iajbijtijc 解：在一個生產(chǎn)周期內(nèi)，假設(shè)第i臺機

6、床加工第j種零件的個數(shù)為 。 ijx由于 是零件個數(shù)，因此 必須是非負(fù)整數(shù)， ijxijx第9頁/共97頁10本問題的數(shù)學(xué)模型為： minjijijxc11mints.injijijaxt1mi2 , 1jmiijbx 1nj2 , 1 為為非非負(fù)負(fù)整整數(shù)數(shù)ijx第10頁/共97頁11三、非線性規(guī)劃模型非線性規(guī)劃模型的一般形式為： )2(., 2 , 10)(.miXgtsi)3(., 2 , 10)(ljXhiDX 為為可可行行集集其其中中nTnRDxxxX,),(21 f(X)為目標(biāo)函數(shù)， (2)、(3)為約束條件， (2)為不等式約束，(3)為等式約束；若只有(1)稱為無約束問題。 )

7、1 ()(minXf第11頁/共97頁1232321213215),(minxxxxxxxxf如如0516223121xxxxx010312221xxxx第12頁/共97頁13例5：容器的設(shè)計問題 某公司專門生產(chǎn)儲藏用容器，定貨合同要求該公司制造一種敞口的長方體容器，容積恰好為12立方米，該容器的底必須為正方形，容器總重量不超過68公斤。已知用作容器四壁的材料為每平方米10 元，重3公斤；用作容器底的材料每平方米20元，重2公斤。試問制造該容器所需的最小費用是多少？ 模型建立 設(shè)該容器底邊長和高分別為 米、 米， 1x2x則問題的數(shù)學(xué)模型為 21212040)(minxxxXf（容器的費用）

8、. 0, 0,68212,12. .212121221xxxxxxxts（容器重量）（容器重量）（容器體積）（容器體積）第13頁/共97頁14一般來說，非線性規(guī)劃模型的求解要比線性規(guī)劃模型求解困難得多，雖然現(xiàn)在已經(jīng)發(fā)展了許多非線性規(guī)劃的算法，但到目前為止，還不象線性規(guī)劃那樣有通用的單純形算法，而是各種算法都有自己特定的適用范圍，如求解法有：最速下降法、牛頓法、可行方向法、懲罰函數(shù)法等。盡管如此，非線性規(guī)劃的實際應(yīng)用還是相當(dāng)廣泛的。第14頁/共97頁15 5.2 實際問題中的優(yōu)化模型一、投資策略 某部門現(xiàn)有資金10萬元，五年內(nèi)有以下投資項目供選擇： 項目A,從第一年到第四年每年初投資，次年末收回

9、本金且獲利15%； 項目B，第三年初投資，第五年末收回本金且獲利25%，最大投資額為4萬元； 項目C，第二年初投資，第五年末收回本金且獲利40%，最大投資額為3萬元； 項目D，每年初投資，年末收回本金且獲利6%。問如何確定投資策略使第五年末本息總額最大。第15頁/共97頁16問題的目標(biāo)函數(shù)是第五年末的本息總額， 決策變量是每年初各個項目的投資額， 約束條件是每年初擁有的資金。 用ijx表示第i年初（5 , , 2 , 1i）項目4 , 3 , 2 , 1(jj分別代表A,B,C,D)的投資額， 根據(jù)所給條件只有下表1列出的ijx才是需要求解的。 項目 年份 A B C D 1 2 3 4 5

10、11x21x31x41x32x23x14x24x34x44x54x第16頁/共97頁17 因為項目D 每年初可以投資，且年末能收回本息，所以每年初都應(yīng)把資金全部投出去， 項目A,從第一年到第四年每年初投資，次年末收回本金且獲利15%； 項目B，第三年初投資，第五年末收回本金且獲利25%，最大投資額為4萬元； 項目C，第二年初投資，第五年末收回本金且獲利40%，最大投資額為3萬元； 項目D，每年初投資，年末收回本金且獲利6%。由此可得如下的約束條件： 第一年初： 101411 xx第二年初： 1424232106. 1xxxx第三年初 241134323106. 115. 1xxxxx第四年初：

11、 3421444106. 115. 1xxxx第五年初： 44315406. 115. 1xxx項目B,C對投資額的限制： 3, 42332xx第17頁/共97頁18項目A,從第一年到第四年每年初投資，次年末收回本金且獲利15%； 項目B，第三年初投資，第五年末收回本金且獲利25%，最大投資額為4萬元； 項目C，第二年初投資，第五年末收回本金且獲利40%，最大投資額為3萬元； 項目D，每年初投資，年末收回本金且獲利6%。 每項投資應(yīng)為非負(fù)的： 0ijx第五年末本息總額為5432234106. 125. 140. 115. 1xxxxz將上條件等價變形如1424232106. 1xxxx006.

12、 124232114xxxx第18頁/共97頁19由此得投資問題的線性規(guī)劃模型如下：5432234106. 125. 140. 115. 1maxxxxxzs.t. 101411 xx006. 124232114xxxx006. 115.xxxx006. 115, 144413421xxxx006. 115. 1544431xxx3, 42332xx0ijx第19頁/共97頁20求解得4008. 0, 0,000. 3,5436. 3,1732. 6,8268. 3312423211411xxxxxx4609. 0, 0,0752. 4, 0,0000. 454444

13、13432xxxxx3750.14z 即第1年項目A,D分別投資3.8268和6.1732(萬元)；第2年項目A,C分別投資3.5436和3(萬元)；第3年項目A,B分別投資0.4008和4(萬元)；第4年項目A投資4.0752(萬元)；第5年項目D投資0.4609(萬元)；5年后總資金 14。375萬元，即盈利43.75%.第20頁/共97頁21二、貨機裝運問題 某架貨機有三個貨艙：前倉、中倉、后倉。三個貨艙所能裝載的貨物的最大重量和體積都有限制，如表3所示。并且，為了保持飛機的平衡，三個貨艙中實際裝載貨物的重量必須與其最大容許重量成比例。前倉中倉后倉重量限制（噸）10168體積限制（米3）

14、680087005300 現(xiàn)有四類貨物供該貨機本次飛行裝運，其有關(guān)信息如表4，最后一列指裝運后所獲得的利潤。第21頁/共97頁22重量（噸）空間（米3/噸）利潤（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物4123902850應(yīng)如何安排裝運，使該貨機本次飛行獲利最大？模型假設(shè) 問題中沒有對貨物裝運提出其它要求，我們可作如下假設(shè)： 1）每種貨物可以分割到任意小；2）每種貨物可以在一個或多個貨艙中任意分布；第22頁/共97頁233）多種貨物可以混裝，并保證不留空隙。模型建立決策變量： ijx表示第i種貨物裝入第j個貨艙的重量（噸）， 貨艙j=1,2,3分別表

15、示前倉、中倉、后倉。 決策目標(biāo)是最大化總利潤，即)(3800)(3100232221131211xxxxxxZMax)(2850)(3500434241333231xxxxxx)13(約束條件包括以下4個方面：1）從裝載的四種貨物的總重量約束，即)14(18131211xxx第23頁/共97頁24)15(15232221xxx)16(23333231xxx)17(12434241xxx2）三個貨艙的重量限制，即)18(1041312111xxxx)19(1642322212xxxx)20(843332313xxxx3）三個貨艙的空間限制，即)21(68003905806504804131211

16、1xxxx)22(870039058065048042322212xxxx)23(530039058065048043332313xxxx第24頁/共97頁254）三個貨艙裝入重量的平衡約束，即)24(81610433323134232221241312111xxxxxxxxxxxx模型求解將以上模型輸入LINDO求解，可以得到：第25頁/共97頁26OBJECTIVE FUNCTION VALUE1) 121515.8VARIABLE VALUE REDUCED COSTX11 0.000000 400.000000X12 0.000000 57.894737X13 0.000000 400

17、.000000X21 10.000000 0.000000X22 0.000000 239.473679X23 5.000000 0.000000X31 0.000000 0.000000X32 12.947369 0.000000X33 3.000000 0.000000X41 0.000000 650.000000X42 3.052632 0.000000X43 0.000000 650.000000實際上，不妨將所得最優(yōu)解作四舍五入， 第26頁/共97頁27結(jié)果為 貨物2裝入前倉10噸、裝入后倉5噸； 貨物3裝入中倉13噸、裝入后倉3噸； 貨物4裝入中倉3噸， 最大利潤約121516元。

18、 評注 初步看來，本例與運輸問題類似，似乎可以把4種貨物看成4個供應(yīng)點，3個貨艙看成3個需求點（或者反過來，把貨艙看成供應(yīng)點，貨物看成需求點）。但是，這里對供需量的限制包括兩個方面：重量限制和空間限制，且有裝載均勻要求，因此它只能看成是運輸問題的一種變形和擴展。 第27頁/共97頁28三、鋼管下料問題 某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客的要求切割后售出，從鋼管廠進(jìn)貨時得到的原料鋼管都是19m。（1）現(xiàn)有一客戶需要50根4 m、20根6 m和15根8 m的鋼管，應(yīng)如何下料最節(jié)省？（2）零售商如果采用的不同切割模式太多，將會導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的

19、不同切割模式不能超過3種。此外，該客戶除需要（1）中的三種鋼管外，還需要10根5 m的鋼管。應(yīng)如何下料最節(jié)省。問題（1）的求解問題分析 首先，應(yīng)當(dāng)確定哪些切割模式是可行的。 第28頁/共97頁29 所謂一個切割模式，是指按照客戶需要在原料鋼管上安排切割的一種組合。 例如：我們可以將19 m的鋼管切割成3根4 m的鋼管，余料為7 m；或者將19 m的鋼管切割成4 m、6 m和8 m的鋼管各1根，余料為1 m。 顯然，可行的切割模式是很多的。其次，應(yīng)當(dāng)確定哪些切割模式是合理的。 通常假設(shè)一個合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸。 例如：將19 m的鋼管切割成3根4 m的鋼管

20、，余料為7 m，可進(jìn)一步將7m的余料切割成4m 鋼管（余料為3 m），或者將7 m的余料切割成6 m鋼管（余料為1 m）。 第29頁/共97頁30 在這種合理性假設(shè)下，切割模式一共有7種，如表9所示。4 m鋼管根數(shù)6 m鋼管根數(shù)8 m鋼管根數(shù)余料（m）模式14003模式23101模式32013模式41203模式51111模式60301模式70023 問題化為在滿足客戶需要的條件下，按照哪些種合理的模式，切割多少根原料鋼管，最為節(jié)省。 而所謂節(jié)省，可以有兩種標(biāo)準(zhǔn)： 第30頁/共97頁31一是切割后剩余的總余料量最小， 二是切割原料鋼管的總根數(shù)最小。 下面將對這兩個目標(biāo)分別討論。模型建立決策變量

21、ix表示按照第i種模式（7 , 2, 1i ）切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。 決策目標(biāo) 以切割后剩余的總余料量最小為目標(biāo)，則由表9可得 ) 1 (333376543211xxxxxxxZMin以切割原料鋼管的總根數(shù)最少為目標(biāo)，則有)2(76543212xxxxxxxZMin第31頁/共97頁324 m鋼管根數(shù)6 m鋼管根數(shù)8 m鋼管根數(shù)余料（m）模式14003模式23101模式32013模式41203模式51111模式60301模式70023約束條件 為滿足客戶的需求，按照表9應(yīng)有 )3(5023454321xxxxx)4(20326542xxxx)5(152753xxx模型求

22、解第32頁/共97頁33 1將（1），（3），（4），（5）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入LINDO如下： Min 3x1+x2+3x3+3x4+x5+x6+3x7s.t. 4x1+3x2+2x3+x4+x5=50 x2+2x4+x5+3x6=20 x3+x5+2x7=15endgin7求解可以得到最優(yōu)解如下：第33頁/共97頁34OBJECTIVE FUNCTION VALUE1) 27.00000VARIABLE VALUE REDUCED COST X1 0.000000 3.000000 X2 12.000000 1.000000 X3 0.000000 3.000000

23、X4 0.000000 3.000000 X5 15.000000 1.000000 X6 0.000000 1.000000 X7 0.000000 3.000000 即按照模式2切割12根原料鋼管，按照模式5切割15根原料鋼管，共27根，總余料量為27m。 顯然，在總余料量最小的目標(biāo)下，最優(yōu)解將是使用余料盡可能小的切割模式（模式2和5的余料為1 m），這會導(dǎo)致切割原料鋼管的總根數(shù)較多。第34頁/共97頁35 2將（2）（5）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入LINDO求解，可以得到最優(yōu)解如下： OBJECTIVE FUNCTION VALUE1） 25.00000VARIABLE

24、VALUE REDUCED COST X1 0.000000 1.000000 X2 15.000000 1.000000 X3 0.000000 1.000000 X4 0.000000 1.000000 X5 5.000000 1.000000 X6 0.000000 1.000000 X7 5.000000 1.000000 即按照模式2切割15根原料鋼管、按模式5切割5根、按模式7切割5根、共25根，可算出總余料量為35 m。 與上面得到的結(jié)果相比，總余料量增加了8 m，但是所用的原料鋼管的總根數(shù)減少了2根。 在余料沒有用途情況下，通常選擇總根數(shù)最小為目標(biāo)。 第35頁/共97頁36問題

25、（2）的求解問題（2）：零售商如果采用的不同切割模式太多，將會導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的不同切割模式不能超過3種。此外，該客戶除需要（1）中的三種鋼管外，還需要10根5 m的鋼管。應(yīng)如何下料最節(jié)省。問題分析 按照（1）的思路，可以通過枚舉法首先確定哪些切割模式是可行的。但由于需求的鋼管規(guī)格增加到4種，所以枚舉法的工作量較大。 下面介紹的整數(shù)非線性規(guī)劃模型，可以同時確定切割模式和切割計劃，是帶有普遍性的方法。 第36頁/共97頁37 同（1）類似，一個合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸（本題中為4 m），切割計劃中只使用合理的切

26、割模式，而由于本題中參數(shù)都是整數(shù)，所以合理的切割模式的余量不能大于3 m。 此外，這里我們僅選擇總根數(shù)最小為目標(biāo)進(jìn)行求解。模型建立決策變量 由于不同切割模式不能超過3種， 可以用ix表示按照第i種模式（3, 2, 1i ）切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。 第37頁/共97頁38 設(shè)所使用的第i種切割模式下每根原料鋼管生產(chǎn)4 m，5 m，6 m和8 m的鋼管數(shù)量分別為iiiirrrr4321,（非負(fù)整數(shù)）。 決策目標(biāo) 切割原料鋼管的總根數(shù)最小，目標(biāo)為)6(321xxxMin約束條件 為滿足客戶的需求，應(yīng)有)7(50313212111xrxrxr)8(10323222121xrxrx

27、r)9(20333232131xrxrxr)10rxrxr第38頁/共97頁39 每一種切割模式必須可行、合理，所以每根原料鋼管的成品量不能超過19m，也不能少于16 m（余量不能大于3 m），于是)11(1986541641312111rrrr)12(1986541642322212rrrr)13(1986541643332313rrrr模型求解 在（7）（10）式中出現(xiàn)決策變量的乘積，是一個整數(shù)非線性規(guī)劃模型，雖然用LINGO軟件可以直接求解，但我們發(fā)現(xiàn)運行很長時間也難以得到最優(yōu)解。 為了減少運行時間，可以增加一些顯然的約束條件，從而縮小可行解的搜索范圍。 第39

28、頁/共97頁40 例如，由于3種切割模式的排列順序是無關(guān)緊要的，所以不妨增加以下約束)14(321xxx 又例如，我們注意到所需原料鋼管的總根數(shù)有著明顯的上界和下界。 首先，無論如何，原料鋼管的總根數(shù)不可能少于19158206105504根即至少需26根。 其次，考慮一種非常特殊的生產(chǎn)計劃： 第一種切割模式下只生產(chǎn)4m鋼管，一根原料鋼管切割成4根4 m鋼管，為滿足50根4 m鋼管的需求，需要13根原料鋼管； 第40頁/共97頁41 第二種切割模式下只生產(chǎn)5 m、6 m鋼管，一根原料鋼管切割成1根5 m鋼管和2根6 m鋼管，為滿足10根5 m和20根6 m鋼管的需求，需要10根原料鋼管； 第三種

29、切割模式下只生產(chǎn)8 m鋼管，一根原料鋼管切割成2根8 m鋼管，為滿足15根8 m鋼管的需求，需要8根原料鋼管。 于是滿足要求的這種生產(chǎn)計劃共需13+10+8=31根原料鋼管，這就得到了最優(yōu)解的一個上界。 所以可增加以下約束)15(3126321xxx將（6）（15）構(gòu)成的模型輸入LINGO如下：第41頁/共97頁42model：min=x1+x2+x3；x1*r11+x2*r12+x3*r13=50；x1*r21+x2*r22+x3*r23=10；x1*r31+x2*r32+x3*r33=20；x1*r41+x2*r42+x3*r43=15；4*r11+5*r21+6*r31+8*r41=19

30、；4*r12+5*r22+6*r32+8*r42=19；4*r13+5*r23+6*r33+8*r43=16；4*r12+5*r22+6*r32+8*r42=16；4*r13+5*r23+6*r33+8*r43=16；x1+x2+x3=26；x1+x2+x3=x2；x2=x3；gin(x1) ；gin(x2) ；gin(x3) ；gin(r11) ；gin(r12) ；gin(r13) ；gin(r21) ；gin(r22) ；gin(r23) ；gin(r31) ；gin(r32) ；gin(r33) ；gin(r41) ；gin(r42) ；gin(r43) ；end第42頁/共97頁43

31、 注：LINGO軟件用于求解非線性規(guī)劃（包括含有整數(shù)變量的），輸入總是以“model：”開始，以“end”結(jié)束；中間的語句必須以“；”分開。約束中“gin(x1)”表示x1為整數(shù)，其他類似（如果要表示x1為0-1整數(shù)，應(yīng)該用“int(x1)”）。在LINGO8.0版本中，缺省設(shè)置假定所有變量非負(fù)，所以上面的輸入中沒有關(guān)于變量非負(fù)的顯式約束。經(jīng)過運行（一般需要幾分鐘），得到輸出如下：第43頁/共97頁44Local optimal solution found at iteration： 12211Objective value： 28.00000 Variable Value Reduced

32、Cost X1 10.00000 0.000000 X2 10.00000 2.000000 X3 8.00000 1.000000 R11 3.00000 0.000000 R12 2.00000 0.000000 R21 0.00000 0.000000 R22 1.00000 0.000000 R31 1.00000 0.000000 R32 1.00000 0.000000 R33 0.00000 0.000000 R41 0.00000 0.000000 R42 0.00000 0.000000 R43 2.00000 0.000000第44頁/共97頁45 即按照模式1，2，3分別

33、切割10，10，8根原料鋼管，使用原料鋼管總根數(shù)為28根， 第一種切割模式下一根原料鋼管切割成3根4m鋼管和1根6 m鋼管； 第二種切割模式下一根原料鋼管切割成2根4 m鋼管、1根5 m鋼管和1根6 m鋼管； 第三種切割模式下一根原料鋼管切割成2根8 m鋼管。第45頁/共97頁46 5.3 動態(tài)規(guī)劃模型例8：最短線路問題0A6A 問題：現(xiàn)選擇一條從 到 的鋪管線路，使總距離最短？ 若用窮舉法要算23222148種不同線路，比較這48種結(jié)果即可得出，但當(dāng)段數(shù)增加，且各段選擇也增加時，窮舉法將變得非常龐大，以至利用計算機都十分困難。 第46頁/共97頁47下面用動態(tài)規(guī)劃的方法計算最短線路問題的特性

34、： 如果最短線路在第k站通過點 ，則這一線路在由 出發(fā)到達(dá)終點的那一部分線路，對于從 點到達(dá)終點的所有可能選擇的不同線路來說，必定也是距離最短的。（反正法） kPkPkP 最短線路問題的這一特性啟示我們，從最后一段 開始，用從后向前逐步遞推的方法，求出各點到 的最短線路，最后求得從 到 的最短線路。 6A0A6A第47頁/共97頁48k6時： 設(shè) 表示由 到 的最短距離； )(56Af5A6A設(shè) 表示由 到 的最短距離； )(56Bf5B6A顯然 4)(56Af3)(56Bfk5時： 如果 表示由 到 的最短距離。 )(45Af4A6Amin)(45Af)(),()(),(56545654Bf

35、BAdAfAAd73543min（以下類似定義）（以下類似定義）第48頁/共97頁49最短線路是 654AAA)(45Bf53245min)(),()(),(min5654556545BfBBdAfABd最短線路是 654ABB93646min)(),()(),(min)(565455654545BfBCdAfACdCf最短線路是 654ABC第49頁/共97頁50k4時： 75272min)(),()(),(min)(454344543434BfBAdAfAAdAf最短線路是 6543ABBA69251min)(),()(),(min)(454344543434CfCBdBfBBdBf最短線

36、路是 6543ABBB第50頁/共97頁5189353min)(),()(),(min)(454344543434CfCCdBfBCdCf最短線路是 6543ABBCk3時： 136876min)(),()(),(min)(343233432323BfBAdAfAAdAf最短線路是 65432ABBAA第51頁/共97頁52106573min)(),()(),(min)(343233432323BfBBdAfABdBf最短線路是 65432ABBAB98363min)(),()(),(min)(343233432323CfCCdBfBCdCf最短線路是 65432ABBBC第52頁/共97頁5

37、3128468min)(),()(),(min)(343233432323CfCDdBfBDdDf最短線路是 65432ABBCDk2時： 1396103131min)(),()(),()(),(min)(23212232122321212CfCAdBfBAdAfAAdAf最短線路是 654321ABBABA第53頁/共97頁541612697108min)(),()(),()(),(min)(23212232122321212DfDBdCfCBdBfBBdBf最短線路是 出發(fā)點只有 0A18163135min)(),()(),(min)(121011210101BfBAdAfAAdAf最短線

38、路是 6543210ABBABAA最短距離為18。654321ABBBCB第54頁/共97頁55說明 1)此例揭示了動態(tài)規(guī)劃的基本思想。 2)動態(tài)規(guī)劃方法比窮舉法（48種）大大節(jié)省了計算量。 3)計算結(jié)果不僅得到了 到 的最短線路和最短距離，而且得到了其它各點到 的最短線路和最短距離，這對于很多實際問題來說是很有用處的。 0A6A6A動態(tài)規(guī)劃法求解的數(shù)學(xué)描述 討論動態(tài)規(guī)劃中最優(yōu)目標(biāo)函數(shù)的建立，一般有下列術(shù)語和步驟： 、階段 用動態(tài)規(guī)劃求解多階段決策系統(tǒng)時，要根據(jù)具體情況，將系統(tǒng)適當(dāng)?shù)胤殖扇舾蓚€階段，以便分若干個階段求解，描述階段的變量稱為階段變量。 第55頁/共97頁56 上例分六個階段，是一

39、個六階段的決策過程。例中由系統(tǒng)的最后階段向初始階段求最優(yōu)解的過程稱為動態(tài)規(guī)劃的逆推解法。 、狀態(tài)狀態(tài)表示系統(tǒng)在某一階段所處的位置或狀態(tài)。 上例中第一階段有一個狀態(tài)， ；即即0A第二階段有兩個狀態(tài)， ；即即,11BA 過程的狀態(tài)可用狀態(tài)變量 來描述，某個階段所有可能狀態(tài)的全體可用狀態(tài)集合來描述， kx01AS 如如,22223112DCBASBAS第56頁/共97頁57、決策 某一階段的狀態(tài)確定之后，從該狀態(tài)演變到下一階段某一狀態(tài)所作的選擇稱為決策。描述決策的變量稱為決策變量 如上例中在第k階段用 表示處于 狀態(tài)時的決策變量。 )(kkxukx決策變量限制的范圍稱為允許決策集合。 用 表示第k階

40、段從 出發(fā)的決策集合。 )(kkxDkx、策略 由每階段的決策 (i1,2,n)組成的決策函數(shù)序列稱為全過程策略或簡稱策略，用p表示， )(iixu)(,),(),()(22111nnxuxuxuxP即即第57頁/共97頁58 由系統(tǒng)的第k個階段開始到終點的決策過程稱為全過程的后部子過程，相應(yīng)的策略稱為后部子過程策略。 用 表示k子過程策略， )(kkxP)(,),(),()(11nnkkkkkkxuxuxuxP即即 對于每一個實際的多階段決策過程，可供選擇的策略有一定的范圍限制，這個范圍稱為允許策略集合。 允許策略集合中達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。 、狀態(tài)轉(zhuǎn)移 某一階段的狀態(tài)變量及決策變

41、量取定后，下一階段的狀態(tài)就隨之而定。 第58頁/共97頁59 設(shè)第k個階段的狀態(tài)變量為 ，決策變量為 ，則第k+1個階段的狀態(tài) 用 表示從k階段到k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱它為狀態(tài)轉(zhuǎn)移方程。kx)(kkxu1kx),(1kkkkuxTx、階段效益 系統(tǒng)某階段的狀態(tài)一經(jīng)確定，執(zhí)行某一決策所得的效益稱為階段效益，它是整個系統(tǒng)效益的一部分，是 階段狀態(tài)和 階段決策的函數(shù)，記為 kxku),(kkkuxW、指標(biāo)函數(shù) 指標(biāo)函數(shù)是系統(tǒng)執(zhí)行某一策略所產(chǎn)生的效益的數(shù)量表示，根據(jù)不同的實際問題，效益可以是利潤、距離、產(chǎn)量或資源的耗量等。 第59頁/共97頁60 指標(biāo)函數(shù)可以定義在全過程上，也可以定義在后部子過

42、程上。指標(biāo)函數(shù)往往是各階段效益的某種和式，取最優(yōu)策略時的指標(biāo)函數(shù)稱為最優(yōu)策略指標(biāo)。 如上例中， 表示從 出發(fā)到終點 的最優(yōu)策略指標(biāo)。 )(45Af4A6A上例中 顯然為零，稱它為邊值條件。 )(66Af 而動態(tài)規(guī)劃的求解就是對kn,n-1,2,1逐級求出最優(yōu)策略指標(biāo)的過程。 、動態(tài)規(guī)劃的基本方程)(),(min)(11kkkkkukkxfuxWxfk第60頁/共97頁61例9：機器負(fù)荷分配問題 某種機器可以在高低兩種負(fù)荷下生產(chǎn)，年產(chǎn)量與年初投入生產(chǎn)的機器數(shù)有關(guān)。在高負(fù)荷下生產(chǎn)時，年產(chǎn)量 ，式中 為投入生產(chǎn)的機器數(shù)，年終的完好機器數(shù)為 ，稱系數(shù)0.7為機器完好率。在低負(fù)荷下生產(chǎn)時，年產(chǎn)量 ，式中

43、 為投入生產(chǎn)的機器數(shù)，機器完好率為0.9，設(shè)開始時，完好的機器數(shù)為 臺，要求制定一個五年計劃，在每年開始時決定如何重新分配完好機器在兩種不同負(fù)荷下工作的數(shù)量，使五年的總產(chǎn)量最高。 118us 1u17 . 0 u225us 2u10001x第61頁/共97頁62解：此問題與上例類似。 設(shè)階段變量k表示年度； 狀態(tài)變量 是第k年初擁有的完好機器數(shù)（也是第k-1年度末完好機器數(shù)）。 kx 決策變量 規(guī)定為第k年度中分配在高負(fù)荷下生產(chǎn)的機器數(shù)。 ku 于是 是該年度分配在低負(fù)荷下生產(chǎn)的機器數(shù)。 kkux k=2 k=3 k=4 k=5 1k1x2x3x4x5x 1u2u3u4u5u第62頁/共97頁

44、63記 表示第k年到第五年末的最高總產(chǎn)量)(kkxfk5時)(58max)(55505555uxuxfxu5550835max55xuxxu最優(yōu)點最優(yōu)點5*5xu 這說明第5年初要把全部完好機器投入高負(fù)荷下生產(chǎn)。 k4時4444452 . 09 . 0)(9 . 07 . 0uxuxux因為因為)()(58max)(5544404444xfuxuxfxu所所以以)2 . 09 . 0(835max4444044uxuxxu第63頁/共97頁6444406 .134 . 12 .12max44xuxxu最優(yōu)點最優(yōu)點4*4xu k3時3333342 . 09 . 0)(9 . 07 . 0uxux

45、ux因為因為)()(58max)(4433303333xfuxuxfxu所所以以)2 . 09 . 0(6 .1335max3333033uxuxxu33305 .1728. 024.17max33xuxxu最優(yōu)點最優(yōu)點3*3xu 第64頁/共97頁65k2時2222232 . 09 . 0)(9 . 07 . 0uxuxux因為因為)()(58max)(3322202222xfuxuxfxu所所以以)2 . 09 . 0(5 .1735max2222022uxuxxu22208 .205 . 075.20max22xuxxu最優(yōu)點最優(yōu)點0*2uk1時10001x因為因為1111122 . 0

46、9 . 0)(9 . 07 . 0uxuxux)()(58max)1000(221110111xfuxufxu所所以以)2 . 09 . 0(8 .2035max1111011uxuxxu第65頁/共97頁66)2 . 09 . 0(8 .2035max1111011uxuxxu16. 172.23max11011uxxu2370010007 .237 .231x最優(yōu)點最優(yōu)點0*1u 由此知五年最高總產(chǎn)量為23700再由上遞推知 10001x0*1u9002x0*2u8103x810*3u5674x567*4u3975x397*5u第66頁/共97頁67高負(fù)荷生產(chǎn)的完好機器的最優(yōu)組合簡記：39

47、7,567,810, 0, 0,*5*2*1uuu 這表明在前兩年年初全部完好機器投入低負(fù)荷生產(chǎn)，后三年年初全部完好機器投入高負(fù)荷生產(chǎn)。 第五年末的完好機器數(shù)為 0.7397278臺 在此例中，我們僅考慮最高產(chǎn)量，而未考慮五年計劃后的完好機器數(shù)。 問題1：若計劃為n個年度，怎樣決策？ 問題2：若要求在第5年末完好的機器數(shù)為500臺，如何決策使5年總產(chǎn)量最高？ 第67頁/共97頁68這類問題稱為固定終端問題1x2x3x4x5x5006x1u2u3u4u5u由上討論知：狀態(tài)轉(zhuǎn)移方程仍為 ) 1 (2 . 09 . 0)(9 . 07 . 01kkkkkkuxuxux 表示第k年初開始到第5年末的最

48、高產(chǎn)量，稱為最優(yōu)值函數(shù)，其遞推關(guān)系為 )(kkxf)2()2 . 09 . 0()(58(max)(10kkkkkkxukkuxfuxuxfkkk=1,2,3,4,50)(66xf第68頁/共97頁69其中 為第k段的效益值，即第k年的產(chǎn)量。 )(58),(kkkkkkuxuuxy 表示第6年的產(chǎn)量不計算在總產(chǎn)量之內(nèi)，故為零。 0)(66xf由假設(shè) ， 5006x又根據(jù)(1)得 5562 . 09 . 0uxx一般地，當(dāng) 確定后，選擇 來確定 ，現(xiàn)在 已經(jīng)給定，故 已經(jīng)沒有選擇余地，它由 和 確定。 5x5u6x6x5u6x5x于是25005 . 455 . 45655xxxu第69頁/共97

49、頁70由(2)可知035max)(5505555uxxfxu)25005 . 4(3555xx75005 .185x)2 . 09 . 0(35max)(4454404444uxfuxxfxu7500)2 . 09 . 0(5 .1835max4444044uxuxxu.max750070652144044uxxu75007 .214x最優(yōu)值 0*4u第70頁/共97頁717500)2 . 09 . 0(7 .2135max)(333303333uxuxxfxu75005 .243x最優(yōu)值 0*3u類似地得到 75007 .21)(222xxf0*2u75004 .29)(111xxf0*1u

50、21900750029400)1000(1f這是五年最高產(chǎn)量 這表明，如果限定五年后的完好機器數(shù)為500臺，則總產(chǎn)量低于無限制的情況，最優(yōu)策略也相應(yīng)有所變化，由第一年到第四年全部完好機器投入低負(fù)荷生產(chǎn)。第71頁/共97頁72 為了計算第5年投入高負(fù)荷生產(chǎn)的完好機器數(shù) ，先計算 5u9009 . 012xx8109 . 023xx7299 . 034xx6569 . 045xx所以 45225005 . 455xu 即第5年有452臺機器投入高負(fù)荷生產(chǎn)，其余投入低負(fù)荷生產(chǎn)。 第72頁/共97頁733 存貯模型 工廠為了連續(xù)生產(chǎn)必須貯存一些原材料，商店為了連續(xù)銷售必須貯存一些商品，象這類的實際問題

51、當(dāng)然要考慮其經(jīng)濟(jì)效益。因此就必須考慮一個貯存多少的問題。原料、商品存得太多，貯存費用高，存得太少則無法滿足需求。 如：元。每次的訂貨費為元，件，每件每天儲存費為某商品每天出售10001010元。每天費用件，則無儲存費，次訂、若每天訂一次貨，每1000101件，則儲存費為天訂一次貨，每次訂、若每100102101010801090元4500第73頁/共97頁74平均每天的費用1010004500）（元550件，則儲存費為天訂一次貨，每次訂、若每30030310101028010290元43500平均每天的費用30100043500）（元1483最好？問題：多少天訂一次貨第74頁/共97頁75 問

52、題：尋求一個好的存貯策略，即多長時間訂一次貨，每次訂多少貨才能使總費用最少？ 模型一：不允許缺貨的存貯模型建模目的： 在單位時間的需求量為常數(shù)的情況下，制定最優(yōu)存貯策略，即多長時間訂一次貨，每次訂多少貨，使總費用最小。 模型假設(shè)、每次訂貨費為 ，每天每噸貨物貯存費為 ； 1c2c、每天的貨物需求量為r噸； 、每T天訂貨Q噸，當(dāng)貯存量降到零時，訂貨立即到達(dá)（即不允許缺貨）。 第75頁/共97頁76 對于第3條假設(shè)中訂貨可以瞬時完成，可解釋為由于需求是確定和已知的，只要提前訂貨使得貯存量為零時立即進(jìn)貨就行了，當(dāng)然，貯存量降到零不符合實際生產(chǎn)需要，應(yīng)該有一個最低庫存量，可以認(rèn)為模型中的貯存量是在這個

53、最低存量之上計算的。 模型建立 訂貨周期T、訂貨量Q與每天需求量r之間滿足 QrT (3-1) 訂貨后貯存量由Q均勻地下降，記任意時刻t的貯存量為q，則q(t)的變化規(guī)律可以用圖表示： 第76頁/共97頁77 考察一個訂貨周期的總費用： 訂貨費為 ； 1c貯存費是 Tdttqc02)(因為積分值恰是圖中三角形面積A，顯然A 。 QT21第77頁/共97頁78由(3-1)式可知一個訂貨周期T內(nèi)的總費用為)23(21221rTccc于是平均每天的費用為)33(21)(21rTcTcTcTc 所以制定最優(yōu)貯存策略可歸結(jié)為：求訂貨周期T,使C(T)最小。 思考：為什么不用 作為目標(biāo)函數(shù)？ c 利用微分

54、法， 得得：令令0dTdc)43(221rccT第78頁/共97頁79再根據(jù)(3-1)式有 )53(221crcQ (3-5)式是經(jīng)濟(jì)理論中著名的經(jīng)濟(jì)訂貨批量公式（簡稱公式）。 (3-5)式表明：訂貨費越高，需求量r越大，訂貨批量Q應(yīng)越大；貯存費越高，則每次訂貨批量應(yīng)越小。這些當(dāng)然符合常識，但公式中平方根關(guān)系是憑常識難以得到的。 說明：貨物本身的價格不影響最優(yōu)貯存策略。 因為若記每噸貨物價格為k，則一周期T的總費用 中應(yīng)添加一項kQ，由于QrT，所以(3-3)中增加一常數(shù)項kr對求解結(jié)果(3-4),(3-5)無影響。 c第79頁/共97頁80 例1.某商店有甲商品出售，每單位甲商品價格500元

55、，其存貯費每年為價格的20，甲商品每次訂購費需20元，顧客對甲商品的年需求量為365單位，而且需求率為常數(shù)（即顧客每天需求商品1單位），在不缺貨的條件下，求最優(yōu)策略。 解：以年為單位，則需求速度： r365 201c100%205002c于是訂貨批量 12100365202221crcQ（單位） 訂貨周期 （天天）年年1236512rQT第80頁/共97頁81即每隔12天訂一次貨，每次訂12個單位為最優(yōu)策略。 若按天為單位： 則r1， 201c365100365%205002c)(123651001202221單單位位crcQ)(12112天天T這與以年為單位結(jié)果相同。第81頁/共97頁82模

56、型二：允許缺貨的存貯模型 允許缺貨就是企業(yè)或商店可以在存貯降到零后，還可以再等一段時間訂貨。缺貨時因失去銷售機會而使利潤減少，減少的利潤可以視為因缺貨而付出的費用，稱缺貨費；于是此模型的第1,2條假設(shè)與不允許缺貨的存貯模型相同，而第3條該為： 每隔T天訂貨Q噸，允許缺貨，每天每噸貨物缺貨費為 。 3c缺貨時貯存量視作負(fù)值，q(t)圖形如下： 第82頁/共97頁83 貨物在t 時售完，有一段時間缺貨（這時需求量仍為r），在tT時下一次訂貨量Q到達(dá)。1T于是 1rTQ 一個訂貨周期T內(nèi)的總費用：訂貨費 1c 貯存費 102)(Tdttqc 由圖知 10121)(QTAdttqT缺貨費 dttqcT

57、T1)(3由圖知21)(21)(1TTrBdttqTT所以總費用 213121)(2121TTrcQTccc第83頁/共97頁84每天平均費用TTTrcTQTcTcTcQTC2)(2),(213121rTQrTcrTQcTc2)(223221下面問題是當(dāng)T,Q為何值時，使C(T,Q)最小。利用微分法， 0, 0QcTc令令求出T,Q的最優(yōu)值，記為 QT,332212cccrccT323212ccccrcQ第84頁/共97頁85)( 1332ccc 記記則與不允許缺貨的存貯模型相比TT QQ TT 顯然顯然QQ 即：允許缺貨時訂貨周期應(yīng)增大，而訂貨批量應(yīng)減少。 當(dāng)缺貨費 越大時,3c 和 越接近

58、T和Q。 TQ時時，當(dāng)當(dāng)3cTTQQ 這個結(jié)果是合理的，因為 即缺貨造成的損失無限變大，相當(dāng)于不允許缺貨。 3c第85頁/共97頁86問題 1、某廠每天需要角鋼100噸，目前每月訂購一次，每次訂購的費用為2500元，每天每噸角鋼的儲存費為0.18元。 （1）如果不允許缺貨，問是否應(yīng)改變訂貨策略，改變后能節(jié)省多少費用。 （2）如果允許缺貨，每天每噸的缺貨費為0.4元，試制訂訂策略。 2、飲料廠某種飲料生產(chǎn)能力為5000L/天，需求為2000L/天，每次生產(chǎn)準(zhǔn)備費為300元，生產(chǎn)成本為10元/L，而資金為貸款，貸款月息為3%，試制訂生產(chǎn)計劃。 第86頁/共97頁874 森林救火的數(shù)學(xué)模型 問題：森林失火了，消防站接到報警后應(yīng)派多少消防隊員前去救火？ 問題分析 森