運籌學在數(shù)學建模中的應(yīng)用

1、2024年3月19日星期二8時16分32秒,,運籌學在數(shù)學建模中的應(yīng)用,一、運籌學概況二、線性規(guī)劃三、整數(shù)規(guī)劃與多目標規(guī)劃四、圖論與網(wǎng)絡(luò)優(yōu)化五、動態(tài)規(guī)劃六、賽題選講,2024年3月19日星期二8時16分32秒,2024年3月19日星期二8時16分32秒,運 籌 學 概 況,運籌學的定義運籌學簡史運籌學的主要內(nèi)容及應(yīng)用重點運籌學應(yīng)用步驟運籌學在數(shù)學建模競賽中的地位,2024年3月19日星期二8時16分32秒,

2、運籌學是一種給出問題不壞的答案的藝術(shù)，否則的話問題的結(jié)果會更壞。,一、運籌學的定義,☆ 運籌學(《辭海》)：20世紀40年代開始形成的一門學科，主要研究經(jīng)濟活動與軍事活動中能用數(shù)量來表達的有關(guān)運用、籌劃與管理方面的問題，它根據(jù)問題的要求，通過數(shù)學的分析與運算，做出綜合性合理安排，以達到較經(jīng)濟有效地使用人力物力.,2024年3月19日星期二8時16分32秒,☆ 作為一門定量優(yōu)化決策科學，起源于第二次世界戰(zhàn)，英文原意Operation　

3、Research；,二、運籌學簡史,深水炸彈的釋放問題防空系統(tǒng)的預(yù)警問題,,運籌學的一些分支,英美海空軍作戰(zhàn)參謀部組成了運籌學研究小組,,二戰(zhàn)中,2024年3月19日星期二8時16分32秒,二戰(zhàn)后,軍事,工、商業(yè)領(lǐng)域,,,存儲論、決策科學、預(yù)測科學等分支,☆ 20世紀50年代中期錢學森和許國志教授引入 “運用學”,＊ 1957年 取 “運籌”二字，將OR正式命名為“運籌學” 開始應(yīng)用于建筑業(yè)和紡織業(yè),《史記》中“夫

4、運籌帷幄之中，決勝千里之外”,2024年3月19日星期二8時16分32秒,線性規(guī)劃,數(shù)學規(guī)劃,非線性規(guī)劃,整數(shù)規(guī)劃,動態(tài)規(guī)劃,多目標規(guī)劃,組合優(yōu)化,最優(yōu)計數(shù)問題,網(wǎng)絡(luò)優(yōu)化,排序問題,統(tǒng)籌圖,隨機優(yōu)化,對策論,排隊論,庫存論,決策分析,可靠性分析,,,,,三、運 籌 學 主 要 內(nèi) 容,2024年3月19日星期二8時16分32秒,下的最大值或最小值，,將一個優(yōu)化問題用數(shù)學式子來描述，即求函數(shù),在約束條件,和,,2024年

5、3月19日星期二8時16分32秒,數(shù)學規(guī)劃問題的一般形式,“受約束于”之意,2024年3月19日星期二8時16分32秒,網(wǎng)絡(luò)優(yōu)化研究解決生產(chǎn)組織、計劃管理中諸如最短路徑問題、最小連接問題、最小費用流問題、最優(yōu)分派問題及關(guān)鍵線路圖等。特別在計劃和安排大型復(fù)雜工程時，網(wǎng)絡(luò)技術(shù)是重要的工具,2024年3月19日星期二8時16分32秒,排隊論是20世紀初由丹麥數(shù)學家Erlang應(yīng)用數(shù)學方法在研究電話話務(wù)理論過程中而發(fā)展起來的一門學科，排隊論

6、也稱隨機服務(wù)系統(tǒng)理論，排隊論是定量的研究排隊問題，尋找系統(tǒng)內(nèi)在規(guī)律，尋找供求關(guān)系平衡的最優(yōu)方案。,如機器等待修理、船舶等待裝卸、顧客等待服務(wù)等,2024年3月19日星期二8時16分32秒,對策論研究具有利害沖突的各方，如何制定對自己有利從而戰(zhàn)勝對手的斗爭策略,田忌賽馬,2024年3月19日星期二8時16分32秒,運籌學的應(yīng)用重點,1.市場銷售在廣告預(yù)算和媒體的選擇、競爭性定價、新產(chǎn)品開發(fā)、銷售計劃的制定等方面。如美國杜邦公司在五十年

7、代起就非常重視將作業(yè)研究用于研究如合做好廣告工作、產(chǎn)品定價和新產(chǎn)品的引入。,2. 生產(chǎn)計劃在總體計劃方面主要是從總體確定生產(chǎn)、儲存和勞動力的配合等計劃以適應(yīng)變動的需求計劃，主要用線性規(guī)劃和仿真方法等。此外，還可用于生產(chǎn)作業(yè)計劃、日程表的編排等。還有在合理下料、配料問題、物料管理等方面的應(yīng)用。,2024年3月19日星期二8時16分32秒,3. 庫存管理存貨模型將庫存理論與計算器的物料管理信息系統(tǒng)相結(jié)合，主要應(yīng)用于多種物料庫存量的管理，

8、確定某些設(shè)備的能力或容量，如工廠的庫存、停車廠的大小、新增發(fā)電設(shè)備容量大小、計算機的主存儲器容量、合理的水庫容量等。,4. 運輸問題這里涉及空運、水運、公路運輸、鐵路運輸、捷運、管道運輸和廠內(nèi)運輸?shù)?。包括班次調(diào)度計劃及人員服務(wù)時間安排等問題。,2024年3月19日星期二8時16分32秒,5.財政和會計這里涉及預(yù)算、貸款、成本分析、定價、投資、證券管理、現(xiàn)金管理等。用得較多的方法是：統(tǒng)計分析、數(shù)學規(guī)劃、決策分析。此外，還有盈虧點分析法

9、、價值分析法等。,6. 人事管理這里涉及六方面。(1)人員的獲得和需求估計；(2)人才的開發(fā)，即進行教育和訓(xùn)練；(3)人員的分配，主要是各種指派問題；(4)各類人員的合理利用問題；(5)人才的評價，其中有如何測定一個人對組織、社會的貢獻；(6)薪資和津貼的確定等。,2024年3月19日星期二8時16分32秒,7.設(shè)備維修、更新和可靠度、項目選擇和評價如電力系統(tǒng)的可靠度分析、核能電廠的可靠度以及風險評估等。,8.工程的最佳化設(shè)計在土

10、木、建筑、水利、信息、電子、電機、光學、機械、環(huán)境和化工等領(lǐng)域皆有作業(yè)研究的應(yīng)用。,9.城市管理包括各種緊急服務(wù)救難系統(tǒng)的設(shè)計和運用。如消防隊救火站、救護車、警車等分布點的設(shè)立。美國曾用等候理論方法來確定紐約市緊急電話站的值班人數(shù)。加拿大亦曾研究一城市警車的配置和負則范圍，事故發(fā)生后警車應(yīng)走的路線等。,2024年3月19日星期二8時16分32秒,分析與表述問題,建立模型,對模型和由模型導(dǎo)出的解進行檢驗,建立起對解的有效控制,對問題求解

11、,方案實施,,,,,,不滿意,滿意,運籌學應(yīng)用步驟,2024年3月19日星期二8時16分32秒,五、運籌學在數(shù)學建模競賽中的地位,有人統(tǒng)計：在全國大學生數(shù)學建模競賽題中有40%可以用運籌學中的優(yōu)化方法解決,2024年3月19日星期二8時16分32秒,1. CUMCM-1995A: 一個飛行管理問題 2. CUMCM-2000B: 鋼管訂購與運輸3. CUMCM-2003B：露天礦生產(chǎn)的車輛安排4. CUMCM-2000D: 空洞

12、探測5. CUMCM-2006 B: 艾滋病療法的評價及療效的預(yù)測6. CUMCM-2006 C : 易拉罐形狀和尺寸的最優(yōu)設(shè)計7. CUMCM-2009B：眼科病床的合理安排,2024年3月19日星期二8時16分32秒,線 性 規(guī) 劃,線性規(guī)劃實例,2024年3月19日星期二8時16分32秒,★ 在各類經(jīng)濟活動中，經(jīng)常遇到這樣的問題：在生產(chǎn)條件不變的情況下，如何通過統(tǒng)籌安排，改進生產(chǎn)組織或計劃，合理安排人力、物力資源，組織生產(chǎn)

13、過程，使總的經(jīng)濟效益最好。,可以化成或近似地化成“線性規(guī)劃”（Linear Programming，簡記為LP）問題,線性規(guī)劃研究的實際問題：生產(chǎn)計劃問題、物資運輸問題、合理下料問題、庫存問題、勞動力問題、最優(yōu)設(shè)計問題等,2024年3月19日星期二8時16分32秒,50桶牛奶,時間480小時,至多加工100公斤A1,制訂生產(chǎn)計劃，使每天獲利最大,35元可買到1桶牛奶，買嗎？若買，每天最多買多少?,可聘用臨時工人，付出的工資最多是每小時

14、幾元?,A1的獲利增加到 30元/公斤，應(yīng)否改變生產(chǎn)計劃？,每天：,例: 奶制品生產(chǎn)計劃,2024年3月19日星期二8時16分32秒,x1桶牛奶生產(chǎn)A1,x2桶牛奶生產(chǎn)A2,獲利 24×3x1,獲利 16×4 x2,原料供應(yīng),勞動時間,加工能力,決策變量,目標函數(shù),每天獲利,約束條件,非負約束,線性規(guī)劃模型(LP),時間480小時,至多加工100公斤A1,2024年3月19日星期二8時16分32秒,2024年3月

15、19日星期二8時16分32秒,,,,,,,,⑴．一般形式,目標函數(shù) 價值向量 價值系數(shù) 決策變量,右端向量,系數(shù)矩陣,2024年3月19日星期二8時16分32秒,⑵．規(guī)范形式,⑶．標準形式,三種形式的LP問題全都是等價的，即一種形式的LP可以簡單的變換為另一種形式的LP，且它們有相同

16、的解 .,2024年3月19日星期二8時16分32秒,對于非標準形式的線性規(guī)劃，可通過下列辦法化成標準形式,①若求 ,可化為求,②若約束條件中含有不等式 或 則可引進新變量 （稱為松弛變量），化為等式約束： 或,③總假定 ，否則在等式兩邊乘以-1

17、即可,④若變量 無非負限制，則引入兩個非負變量 與 令 ，便可化為標準形式,2024年3月19日星期二8時16分32秒,線性規(guī)劃模型的解的幾種情況,2024年3月19日星期二8時16分32秒,2024年3月19日星期二8時16分33秒,圖解法,約束條件,,,,,目標函數(shù),在B(20,30)點得到最優(yōu)解,模型求解,軟件實現(xiàn),LINDO 6.1,max 72x1+64x

18、2st2）x1+x2<503）12x1+8x2<4804）3x1<100end,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X

19、2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 4

20、0.000000 0.000000 NO. ITERATIONS= 2,DO RANGE (SENSITIVITY) ANALYSIS?,No,20桶牛奶生產(chǎn)A1, 30桶生產(chǎn)A2，利潤3360元。,結(jié)果解釋,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE RED

21、UCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000

22、 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,原料無剩余,時間無剩余,加工能力剩余40,max 72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100

23、end,三種資源,“資源” 剩余為零的約束為緊約束（有效約束）,結(jié)果解釋,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000

24、 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000

25、 0.000000 NO. ITERATIONS= 2,最優(yōu)解下“資源”增加1單位時“效益”的增量,原料增加1單位, 利潤增長48,時間增加1單位, 利潤增長2,加工能力增長不影響利潤,影子價格,35元可買到1桶牛奶，要買嗎？,35 <48, 應(yīng)該買！,聘用臨時工人付出的工資最多每小時幾元？,2元！,RANGES IN WHICH THE BASIS IS UNCHANGED:

26、 OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2

27、 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE

28、 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,最優(yōu)解不變時目標函數(shù)系數(shù)允許變化范

29、圍,DO RANGE(SENSITIVITY) ANALYSIS?,Yes,x1系數(shù)范圍(64,96),x2系數(shù)范圍(48,72),A1獲利增加到 30元/公斤，應(yīng)否改變生產(chǎn)計劃,x1系數(shù)由24 ?3=72增加為30?3=90，在允許范圍內(nèi),不變！,(約束條件不變),結(jié)果解釋,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIEN

30、T RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000

31、 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 5

32、0.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,影子價格有意義時約束右端的允許變化范圍,原料最多增加10,時間最多增加5

33、3,35元可買到1桶牛奶，每天最多買多少？,最多買10桶!,(目標函數(shù)不變),運 輸 問 題,分 析：,決策變量,,設(shè) 表示從倉庫 運往零售點 的物資數(shù)量,目標函數(shù),目標：運費最省,約束條件,,從倉庫運出總量不超過可用總量，運入零售點的數(shù)量不低于需求量。由于總供給量等于總需求量，所以都是等號。即,蘊含約束：數(shù)量非負,模 型：,收發(fā)平衡型的運輸問題,從m個發(fā)點Ai,i=1,2, …,m,調(diào)運物資到n個收點B

34、j,j=1,2, …,n；發(fā)點Ai有物資ai，收點Bj的需求量是bj，從Ai運到Bj的運價為cij，且收發(fā)平衡，如何運輸使總運費最省,運輸問題的求解過程　　為了便于討論，以一個運輸問題實例的求解過程來介紹如何用LINDO或LINGO軟件求解運輸問題模型.　例 設(shè) m=3, n=4即為有3個產(chǎn)地和4個銷地的運輸問題，其產(chǎn)量、銷量及單位運費如表7-1所示.試求總運費最少的運輸方案，以及總運費.,解：從前面的分析來看，運輸問題屬于線

35、性規(guī)劃問題，因此，不論是LINDO軟件或LINGO軟件都可以對該問題求解. 寫出LINDO軟件的模型（程序），程序名：exam0702.ltx. ! 3 Warehouse, 4 Customer Transportation Problem　　! The objective　　min 6x11 + 2x12 + 6x13 + 7x14　 + 4x21 + 9x22 + 5x23 + 3x24　 +

36、 8x31 + 8x32 + x33 + 5x34　　subject to,! The supply constraints2) x11 + x12 + x13 + x14 <= 303) x21 + x22 + x23 + x24 <= 254) x31 + x32 + x33 + x34 <= 21! The demand constraints5) x11 + x21 + x31 = 15

37、6) x12 + x22 + x32 = 177) x13 + x23 + x33 = 228) x14 + x24 + x34 = 12end,LINDO軟件的計算結(jié)果如下：LP OPTIMUM FOUND AT STEP 6 OBJECTIVE FUNCTION VALUE 1) 161.0000 VARIABLE VALUE RE

38、DUCED COST X11 2.000000 0.000000 X12 17.000000 0.000000 X13 1.000000 0.000000 X14 0.000000 2.000000 X21 13.0000

39、00 0.000000 X22 0.000000 9.000000 X23 0.000000 1.000000,X24 12.000000 0.000000 X31 0.000000 7.000000 X32 0.0

40、00000 11.000000 X33 21.000000 0.000000 X34 0.000000 5.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 10.000000 0.000000 3)

41、 0.000000 2.000000 4) 0.000000 5.000000 5) 0.000000 -6.000000 6) 0.000000 -2.000000 7) 0.000000 -6.000000

42、 8) 0.000000 -5.000000 NO. ITERATIONS= 6,事實上，我們關(guān)心更多的是那些非零變量，因此,可選擇LINDO中的命令只列出非零變量.,OBJECTIVE FUNCTION VALUE 1) 161.0000 VARIABLE VALUE REDUCED COST X11

43、 2.000000 0.000000 X12 17.000000 0.000000,X13 1.000000 0.000000 X21 13.000000 0.000000 X24 12.000000 0.000000 X

44、33 21.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 3) 0.000000 2.000000 4) 0.000000 5.000000 5) 0.000000 -6.00000

45、0 6) 0.000000 -2.000000 7) 0.000000 -6.000000 8) 0.000000 -5.000000 NO. ITERATIONS= 6,參考文獻,[1] 謝金星，薛毅.優(yōu)化建模與LINDO/LINGO軟件[M].北京： 清華大學

46、出版社.2005,7.[2] 姜啟源，謝金星，葉俊.數(shù)學模型（第三版）[M].北京： 高等教育出版社.2005,12.[3] 刁在筠，劉桂真等. 運籌學[M].北京：高等教育出版 社.2009,12.[4] 牛映武，運籌學[M].西安：西安交通大學出版社. 2006.5[5] 胡運權(quán)，運籌學教程[M]. 北京：清華大學出版社. 2007.4,2024年3月19日星期二8時16分33秒,整 數(shù) 規(guī) 劃,要求

47、變量取整數(shù)值的線性規(guī)劃問題稱為整數(shù)線性規(guī)劃,要求變量取0或1的線性規(guī)劃問題稱為0-1規(guī)劃,只要求部分變量取整數(shù)值的線性規(guī)劃稱為混合整數(shù)線性規(guī)劃,2024年3月19日星期二8時16分33秒,例,投資決策問題,解,2024年3月19日星期二8時16分33秒,,,,,,,,,投資決策變量,2024年3月19日星期二8時16分33秒,,設(shè)獲得的總利潤為z，則上述問題的數(shù)學模型為,變量限制為整數(shù)本質(zhì)上是一個非線性約束，它不可能用線性約束來代替它.

48、,2024年3月19日星期二8時16分33秒,☆1954年 G.G.Dantzig D.R.Fulkerson and S.M.Johnson研究推銷商問題（貨郎擔問題）,首先提出破子圈方法和將問題分解為幾個子問題之和的思想，這是割平面方法和分枝定界法的萌芽,☆1958年 R.E.Gomory 創(chuàng)立割平面算法,☆1960年 A.H.Land and A.G.Doig 對推銷商問題提出分解算法，緊接著，E.Balas等人將其發(fā)展成一般

49、的分枝定界法，從而形成獨立的整數(shù)規(guī)劃分支,☆1993年 W.J.Cook 平行計算研究10907064個城市的貨郎擔問題,整數(shù)規(guī)劃簡史,2024年3月19日星期二8時16分33秒,例,旅行售貨員問題 （貨郎擔問題）(TSP問題）,解,2024年3月19日星期二8時16分33秒,首先，每個城市恰好進入一次，即,其次，每個城市恰好離開一次，即,2024年3月19日星期二8時16分33秒,第三，不能出現(xiàn)多于一個互不連通的旅行路線圈，且不排除任

50、何可能的旅行路線,2024年3月19日星期二8時16分33秒,常用算法：,割平面算法、分枝定界法、解0-1規(guī)劃的隱枚舉法、分解算法、 群論方法、動態(tài)規(guī)劃方法,一般只能用來解決中小型的ILP問題,近似算法,1993年7月 W.J.Cook 并行計算 10907064個城市貨郎擔問題,計算機模擬法 如Monte-Carlo方法,丁的蛙泳成績退步到1’15”2；戊的自由泳成績進步到57”5, 組成接力隊的方案是否應(yīng)該調(diào)整？,如何選拔隊員組成4

51、?100米混合泳接力隊?,例 混合泳接力隊的選拔,5名候選人的百米成績,窮舉法：組成接力隊的方案共有5!=120種。,目標函數(shù),若選擇隊員i參加泳姿j 的比賽，記xij=1, 否則記xij=0,0-1規(guī)劃模型,cij(秒)~隊員i 第j 種泳姿的百米成績,約束條件,每人最多入選泳姿之一,每種泳姿有且只有1人,模型求解,最優(yōu)解：x14 = x21 = x32 = x43 = 1, 其它變量為0;成績?yōu)?53.2(秒)=4’13”2,

52、MIN 66.8x11+75.6x12+87x13+58.6x14 +… … +67.4x51+71 x52+83.8x53+62.4x54SUBJECT TO x11+x12+x13+x14 <=1 … … x41+x42+x43+x44 <=1 x11+x21+x31+x41+x51 =1 … … x14+x24+x34+x44+x54 =

53、1END INT 20,輸入LINDO求解,甲~ 自由泳、乙~ 蝶泳、丙~ 仰泳、丁~ 蛙泳.,丁蛙泳c43 =69.6?75.2，戊自由泳c54=62.4 ? 57.5, 方案是否調(diào)整？,敏感性分析？,乙~ 蝶泳、丙~ 仰泳、丁~ 蛙泳、戊~ 自由泳,IP規(guī)劃一般沒有與LP規(guī)劃相類似的理論，LINDO輸出的敏感性分析結(jié)果通常是沒有意義的。,最優(yōu)解：x21 = x32 = x43 = x51 = 1, 成績?yōu)?’17”7,c43

54、, c54 的新數(shù)據(jù)重新輸入模型，用LINDO求解,指派(Assignment)問題：每項任務(wù)有且只有一人承擔，每人只能承擔一項，效益不同，怎樣分派使總效益最大.,討論,為了選修課程門數(shù)最少，應(yīng)學習哪些課程 ？,例 選課策略,要求至少選兩門數(shù)學課、三門運籌學課和兩門計算機課,選修課程最少，且學分盡量多，應(yīng)學習哪些課程 ？,0-1規(guī)劃模型,決策變量,目標函數(shù),xi=1 ~選修課號i 的課程（xi=0 ~不選）,選修課程總數(shù)最少,約束條

55、件,最少2門數(shù)學課，3門運籌學課，2門計算機課。,先修課程要求,最優(yōu)解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它為0；6門課程，總學分21,,0-1規(guī)劃模型,約束條件,x3=1必有x1 = x2 =1,,,模型求解（LINDO）,學分最多,多目標優(yōu)化的處理方法：化成單目標優(yōu)化。,兩目標(多目標)規(guī)劃,討論：選修課程最少，學分盡量多，應(yīng)學習哪些課程？,課程最少,以學分最多為目標，不管課程多少。,以課程最少為

56、目標，不管學分多少。,,多目標規(guī)劃,在課程最少的前提下以學分最多為目標。,最優(yōu)解： x1 = x2 = x3 = x5 = x7 = x9 =1, 其它為0；總學分由21增至22。,注意：最優(yōu)解不唯一！,LINDO無法告訴優(yōu)化問題的解是否唯一。,可將x9 =1 易為x6 =1,2024年3月19日星期二8時16分33秒,多目標規(guī)劃,對學分數(shù)和課程數(shù)加權(quán)形成一個目標，如三七開。,,,=-0.8x1-0.5x2-0.5x3-0.2x4-0.

57、5x5-0.2x6+0.1x7+0.1x8-0.2x9,2024年3月19日星期二8時16分33秒,多目標規(guī)劃,對學分數(shù)和課程數(shù)加權(quán)形成一個目標，如三七開。,最優(yōu)解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x9 =1，其它為0；總學分28。,2024年3月19日星期二8時16分33秒,多目標規(guī)劃的求解方法,1、化多為少的方法：把多目標規(guī)劃問題歸為單目標的數(shù)學規(guī)劃(線性規(guī)劃或非線 性規(guī)劃)問題進行求解,①

58、 線性加權(quán)和法② 理想點法,2、分層求解法,假若目標函數(shù)多目標規(guī)劃 的各個分目標可以按其在問題中的重要程度排出先后次序，先對第一個目標進行極小化，設(shè)得到的最優(yōu)解 x,然后按固定格式依次分層對各目標進行極小化,3、層次分析法,2024年3月19日星期二8時16分33秒,圖 論 與 網(wǎng) 絡(luò) 優(yōu) 化,圖論的研究最早可追溯到著名的七橋問題.18世紀歐洲的哥尼斯堡城中有一條河叫普雷格爾河，該河中有兩個島，河上有七座橋，如圖所示.當時那里的人們就

59、考慮：能否從A、B、C、D中任一地方出發(fā)，走每座橋一次而且只走一次，最后剛好回到出發(fā)點.,例 公路連接問題某一地區(qū)有若干個主要城市，現(xiàn)準備修建高速公路把這些城市連接起來， 使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達另一個城市. 假定已經(jīng)知道了任意兩個城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最?。?例 最短路問題（SPP-Shortest Path Problem）一名貨柜車司機奉命在最

60、短的時間內(nèi)將一車貨物從甲地運往乙地. 從甲地到乙地的公路網(wǎng)縱橫交錯，因此有多種行車路線，這名司機應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運行速度是恒定的，那么這一問題相當于需要找到一條從甲地到乙地的最短路.,例 運輸問題(Transportation Problem)某種原材料有M個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運往N個使用這些原材料的工廠. 假定M個產(chǎn)地的產(chǎn)量和N家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的的運費已知，那么如何安排運輸方案

61、可以使總運輸成本最低？,例 指派問題(Assignment Problem)一家公司經(jīng)理準備安排N名員工去完成N項任務(wù)，每人一項. 由于各員工的特點不同，不同的員工去完成同一項任務(wù)時所獲得的回報是不同的. 如何分配工作方案可以使總回 報最大？,例 中國郵遞員問題(CPP-Chinese Postman Problem)一名郵遞員負責投遞某個街區(qū)的郵件. 如何為他(她)設(shè)計一條最短的投遞路線(從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，

62、最后返回郵局)？由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題.,例 旅行商問題/貨郎（擔）問題(TSP-Traveling Salesman Problem)一名推銷員準備前往若干城市推銷產(chǎn)品. 如何為他(她)設(shè)計一條最短的旅行路線(從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地)？這一問題的研究歷史十分悠久，通常稱之為旅行商問題.,動 態(tài) 規(guī) 劃,運籌學的一個分支，解決多階段決策過程最優(yōu)化的

63、一種數(shù)學方法,★多階段決策過程—指一類活動過程，它可以分為若干個相互聯(lián)系的階段，在每個階段都需要作出決策. 這個決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài). 每個階段的決策確定以后，就得到一個決策序列，稱為策略. 求解目的就是求一個策略，使各階段的效益的總和達到最優(yōu)，這種把一個問題可看作是一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程稱為多階段決策過程，這種問題稱為多階段決策問題,例 最短路線問題如圖所示,設(shè)某廠A要把一批貨物運到

64、E城出售,中間可經(jīng)過1~8城市,各城市間的交通線及距離如圖所示,問應(yīng)選擇什么路線,可使總距離最短?,為了求出最短路線，一種簡單的方法，可以求出所有從A至E的路長并加以比較. 從A至E共有18條不同路徑，要求出最短路線只需分別求出這18條路徑的長度，再進行比較即可，這種方法稱窮舉法. 可以看出，當問題的段數(shù)很多、各段的狀態(tài)也很多時,窮舉法的計算量會大大增加,甚至使得求優(yōu)成為不可能,下面介紹動態(tài)規(guī)劃方法 注意本方法是從過程的最后

65、一段開始，用逆序遞推方法求解，逐步求出各段各點到終點E的最短路線，最后求得A點到E點的最短路線.,★最短路的重要性質(zhì)：,A到C的最短路,B到C的最短路,,反證：如果II不是從B到C的最優(yōu)路線，II’是比II好的從B到C的路線，那么I-II’就是比I-II更好的從A到C的路線，與I-II是最優(yōu)路線矛盾,用d(sk,xk)表示由狀態(tài)sk點出發(fā)，采用決策xk到達下一階段sk+1點時的兩點距離.,第一步：從k=4開始，狀態(tài)變量s4可取兩種狀態(tài)⑦

66、,⑧，它們到E點的路長分別為4,3, 即f4(7)=4，f4(8)=3,第二步：k＝3，狀態(tài)變量s3可取三個值④,⑤,⑥ ，這是經(jīng)過一個中途點到達終點的兩級決策問題，從④到E有兩條路線，需加以比較、取其中最短的，即：,,這說明由④到終點的最短距離為7，其路徑為④→⑦→E . 相應(yīng)決策為 .,⑤到終點的最短距離為5，其路徑為⑤→⑧→E .相應(yīng)決策為 .,⑥到終點的最短距離為5，其路徑

67、為⑥→⑦→E . 相應(yīng)決策為 .,第三步：k＝2，狀態(tài)變量s2可取三個值①,②,③，這是經(jīng)過兩個中途點到達終點的三級決策問題. 因為第三段各點④,⑤,⑥到E的最短距離f3(4), f3(5), f3(6)已知,所以若求①到E的最短距離，只需以它們?yōu)榛A(chǔ)，分別加上①與④,⑤,⑥的一段距離，取其中最短者即可,①到終點的最短距離為9，其路徑為①→⑤→⑥→⑧→E 。相應(yīng)決策為 。,同理有：

68、,第四步：k＝1，只有一個狀態(tài)點A，,即從A到E的最短距離為17，第一階段決策為,再按計算順序反推可得最優(yōu)決策序列{xk}，即有,最優(yōu)路線為：A→①→⑤→⑧→E,從上述計算過程可看出，在求解的各階段，都利用了第k段和第k十1段的如下關(guān)系：,,這種遞推關(guān)系稱為動態(tài)規(guī)劃的基本方程，f5(s5)=0稱為邊界條件,,,退 出,,,前一頁,后一頁,[4],[3],[7],[5],[5],[9],[11],[13],[17],上述最短路線的計算過