1、水質(zhì)模型（水處理數(shù)學(xué)模型）,山東建筑大學(xué) 市政與環(huán)境工程學(xué)院 李 梅,課程內(nèi)容: 以環(huán)境（水環(huán)境）系統(tǒng)為研究對(duì)象,通過(guò)分綜合,建立數(shù)學(xué)模型,以尋求系統(tǒng)的最優(yōu)或較滿意的規(guī)劃方案. 環(huán)境系統(tǒng)規(guī)劃：運(yùn)用現(xiàn)代科技的最新技術(shù)系統(tǒng)工程和計(jì)算機(jī)方法來(lái)解決環(huán)境系統(tǒng)的規(guī)劃方法。 環(huán)境系統(tǒng)特點(diǎn)： 是一個(gè)涉及到社會(huì)、經(jīng)濟(jì)、環(huán)境、資源等方面的問(wèn)題 是一個(gè)多變量、多目標(biāo)、多層次的復(fù)雜系統(tǒng)問(wèn)題 水環(huán)境系統(tǒng)數(shù)學(xué)模型類型： 各類水體的水質(zhì)模型、生態(tài)模型、污水處理和輸送過(guò)程的模型 各類工程實(shí)施的經(jīng)濟(jì)模型、效益費(fèi)用分析模型 水質(zhì)評(píng)價(jià)模型、規(guī)劃模型,課程內(nèi)容,Chapter 1 系統(tǒng)與系統(tǒng)工程 Chapter 2 系統(tǒng)分析 Cha

2、pter 3 最優(yōu)化技術(shù) (網(wǎng)絡(luò)技術(shù)) Chapter 4 環(huán)境系統(tǒng)數(shù)學(xué)模型(邢老師講授) Chapter 5 系統(tǒng)預(yù)測(cè) (決策分析 ) Chapter 6 城市污水排海工程 Chapter 7 環(huán)境污染控制系統(tǒng)規(guī)劃,本課程主要參考書(shū)籍,1.環(huán)境系統(tǒng)工程. 韋鶴平. 同濟(jì)大學(xué)出版社 2.水污染控制系統(tǒng)規(guī)劃.傅國(guó)偉,程聲通. 清華大學(xué)出版社 3.河流水質(zhì)數(shù)學(xué)模型及其模擬計(jì)算.傅國(guó)偉. 中國(guó)環(huán)境科學(xué)出版社 4.系統(tǒng)工程,汪應(yīng)洛. 機(jī)械工業(yè)出版社 5.系統(tǒng)分析.顧培亮 .機(jī)械工業(yè)出版社 6.中國(guó)水環(huán)境預(yù)測(cè)與對(duì)策概論. 劉鴻亮,韓國(guó)鋼. 中國(guó)環(huán)境科學(xué)出版社，1988 7.最優(yōu)化技術(shù)應(yīng)用. 韋鶴平.同濟(jì)

3、大學(xué)出版社. 8.優(yōu)化與決策. 徐裕生.陜西科學(xué)技術(shù)出版社.2004,Chapter 1 系統(tǒng)與系統(tǒng)工程,1.1 系統(tǒng)(System),集合性：2個(gè)要素構(gòu)成集合體 相關(guān)性：內(nèi)在要素的相互作用相互聯(lián)系 目的性：有規(guī)定目的、功能 (不可控自然系統(tǒng)除外) 環(huán)境適應(yīng)性：適應(yīng)系統(tǒng)外部環(huán)境的變化,基本特征 ：,“極其復(fù)雜的研究對(duì)象，即由相互作用和相互依賴的若干 組成部分組合成具有特定功能的有機(jī)整體，它又從屬于一個(gè)更大系統(tǒng)的組成部分”(錢(qián)學(xué)森)。,定義：,（1）按組成的屬性分為 自然系統(tǒng)：海洋、大氣、生態(tài)系統(tǒng)等 人造系統(tǒng)：工業(yè)、給排水、污染監(jiān)測(cè)控制等 復(fù)合系統(tǒng)：利用自然系統(tǒng)為人類服務(wù)建造的系統(tǒng)，氣象預(yù)報(bào)等

4、（2）按形態(tài)分 實(shí)體系統(tǒng)：物體實(shí)體，如管道構(gòu)件、機(jī)械 概念系統(tǒng)：由概念、原理、法規(guī)等組成，如法律系統(tǒng)、教育系統(tǒng),分類 ：,（3）按所處的狀態(tài)分 靜態(tài)系統(tǒng)：不隨時(shí)間變化的系統(tǒng) 動(dòng)態(tài)系統(tǒng)：隨時(shí)間變化的系統(tǒng) （4）按照規(guī)模分 小型系統(tǒng) 中型系統(tǒng) 大型系統(tǒng),分類 ：,1.2 系統(tǒng)工程(System Engineering) 系統(tǒng)工程是一門(mén)新興的高度綜合的科學(xué)，是一種組織管理的科學(xué)方法。把研究的對(duì)象看成一個(gè)系統(tǒng)，解決如何對(duì)系統(tǒng)進(jìn)行規(guī)劃、治理、組織和管理，使之獲得最佳效益。 系統(tǒng)工程的產(chǎn)生發(fā)展： 40年代正式形成 5060年代逐步形成較為完整的體系 70年代得到廣泛應(yīng)用，進(jìn)入初步成熟階段,環(huán)境系統(tǒng)工程的產(chǎn)

5、生： 人類社會(huì)的發(fā)展，環(huán)境問(wèn)題越來(lái)越嚴(yán)重，尤其是二戰(zhàn)之后生產(chǎn)的工業(yè)化程度的提高，八大公害事件的發(fā)生。 與污染環(huán)境作斗爭(zhēng)的三個(gè)經(jīng)歷： 凈水系統(tǒng)（60年代中期之前） 污水處理系統(tǒng)（60年代末、70年代初） 水環(huán)境系統(tǒng)、生態(tài)環(huán)境系統(tǒng)等（70年代以后） 研究水污染控制系統(tǒng)，使水環(huán)境恢復(fù)，符合“可持續(xù)發(fā)展”原則,系統(tǒng)工程的原則： 1. 整體性原則：全面、整體 2. 綜合性原則：目標(biāo)多樣性，方法、方案多樣性 3. 優(yōu)化性原則：實(shí)現(xiàn)最佳目標(biāo)體系 4. 模型化原則：模擬與仿真 5. 交互性原則：決策者與系統(tǒng)的信息交換,研究步驟： 1. 明確和提出問(wèn)題 2. 建立數(shù)學(xué)模型 3. 求解數(shù)學(xué)模型 4. 模型驗(yàn)證 5

6、. 結(jié)果實(shí)施,1.3 模型化 1.3.1 分類,物理模型 圖形模型 數(shù)學(xué)模型 宏觀模型 微觀模型,按基本分類:,按問(wèn)題出發(fā)點(diǎn),水質(zhì)模型 大氣模型 生態(tài)模型 經(jīng)濟(jì)模型 預(yù)測(cè)模型 決策模型 最優(yōu)化模型,按對(duì)象可分為,按用途可分為,1.3.2 數(shù)學(xué)模型分類,1.3.3 模型化程序,1.4 系統(tǒng)工程的應(yīng)用,1.4.1 應(yīng)用領(lǐng)域 涉及人類活動(dòng)的各個(gè)領(lǐng)域 (p10 表1.1),（一）大環(huán)境系統(tǒng) 水域：排污量，污徑比（p13 表1.2 ) 大氣：排污 生態(tài)系統(tǒng)：人類活動(dòng)涉及的各個(gè)方面 （二）城市生態(tài)系統(tǒng)：城市建設(shè)、生活生產(chǎn)環(huán)境與質(zhì)量提高 （三）污染控制 典型系統(tǒng)：1. 流域系統(tǒng) (如河流 ) 2. 城鎮(zhèn)給排

7、水系統(tǒng) (取水、處理、排放等) 3. 污水處理系統(tǒng) (城市污水二級(jí)處理) 舉例：黃浦江上游水源保護(hù)、綜合治理。,舉例： 城市污水再生回用系統(tǒng),污水回用系統(tǒng)影響因素 系統(tǒng)構(gòu)成 子系統(tǒng)劃分 二級(jí)子系統(tǒng)劃分 系統(tǒng)包含的元素分析 系統(tǒng)的特點(diǎn) 系統(tǒng)分析的方法,1.污水再生回用系統(tǒng)影響因素分析,2. 污水再生回用系統(tǒng)構(gòu)成,（1）再生水供水子系統(tǒng) （二級(jí)子系統(tǒng)）,（2）再生水需水子系統(tǒng) （二級(jí)子系統(tǒng)）,（3）城市供需水子系統(tǒng) （二級(jí)子系統(tǒng)）,城市供需水平衡反饋機(jī)制圖,城市污水再生回用SD模型子系統(tǒng)相互關(guān)系圖,3.城市污水再生回用系統(tǒng)特征,污水再生回用系統(tǒng)影響因素眾多且相互聯(lián)系、相互作用，并組成一個(gè)有機(jī)整體

8、系統(tǒng)具有多層次和相互嵌套性 是一個(gè)含有反饋結(jié)構(gòu)的系統(tǒng) 一個(gè)隨時(shí)間變化的動(dòng)態(tài)系統(tǒng) 采用系統(tǒng)動(dòng)力學(xué)（System Dynamics）方法,八大公害事件,比利時(shí)馬斯河谷煙霧事件：（1930年） 美國(guó)洛杉磯煙霧事件： （1943年） 美國(guó)多諾拉煙霧事件：（1948年） 英國(guó)倫敦?zé)熿F事件：(1952年) 日本熊本水俁病事件：（1953年） 日本四日市哮喘病事件：（1955年） 日本富山痛痛病事件： （ 1955年1977年） 日本愛(ài)知米糠油事件：（1966年）,可持續(xù)發(fā)展概念,可持續(xù)發(fā)展的英文翻譯：sustainable development 可持續(xù)發(fā)展的來(lái)源：最初是從環(huán)境保護(hù)角度提出來(lái)的， 在197

9、2年的斯德哥爾摩人類環(huán)境會(huì)議上首次提出了“可持續(xù)發(fā)展”。定義有很多，經(jīng)濟(jì)學(xué)家、環(huán)境學(xué)家及生態(tài)學(xué)家都給過(guò)學(xué)科性的定義，但是都有一定的局限性。到1987年，在世界環(huán)境委員會(huì)出版的我們共同的未來(lái)(our conmen future)一書(shū)中給出了一個(gè)明確的大家公認(rèn)的定義。 可持續(xù)發(fā)展的定義：既滿足當(dāng)代人的需求又不對(duì)后代人滿足其需求能力構(gòu)成危害的發(fā)展。 水資源可持續(xù)發(fā)展的含義：水資源的可持續(xù)利用,整體性原則,假設(shè)系統(tǒng)的屬性度量為a，系統(tǒng)中第i（i=1,2,3m）的屬性,數(shù)量為ai,全系統(tǒng)的屬性數(shù)量和該系統(tǒng)中各部分的屬性數(shù)量 關(guān)系: aai系統(tǒng)中各組成部分或子系統(tǒng)協(xié)調(diào)的融合在一起,使系統(tǒng)的功能增強(qiáng). a

10、=ai 系統(tǒng)總體功能等于各部分功能總和. aai 發(fā)生了不協(xié)調(diào)現(xiàn)象,產(chǎn)生” 內(nèi)耗” , 使系統(tǒng)的功能減弱,Chapter 2 系統(tǒng)分析,2.1 概述 2.1.1 系統(tǒng)分析(System Analysis) 基本概念 對(duì)一個(gè)系統(tǒng)內(nèi)的基本問(wèn)題,用系統(tǒng)的觀點(diǎn)思維推理,在確定和不確定條件下,通過(guò)分析對(duì)比,對(duì)可能采取的方法進(jìn)行優(yōu)化, 得最優(yōu)方案的輔助決策方法。 2.1.2 環(huán)境系統(tǒng)分析,排污決策，實(shí)際上就是一個(gè)系統(tǒng)優(yōu)化問(wèn)題。,2.1.3 系統(tǒng)分析的準(zhǔn)則 外、內(nèi)條件相結(jié)合：周圍環(huán)境、能源、交通等 當(dāng)前利益與長(zhǎng)遠(yuǎn)利益相結(jié)合：處理程度與投資 局部與整體利益相結(jié)合：管網(wǎng)與廠址 定量與定性分析相結(jié)合：定性定量定性

11、 2.2 系統(tǒng)分析基本要素,2.3 系統(tǒng)分析步驟 1. 確定目的（目的與目標(biāo)關(guān)系） 2. 收集分析資料 3. 系統(tǒng)模型化 4. 系統(tǒng)的最優(yōu)化 5. 系統(tǒng)的評(píng)價(jià) 2.4 系統(tǒng)分析的方法 2.4.1 系統(tǒng)最優(yōu)化,一般形式,2.4.2 層次分析法（AHP-Analytical Hierarchy Process) 定性與定量相結(jié)合、簡(jiǎn)單易行、行之有效的一種系統(tǒng)分析方法，70年代美國(guó)的薩蒂提出的。 該法1982年引入，能源、環(huán)保也得到應(yīng)用。 層次分析法步驟： 1. 明確問(wèn)題 2. 建立層次分析模型 最高層（目標(biāo)層） 中間層（準(zhǔn)則層） 最低層（方案層） 3. 建立判斷矩陣，求最大特征根及特征向量 判斷矩

12、陣構(gòu)造： 逐層逐項(xiàng)兩兩比較，評(píng)出優(yōu)劣，可從最低層始。,（最簡(jiǎn)單可分為3層） 如Fig2.4層次圖,層次圖,（第i個(gè)準(zhǔn)則）,判斷矩陣,對(duì)準(zhǔn)則Ci,亦可采用2，4，6，8等，（專家、分析人員、資料） 對(duì)i=1,2,m，由上式可得Ci的判斷矩陣，對(duì)目標(biāo)A，也要建立m個(gè)準(zhǔn)則的判斷矩陣，兩兩比較，得出判斷矩陣。,計(jì)算判斷矩陣的最大特征根及特征向量通常有三種方法：,方根法,正規(guī)化（則）求和,求和法,4. 層次單排序及判斷矩陣一致性檢驗(yàn) 層次單排序： 特征向量W為同一層次相應(yīng)因素對(duì)上一層次某一因素相對(duì)重要性的權(quán)值，稱為層次單排序。,判斷矩陣一致性： 判斷矩陣B應(yīng)滿足 具唯一非“0”最大特征根max： 隨機(jī)一

13、致性比率CR : CR 0.10，具完全一致性，否則需要新調(diào)整判斷矩陣。 其中，CI 為判斷矩陣的一致性指標(biāo), RI 為同階平均隨機(jī)一致性指標(biāo)，可從表2-1中得到,5. 層次總排序和一致性檢驗(yàn) 層次總排序，見(jiàn)表2.2（以圖2.4為例）,a1 , a2 , , am C對(duì)A的單排序權(quán)值; Wij Pi對(duì)Cj單排序的權(quán)值，,層次總排序一致性檢驗(yàn) P層次對(duì)Cj單排序一致性指標(biāo)CIi,平均隨機(jī)性指標(biāo)Rij 則 CR0.10，滿足一致性，否則重新調(diào)整判斷矩陣。 舉例2.1（作業(yè)）（說(shuō)明應(yīng)用方法，注意計(jì)算結(jié)果有誤） 舉例: (P41)常州市城市污水排江工程排放口選擇系統(tǒng)分析(P50圖2-11),2.4.3

14、 環(huán)境問(wèn)題費(fèi)用效益分析(Cost-Benefit Analysis) 1.基本學(xué)理 國(guó)外應(yīng)用較多，58年應(yīng)用于環(huán)境污染； 國(guó)內(nèi)在環(huán)境決策方面的應(yīng)用較晚。 最佳污染點(diǎn)：費(fèi)用曲線與效益曲線的交點(diǎn)（如圖）。 是準(zhǔn)優(yōu)，而非最優(yōu),2.費(fèi)用效益分析在環(huán)保中的應(yīng)用 （后述內(nèi)容自學(xué)）,城市污水處理層次模型,Chapter 3 最優(yōu)化技術(shù),1.最優(yōu)化技術(shù),最優(yōu)化技術(shù): 是從所有可能的方案中選擇最佳一種以達(dá)到最有目標(biāo)的科學(xué)，它是運(yùn)籌學(xué)的一個(gè)分支。 廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、交通運(yùn)輸、商業(yè)、國(guó)防等各個(gè)部門(mén)各個(gè)領(lǐng)域.,2.運(yùn)籌學(xué)的概念,運(yùn)籌學(xué)（Operational Research,縮寫(xiě)為O.R ）:是一門(mén)應(yīng)用于管理有

15、組織系統(tǒng)的科學(xué); 運(yùn)籌學(xué)一詞起源于20世紀(jì)30年代,1940年英國(guó)成立了由物理學(xué)家布萊克特(P.M.S.Blackett)組成的第一個(gè)研究組,3.運(yùn)籌學(xué)的發(fā)展可分為三個(gè)階段,(1)1945到50年代初,稱為創(chuàng)建時(shí)期. (2)50年代初期到50年代末期,稱為成長(zhǎng)時(shí)期 (3)20世紀(jì)60年代,迅速發(fā)展和普及時(shí)期 在1956年引入我國(guó)的，80年代后得到廣泛的推廣。,4.運(yùn)籌學(xué)基本特征,系統(tǒng)的整體觀念 多學(xué)科的綜合 模型方法的應(yīng)用,分析和表述問(wèn)題：定性、定量分析確定目標(biāo) 建立模型 求解模型和優(yōu)化方案 對(duì)模型和由模型導(dǎo)出的解進(jìn)行檢驗(yàn) 建立起對(duì)解的有效控制：任何模型都有適用范圍,注意模型和它的解是否有效，

16、并及時(shí)調(diào)整； 方案的實(shí)施,5 運(yùn)籌學(xué)研究問(wèn)題的步驟,線性規(guī)劃（linear programming） 非線性規(guī)劃（nonlinear programming） 動(dòng)態(tài)規(guī)劃（dynamic programming） 整數(shù)規(guī)劃（integer programming） 網(wǎng)絡(luò)分析（graph theory and network analysis) 存貯論（inventory theory） 排隊(duì)論（queuing theory ，waiting line） 對(duì)策論（game theory） 決策論（decision theory）,6.運(yùn)籌學(xué)的分支,最優(yōu)化方法,3.1 線性規(guī)劃 3.1.1 定義 1

17、. 目標(biāo)函數(shù)為線性 2. 約束條件線性 3. 變量非負(fù),矩陣表示,非標(biāo)準(zhǔn)形式化為標(biāo)準(zhǔn)型式，引入 1. 松馳變量 約束矩陣方程為“”時(shí)，不等式左端加上一個(gè)非負(fù)變量松馳變量，使不等式約束變?yōu)榈仁郊s束，目標(biāo)函數(shù)cn+I(i=1,2,m)=0 2. 剩余變量 約束方程“”時(shí)，不等式左端減去一個(gè)非負(fù)變量剩余變量，變不等式約束為等式約束，目標(biāo)函數(shù)同上。 3. 自由變量 變量非負(fù)問(wèn)題 目標(biāo)函數(shù)由最大求最小，變量可負(fù),標(biāo)準(zhǔn)形式:,例題: 將下列線性規(guī)劃化為標(biāo)準(zhǔn)形,解: 令z=z， x1=x1，x3=x3x3，其中x30 ，x30； 該問(wèn)題的標(biāo)準(zhǔn)形式為 :,3.1.2 線性規(guī)劃求解方法,1.圖解法（二維平面問(wèn)題

18、） 2. 單純形法（simplex method) 3.人工變量法（人造基） 4.改進(jìn)單純形法 5.對(duì)偶線性規(guī)劃,1.圖解法（二維平面問(wèn)題）,圖解法適合于二維、三維的線性規(guī)劃問(wèn)題，圖解法有助于了解線性規(guī)劃的基本原理。 先給出可行域，令f(x1,x2)=0在可行域內(nèi)平移，直接得出最優(yōu)解 （p56例3-1，圖3-2；p56例3-2 ，圖3-3 ）,圖解法例題1,用圖解法求解,以上條件在圖形中形成的區(qū)域?yàn)殛幱安糠郑碠ABC區(qū)域） 構(gòu)成了凸多邊形（凸集，滿足于約束條件的可行域） 虛線表示z=2 x1+3x2 ， 在可行域中尋找目標(biāo)函數(shù)的最優(yōu)解，先設(shè)z=0，然后平行上移，直到最大值，得出在B點(diǎn)（4，2

19、），計(jì)算z=2 x1+3x2 =14,約束條件： 3 x1+6 x224代表直線AB左下方的半平面； 2 x1+ x210代表直線BC左下方的半平面； x1，x20 是指第一象限；,用圖解法求解,maxz=2x1+x2,目標(biāo)函數(shù)變化,有無(wú)限多個(gè)最優(yōu)解,圖解法例題2,maxz=2x1+2x2 x1 x21 s. t. x1+ 2x20 x1，x20,無(wú)最優(yōu)解,圖解法例題3,2. 單純形法（simplex method),（1）丹塞(Dantzig) 1947年提出的。 （2）思路 從可行域中尋求出一個(gè)初始基本可行解，檢驗(yàn)?zāi)繕?biāo)函數(shù)值是否最優(yōu)，若不是設(shè)法求另一個(gè)基本可行解，使這個(gè)可行解的目標(biāo)函數(shù)優(yōu)于

20、前一個(gè)基本可行解的目標(biāo)函數(shù)，使目標(biāo)函數(shù)值逐漸增大，直到達(dá)到最大值，或判別出無(wú)最優(yōu)解為止。 （由一基本可行解出發(fā)，逐步改進(jìn)目標(biāo)點(diǎn)數(shù)值，直至求到最優(yōu)解）,（3）步驟 求初始解可行解,列出初始單純形表; 最優(yōu)性檢驗(yàn): 檢驗(yàn)數(shù) 0，表中的基可行解為最優(yōu)解，計(jì)算結(jié)束，否則轉(zhuǎn)為下一步; 從一個(gè)基可行解轉(zhuǎn)換到相鄰的目標(biāo)函數(shù)更大的基可行解，列出新的單純形表。 確定調(diào)入基的變量，檢驗(yàn)數(shù) 確定調(diào)出基的變量，離基變量的最小比值 基變量變換，得到一個(gè)新的基 重復(fù)2，3步,單純形法基本概念,（1）確定初始基本可行解：從約束函數(shù)中觀察到存在m個(gè)線性無(wú)關(guān)的單位向量，令 非基變量xN=（x1。x2xm）T=（0，0， 0）

21、T， 得到基變量xB=（bm+1，b2bn）T，得到xN=（0，0， 0， bm+1，b2bn ） T為基可行解。 （2）最優(yōu)解檢驗(yàn)：檢驗(yàn)數(shù) 0，表中的基可行解為最優(yōu)解， 檢驗(yàn)數(shù)的求法 用檢驗(yàn)數(shù)做最優(yōu)解的檢驗(yàn)原因：定理2個(gè) 最優(yōu)解判別定理 無(wú)有限最優(yōu)解判別定理 （3）單純形表：設(shè)計(jì)單純形表 （4） 基變換 ： 確定調(diào)入變量，一般選檢驗(yàn)數(shù)j 0中的最大者，即maxj0=k對(duì)應(yīng)的這一列的非基變量xk作為調(diào)入變量； 確定調(diào)出變量，離基變量的最小比值，遵守規(guī)則（最小比值規(guī)則） 對(duì)應(yīng)的這一行的基變量xi為調(diào)出變量。 （5）主元素：調(diào)入變量與調(diào)出變量的交叉點(diǎn)處的元素。,原方程可改寫(xiě)為：,寫(xiě)成增廣矩陣的形式

22、,利用矩陣的初等行變換，將c1 c2cm消為0，得單純形表。,單純形法例題,+0 x3+0 x4,變標(biāo)準(zhǔn)形,1.變標(biāo)準(zhǔn)形,取松弛變量為x3，x4基變量, x1，x2為非基變量, 建立初始單純形表,最優(yōu)解檢驗(yàn)數(shù)1=2, 2=3,3= 4 =0,令非基變量 x1=x2=0,得到初始可行解X=（0，0，24，10）T目標(biāo)函數(shù)值z(mì)= 0,寫(xiě)成增廣矩陣 3x1+ 6x2+x3+0 x4=24 2 x1+x2+0 x3+x4=10 z+2x1+3x2+0 x3+0 x4=0,2. 因基變量檢驗(yàn)數(shù) 1 和 2大于0, 取max1, 2=3 ,2=3 對(duì)應(yīng)的非基變量為x2作為換入變量, 3.確定換出變量: 4

23、.1=4對(duì)應(yīng)于變量x3這一行,所以x3為換出變量: x2所在列與x3所在行的交叉點(diǎn)為6,作為主元素,檢驗(yàn)數(shù)值,-z值,基變量系數(shù),基變量,值,1 =2-（0 3+ 0 2）=2 2 =3-（06+ 01）=3,1=24/6=4 2=10/1=10,增廣矩陣 3x1+ 6x2+x3+0 x4=24 2 x1+x2+0 x3+x4=10 z+2x1+3x2+0 x3+0 x4=0,4.以6 為主元素進(jìn)行變換,把這一列變成單位向量,將x2換到原基變量x3的位置,得到新的單純形表,令非基變量x1=0，x3=0,得到新的基本可行解X=（0，4，0，6）T， 目標(biāo)函數(shù)值z(mì)= 12,此時(shí)，最后以行的檢驗(yàn)數(shù)都

24、是負(fù)數(shù)或零，即i 0，目標(biāo)函數(shù)已不再增大，那么最優(yōu)解x=（4，2，0，0）T， 目標(biāo)函數(shù)值z(mì)= 14,說(shuō)明: 例題以maxz =cx, Ax =b, x0為標(biāo)準(zhǔn)型時(shí)，以檢驗(yàn)數(shù)j0(j=1,n),為最優(yōu)判別準(zhǔn)則 若以minz =cx, Ax =b, x0為標(biāo)準(zhǔn)型時(shí)以檢驗(yàn)數(shù)j0(j=1,n),為最優(yōu)判別準(zhǔn)則選擇換入變量時(shí)，取j=cjzj0 確定換入變量.,5.檢查所有的檢驗(yàn)數(shù)1 =1/2, 3 = -1/2 ,2= 4 =0, max1, 3=1/2 0,取x1為換入變量, 計(jì)算得x4為換出變量，通過(guò)矩陣變換,得到新的單純形表,單純形法求(最大值)步驟框圖,3. 人造基,規(guī)劃中當(dāng)約束方程中至少有一

25、個(gè)為“=”或“”時(shí)，松馳變量無(wú)法給出一個(gè)初始基本可行解，需引入人造基變量。 不是為了滿足約束條件有不等式變成等式而加的，而為了能應(yīng)用單純形法來(lái)迭代并求極值而引進(jìn)的，有人為引進(jìn)的意思的。 步驟： 問(wèn)題化為標(biāo)準(zhǔn)形式 “” “”約束方程左邊加一個(gè)非負(fù)變量 對(duì)初始基本解應(yīng)用人造基變量 按單純形法進(jìn)行求解,3.2 整數(shù)規(guī)劃(integer programming）,3.2.1 定義 至少一個(gè)變量限定為非負(fù)整數(shù)整數(shù)或混合整數(shù)線性規(guī)劃。 3.2.2 求解方法 1. 圓整法按非整數(shù)求解，最優(yōu)解取整。 問(wèn)題：圓整解并非直正整數(shù)規(guī)劃最優(yōu)解。（見(jiàn)p71例題） 2. 割平面法壓縮可行解集合，割掉部分可行域。 a、按非

26、整法應(yīng)用單純形式求解； b、若最優(yōu)解為整，則完成，若非整轉(zhuǎn)c； c、引入一個(gè)附加約束，割去部分可行域，重復(fù)上述a,b。 （見(jiàn)p72例題3-13）,3.3 非線性規(guī)劃(Nonlinear Programming）,3.3.1 定義 目標(biāo)函數(shù)或約束條件中有一個(gè)或多個(gè)為非線性函數(shù)時(shí)的規(guī)劃問(wèn)題。 科學(xué)研究和工程技術(shù)中多數(shù)是非線性規(guī)劃問(wèn)題。 例如：opti f（x1，x2 xn） s.t. gi（ x1，x2 xn）（=，）0 xj 0 f 和gi至少有一個(gè)函數(shù)為非線性函數(shù)。 類型：無(wú)約束最優(yōu)化法： 有約束最優(yōu)化法,如果無(wú)約束條件，求f（x，y）的最小值，稱為無(wú)約束最優(yōu)化問(wèn)題,舉例： 某市有n個(gè)工廠排放

27、污水，擬集中于污水處理廠。已知工廠j的污水排放量為Qj，單方水每公里的費(fèi)用為cj，確定污水處理廠的位置，使總輸水投資最小。 解：設(shè)污水處理廠位置為（x，y），則 從工廠j到污水處理廠的輸水費(fèi)用為 n工廠的總輸水費(fèi)用,3.3.2 無(wú)約束最優(yōu)化方法,1. 含義 無(wú)約束NP問(wèn)題為minf（X）， XEn也就是求n元目標(biāo)函數(shù)f（x）在n維空間En上的的最小值。 2.方法 （1）解析法：在構(gòu)造算法時(shí)，利用目標(biāo)函數(shù)的一階導(dǎo)數(shù)（梯度）或二階導(dǎo)數(shù) （海森矩陣） （2）直接法：只比較目標(biāo)函數(shù)的大小，構(gòu)造下降迭代算法 3.存在最優(yōu)解充要條件,1. 最速下降法（梯度法、登山法）,（f(x)在x(h)處一階逼近） 若

28、目標(biāo)函數(shù)寫(xiě)成操作變量的函數(shù) P=F(x1，x2，xm )，那么 P 與 xh 構(gòu)成 m+1 維空間。若以圖形表示函數(shù)，就為曲面，曲面的最高點(diǎn)（或最低點(diǎn)）即極值點(diǎn) 所謂“登山”即從曲面上任意點(diǎn)（初始解）出發(fā)向峰點(diǎn)逼近的過(guò)程。 設(shè) minF（X） XRn 函數(shù)在點(diǎn)處的梯度為： 沿著法線方向上升最快（等高線），反之，沿負(fù)梯度的方向，即為下降最快的方向 S（k）= f（X（k） （負(fù)梯度的方向）,Dm,起點(diǎn)、終點(diǎn) Dm 必須滿足（3.31）式，或由該式協(xié)調(diào)，然而， 都是未知的，需要有一種方法解決這一問(wèn)題。,（2）快速登山法,或,（1）搜索矢量與步長(zhǎng) 搜索矢量：表示從出發(fā)點(diǎn)前進(jìn)的矢量，步長(zhǎng)則表示求前進(jìn)步

29、幅大小。 若以矢量表示出發(fā)點(diǎn)、到達(dá)點(diǎn)，則與搜索矢量的關(guān)系可表示為,（3.31）,登山方向矢量,使符合由出發(fā)點(diǎn)以最大梯度前進(jìn) 符號(hào)“”，求極大用“”，求極小用“”。,步長(zhǎng)k的求法：確定為一個(gè)常數(shù)，試算，但需要檢驗(yàn) 公式計(jì)算： Xm先給定一個(gè)初始點(diǎn) X（0）,并且 xh 在方向移動(dòng)距離為, 為任意常數(shù)，相當(dāng)于步長(zhǎng),最速下降法步驟： a. 選取初值X（0）及精度 ； b. 令k=0； c. 計(jì)算f（X（k），并令 Dm= f（X（k）； d. 如果 f（X（k）2，最優(yōu)解迭代終止，X*即為所求，否則進(jìn)行下一步； e. 用公式求步長(zhǎng)k f. 計(jì)算 ，k=k+1，轉(zhuǎn)向c,幾點(diǎn)說(shuō)明： 步長(zhǎng)很重要，P 曲面

30、復(fù)雜時(shí)要選小些，曲面簡(jiǎn)單時(shí)可大些； 當(dāng)存在兩個(gè)以上極值時(shí)，一旦到達(dá)其一就不能前進(jìn)，為此應(yīng)選擇幾個(gè)出發(fā)點(diǎn)； 到達(dá)是極值點(diǎn)還是鞍點(diǎn)，落入鞍點(diǎn)就無(wú)法解脫； 變步長(zhǎng)方法： 一次成功，下次取3倍步長(zhǎng)； 一次失敗，下次取1/2步長(zhǎng)。,為什么搜索失??？ 如從1點(diǎn)出發(fā)，因步長(zhǎng)太大，超越極值點(diǎn) 步長(zhǎng)小些為好，視 P 增加情況而定。 01 ，步長(zhǎng)太大, 改向，說(shuō)明步長(zhǎng)不當(dāng) 如極值為極大, 改向， 即表示有問(wèn)題 01，P 增長(zhǎng)不多,要判別平坦或越過(guò)。,梯度法例題,用梯度法求：f(X)=(x1-1)2+(x2-1)2的極小值， 取初值：X（0）=（0，0）T，=0.1 解 ： (1)求目標(biāo)函數(shù)的一階偏導(dǎo)數(shù) f(X)=

31、2(x1-1) ，2(x2-1)T 那么 f(X（0）)=（-2，-2）T (2)檢驗(yàn) (3)繼續(xù)迭代，求步長(zhǎng)k 先求海森矩陣,所以X（1）為極小點(diǎn),因?yàn)?步長(zhǎng)k,則,f(X)=2(x1-1) ，2(x2-1)T,2. 二階梯度法（ x(h)處的二階逼近）,如果將最速下降法的搜索方向可看作對(duì)目標(biāo)函數(shù)的一種線性逼近或一階逼近，那么，二階梯度法則可認(rèn)為是F(X)在X(k)點(diǎn)處的二階逼近。 將F(X)在其某個(gè)近似極小點(diǎn)X(k)處進(jìn)行二階Talor 級(jí)數(shù)展開(kāi)，有,二階梯度法迭代程序,.3 有約束非線性規(guī)劃 1. 線性逼近法 非線性目標(biāo)函數(shù)、線性約束：將目標(biāo)函數(shù)在可行域的任一頂點(diǎn)X(0)處展開(kāi)變?yōu)榫€性函

32、數(shù)求解線性規(guī)劃問(wèn)題。 設(shè)目標(biāo)函數(shù)是非線性的，約束條件為線性的，其數(shù)學(xué)模型為,（3.39）,式中,約束條件構(gòu)成的可行域,是凸多面體。若F(X)為二次函數(shù)，這就是所謂二次規(guī)劃。 由線性規(guī)劃的理論可知，其可行點(diǎn)的集合為一凸多面體，它有有限個(gè)頂點(diǎn)?，F(xiàn)取R的任一頂點(diǎn) ，將目標(biāo)函數(shù)F(X)在X(0)處展開(kāi)：,這樣，就將F(X)近似表達(dá)成X的線性函數(shù)L(X)，求以下線性規(guī)劃問(wèn)題,（3.40）,上述線性規(guī)劃的最優(yōu)解等價(jià)于求下述線性規(guī)劃的最優(yōu)解。,由此，非線性最優(yōu)化問(wèn)題在X(0)初始點(diǎn)就變成線性規(guī)劃問(wèn)題，若其最優(yōu)解為Y(0)，則Y(0)一定在約束凸集的頂點(diǎn)。 線性逼近法迭代步驟為：,（3.40a）,a. 令k=

33、0；給定原問(wèn)題式（3.39）可行域某一個(gè)可行點(diǎn)X(0)和允許誤差； b. 求線性規(guī)劃 的最優(yōu)解。,c. 檢驗(yàn)是否滿足收斂準(zhǔn)則,如滿足，則X*= X(k) ，迭代終止；否則，執(zhí)行d； d. 求一維極值問(wèn)題,e.,令 k=k +1，轉(zhuǎn)向b。,2. 罰函數(shù)法 建立一新的函數(shù)，將有約束非線性規(guī)劃轉(zhuǎn)化為無(wú)約束問(wèn)題求解。,由最優(yōu)解 計(jì)算：,構(gòu)成,對(duì)不滿足約束時(shí)函數(shù) 值越大（求極?。ㄆ渲蠱k為任意大的正數(shù)“罰因子”）則偏離最優(yōu)（小）值越遠(yuǎn)，以示懲罰；當(dāng)滿足約束時(shí)，其值為“0”，無(wú)懲罰。 對(duì)于引入函數(shù) ，當(dāng)X不在可行域時(shí)，取正值構(gòu)成罰函數(shù)，因而也稱為外點(diǎn)罰函數(shù)法。,外點(diǎn)法 對(duì)引進(jìn)函數(shù) ，當(dāng)X不在可行解集合時(shí)

34、，取正值以構(gòu)成罰函數(shù)。,內(nèi)點(diǎn)法 罰函數(shù)為 式中 為內(nèi)點(diǎn)罰函數(shù)。,若 rk0時(shí)，極小值點(diǎn)為最優(yōu)解。 例3-18 說(shuō)明，內(nèi)、外點(diǎn)罰函數(shù)法應(yīng)用。,3.4 動(dòng)態(tài)規(guī)劃（Dynamic Programming）,有些問(wèn)題是時(shí)間而變化（或隨空間位置的變化）的活動(dòng)過(guò)程，這樣一個(gè)系統(tǒng)的最優(yōu)決策含有多階段決策。稱為動(dòng)態(tài)規(guī)劃(簡(jiǎn)稱DP）。 3.4.1 基本概念 1. 階段：若干互相聯(lián)系階段。 2. 狀態(tài)與狀態(tài)變量：xk 出發(fā)位置：本段起點(diǎn)，前段終點(diǎn)，一階段含多個(gè)狀態(tài)。 描述狀態(tài)的變量：可為一個(gè)數(shù)、數(shù)組、向量等。 3. 決策與決策變量：uk(xk) 某階段狀態(tài)給定后，從該狀態(tài)演變到下階段某狀態(tài)的選擇。 描述決策的變量

35、稱為決策變量。 4. 策略：ui(xi) 決策函數(shù)的集合 5. 指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)：Vk,n 最優(yōu)fk(xk） 隨空間位置的變化的舉例：水質(zhì)規(guī)劃、投資分配,3.4.2 動(dòng)態(tài)規(guī)劃方法的應(yīng)用 河流水污染控制系統(tǒng)規(guī)劃 資源分配問(wèn)題 1. 河流水污染控制系統(tǒng)規(guī)劃 河流系統(tǒng)分析：以河流水污染控制系統(tǒng)規(guī)劃說(shuō)明應(yīng)用（逆序法求解） 一條河流可分為多個(gè)河段串聯(lián)系統(tǒng)，如下圖。 前一級(jí)的輸出即為后一級(jí)輸入。,為第i級(jí)的m維決策向量（如：Q，等）,n,為第i級(jí)的n維狀態(tài)向量（如：BOD，COD， TOC，DO，SS等）,第i級(jí)的狀態(tài)方程 n維狀態(tài)向量函數(shù) 求滿足每一級(jí)狀態(tài)方程約束條件下，使目標(biāo)最優(yōu)的決策序列： 以費(fèi)用為目標(biāo)， 則規(guī)劃問(wèn)題寫(xiě)為：,以Streeter-Phelps水質(zhì)模型為例，狀態(tài)變量：BOD5 ，DO，決策變量為各河段污水處理程度：目標(biāo)為總費(fèi)用，即在各沿程i為何值時(shí)（滿足各段水質(zhì)約束條件下），總費(fèi)用為最小？ 逆序法從最后一級(jí)開(kāi)始（下圖）,此時(shí)：狀態(tài)變量xi為：Li，Oi 決策變量ui為：