【正文】 數(shù)學(xué)建模 優(yōu)化模型介紹 引言 數(shù)學(xué)之重要 …… 數(shù)學(xué)使人周密 …… Francis Bacon 數(shù)學(xué)處于人類(lèi)智能的中心領(lǐng)域 …… 數(shù)學(xué)方 法滲透、支配著一切自然科學(xué)的理論分支 …… 它已愈來(lái)愈成為衡量成就的主要標(biāo)志。 von Neumann 引言 數(shù)學(xué)之重要 一門(mén)科學(xué)只有當(dāng)它達(dá)到能夠成功地運(yùn)用 數(shù)學(xué)時(shí)，才算真正發(fā)展了。 Karl Marx Galileo : 展現(xiàn)在我們眼前的宇宙像一本用數(shù) 學(xué)語(yǔ)言寫(xiě)成的大書(shū)，如不掌握數(shù)學(xué)符號(hào)語(yǔ)言，就像在黑暗 的迷宮里游蕩，什么也認(rèn)識(shí)不清。 數(shù)學(xué)是一種語(yǔ)言，是一切科學(xué)的共同語(yǔ)言 引言 數(shù)學(xué)之重要 數(shù)學(xué)是一種技術(shù)，是高技術(shù)的本質(zhì) 數(shù)學(xué)技術(shù) 數(shù)學(xué)方法與計(jì)算技術(shù)的結(jié)合形 成的一種關(guān)鍵性的、可實(shí)現(xiàn)的技術(shù) 二十世紀(jì)最偉大的數(shù)學(xué)家 二十世紀(jì)最偉大的物理學(xué)家 Go back 諾貝爾獎(jiǎng) 菲爾茲獎(jiǎng) 1. 什么是數(shù)學(xué)模型？ 數(shù)學(xué)模型 是對(duì)于現(xiàn)實(shí)世界的一個(gè) 特定對(duì)象 ，一個(gè)特定目的 ，根據(jù)特有的 內(nèi)在規(guī)律 ，做出一些 必要的假設(shè) ，運(yùn)用適當(dāng)?shù)?數(shù)學(xué)工具 ，得到一個(gè) 數(shù)學(xué)結(jié)構(gòu) ． 簡(jiǎn)單地說(shuō)：就是系統(tǒng)的某種特征的本質(zhì)的數(shù)學(xué)表達(dá)式（或是用數(shù)學(xué)術(shù)語(yǔ)對(duì)部分現(xiàn)實(shí)世界的描述），即用數(shù)學(xué)式子（如函數(shù)、圖形、代數(shù)方程、微分方程、積分方程、差分方程等）來(lái)描述（表述、模擬）所研究的客觀對(duì)象或系統(tǒng)在某一方面的存在規(guī)律． 2. 什么是數(shù)學(xué)建模 ? 數(shù)學(xué)建模 是利用數(shù)學(xué)方法解決實(shí)際問(wèn)題的一種實(shí)踐．即通過(guò)抽象、簡(jiǎn)化、假設(shè)、引進(jìn)變量等處理過(guò)程后，將實(shí)際問(wèn)題用數(shù)學(xué)方式表達(dá)，建立起數(shù)學(xué)模型，然后運(yùn)用先進(jìn)的數(shù)學(xué)方法及計(jì)算機(jī)技術(shù)進(jìn)行求解． 觀點(diǎn)：“所謂 高科技 就是一種 數(shù)學(xué)技術(shù) ” ? 數(shù)學(xué)建模 其實(shí)并不是什么新東西，可以說(shuō)有了數(shù)學(xué)并需要用數(shù)學(xué)去解決實(shí)際問(wèn)題，就一定要用數(shù)學(xué)的語(yǔ)言、方法去近似地刻畫(huà)該實(shí)際問(wèn)題，這種刻劃的數(shù)學(xué)表述的就是一個(gè)數(shù)學(xué)模型，其過(guò)程就是數(shù)學(xué)建模的過(guò)程．?dāng)?shù)學(xué)模型一經(jīng)提出，就要用一定的技術(shù)手段（計(jì)算、證明等）來(lái)求解并驗(yàn)證，其中大量的計(jì)算往往是必不可少的，高性能的計(jì)算機(jī)的出現(xiàn)使數(shù)學(xué)建模這一方法如虎添翼似的得到了飛速的發(fā)展，掀起一個(gè)高潮． ? 數(shù)學(xué)建模將各種知識(shí)綜合應(yīng)用于解決實(shí)際問(wèn)題中，是培養(yǎng)和提高同學(xué)們應(yīng)用所學(xué)知識(shí)分析問(wèn)題、解決問(wèn)題的能力的必備手段之一 . 數(shù)學(xué)建模參考書(shū) 1.《 數(shù)學(xué)模型 》 姜啟源、謝金星、葉俊編 高等教育出版社 2.《 數(shù)學(xué)建模方法及其應(yīng)用 》 解放軍信息工程大學(xué) 韓中庚編 高教社 3.《 數(shù)學(xué)模型與數(shù)學(xué)建模 》 劉來(lái)福、曾文藝編著 北師大出版社 4. 葉其孝等， 《 大學(xué)生數(shù)學(xué)建模競(jìng)賽輔導(dǎo)教材（一） ~（四） 》 ，湖南教育出版社 ， 《 數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn) 》 ，高等教育出版社，施普林格出版社 規(guī)劃模型的應(yīng)用極其廣泛，其作用已為越來(lái) 來(lái)越急速地滲透于工農(nóng)業(yè)生產(chǎn)、商業(yè)活動(dòng)、軍事 行為 科學(xué)研究的各個(gè)方面，為社會(huì)節(jié)省的財(cái)富、 創(chuàng)造的價(jià)值無(wú)法估量 . 特別是在數(shù)模競(jìng)賽過(guò)程中，規(guī)劃模型是最常 見(jiàn)的一類(lèi)數(shù)學(xué)模型 . 從 9206年全國(guó)大學(xué)生數(shù)模競(jìng) 越多的人所重視 . 隨著計(jì)算機(jī)的逐漸普及，它越 賽試題的解題方法統(tǒng)計(jì)結(jié)果來(lái)看，規(guī)劃模型共出 現(xiàn)了 15次，占到了 50%，也就是說(shuō)每?jī)傻栏?jìng)賽題 中就有一道涉及到利用規(guī)劃理論來(lái)分析、求解 . 優(yōu)化問(wèn)題，一般是指用“最好”的方式，使用或分配有限的資源，即勞動(dòng)力、原材料、機(jī)器、資金等，使得費(fèi)用最小或者利潤(rùn)最大。 優(yōu)化模型 min f(x) 目標(biāo)函數(shù) . x?S 約束集合，可行集 其中， S ? Rn， f :S ? R， x?S稱(chēng)（ f S )的可行解 ? 最優(yōu)解 : x*?S， 滿(mǎn)足 f (x*)≤ f (x), ? x?S。 則稱(chēng) x*為 (f S)的全局最優(yōu)解 (最優(yōu)解 ), 記 .(global optimum),簡(jiǎn)記 opt. ? 最優(yōu)值 : x*為 (f S)的最優(yōu)解 , 則稱(chēng) f * = f (x*) 為 (f S)的最優(yōu)值 (最優(yōu)目標(biāo)函數(shù)值 ) 數(shù)學(xué)規(guī)劃模型的一般形式 (f S) ? 局部最優(yōu)解 : x*?S， ? x* 的鄰域 N(x*) ，使?jié)M足 f (x*)≤ f (x), ? x ?S ? N(x*) 。 則稱(chēng) x*為 (f S)的局部最優(yōu)解 ,記 l .opt.(local optimum) ? 在上述定義中，當(dāng) x ? x* 時(shí)有嚴(yán)格不等式成立， 則分別稱(chēng) x* 為 (f S)的嚴(yán)格全局最優(yōu)解和嚴(yán)格局部最優(yōu)解 。 嚴(yán)格 l .opt . 嚴(yán)格 g .opt . l .opt . 數(shù)學(xué)規(guī)劃模型的一般形式 ? 函數(shù)形式 : f(x), gi(x) , hj(x) : Rn?R min f(x) (fgh) . gi(x) ≤ 0 , i = 1,2,…,m hj(x) = 0 , j = 1,2,…,l ? 矩陣形式 : min f(x) ， f(x) : Rn?R (fgh) . g(x) ≤ 0 , g(x) : Rn?Rm h(x) = 0 , h(x) : Rn?Rl 當(dāng) f(x), gi(x) , hj(x)均為線性函數(shù)時(shí)，稱(chēng)線性規(guī)劃；若其中有非線性函數(shù)時(shí)，稱(chēng)非線性規(guī)劃 。 優(yōu)化模型的 簡(jiǎn)單分類(lèi) ? 線性規(guī)劃 (LP) 目標(biāo)和約束均為線性函數(shù) ? 非線性規(guī)劃 (NLP) 目標(biāo)或約束中存在非線性函數(shù) ? 二次規(guī)劃 (QP) 目標(biāo)為二次函數(shù)、約束為線性 ? 整數(shù)規(guī)劃 (IP) 決策變量 (全部或部分 )為整數(shù) ? 整數(shù) 線性 規(guī)劃 (ILP)，整數(shù) 非線性 規(guī)劃 (INLP) ? 純整數(shù)規(guī)劃 (PIP), 混合整數(shù)規(guī)劃 (MIP) ? 一般整數(shù)規(guī)劃， 01（整數(shù)）規(guī)劃 njiDxljxgmixhtsxf???????, . . . ,1,0)(, . . . ,1,0)(..)(m i n連續(xù)優(yōu)化 離散優(yōu)化 數(shù)學(xué)規(guī)劃 優(yōu)化模型的簡(jiǎn)單分類(lèi)和求解難度 優(yōu)化 線性規(guī)劃 非線性規(guī)劃 二次規(guī)劃 連續(xù)優(yōu)化 整數(shù)規(guī)劃 問(wèn)題求解的難度增加 線性規(guī)劃 Linear Programming 問(wèn)題一 ： 任務(wù)分配問(wèn)題 ： 某車(chē)間有甲、乙兩臺(tái)機(jī)床，可用于加工三種工件 .假定這兩臺(tái)車(chē)床的可用臺(tái)時(shí)數(shù)分別為 800和900，三種工件的數(shù)量分別為 400、 600和 500，且已知用三種不同車(chē)床加工單位數(shù)量不同工件所需的臺(tái)時(shí)數(shù)和加工費(fèi)用如下表 .問(wèn)怎樣分配車(chē)床的加工任務(wù)，才能既滿(mǎn)足加工工件的要求，又使加工費(fèi)用最低？ 單位工件所需加工臺(tái)時(shí)數(shù) 單位工件的加工費(fèi)用 車(chē)床類(lèi) 型 工件 1 工件 2 工件 3 工件 1 工件 2 工件 3 可用臺(tái)時(shí)數(shù) 甲 0. 4 1. 1 1. 0 13 9 10 800 乙 0. 5 1. 2 1. 3 11 12 8 900 兩個(gè)引例 建立線性規(guī)劃模型的基本步驟 ： （ 1） 設(shè)出決策變量 （ 2） 確定目標(biāo)函數(shù) （ 3） 確定約束條件 找出待定的未知變量（決策變量），并用代數(shù)符號(hào)表示 找到模型的目標(biāo)或判據(jù)，寫(xiě)成決策變量的線性函數(shù)，以便求出 其最大值或最小值 找出問(wèn)題的所有的限制或約束，寫(xiě)出未知變量的線性方程或 線性不等式 解 設(shè)在甲車(chē)床上加工工件 3的數(shù)量分別為 x x x3，在乙車(chē)床上加工工件 3的數(shù)量分別為 x x x6,可建立以下線性規(guī)劃模型： 654321 8121110913m i n xxxxxxz ?????? 1425361 2 34 5 6x 40 0600500. 0. 4 1. 1 80 00. 5 1. 2 1. 3 90 00 , 1 , 2 , , 6ixxxxxx x xx x xxi???????? ????? ? ???? ? ?????? 解答 問(wèn)題二： 某廠每日 8小時(shí)的產(chǎn)量不低于 1800件 .為了進(jìn)行質(zhì)量控制，計(jì)劃聘請(qǐng)兩種不同水平的檢驗(yàn)員 .一級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度 25件 /小時(shí)，正確率 98%，計(jì)時(shí)工資 4元 /小時(shí)；二級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度 15件 /小時(shí)，正確率 95%，計(jì)時(shí)工資 3元 /小時(shí) .檢驗(yàn)員每錯(cuò)檢一次，工廠要損失 2元 .為使總檢驗(yàn)費(fèi)用最省，該工廠應(yīng)聘一級(jí)、二級(jí)檢驗(yàn)員各幾名？ 解 設(shè)需要一級(jí)和二級(jí)檢驗(yàn)員的人數(shù)分別為 x x2人 , 則應(yīng)付檢驗(yàn)員的工資為： 2121 24323848 xxxx ???????因檢驗(yàn)員錯(cuò)檢而造成的損失為 ： 2121 1282)%5158%2258( xxxx ??????????故目標(biāo)函數(shù)為： 212121 3640)128()2432(m i n xxxxxxz ??????約束條件為： ?????????????????????0,01 8 0 01581 8 0 02581 8 0 0158258212121xxxxxx線性規(guī)劃模型： 21 3640m in xxz ??1212125 3 4 59s. t. 150 , 0xxxxxx?????????? ??? 解答 返 回 –模型特點(diǎn)：目標(biāo)函數(shù) (Objective function) –與約束條件 (Constraint)均為線性的； –目標(biāo)函數(shù)實(shí)現(xiàn)極大化或極小化。 線性規(guī)劃問(wèn)題的一般形式： Max(Min)S=c1x1+c2x2+… ..+xn . a11x1+a12x2+… .+a1nxn ?(=, ?)b1 a21x1+a22x2+… .+a2nxn ?(=, ?)b2 ………………… . am1x1+am2x2+… .+amnxn ?(=, ?)bm x1,x2… .xn ? 0 ?m i n().????? (m ax ) u c xA x bv l b x v u b矩 陣 形 式 ：線性規(guī)劃的 基本概念 (Feasible Solution)——任一滿(mǎn)足約束條件的 一組決策變量的數(shù)值 . (Feasible Region)——所有可行解組成的集合， 也稱(chēng)為可行解集 . 3. 目標(biāo)函數(shù)等值線 (Objective function line)—— 為于同一直線上的點(diǎn)，具有相同的目標(biāo)函數(shù)值 . 線性規(guī)劃模型的解的幾種情況 線性規(guī)劃問(wèn)題 有可行解 (Feasible) 無(wú) 可 行 解（ Infeasible） 有最優(yōu)解 （ Optimal） 無(wú) 最 優(yōu) 解(Unbounded) 數(shù)學(xué)建模中線性規(guī)劃模型的常用解法 線性規(guī)劃問(wèn)題的求解在理在理論上有單純型法，在實(shí)際建模中常用以下解法： 4. MATLAB 軟件包 主要介紹線性規(guī)劃模型的 MATlAB軟件包和 LINGO軟件包解法 模型求解方法 1. 圖解法 例 1 max z=50x1+100x2 x1 + x2≤300 2x1 + x2≤400 x2≤250 x x2≥0 該問(wèn)題的最優(yōu)解為 x1=50； x2=250 x2 z*=50x1+100x2=27500 x1 + x2≤300 x1 x2≤250 2x1 + x2≤400 z1=50x1+100x2=0 B O