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

1、*運(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)運(yùn) 籌籌 學(xué)學(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ù)，否則的運(yùn)籌學(xué)是一種給出問(wèn)題不壞的答案的藝術(shù)，否則的話問(wèn)題的結(jié)果會(huì)更壞。話問(wèn)題的結(jié)果會(huì)更壞。一、運(yùn)籌學(xué)的定義一、運(yùn)籌學(xué)的定義 運(yùn)籌學(xué)運(yùn)籌學(xué)( (辭海辭海) )：2020世紀(jì)世紀(jì)4040年代開(kāi)始形成的一年代開(kāi)始形成的一門(mén)學(xué)科，主要研究門(mén)學(xué)科，主要研究經(jīng)濟(jì)活動(dòng)與軍事活動(dòng)中能用數(shù)量經(jīng)濟(jì)活動(dòng)與軍事活動(dòng)中能用數(shù)量來(lái)表達(dá)的有關(guān)運(yùn)用、籌

2、劃與管理方面的問(wèn)題來(lái)表達(dá)的有關(guān)運(yùn)用、籌劃與管理方面的問(wèn)題，它根，它根據(jù)問(wèn)題的要求，通過(guò)數(shù)學(xué)的分析與運(yùn)算，做出綜合據(jù)問(wèn)題的要求，通過(guò)數(shù)學(xué)的分析與運(yùn)算，做出綜合性合理安排，以達(dá)到較經(jīng)濟(jì)有效地使用人力物力性合理安排，以達(dá)到較經(jīng)濟(jì)有效地使用人力物力. .* 作為一門(mén)定量?jī)?yōu)化決策科學(xué)，起源于第二次世界作為一門(mén)定量?jī)?yōu)化決策科學(xué)，起源于第二次世界戰(zhàn)戰(zhàn)，英文原意英文原意OperationOperationResearchResearch；二、運(yùn)籌學(xué)簡(jiǎn)史二、運(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è)科

3、學(xué)等分支 20世紀(jì)世紀(jì)50年代中期錢(qián)學(xué)森和許國(guó)志教授引入年代中期錢(qián)學(xué)森和許國(guó)志教授引入 “運(yùn)用學(xué)運(yùn)用學(xué)” 1957年年 取取 “運(yùn)籌運(yùn)籌”二字，將二字，將OR正式命名為正式命名為“運(yùn)運(yùn)籌學(xué)籌學(xué)” 開(kāi)始應(yīng)用于建筑業(yè)和紡織業(yè)開(kāi)始應(yīng)用于建筑業(yè)和紡織業(yè)史記史記中中“夫運(yùn)籌帷幄之中，決勝千里之外夫運(yùn)籌帷幄之中，決勝千里之外”*線性規(guī)劃線性規(guī)劃數(shù)數(shù)學(xué)學(xué)規(guī)規(guī)劃劃非線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃組組合合優(yōu)優(yōu)化化最優(yōu)計(jì)數(shù)問(wèn)題最優(yōu)計(jì)數(shù)問(wèn)題網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)優(yōu)化排序問(wèn)題排序問(wèn)題統(tǒng)籌圖統(tǒng)籌圖隨隨機(jī)機(jī)優(yōu)優(yōu)化化對(duì)策論對(duì)策論排隊(duì)論排隊(duì)論庫(kù)存論庫(kù)存論決策分析決策分析可靠性分析可靠性分析三、運(yùn)

4、三、運(yùn) 籌籌 學(xué)學(xué) 主主 要要 內(nèi)內(nèi) 容容*數(shù)學(xué)規(guī)劃模型的數(shù)學(xué)描述數(shù)學(xué)規(guī)劃模型的數(shù)學(xué)描述下的最大值或最小值，下的最大值或最小值，.,.,)(mihi210 x.,.,),)()(piggii2100 xx),.,(nxxxx321x將一個(gè)優(yōu)化問(wèn)題用數(shù)學(xué)式子來(lái)描述，即求函數(shù)將一個(gè)優(yōu)化問(wèn)題用數(shù)學(xué)式子來(lái)描述，即求函數(shù))(xfu 在約束條件在約束條件和和*數(shù)學(xué)規(guī)劃問(wèn)題的一般形式數(shù)學(xué)規(guī)劃問(wèn)題的一般形式約約束束條條件件決策變量決策變量njiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(minnjiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min目

5、標(biāo)函數(shù)目標(biāo)函數(shù)tosubjectts .“受約束于”之意*網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)優(yōu)化研究解決生產(chǎn)組織、計(jì)劃管理中諸如最短路徑問(wèn)研究解決生產(chǎn)組織、計(jì)劃管理中諸如最短路徑問(wèn)題、最小連接問(wèn)題、最小費(fèi)用流問(wèn)題、最優(yōu)分派題、最小連接問(wèn)題、最小費(fèi)用流問(wèn)題、最優(yōu)分派問(wèn)題及關(guān)鍵線路圖等。特別在計(jì)劃和安排大型復(fù)問(wèn)題及關(guān)鍵線路圖等。特別在計(jì)劃和安排大型復(fù)雜工程時(shí)，網(wǎng)絡(luò)技術(shù)是重要的工具雜工程時(shí)，網(wǎng)絡(luò)技術(shù)是重要的工具*排隊(duì)論排隊(duì)論是是20世紀(jì)初由丹麥數(shù)學(xué)家世紀(jì)初由丹麥數(shù)學(xué)家Erlang應(yīng)用數(shù)學(xué)方法在研應(yīng)用數(shù)學(xué)方法在研究電話話務(wù)理論過(guò)程中而發(fā)展起來(lái)的一門(mén)學(xué)科，排究電話話務(wù)理論過(guò)程中而發(fā)展起來(lái)的一門(mén)學(xué)科，排隊(duì)論也稱隨機(jī)服務(wù)系統(tǒng)理論

6、，排隊(duì)論是定量的研究隊(duì)論也稱隨機(jī)服務(wù)系統(tǒng)理論，排隊(duì)論是定量的研究排隊(duì)問(wèn)題，尋找系統(tǒng)內(nèi)在規(guī)律，尋找供求關(guān)系平衡排隊(duì)問(wèn)題，尋找系統(tǒng)內(nèi)在規(guī)律，尋找供求關(guān)系平衡的最優(yōu)方案。的最優(yōu)方案。如機(jī)器等待修理、船舶等待裝卸、顧客等待服務(wù)等如機(jī)器等待修理、船舶等待裝卸、顧客等待服務(wù)等*對(duì)策論對(duì)策論研究具有利害沖突的各方，如何制定對(duì)自己有利研究具有利害沖突的各方，如何制定對(duì)自己有利從而戰(zhàn)勝對(duì)手的斗爭(zhēng)策略從而戰(zhàn)勝對(duì)手的斗爭(zhēng)策略田忌賽馬田忌賽馬*運(yùn)籌學(xué)的應(yīng)用重點(diǎn)運(yùn)籌學(xué)的應(yīng)用重點(diǎn)1.市場(chǎng)銷(xiāo)售市場(chǎng)銷(xiāo)售在廣告預(yù)算和媒體的選擇、競(jìng)爭(zhēng)性定價(jià)、新產(chǎn)品開(kāi)發(fā)、在廣告預(yù)算和媒體的選擇、競(jìng)爭(zhēng)性定價(jià)、新產(chǎn)品開(kāi)發(fā)、銷(xiāo)售計(jì)劃的制定等方面。如美國(guó)

7、杜邦公司在五十年代起銷(xiāo)售計(jì)劃的制定等方面。如美國(guó)杜邦公司在五十年代起就非常重視將作業(yè)研究用于研究如合做好廣告工作、產(chǎn)就非常重視將作業(yè)研究用于研究如合做好廣告工作、產(chǎn)品定價(jià)和新產(chǎn)品的引入。品定價(jià)和新產(chǎn)品的引入。2. 生產(chǎn)計(jì)劃生產(chǎn)計(jì)劃在總體計(jì)劃方面主要是從總體確定生產(chǎn)、儲(chǔ)存和勞動(dòng)力在總體計(jì)劃方面主要是從總體確定生產(chǎn)、儲(chǔ)存和勞動(dòng)力的配合等計(jì)劃以適應(yīng)變動(dòng)的需求計(jì)劃，主要用線性規(guī)劃的配合等計(jì)劃以適應(yīng)變動(dòng)的需求計(jì)劃，主要用線性規(guī)劃和仿真方法等。此外，還可用于生產(chǎn)作業(yè)計(jì)劃、日程表和仿真方法等。此外，還可用于生產(chǎn)作業(yè)計(jì)劃、日程表的編排等。還有在合理下料、配料問(wèn)題、物料管理等方的編排等。還有在合理下料、配料問(wèn)題

8、、物料管理等方面的應(yīng)用。面的應(yīng)用。 *3. 庫(kù)存管理庫(kù)存管理存貨模型將庫(kù)存理論與計(jì)算器的物料管理信息系統(tǒng)相結(jié)存貨模型將庫(kù)存理論與計(jì)算器的物料管理信息系統(tǒng)相結(jié)合，主要應(yīng)用于多種物料庫(kù)存量的管理，確定某些設(shè)備合，主要應(yīng)用于多種物料庫(kù)存量的管理，確定某些設(shè)備的能力或容量，如工廠的庫(kù)存、停車(chē)廠的大小、新增發(fā)的能力或容量，如工廠的庫(kù)存、停車(chē)廠的大小、新增發(fā)電設(shè)備容量大小、計(jì)算機(jī)的主存儲(chǔ)器容量、合理的水庫(kù)電設(shè)備容量大小、計(jì)算機(jī)的主存儲(chǔ)器容量、合理的水庫(kù)容量等。容量等。 4. 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題這里涉及空運(yùn)、水運(yùn)、公路運(yùn)輸、鐵路運(yùn)輸、捷運(yùn)、管這里涉及空運(yùn)、水運(yùn)、公路運(yùn)輸、鐵路運(yùn)輸、捷運(yùn)、管道運(yùn)輸和廠內(nèi)運(yùn)輸?shù)取?/p>

9、包括班次調(diào)度計(jì)劃及人員服務(wù)時(shí)道運(yùn)輸和廠內(nèi)運(yùn)輸?shù)?。包括班次調(diào)度計(jì)劃及人員服務(wù)時(shí)間安排等問(wèn)題。間安排等問(wèn)題。 *5.財(cái)政和會(huì)計(jì)財(cái)政和會(huì)計(jì)這里涉及預(yù)算、貸款、成本分析、定價(jià)、投資、證券管這里涉及預(yù)算、貸款、成本分析、定價(jià)、投資、證券管理、現(xiàn)金管理等。用得較多的方法是：統(tǒng)計(jì)分析、數(shù)學(xué)理、現(xiàn)金管理等。用得較多的方法是：統(tǒng)計(jì)分析、數(shù)學(xué)規(guī)劃、決策分析。此外，還有盈虧點(diǎn)分析法、價(jià)值分析規(guī)劃、決策分析。此外，還有盈虧點(diǎn)分析法、價(jià)值分析法等。法等。 6. 人事管理人事管理這里涉及六方面。這里涉及六方面。(1)人員的獲得和需求估計(jì)；人員的獲得和需求估計(jì)；(2)人才人才的開(kāi)發(fā)，即進(jìn)行教育和訓(xùn)練；的開(kāi)發(fā)，即進(jìn)行教育和訓(xùn)

10、練；(3)人員的分配，主要是人員的分配，主要是各種指派問(wèn)題；各種指派問(wèn)題；(4)各類人員的合理利用問(wèn)題；各類人員的合理利用問(wèn)題；(5)人才人才的評(píng)價(jià)，其中有如何測(cè)定一個(gè)人對(duì)組織、社會(huì)的貢獻(xiàn)；的評(píng)價(jià)，其中有如何測(cè)定一個(gè)人對(duì)組織、社會(huì)的貢獻(xiàn)；(6)薪資和津貼的確定等。薪資和津貼的確定等。 *7.設(shè)備維修、更新和可靠度、項(xiàng)目選擇和評(píng)價(jià)設(shè)備維修、更新和可靠度、項(xiàng)目選擇和評(píng)價(jià)如電力系統(tǒng)的可靠度分析、核能電廠的可靠度以及風(fēng)如電力系統(tǒng)的可靠度分析、核能電廠的可靠度以及風(fēng)險(xiǎn)評(píng)估等。險(xiǎn)評(píng)估等。 8.工程的最佳化設(shè)計(jì)工程的最佳化設(shè)計(jì)在土木、建筑、水利、信息、電子、電機(jī)、光學(xué)、機(jī)在土木、建筑、水利、信息、電子、電機(jī)

11、、光學(xué)、機(jī)械、環(huán)境和化工等領(lǐng)域皆有作業(yè)研究的應(yīng)用。械、環(huán)境和化工等領(lǐng)域皆有作業(yè)研究的應(yīng)用。 9.城市管理城市管理包括各種緊急服務(wù)救難系統(tǒng)的設(shè)計(jì)和運(yùn)用。如消防隊(duì)救包括各種緊急服務(wù)救難系統(tǒng)的設(shè)計(jì)和運(yùn)用。如消防隊(duì)救火站、救護(hù)車(chē)、警車(chē)等分布點(diǎn)的設(shè)立。美國(guó)曾用等候理火站、救護(hù)車(chē)、警車(chē)等分布點(diǎn)的設(shè)立。美國(guó)曾用等候理論方法來(lái)確定紐約市緊急電話站的值班人數(shù)。加拿大亦論方法來(lái)確定紐約市緊急電話站的值班人數(shù)。加拿大亦曾研究一城市警車(chē)的配置和負(fù)則范圍，事故發(fā)生后警車(chē)曾研究一城市警車(chē)的配置和負(fù)則范圍，事故發(fā)生后警車(chē)應(yīng)走的路線等。應(yīng)走的路線等。*分析與表述問(wèn)題分析與表述問(wèn)題建立模型建立模型對(duì)模型和由模型導(dǎo)出的解進(jìn)行檢驗(yàn)

12、對(duì)模型和由模型導(dǎo)出的解進(jìn)行檢驗(yàn)建立起對(duì)解的有效控制建立起對(duì)解的有效控制對(duì)問(wèn)題求解對(duì)問(wèn)題求解方案實(shí)施方案實(shí)施不滿意不滿意滿意滿意運(yùn)籌學(xué)應(yīng)用步驟運(yùn)籌學(xué)應(yīng)用步驟*五、運(yùn)籌學(xué)在數(shù)學(xué)建模競(jìng)賽中的地位五、運(yùn)籌學(xué)在數(shù)學(xué)建模競(jìng)賽中的地位有人統(tǒng)計(jì)：有人統(tǒng)計(jì)：在全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題中有在全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題中有40%可以用運(yùn)籌可以用運(yùn)籌學(xué)中的優(yōu)化方法解決學(xué)中的優(yōu)化方法解決*1. CUMCM-1995A: 一個(gè)飛行管理問(wèn)題一個(gè)飛行管理問(wèn)題 2. CUMCM-2000B: 鋼管訂購(gòu)與運(yùn)輸鋼管訂購(gòu)與運(yùn)輸3. CUMCM-2003B：露天礦生產(chǎn)的車(chē)輛安排：露天礦生產(chǎn)的車(chē)輛安排4. CUMCM-2000D: 空洞探

13、測(cè)空洞探測(cè)5. CUMCM-2006 B: 艾滋病療法的評(píng)價(jià)及療效的預(yù)測(cè)艾滋病療法的評(píng)價(jià)及療效的預(yù)測(cè)6. CUMCM-2006 C : 易拉罐形狀和尺寸的最優(yōu)設(shè)計(jì)易拉罐形狀和尺寸的最優(yōu)設(shè)計(jì)7. CUMCM-2009B：眼科病床的合理安排：眼科病床的合理安排*線線 性性 規(guī)規(guī) 劃劃線性規(guī)劃實(shí)例* 在各類經(jīng)濟(jì)活動(dòng)中，經(jīng)常遇到這樣的問(wèn)題：在各類經(jīng)濟(jì)活動(dòng)中，經(jīng)常遇到這樣的問(wèn)題：在生產(chǎn)條件不變的情況下，如何通過(guò)統(tǒng)籌安排，在生產(chǎn)條件不變的情況下，如何通過(guò)統(tǒng)籌安排，改進(jìn)生產(chǎn)組織或計(jì)劃，合理安排人力、物力資源，改進(jìn)生產(chǎn)組織或計(jì)劃，合理安排人力、物力資源，組織生產(chǎn)過(guò)程，使總的經(jīng)濟(jì)效益最好。組織生產(chǎn)過(guò)程，使總的經(jīng)

14、濟(jì)效益最好?？梢曰苫蚪频鼗煽梢曰苫蚪频鼗伞熬€性規(guī)劃線性規(guī)劃”（Linear Linear ProgrammingProgramming，簡(jiǎn)記為，簡(jiǎn)記為L(zhǎng)PLP）問(wèn)題）問(wèn)題*1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 制訂生產(chǎn)計(jì)劃，使每天獲利最大制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買(mǎi)到元可買(mǎi)到1桶牛奶，買(mǎi)嗎？若買(mǎi)，每天最多買(mǎi)多少桶牛奶，買(mǎi)嗎？若買(mǎi)，每天最多買(mǎi)多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲

15、利增加到的獲利增加到 30元元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？公斤，應(yīng)否改變生產(chǎn)計(jì)劃？ 每天：每天：例例: 奶制品生產(chǎn)計(jì)劃奶制品生產(chǎn)計(jì)劃 *1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動(dòng)時(shí)間勞動(dòng)時(shí)間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472xxzMax每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時(shí)間時(shí)間480

16、小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天*1212121127264. .501284803100,0Max zxxstxxxxxx x*一般形式一般形式 目標(biāo)函數(shù)目標(biāo)函數(shù) 價(jià)值向量?jī)r(jià)值向量 價(jià)值系數(shù)價(jià)值系數(shù) 決策變量決策變量Tnccc),(1 njcj, 2 , 1, njxj, 2 , 1, nqjxqjxmsibxaxaxaspibxaxaxapibxaxaxatsxcxczjjininiiininiiininiinn, 1, 0, 1, 0, 1, 1, 1,.min(max)22112211221111右端向量右端向量 mbbb1系系數(shù)數(shù)矩矩陣陣 mn

17、mmnnaaaaaaaaaA212222111211非負(fù)約束非負(fù)約束自由變量自由變量*規(guī)范形式規(guī)范形式標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式 0.minxbAxtsxcT 0.minxbAxtsxcT三種形式的三種形式的LP問(wèn)題全都是等價(jià)的，即一種形式問(wèn)題全都是等價(jià)的，即一種形式的的LP可以簡(jiǎn)單的變換為另一種形式的可以簡(jiǎn)單的變換為另一種形式的LP，且它，且它們有相同的解們有相同的解 .* max fx)(min(xfAxbAxb1nx1nAxxb1nAxxb0b jxjxjx jjjxxx *min. .0Tc xst Axbx最優(yōu)值：最優(yōu)解的目標(biāo)函數(shù)值最優(yōu)值：最優(yōu)解的目標(biāo)函數(shù)值 0, xbAxxD線性規(guī)劃模型的解

18、的幾種情況線性規(guī)劃模型的解的幾種情況 *線性規(guī)劃問(wèn)題線性規(guī)劃問(wèn)題有可行解有可行解(Feasible)無(wú)可行解無(wú)可行解（Infeasible）有最優(yōu)解（有最優(yōu)解（Optimal）無(wú)最優(yōu)解無(wú)最優(yōu)解(Unbounded)*圖解法圖解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx約約束束條條件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMax目標(biāo)目標(biāo)函數(shù)函數(shù) Z=0Z=2400Z=3600c在在B(20,30)點(diǎn)得到最優(yōu)解點(diǎn)得到最優(yōu)解模型求解模型求解 軟件實(shí)現(xiàn)軟件實(shí)現(xiàn) LIND

19、O 6.1 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY

20、) ANALYSIS? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤(rùn)，利潤(rùn)3360元。元。 結(jié)果解釋結(jié)果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2原料無(wú)剩余原料無(wú)剩余時(shí)間

21、無(wú)剩余時(shí)間無(wú)剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 結(jié)果解釋結(jié)果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.00

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

23、OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000

24、INFINITY 40.000000最優(yōu)解不變時(shí)目標(biāo)函最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍數(shù)系數(shù)允許變化范圍 DO RANGE(SENSITIVITY) ANALYSIS? Yesx1系數(shù)范圍系數(shù)范圍(64,96) x2系數(shù)范圍系數(shù)范圍(48,72) A1獲利增加到獲利增加到 30元元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃公斤，應(yīng)否改變生產(chǎn)計(jì)劃 x1系數(shù)由系數(shù)由24 3=72增加增加為為30 3=90，在在允許范圍內(nèi)允許范圍內(nèi) 不變！不變！(約束條件不變約束條件不變)結(jié)果解釋結(jié)果解釋 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES

25、 VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000影子價(jià)格

26、有意義時(shí)約束右端的允許變化范圍影子價(jià)格有意義時(shí)約束右端的允許變化范圍 原料最多增加原料最多增加10 時(shí)間最多增加時(shí)間最多增加53 35元可買(mǎi)到元可買(mǎi)到1桶牛奶，每天最多買(mǎi)多少？桶牛奶，每天最多買(mǎi)多少？最多買(mǎi)最多買(mǎi)10桶桶!(目標(biāo)函數(shù)不變目標(biāo)函數(shù)不變)運(yùn)運(yùn) 輸輸 問(wèn)問(wèn) 題題分分 析：析：v決策變量決策變量 設(shè)設(shè) 表示從倉(cāng)庫(kù)表示從倉(cāng)庫(kù) 運(yùn)往零售點(diǎn)運(yùn)往零售點(diǎn) 的物資數(shù)量的物資數(shù)量ijxiAjBv目標(biāo)函數(shù)目標(biāo)函數(shù)目標(biāo)：運(yùn)費(fèi)最省目標(biāo)：運(yùn)費(fèi)最省11 11121213 1314142121222223232424zc xc xc xc xc xc xc xc xv約束條件約束條件從倉(cāng)庫(kù)運(yùn)出總量不超過(guò)可用總量

27、，運(yùn)入零售從倉(cāng)庫(kù)運(yùn)出總量不超過(guò)可用總量，運(yùn)入零售點(diǎn)的數(shù)量不低于需求量。由于總供給量等于點(diǎn)的數(shù)量不低于需求量。由于總供給量等于總需求量，所以都是等號(hào)。即總需求量，所以都是等號(hào)。即2 , 1;4321 iaxxxxiiiii4 , 3 , 2 , 1;21 jbxxjjj蘊(yùn)含約束蘊(yùn)含約束：數(shù)量非負(fù)：數(shù)量非負(fù)4 , 3 , 2 , 1, 2 , 1; 0 jixij模模 型：型：收發(fā)平衡型的運(yùn)輸問(wèn)題收發(fā)平衡型的運(yùn)輸問(wèn)題1111min. .,1,2,1,2,0,1,2,1,2,mnijijijnijijmijjiijzc xstxa imxbjnxim jn從從m個(gè)發(fā)點(diǎn)個(gè)發(fā)點(diǎn)Ai,i=1,2, ,m,

28、調(diào)運(yùn)物資到調(diào)運(yùn)物資到n個(gè)收點(diǎn)個(gè)收點(diǎn)Bj,j=1,2, ,n；發(fā)點(diǎn)；發(fā)點(diǎn)Ai有物資有物資ai，收點(diǎn)，收點(diǎn)Bj的需求量是的需求量是bj，從，從Ai運(yùn)到運(yùn)到Bj的運(yùn)價(jià)為的運(yùn)價(jià)為cij，且收發(fā)平衡，如何運(yùn)輸，且收發(fā)平衡，如何運(yùn)輸使總運(yùn)費(fèi)最省使總運(yùn)費(fèi)最省運(yùn)輸問(wèn)題的求解過(guò)程運(yùn)輸問(wèn)題的求解過(guò)程為了便于討論，以一個(gè)運(yùn)輸問(wèn)題實(shí)例的求解過(guò)為了便于討論，以一個(gè)運(yùn)輸問(wèn)題實(shí)例的求解過(guò)程來(lái)介紹如何用程來(lái)介紹如何用LINDO或或LINGO軟件求解運(yùn)輸問(wèn)軟件求解運(yùn)輸問(wèn)題模型題模型.例例 設(shè)設(shè) m=3, n=4即為有即為有3個(gè)產(chǎn)地和個(gè)產(chǎn)地和4個(gè)銷(xiāo)地的運(yùn)個(gè)銷(xiāo)地的運(yùn)輸問(wèn)題，其產(chǎn)量、銷(xiāo)量及單位運(yùn)費(fèi)如表輸問(wèn)題，其產(chǎn)量、銷(xiāo)量及單位運(yùn)費(fèi)如

29、表7-1所示所示.試求總運(yùn)費(fèi)最少的運(yùn)輸方案，以及總運(yùn)費(fèi)試求總運(yùn)費(fèi)最少的運(yùn)輸方案，以及總運(yùn)費(fèi).解：解：從前面的分析來(lái)看，運(yùn)輸問(wèn)題屬于線性規(guī)劃問(wèn)從前面的分析來(lái)看，運(yùn)輸問(wèn)題屬于線性規(guī)劃問(wèn)題，因此，不論是題，因此，不論是LINDO軟件或軟件或LINGO軟件都可以對(duì)軟件都可以對(duì)該問(wèn)題求解該問(wèn)題求解. 寫(xiě)出寫(xiě)出LINDO軟件的模型（程序），程序名：軟件的模型（程序），程序名：exam0702.ltx. ! 3 Warehouse, 4 Customer Transportation Problem! The objectivemin 6x11 + 2x12 + 6x13 + 7x14 + 4x21 + 9

30、x22 + 5x23 + 3x24 + 8x31 + 8x32 + x33 + 5x34subject 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 = 156) x12 + x22 + x32 = 177) x13 + x23 + x33 = 228) x14 + x24 + x34 = 12endLINDO軟件的計(jì)算結(jié)果如下：軟

31、件的計(jì)算結(jié)果如下：LP OPTIMUM FOUND AT STEP 6 OBJECTIVE FUNCTION VALUE 1) 161.0000 VARIABLE VALUE REDUCED COST X11 2.000000 0.000000 X12 17.000000 0.000000 X13 1.000000 0.000000 X14 0.000000 2.000000 X21 13.000000 0.000000 X22 0.000000 9.000000 X23 0.000000 1.000000X24 12.000000 0.000000 X31 0.000000 7.000000

32、 X32 0.000000 11.000000 X33 21.000000 0.000000 X34 0.000000 5.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 10.000000 0.000000 3) 0.000000 2.000000 4) 0.000000 5.000000 5) 0.000000 -6.000000 6) 0.000000 -2.000000 7) 0.000000 -6.000000 8) 0.000000 -5.000000 NO. ITERATIONS= 6事實(shí)上，我們關(guān)心更多的是那些非零變量，因此事實(shí)上，我們關(guān)心

33、更多的是那些非零變量，因此,可選擇可選擇LINDO中的命令只列出非零變量中的命令只列出非零變量. OBJECTIVE FUNCTION VALUE 1) 161.0000 VARIABLE VALUE REDUCED COST X11 2.000000 0.000000 X12 17.000000 0.000000 X13 1.000000 0.000000 X21 13.000000 0.000000 X24 12.000000 0.000000 X33 21.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 3) 0.000000 2.000

34、000 4) 0.000000 5.000000 5) 0.000000 -6.000000 6) 0.000000 -2.000000 7) 0.000000 -6.000000 8) 0.000000 -5.000000 NO. ITERATIONS= 6參考文獻(xiàn)參考文獻(xiàn)1 謝金星，薛毅謝金星，薛毅.優(yōu)化建模與優(yōu)化建模與LINDO/LINGO軟件軟件M.北京：北京： 清華大學(xué)出版社清華大學(xué)出版社.2005,7.2 姜啟源，謝金星，葉俊姜啟源，謝金星，葉俊.數(shù)學(xué)模型（第三版）數(shù)學(xué)模型（第三版）M.北京：北京： 高等教育出版社高等教育出版社.2005,12.3 刁在筠，劉桂真等刁在筠，劉桂真等

35、. 運(yùn)籌學(xué)運(yùn)籌學(xué)M.北京：高等教育出版北京：高等教育出版 社社.2009,12.4 牛映武，運(yùn)籌學(xué)牛映武，運(yùn)籌學(xué)M.西安：西安交通大學(xué)出版社西安：西安交通大學(xué)出版社. 2006.55 胡運(yùn)權(quán)，運(yùn)籌學(xué)教程胡運(yùn)權(quán)，運(yùn)籌學(xué)教程M. 北京：清華大學(xué)出版社北京：清華大學(xué)出版社. 2007.4*整整 數(shù)數(shù) 規(guī)規(guī) 劃劃要求變量取整數(shù)值的線性規(guī)劃問(wèn)題稱為要求變量取整數(shù)值的線性規(guī)劃問(wèn)題稱為整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃要求變量取要求變量取0 0或或1 1的線性規(guī)劃問(wèn)題稱為的線性規(guī)劃問(wèn)題稱為0-10-1規(guī)劃規(guī)劃只要求部分變量取整數(shù)值的線性規(guī)劃稱為只要求部分變量取整數(shù)值的線性規(guī)劃稱為混合整數(shù)線混合整數(shù)線性規(guī)劃性規(guī)劃*例例

36、投資決策問(wèn)題投資決策問(wèn)題 某某部部門(mén)門(mén)在在今今后后五五年年中中可可用用于于投投資資的的資資金金總總額額為為B萬(wàn)萬(wàn)元元，有有)2( nn個(gè)個(gè)可可以以考考慮慮的的投投資資項(xiàng)項(xiàng)目目，假假定定每每個(gè)個(gè)項(xiàng)項(xiàng)目目最最多多投投資資一一次次， 第第), 1(njj 個(gè)個(gè)項(xiàng)項(xiàng)目目所所需需的的資資金金為為jb萬(wàn)萬(wàn)元元，將將會(huì)會(huì)獲獲得得的的利利潤(rùn)潤(rùn)為為jc萬(wàn)萬(wàn)元元.問(wèn)問(wèn)應(yīng)應(yīng)如如何何選選擇擇投投資資項(xiàng)項(xiàng)目目，才才能能使使獲獲得得的的總總利利潤(rùn)潤(rùn)最最大大. 解解*B21n1b2bnb1c2cnc個(gè)項(xiàng)目個(gè)項(xiàng)目決定投資第決定投資第jjjbb1 jjcc1 個(gè)項(xiàng)目個(gè)項(xiàng)目決定不投資第決定不投資第jjb00 jc00 個(gè)項(xiàng)目；個(gè)

37、項(xiàng)目；，決定不投資第，決定不投資第個(gè)項(xiàng)目；個(gè)項(xiàng)目；，決定投資第，決定投資第jjxj01投資決策變量投資決策變量 *設(shè)獲得的總利潤(rùn)為設(shè)獲得的總利潤(rùn)為z，則上述問(wèn)題的數(shù)學(xué)模型為，則上述問(wèn)題的數(shù)學(xué)模型為 njxBxbtsxczjnjjjnjjj, 1100.max11，或或0)1( jjxx變量限制為整數(shù)本質(zhì)上是一個(gè)非線性約束，它不可變量限制為整數(shù)本質(zhì)上是一個(gè)非線性約束，它不可能用線性約束來(lái)代替它能用線性約束來(lái)代替它. *1954年年 G.G.Dantzig D.R.Fulkerson and S.M.Johnson研究研究推銷(xiāo)商問(wèn)題（貨郎擔(dān)問(wèn)題）推銷(xiāo)商問(wèn)題（貨郎擔(dān)問(wèn)題）,首先提出首先提出破子圈方法

38、破子圈方法和將和將問(wèn)題問(wèn)題分解為幾個(gè)子問(wèn)題之和分解為幾個(gè)子問(wèn)題之和的思想，這是的思想，這是割平面方法割平面方法和和分分枝定界法枝定界法的萌芽的萌芽1958年年 R.E.Gomory 創(chuàng)立創(chuàng)立割平面算法割平面算法1960年年 A.H.Land and A.G.Doig 對(duì)推銷(xiāo)商問(wèn)題提出對(duì)推銷(xiāo)商問(wèn)題提出分解算分解算法法，緊接著，緊接著，E.Balas等人將其發(fā)展成一般的等人將其發(fā)展成一般的分枝定界法分枝定界法，從而形成獨(dú)立的整數(shù)規(guī)劃分支從而形成獨(dú)立的整數(shù)規(guī)劃分支1993年年 W.J.Cook 平行計(jì)算平行計(jì)算研究研究10907064個(gè)城市的貨郎擔(dān)個(gè)城市的貨郎擔(dān)問(wèn)題問(wèn)題整數(shù)規(guī)劃簡(jiǎn)史整數(shù)規(guī)劃簡(jiǎn)史*例例

39、旅行售貨員問(wèn)題旅行售貨員問(wèn)題 （貨郎擔(dān)問(wèn)題）（貨郎擔(dān)問(wèn)題）(TSP問(wèn)題）問(wèn)題）解*對(duì)每一對(duì)城市對(duì)每一對(duì)城市iv和和jv，我們指定一個(gè)變量，我們指定一個(gè)變量ijx，令，令 ，其其它它情情況況；直直接接進(jìn)進(jìn)入入，如如果果推推銷(xiāo)銷(xiāo)員員決決定定從從01jiijvvx首先，每個(gè)城市恰好進(jìn)入一次，即首先，每個(gè)城市恰好進(jìn)入一次，即njxniij, 0, 10 nixnjij, 0, 10 其次，每個(gè)城市恰好離開(kāi)一次，即其次，每個(gè)城市恰好離開(kāi)一次，即*第三，不能第三，不能出現(xiàn)多于一個(gè)互不連通的旅行路線圈，出現(xiàn)多于一個(gè)互不連通的旅行路線圈，且不排除任何可能的旅行路線且不排除任何可能的旅行路線 1 22 11 2

40、2 33 11 22 32-1-11122nnni ii ii ii ii ii ii iiiiixxxxxxxxxn*常用算法：常用算法：割平面算法、分枝定界法、解割平面算法、分枝定界法、解0-10-1規(guī)劃的隱枚規(guī)劃的隱枚舉法、分解算法、舉法、分解算法、 群論方法、動(dòng)態(tài)規(guī)劃方法群論方法、動(dòng)態(tài)規(guī)劃方法一般只能用來(lái)解決中小型的一般只能用來(lái)解決中小型的ILPILP問(wèn)題問(wèn)題近似算法近似算法19931993年年7 7月月 W.J.Cook 并行計(jì)算并行計(jì)算 10907064個(gè)城市個(gè)城市貨郎擔(dān)問(wèn)題貨郎擔(dān)問(wèn)題計(jì)算機(jī)模擬法計(jì)算機(jī)模擬法 如如Monte-Carlo方法方法丁的蛙泳成績(jī)退步到丁的蛙泳成績(jī)退步到1

41、15”2；戊的自由泳成績(jī)進(jìn)；戊的自由泳成績(jī)進(jìn)步到步到57”5, 組成接力隊(duì)的方案是否應(yīng)該調(diào)整組成接力隊(duì)的方案是否應(yīng)該調(diào)整？如何選拔隊(duì)員組成如何選拔隊(duì)員組成4 4 100100米混合泳接力隊(duì)米混合泳接力隊(duì)? ?例例 混合泳接力隊(duì)的選拔混合泳接力隊(duì)的選拔 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”45名候選人的名候選人的百米成績(jī)百米成績(jī)窮舉法窮舉法：組成接力隊(duì)的方案共有組成接力隊(duì)的方案共有5!=120種種。目標(biāo)

42、目標(biāo)函數(shù)函數(shù)若選擇隊(duì)員若選擇隊(duì)員i參加泳姿參加泳姿j 的比賽，記的比賽，記xij=1, , 否則記否則記xij=0 0-10-1規(guī)劃模型規(guī)劃模型 cij( (秒秒) )隊(duì)員隊(duì)員i 第第j 種泳姿的百米成績(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.44151jiijijxcZMin每種泳姿有且只有每種泳姿有且只有1 1人人 5, 1, 141ixjij4, 1, 151jx

43、iij模型求解模型求解 最優(yōu)解：最優(yōu)解：x14 = x21 = x32 = x43 = 1, 其它變量為其它變量為0;成績(jī)?yōu)槌煽?jī)?yōu)?53.2( (秒秒) )=413”2 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 =1END INT 20 輸入輸入LINDO求解求解 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”11

44、0”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”4甲甲 自由泳、乙自由泳、乙 蝶泳、蝶泳、丙丙 仰泳、丁仰泳、丁 蛙泳蛙泳. .丁蛙泳丁蛙泳c43 = =69.675.2，戊自由泳，戊自由泳c54= =62.4 57.5, , 方案是否調(diào)整？方案是否調(diào)整？ 敏感性分析？敏感性分析？乙乙 蝶泳、丙蝶泳、丙 仰泳、仰泳、丁丁 蛙泳、戊蛙泳、戊 自由泳自由泳IP規(guī)劃一般沒(méi)有與規(guī)劃一般沒(méi)有與LP規(guī)劃相類似的理論，規(guī)劃相類似的理論，LINDO輸出的敏感性分析結(jié)果通常是沒(méi)有意義的。

45、輸出的敏感性分析結(jié)果通常是沒(méi)有意義的。最優(yōu)解：最優(yōu)解：x21 = x32 = x43 = x51 = 1, 成績(jī)?yōu)槌煽?jī)?yōu)?17”7 c43, c54 的新數(shù)據(jù)重新輸入模型，用的新數(shù)據(jù)重新輸入模型，用LINDO求解求解 指派指派( (Assignment) )問(wèn)題問(wèn)題：每項(xiàng)任務(wù)有且只有一人承擔(dān)，每項(xiàng)任務(wù)有且只有一人承擔(dān)，每人只能承擔(dān)一項(xiàng)每人只能承擔(dān)一項(xiàng)，效益不同，怎樣分派使總效益最大，效益不同，怎樣分派使總效益最大. 討論討論甲甲 自由泳、乙自由泳、乙 蝶泳、蝶泳、丙丙 仰泳、丁仰泳、丁 蛙泳蛙泳. .原原方方案案為了選修課程門(mén)數(shù)最少，應(yīng)學(xué)習(xí)哪些課程為了選修課程門(mén)數(shù)最少，應(yīng)學(xué)習(xí)哪些課程 ？ 例例

46、 選課策略選課策略要求至少選兩門(mén)數(shù)學(xué)課、三門(mén)運(yùn)籌學(xué)課和兩門(mén)計(jì)算機(jī)課要求至少選兩門(mén)數(shù)學(xué)課、三門(mén)運(yùn)籌學(xué)課和兩門(mén)計(jì)算機(jī)課 課號(hào)課號(hào)課名課名學(xué)分學(xué)分所屬類別所屬類別先修課要求先修課要求1微積分微積分5數(shù)學(xué)數(shù)學(xué) 2線性代數(shù)線性代數(shù)4數(shù)學(xué)數(shù)學(xué) 3最優(yōu)化方法最優(yōu)化方法4數(shù)學(xué)；運(yùn)籌學(xué)數(shù)學(xué)；運(yùn)籌學(xué)微積分；線性代數(shù)微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)3數(shù)學(xué)；計(jì)算機(jī)數(shù)學(xué)；計(jì)算機(jī)計(jì)算機(jī)編程計(jì)算機(jī)編程5應(yīng)用統(tǒng)計(jì)應(yīng)用統(tǒng)計(jì)4數(shù)學(xué)；運(yùn)籌學(xué)數(shù)學(xué)；運(yùn)籌學(xué)微積分；線性代數(shù)微積分；線性代數(shù)6計(jì)算機(jī)模擬計(jì)算機(jī)模擬3計(jì)算機(jī)；運(yùn)籌學(xué)計(jì)算機(jī)；運(yùn)籌學(xué)計(jì)算機(jī)編程計(jì)算機(jī)編程7計(jì)算機(jī)編程計(jì)算機(jī)編程2計(jì)算機(jī)計(jì)算機(jī) 8預(yù)測(cè)理論預(yù)測(cè)理論2運(yùn)籌學(xué)運(yùn)籌學(xué)應(yīng)用統(tǒng)

47、計(jì)應(yīng)用統(tǒng)計(jì)9數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)實(shí)驗(yàn)3運(yùn)籌學(xué)；計(jì)算機(jī)運(yùn)籌學(xué)；計(jì)算機(jī)微積分；線性代數(shù)微積分；線性代數(shù)選修課程最少，且學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程選修課程最少，且學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程 ？ 0-1規(guī)劃模型規(guī)劃模型 決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) xi=1 選修課號(hào)選修課號(hào)i 的的課程（課程（xi=0 不選）不選） 91iixZMin選修課程總數(shù)最少選修課程總數(shù)最少 約束條件約束條件最少最少2門(mén)數(shù)學(xué)課，門(mén)數(shù)學(xué)課，3門(mén)運(yùn)籌學(xué)課，門(mén)運(yùn)籌學(xué)課，2門(mén)計(jì)算機(jī)課。門(mén)計(jì)算機(jī)課。 254321xxxxx398653xxxxx29764xxxx課號(hào)課號(hào)課名課名所屬類別所屬類別1微積分微積分?jǐn)?shù)學(xué)數(shù)學(xué)2線性代數(shù)線性代數(shù)數(shù)學(xué)

48、數(shù)學(xué)3最優(yōu)化方法最優(yōu)化方法數(shù)學(xué)；運(yùn)籌學(xué)數(shù)學(xué)；運(yùn)籌學(xué)4數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)學(xué)；計(jì)算機(jī)數(shù)學(xué)；計(jì)算機(jī)5應(yīng)用統(tǒng)計(jì)應(yīng)用統(tǒng)計(jì)數(shù)學(xué)；運(yùn)籌學(xué)數(shù)學(xué)；運(yùn)籌學(xué)6計(jì)算機(jī)模擬計(jì)算機(jī)模擬計(jì)算機(jī)；運(yùn)籌學(xué)計(jì)算機(jī)；運(yùn)籌學(xué)7計(jì)算機(jī)編程計(jì)算機(jī)編程計(jì)算機(jī)計(jì)算機(jī)8預(yù)測(cè)理論預(yù)測(cè)理論運(yùn)籌學(xué)運(yùn)籌學(xué)9數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)；計(jì)算機(jī)運(yùn)籌學(xué)；計(jì)算機(jī)先修課程要求先修課程要求74xx 02215xxx076 xx058xx02219xxx最優(yōu)解：最優(yōu)解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它為其它為0；6門(mén)課程，總學(xué)分門(mén)課程，總學(xué)分21 02213xxx0-1規(guī)劃模型規(guī)劃模型 約束條件約束條件x3=1必有必有x1 = x

49、2 =12313,xxxx074 xx模型求解（模型求解（LINDO） 課號(hào)課號(hào)課名課名先修課要求先修課要求1微積分微積分 2線性代數(shù)線性代數(shù) 3最優(yōu)化方法最優(yōu)化方法微積分；線性代數(shù)微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)編程計(jì)算機(jī)編程5應(yīng)用統(tǒng)計(jì)應(yīng)用統(tǒng)計(jì)微積分；線性代數(shù)微積分；線性代數(shù)6計(jì)算機(jī)模擬計(jì)算機(jī)模擬計(jì)算機(jī)編程計(jì)算機(jī)編程7計(jì)算機(jī)編程計(jì)算機(jī)編程 8預(yù)測(cè)理論預(yù)測(cè)理論應(yīng)用統(tǒng)計(jì)應(yīng)用統(tǒng)計(jì)9數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)實(shí)驗(yàn)微積分；線性代數(shù)微積分；線性代數(shù)學(xué)分最多學(xué)分最多多目標(biāo)優(yōu)化的處理方法：化成單目標(biāo)優(yōu)化。多目標(biāo)優(yōu)化的處理方法：化成單目標(biāo)優(yōu)化。兩目標(biāo)兩目標(biāo)( (多目標(biāo)多目標(biāo)) )規(guī)劃規(guī)劃 9876543213223

50、43445xxxxxxxxxWMax,WZMin討論：選修課程最少，學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？討論：選修課程最少，學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？ 91iixZMin課程最少課程最少 以以學(xué)分最多為目標(biāo)，不學(xué)分最多為目標(biāo)，不管課程多少。管課程多少。 以課程最少以課程最少為目標(biāo)，不為目標(biāo)，不管學(xué)分多少。管學(xué)分多少。最優(yōu)解如上，最優(yōu)解如上，6門(mén)課門(mén)課程，總學(xué)分程，總學(xué)分21 。最優(yōu)解顯然是選修所最優(yōu)解顯然是選修所有有9門(mén)課程門(mén)課程 。多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃 在在課程最少的前提下課程最少的前提下以以學(xué)分最多為目標(biāo)。學(xué)分最多為目標(biāo)。最優(yōu)解：最優(yōu)解： x1 = x2 = x3 = x5 = x7 = x9

51、=1, 其它為其它為0；總總學(xué)分由學(xué)分由21增至增至22。注意：最優(yōu)解不唯一！注意：最優(yōu)解不唯一！課號(hào)課號(hào)課名課名學(xué)分學(xué)分1微積分微積分52線性代數(shù)線性代數(shù)43最優(yōu)化方法最優(yōu)化方法44數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計(jì)應(yīng)用統(tǒng)計(jì)46計(jì)算機(jī)模擬計(jì)算機(jī)模擬37計(jì)算機(jī)編程計(jì)算機(jī)編程28預(yù)測(cè)理論預(yù)測(cè)理論29數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)實(shí)驗(yàn)3 LINDO無(wú)法告訴優(yōu)化無(wú)法告訴優(yōu)化問(wèn)題的解是否唯一。問(wèn)題的解是否唯一?？蓪⒖蓪9 =1 易為易為x6 =1增加約束增加約束 ，以學(xué)分最多為目標(biāo)求解。以學(xué)分最多為目標(biāo)求解。691iix*多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃 對(duì)學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開(kāi)。對(duì)學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如

52、三七開(kāi)。 987654321322343445xxxxxxxxxW91iixZWZWZYMin3 . 07 . 021WZWZYMin3 . 07 . 021=-0.8x1-0.5x2-0.5x3-0.2x4-0.5x5-0.2x6+0.1x7+0.1x8-0.2x9*多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃 對(duì)學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開(kāi)。對(duì)學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開(kāi)。 最優(yōu)解：最優(yōu)解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x9 =1，其它為其它為0；總學(xué)分總學(xué)分28。課號(hào)課號(hào)課名課名學(xué)分學(xué)分1微積分微積分52線性代數(shù)線性代數(shù)43最優(yōu)化方法最優(yōu)化方法4

53、4數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計(jì)應(yīng)用統(tǒng)計(jì)46計(jì)算機(jī)模擬計(jì)算機(jī)模擬37計(jì)算機(jī)編程計(jì)算機(jī)編程28預(yù)測(cè)理論預(yù)測(cè)理論29數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)實(shí)驗(yàn)3 *多目標(biāo)規(guī)劃的求解方法多目標(biāo)規(guī)劃的求解方法1、化多為少的方法：把多目標(biāo)規(guī)劃問(wèn)題歸為單目標(biāo)、化多為少的方法：把多目標(biāo)規(guī)劃問(wèn)題歸為單目標(biāo)的數(shù)學(xué)規(guī)劃的數(shù)學(xué)規(guī)劃(線性規(guī)劃或非線線性規(guī)劃或非線 性規(guī)劃性規(guī)劃)問(wèn)題進(jìn)行求解問(wèn)題進(jìn)行求解 線性加權(quán)和法線性加權(quán)和法 理想點(diǎn)法理想點(diǎn)法 2、分層求解法、分層求解法 假若目標(biāo)函數(shù)多目標(biāo)規(guī)劃假若目標(biāo)函數(shù)多目標(biāo)規(guī)劃 的各個(gè)分目標(biāo)可以按其的各個(gè)分目標(biāo)可以按其在問(wèn)題中的重要程度排出先后次序，先對(duì)第一個(gè)在問(wèn)題中的重要程度排出先后次序，先對(duì)第一個(gè)目標(biāo)

54、進(jìn)行極小化，設(shè)得到的最優(yōu)解目標(biāo)進(jìn)行極小化，設(shè)得到的最優(yōu)解 x,然后按固定然后按固定格式依次分層對(duì)各目標(biāo)進(jìn)行極小化格式依次分層對(duì)各目標(biāo)進(jìn)行極小化 3、層次分析法、層次分析法 *圖圖 論論 與與 網(wǎng)網(wǎng) 絡(luò)絡(luò) 優(yōu)優(yōu) 化化 圖論的研究最早可追溯到著名的圖論的研究最早可追溯到著名的七橋問(wèn)題七橋問(wèn)題. .1818世紀(jì)歐世紀(jì)歐洲的哥尼斯堡城中有一條河叫普雷格爾河，該河中有洲的哥尼斯堡城中有一條河叫普雷格爾河，該河中有兩個(gè)島，河上有七座橋，如圖所示兩個(gè)島，河上有七座橋，如圖所示. .當(dāng)時(shí)那里的人們當(dāng)時(shí)那里的人們就考慮：能否從就考慮：能否從A A、B B、C C、D D中任一地方出發(fā)，走每座中任一地方出發(fā)，走每

55、座橋一次而且只走一次，最后剛好回到出發(fā)點(diǎn)橋一次而且只走一次，最后剛好回到出發(fā)點(diǎn). .例例 公路連接問(wèn)題公路連接問(wèn)題某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來(lái)，城市連接起來(lái)， 使得從其中任何一個(gè)城市都可以經(jīng)高速公使得從其中任何一個(gè)城市都可以經(jīng)高速公路直接或間接到達(dá)另一個(gè)城市路直接或間接到達(dá)另一個(gè)城市. 假定已經(jīng)知道了任意兩個(gè)城假定已經(jīng)知道了任意兩個(gè)城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最??？間修建高速公路，使得總成本最??？ 例例 最短路問(wèn)

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

57、地，現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往個(gè)產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往N個(gè)個(gè)使用這些原材料的工廠使用這些原材料的工廠. 假定假定M個(gè)產(chǎn)地的產(chǎn)量和個(gè)產(chǎn)地的產(chǎn)量和N家工廠的家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的的運(yùn)費(fèi)已需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的的運(yùn)費(fèi)已知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？ 例例 指派問(wèn)題指派問(wèn)題(Assignment Problem)一家公司經(jīng)理準(zhǔn)備安排一家公司經(jīng)理準(zhǔn)備安排N名員工去完成名員工去完成N項(xiàng)任務(wù)，每人一項(xiàng)項(xiàng)任務(wù)，每人一項(xiàng). 由于各員工的特點(diǎn)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)由于各員工的特點(diǎn)不同

58、，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)是不同的所獲得的回報(bào)是不同的. 如何分配工作方案可以使總回如何分配工作方案可以使總回 報(bào)最報(bào)最大？大？ 例例 中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題(CPP-Chinese 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年首先提出的，所以

59、國(guó)際上稱之為中國(guó)郵遞員問(wèn)題年首先提出的，所以國(guó)際上稱之為中國(guó)郵遞員問(wèn)題. . 例例 旅行商問(wèn)題旅行商問(wèn)題/貨郎（擔(dān)）問(wèn)題貨郎（擔(dān)）問(wèn)題(TSP-Traveling Salesman Problem)一名推銷(xiāo)員準(zhǔn)備前往若干城市推銷(xiāo)產(chǎn)品一名推銷(xiāo)員準(zhǔn)備前往若干城市推銷(xiāo)產(chǎn)品. . 如何為他如何為他( (她她) )設(shè)設(shè)計(jì)一條最短的旅行路線計(jì)一條最短的旅行路線( (從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市恰好一從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市恰好一次，最后返回駐地次，最后返回駐地) )？這一問(wèn)題的研究歷史十分悠久，通常？這一問(wèn)題的研究歷史十分悠久，通常稱之為旅行商問(wèn)題稱之為旅行商問(wèn)題. . 動(dòng)動(dòng) 態(tài)態(tài) 規(guī)規(guī) 劃劃運(yùn)籌學(xué)的一個(gè)分支

60、，解決多階段決策過(guò)程最優(yōu)化運(yùn)籌學(xué)的一個(gè)分支，解決多階段決策過(guò)程最優(yōu)化的一種數(shù)學(xué)方法的一種數(shù)學(xué)方法多階段決策過(guò)程多階段決策過(guò)程指一類活動(dòng)過(guò)程，它可以分為指一類活動(dòng)過(guò)程，它可以分為若干個(gè)相互聯(lián)系的階段，在每個(gè)階段都需要作出決若干個(gè)相互聯(lián)系的階段，在每個(gè)階段都需要作出決策策. 這個(gè)決策不僅決定這一階段的效益，而且決定下這個(gè)決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)一階段的初始狀態(tài). 每個(gè)階段的決策確定以后，就得每個(gè)階段的決策確定以后，就得到一個(gè)決策序列，稱為到一個(gè)決策序列，稱為策略策略. 求解目的就是求一個(gè)策求解目的就是求一個(gè)策略，使各階段的效益的總和達(dá)到最優(yōu)，這種把一個(gè)略，使各階段的效