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

運籌學(xué)在數(shù)學(xué)建模中的應(yīng)用一、運籌學(xué)概況二、線性規(guī)劃三、整數(shù)規(guī)劃與多目標規(guī)劃四、圖論與網(wǎng)絡(luò)優(yōu)化五、動態(tài)規(guī)劃六、賽題選講運籌學(xué)概況運籌學(xué)的定義運籌學(xué)簡史運籌學(xué)的主要內(nèi)容及應(yīng)用重點運籌學(xué)應(yīng)用步驟運籌學(xué)在數(shù)學(xué)建模競賽中的地位運籌學(xué)是一種給出問題不壞的答案的藝術(shù)，否則的話問題的結(jié)果會更壞。一、運籌學(xué)的定義☆

運籌學(xué)(《辭?！?：20世紀40年代開始形成的一門學(xué)科，主要研究經(jīng)濟活動與軍事活動中能用數(shù)量來表達的有關(guān)運用、籌劃與管理方面的問題，它根據(jù)問題的要求，通過數(shù)學(xué)的分析與運算，做出綜合性合理安排，以達到較經(jīng)濟有效地使用人力物力.☆作為一門定量優(yōu)化決策科學(xué)，起源于第二次世界戰(zhàn)，英文原意OperationResearch；二、運籌學(xué)簡史深水炸彈的釋放問題防空系統(tǒng)的預(yù)警問題運籌學(xué)的一些分支英美?？哲娮鲬?zhàn)參謀部組成了運籌學(xué)研究小組二戰(zhàn)中二戰(zhàn)后軍事工、商業(yè)領(lǐng)域存儲論、決策科學(xué)、預(yù)測科學(xué)等分支☆

20世紀50年代中期錢學(xué)森和許國志教授引入“運用學(xué)”＊

1957年取“運籌”二字，將OR正式命名為“運籌學(xué)”開始應(yīng)用于建筑業(yè)和紡織業(yè)《史記》中“夫運籌帷幄之中，決勝千里之外”線性規(guī)劃數(shù)學(xué)規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃動態(tài)規(guī)劃多目標規(guī)劃組合優(yōu)化最優(yōu)計數(shù)問題網(wǎng)絡(luò)優(yōu)化排序問題統(tǒng)籌圖隨機優(yōu)化對策論排隊論庫存論決策分析可靠性分析三、運籌學(xué)主要內(nèi)容數(shù)學(xué)規(guī)劃模型的數(shù)學(xué)描述下的最大值或最小值。將一個優(yōu)化問題用數(shù)學(xué)式子來描述，即求函數(shù)在約束條件和數(shù)學(xué)規(guī)劃問題的一般形式約束條件決策變量目標函數(shù)“受約束于”之意網(wǎng)絡(luò)優(yōu)化研究解決生產(chǎn)組織、計劃管理中諸如最短路徑問題、最小連接問題、最小費用流問題、最優(yōu)分派問題及關(guān)鍵線路圖等。特別在計劃和安排大型復(fù)雜工程時，網(wǎng)絡(luò)技術(shù)是重要的工具。排隊論是20世紀初由丹麥數(shù)學(xué)家Erlang應(yīng)用數(shù)學(xué)方法在研究電話話務(wù)理論過程中而發(fā)展起來的一門學(xué)科，排隊論也稱隨機服務(wù)系統(tǒng)理論，排隊論是定量的研究排隊問題，尋找系統(tǒng)內(nèi)在規(guī)律，尋找供求關(guān)系平衡的最優(yōu)方案。如機器等待修理、船舶等待裝卸、顧客等待服務(wù)等。對策論研究具有利害沖突的各方，如何制定對自己有利從而戰(zhàn)勝對手的斗爭策略田忌賽馬運籌學(xué)的應(yīng)用重點1.市場銷售在廣告預(yù)算和媒體的選擇、競爭性定價、新產(chǎn)品開發(fā)、銷售計劃的制定等方面。如美國杜邦公司在五十年代起就非常重視將作業(yè)研究用于研究如合做好廣告工作、產(chǎn)品定價和新產(chǎn)品的引入。2.生產(chǎn)計劃在總體計劃方面主要是從總體確定生產(chǎn)、儲存和勞動力的配合等計劃以適應(yīng)變動的需求計劃，主要用線性規(guī)劃和仿真方法等。此外，還可用于生產(chǎn)作業(yè)計劃、日程表的編排等。還有在合理下料、配料問題、物料管理等方面的應(yīng)用。3.庫存管理存貨模型將庫存理論與計算器的物料管理信息系統(tǒng)相結(jié)合，主要應(yīng)用于多種物料庫存量的管理，確定某些設(shè)備的能力或容量，如工廠的庫存、停車廠的大小、新增發(fā)電設(shè)備容量大小、計算機的主存儲器容量、合理的水庫容量等。4.運輸問題這里涉及空運、水運、公路運輸、鐵路運輸、捷運、管道運輸和廠內(nèi)運輸?shù)?。包括班次調(diào)度計劃及人員服務(wù)時間安排等問題。5.財政和會計這里涉及預(yù)算、貸款、成本分析、定價、投資、證券管理、現(xiàn)金管理等。用得較多的方法是：統(tǒng)計分析、數(shù)學(xué)規(guī)劃、決策分析。此外，還有盈虧點分析法、價值分析法等。6.人事管理這里涉及六方面。(1)人員的獲得和需求估計；(2)人才的開發(fā)，即進行教育和訓(xùn)練；(3)人員的分配，主要是各種指派問題；(4)各類人員的合理利用問題；(5)人才的評價，其中有如何測定一個人對組織、社會的貢獻；(6)薪資和津貼的確定等。7.設(shè)備維修、更新和可靠度、項目選擇和評價如電力系統(tǒng)的可靠度分析、核能電廠的可靠度以及風險評估等。8.工程的最佳化設(shè)計在土木、建筑、水利、信息、電子、電機、光學(xué)、機械、環(huán)境和化工等領(lǐng)域皆有作業(yè)研究的應(yīng)用。9.城市管理包括各種緊急服務(wù)救難系統(tǒng)的設(shè)計和運用。如消防隊救火站、救護車、警車等分布點的設(shè)立。美國曾用等候理論方法來確定紐約市緊急電話站的值班人數(shù)。加拿大亦曾研究一城市警車的配置和負則范圍，事故發(fā)生后警車應(yīng)走的路線等。分析與表述問題建立模型

對模型和由模型導(dǎo)出的解進行檢驗建立起對解的有效控制對問題求解

方案實施不滿意滿意運籌學(xué)應(yīng)用步驟五、運籌學(xué)在數(shù)學(xué)建模競賽中的地位有人統(tǒng)計：在全國大學(xué)生數(shù)學(xué)建模競賽題中有40%可以用運籌學(xué)中的優(yōu)化方法解決1.CUMCM-1995A:一個飛行管理問題2.CUMCM-2000B:鋼管訂購與運輸3.CUMCM-2003B：露天礦生產(chǎn)的車輛安排4.CUMCM-2000D:空洞探測5.CUMCM-2006B:艾滋病療法的評價及療效的預(yù)測6.CUMCM-2006C:易拉罐形狀和尺寸的最優(yōu)設(shè)計7.CUMCM-2009B：眼科病床的合理安排線性規(guī)劃線性規(guī)劃實例★在各類經(jīng)濟活動中，經(jīng)常遇到這樣的問題：在生產(chǎn)條件不變的情況下，如何通過統(tǒng)籌安排，改進生產(chǎn)組織或計劃，合理安排人力、物力資源，組織生產(chǎn)過程，使總的經(jīng)濟效益最好?？梢曰苫蚪频鼗伞熬€性規(guī)劃”（LinearProgramming，簡記為LP）問題線性規(guī)劃研究的實際問題：生產(chǎn)計劃問題、物資運輸問題、合理下料問題、庫存問題、勞動力問題、最優(yōu)設(shè)計問題等1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時間480小時至多加工100公斤A1

制訂生產(chǎn)計劃，使每天獲利最大

35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時工人，付出的工資最多是每小時幾元?

A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計劃？每天例:奶制品生產(chǎn)計劃

1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤x1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供應(yīng)

勞動時間

加工能力

決策變量

目標函數(shù)

每天獲利約束條件非負約束

線性規(guī)劃模型(LP)時間480小時至多加工100公斤A1

50桶牛奶每天⑴．一般形式目標函數(shù)價值向量價值系數(shù)決策變量右端向量系數(shù)矩陣非負約束自由變量⑵．規(guī)范形式⑶．標準形式三種形式的LP問題全都是等價的，即一種形式的LP可以簡單的變換為另一種形式的LP，且它們有相同的解.對于非標準形式的線性規(guī)劃，可通過下列辦法化成標準形式①若求,可化為求②若約束條件中含有不等式或則可引進新變量（稱為松弛變量），化為等式約束：或③總假定，否則在等式兩邊乘以-1即可④若變量無非負限制，則引入兩個非負變量與令，便可化為標準形式滿足所有約束條件的向量x稱為可行解或者可行點三者皆滿足的向量x是最優(yōu)解最優(yōu)值：最優(yōu)解的目標函數(shù)值可行區(qū)域：所有的可行點組成的集合稱為(LP)問題的可行區(qū)域.記為D線性規(guī)劃模型的解的幾種情況線性規(guī)劃問題有可行解(Feasible)無可行解（Infeasible）有最優(yōu)解（Optimal）無最優(yōu)解(Unbounded)圖解法

x1x20ABCDl1l2l3l4l5約束條件目標函數(shù)

Z=0Z=2400Z=3600c在B(20,30)點得到最優(yōu)解模型求解

軟件實現(xiàn)

LINDO6.1max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤3360元。結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料無剩余時間無剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三種資源“資源”剩余為零的約束為緊約束（有效約束）結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2最優(yōu)解下“資源”增加1單位時“效益”的增量原料增加1單位,利潤增長48時間增加1單位,利潤增長2加工能力增長不影響利潤影子價格

35元可買到1桶牛奶，要買嗎？35<48,應(yīng)該買！聘用臨時工人付出的工資最多每小時幾元？2元！RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最優(yōu)解不變時目標函數(shù)系數(shù)允許變化范圍DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系數(shù)范圍(64,96)

x2系數(shù)范圍(48,72)

A1獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計劃x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！(約束條件不變)結(jié)果解釋

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子價格有意義時約束右端的允許變化范圍原料最多增加10時間最多增加53

35元可買到1桶牛奶，每天最多買多少？最多買10桶!(目標函數(shù)不變)運輸問題分析：決策變量

設(shè)表示從倉庫運往零售點的物資數(shù)量目標函數(shù)目標：運費最省約束條件從倉庫運出總量不超過可用總量，運入零售點的數(shù)量不低于需求量。由于總供給量等于總需求量，所以都是等號。即蘊含約束：數(shù)量非負模型：收發(fā)平衡型的運輸問題從m個發(fā)點Ai,i=1,2,…,m,調(diào)運物資到n個收點Bj,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所示.試求總運費最少的運輸方案，以及總運費.

解：從前面的分析來看，運輸問題屬于線性規(guī)劃問題，因此，不論是LINDO軟件或LINGO軟件都可以對該問題求解.寫出LINDO軟件的模型（程序），程序名：transportation.ltx

!3Warehouse,4CustomerTransportationProblem!Theobjectivemin6x11+2x12+6x13+7x14+4x21+9x22+5x23+3x24+8x31+8x32+x33+5x34subjectto!Thesupplyconstraints2)x11+x12+x13+x14<=303)x21+x22+x23+x24<=254)x31+x32+x33+x34<=21!Thedemandconstraints5)x11+x21+x31=156)x12+x22+x32=177)x13+x23+x33=228)x14+x24+x34=12endLINDO軟件的計算結(jié)果如下：LPOPTIMUMFOUNDATSTEP6OBJECTIVEFUNCTIONVALUE1)161.0000VARIABLEVALUEREDUCEDCOSTX112.0000000.000000X1217.0000000.000000X131.0000000.000000X140.0000002.000000X2113.0000000.000000X220.0000009.000000X230.0000001.000000X2412.0000000.000000X310.0000007.000000X320.00000011.000000X3321.0000000.000000X340.0000005.000000ROWSLACKORSURPLUSDUALPRICES2)10.0000000.0000003)0.0000002.0000004)0.0000005.0000005)0.000000-6.0000006)0.000000-2.0000007)0.000000-6.0000008)0.000000-5.000000NO.ITERATIONS=6事實上，我們關(guān)心更多的是那些非零變量，因此,可選擇LINDO中的命令只列出非零變量.

OBJECTIVEFUNCTIONVALUE1)161.0000VARIABLEVALUEREDUCEDCOSTX112.0000000.000000X1217.0000000.000000

X131.0000000.000000X2113.0000000.000000X2412.0000000.000000X3321.0000000.000000ROWSLACKORSURPLUSDUALPRICES3)0.0000002.0000004)0.0000005.0000005)0.000000-6.0000006)0.000000-2.0000007)0.000000-6.0000008)0.000000-5.000000NO.ITERATIONS=6參考文獻[1]謝金星，薛毅.優(yōu)化建模與LINDO/LINGO軟件[M].北京：清華大學(xué)出版社.2005,7.[2]姜啟源，謝金星，葉俊.數(shù)學(xué)模型（第三版）[M].北京：高等教育出版社.2005,12.[3]刁在筠，劉桂真等.運籌學(xué)[M].北京：高等教育出版社.2009,12.[4]牛映武，運籌學(xué)[M].西安：西安交通大學(xué)出版社.2006.5[5]胡運權(quán)，運籌學(xué)教程[M].北京：清華大學(xué)出版社.2007.4整數(shù)規(guī)劃要求變量取整數(shù)值的線性規(guī)劃問題稱為整數(shù)線性規(guī)劃要求變量取0或1的線性規(guī)劃問題稱為0-1規(guī)劃只要求部分變量取整數(shù)值的線性規(guī)劃稱為混合整數(shù)線性規(guī)劃例投資決策問題

解投資決策變量

設(shè)獲得的總利潤為z，則上述問題的數(shù)學(xué)模型為

變量限制為整數(shù)本質(zhì)上是一個非線性約束，它不可能用線性約束來代替它.☆1954年G.G.DantzigD.R.FulkersonandS.M.Johnson研究推銷商問題（貨郎擔問題）,首先提出破子圈方法和將問題分解為幾個子問題之和的思想，這是割平面方法和分枝定界法的萌芽☆1958年R.E.Gomory創(chuàng)立割平面算法☆1960年A.H.LandandA.G.Doig對推銷商問題提出分解算法，緊接著，E.Balas等人將其發(fā)展成一般的分枝定界法，從而形成獨立的整數(shù)規(guī)劃分支☆1993年W.J.Cook平行計算研究10907064個城市的貨郎擔問題整數(shù)規(guī)劃簡史例旅行售貨員問題（貨郎擔問題）(TSP問題）解首先，每個城市恰好進入一次，即其次，每個城市恰好離開一次，即第三，不能出現(xiàn)多于一個互不連通的旅行路線圈，且不排除任何可能的旅行路線

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

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候選人的百米成績窮舉法：組成接力隊的方案共有5!=120種。目標函數(shù)若選擇隊員i參加泳姿j的比賽，記xij=1,否則記xij=0

0-1規(guī)劃模型

cij(秒)~隊員i第j種泳姿的百米成績約束條件每人最多入選泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每種泳姿有且只有1人模型求解

最優(yōu)解：x14=x21=x32=x43=1,其它變量為0;成績?yōu)?53.2(秒)=4’13”2MIN66.8x11+75.6x12+87x13+58.6x14+……+67.4x51+71x52+83.8x53+62.4x54SUBJECTTOx11+x12+x13+x14<=1

……x51+x52+x53+x54<=1x11+x21+x31+x41+x51=1

……x14+x24+x34+x44+x54=1END輸入LINDO求解

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”4甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.丁蛙泳c43

=69.675.2，戊自由泳c54=62.4

57.5,方案是否調(diào)整？敏感性分析？乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳IP規(guī)劃一般沒有與LP規(guī)劃相類似的理論，LINDO輸出的敏感性分析結(jié)果通常是沒有意義的。最優(yōu)解：x21=x32=x43=x51=1,成績?yōu)?’17”7c43,c54的新數(shù)據(jù)重新輸入模型，用LINDO求解指派(Assignment)問題：每項任務(wù)有且只有一人承擔，每人只能承擔一項，效益不同，怎樣分派使總效益最大.討論甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.原方案為了選修課程門數(shù)最少，應(yīng)學(xué)習哪些課程？

例選課策略要求至少選兩門數(shù)學(xué)課、三門運籌學(xué)課和兩門計算機課課號課名學(xué)分所屬類別先修課要求1微積分5數(shù)學(xué)

2線性代數(shù)4數(shù)學(xué)

3最優(yōu)化方法4數(shù)學(xué)；運籌學(xué)微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)3數(shù)學(xué)；計算機計算機編程5應(yīng)用統(tǒng)計4數(shù)學(xué)；運籌學(xué)微積分；線性代數(shù)6計算機模擬3計算機；運籌學(xué)計算機編程7計算機編程2計算機

8預(yù)測理論2運籌學(xué)應(yīng)用統(tǒng)計9數(shù)學(xué)實驗3運籌學(xué)；計算機微積分；線性代數(shù)選修課程最少，且學(xué)分盡量多，應(yīng)學(xué)習哪些課程？

0-1規(guī)劃模型

決策變量

目標函數(shù)

xi=1~選修課號i的課程（xi=0~不選）

選修課程總數(shù)最少約束條件最少2門數(shù)學(xué)課，3門運籌學(xué)課，2門計算機課。

課號課名所屬類別1微積分數(shù)學(xué)2線性代數(shù)數(shù)學(xué)3最優(yōu)化方法數(shù)學(xué)；運籌學(xué)4數(shù)據(jù)結(jié)構(gòu)數(shù)學(xué)；計算機5應(yīng)用統(tǒng)計數(shù)學(xué)；運籌學(xué)6計算機模擬計算機；運籌學(xué)7計算機編程計算機8預(yù)測理論運籌學(xué)9數(shù)學(xué)實驗運籌學(xué)；計算機先修課程要求最優(yōu)解：

x1=x2=x3=x6=x7=x9=1,其它為0；6門課程，總學(xué)分210-1規(guī)劃模型

約束條件x3=1必有x1=x2=1模型求解（LINDO）課號課名先修課要求1微積分

2線性代數(shù)

3最優(yōu)化方法微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)計算機編程5應(yīng)用統(tǒng)計微積分；線性代數(shù)6計算機模擬計算機編程7計算機編程

8預(yù)測理論應(yīng)用統(tǒng)計9數(shù)學(xué)實驗微積分；線性代數(shù)學(xué)分最多多目標優(yōu)化的處理方法：化成單目標優(yōu)化。兩目標(多目標)規(guī)劃

討論：選修課程最少，學(xué)分盡量多，應(yīng)學(xué)習哪些課程？課程最少以學(xué)分最多為目標，不管課程多少。以課程最少為目標，不管學(xué)分多少。最優(yōu)解如上，6門課程，總學(xué)分21。最優(yōu)解顯然是選修所有9門課程。多目標規(guī)劃

在課程最少的前提下以學(xué)分最多為目標。最優(yōu)解：

x1=x2=x3=x5=x7=x9=1,其它為0；總學(xué)分由21增至22。注意：最優(yōu)解不唯一！課號課名學(xué)分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計46計算機模擬37計算機編程28預(yù)測理論29數(shù)學(xué)實驗3LINDO無法告訴優(yōu)化問題的解是否唯一?？蓪9=1易為x6=1增加約束，以學(xué)分最多為目標求解。多目標規(guī)劃

對學(xué)分數(shù)和課程數(shù)加權(quán)形成一個目標，如三七開。=-0.8x1-0.5x2-0.5x3-0.2x4-0.5x5-0.2x6+0.1x7+0.1x8-0.2x9多目標規(guī)劃

對學(xué)分數(shù)和課程數(shù)加權(quán)形成一個目標，如三七開。最優(yōu)解：

x1=x2=x3=x4=x5=x6=x7=x9=1，其它為0；總學(xué)分28。課號課名學(xué)分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計46計算機模擬37計算機編程28預(yù)測理論29數(shù)學(xué)實驗3多目標規(guī)劃的求解方法1、化多為少的方法：把多目標規(guī)劃問題歸為單目標的數(shù)學(xué)規(guī)劃(線性規(guī)劃或非線性規(guī)劃)問題進行求解①線性加權(quán)和法②理想點法2、分層求解法假若目標函數(shù)多目標規(guī)劃的各個分目標可以按其在問題中的重要程度排出先后次序，先對第一個目標進行極小化，設(shè)得到的最優(yōu)解x,然后按固定格式依次分層對各目標進行極小化3、層次分析法(AnalyticHierarchyProcess,AHP)圖論與網(wǎng)絡(luò)優(yōu)化圖論的研究最早可追溯到著名的七橋問題.18世紀歐洲的哥尼斯堡城中有一條河叫普雷格爾河，該河中有兩個島，河上有七座橋，如圖所示.當時那里的人們就考慮：能否從A、B、C、D中任一地方出發(fā)，走每座橋一次而且只走一次，最后剛好回到出發(fā)點.例公路連接問題某一地區(qū)有若干個主要城市，現(xiàn)準備修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達另一個城市.假定已經(jīng)知道了任意兩個城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最小？

例最短路問題（SPP-ShortestPathProblem）一名貨柜車司機奉命在最短的時間內(nèi)將一車貨物從甲地運往乙地.從甲地到乙地的公路網(wǎng)縱橫交錯，因此有多種行車路線，這名司機應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運行速度是恒定的，那么這一問題相當于需要找到一條從甲地到乙地的最短路.例

運輸問題(TransportationProblem)某種原材料有M個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運往N個使用這些原材料的工廠.假定M個產(chǎn)地的產(chǎn)量和N家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的的運費已知，那么如何安排運輸方案可以使總運輸成本最低？

例

指派問題(AssignmentProblem)一家公司經(jīng)理準備安排N名員工去完成N項任務(wù)，每人一項.由于各員工的特點不同，不同的員工去完成同一項任務(wù)時所獲得的回報是不同的.如何分配工作方案可以使總回

報最大？

例中國郵遞員問題(CPP-ChinesePostmanProblem)一名郵遞員負責投遞某個街區(qū)的郵件.如何為他(她)設(shè)計一條最短的投遞路線(從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局)？由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題.例旅行商問題/貨郎（擔）問題(TSP-TravelingSalesmanProblem)一名推銷員準備前往若干城市推銷產(chǎn)品.如何為他(她)設(shè)計一條最短的旅行路線(從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地)？這一問題的研究歷史十分悠久，通常稱之為旅行商問題.動態(tài)規(guī)劃運籌學(xué)的一個分支，解決多階段決策過程最優(yōu)化的一種數(shù)學(xué)方法★多階段決策過程—指一類活動過程，它可以分為若干個相互聯(lián)系的階段，在每個階段都需要作出決策.這個決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài).每個階段的決策確定以后，就得到一個決策序列，稱為策略.求解目的就是求一個策略，使各階段的效益的總和達到最優(yōu)，這種把一個問題可看作是一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程稱為多階段決策過程，這種問題稱為多階段決策問題12n狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策例最短路線問題如圖所示,設(shè)某廠A要把一批貨物運到E城出售,中間可經(jīng)過1~8城市,各城市間的交通線及距離如圖所示,問應(yīng)選擇什么路線,可使總距離最短?AE873165428956458767893562343為了求出最短路線，一種簡單的方法，可以求出所有從A至E的路長并加以比較.從A至E共有18條不同路徑，要求出最短路線只需分別求出這18條路徑的長度，再進行比較即可，這種方法稱窮舉法.可以看出，當問題的段數(shù)很多、各段的狀態(tài)也很多時,窮舉法的計算量會大大增加,甚至使得求優(yōu)成為不可能下面介紹動態(tài)規(guī)劃方法注意本方法是從過程的最后一段開始，用逆序遞推方法求解，逐步求出各段各點到終點E的最短路線，最后求得A點到E點的最短路線.★最短路的重要性質(zhì)：A到C的最短路B到C的最短路ACBIIIII’I’反證：如果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)⑦,⑧，它們到E點的路長分別為4,3,即f4(7)=4，f4(8)=3第二步：k＝3，狀態(tài)變量s3可取三個值④,⑤,⑥，這是經(jīng)過一個中途點到達終點的兩級決策問題，從④到E有兩條路線，需加以比較、取其中最短的，即：=min=7這說明由④到終點的最短距離為7，其路徑為④→⑦→E.相應(yīng)決策為.⑤到終點的最短距離為5，其路徑為⑤→⑧→E.相應(yīng)決策為.=min=5=min=5⑥到終點的最短距離為5，其路徑為⑥→⑦→E.相應(yīng)決策為.第三步：k＝2，狀態(tài)變量s2可取三個值①,②,③，這是經(jīng)過兩個中途點到達終點的三級決策問題.因為第三段各點④,⑤,⑥到E的最短距離f3(4),f3(5),f3(6)已知,所以若求①到E的最短距離，只需以它們?yōu)榛A(chǔ)，分別加上①與④,⑤,⑥的一段距離，取其中最短者即可=min=9①到終點的最短距離為9，其路徑為①→⑤→⑧→E。相應(yīng)決策為。=min=11=min=13同理有：第四步：k＝1，只有一個狀態(tài)點A，=min=17即從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]上述最短路線的計算過程也可用圖直觀表示出來，每個結(jié)點上方的括號內(nèi)的數(shù)，表示該點到終點E的最短距離.連結(jié)各點到E點的粗線表示最短路徑.這種在圖上直接計算的方法叫標號法.逆序法順序法2003B露天礦生產(chǎn)的車輛安排鋼鐵工業(yè)是國家工業(yè)的基礎(chǔ)之一，鐵礦是鋼鐵工業(yè)的主要原料基地。許多現(xiàn)代化鐵礦是露天開采的，它的生產(chǎn)主要是由電動鏟車（以下簡稱電鏟）裝車、電動輪自卸卡車（以下簡稱卡車）運輸來完成。提高這些大型設(shè)備的利用率是增加露天礦經(jīng)濟效益的首要任務(wù)。

露天礦里有若干個爆破生成的石料堆，每堆稱為一個鏟位，每個鏟位已預(yù)先根據(jù)鐵含量將石料分成礦石和巖石。一般來說，平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個鏟位至多安置一臺電鏟，電鏟平均裝車時間5分鐘。卸貨地點（以下簡稱卸點）有卸礦石的礦石漏、2個鐵路倒裝場（以下簡稱倒裝場）和卸巖石的巖石漏、巖場等，每個卸點都有各自的產(chǎn)量要求。從保護國家資源的角度及礦山的經(jīng)濟效益考慮，應(yīng)該盡量把礦石按礦石卸點需要的鐵含量（假設(shè)要求都為29.5%1%,稱為品位限制)搭配起來送到卸點，搭配的量在一個班次（8小時）內(nèi)滿足品位限制即可。從長遠看，卸點可以移動，但一個班次內(nèi)不變?？ㄜ嚨钠骄盾嚂r間為3分鐘。所用卡車載重量為154噸，平均時速28?？ㄜ嚨暮挠土亢艽?，每個班次每臺車消耗近1噸柴油。發(fā)動機點火時需要消耗相當多的電瓶能量，故一個班次中只在開始工作時點火一次。卡車在等待時所耗費的能量也是相當可觀的，原則上在安排時不應(yīng)發(fā)生卡車等待的情況。電鏟和卸點都不能同時為兩輛及兩輛以上卡車服務(wù)?？ㄜ嚸看味际菨M載運輸。每個鏟位到每個卸點的道路都是專用的寬60的雙向車道，不會出現(xiàn)堵車現(xiàn)象，每段道路的里程都是已知的。一個班次的生產(chǎn)計劃應(yīng)該包含以下內(nèi)容：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛卡車，分別在哪些路線上各運輸多少次（因為隨機因素影響，裝卸時間與運輸時間都不精確，所以排時計劃無效，只求出各條路線上的卡車數(shù)及安排即可）。一個合格的計劃要在卡車不等待條件下滿足產(chǎn)量和質(zhì)量（品位）要求，而一個好的計劃還應(yīng)該考慮下面兩條原則之一：1.總運量（噸公里）最小，同時出動最少的卡車，從而運輸成本最??；2.利用現(xiàn)有車輛運輸，獲得最大的產(chǎn)量（巖石產(chǎn)量優(yōu)先；在產(chǎn)量相同的情況下，取總運量最小的解）。請你就兩條原則分別建立數(shù)學(xué)模型，并給出一個班次生產(chǎn)計劃的快速算法。針對下面的實例，給出具體的生產(chǎn)計劃、相應(yīng)的總運量及巖石和礦石產(chǎn)量。某露天礦有鏟位10個，卸點5個，現(xiàn)有鏟車7臺，卡車20輛。各卸點一個班次的產(chǎn)量要求：礦石漏1.2萬噸、倒裝場Ⅰ1.3萬噸、倒裝場Ⅱ1.3萬噸、巖石漏1.9萬噸、巖場1.3萬噸。平面示意圖各鏟位和各卸點之間的距離（公里）距離鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.265.194.214.002.952.742.461.900.641.27倒裝Ⅰ1.900.991.901.131.272.251.482.043.093.51巖場5.895.615.614.563.513.652.462.461.060.57巖石漏0.641.761.271.832.742.604.213.725.056.10倒裝Ⅱ4.423.863.723.162.252.810.781.621.270.50鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量0．951．051．001．051．101．251．051．301．351．25巖石量1．251．101．351．051．151．351．051．151．351．25鐵含量30%28%29%32%31%33%32%31%33%31%各鏟位礦石、巖石數(shù)量（萬噸）和礦石平均含鐵量一問題剖析露天礦生產(chǎn)主要是運石料，這是一個運輸問題,與典型的運輸問題比較有以下特點：這是運輸?shù)V石與巖石兩種物資的問題；屬于產(chǎn)量大于銷量的不平衡運輸問題；為了完成品位約束，礦石要搭配運輸；變量設(shè)計解決約束條件設(shè)計解決約束條件設(shè)計解決產(chǎn)地、銷地均有單位時間的流量限制；約束條件設(shè)計解決運輸車輛只有一種，每次滿載運輸，154噸/車次；鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于7個產(chǎn)地作為最后結(jié)果中的產(chǎn)地；整數(shù)要求→整數(shù)規(guī)劃從C107=120個整數(shù)規(guī)劃中取最優(yōu)的即得到最佳物流最后求出各條路線上的派出車輛數(shù)及安排。由最佳物流算出各條路線上的最少派出車輛數(shù)再給出具體安排即完成全部計算目的：求出各條路線上的卡車數(shù)及安排兩個階段的規(guī)劃問題第一個階段：確定各條路線上運輸石料的數(shù)量(車次)，可以用整數(shù)規(guī)劃建模第二階段：規(guī)劃各條線路上的派車方案，是一個組合優(yōu)化問題二模型假設(shè)卡車在一個班次中不應(yīng)發(fā)生等待或熄火后再啟動的情況；在鏟位或卸點處由兩條路線以上造成的沖突問題面前，我們認為只要平均時間能完成任務(wù)，就認為不沖突。我們不排時地進行討論；空載與重載的速度都是28km/h，耗油相差很大；卡車可提前退出系統(tǒng)；卡車加油、司機吃飯與上廁所等休息時間忽略不計；對所有卡車來說，一個班次的8小時是同一時刻開始的原則之一總運量(噸公里)最小，同時出動最少的卡車，從而運輸成本最小；三模型建立多目標決策問題（一）分階段考慮，先考慮總運量最小目標：總運量(噸公里)最小xij：從i鏟位到j(luò)號卸點的石料運量車●次；cij：從i號鏟位到j(luò)號卸點的距離公里；目標函數(shù)：xij為整數(shù)約束(1)道路能力約束：一個電鏟(卸點)不能同時為兩輛卡車服務(wù)，所以一條路線上最多能同時運行的卡車數(shù)是有限制的在i號鏟位到j(luò)號卸點路線上運行一個周期平均所需時間從i號鏟位到j(luò)號卸點最多能同時運行的卡車數(shù)(輛)每輛卡車一個班次中在這條路線上最多可以運行的次數(shù)(Aij-1)×5是開始裝車至最后一輛車的延時時間則一個班次中這條固定路線上最多可能運行的總車·次大約為：Lij=Aij×Bij；總噸數(shù)大約為154×Lij(2)電鏟能力約束：還是因為1臺電鏟不能同時為兩輛卡車服務(wù)，所以一臺電鏟在一個班次中的最大可能產(chǎn)量為：8×60／5=96(車·次)。fi:描述第i號鏟位是否使用的0-1變量，取1為使用；0為關(guān)閉。(3)卸點能力約束：卸點的最大吞吐量為每小時60／3=20(車·次)，于是一個卸點在一個班次中的最大可能產(chǎn)量為：8×20=160(車·次)。(4)鏟位儲量約束：各鏟位的礦石和巖石產(chǎn)量都不能超過相應(yīng)的儲藏量cki：i號鏟位的鐵礦石儲量萬噸cyi：i號鏟位的巖石儲量萬噸(5)產(chǎn)量任務(wù)約束：各卸點的產(chǎn)量大于等于該卸點的任務(wù)要求qj:j號卸點任務(wù)需求，q=(1.2,1.3,1.3,1.9,1.3)*10000噸(6)鐵含量約束：各礦石卸點的平均品位要求都在指定的范圍內(nèi)pi：i號鏟位的礦石鐵含量百分比p=(30,28,29,32,31,33,32,31,33,31)(7)車輛數(shù)量約束為各路線上運輸量所需的實數(shù)卡車數(shù)學(xué)模型為計算結(jié)果（LINGO軟件）鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦漏135411倒Ⅰ4243巖場7015巖漏8143倒Ⅱ13270（二）對最佳物流進行派車——第二階段規(guī)劃這是一個組合優(yōu)化中的一維裝箱模型裝箱問題

裝箱問題（BinPacking）是一個經(jīng)典的組合優(yōu)化問題，有著廣泛的應(yīng)用，在日常生活中也屢見不鮮.裝箱問題的描述

設(shè)有許多具有同樣結(jié)構(gòu)和負荷的箱子B1，B2，…其數(shù)量足夠供所達到目的之用.每個箱子的負荷（可為長度、重量etc.）為

C,今有

n

個負荷為wj(0<wj<C,j=1，2，…，n)的物品

J1，J2，…，Jn

需要裝入箱內(nèi).裝箱問題：是指尋找一種方法，使得能以最小數(shù)量的箱子數(shù)將J1，J2，…，Jn全部裝入箱內(nèi).

由于wj<C，所以BP的最優(yōu)解的箱子數(shù)不超過n.設(shè)箱子Bi被使用否則物品Jj放入箱子Bi

中否則則裝箱問題的整數(shù)線性規(guī)劃模型為：約束條件（1）表示：一旦箱子Bi被使用，放入Bi的物品總負荷不超過C；約束條件（2）表示：每個物品恰好放入一個箱子中.上述裝箱問題是這類問題最早被研究的，也是提法上最簡單的問題，稱為一維裝箱問題.但裝箱問題的其他一些提法：1、在裝箱時，不僅考慮長度，同時考慮重量或面積、體積

etc.即二維、三維、…裝箱問題；2、對每個箱子的負荷限制不是常數(shù)C;而是最優(yōu)目標可如何提？3、物品J1，J2，…，Jn的負荷事先并不知道，來貨是隨到隨裝；即在線（On-Line）裝箱問題；4、由于場地的限制，在同一時間只能允許一定數(shù)量的箱子停留現(xiàn)場可供使用,etc.

BP

的應(yīng)用舉例：1、下料問題軋鋼廠生產(chǎn)的線材一般為同一長度,而用戶所需的線材則可能具有各種不同的尺寸,如何根據(jù)用戶提出的要求，用最少的線材截出所需的定貨；2、二維BP

玻璃廠生產(chǎn)出長寬一定的大的平板玻璃,但用戶所需玻璃的長寬可能有許多差異，如何根據(jù)用戶提出的要求，用最少的平板玻璃截出所需的定貨;3、計算機的存貯問題如要把大小不同的共10MB的文件拷貝到磁盤中去，而每張磁盤的容量為1.44MB,已知每個文件的字節(jié)數(shù)不超過1.44MB,而且一個文件不能分成幾部分存貯，如何用最少的磁盤張數(shù)完成.裝箱問題的近似算法一、NF(NextFit)算法設(shè)物品J1，J2,…，Jn的長度分別為w1，w2,…，wn箱子B1，B2，…的長均為C，按物品給定的順序裝箱.先將J1放入B1,如果則將J2放入B1…如果而則B1已放入J1，J2,…，Jj，將其關(guān)閉，將Jj+1放入B2.同法進行，直到所有物品裝完為止.特點：1、按物品給定的順序裝箱；2、關(guān)閉原則.對當前要裝的物品Ji

只關(guān)心具有最大下標的已使用過的箱子Bj

能否裝得下？能.則Ji

放入Bj

；否.關(guān)閉Bj，Ji

放入新箱子Bj+1.計算復(fù)雜性為

O(n).Example1物品J1J2J3J4J5J6wj674283I:C=10J1J5J6J4J3J2B1B2B3B4B5J1J2J3J4J5J6Solution:首先，將J1放入B1;由于J2在B1中放不下,所以關(guān)閉B1,將J2放入B2,J3在B2中放不下(不考慮B1是否能裝),所以關(guān)閉B2將J3放入B3，…解為:其余為零二、FF(FirstFit)算法設(shè)物品J1，J2,…，Jn的長度分別為w1，w2,…，wn箱子B1，B2，…的長均為C，按物品給定的順序裝箱.物品J1J2J3J4J5J6wj674283I:C=10用NF算法裝箱,當放入J3時,僅看B2是否能放入，因B1已關(guān)閉,參見EX.1但事實上，B1此時是能放得下J3的.如何修正NF算法先將J1放入B1，若,

則J2放入B1,否則，J2放入B2;若J2已放入B2，對于J3則依次檢查

B1、B2,若B1能放得下,則J3放入B1,否則查看B2,若B2能放得下，則J3放入B2,否則啟用B3,J3放入B3.一般地，J1,…，Jj已放入B1,…，Bi