1、武漢學(xué)院數(shù)學(xué)建模培訓(xùn) 優(yōu)化模型（一）,1. 什么是數(shù)學(xué)模型？,數(shù)學(xué)模型是對于現(xiàn)實世界的一個特定對象，一個特定目的，根據(jù)特有的內(nèi)在規(guī)律，做出一些必要的假設(shè)，運用適當(dāng)?shù)臄?shù)學(xué)工具，得到一個數(shù)學(xué)結(jié)構(gòu) 簡單地說：就是系統(tǒng)的某種特征的本質(zhì)的數(shù)學(xué)表達(dá)式（或是用數(shù)學(xué)術(shù)語對部分現(xiàn)實世界的描述），即用數(shù)學(xué)式子（如函數(shù)、圖形、代數(shù)方程、微分方程、積分方程、差分方程等）來描述（表述、模擬）所研究的客觀對象或系統(tǒng)在某一方面的存在規(guī)律,一、數(shù)學(xué)建模與優(yōu)化,在實際過程中用那一種方法建模主要是根據(jù)我們對研究對象的了解程度和建模目的來決定機理分析法建模的具體步驟大致可見右圖,建模過程示意圖,模型 數(shù)學(xué)模型的分類： 按研究方法和

2、對象的數(shù)學(xué)特征分：初等模型、幾何模型、優(yōu)化模型、微分方程模型、圖論模型、邏輯模型、穩(wěn)定性模型、擴散模型等 按研究對象的實際領(lǐng)域（或所屬學(xué)科）分：人口模型、交通模型、環(huán)境模型、生態(tài)模型、生理模型、城鎮(zhèn)規(guī)劃模型、水資源模型、污染模型、經(jīng)濟模型、社會模型等,2、數(shù)學(xué)模型的分類,優(yōu)化模型是中國大學(xué)生建模競賽常見的類型，占很大的比重。 92 年以來，優(yōu)化模型有： 94年A題：“逢山開路”設(shè)計最短路徑。 95年A題：“一個飛行管理問題”，線性規(guī)劃 和非線性規(guī)劃模型。 96年A題：“最優(yōu)捕魚策略”，以微分方程為 基礎(chǔ)的優(yōu)化模型。,96年B題：“洗衣節(jié)水問題”，以用水量為目 標(biāo)函數(shù)的優(yōu)化模型。 97年A題：“

3、零件的參數(shù)設(shè)計”，隨機優(yōu)化模型。 97年B題：“截斷切割”，動態(tài)優(yōu)化模型。 98年A題：“投資的收益和風(fēng)險”，雙目標(biāo)優(yōu) 化模型。 98年B題：“災(zāi)情巡視的最佳路線”，0-1線性 規(guī)劃模型。,99年A題：“自動化車床管理”，雙參數(shù)規(guī)劃模型。 99年B題：“鉆井布局”，非線性混合整數(shù)規(guī)劃模型。 00年B題：“鋼管訂購和運輸”，二次規(guī)劃模型。 01年B題：“公交車調(diào)度”，雙目標(biāo)規(guī)劃模型。 02年A題：“車燈線光源的優(yōu)化設(shè)計”，規(guī)劃模型。,03年B題：“露天礦生產(chǎn)的車輛安排”，非線性規(guī)劃模型。 04年B題：“電力市場的輸電阻塞管理”，雙目 標(biāo)線性規(guī)劃模型。 05年B題：“DVD在現(xiàn)租賃”，0-1規(guī)劃模

4、型。 06年A題：“出版社的資源優(yōu)化配置”，線性規(guī)劃模型。 07年B題：乘公交，看奧運,08 B題：高等教育學(xué)費標(biāo)準(zhǔn)探討 線性規(guī)劃 09 B題：眼科病床的合理安排問題 排隊輪 10 B題： 2010年上海世博會影響力的定量評估,實際問題中 的優(yōu)化模型,x是決策變量,f(x)是目標(biāo)函數(shù),gi(x)0是約束條件,數(shù)學(xué)規(guī)劃,線性規(guī)劃(LP) 二次規(guī)劃(QP) 非線性規(guī)劃(NLP),純整數(shù)規(guī)劃(PIP) 混合整數(shù)規(guī)劃(MIP),整數(shù)規(guī)劃(IP),0-1整數(shù)規(guī)劃 一般整數(shù)規(guī)劃,連續(xù)規(guī)劃,3、優(yōu)化模型的分類,運籌學(xué)所使用的數(shù)學(xué)模型的特點： 一般由決策變量、約束或限制條件及目標(biāo)函數(shù)所構(gòu) 成，其實質(zhì)表現(xiàn)為在約

5、束條件允許的范圍內(nèi)，尋求 目標(biāo)函數(shù)的最優(yōu)解!,4、運籌與優(yōu)化,“五劃五論”,運籌學(xué)的基本理論：,規(guī)劃論：線性規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃、 整數(shù)規(guī)劃、目標(biāo)規(guī)劃,排隊論、存貯論、圖與網(wǎng)絡(luò)、決策論、對策論,1、線性規(guī)劃、 2、整數(shù)規(guī)劃、 3、01規(guī)劃、 4、圖論、 5、排隊論,二、優(yōu)化建模主要學(xué)習(xí)內(nèi)容,lingo優(yōu)化軟件建模,線性規(guī)劃（Linear Programming ),運籌學(xué)的一個重要分枝 研究較早 發(fā)展較快 理論較成熟 應(yīng)用極為廣泛,簡記為LP,線性規(guī)劃研究的問題： 1、在現(xiàn)有的人、財、物等資源的條件下， 研究如何合理地計劃、安排，可使得 某一目標(biāo)達(dá)到最大，,尋求在一定約束條件下使某個指標(biāo)

6、達(dá)到最優(yōu),如產(chǎn)量、利潤等。,2、在任務(wù)確定后，如何計劃、安排，使 用最少的人、財、物等資源，去實現(xiàn) 該任務(wù)，,如使生產(chǎn)成本、費用最少等。,典型的線性規(guī)劃在經(jīng)濟管理上的應(yīng)用舉例:,1、合理利用線材問題:,現(xiàn)有一批長度一定的鋼管,由于生產(chǎn)的需要, 要求截出不同規(guī)格的鋼管若干。試問應(yīng)如何 下料，既滿足了生產(chǎn)的需要，又使得使用的 原材料鋼管的數(shù)量最少。,2、配料問題：,用若干種不同價格不同成分含量的原料， 用不同的配比混合調(diào)配出一些不同價格不同 規(guī)格的產(chǎn)品。在原料供應(yīng)量的限制和保證產(chǎn) 品成分的含量的前提下，如何獲取最大的利潤。,3、投資問題：,從不同的投資項目中選出一個投資方案，使投 資的回報最大。,

7、4、產(chǎn)品生產(chǎn)計劃：,合理充分利用廠里現(xiàn)有的人力、物力、才力， 作出最優(yōu)的產(chǎn)品生產(chǎn)計劃，使得工廠獲利最大。,5、勞動力安排：,某單位由于工作需要，在不同時間段需要不同 數(shù)量的勞動力，在每個勞動力工作日連續(xù)工作 8小時的規(guī)定下，如何安排勞動力，才能用最少 的勞動力來滿足工作的需要。,6、運輸問題：,一個公司有若干個 生產(chǎn)單位與銷售單位，根據(jù) 各生產(chǎn)單位的產(chǎn)量及銷售單位的情況，如何制定 調(diào)運方案，將產(chǎn)品運到各銷售單位而總的運費最少。,1、生產(chǎn)計劃問題 2、產(chǎn)銷平衡的運輸問題 3、營養(yǎng)配方問題 4、鋼材下料問題 5、人員安排問題 6、投資問題,LP的數(shù)學(xué)模型舉例與練習(xí),例題1生產(chǎn)計劃問題,某廠生產(chǎn)甲、

8、乙兩種產(chǎn)品，已知各產(chǎn)品的利潤、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表：,問題：如何安排生產(chǎn)，使得獲利最大？,例題1建模,步驟： 1、確定決策變量：設(shè)生產(chǎn)甲產(chǎn)品 噸,乙產(chǎn)品 噸 2、確定目標(biāo)函數(shù)： 3、確定約束條件： 工作日約束 原材料約束 非負(fù)性約束,上述生產(chǎn)計劃問題就是一個典型的線性規(guī)劃問題，,尋求以線性函數(shù)的最大（?。┲禐槟繕?biāo)的數(shù)學(xué)模,型.,它是指在一組線性的等式或不等式的約束條件下，,一、線性規(guī)劃模型的建立及各種形式 、建模的一般步驟： 步驟一：確定決策變量 即用變量取不同的值來表示可供選擇的各種不同方案,步驟二：建立目標(biāo)函數(shù),即找到目標(biāo)值與決策變量的數(shù)量關(guān)系,步驟三：確定約束條件,即

9、決策變量所受到的外界條件的制約。,約束條件一般為決策變量的等式或不等式,要求：目標(biāo)函數(shù)與約束條件均是線性的， 且目標(biāo)函數(shù)只能是一個。,、線性規(guī)劃模型的一般形式：,決策變量,約束方程,非負(fù)約束,目標(biāo)函數(shù),maximum,minimum,subject to,價值向量 價值系數(shù),、線性規(guī)劃的標(biāo)準(zhǔn)形式,、非標(biāo)準(zhǔn)型式線性規(guī)劃問題的標(biāo)準(zhǔn)化,（1）對求目標(biāo)函數(shù)最大值:,=,（2）約束條件為“”型,松弛變量,（3）約束條件為“”型,剩余變量,(4) 約束條件右邊為負(fù),（6）決策變量無符號限制,（5）決策變量0,例如,帶入約束方程及目標(biāo)函數(shù),則原線性規(guī)劃問題的標(biāo)準(zhǔn)型為:,、線性規(guī)劃問題的矩陣表達(dá)式：,二、線性

10、規(guī)劃的解 1、可行解：,2、可行域：,（LP）的全體可行解構(gòu)成的集合稱為可行域,3、最優(yōu)解及最優(yōu)值：,設(shè)S是（LP）的可行域,不唯一,唯一,4、若對任意大的M0,都存在可行解使得該線性規(guī)劃的目標(biāo) 函數(shù)值,，則稱該線性規(guī)劃問題無界,三、兩個變量的線性規(guī)劃的圖解法,解： （1）在直角坐標(biāo)系上畫出可行域,（2）做目標(biāo)函數(shù)的等值線,0,可行域,凸多邊形,頂點,.,圖解法的基本步驟：,（一般是一個凸多邊形）,注意：若是求目標(biāo)函數(shù)的最小值，,目標(biāo)函數(shù)直線向下移動,關(guān)于線性規(guī)劃解的結(jié)論：,1、若（LP）問題有可行解，則可行域是一個凸多邊形 （或凸多面體）。它可能是有界的；也可能是無界的。,2、若（LP）問題

11、有最優(yōu)解，則最優(yōu)解可能是唯一的；也可能 是無窮多個。如果是唯一的，這個解一定在該凸多邊形的某 個頂點上；如果是無窮多個，則這些最優(yōu)解一定充滿凸多邊 形的一條邊界（包括此邊界的兩個頂點）,總之，若（LP）問題有最優(yōu)解，則最優(yōu)解一定可以在凸多邊 形的某個頂點達(dá)到,3、若（LP）問題有可行解，但沒有有限最優(yōu)解，此時凸多邊形 是無界的,（反之不成立）,4、若（LP）問題沒有可行解，則該問題沒有最優(yōu)解,針對標(biāo)準(zhǔn)形式的線性規(guī)劃問題，其解的理論,分析已經(jīng)很完備，在此基礎(chǔ)上也提出了很好的算,單純形方法是線性規(guī)劃問題的最為基礎(chǔ)、也,法單純形方法及其相應(yīng)的變化形式（兩階段,關(guān)于線性規(guī)劃模型的求解,法，對偶單純形法

12、等）.,是最核心的算法。它是一個迭代算法，先從一個,特殊的可行解（極點）出發(fā)，通過判別條件去判,斷該可行解是否為最優(yōu)解（或問題無界），若不,是最優(yōu)解，則根據(jù)相應(yīng)規(guī)則，迭代到下一個更好的可行解（極點），直到最優(yōu)解（或問題無界）.關(guān)于線性規(guī)劃問題解的理論和單純形法具體的求解過程可參見文獻1.,然后在實際應(yīng)用中，特別是數(shù)學(xué)建模過程中，遇到線性規(guī)劃問題的求解，我們一般都是利用現(xiàn)有的軟件進行求解，此時通常并不要求線性規(guī)劃問題是標(biāo)準(zhǔn)形式. 比較常用的求解線性規(guī)劃模型的軟件包有LINGO和LINDO.,例2、設(shè)有三個倉庫A、B、C分別貯存某種商品700噸、400噸、900噸，現(xiàn)有四個商店甲、乙、丙、丁需要該

13、種商品分別為300噸、600噸、500噸、600噸，已知各倉庫到各商店每噸的運價如下表所示，問如何調(diào)運，才能使總運費最省？,例題2 產(chǎn)銷平衡的運輸問題,運價,商店,倉庫,設(shè)由A調(diào)到甲乙丙丁 運量分別為 由B調(diào)到甲乙丙丁運量 分別為 由C調(diào)到甲乙丙丁運量 分別為 總運費為f,則,例2 建模,解：,解答,一般的運輸問題可以表述如下：,數(shù)學(xué)模型：,若其中各產(chǎn)地的總產(chǎn)量等于各銷地的總銷量，即,類似與將一般的線性規(guī)劃問題轉(zhuǎn)化為其標(biāo)準(zhǔn),否則，稱為不平衡的運輸問題，包括：,，則稱該問題為平衡的運輸問題.,總產(chǎn)量總銷量和總產(chǎn)量總銷量.,形式，我們總可以通過引入假想的銷地或產(chǎn)地，,將不平衡的運輸問題轉(zhuǎn)化為平衡的

14、運輸問題. 從,而，我們的重點就是解決平衡運輸問題的求解.,顯然，運輸問題是一個標(biāo)準(zhǔn)的線性規(guī)劃問題，因而當(dāng)然可以運用單純形方法求解. 但由于平衡的運輸問題的特殊性質(zhì)，它還可以用其它的一些特殊方法求解，其中最常用的就是表上作業(yè)法，該方法將單純形法與平衡的運輸問題的特殊性質(zhì)結(jié)合起來，很方便地實行了運輸問題的求解. 關(guān)于運輸問題及其解法的進一步介紹可參考相關(guān)運籌學(xué)書籍.,例題3營養(yǎng)搭配問題,用3種原料配制某種食品，要求該食品中蛋白質(zhì)、脂肪、糖、維生素的含量不低于15、20、25、30單位以上3種原料的單價及每單位原料所含各種成分的數(shù)量，如下表2-2所示問應(yīng)如何配制該食品，使所需成本最低？,例題3建模

15、,解答,解: 設(shè) 分別表示 原料的用量 （千克），f表示食品的成本（元），則這一食 品配制問題變?yōu)椋?對于線性規(guī)劃問題，如果要求其決策變量取,整數(shù)值，則稱該問題為整數(shù)線性規(guī)劃問題.,平面法和分支定界法是兩種常用的求解整數(shù)線性,對于整數(shù)線性規(guī)劃問題的求解，其難度和運,整數(shù)線性規(guī)劃模型,算量遠(yuǎn)大于同規(guī)模的線性規(guī)劃問題. Gomory割,規(guī)劃問題的方法. 此外，同線性規(guī)劃模型一樣，,們也可以運用LINGO和LINDO軟件包來求解整數(shù),線性規(guī)劃模型.,2020/7/28,48,整數(shù)規(guī)劃問題一般形式,整數(shù)線性規(guī)劃(ILP) 目標(biāo)和約束均為線性函數(shù) 整數(shù)非線性規(guī)劃(NLP) 目標(biāo)或約束中存在非線性函數(shù),整

16、數(shù)規(guī)劃問題的分類,純(全)整數(shù)規(guī)劃(PIP) 決策變量均為整數(shù) 混合整數(shù)規(guī)劃(MIP) 決策變量有整數(shù)，也有實數(shù),0-1規(guī)劃 決策變量只取0或1,取消整數(shù)規(guī)劃中決策變量為整數(shù)的限制（松弛），對應(yīng)的連續(xù)優(yōu)化問題稱為原問題的松弛問題,整數(shù)規(guī)劃問題對應(yīng)的松弛問題,下界（對Min問題） 上界（對Max問題）,用連續(xù)優(yōu)化方法求解松弛問題，如果松弛問題 最優(yōu)解（分量）全為整數(shù)，則也是原整數(shù)規(guī)劃 問題的最優(yōu)解,對松弛問題的最優(yōu)解（分量）舍入為整數(shù)，得 到的往往不是原整數(shù)規(guī)劃問題的最優(yōu)解（甚至 不是可行解）,基本思想：隱式地枚舉一切可行解（“分而治之”）,所謂分枝，就是逐次對解空間（可行域）進行劃分；而所謂定

17、界，是指對于每個分枝（或稱子域），要計算原問題的最優(yōu)解的下界（對極小化問題）. 這些下界用來在求解過程中判定是否需要對目前的分枝進一步劃分，也就是盡可能去掉一些明顯的非最優(yōu)點，避免完全枚舉.,分枝定界法（B 2x1+x250; 312x1+8x2480; 43x1100; end,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.00

18、0000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,20桶牛奶生產(chǎn)A1, 30桶生產(chǎn)A2，收益3360元。,模型求解,reduced cost值表示當(dāng)該非基變量增加一個單位時（其他非基變量保持不變）目標(biāo)函數(shù)減少的量(對max型問題),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

19、) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,也可理解為： 為了使該非基變量變成基變量，目標(biāo)函數(shù)中對應(yīng)系數(shù)應(yīng)增加的量,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.0000

20、00 4) 40.000000 0.000000,原料無剩余,時間無剩余,加工能力剩余40,Max72x1+64x2； 2）x1+x250； 3）12x1+8x2480； 4）3x1100；,三種資源,“資源” 剩余為零的約束為緊約束（有效約束）,結(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

21、) 0.000000 2.000000 4) 40.000000 0.000000,結(jié)果解釋,最優(yōu)解下“資源”增加1單位時“效益”的增量,原料增1單位, 收益增48,時間加1單位, 收益增2,能力增減不影響收益,影子價格 (對偶價格）,35元可買到1桶牛奶，要買嗎？,35 48, 應(yīng)該買！,聘用臨時工人付出的工資最多每小時幾元？,2元！,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.0

22、00000 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,最優(yōu)解不變時目標(biāo)系數(shù)允許變化范圍,DO RANGE(SENSITIVITY) ANALYSIS?,Yes,x1系數(shù)范圍(64,96),x2系數(shù)

23、范圍(48,72),A1價格增加到 30元/千克，應(yīng)否改變生產(chǎn)計劃,x1系數(shù)由243= 72 增加為303= 90，在允許范圍內(nèi),不變！,(約束條件不變),結(jié)果解釋,結(jié)果解釋,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

24、 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,影子價格有意義時約束右端的允許變化范圍,原料最多增加10,時間最多增加53,35元可買到1桶牛奶，每天最多買多少？,最多買10桶？,(目標(biāo)函數(shù)不變),問題1. 如何下料最節(jié)省 ?,練習(xí)3 鋼管下料,問題2. 客戶增加需求：,節(jié)省的標(biāo)準(zhǔn)是什么？,由于采用不同切割模式太多，會增加生產(chǎn)和管理成本，規(guī)定切割模式不

25、能超過3種。如何下料最節(jié)??？,按照客戶需要在一根原料鋼管上安排切割的一種組合。,切割模式,合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸,鋼管下料,為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)??？,合理切割模式（套裁）,2. 所用原料鋼管總根數(shù)最少,鋼管下料問題1,兩種標(biāo)準(zhǔn),1. 原料鋼管剩余總余量最小,xi 按第i 種模式切割的原料鋼管根數(shù)(i=1,2,7),約束,滿足需求,決策變量,目標(biāo)1（總余量）,按模式2切割12根,按模式5切割15根，余料27米,最優(yōu)解：x2=12, x5=15, 其余為0； 最優(yōu)值：27,整數(shù)約束： xi 為整數(shù),Lingo4.lg4,當(dāng)余

26、料沒有用處時，通常以總根數(shù)最少為目標(biāo),目標(biāo)2（總根數(shù)）,鋼管下料問題1,約束條件不變,最優(yōu)解：x2=15, x5=5, x7=5, 其余為0； 最優(yōu)值：25。,xi 為整數(shù),按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,雖余料增加8米，但減少了2根,與目標(biāo)1的結(jié)果“共切割27根，余料27米” 相比,Lingo5（根數(shù)）.lg4,鋼管下料問題2,對大規(guī)模問題，用模型的約束條件界定合理模式,增加一種需求：5米10根；切割模式不超過3種。,現(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過于復(fù)雜。,決策變量,xi 按第i 種模式切割的原料鋼管根數(shù)(i=1,2,3),r1i, r2i, r3i, r4i 第i 種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長的鋼管的數(shù)量,滿足需求,模式合理：每根余料不超過3米,整數(shù)非線性規(guī)劃模型,鋼管下料問題2