組合優(yōu)化模型

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

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

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

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

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

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

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

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

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

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

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

12、，對(duì)同一問題，從不同角度、不同要求出發(fā)，甚至問題的解表示結(jié)構(gòu)不同，都可以建立不同的數(shù)學(xué)模型. 建立數(shù)學(xué)模型也沒有固定的方法、標(biāo)準(zhǔn) . 不同的實(shí)際問題，建模模式千差萬(wàn)別. 在此介紹通常的幾個(gè)步驟： 數(shù)學(xué)建模問題直接來(lái)源各領(lǐng)域?qū)嶋H，往往含糊不清（目的、條件、類型 etc.）. 首先，要對(duì)該問題進(jìn)行全面的、深入細(xì)微的調(diào)查和研究. 明確所解決問題的性質(zhì)，著手收集數(shù)據(jù) ；1、明確問題合理地、有目的地注意精度第十八張，PPT共三十一頁(yè)，創(chuàng)作于2022年6月192、合理假設(shè) 現(xiàn)實(shí)問題錯(cuò)綜復(fù)雜，涉及面非常之廣. 一個(gè)數(shù)學(xué)模型面面俱到、無(wú)所不包地反映一個(gè)現(xiàn)實(shí)是不可能的，即使可能，也因其過(guò)于復(fù)雜而很難求解，也是沒

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

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

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

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

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

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