組合優(yōu)化模型_第1頁
組合優(yōu)化模型_第2頁
組合優(yōu)化模型_第3頁
組合優(yōu)化模型_第4頁
組合優(yōu)化模型_第5頁
已閱讀5頁,還剩26頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、關于組合優(yōu)化模型1第一張,PPT共三十一頁,創(chuàng)作于2022年6月2第一章 模 型1 關于模型2 數學模型3 組合優(yōu)化模型第二張,PPT共三十一頁,創(chuàng)作于2022年6月3第一章 組合優(yōu)化模型 模型(model )是所研究的系統(tǒng)、過程、事物或概念的一種表達形式 . 1 關于模型一、模型的概念 模型不是研究對象本身,而是對研究對象的一種抽象,它反映現實中對象系統(tǒng)的主要特征,但它又高于現實,因而具有同類問題的共性 . 由于研究目的的不同,對于同一個對象系統(tǒng),可以建立完全不同的模型,分別反映該系統(tǒng)的不同側面;出于相同的研究目的,對于同一個對象系統(tǒng),也可能建立不同的模型,反映不同的研究角度、考察因素和價值

2、取向 .第三張,PPT共三十一頁,創(chuàng)作于2022年6月41 關于模型二、模型的本質 從系統(tǒng)概念上看,模型是系統(tǒng)中各種關系的表達形式 . 因此,建立模型要從狀態(tài)和過程兩個方面去尋找、把握和描述各系統(tǒng)要素之間的相互關系 .狀態(tài):事物在某個時刻所處的狀況或表現形態(tài) 過程:事物狀態(tài)的變化在時間上的持續(xù)和空間上的延伸 過程和狀態(tài)兩者緊密聯系、不可分割,狀態(tài)決定和影響過程,過程又決定和影響新的狀態(tài) . 狀態(tài)和過程是相對的 .第四張,PPT共三十一頁,創(chuàng)作于2022年6月5 從認識論上看,模型是作為認識與實踐活動的中介 .現實世界認識(信息) 模 型實踐活動概念化用信息載體表達決策(行動方案)產品和服務模型

3、化過程示意圖模型既是認識的表達,又是實踐活動的先導 . 模型參與認識世界和改造世界的不斷的循環(huán)往復過程,既是認識不斷深化的體現,又是實踐活動不斷拓展的體現 .第一章 組合優(yōu)化模型第五張,PPT共三十一頁,創(chuàng)作于2022年6月61 關于模型 從信息論上看,模型和認識之間存在密切的反饋關系 . 從已知信息可以通過模型加工產生出新的信息,相關信息的積累可以從量變產生質變,形成新的概念,促使認識深化 . 因此,模型的建立和完善不僅要注重對系統(tǒng)物質形態(tài)和能量形態(tài)的認識、把握和描述,而且也依賴于對系統(tǒng)相關信息不斷的采集、積累和加工,這就是用模型研究問題的現實活動 .第六張,PPT共三十一頁,創(chuàng)作于2022

4、年6月7三、模型的分類1、原樣模型 原樣模型是在工程開發(fā)末期建立的一種具象實體,是具有實物形態(tài)的模型 .它與目的工程在結構和過程方面基本相同 . 原樣模型經過試驗改進和完善后便是所要開發(fā)的目的工程 .新產品的樣機、新著作的原稿 第一章 組合優(yōu)化模型第七張,PPT共三十一頁,創(chuàng)作于2022年6月81 關于模型2、相似模型 相似模型是根據不同系統(tǒng)間的相似規(guī)律(包括幾何相似、邏輯相似和過程相似等)而建立的用于研究的模型 .3、圖形模型 地球儀、船體放樣模型、飛機風洞實驗模擬模型等等圖形模型可以表達非常豐富的內容,主要有: 圖畫 一種可以示形的圖形; 草圖 一種可以示意的圖形; 框圖 一種可以表示系統(tǒng)

5、的部分之間或部分 與整體之間聯系的圖形; 稱為不嚴格圖(沒有嚴格的規(guī)范) 系統(tǒng)分析和設計人員常常借助于這些圖形模型來開發(fā)、構建一個新系統(tǒng)的想象力和創(chuàng)造力,逐步引申出與之有關的問題和需要進一步探索的問題,使所要開發(fā)的系統(tǒng)變得越來越清晰、越來越具體 .第八張,PPT共三十一頁,創(chuàng)作于2022年6月9 邏輯圖 一種可以反映因素或對象間邏輯關系 的圖形; 如:程序流程圖、控制關系圖 etc. 工程圖 一種可以反映物體確定的結構和順序 關系的圖形; 如:建筑工程圖、鐵路站場配置圖 etc. 圖論圖 包括圖論所定義的無向圖 G(V,E) 、 有向圖 G(V,A)、加權有(無)向圖G(V,A(E),w).關

6、系 稱為嚴格圖(有嚴格確定的結構形式和規(guī)范)4、數學模型 數學模型是指運用數學符號和公式來表達、研究對象系統(tǒng)的結構或過程的模型 .數學模型是用數學的語言、方法去近似地刻畫實際 ,是由數字、字母或其他數學符號組成的,描述現實對象數量規(guī)律的數學公式、圖形或算法 . 是對現實對象本質屬性的抽象而又簡潔的刻畫,它或能解釋某些客觀現象,或能預測未來的發(fā)展規(guī)律,或能為控制某一現象的發(fā)展提供某種意義下的最優(yōu)策略或較好策略 .Go back第一章 組合優(yōu)化模型第九張,PPT共三十一頁,創(chuàng)作于2022年6月102 數學模型Example 1七橋問題 18世紀的德國有個哥尼斯堡城,在流貫全城的普雷爾河兩岸和河中兩

7、個島之間架設了七座橋,把河的兩岸和兩島連接起來,能否有這樣一種走法,它通過每座橋一次且僅一次 .該問題由Euler在1736年解決Solution :第十張,PPT共三十一頁,創(chuàng)作于2022年6月11ABCD 顯然,解決該問題時,兩岸和島的大小、形狀以及橋的長短曲直都無關,重要的是什么?每塊陸地間有幾座橋對問題進行數學抽象: 把兩岸和兩島都看做頂點,將連接這些頂點的橋當作邊,于是得到一無向圖 . 則七橋問題就成為無向圖中是否存在通過每一邊一次且僅一次的路(即一筆畫)問題 .第一章 組合優(yōu)化模型第十一張,PPT共三十一頁,創(chuàng)作于2022年6月122 數學模型ABCDEuler 在他的論文中證明:

8、 一個圖中存在一筆畫的充要條件是同時滿足:1、圖是連通的;2、與圖中每一頂點(可能有兩點例外)相連的邊 (線度)必須是偶數條 .這是關于圖論的第一篇論文 見圖可知,與四個頂點相連的邊都是奇數條,因而不可能存在通過每條邊一次且僅一次的畫法,即一筆畫不存在 . 故七橋問題不可能有解 .問題原型七橋問題數學模型一筆畫問題無 解(一次過七座橋不可能)無 解(一筆畫不可能)數學抽象邏輯推理翻譯回去有無解?這是利用數學模型分析和解決問題的一個成功范例第十二張,PPT共三十一頁,創(chuàng)作于2022年6月13一、數學模型的特點1、高度的抽象性 數學方法不僅要拋開事物的次要屬性,突出事物的本質屬性,而且要舍棄事物的

9、物質和能量方面的具體內容,只考慮其數量關系和空間形式,同時還要把這些數量關系和空間形式作進一步的抽象,加以形式化和符號化,以便能夠進行邏輯推理和數值運算 . 這種高度的抽象性,實質是對事物認識上的高度概括和深化,對同類問題包含更多的經驗和理解 .第一章 組合優(yōu)化模型第十三張,PPT共三十一頁,創(chuàng)作于2022年6月142 數學模型2、高度的精確性數學方法的高度精確性表現在三個方面: 一是表達各種因素、變量和它們之間的關系相當明確、清楚;二是邏輯推演和運算規(guī)則十分嚴密;三是結論非常確定 . 數學方法可以處理多變量、關系復雜的問題,可在有意義的范圍內獲得令人滿意的計算精度 . 特別適合于揭示事物的量

10、的規(guī)定性,成為定量研究的有力工具 .第十四張,PPT共三十一頁,創(chuàng)作于2022年6月153、應用的普適性 數學方法的高度抽象和精確,使之比任何一種科學方法的應用范圍都更為廣泛 . 只存在尚未運用數學方法的領域而不存在不能運用數學方法的領域 . 許多相同形式的數學模型可用于不同的實際問題,具有重要類比和借鑒意義 .數學方法的形式化和公理化,使模型本身、計算過程和計算結果都便于交流,數學模型易變動,便于修改和改變計算關系,分析和求解問題速度快,求解成本低 .數學模型缺乏直觀性、形象性和實時感第一章 組合優(yōu)化模型第十五張,PPT共三十一頁,創(chuàng)作于2022年6月162 數學模型二、數學模型分類數學模型

11、分類的方法很多,如:1、按所研究問題的性質分類 靜態(tài)模型與動態(tài)模型 確定型模型與隨機型模型 連續(xù)模型與離散模型 線性模型與非線性模型 宏觀模型與微觀模型第十六張,PPT共三十一頁,創(chuàng)作于2022年6月172、按模型的解的特征分類解析模型與數值模型3、按模型所用的數學方法分類初等模型、微分方程模型、差分方程模型、優(yōu)化模型等4、按模型研究的實際范疇分類人口模型、生態(tài)系統(tǒng)模型 、交通流模型、經濟模型、 基因模型等5、按對實際問題了解的程度分類 白箱模型、灰箱模型、黑箱模型第一章 組合優(yōu)化模型第十七張,PPT共三十一頁,創(chuàng)作于2022年6月182 數學模型三、數學建模的基本步驟 數學模型因問題不同而異

12、,對同一問題,從不同角度、不同要求出發(fā),甚至問題的解表示結構不同,都可以建立不同的數學模型. 建立數學模型也沒有固定的方法、標準 . 不同的實際問題,建模模式千差萬別. 在此介紹通常的幾個步驟: 數學建模問題直接來源各領域實際,往往含糊不清(目的、條件、類型 etc.). 首先,要對該問題進行全面的、深入細微的調查和研究. 明確所解決問題的性質,著手收集數據 ;1、明確問題合理地、有目的地注意精度第十八張,PPT共三十一頁,創(chuàng)作于2022年6月192、合理假設 現實問題錯綜復雜,涉及面非常之廣. 一個數學模型面面俱到、無所不包地反映一個現實是不可能的,即使可能,也因其過于復雜而很難求解,也是沒

13、有必要的 . 所以,要作合理的假設 .1、簡化問題2、限定適用范圍但也不能忽略實質相關的因素 作假設的依據通常是出于對問題內在規(guī)律的認識,或來自對數據或現象的分析,也可以是二者的綜合. 善于辨別問題的主次,抓住主要因素,通過合理假設,使問題簡化以便進行數學描述 . 假設是在模型的建立、求解和分析過程中完善 .通常開始讓問題盡可能簡化第一章 組合優(yōu)化模型第十九張,PPT共三十一頁,創(chuàng)作于2022年6月202 數學模型3、建立模型 建模時,要分清問題的類型恰當使用數學工具;抓住問題的本質簡化變量之間的關系 . 用什么樣的方法建立數學模型,沒有絕對的標準;數學模型的形式可以是多種多樣,數學公式、表格

14、、圖形、算法 . 模型的優(yōu)劣在于是否采用了恰當的方法,合理地描述了實際問題,而不在于是否用到了高深的數學工具 .數學建模是一個過程 .第二十張,PPT共三十一頁,創(chuàng)作于2022年6月214、模型求解 不同的模型要用到不同的數學工具求解 . 這就要求從事實際工作者對相應的數學分支知識有一定的了解 .可借助計算機,特別是利用數學工具軟件 .5、模型分析 對模型求出的解進行數學上的分析,有助于對實際問題的解決 .如: 結果的誤差分析誤差是否在允許的范圍內分析誤差來源:建模假設的誤差;數據測量的誤差;近似求解方法的誤差;計算工具的舍入誤差 . 結果的統(tǒng)計分析結果是否符合特定的統(tǒng)計規(guī)律 模型對數據的靈敏

15、度分析模型的結果是否會因數據的微小改變而發(fā)生大的變化 對假設的魯棒性分析模型的結果是否對某一假設非常依賴 不同模型間的對比分析robustness第一章 組合優(yōu)化模型第二十一張,PPT共三十一頁,創(chuàng)作于2022年6月222 數學模型6、模型檢驗 將求解結果和分析結果翻譯回到實際問題之中,與實際現象、實際數據進行比較,檢驗是否與實際吻合 . 如果吻合較好,則模型及其結果可以應用于實際問題;如果吻合不好,則需要對模型進行修正 .7、改進模型 吻合不好,問題常常出現在模型假設上 . 可能由于假設了過于苛刻的條件,或者忽略了一些不該忽略的因素. 所以, 要對實際問題中的主次因素再次分析,對模型進行修改

16、、補充、完善 . 需要多次反復才能達到比較滿意的程度 。第二十二張,PPT共三十一頁,創(chuàng)作于2022年6月238、模型應用 數學建模最終的目的是為了解決問題 . 一方面可以解釋以前的實踐成果;另一方面可以為現在的實際問題提供解決方案,甚至可以對一些不確定的現象或規(guī)律作出預測 .現實問題簡化、假設建立模型求解模型檢驗分析模型模型應用觀察、分析收集數據確定主要因素及相互關系Go back第一章 組合優(yōu)化模型第二十三張,PPT共三十一頁,創(chuàng)作于2022年6月243 組合優(yōu)化模型Example 2 某商場根據客流量統(tǒng)計得出一周中每天所需要的營業(yè)員數如表:營業(yè)員配置問題時間周一周二周三周四周五周六周日所

17、需營業(yè)員數677278768510698 如果規(guī)定每個營業(yè)員每周連續(xù)工作 5 天,休息 2 天,求總人數最少的營業(yè)員排班方案 .Solution : 設 xj 為從周 j 開始連續(xù)工作 5 天的營業(yè)員人數,j = 1,7 (其中 x7 為周日開始連續(xù)工作 5 天的營業(yè)員數),則可行解集是有限集第二十四張,PPT共三十一頁,創(chuàng)作于2022年6月25Example 3 旅行商問題(Traveling Salesman Problem)TSP : 有一位旅行售貨員,欲到城市 v1,v2,,vn 進行商品銷售,已知: 的距離為 wij.( , ).他從其中某個城市出發(fā),需訪問每一個城市一次而回到出發(fā)的

18、城市.問應如何計劃他的旅行路線,使他所走路線的總長度最短?TSP可分為:對稱(dij = dji)和非對稱(dij dji)距離兩種第一章 組合優(yōu)化模型第二十五張,PPT共三十一頁,創(chuàng)作于2022年6月263 組合優(yōu)化模型Hamilton 回路:不含平行邊及自環(huán) 這是1856年,Hamilton 首先提出的所謂環(huán)球航行問題而得名。它的存在性遠比 Eular 回路的存在性復雜得多。最優(yōu) Hamilton 回路:在賦權圖中,權和最小的 Hamilton 回路 .過簡單圖 G 的每一個頂點一次且僅一次的回路 .第二十六張,PPT共三十一頁,創(chuàng)作于2022年6月27最優(yōu)旅行商問題與最優(yōu) Hamilton 回路一樣嗎? 如果不滿足三角不等式,則可通過求最短路方法,構造新圖,使之滿足三角不等式 . 所以以下僅討論最優(yōu)的 Hamilton 回路 . 2 5 2 3Theorem 如果賦權圖滿足三角不等式(歐氏距離),則它的最優(yōu)旅行商回路與最優(yōu) Hamilton 回路相同 (Hamilton 回路存在時).第一章 組合優(yōu)化模型第二十七張,PPT共三十一頁,創(chuàng)作于2022年6月283 組合優(yōu)化模型TSP 問題的數學模型(非對稱的):v6v4v5v3v2v1Note:條件(1),(2)表示每個城市經過一次,但不能保證它可行. 要求局部不構成圈,條件(3)就是為了約束這一點

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論