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

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

2、要研究門學科，主要研究經(jīng)濟活動與軍事活動中能用數(shù)量經(jīng)濟活動與軍事活動中能用數(shù)量來表達的有關運用、籌劃與管理方面的問題來表達的有關運用、籌劃與管理方面的問題，它根，它根據(jù)問題的要求，通過數(shù)學的分析與運算，做出綜合據(jù)問題的要求，通過數(shù)學的分析與運算，做出綜合性合理安排，以達到較經(jīng)濟有效地使用人力物力性合理安排，以達到較經(jīng)濟有效地使用人力物力. . 作為一門定量優(yōu)化決策科學，起源于第二次世界作為一門定量優(yōu)化決策科學，起源于第二次世界戰(zhàn)戰(zhàn)，英文原意英文原意OperationOperationResearchResearch；二、運籌學簡史二、運籌學簡史深水炸彈的釋放問題防空系統(tǒng)的預警問題運籌學的一些分

3、支英美?？哲娮鲬?zhàn)參謀部組成了運籌學研究小組二戰(zhàn)中二戰(zhàn)后軍事工、商業(yè)領域存儲論、決策科學、預測科學等分支 20世紀世紀50年代中期錢學森和許國志教授引入年代中期錢學森和許國志教授引入 “運用學運用學” 1957年年 取取 “運籌運籌”二字，將二字，將OR正式命名為正式命名為“運運籌學籌學” 開始應用于建筑業(yè)和紡織業(yè)開始應用于建筑業(yè)和紡織業(yè)史記史記中中“夫運籌帷幄之中，決勝千里之外夫運籌帷幄之中，決勝千里之外”線性規(guī)劃線性規(guī)劃數(shù)數(shù)學學規(guī)規(guī)劃劃非線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃動態(tài)規(guī)劃動態(tài)規(guī)劃多目標規(guī)劃多目標規(guī)劃組組合合優(yōu)優(yōu)化化最優(yōu)計數(shù)問題最優(yōu)計數(shù)問題網(wǎng)絡優(yōu)化網(wǎng)絡優(yōu)化排序問題排序問題統(tǒng)籌圖統(tǒng)籌圖隨

4、隨機機優(yōu)優(yōu)化化對策論對策論排隊論排隊論庫存論庫存論決策分析決策分析可靠性分析可靠性分析三、運三、運 籌籌 學學 主主 要要 內(nèi)內(nèi) 容容數(shù)學規(guī)劃模型的數(shù)學描述數(shù)學規(guī)劃模型的數(shù)學描述下的最大值或最小值。下的最大值或最小值。.,.,)(mihi210 x.,.,),)()(piggii2100 xx),.,(nxxxx321x將一個優(yōu)化問題用數(shù)學式子來描述，即求函數(shù)將一個優(yōu)化問題用數(shù)學式子來描述，即求函數(shù))(xfu 在約束條件在約束條件和和數(shù)學規(guī)劃問題的一般形式數(shù)學規(guī)劃問題的一般形式約約束束條條件件決策變量決策變量njiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min

5、njiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min目標函數(shù)目標函數(shù)tosubjectts .“受約束于”之意網(wǎng)絡優(yōu)化網(wǎng)絡優(yōu)化研究解決生產(chǎn)組織、計劃管理中諸如最短路徑問研究解決生產(chǎn)組織、計劃管理中諸如最短路徑問題、最小連接問題、最小費用流問題、最優(yōu)分派題、最小連接問題、最小費用流問題、最優(yōu)分派問題及關鍵線路圖等。特別在計劃和安排大型復問題及關鍵線路圖等。特別在計劃和安排大型復雜工程時，網(wǎng)絡技術是重要的工具。雜工程時，網(wǎng)絡技術是重要的工具。排隊論排隊論是是20世紀初由丹麥數(shù)學家世紀初由丹麥數(shù)學家Erlang應用數(shù)學方法在研應用數(shù)學方法在研究電話話務理論過程中而發(fā)

6、展起來的一門學科，排究電話話務理論過程中而發(fā)展起來的一門學科，排隊論也稱隨機服務系統(tǒng)理論，排隊論是定量的研究隊論也稱隨機服務系統(tǒng)理論，排隊論是定量的研究排隊問題，尋找系統(tǒng)內(nèi)在規(guī)律，尋找供求關系平衡排隊問題，尋找系統(tǒng)內(nèi)在規(guī)律，尋找供求關系平衡的最優(yōu)方案。的最優(yōu)方案。如機器等待修理、船舶等待裝卸、顧客等待服務等。如機器等待修理、船舶等待裝卸、顧客等待服務等。對策論對策論研究具有利害沖突的各方，如何制定對自己有利研究具有利害沖突的各方，如何制定對自己有利從而戰(zhàn)勝對手的斗爭策略從而戰(zhàn)勝對手的斗爭策略田忌賽馬田忌賽馬運籌學的應用重點運籌學的應用重點1.市場銷售市場銷售在廣告預算和媒體的選擇、競爭性定價、

7、新產(chǎn)品開發(fā)、在廣告預算和媒體的選擇、競爭性定價、新產(chǎn)品開發(fā)、銷售計劃的制定等方面。如美國杜邦公司在五十年代起銷售計劃的制定等方面。如美國杜邦公司在五十年代起就非常重視將作業(yè)研究用于研究如合做好廣告工作、產(chǎn)就非常重視將作業(yè)研究用于研究如合做好廣告工作、產(chǎn)品定價和新產(chǎn)品的引入。品定價和新產(chǎn)品的引入。2. 生產(chǎn)計劃生產(chǎn)計劃在總體計劃方面主要是從總體確定生產(chǎn)、儲存和勞動力在總體計劃方面主要是從總體確定生產(chǎn)、儲存和勞動力的配合等計劃以適應變動的需求計劃，主要用線性規(guī)劃的配合等計劃以適應變動的需求計劃，主要用線性規(guī)劃和仿真方法等。此外，還可用于生產(chǎn)作業(yè)計劃、日程表和仿真方法等。此外，還可用于生產(chǎn)作業(yè)計劃、

8、日程表的編排等。還有在合理下料、配料問題、物料管理等方的編排等。還有在合理下料、配料問題、物料管理等方面的應用。面的應用。 3. 庫存管理庫存管理存貨模型將庫存理論與計算器的物料管理信息系統(tǒng)相結存貨模型將庫存理論與計算器的物料管理信息系統(tǒng)相結合，主要應用于多種物料庫存量的管理，確定某些設備合，主要應用于多種物料庫存量的管理，確定某些設備的能力或容量，如工廠的庫存、停車廠的大小、新增發(fā)的能力或容量，如工廠的庫存、停車廠的大小、新增發(fā)電設備容量大小、計算機的主存儲器容量、合理的水庫電設備容量大小、計算機的主存儲器容量、合理的水庫容量等。容量等。 4. 運輸問題運輸問題這里涉及空運、水運、公路運輸、

9、鐵路運輸、捷運、管這里涉及空運、水運、公路運輸、鐵路運輸、捷運、管道運輸和廠內(nèi)運輸?shù)取０ò啻握{(diào)度計劃及人員服務時道運輸和廠內(nèi)運輸?shù)?。包括班次調(diào)度計劃及人員服務時間安排等問題。間安排等問題。 5.財政和會計財政和會計這里涉及預算、貸款、成本分析、定價、投資、證券管這里涉及預算、貸款、成本分析、定價、投資、證券管理、現(xiàn)金管理等。用得較多的方法是：統(tǒng)計分析、數(shù)學理、現(xiàn)金管理等。用得較多的方法是：統(tǒng)計分析、數(shù)學規(guī)劃、決策分析。此外，還有盈虧點分析法、價值分析規(guī)劃、決策分析。此外，還有盈虧點分析法、價值分析法等。法等。 6. 人事管理人事管理這里涉及六方面。這里涉及六方面。(1)人員的獲得和需求估計；

10、人員的獲得和需求估計；(2)人才人才的開發(fā)，即進行教育和訓練；的開發(fā)，即進行教育和訓練；(3)人員的分配，主要是人員的分配，主要是各種指派問題；各種指派問題；(4)各類人員的合理利用問題；各類人員的合理利用問題；(5)人才人才的評價，其中有如何測定一個人對組織、社會的貢獻；的評價，其中有如何測定一個人對組織、社會的貢獻；(6)薪資和津貼的確定等。薪資和津貼的確定等。 7.設備維修、更新和可靠度、項目選擇和評價設備維修、更新和可靠度、項目選擇和評價如電力系統(tǒng)的可靠度分析、核能電廠的可靠度以及風如電力系統(tǒng)的可靠度分析、核能電廠的可靠度以及風險評估等。險評估等。 8.工程的最佳化設計工程的最佳化設計

11、在土木、建筑、水利、信息、電子、電機、光學、機在土木、建筑、水利、信息、電子、電機、光學、機械、環(huán)境和化工等領域皆有作業(yè)研究的應用。械、環(huán)境和化工等領域皆有作業(yè)研究的應用。 9.城市管理城市管理包括各種緊急服務救難系統(tǒng)的設計和運用。如消防隊救包括各種緊急服務救難系統(tǒng)的設計和運用。如消防隊救火站、救護車、警車等分布點的設立。美國曾用等候理火站、救護車、警車等分布點的設立。美國曾用等候理論方法來確定紐約市緊急電話站的值班人數(shù)。加拿大亦論方法來確定紐約市緊急電話站的值班人數(shù)。加拿大亦曾研究一城市警車的配置和負則范圍，事故發(fā)生后警車曾研究一城市警車的配置和負則范圍，事故發(fā)生后警車應走的路線等。應走的路

12、線等。分析與表述問題分析與表述問題建立模型建立模型對模型和由模型導出的解進行檢驗對模型和由模型導出的解進行檢驗建立起對解的有效控制建立起對解的有效控制對問題求解對問題求解方案實施方案實施不滿意不滿意滿意滿意運籌學應用步驟運籌學應用步驟五、運籌學在數(shù)學建模競賽中的地位五、運籌學在數(shù)學建模競賽中的地位有人統(tǒng)計：有人統(tǒng)計：在全國大學生數(shù)學建模競賽題中有在全國大學生數(shù)學建模競賽題中有40%可以用運籌可以用運籌學中的優(yōu)化方法解決學中的優(yōu)化方法解決1. CUMCM-1995A: 一個飛行管理問題一個飛行管理問題 2. CUMCM-2000B: 鋼管訂購與運輸鋼管訂購與運輸3. CUMCM-2003B：露天

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

14、人力、物力資源，組織生產(chǎn)過程，使總的經(jīng)濟效益最好。組織生產(chǎn)過程，使總的經(jīng)濟效益最好?？梢曰苫蚪频鼗煽梢曰苫蚪频鼗伞熬€性規(guī)劃線性規(guī)劃”（Linear Linear ProgrammingProgramming，簡記為，簡記為LPLP）問題）問題1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時間時間480小時小時 至多加工至多加工100公斤公斤A1 制訂生產(chǎn)計劃，使每天獲利最大制訂生產(chǎn)計劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資

15、最多是每小時幾元可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應否改變生產(chǎn)計劃？公斤，應否改變生產(chǎn)計劃？ 每天每天例例: 奶制品生產(chǎn)計劃奶制品生產(chǎn)計劃 1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應原料供應 5021 xx勞動時間勞動時間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標函數(shù)目標函數(shù) 216472xxzMax每天獲利每天獲利約束條件約束條件非負約束非負

16、約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時間時間480小時小時 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天1212121127264. .501284803100,0Max zxxstxxxxxx x一般形式一般形式 目標函數(shù)目標函數(shù) 價值向量價值向量 價值系數(shù)價值系數(shù) 決策變量決策變量Tnccc),(1 njcj, 2 , 1, njxj, 2 , 1, nqjxqjxmsibxaxaxaspibxaxaxapibxaxaxatsxcxczjjininiiininiiininiinn, 1, 0, 1, 0, 1, 1, 1,.min(max)221122112

17、21111右端向量右端向量 mbbb1系系數(shù)數(shù)矩矩陣陣 mnmmnnaaaaaaaaaA212222111211非負約束非負約束自由變量自由變量規(guī)范形式規(guī)范形式標準形式標準形式 0.minxbAxtsxcT 0.minxbAxtsxcT三種形式的三種形式的LP問題全都是等價的，即一種形式問題全都是等價的，即一種形式的的LP可以簡單的變換為另一種形式的可以簡單的變換為另一種形式的LP，且它，且它們有相同的解們有相同的解 . max fx)(min(xfAxbAxb1nx1nAxxb1nAxxb0b jxjxjx jjjxxx min. .0Tc xst Axbx三者皆滿足的向量三者皆滿足的向量x

18、是最優(yōu)解是最優(yōu)解最優(yōu)值：最優(yōu)解的目標函數(shù)值最優(yōu)值：最優(yōu)解的目標函數(shù)值 0, xbAxxD線性規(guī)劃模型的解的幾種情況線性規(guī)劃模型的解的幾種情況 線性規(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目標目標函數(shù)函數(shù) Z=0Z=2400Z

19、=3600c在在B(20,30)點得到最優(yōu)解點得到最優(yōu)解模型求解模型求解 軟件實現(xiàn)軟件實現(xiàn) LINDO 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.0000

20、00 0.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤，利潤3360元。元。 結果解釋結果解釋 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

21、) 40.000000 0.000000 NO. ITERATIONS= 2原料無剩余原料無剩余時間無剩余時間無剩余加工能力剩余加工能力剩余40max 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

22、 SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2最優(yōu)解下最優(yōu)解下“資源資源”增加增加1單位時單位時“效益效益”的增的增量量 原料增加原料增加1單位單位, 利潤增長利潤增長48 時間增加時間增加1單位單位, 利潤增長利潤增長2 加工能力增長不影響利潤加工能力增長不影響利潤影子價格影子價格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？35 48, 應該買！應該買！ 聘用臨時工人付出的工資最多每小時幾元？聘用臨時工人付出的工資最多每小

23、時幾元？ 2元！元！RANGES IN WHICH THE BASIS IS UNCHANGED: 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.666

24、667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000最優(yōu)解不變時目標函最優(yōu)解不變時目標函數(shù)系數(shù)允許變化范圍數(shù)系數(shù)允許變化范圍 DO RANGE(SENSITIVITY) ANALYSIS? Yesx1系數(shù)范圍系數(shù)范圍(64,96) x2系數(shù)范圍系數(shù)范圍(48,72) A1獲利增加到獲利增加到 30元元/公斤，應否改變生產(chǎn)計劃公斤，應否改變生產(chǎn)計劃 x1系數(shù)由系數(shù)由24 3=72增加增加為為30 3=90，在在允許范圍內(nèi)允許范圍內(nèi) 不變！不變！(約束條件不變約束條件不變)結果解釋結果解釋 RANGES IN WH

25、ICH THE BASIS IS UNCHANGED: 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.33

26、3332 80.000000 4 100.000000 INFINITY 40.000000影子價格有意義時約束右端的允許變化范圍影子價格有意義時約束右端的允許變化范圍 原料最多增加原料最多增加10 時間最多增加時間最多增加53 35元可買到元可買到1桶牛奶，每天最多買多少？桶牛奶，每天最多買多少？最多買最多買10桶桶!(目標函數(shù)不變目標函數(shù)不變)運運 輸輸 問問 題題分分 析：析：v決策變量決策變量 設設 表示從倉庫表示從倉庫 運往零售點運往零售點 的物資數(shù)量的物資數(shù)量ijxiAjBv目標函數(shù)目標函數(shù)目標：運費最省目標：運費最省11 11121213 13141421212222232324

27、24zc xc xc xc xc xc xc xc xv約束條件約束條件從倉庫運出總量不超過可用總量，運入零售從倉庫運出總量不超過可用總量，運入零售點的數(shù)量不低于需求量。由于總供給量等于點的數(shù)量不低于需求量。由于總供給量等于總需求量，所以都是等號。即總需求量，所以都是等號。即2 , 1;4321 iaxxxxiiiii4 , 3 , 2 , 1;21 jbxxjjj蘊含約束蘊含約束：數(shù)量非負：數(shù)量非負4 , 3 , 2 , 1, 2 , 1; 0 jixij模模 型：型：收發(fā)平衡型的運輸問題收發(fā)平衡型的運輸問題1111min. .,1,2,1,2,0,1,2,1,2,mnijijijnijij

28、mijjiijzc xstxa imxbjnxim jn從從m個發(fā)點個發(fā)點Ai,i=1,2, ,m,調(diào)運物資到調(diào)運物資到n個收點個收點Bj,j=1,2, ,n；發(fā)點；發(fā)點Ai有物資有物資ai，收點，收點Bj的需求量是的需求量是bj，從，從Ai運到運到Bj的運價為的運價為cij，且收發(fā)平衡，如何運輸，且收發(fā)平衡，如何運輸使總運費最省使總運費最省運輸問題的求解過程運輸問題的求解過程為了便于討論，以一個運輸問題實例的求解過為了便于討論，以一個運輸問題實例的求解過程來介紹如何用程來介紹如何用LINDO或或LINGO軟件求解運輸問軟件求解運輸問題模型題模型.例例 設設 m=3, n=4即為有即為有3個產(chǎn)

29、地和個產(chǎn)地和4個銷地的運個銷地的運輸問題，其產(chǎn)量、銷量及單位運費如表輸問題，其產(chǎn)量、銷量及單位運費如表7-1所示所示.試求總運費最少的運輸方案，以及總運費試求總運費最少的運輸方案，以及總運費.解：解：從前面的分析來看，運輸問題屬于線性規(guī)劃問從前面的分析來看，運輸問題屬于線性規(guī)劃問題，因此，不論是題，因此，不論是LINDO軟件或軟件或LINGO軟件都可以對軟件都可以對該問題求解該問題求解. 寫出寫出LINDO軟件的模型（程序），程序名：軟件的模型（程序），程序名：transportation.ltx ! 3 Warehouse, 4 Customer Transportation Problem

30、! The objectivemin 6x11 + 2x12 + 6x13 + 7x14 + 4x21 + 9x22 + 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 + x

31、23 + x33 = 228) x14 + x24 + x34 = 12endLINDO軟件的計算結果如下：軟件的計算結果如下：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.0000

32、00 1.000000X24 12.000000 0.000000 X31 0.000000 7.000000 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 -

33、5.000000 NO. ITERATIONS= 6事實上，我們關心更多的是那些非零變量，因此事實上，我們關心更多的是那些非零變量，因此,可選擇可選擇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.00

34、0000 ROW SLACK OR SURPLUS DUAL PRICES 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參考文獻參考文獻1 謝金星，薛毅謝金星，薛毅.優(yōu)化建模與優(yōu)化建模與LINDO/LINGO軟件軟件M.北京：北京： 清華大學出版社清華大學出版社.2005,7.2 姜啟源，謝金星，葉俊姜啟源，謝金星，葉俊.數(shù)學模型（第三版）數(shù)學模型

35、（第三版）M.北京：北京： 高等教育出版社高等教育出版社.2005,12.3 刁在筠，劉桂真等刁在筠，劉桂真等. 運籌學運籌學M.北京：高等教育出版北京：高等教育出版 社社.2009,12.4 牛映武，運籌學牛映武，運籌學M.西安：西安交通大學出版社西安：西安交通大學出版社. 2006.55 胡運權，運籌學教程胡運權，運籌學教程M. 北京：清華大學出版社北京：清華大學出版社. 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ī)劃只

36、要求部分變量取整數(shù)值的線性規(guī)劃稱為只要求部分變量取整數(shù)值的線性規(guī)劃稱為混合整數(shù)線混合整數(shù)線性規(guī)劃性規(guī)劃例例投資決策問題投資決策問題 某某部部門門在在今今后后五五年年中中可可用用于于投投資資的的資資金金總總額額為為B萬萬元元，有有)2( nn個個可可以以考考慮慮的的投投資資項項目目，假假定定每每個個項項目目最最多多投投資資一一次次， 第第), 1(njj 個個項項目目所所需需的的資資金金為為jb萬萬元元，將將會會獲獲得得的的利利潤潤為為jc萬萬元元.問問應應如如何何選選擇擇投投資資項項目目，才才能能使使獲獲得得的的總總利利潤潤最最大大. B解解21n1b2bnb1c2cnc個項目個項目決定投資第

37、決定投資第jjjbb1 jjcc1 個項目個項目決定不投資第決定不投資第jjb00 jc00 個個項項目目；，決決定定不不投投資資第第個個項項目目；，決決定定投投資資第第jjxj01投資決策變量投資決策變量 設獲得的總利潤為設獲得的總利潤為z，則上述問題的數(shù)學模型為，則上述問題的數(shù)學模型為 njxBxbtsxczjnjjjnjjj, 1100.max11，或或0)1( jjxx變量限制為整數(shù)本質(zhì)上是一個非線性約束，它不可變量限制為整數(shù)本質(zhì)上是一個非線性約束，它不可能用線性約束來代替它能用線性約束來代替它. 1954年年 G.G.Dantzig D.R.Fulkerson and S.M.Joh

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

39、算研究研究10907064個城市的貨郎擔個城市的貨郎擔問題問題整數(shù)規(guī)劃簡史整數(shù)規(guī)劃簡史例例旅行售貨員問題旅行售貨員問題 （貨郎擔問題）（貨郎擔問題）(TSP問題）問題）解對每一對城市對每一對城市iv和和jv，我們指定一個變量，我們指定一個變量ijx，令，令 ，其它情況，其它情況；直接進入直接進入，如果推銷員決定從，如果推銷員決定從01jiijvvx首先，每個城市恰好進入一次，即首先，每個城市恰好進入一次，即njxniij, 0, 10 nixnjij, 0, 10 其次，每個城市恰好離開一次，即其次，每個城市恰好離開一次，即第三，不能第三，不能出現(xiàn)多于一個互不連通的旅行路線圈，出現(xiàn)多于一個互不

40、連通的旅行路線圈，且不排除任何可能的旅行路線且不排除任何可能的旅行路線 1 22 11 22 33 11 22 32-1-11122nnni ii ii ii ii ii ii iiiiixxxxxxxxxn常用算法：常用算法：割平面算法、分枝定界法、解割平面算法、分枝定界法、解0-10-1規(guī)劃的隱枚規(guī)劃的隱枚舉法、分解算法、舉法、分解算法、 群論方法、動態(tài)規(guī)劃方法群論方法、動態(tài)規(guī)劃方法一般只能用來解決中小型的一般只能用來解決中小型的ILPILP問題問題近似算法近似算法19931993年年7 7月月 W.J.Cook 并行計算并行計算 10907064個城市個城市貨郎擔問題貨郎擔問題計算機模擬

41、法計算機模擬法 如如Monte-Carlo方法方法丁的蛙泳成績退步到丁的蛙泳成績退步到115”2；戊的自由泳成績進；戊的自由泳成績進步到步到57”5, 組成接力隊的方案是否應該調(diào)整組成接力隊的方案是否應該調(diào)整？如何選拔隊員組成如何選拔隊員組成4 4 100100米混合泳接力隊米混合泳接力隊? ?例例 混合泳接力隊的選拔混合泳接力隊的選拔 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”45名候選人的名候選人的百米

42、成績百米成績窮舉法窮舉法：組成接力隊的方案共有組成接力隊的方案共有5!=120種種。目標目標函數(shù)函數(shù)若選擇隊員若選擇隊員i參加泳姿參加泳姿j 的比賽，記的比賽，記xij=1, , 否則記否則記xij=0 0-1規(guī)劃模型規(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.44151jiijijxcZMin每種泳姿有且

43、只有每種泳姿有且只有1 1人人 5, 1, 141ixjij4, 1, 151jxiij模型求解模型求解 最優(yōu)解：最優(yōu)解：x14 = x21 = x32 = x43 = 1, 其它變量為其它變量為0;成績?yōu)槌煽優(yōu)?53.2( (秒秒) )=413”2 MIN 66.8x11+75.6x12+87x13+58.6x14 + +67.4x51+71x52+83.8x53+62.4x54SUBJECT TO x11+x12+x13+x14 =1 x51+x52+x53+x54 =1 x11+x21+x31+x41+x51 =1 x14+x24+x34+x44+x54 =1END 輸入輸入LINDO求

44、解求解 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”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ī)劃一般沒有與規(guī)劃一般沒有與LP規(guī)劃相類似的理論，

45、規(guī)劃相類似的理論，LINDO輸出的敏感性分析結果通常是沒有意義的。輸出的敏感性分析結果通常是沒有意義的。最優(yōu)解：最優(yōu)解：x21 = x32 = x43 = x51 = 1, 成績?yōu)槌煽優(yōu)?17”7 c43, c54 的新數(shù)據(jù)重新輸入模型，用的新數(shù)據(jù)重新輸入模型，用LINDO求解求解 指派指派( (Assignment) )問題問題：每項任務有且只有一人承擔，每項任務有且只有一人承擔，每人只能承擔一項每人只能承擔一項，效益不同，怎樣分派使總效益最大，效益不同，怎樣分派使總效益最大. 討論討論甲甲 自由泳、乙自由泳、乙 蝶泳、蝶泳、丙丙 仰泳、丁仰泳、丁 蛙泳蛙泳. .原原方方案案為了選修課程門數(shù)

46、最少，應學習哪些課程為了選修課程門數(shù)最少，應學習哪些課程 ？ 例例 選課策略選課策略要求至少選兩門數(shù)學課、三門運籌學課和兩門計算機課要求至少選兩門數(shù)學課、三門運籌學課和兩門計算機課 課號課號課名課名學分學分所屬類別所屬類別先修課要求先修課要求1微積分微積分5數(shù)學數(shù)學 2線性代數(shù)線性代數(shù)4數(shù)學數(shù)學 3最優(yōu)化方法最優(yōu)化方法4數(shù)學；運籌學數(shù)學；運籌學微積分；線性代數(shù)微積分；線性代數(shù)4數(shù)據(jù)結構數(shù)據(jù)結構3數(shù)學；計算機數(shù)學；計算機計算機編程計算機編程5應用統(tǒng)計應用統(tǒng)計4數(shù)學；運籌學數(shù)學；運籌學微積分；線性代數(shù)微積分；線性代數(shù)6計算機模擬計算機模擬3計算機；運籌學計算機；運籌學計算機編程計算機編程7計算機編

47、程計算機編程2計算機計算機 8預測理論預測理論2運籌學運籌學應用統(tǒng)計應用統(tǒng)計9數(shù)學實驗數(shù)學實驗3運籌學；計算機運籌學；計算機微積分；線性代數(shù)微積分；線性代數(shù)選修課程最少，且學分盡量多，應學習哪些課程選修課程最少，且學分盡量多，應學習哪些課程 ？ 0-1規(guī)劃模型規(guī)劃模型 決策變量決策變量 目標函數(shù)目標函數(shù) xi=1 選修課號選修課號i 的的課程（課程（xi=0 不選）不選） 91iixZMin選修課程總數(shù)最少選修課程總數(shù)最少 約束條件約束條件最少最少2門數(shù)學課，門數(shù)學課，3門運籌學課，門運籌學課，2門計算機課。門計算機課。 254321xxxxx398653xxxxx29764xxxx課號課號課

48、名課名所屬類別所屬類別1微積分微積分數(shù)學數(shù)學2線性代數(shù)線性代數(shù)數(shù)學數(shù)學3最優(yōu)化方法最優(yōu)化方法數(shù)學；運籌學數(shù)學；運籌學4數(shù)據(jù)結構數(shù)據(jù)結構數(shù)學；計算機數(shù)學；計算機5應用統(tǒng)計應用統(tǒng)計數(shù)學；運籌學數(shù)學；運籌學6計算機模擬計算機模擬計算機；運籌學計算機；運籌學7計算機編程計算機編程計算機計算機8預測理論預測理論運籌學運籌學9數(shù)學實驗數(shù)學實驗運籌學；計算機運籌學；計算機先修課程要求先修課程要求74xx 02215xxx076 xx058xx02219xxx最優(yōu)解：最優(yōu)解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它為其它為0；6門課程，總學分門課程，總學分21 02213xxx0

49、-1規(guī)劃模型規(guī)劃模型 約束條件約束條件x3=1必有必有x1 = x2 =12313,xxxx074 xx模型求解（模型求解（LINDO） 課號課號課名課名先修課要求先修課要求1微積分微積分 2線性代數(shù)線性代數(shù) 3最優(yōu)化方法最優(yōu)化方法微積分；線性代數(shù)微積分；線性代數(shù)4數(shù)據(jù)結構數(shù)據(jù)結構計算機編程計算機編程5應用統(tǒng)計應用統(tǒng)計微積分；線性代數(shù)微積分；線性代數(shù)6計算機模擬計算機模擬計算機編程計算機編程7計算機編程計算機編程 8預測理論預測理論應用統(tǒng)計應用統(tǒng)計9數(shù)學實驗數(shù)學實驗微積分；線性代數(shù)微積分；線性代數(shù)學分最多學分最多多目標優(yōu)化的處理方法：化成單目標優(yōu)化。多目標優(yōu)化的處理方法：化成單目標優(yōu)化。兩目標

50、兩目標( (多目標多目標) )規(guī)劃規(guī)劃 987654321322343445xxxxxxxxxWMax,WZMin討論：選修課程最少，學分盡量多，應學習哪些課程？討論：選修課程最少，學分盡量多，應學習哪些課程？ 91iixZMin課程最少課程最少 以以學分最多為目標，不學分最多為目標，不管課程多少。管課程多少。 以課程最少以課程最少為目標，不為目標，不管學分多少。管學分多少。最優(yōu)解如上，最優(yōu)解如上，6門課門課程，總學分程，總學分21 。最優(yōu)解顯然是選修所最優(yōu)解顯然是選修所有有9門課程門課程 。多目標規(guī)劃多目標規(guī)劃 在在課程最少的前提下課程最少的前提下以以學分最多為目標。學分最多為目標。最優(yōu)解：

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

52、加權形成一個目標，如三七開。對學分數(shù)和課程數(shù)加權形成一個目標，如三七開。 987654321322343445xxxxxxxxxW91iixZWZWZYMin3 . 07 . 021WZWZYMin3 . 07 . 021=-0.8x1-0.5x2-0.5x3-0.2x4-0.5x5-0.2x6+0.1x7+0.1x8-0.2x9多目標規(guī)劃多目標規(guī)劃 對學分數(shù)和課程數(shù)加權形成一個目標，如三七開。對學分數(shù)和課程數(shù)加權形成一個目標，如三七開。 最優(yōu)解：最優(yōu)解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x9 =1，其它為其它為0；總學分總學分28。課號課號課名課名學分學

53、分1微積分微積分52線性代數(shù)線性代數(shù)43最優(yōu)化方法最優(yōu)化方法44數(shù)據(jù)結構數(shù)據(jù)結構35應用統(tǒng)計應用統(tǒng)計46計算機模擬計算機模擬37計算機編程計算機編程28預測理論預測理論29數(shù)學實驗數(shù)學實驗3 多目標規(guī)劃的求解方法多目標規(guī)劃的求解方法1、化多為少的方法：把多目標規(guī)劃問題歸為單目標、化多為少的方法：把多目標規(guī)劃問題歸為單目標的數(shù)學規(guī)劃的數(shù)學規(guī)劃(線性規(guī)劃或非線線性規(guī)劃或非線 性規(guī)劃性規(guī)劃)問題進行求解問題進行求解 線性加權和法線性加權和法 理想點法理想點法 2、分層求解法、分層求解法 假若目標函數(shù)多目標規(guī)劃假若目標函數(shù)多目標規(guī)劃 的各個分目標可以按其的各個分目標可以按其在問題中的重要程度排出先后次

54、序，先對第一個在問題中的重要程度排出先后次序，先對第一個目標進行極小化，設得到的最優(yōu)解目標進行極小化，設得到的最優(yōu)解 x,然后按固定然后按固定格式依次分層對各目標進行極小化格式依次分層對各目標進行極小化 3、層次分析法、層次分析法 (Analytic Hierarchy Process, AHP)圖圖 論論 與與 網(wǎng)網(wǎng) 絡絡 優(yōu)優(yōu) 化化 圖論的研究最早可追溯到著名的圖論的研究最早可追溯到著名的七橋問題七橋問題. .1818世紀歐世紀歐洲的哥尼斯堡城中有一條河叫普雷格爾河，該河中有洲的哥尼斯堡城中有一條河叫普雷格爾河，該河中有兩個島，河上有七座橋，如圖所示兩個島，河上有七座橋，如圖所示. .當時

55、那里的人們當時那里的人們就考慮：能否從就考慮：能否從A A、B B、C C、D D中任一地方出發(fā)，走每座中任一地方出發(fā)，走每座橋一次而且只走一次，最后剛好回到出發(fā)點橋一次而且只走一次，最后剛好回到出發(fā)點. .例例 公路連接問題公路連接問題某一地區(qū)有若干個主要城市，現(xiàn)準備修建高速公路把這些某一地區(qū)有若干個主要城市，現(xiàn)準備修建高速公路把這些城市連接起來，城市連接起來， 使得從其中任何一個城市都可以經(jīng)高速公使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達另一個城市路直接或間接到達另一個城市. 假定已經(jīng)知道了任意兩個城假定已經(jīng)知道了任意兩個城市之間修建高速公路的成本，那么應如何決定在哪些城市市之間

56、修建高速公路的成本，那么應如何決定在哪些城市間修建高速公路，使得總成本最?。块g修建高速公路，使得總成本最??？ 例例 最短路問題（最短路問題（SPP-Shortest Path Problem）一名貨柜車司機奉命在最短的時間內(nèi)將一車貨物從甲地運一名貨柜車司機奉命在最短的時間內(nèi)將一車貨物從甲地運往乙地往乙地. 從甲地到乙地的公路網(wǎng)縱橫交錯，因此有多種行車從甲地到乙地的公路網(wǎng)縱橫交錯，因此有多種行車路線，這名司機應選擇哪條線路呢？假設貨柜車的運行速路線，這名司機應選擇哪條線路呢？假設貨柜車的運行速度是恒定的，那么這一問題相當于需要找到一條從甲地到度是恒定的，那么這一問題相當于需要找到一條從甲地到乙地

57、的最短路乙地的最短路. 例例 運輸問題運輸問題(Transportation Problem)某種原材料有某種原材料有M個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運往個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運往N個個使用這些原材料的工廠使用這些原材料的工廠. 假定假定M個產(chǎn)地的產(chǎn)量和個產(chǎn)地的產(chǎn)量和N家工廠的家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的的運費已需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的的運費已知，那么如何安排運輸方案可以使總運輸成本最低？知，那么如何安排運輸方案可以使總運輸成本最低？ 例例 指派問題指派問題(Assignment Problem)一家公司經(jīng)理準備安排一家公司經(jīng)理準備安排N名員工去

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

59、局至少一次，最后返回郵局) )？由于這一問題是我國？由于這一問題是我國管梅谷管梅谷教教授授19601960年首先提出的，所以國際上稱之為中國郵遞員問題年首先提出的，所以國際上稱之為中國郵遞員問題. . 例例 旅行商問題旅行商問題/貨郎（擔）問題貨郎（擔）問題(TSP-Traveling Salesman Problem)一名推銷員準備前往若干城市推銷產(chǎn)品一名推銷員準備前往若干城市推銷產(chǎn)品. . 如何為他如何為他( (她她) )設設計一條最短的旅行路線計一條最短的旅行路線( (從駐地出發(fā)，經(jīng)過每個城市恰好一從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地次，最后返回駐地) )？這一問題的研究歷史十

60、分悠久，通常？這一問題的研究歷史十分悠久，通常稱之為旅行商問題稱之為旅行商問題. . 動動 態(tài)態(tài) 規(guī)規(guī) 劃劃運籌學的一個分支，解決多階段決策過程最優(yōu)化運籌學的一個分支，解決多階段決策過程最優(yōu)化的一種數(shù)學方法的一種數(shù)學方法多階段決策過程多階段決策過程指一類活動過程，它可以分為指一類活動過程，它可以分為若干個相互聯(lián)系的階段，在每個階段都需要作出決若干個相互聯(lián)系的階段，在每個階段都需要作出決策策. 這個決策不僅決定這一階段的效益，而且決定下這個決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)一階段的初始狀態(tài). 每個階段的決策確定以后，就得每個階段的決策確定以后，就得到一個決策序列，稱為到一個決