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

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

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

20世紀(jì)50年代中期錢(qián)學(xué)森和許國(guó)志教授引入“運(yùn)用學(xué)”＊

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

對(duì)模型和由模型導(dǎo)出的解進(jìn)行檢驗(yàn)建立起對(duì)解的有效控制對(duì)問(wèn)題求解

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

12小時(shí)8小時(shí)4公斤A2

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

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

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

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

1桶牛奶3公斤A1

12小時(shí)8小時(shí)4公斤A2

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

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

獲利24×3x1

獲利16×4x2

原料供應(yīng)

勞動(dòng)時(shí)間

加工能力

決策變量

目標(biāo)函數(shù)

每天獲利約束條件非負(fù)約束

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

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

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

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

軟件實(shí)現(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，利潤(rùn)3360元。結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料無(wú)剩余時(shí)間無(wú)剩余加工能力剩余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單位時(shí)“效益”的增量原料增加1單位,利潤(rùn)增長(zhǎng)48時(shí)間增加1單位,利潤(rùn)增長(zhǎng)2加工能力增長(zhǎng)不影響利潤(rùn)影子價(jià)格

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

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

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

A1獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃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影子價(jià)格有意義時(shí)約束右端的允許變化范圍原料最多增加10時(shí)間最多增加53

35元可買(mǎi)到1桶牛奶，每天最多買(mǎi)多少？最多買(mǎi)10桶!(目標(biāo)函數(shù)不變)運(yùn)輸問(wèn)題分析：決策變量

設(shè)表示從倉(cāng)庫(kù)運(yùn)往零售點(diǎn)的物資數(shù)量目標(biāo)函數(shù)目標(biāo)：運(yùn)費(fèi)最省約束條件從倉(cāng)庫(kù)運(yùn)出總量不超過(guò)可用總量，運(yùn)入零售點(diǎn)的數(shù)量不低于需求量。由于總供給量等于總需求量，所以都是等號(hào)。即蘊(yùn)含約束：數(shù)量非負(fù)模型：收發(fā)平衡型的運(yùn)輸問(wèn)題從m個(gè)發(fā)點(diǎn)Ai,i=1,2,…,m,調(diào)運(yùn)物資到n個(gè)收點(diǎn)Bj,j=1,2,…,n；發(fā)點(diǎn)Ai有物資ai，收點(diǎn)Bj的需求量是bj，從Ai運(yùn)到Bj的運(yùn)價(jià)為cij，且收發(fā)平衡，如何運(yùn)輸使總運(yùn)費(fèi)最省

運(yùn)輸問(wèn)題的求解過(guò)程為了便于討論，以一個(gè)運(yùn)輸問(wèn)題實(shí)例的求解過(guò)程來(lái)介紹如何用LINDO或LINGO軟件求解運(yùn)輸問(wèn)題模型.

例設(shè)m=3,n=4即為有3個(gè)產(chǎn)地和4個(gè)銷(xiāo)地的運(yùn)輸問(wèn)題，其產(chǎn)量、銷(xiāo)量及單位運(yùn)費(fèi)如表7-1所示.試求總運(yùn)費(fèi)最少的運(yùn)輸方案，以及總運(yùn)費(fèi).

解：從前面的分析來(lái)看，運(yùn)輸問(wèn)題屬于線性規(guī)劃問(wèn)題，因此，不論是LINDO軟件或LINGO軟件都可以對(duì)該問(wèn)題求解.寫(xiě)出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軟件的計(jì)算結(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事實(shí)上，我們關(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參考文獻(xiàn)[1]謝金星，薛毅.優(yōu)化建模與LINDO/LINGO軟件[M].北京：清華大學(xué)出版社.2005,7.[2]姜啟源，謝金星，葉俊.數(shù)學(xué)模型（第三版）[M].北京：高等教育出版社.2005,12.[3]刁在筠，劉桂真等.運(yùn)籌學(xué)[M].北京：高等教育出版社.2009,12.[4]牛映武，運(yùn)籌學(xué)[M].西安：西安交通大學(xué)出版社.2006.5[5]胡運(yùn)權(quán)，運(yùn)籌學(xué)教程[M].北京：清華大學(xué)出版社.2007.4整數(shù)規(guī)劃要求變量取整數(shù)值的線性規(guī)劃問(wèn)題稱(chēng)為整數(shù)線性規(guī)劃要求變量取0或1的線性規(guī)劃問(wèn)題稱(chēng)為0-1規(guī)劃只要求部分變量取整數(shù)值的線性規(guī)劃稱(chēng)為混合整數(shù)線性規(guī)劃例投資決策問(wèn)題

解投資決策變量

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

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

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

甲乙丙丁戊蝶泳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名候選人的百米成績(jī)窮舉法：組成接力隊(duì)的方案共有5!=120種。目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽，記xij=1,否則記xij=0

0-1規(guī)劃模型

cij(秒)~隊(duì)員i第j種泳姿的百米成績(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;成績(jī)?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ī)劃一般沒(méi)有與LP規(guī)劃相類(lèi)似的理論，LINDO輸出的敏感性分析結(jié)果通常是沒(méi)有意義的。最優(yōu)解：x21=x32=x43=x51=1,成績(jī)?yōu)?’17”7c43,c54的新數(shù)據(jù)重新輸入模型，用LINDO求解指派(Assignment)問(wèn)題：每項(xiàng)任務(wù)有且只有一人承擔(dān)，每人只能承擔(dān)一項(xiàng)，效益不同，怎樣分派使總效益最大.討論甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.原方案為了選修課程門(mén)數(shù)最少，應(yīng)學(xué)習(xí)哪些課程？

例選課策略要求至少選兩門(mén)數(shù)學(xué)課、三門(mén)運(yùn)籌學(xué)課和兩門(mén)計(jì)算機(jī)課課號(hào)課名學(xué)分所屬類(lèi)別先修課要求1微積分5數(shù)學(xué)

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

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

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

0-1規(guī)劃模型

決策變量

目標(biāo)函數(shù)

xi=1~選修課號(hào)i的課程（xi=0~不選）

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

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

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

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

2線性代數(shù)

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

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

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

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

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

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

對(duì)學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開(kāi)。最優(yōu)解：

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

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

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

例

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

報(bào)最大？

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

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

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

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

C,今有

n

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

J1，J2，…，Jn

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

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

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

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

BP

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

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

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

能否裝得下？能.則Ji

放入Bj

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

放入新箱子Bj+1.計(jì)算復(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的長(zhǎng)度分別為w1，w2,…，wn箱子B1，B2，…的長(zhǎng)均為C，按物品給定的順序裝箱.物品J1J2J3J4J5J6wj674283I:C=10用NF算法裝箱,當(dāng)放入J3時(shí),僅看B2是否能放入，因B1已關(guān)閉,參見(jiàn)EX.1但事實(shí)上，B1此時(shí)是能放得下J3的.如何修正NF算法先將J1放入B1，若,

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

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