數學實驗：線性規(guī)劃

1、單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級1單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級1 單擊此處編輯母版副標題樣式1單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/20221數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 12002.5.編輯ppt重慶大學數理學院國家級精品課程數學實驗課件數學實驗之線性規(guī)劃SHUXUESHIYANZHIXIANXINGGUIHUA課件制作：數學實驗課程組單擊此處編輯母版標題樣式 單擊此處編輯

2、母版文本樣式 第二級 第三級 第四級 第五級2單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2 單擊此處編輯母版副標題樣式2單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/20222數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 22002.5.編輯ppt1理解優(yōu)化模型的三個要素:決策變量，目標函數和約束條件；掌握用MATLAB優(yōu)化工具箱求解線性規(guī)劃的方法；了解線性規(guī)劃模型中的靈敏度分析方法；掌握如何使用軟件來實現分析；體驗由實際問題建立線性規(guī)劃模型的全過程。實驗目的單

3、擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級3單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級3 單擊此處編輯母版副標題樣式3單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/20223數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 32002.5.編輯ppt成功的優(yōu)化例子成功的優(yōu)化例子“最優(yōu)人員安排”為美國航空每年節(jié)約兩千萬美元. 單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級4單擊此處編輯母版標題樣

4、式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級4 單擊此處編輯母版副標題樣式4單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/20224數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 42002.5.編輯ppt成功的優(yōu)化例子成功的優(yōu)化例子 “改進的出貨流程”每年為Yellow Freight 公司節(jié)約一千七百多萬美元.單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級5單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級5 單擊此

5、處編輯母版副標題樣式5單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/20225數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 52002.5.編輯ppt成功的優(yōu)化例子成功的優(yōu)化例子 “改進的卡車分派”為 Reynolds 公司每年節(jié)約七百萬美元 .單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級6單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級6 單擊此處編輯母版副標題樣式6單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第

6、三級 第四級 第五級2/14/20226數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 62002.5.編輯ppt成功的優(yōu)化例子成功的優(yōu)化例子 “最優(yōu)全局供應鏈”為數字設備行業(yè)節(jié)約超過三億美元.單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級7單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級7 單擊此處編輯母版副標題樣式7單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/20227數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解

7、范 例 布置實驗 結 束課堂延伸 72002.5.編輯ppt成功的優(yōu)化例子成功的優(yōu)化例子 寶潔公司重建北美業(yè)務, 減少 20%的工廠, 每年節(jié)約兩億美元.單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級8單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級8 單擊此處編輯母版副標題樣式8單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/20228數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 82002.5.編輯ppt成功的優(yōu)化例子成功的優(yōu)化例

8、子 大阪Hanshin高速的 “最優(yōu)交通控制”每年節(jié)約一千七百萬人小時 ,為他們帶來三億二千萬美圓的收益.單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級9單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級9 單擊此處編輯母版副標題樣式9單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/20229數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 92002.5.編輯ppt單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級

9、 第五級10單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級10 單擊此處編輯母版副標題樣式10單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202210數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 102002.5.編輯ppt引例單耗 甲 乙 丙限額材料工時工人 2 3 1 3 2 1.5 3 2 5343640利潤(元/件) 4 3 2在一定的條件下，問生產數量為多少時, 利潤達到最大？數據表生產計劃問題生產計劃問題引例運輸問題運輸問題A1325801010312

10、012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道鐵路公路S1S7 鋼管廠火車站450里程(km)目標：運費達到最小單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級12單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級12 單

11、擊此處編輯母版副標題樣式12單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202212數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 122002.5.編輯ppt特點：從若干可能的計劃（方案）中尋求某種意義下的最優(yōu)方案，數學上將這種問題稱為最優(yōu)化問題（optimization).1、生產計劃問題；2、運輸問題；最優(yōu)化問題簡介最優(yōu)化問題簡介單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級13單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級

12、13 單擊此處編輯母版副標題樣式13單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202213數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 132002.5.編輯ppt優(yōu)化問題的表述優(yōu)化問題的表述 最優(yōu)化是企業(yè)運作、科技研發(fā)和工程設計中常見的問題。要表述一個最優(yōu)化問題（即建立數學模型），應明明確三樣東西：決策變量、約束條件 和目標函數決策變量：它們是決策者（你）所控制的那些數量，它們取什么數值需要決策者來決策，最優(yōu)化問題的求解就是找出決策變量的最優(yōu)取值。約束條件：它們是決策變量在現實世界中所受到的限制

13、，或者說決策變量在這些限制范圍之內取值才有實際意義。 目標函數：它代表決策者希望對其進行優(yōu)化的那個指標。目標函數是決策變量的函數。單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級14單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級14 單擊此處編輯母版副標題樣式14單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202214數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 142002.5.編輯ppt1232334xxx規(guī)劃模型利潤材料工時

14、人力單耗 甲 乙 丙 x1 x2 x3限額材料工時工人 2 3 1 3 2 1.5 3 2 5343640利潤(元/件) 4 3 2生產計劃問題生產計劃問題123432Zxxxmax目標函數123,0 x x x 123321.536xxx12332540 xxx約束條件決策變量x1, x2, x3單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級15單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級15 單擊此處編輯母版副標題樣式15單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/20

15、2215數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 152002.5.編輯ppt單耗 甲 乙 丙 x1 x2 x3限額材料工時工人 2 3 1 3 2 1.5 3 2 5343640利潤(元/件) 4 3 2生產計劃問題生產計劃問題123123123123123max4322334321.536. .32540,0Zxxxxxxxxxstxxxx x x規(guī)劃模型利潤材料工時人力最優(yōu)化問題運輸問題運輸問題A13258010103120124270108810706270302020304501043017506061942052016804803

16、00220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道鐵路公路S1S7 鋼管廠火車站450里程(km)目標：運費達到最小單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級17單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級17 單擊此處編輯母版副標題樣式17單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/1

17、4/202217數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 172002.5.編輯pptcij 單位運費；ai 在第i 廠提供的量； bj 第j 地需要量；求從si運多少鋼管到Aj, 可使總運費最少.決策變量: xij 從si運到Aj的鋼管數量s1s2sis7 A1A2AjA15 C11C12C1jC1,15Ci,jaia1a2a7b15b1b2bj單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級18單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級18 單擊此處編輯母版副標題樣

18、式18單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202218數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 182002.5.編輯ppts1s2sis7 A1A2AjA15 C11C12C1jC1,15Ci,jaia1a2a7b15b1b2bj151. .,1,2,.,7ijijstxai71511minijijijc x 711,2,.,15ijjixbj0,1,7,1,15ijxij單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級19單擊此處編輯母版標題樣式 單

19、擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級19 單擊此處編輯母版副標題樣式19單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202219數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 192002.5.編輯ppt三個基本要素1、決策變量（decision variables);2、約束條件（constraints);3、目標函數（objective function)最優(yōu)化問題分類線性、非線性靜態(tài)、動態(tài)整數、非整數隨機、非隨機等 最優(yōu)化問題單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式

20、第二級 第三級 第四級 第五級20單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級20 單擊此處編輯母版副標題樣式20單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202220數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 202002.5.編輯ppt最優(yōu)化數學模型的分類 線性規(guī)劃(LP) 非線性規(guī)劃(NLP) 二次規(guī)劃(QP) 整數規(guī)劃(IP)多目標規(guī)劃 動態(tài)規(guī)劃 最優(yōu)化問題單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級21單擊此處

21、編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級21 單擊此處編輯母版副標題樣式21單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202221數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 212002.5.編輯ppt生產計劃問題生產計劃問題該模型的目標函數和約束條件均為線性函數, 滿足線性規(guī)劃的要求,故該問題為一線性規(guī)劃問題,其模型為線性規(guī)劃模型.123123123123123max4322334321.536. .32540,0Zxxxxxxxxxstxxxx x x利潤材

22、料工時人力線性規(guī)劃單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級22單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級22 單擊此處編輯母版副標題樣式22單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202222數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 222002.5.編輯ppt生產計劃問題生產計劃問題max cTxs.t. Axb x0矩陣形式：TT123c4, 3, 2, ,2 3134A3 2 1.5 ,b363 2540

23、 x x xx123123123123123max4322334321.536. .32540,0Zxxxxxxxxxstxxxx x x利潤材料工時人力線性規(guī)劃模型單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級23單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級23 單擊此處編輯母版副標題樣式23單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202223數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 232002.5.編輯pptmi

24、n (max) cTxs.t. Axb, (或Ax = b) x0 (或a x b)標準形式其中：xRn，A Rmn， bRm， cRn線性規(guī)劃單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級24單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級24 單擊此處編輯母版副標題樣式24單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202224數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 242002.5.編輯ppt2 X1 + X2 = 4

25、0X1 + 2 X2 = 50 X1 X2abcd可行點可行域凸多面體v內點邊界點頂點vB線性規(guī)劃解的若干概念線性規(guī)劃模型max z = 5x1+3x2s.t. 2x1+x240 x1+2x250 x1，x20單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級25單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級25 單擊此處編輯母版副標題樣式25單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202225數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結

26、束課堂延伸 252002.5.編輯ppt線性規(guī)劃解的圖示線性規(guī)劃模型max z = 5x1+3x2s.t. 2x1+x240 x1+2x250 x1，x202 X1 + X2 = 40X1 + 2 X2 = 50 X1 X2a20 x1=10,x2=2025問問: :什么樣的問題可以使用圖解法什么樣的問題可以使用圖解法? ?你從圖中得到什么啟示你從圖中得到什么啟示? ?P=0P=50P=110Max z = 3x1+x2s.t. -x1+x22 -L1 x1-2x22 -L2 3x1+2x214 -L3 x1，x20 x1x2L2L1L30 x1x2L2L1L30 x1x2L2L10 x1x2

27、L2L1L30z=c 無最優(yōu)解 無可行解 最優(yōu)解不唯一線性規(guī)劃的基本性質線性規(guī)劃的基本性質可行域 線段組成的凸多邊形目標函數 等值線為直線最優(yōu)解 凸多邊形的某個頂點LP的基本性質： 可行域存在時，必是凸多面體； 可行解對應于可行域中的點； 最優(yōu)解存在時，必在可行域的頂點取得。LP的通常解法是單純形法。超平面組成的凸多面體等值線是超平面凸多面體的某個頂點2 維n 維單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級28單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級28 單擊此處編輯母版副標題樣式28單擊此處編輯母版標題樣式 單擊

28、此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202228數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 282002.5.編輯ppt Matlab中求解線性規(guī)劃的命令為: linprog, 解決的線性規(guī)劃的標準格式為： min c cTx x x xR Rn n s.t. Ax x 0：收斂=0: 到最大迭代次數時都還未收斂0：infeasible或方法失敗迭代次數和算法類型MATLABMATLAB軟件求解軟件求解單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級31單擊此處編輯母版標題樣式 單擊此

29、處編輯母版文本樣式 第二級 第三級 第四級 第五級31 單擊此處編輯母版副標題樣式31單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202231數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 312002.5.編輯ppt看一個小例子 程序: c=-5,3; A=2,1;1,2; b=40,50; L=0, 0; x,fmin=linprog(c,A,b,L); Pmax=-fmin x1=x(1), x2=x(2) 輸出結果: Pmax=110, x1=10, x2=20.模型: max P=5 X1

30、+ 3 X2 s.t. 2 X1 + X2 40 X1 + 2 X2 50 X10, X20 MATLABMATLAB軟件求解軟件求解單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級32單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級32 單擊此處編輯母版副標題樣式32單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202232數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 322002.5.編輯ppt加工奶制品的生產計劃加工奶制品的生產

31、計劃1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶 時間480小時 至多加工100公斤A1 制訂生產計劃，使每天獲利最大 每天：范范 例例x1桶牛奶生產A1 x2桶牛奶生產A2 獲利 243x1 獲利 164 x2 原料供應 5021 xx勞動時間 48081221 xx加工能力 10031x決策變量 目標函數 216472xxzMax每天獲利約束條件非負約束 0,21xx1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 加工奶制品的生產計劃加工奶制品的生產計劃單擊此處編輯母版標題樣式 單擊此處編輯母

32、版文本樣式 第二級 第三級 第四級 第五級34單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級34 單擊此處編輯母版副標題樣式34單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202234數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 342002.5.編輯ppt max 72x1+64x2max 72x1+64x2st st2 2）x1+x250 x1+x2503 3）12x1+8x248012x1+8x24804 4）3x11003x1100endendDO RAN

33、GE (SENSITIVITY) ANALYSIS? NoNo加工奶制品的生產計劃加工奶制品的生產計劃范范 例例單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級35單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級35 單擊此處編輯母版副標題樣式35單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202235數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 352002.5.編輯ppt OBJECTIVE FUNCTION VALUE VAR

34、IABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES NO. ITERATIONS= 220桶牛奶生產A1, 30桶生產A2，利潤3360元。 范范 例例單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級36單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級36 單擊此處編輯母版副標題樣式36單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202236數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗

35、 結 束課堂延伸 362002.5.編輯ppt OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES NO. ITERATIONS= 2原料無剩余時間無剩余加工能力剩余40三種資源“資源” 剩余為零的約束為緊約束（有效約束） 單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級37單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級37 單擊此處編輯母版副標題樣式37單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式

36、第二級 第三級 第四級 第五級2/14/202237數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 372002.5.編輯ppt OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3) 0.000000 4) 40.000000 NO. ITERATIONS= 2最優(yōu)解下“資源”增加1單位時“效益”的增量 原料增加1單位, 利潤增長48 時間增加1單位, 利潤增長2 加工能力增長不影響利潤影子價格影子價格

37、 結果解釋 單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級38單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級38 單擊此處編輯母版副標題樣式38單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202238數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 382002.5.編輯ppt 35元可買到1桶牛奶，要買嗎？35 48, 應該買！ 聘用臨時工人付出的工資最多每小時幾元？ 2元！加工奶制品的生產計劃加工奶制品的生產計劃范范 例例單擊此

38、處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級39單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級39 單擊此處編輯母版副標題樣式39單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202239數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 392002.5.編輯pptRANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABL

39、E ALLOWABLE COEF INCREASE DECREASE RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASEDO RANGE(SENSITIVITY) ANALYSIS? Yes最優(yōu)解不變時目標函數系數允許變化范圍 (約束條件不變)x1系數范圍(64,96) x2系數范圍(48,72) x1系數由24 3=72增加為303=90，在允許范圍內 A1獲利增加到 30元/千克，應否改變生產計劃 不變！單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級40單

40、擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級40 單擊此處編輯母版副標題樣式40單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202240數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 402002.5.編輯pptRANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE RIGHTH

41、AND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE影子價格有意義時約束右端的允許變化范圍 (目標函數不變)原料最多增加10 時間最多增加53 35元可買到1桶牛奶，每天最多買多少？最多買10桶!范范 例例單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級41單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級41 單擊此處編輯母版副標題樣式41單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202241

42、數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 412002.5.編輯ppt課堂延伸課堂延伸 重要事件重要事件 重要人物重要人物 優(yōu)化技術成功應用的故事優(yōu)化技術成功應用的故事單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級42單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級42 單擊此處編輯母版副標題樣式42單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202242數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置

43、實驗 結 束課堂延伸 422002.5.編輯ppt課堂延伸課堂延伸重要事件重要事件 在1762年, Lagrange 解僅含等式約束的最優(yōu)化問題 在1820年, Gauss利用消去法解線性方程組. 在1945年, 計算機出現. 在1947年, Dantzig 發(fā)明單純形法. 在1968年, Fiacco and McCormick 引進內點法. 在1984年, Karmarkar 提出了解線性規(guī)劃的有效算法.單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級43單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級43 單擊此處編輯母

44、版副標題樣式43單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202243數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 432002.5.編輯ppt課堂延伸課堂延伸重要人物重要人物 John Von Neumann George B. Dantzig Leonid Vitalyevich Kantorovich Narendra Karmarkar Harry Max Markowitz單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級44單擊此處編輯母版標題樣式 單擊

45、此處編輯母版文本樣式 第二級 第三級 第四級 第五級44 單擊此處編輯母版副標題樣式44單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202244數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 442002.5.編輯ppt重要人物重要人物 John Von Neumann 約翰馮諾依曼(19031957),美藉匈牙利人.20世紀最杰出的數學家之一,被譽為”計算機之父”,”博弈論之父”.被認為是數學規(guī)劃的三大創(chuàng)始人之一.課堂延伸課堂延伸單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第

46、四級 第五級45單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級45 單擊此處編輯母版副標題樣式45單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202245數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 452002.5.編輯pptGeorge B. Dantzig George B. Dantzig(1914-2005),美國人,線性規(guī)劃單純形法的創(chuàng)始人,被譽為”線性規(guī)劃之父”.美國科學院三院院士,美國軍方數學顧問,教授.并以其名字設立Dantzig獎.數學規(guī)劃的三

47、大創(chuàng)始人之一. 發(fā)現算法時非常年輕,以至到日本時,人們以為”線性規(guī)劃之父”是個老人,而對他無人問津.課堂延伸課堂延伸單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級46單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級46 單擊此處編輯母版副標題樣式46單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202246數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 462002.5.編輯pptLeonid Vitalyevich Kantorov

48、ich Kantorovich(1912-1986)蘇聯人,著名數學家和經濟學家,教授,年僅18歲獲博士學位.因在經濟學上提出稀缺資源的最優(yōu)配置獲諾貝爾獎.線性規(guī)劃對偶理論的提出者,數學規(guī)劃的三大創(chuàng)始人之一.課堂延伸課堂延伸單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級47單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級47 單擊此處編輯母版副標題樣式47單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202247數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例

49、布置實驗 結 束課堂延伸 472002.5.編輯ppt課堂延伸課堂延伸單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級48單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級48 單擊此處編輯母版副標題樣式48單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202248數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 482002.5.編輯ppt 在1990年,Markowitz因為金融經濟學方面的貢獻和另外兩位學者分獲諾貝爾經濟學獎.左邊的文

50、字說明了他獲獎的原因以及關于他的理論的簡介.課堂延伸課堂延伸單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級49單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級49 單擊此處編輯母版副標題樣式49單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202249數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 492002.5.編輯ppt課堂延伸課堂延伸優(yōu)化技術成功應用的故事優(yōu)化技術成功應用的故事在現實世界中，都有一些什么成功應用優(yōu)化技術的故事呢

51、 大陸航空公司乘務組快速補救計劃大陸航空公司乘務組快速補救計劃 AT&TAT&T網絡的快速恢復及優(yōu)化網絡的快速恢復及優(yōu)化 香港國際貨柜碼頭裝卸的優(yōu)化決策香港國際貨柜碼頭裝卸的優(yōu)化決策 聯合包裹服務公司優(yōu)化空中與地面運輸計劃聯合包裹服務公司優(yōu)化空中與地面運輸計劃 得克薩斯兒童醫(yī)院最小化金融風險得克薩斯兒童醫(yī)院最小化金融風險單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級50單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級50 單擊此處編輯母版副標題樣式50單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級

52、 第三級 第四級 第五級2/14/202250數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 502002.5.編輯ppt問題：甚至在九一一恐怖襲擊事件之前, 美國大陸航空公司總裁就考慮到對大型航空公司,應該制定一個危機計劃,以應對緊急情況。 突發(fā)事件,包括惡劣的天氣,飛機機械故障在現實世界中，都有一些什么成功應用優(yōu)化技術的故事呢 大陸航空公司乘務組快速補救計劃大陸航空公司乘務組快速補救計劃 乘務組缺班，航空公司會面臨航班中斷,航班延誤,取消等情況。 由于乘務組未必能夠保證剩余的定期航班的正常飛行. 航空公司必須盡快讓乘務組完成補償飛行計劃，并返回

53、自己的原時刻表。這個決策要滿足成本最小、政府規(guī)定、合同約定以及對生活品質的要求。 解決這些問題需要專門的能進行復雜建模并平衡多種因素的運籌研究技術。 課堂延伸課堂延伸單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級51單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級51 單擊此處編輯母版副標題樣式51單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202251數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 512002.5.編輯ppt 運

54、籌學解決方案： 大陸航空公司采用Caleb技術,研發(fā)了CrewSolver決策支持系統(tǒng)，生成全局最優(yōu)或接近最優(yōu)的乘務組補救方案. 大陸航空公司乘務組快速補救計劃大陸航空公司乘務組快速補救計劃 效果：大陸航空公司自實施此計劃以來，在每一次嚴重的突發(fā)事件中,都能實現乘務組快速補救,取得價值數百萬美元的效益。 公司估計,在2001年CrewSolver系統(tǒng)幫助它節(jié)省約了4000萬美元。由于該系統(tǒng),使美國航空業(yè)自2001年9月11日后開始復蘇,從那時起,五家航空公司已采用了類似的基于運籌學的軟件用于突發(fā)事件后航班時刻表、飛行員安排等的補救計劃。課堂延伸課堂延伸單擊此處編輯母版標題樣式 單擊此處編輯母版

55、文本樣式 第二級 第三級 第四級 第五級52單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級52 單擊此處編輯母版副標題樣式52單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202252數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 522002.5.編輯ppt背后的故事： 1995年，美國大陸航空公司邀請于剛教授為他們編寫決策支持系統(tǒng)。于剛領導他的研究人員克服了重重困難，取得了一個又一個的突破性成果，為大陸航空公司編寫了三個決策支持系 統(tǒng)，解決了當航空系統(tǒng)遭遇惡劣天氣

56、、飛機故障等干擾后，飛機航班的最優(yōu)恢復問題、機組人員的調度問題和機組人員的計劃、培訓、休假等總體決策的最優(yōu)方案。2001年9月11日，震驚世界的“9.11”恐怖事件不幸發(fā)生了。這次事件給美國航空業(yè)帶來了災難性的打擊。但是，就是通過這次突發(fā)的災難性事件，于剛的實時決策系統(tǒng)的優(yōu)越性得到了充分體現。大陸航空公司由于采用了他的優(yōu)化實時決策系統(tǒng)，比其他航空公司提前兩天開始正常運營，為公司挽回3000多萬美元的損失。由于有了于剛的完備的決策支持系統(tǒng)，大陸航空公司在整個“9.11”事件中避免了上億美元的損失。 課堂延伸課堂延伸單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級

57、53單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級53 單擊此處編輯母版副標題樣式53單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202253數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 532002.5.編輯ppt 大陸航空公司乘務組快速補救計劃大陸航空公司乘務組快速補救計劃 該案例使旅美華裔著名運籌學家于剛教授榮獲2002年度運籌與管理科學應用Franz Edelman 獎，Franz Edelman獎是由世界著名的運籌和管理科學家Franz Edelman于

58、1971年創(chuàng)立的。它作為運籌和管理科學在國際上的一項最高榮譽，一年一度地頒發(fā)給在這一領域取得了最突出成就的科學家和企業(yè)家。課堂延伸課堂延伸單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級54單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級54 單擊此處編輯母版副標題樣式54單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202254數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 542002.5.編輯ppt問題：AT&T是一個全球

59、性電信公司，提供多種服務,如遠程語音數據、視頻、無線通訊、衛(wèi)星及互聯網服務。 AT&T面對的問題是防止網絡出錯,并提供應對失誤發(fā)生時的快速反應。AT&T在發(fā)生網絡 故障時，要快速改換通訊通道,這要求網絡有足夠的恢復能力來傳送相應需求。 這個問題很重要,因為服務的失敗,直接影響到公司的核心服務和客戶忠誠度。解決它需要運籌學研究專門技術,因為這個問題涉及到全系統(tǒng)而運籌學有強大的能力來處理眾多的參數。 AT&TAT&T網絡的快速恢復及優(yōu)化網絡的快速恢復及優(yōu)化課堂延伸課堂延伸單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級55單擊此處編

60、輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級55 單擊此處編輯母版副標題樣式55單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式 第二級 第三級 第四級 第五級2/14/202255數學實驗之線性規(guī)劃實驗目的 引 例優(yōu)化問題線性規(guī)劃軟件求解 范 例 布置實驗 結 束課堂延伸 552002.5.編輯ppt運籌學解決方案： 一個由運籌學專家、網絡設計師、 管理者組成的AT&T團隊提出了一種方法，在任何單一鏈接出現故障時，通過確定修復能力要求的適當的數量和位置,來恢復需求。該辦法使網絡恢復成本最小化,并產生新的恢復路徑。價值： 在約10個月內，AT&T團隊以此方法為工具,優(yōu)化恢復能力的配置. 這一工具被擴展到交換中心出現故障時的恢復，并用于