運(yùn)籌學(xué)在數(shù)學(xué)建模中的應(yīng)用復(fù)習(xí)課程

1、延延 安安 大大 學(xué)學(xué) 第第 四四 屆屆 大大 學(xué)學(xué) 生生 數(shù)數(shù) 學(xué)學(xué) 建建 模模 競競 賽賽 專專 題題 報(bào)報(bào) 告告運(yùn)籌學(xué)在數(shù)學(xué)建模中的應(yīng)用運(yùn)運(yùn) 籌籌 學(xué)學(xué) 概概 況況運(yùn)籌學(xué)的定義運(yùn)籌學(xué)簡史運(yùn)籌學(xué)的主要內(nèi)容及應(yīng)用重點(diǎn)運(yùn)籌學(xué)應(yīng)用步驟運(yùn)籌學(xué)在數(shù)學(xué)建模競賽中的地位運(yùn)籌學(xué)是一種給出問題不壞的答案的藝術(shù)，否則的運(yùn)籌學(xué)是一種給出問題不壞的答案的藝術(shù)，否則的話問題的結(jié)果會(huì)更壞。話問題的結(jié)果會(huì)更壞。一、運(yùn)籌學(xué)的定義一、運(yùn)籌學(xué)的定義 運(yùn)籌學(xué)運(yùn)籌學(xué)( (辭海辭海) )：2020世紀(jì)世紀(jì)4040年代開始形成的一年代開始形成的一門學(xué)科，主要研究門學(xué)科，主要研究經(jīng)濟(jì)活動(dòng)與軍事活動(dòng)中能用數(shù)量經(jīng)濟(jì)活動(dòng)與軍事活動(dòng)中能用數(shù)量

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

3、決策科學(xué)、預(yù)測科學(xué)等分支 20世紀(jì)世紀(jì)50年代中期錢學(xué)森和許國志教授引入年代中期錢學(xué)森和許國志教授引入 “運(yùn)用學(xué)運(yùn)用學(xué)” 1957年年 取取 “運(yùn)籌運(yùn)籌”二字，將二字，將OR正式命名為正式命名為“運(yùn)運(yùn)籌學(xué)籌學(xué)” 開始應(yīng)用于建筑業(yè)和紡織業(yè)開始應(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ù)問題最優(yōu)計(jì)數(shù)問題網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)優(yōu)化排序問題排序問題統(tǒng)籌圖統(tǒng)籌圖隨隨機(jī)機(jī)優(yōu)優(yōu)化化對策論對策論排隊(duì)論排隊(duì)論庫存論庫存論決策分析決策分析可靠性分析可

4、靠性分析三、運(yùn)三、運(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)化問題用數(shù)學(xué)式子來描述，即求函數(shù)將一個(gè)優(yōu)化問題用數(shù)學(xué)式子來描述，即求函數(shù))(xfu 在約束條件在約束條件和和數(shù)學(xué)規(guī)劃問題的一般形式數(shù)學(xué)規(guī)劃問題的一般形式約約束束條條件件決策變量決策變量njiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(minnjiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)

5、(min目標(biāo)函數(shù)目標(biāo)函數(shù)tosubjectts .“受約束于”之意網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)優(yōu)化研究解決生產(chǎn)組織、計(jì)劃管理中諸如最短路徑問研究解決生產(chǎn)組織、計(jì)劃管理中諸如最短路徑問題、最小連接問題、最小費(fèi)用流問題、最優(yōu)分派題、最小連接問題、最小費(fèi)用流問題、最優(yōu)分派問題及關(guān)鍵線路圖等。特別在計(jì)劃和安排大型復(fù)問題及關(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ù)理論過程中而發(fā)展起來的一門學(xué)科，排究電話話務(wù)理論過程中而發(fā)展起來的一門學(xué)科，排隊(duì)論也稱隨機(jī)服務(wù)系

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

7、國杜邦公司在五十年代起銷售計(jì)劃的制定等方面。如美國杜邦公司在五十年代起就非常重視將作業(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ì)劃、日程表的編排等。還有在合理下料、配料問題、物料管理等方的編排等。還有在合理下料、配料問

8、題、物料管理等方面的應(yīng)用。面的應(yīng)用。 3. 庫存管理庫存管理存貨模型將庫存理論與計(jì)算器的物料管理信息系統(tǒng)相結(jié)存貨模型將庫存理論與計(jì)算器的物料管理信息系統(tǒng)相結(jié)合，主要應(yīng)用于多種物料庫存量的管理，確定某些設(shè)備合，主要應(yīng)用于多種物料庫存量的管理，確定某些設(shè)備的能力或容量，如工廠的庫存、停車廠的大小、新增發(fā)的能力或容量，如工廠的庫存、停車廠的大小、新增發(fā)電設(shè)備容量大小、計(jì)算機(jī)的主存儲(chǔ)器容量、合理的水庫電設(shè)備容量大小、計(jì)算機(jī)的主存儲(chǔ)器容量、合理的水庫容量等。容量等。 4. 運(yùn)輸問題運(yù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í)間安排等問題。間安排等問題。 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)人才人才的開發(fā)，即進(jìn)行教育和訓(xùn)練；的開發(fā)，即進(jìn)行教育和訓(xùn)練

10、；(3)人員的分配，主要是人員的分配，主要是各種指派問題；各種指派問題；(4)各類人員的合理利用問題；各類人員的合理利用問題；(5)人才人才的評價(jià)，其中有如何測定一個(gè)人對組織、社會(huì)的貢獻(xiàn)；的評價(jià)，其中有如何測定一個(gè)人對組織、社會(huì)的貢獻(xiàn)；(6)薪資和津貼的確定等。薪資和津貼的確定等。 7.設(shè)備維修、更新和可靠度、項(xiàng)目選擇和評價(jià)設(shè)備維修、更新和可靠度、項(xiàng)目選擇和評價(jià)如電力系統(tǒng)的可靠度分析、核能電廠的可靠度以及風(fēng)如電力系統(tǒng)的可靠度分析、核能電廠的可靠度以及風(fēng)險(xiǎn)評估等。險(xiǎn)評估等。 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ù)車、警車等分布點(diǎn)的設(shè)立。美國曾用等候理火站、救護(hù)車、警車等分布點(diǎn)的設(shè)立。美國曾用等候理論方法來確定紐約市緊急電話站的值班人數(shù)。加拿大亦論方法來確定紐約市緊急電話站的值班人數(shù)。加拿大亦曾研究一城市警車的配置和負(fù)則范圍，事故發(fā)生后警車曾研究一城市警車的配置和負(fù)則范圍，事故發(fā)生后警車應(yīng)走的路線等。應(yīng)走的路線等。分析與表述問題分析與表述問題建立模型建立模型對模型和由模型導(dǎo)出的解進(jìn)行檢驗(yàn)對模型

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

13、5. CUMCM-2006 B: 艾滋病療法的評價(jià)及療效的預(yù)測艾滋病療法的評價(jià)及療效的預(yù)測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)常遇到這樣的問題：在各類經(jīng)濟(jì)活動(dòng)中，經(jīng)常遇到這樣的問題：在生產(chǎn)條件不變的情況下，如何通過統(tǒng)籌安排，在生產(chǎn)條件不變的情況下，如何通過統(tǒng)籌安排，改進(jìn)生產(chǎn)組織或計(jì)劃，合理安排人力、物力資源，改進(jìn)生產(chǎn)組織或計(jì)劃，合理安排人力、物力資源，組織生產(chǎn)過程，使總的經(jīng)濟(jì)效益最好。組織生產(chǎn)過程，使總的經(jīng)濟(jì)效益最好。可

14、以化成或近似地化成可以化成或近似地化成“線性規(guī)劃線性規(guī)劃”（Linear Linear ProgrammingProgramming，簡記為，簡記為LPLP）問題）問題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元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時(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小時(shí)小時(shí) 至多加工

16、至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天1212121127264. .501284803100,0Max zxxstxxxxxx x一般形式一般形式 目標(biāo)函數(shù)目標(biāo)函數(shù) 價(jià)值向量價(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ù)矩矩陣陣 mnmmnnaaaaaaa

17、aaA212222111211非負(fù)約束非負(fù)約束自由變量自由變量規(guī)范形式規(guī)范形式標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式 0.minxbAxtsxcT 0.minxbAxtsxcT三種形式的三種形式的LP問題全都是等價(jià)的，即一種形式問題全都是等價(jià)的，即一種形式的的LP可以簡單的變換為另一種形式的可以簡單的變換為另一種形式的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ī)劃模型的解的幾種情況線性規(guī)劃模型的解的

18、幾種情況 線性規(guī)劃問題線性規(guī)劃問題有可行解有可行解(Feasible)無可行解無可行解（Infeasible）有最優(yōu)解（有最優(yōu)解（Optimal）無最優(yōu)解無最優(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) LINDO 6.1 max 72x1+6

19、4x2st2）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) ANALYSIS? No20

20、桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤，利潤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原料無剩余原料無剩余時(shí)間無剩余時(shí)間無剩余加工能力剩余加工

21、能力剩余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.000000 2.000000 4)

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

23、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 INFINITY 40.0000

24、00最優(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 VARIABLE CURREN

25、T 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à)格有意義時(shí)約束右端的允許變化范圍影

26、子價(jià)格有意義時(shí)約束右端的允許變化范圍 原料最多增加原料最多增加10 時(shí)間最多增加時(shí)間最多增加53 35元可買到元可買到1桶牛奶，每天最多買多少？桶牛奶，每天最多買多少？最多買最多買10桶桶!(目標(biāo)函數(shù)不變目標(biāo)函數(shù)不變)運(yùn)運(yùn) 輸輸 問問 題題分分 析：析：v決策變量決策變量 設(shè)設(shè) 表示從倉庫表示從倉庫 運(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約束條件約束條件從倉庫運(yùn)出總量不超過可用總量，運(yùn)入零售從倉庫運(yùn)出總量不超過可

27、用總量，運(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)輸問題收發(fā)平衡型的運(yù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,調(diào)運(yùn)物資到調(diào)運(yùn)物資到n個(gè)收點(diǎn)個(gè)收

28、點(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)輸問題的求解過程運(yùn)輸問題的求解過程為了便于討論，以一個(gè)運(yùn)輸問題實(shí)例的求解過為了便于討論，以一個(gè)運(yùn)輸問題實(shí)例的求解過程來介紹如何用程來介紹如何用LINDO或或LINGO軟件求解運(yùn)輸問軟件求解運(yùn)輸問題模型題模型.例例 設(shè)設(shè) m=3, n=4即為有即為有3個(gè)產(chǎn)地和個(gè)產(chǎn)地和4個(gè)銷地的運(yùn)個(gè)銷地的運(yùn)輸問題，其產(chǎn)量、銷量及單位運(yùn)費(fèi)如表輸問題，其產(chǎn)量、銷量及單位運(yùn)費(fèi)如表7-1所示所示.試求總運(yùn)費(fèi)最少

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

30、4 + 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é)果如下：軟件的計(jì)算結(jié)果如下：LP OPTI

31、MUM 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 X32 0.000000 11

32、.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.000000 4) 0.000000

34、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 刁在筠，劉桂真等刁在筠，劉桂真等. 運(yùn)籌學(xué)運(yùn)籌學(xué)M.北京：高等教

35、育出版北京：高等教育出版 社社.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ī)劃問題稱為要求變量取整數(shù)值的線性規(guī)劃問題稱為整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃要求變量取要求變量取0 0或或1 1的線性規(guī)劃問題稱為的線性規(guī)劃問題稱為0-10-1規(guī)劃規(guī)劃只要求部分變量取整數(shù)值的線性規(guī)劃稱為只要求部分變量取整數(shù)值的線性規(guī)劃稱為混合整數(shù)線混合整數(shù)線性規(guī)劃性規(guī)劃例例投資決策問題投資決策問題 某某部部門

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

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

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

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

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

41、到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名候選人的名候選人的百米成績百米成績窮舉法窮舉法：組成接力隊(duì)的方案共有組成接力隊(duì)的方案共有5!=120種種。目標(biāo)目標(biāo)函數(shù)函數(shù)若選擇隊(duì)員若選擇隊(duì)員i參加泳姿參加泳姿

42、j 的比賽，記的比賽，記xij=1, , 否則記否則記xij=0 0-10-1規(guī)劃模型規(guī)劃模型 cij( (秒秒) )隊(duì)員隊(duì)員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.44151jiijijxcZMin每種泳姿有且只有每種泳姿有且只有1 1人人 5, 1, 141ixjij4, 1, 151jxiij模型求解模型求解 最優(yōu)解：最優(yōu)解：x14 =

43、 x21 = x32 = x43 = 1, 其它變量為其它變量為0;成績?yōu)槌煽優(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”110”107”4仰泳仰泳115”6106”107”8

44、114”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ī)劃一般沒有與規(guī)劃一般沒有與LP規(guī)劃相類似的理論，規(guī)劃相類似的理論，LINDO輸出的敏感性分析結(jié)果通常是沒有意義的。輸出的敏感性分析結(jié)果通常是沒有意義的。最優(yōu)解：最優(yōu)

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

46、課和兩門計(jì)算機(jī)課要求至少選兩門數(shù)學(xué)課、三門運(yùn)籌學(xué)課和兩門計(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ù)測理論預(yù)測理論2運(yùn)籌學(xué)運(yùn)籌學(xué)應(yīng)用統(tǒng)計(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é)

47、；計(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門數(shù)學(xué)課，門數(shù)學(xué)課，3門運(yùn)籌學(xué)課，門運(yùn)籌學(xué)課，2門計(jì)算機(jī)課。門計(jì)算機(jī)課。 254321xxxxx398653xxxxx29764xxxx課號(hào)課號(hào)課名課名所屬類別所屬類別1微積分微積分?jǐn)?shù)學(xué)數(shù)學(xué)2線性代數(shù)線性代數(shù)數(shù)學(xué)數(shù)學(xué)3最優(yōu)化方法最優(yōu)化方法數(shù)學(xué)；運(yùn)籌學(xué)數(shù)學(xué)；運(yùn)籌學(xué)

48、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ù)測理論預(yù)測理論運(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門課程，總學(xué)分門課程，總學(xué)分21 02213xxx0-1規(guī)劃模型規(guī)劃模型 約束條件約束條件x3=1必有必有x1 = x2 =12313,xxxx074 xx模型求解（模

49、型求解（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ù)測理論預(yù)測理論應(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ī)劃 987654321322343445xxxxxxxxxWMax,WZMin討

50、論：選修課程最少，學(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門課門課程，總學(xué)分程，總學(xué)分21 。最優(yōu)解顯然是選修所最優(yōu)解顯然是選修所有有9門課程門課程 。多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃 在在課程最少的前提下課程最少的前提下以以學(xué)分最多為目標(biāo)。學(xué)分最多為目標(biāo)。最優(yōu)解：最優(yōu)解： x1 = x2 = x3 = x5 = x7 = x9 =1, 其它為其它為0；總總學(xué)分由學(xué)分由21增至增

51、至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ù)測理論預(yù)測理論29數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)實(shí)驗(yàn)3 LINDO無法告訴優(yōu)化無法告訴優(yōu)化問題的解是否唯一。問題的解是否唯一。可將可將x9 =1 易為易為x6 =1增加約束增加約束 ，以學(xué)分最多為目標(biāo)求解。以學(xué)分最多為目標(biāo)求解。691iix多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃 對學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開。對學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開。 987654321322343445xxx

52、xxxxxxW91iixZWZWZYMin3 . 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ī)劃 對學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開。對學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開。 最優(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)化方法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ì)

53、算機(jī)模擬37計(jì)算機(jī)編程計(jì)算機(jī)編程28預(yù)測理論預(yù)測理論29數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)實(shí)驗(yàn)3 多目標(biāo)規(guī)劃的求解方法多目標(biāo)規(guī)劃的求解方法1、化多為少的方法：把多目標(biāo)規(guī)劃問題歸為單目標(biāo)、化多為少的方法：把多目標(biāo)規(guī)劃問題歸為單目標(biāo)的數(shù)學(xué)規(guī)劃的數(shù)學(xué)規(guī)劃(線性規(guī)劃或非線線性規(guī)劃或非線 性規(guī)劃性規(guī)劃)問題進(jì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)可以按其在問題中的重要程度排出先后次序，先對第一個(gè)在問題中的重要程度排出先后次序，先對第一個(gè)目標(biāo)進(jìn)行極小化，設(shè)得到的最優(yōu)解目標(biāo)進(jìn)行極小化，設(shè)得到的最優(yōu)解

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

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

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

57、地運(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)輸成本最低？ 例例 指派問題指派問題(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)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)是不同的所獲得的

58、回報(bào)是不同的. 如何分配工作方案可以使總回如何分配工作方案可以使總回 報(bào)最報(bào)最大？大？ 例例 中國郵遞員問題中國郵遞員問題(CPP-Chinese Postman Problem)一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件. . 如何為他如何為他( (她她) )設(shè)計(jì)設(shè)計(jì)一條最短的投遞路線一條最短的投遞路線( (從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局至少一次，最后返回郵局) )？由于這一問題是我國？由于這一問題是我國管梅谷管梅谷教教授授19601960年首先提出的，所以國際上稱之為中國郵遞員問題年首先提出的，所以國際上稱之為中

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

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