關于組合優化模型1第一頁，共31頁幻燈片2第一章模型§1關于模型§2數學模型§3組合優化模型第二頁，共31頁幻燈片3第一章組合優化模型

模型（model）是所研究的系統、過程、事物或概念的一種表達形式.

§1關于模型一、模型的概念

模型不是研究對象本身，而是對研究對象的一種抽象，它反映現實中對象系統的主要特征，但它又高于現實，因而具有同類問題的共性.

由于研究目的的不同，對于同一個對象系統，可以建立完全不同的模型，分別反映該系統的不同側面；出于相同的研究目的，對于同一個對象系統，也可能建立不同的模型，反映不同的研究角度、考察因素和價值取向.第三頁，共31頁幻燈片4§1關于模型二、模型的本質

從系統概念上看，模型是系統中各種關系的表達形式.因此，建立模型要從狀態和過程兩個方面去尋找、把握和描述各系統要素之間的相互關系.狀態：事物在某個時刻所處的狀況或表現形態

過程：事物狀態的變化在時間上的持續和空間上的延伸

過程和狀態兩者緊密聯系、不可分割，狀態決定和影響過程，過程又決定和影響新的狀態.

狀態和過程是相對的.第四頁，共31頁幻燈片5

從認識論上看，模型是作為認識與實踐活動的中介.現實世界認識（信息）

模型實踐活動概念化用信息載體表達決策（行動方案）產品和服務模型化過程示意圖模型既是認識的表達，又是實踐活動的先導.

模型參與認識世界和改造世界的不斷的循環往復過程，既是認識不斷深化的體現，又是實踐活動不斷拓展的體現.第一章組合優化模型第五頁，共31頁幻燈片6§1關于模型

從信息論上看，模型和認識之間存在密切的反饋關系.從已知信息可以通過模型加工產生出新的信息，相關信息的積累可以從量變產生質變，形成新的概念，促使認識深化.

因此，模型的建立和完善不僅要注重對系統物質形態和能量形態的認識、把握和描述，而且也依賴于對系統相關信息不斷的采集、積累和加工，這就是用模型研究問題的現實活動.第六頁，共31頁幻燈片7三、模型的分類1、原樣模型

原樣模型是在工程開發末期建立的一種具象實體，是具有實物形態的模型.它與目的工程在結構和過程方面基本相同.

原樣模型經過試驗改進和完善后便是所要開發的目的工程.新產品的樣機、新著作的原稿…第一章組合優化模型第七頁，共31頁幻燈片8§1關于模型2、相似模型

相似模型是根據不同系統間的相似規律（包括幾何相似、邏輯相似和過程相似等）而建立的用于研究的模型.3、圖形模型

地球儀、船體放樣模型、飛機風洞實驗模擬模型等等圖形模型可以表達非常豐富的內容，主要有：①圖畫

——一種可以示形的圖形；②草圖

——一種可以示意的圖形；③框圖

——一種可以表示系統的部分之間或部分與整體之間聯系的圖形；

稱為不嚴格圖（沒有嚴格的規范）

系統分析和設計人員常常借助于這些圖形模型來開發、構建一個新系統的想象力和創造力，逐步引申出與之有關的問題和需要進一步探索的問題，使所要開發的系統變得越來越清晰、越來越具體.第八頁，共31頁幻燈片9④邏輯圖

——一種可以反映因素或對象間邏輯關系的圖形；

如：程序流程圖、控制關系圖etc.⑤工程圖

——一種可以反映物體確定的結構和順序關系的圖形；

如：建筑工程圖、鐵路站場配置圖etc.⑥圖論圖

——包括圖論所定義的無向圖G(V，E)、有向圖G(V，A)、加權有(無)向圖G(V，A(E)，w).關系

稱為嚴格圖（有嚴格確定的結構形式和規范）4、數學模型

數學模型是指運用數學符號和公式來表達、研究對象系統的結構或過程的模型.數學模型是用數學的語言、方法去近似地刻畫實際,是由數字、字母或其他數學符號組成的，描述現實對象數量規律的數學公式、圖形或算法.

是對現實對象本質屬性的抽象而又簡潔的刻畫，它或能解釋某些客觀現象，或能預測未來的發展規律，或能為控制某一現象的發展提供某種意義下的最優策略或較好策略.Goback第一章組合優化模型第九頁，共31頁幻燈片10§2數學模型Example1七橋問題

18世紀的德國有個哥尼斯堡城，在流貫全城的普雷爾河兩岸和河中兩個島之間架設了七座橋，把河的兩岸和兩島連接起來，能否有這樣一種走法，它通過每座橋一次且僅一次.該問題由Euler在1736年解決Solution:第十頁，共31頁幻燈片11ABCD

顯然，解決該問題時，兩岸和島的大小、形狀以及橋的長短曲直都無關，重要的是什么？每塊陸地間有幾座橋對問題進行數學抽象：

把兩岸和兩島都看做頂點，將連接這些頂點的橋當作邊，于是得到一無向圖.

則七橋問題就成為無向圖中是否存在通過每一邊一次且僅一次的路（即一筆畫）問題.第一章組合優化模型第十一頁，共31頁幻燈片12§2數學模型ABCDEuler

在他的論文中證明：

一個圖中存在一筆畫的充要條件是同時滿足：1、圖是連通的；2、與圖中每一頂點（可能有兩點例外）相連的邊（線度）必須是偶數條.這是關于圖論的第一篇論文

見圖可知，與四個頂點相連的邊都是奇數條，因而不可能存在通過每條邊一次且僅一次的畫法，即一筆畫不存在.故七橋問題不可能有解

.問題原型七橋問題數學模型一筆畫問題無解(一次過七座橋不可能)無解(一筆畫不可能)數學抽象邏輯推理翻譯回去有無解？這是利用數學模型分析和解決問題的一個成功范例第十二頁，共31頁幻燈片13一、數學模型的特點1、高度的抽象性

數學方法不僅要拋開事物的次要屬性，突出事物的本質屬性，而且要舍棄事物的物質和能量方面的具體內容，只考慮其數量關系和空間形式，同時還要把這些數量關系和空間形式作進一步的抽象，加以形式化和符號化，以便能夠進行邏輯推理和數值運算.

這種高度的抽象性，實質是對事物認識上的高度概括和深化，對同類問題包含更多的經驗和理解.第一章組合優化模型第十三頁，共31頁幻燈片14§2數學模型2、高度的精確性數學方法的高度精確性表現在三個方面：

一是表達各種因素、變量和它們之間的關系相當明確、清楚；二是邏輯推演和運算規則十分嚴密；三是結論非常確定.

數學方法可以處理多變量、關系復雜的問題，可在有意義的范圍內獲得令人滿意的計算精度.

特別適合于揭示事物的量的規定性，成為定量研究的有力工具.第十四頁，共31頁幻燈片153、應用的普適性

數學方法的高度抽象和精確，使之比任何一種科學方法的應用范圍都更為廣泛.

只存在尚未運用數學方法的領域而不存在不能運用數學方法的領域.

許多相同形式的數學模型可用于不同的實際問題，具有重要類比和借鑒意義.數學方法的形式化和公理化，使模型本身、計算過程和計算結果都便于交流，數學模型易變動，便于修改和改變計算關系，分析和求解問題速度快，求解成本低.數學模型缺乏直觀性、形象性和實時感第一章組合優化模型第十五頁，共31頁幻燈片16§2數學模型二、數學模型分類數學模型分類的方法很多，如：1、按所研究問題的性質分類⑴靜態模型與動態模型⑵確定型模型與隨機型模型⑶連續模型與離散模型⑷線性模型與非線性模型⑸宏觀模型與微觀模型第十六頁，共31頁幻燈片172、按模型的解的特征分類解析模型與數值模型3、按模型所用的數學方法分類初等模型、微分方程模型、差分方程模型、優化模型等4、按模型研究的實際范疇分類人口模型、生態系統模型、交通流模型、經濟模型、基因模型等5、按對實際問題了解的程度分類

白箱模型、灰箱模型、黑箱模型第一章組合優化模型第十七頁，共31頁幻燈片18§2數學模型三、數學建模的基本步驟

數學模型因問題不同而異，對同一問題，從不同角度、不同要求出發，甚至問題的解表示結構不同，都可以建立不同的數學模型.建立數學模型也沒有固定的方法、標準.不同的實際問題，建模模式千差萬別.在此介紹通常的幾個步驟：

數學建模問題直接來源各領域實際，往往含糊不清（目的、條件、類型etc.）.首先，要對該問題進行全面的、深入細微的調查和研究.明確所解決問題的性質，著手收集數據；1、明確問題合理地、有目的地注意精度第十八頁，共31頁幻燈片192、合理假設

現實問題錯綜復雜，涉及面非常之廣.一個數學模型面面俱到、無所不包地反映一個現實是不可能的，即使可能，也因其過于復雜而很難求解，也是沒有必要的.

所以，要作合理的假設.1、簡化問題2、限定適用范圍但也不能忽略實質相關的因素

作假設的依據通常是出于對問題內在規律的認識,或來自對數據或現象的分析，也可以是二者的綜合.善于辨別問題的主次，抓住主要因素，通過合理假設,使問題簡化以便進行數學描述.

假設是在模型的建立、求解和分析過程中完善.通常開始讓問題盡可能簡化第一章組合優化模型第十九頁，共31頁幻燈片20§2數學模型3、建立模型

建模時，要分清問題的類型恰當使用數學工具；抓住問題的本質簡化變量之間的關系.

用什么樣的方法建立數學模型，沒有絕對的標準；數學模型的形式可以是多種多樣，數學公式、表格、圖形、算法.

模型的優劣在于是否采用了恰當的方法，合理地描述了實際問題，而不在于是否用到了高深的數學工具.數學建模是一個過程.第二十頁，共31頁幻燈片214、模型求解

不同的模型要用到不同的數學工具求解.這就要求從事實際工作者對相應的數學分支知識有一定的了解.可借助計算機，特別是利用數學工具軟件.5、模型分析

對模型求出的解進行數學上的分析，有助于對實際問題的解決.如：①結果的誤差分析誤差是否在允許的范圍內分析誤差來源：建模假設的誤差；數據測量的誤差；近似求解方法的誤差；計算工具的舍入誤差.②

結果的統計分析結果是否符合特定的統計規律③模型對數據的靈敏度分析模型的結果是否會因數據的微小改變而發生大的變化④對假設的魯棒性分析模型的結果是否對某一假設非常依賴⑤不同模型間的對比分析robustness第一章組合優化模型第二十一頁，共31頁幻燈片22§2數學模型6、模型檢驗

將求解結果和分析結果翻譯回到實際問題之中，與實際現象、實際數據進行比較，檢驗是否與實際吻合.如果吻合較好，則模型及其結果可以應用于實際問題；如果吻合不好，則需要對模型進行修正.7、改進模型

吻合不好，問題常常出現在模型假設上.可能由于假設了過于苛刻的條件，或者忽略了一些不該忽略的因素.所以,要對實際問題中的主次因素再次分析,對模型進行修改、補充、完善.需要多次反復才能達到比較滿意的程度。第二十二頁，共31頁幻燈片238、模型應用

數學建模最終的目的是為了解決問題.一方面可以解釋以前的實踐成果；另一方面可以為現在的實際問題提供解決方案，甚至可以對一些不確定的現象或規律作出預測.現實問題簡化、假設建立模型求解模型檢驗分析模型模型應用觀察、分析收集數據確定主要因素及相互關系Goback第一章組合優化模型第二十三頁，共31頁幻燈片24§3組合優化模型Example2

某商場根據客流量統計得出一周中每天所需要的營業員數如表：營業員配置問題時間周一周二周三周四周五周六周日所需營業員數677278768510698

如果規定每個營業員每周連續工作5天，休息2天，求總人數最少的營業員排班方案.Solution:

設xj

為從周j開始連續工作5天的營業員人數，j=1,…,7(其中

x7

為周日開始連續工作5天的營業員數)，則可行解集是有限集第二十四頁，共31頁幻燈片25Example3

旅行商問題（Traveling

Salesman

Problem）TSP

:

有一位旅行售貨員，欲到城市v1，v2,…，vn

進行商品銷售，已知：的距離為

wij.(,).他從其中某個城市出發，需訪問每一個城市一次而回到出發的城市.問應如何計劃他的旅行路線，使他所走路線的總長度最短？TSP可分為：對稱（dij=dji)和非對稱（dij≠dji）距離兩種第一章組合優化模型第二十五頁，共31頁幻燈片26§3組合優化模型Hamilton

回路：不含平行邊及自環

這是1856年，Hamilton

首先提出的所謂環球航行問題而得名。它的存在性遠比Eular回路的存在性復雜得多。最優

Hamilton

回路：在賦權圖中，權和最小的

Hamilton

回路.過簡單圖G

的每一個頂點一次且僅一次的回路.第二十六頁，共31頁幻燈片27最優旅行商問題與最優Hamilton回路一樣嗎？

如果不滿足三角不等式，則可通過求最短路方法，構造新圖，使之滿足三角不等式.所以以下僅討論最優的

Hamilton

回路.2523Theorem

如果賦權圖滿足三角不等式（歐氏距離），則它的最優旅行商回路與最優Hamilton

回路相同（Hamilton回路存在時）.第一章組合優化模型第二十七頁，共31頁幻燈片28§3組合優化模型TSP

問題的數學模型（非對稱的）：v6v4v5v3v2v1Note：條件(1)，(2)表示每個城市經過一次，但不能保證它可行.

要求局部不構成圈，條件(3)就是為了約束這一點.第二十八頁，共31頁幻燈片29共同特點：可行方案是有限的

——組合優化問題

Definition1

組合優化問題