第一章初等模型

1、數(shù)學(xué)建模簡明教程數(shù)學(xué)建模簡明教程楊尚俊楊尚俊 編著編著安徽大學(xué)出版社出版安徽大學(xué)出版社出版 20062006年年引引 言言0.1 0.1 數(shù)學(xué)的重要性數(shù)學(xué)的重要性0.2 0.2 本書主要內(nèi)容本書主要內(nèi)容0.3 0.3 本課程主要特點(diǎn)本課程主要特點(diǎn)0.1 0.1 數(shù)學(xué)的重要性數(shù)學(xué)的重要性n新世紀(jì)國家間的競爭主要是經(jīng)濟(jì)競爭新世紀(jì)國家間的競爭主要是經(jīng)濟(jì)競爭, ,是人是人才的競爭才的競爭; ;人才培養(yǎng)的關(guān)鍵是素質(zhì)教育人才培養(yǎng)的關(guān)鍵是素質(zhì)教育, ,數(shù)數(shù)學(xué)教育在素質(zhì)教育中占據(jù)重要地位學(xué)教育在素質(zhì)教育中占據(jù)重要地位. .n當(dāng)今社會(huì)正日益數(shù)學(xué)化當(dāng)今社會(huì)正日益數(shù)學(xué)化, ,數(shù)學(xué)是高科技的基數(shù)學(xué)是高科技的基礎(chǔ)礎(chǔ).

2、.n數(shù)學(xué)在工程技術(shù)以及國民生產(chǎn)中發(fā)揮愈來數(shù)學(xué)在工程技術(shù)以及國民生產(chǎn)中發(fā)揮愈來愈重要的作用甚至是決定性的作用愈重要的作用甚至是決定性的作用. .素質(zhì)教育的重要性素質(zhì)教育的重要性n素質(zhì)教育既是素質(zhì)教育既是“科教興國科教興國”戰(zhàn)略的必然選擇戰(zhàn)略的必然選擇, ,也也是教育自身進(jìn)一步發(fā)展的客觀需要是教育自身進(jìn)一步發(fā)展的客觀需要, ,更是高校發(fā)更是高校發(fā)展的靈魂和動(dòng)力展的靈魂和動(dòng)力. .n理工科的特征往往體現(xiàn)在嚴(yán)謹(jǐn)理工科的特征往往體現(xiàn)在嚴(yán)謹(jǐn), ,規(guī)范的教育體系規(guī)范的教育體系上上, ,而綜合性大學(xué)更重要的是強(qiáng)調(diào)個(gè)性化教育而綜合性大學(xué)更重要的是強(qiáng)調(diào)個(gè)性化教育. .能充分挖掘每個(gè)學(xué)生的潛力的個(gè)性化教育往往能充分

3、挖掘每個(gè)學(xué)生的潛力的個(gè)性化教育往往是一所綜合性大學(xué)的重要特征和體現(xiàn)是一所綜合性大學(xué)的重要特征和體現(xiàn), ,而數(shù)學(xué)建而數(shù)學(xué)建模的教育及實(shí)踐正符合這方面的要求模的教育及實(shí)踐正符合這方面的要求. . 數(shù)學(xué)是高科技的基礎(chǔ)數(shù)學(xué)是高科技的基礎(chǔ)n社會(huì)進(jìn)步依賴于科學(xué)的創(chuàng)新而數(shù)學(xué)對于科學(xué)的發(fā)展社會(huì)進(jìn)步依賴于科學(xué)的創(chuàng)新而數(shù)學(xué)對于科學(xué)的發(fā)展則具有根本的意義則具有根本的意義. .在今天在今天, ,數(shù)學(xué)已成為高科技的基數(shù)學(xué)已成為高科技的基礎(chǔ)礎(chǔ), ,并且在一定意義上并且在一定意義上, ,可以說是現(xiàn)代文明的標(biāo)志可以說是現(xiàn)代文明的標(biāo)志 (2002(2002年北京國際數(shù)學(xué)家大會(huì)東道國歡迎詞摘錄年北京國際數(shù)學(xué)家大會(huì)東道國歡迎詞摘錄

4、).).n各行各業(yè)日益依賴于數(shù)學(xué)各行各業(yè)日益依賴于數(shù)學(xué), ,可以說可以說, ,當(dāng)今社會(huì)正日益當(dāng)今社會(huì)正日益數(shù)學(xué)化數(shù)學(xué)化. .數(shù)學(xué)正在向一切領(lǐng)域滲透數(shù)學(xué)正在向一切領(lǐng)域滲透, ,數(shù)學(xué)正在不停地?cái)?shù)學(xué)正在不停地與別的學(xué)科結(jié)合產(chǎn)生活躍的新興學(xué)科與別的學(xué)科結(jié)合產(chǎn)生活躍的新興學(xué)科.”.”高科技本高科技本質(zhì)上是一種數(shù)學(xué)技術(shù)質(zhì)上是一種數(shù)學(xué)技術(shù)”的觀點(diǎn)正在被越來越多的人的觀點(diǎn)正在被越來越多的人接受接受. . 20022002年年8 8月在中國首都北京舉行國際數(shù)學(xué)月在中國首都北京舉行國際數(shù)學(xué)家家20022002年大會(huì)年大會(huì), ,這是該國際最高級(jí)數(shù)學(xué)學(xué)術(shù)會(huì)這是該國際最高級(jí)數(shù)學(xué)學(xué)術(shù)會(huì)議第一次在一個(gè)發(fā)展中國家舉行議第一次

5、在一個(gè)發(fā)展中國家舉行. .我國政府非我國政府非常重視和支持這次會(huì)議常重視和支持這次會(huì)議, ,最高領(lǐng)導(dǎo)人出席了會(huì)最高領(lǐng)導(dǎo)人出席了會(huì)議開幕式議開幕式, ,并為得獎(jiǎng)?wù)呤讵?jiǎng)并為得獎(jiǎng)?wù)呤讵?jiǎng). .這是李嵐清副總這是李嵐清副總理在致大會(huì)歡迎詞中的一段話理在致大會(huì)歡迎詞中的一段話. . 數(shù)學(xué)在生產(chǎn)中起重要作用的例子數(shù)學(xué)在生產(chǎn)中起重要作用的例子n曾經(jīng)有一家電器公司生產(chǎn)中出現(xiàn)成品率只曾經(jīng)有一家電器公司生產(chǎn)中出現(xiàn)成品率只有有84%,84%,并僅有并僅有50%50%的發(fā)貨日期可以兌現(xiàn)所造的發(fā)貨日期可以兌現(xiàn)所造成的嚴(yán)重虧損問題成的嚴(yán)重虧損問題. . 他們應(yīng)用統(tǒng)計(jì)質(zhì)量控他們應(yīng)用統(tǒng)計(jì)質(zhì)量控制在很短時(shí)間就成功地發(fā)現(xiàn)和解決了問

6、題制在很短時(shí)間就成功地發(fā)現(xiàn)和解決了問題, ,使成品率穩(wěn)定在使成品率穩(wěn)定在95%95%以上以上, ,按期發(fā)貨率也達(dá)按期發(fā)貨率也達(dá)到到95%,95%,當(dāng)年就實(shí)現(xiàn)扭虧增盈當(dāng)年就實(shí)現(xiàn)扭虧增盈12001200萬美元萬美元. .n這個(gè)故事告訴我們這個(gè)故事告訴我們: :數(shù)學(xué)可以在國民生產(chǎn)中數(shù)學(xué)可以在國民生產(chǎn)中發(fā)揮重要作用發(fā)揮重要作用, ,甚至決定性作用甚至決定性作用. .Mathematical Science,Technology,Economic Compitive- Mathematical Science,Technology,Economic Compitive- ness,Nationalnes

7、s,National Academy Press, Washington D.C.1991. Academy Press, Washington D.C.1991.該公司最先發(fā)現(xiàn)出現(xiàn)電器元件的各種性能波動(dòng)太大該公司最先發(fā)現(xiàn)出現(xiàn)電器元件的各種性能波動(dòng)太大. .他們首先用數(shù)學(xué)技術(shù)找出產(chǎn)生元件性能波動(dòng)的原因他們首先用數(shù)學(xué)技術(shù)找出產(chǎn)生元件性能波動(dòng)的原因是在自動(dòng)控制的酸洗工序中確定酸洗液是在自動(dòng)控制的酸洗工序中確定酸洗液PHPH值的機(jī)制值的機(jī)制有問題有問題, ,產(chǎn)生校正過度產(chǎn)生校正過度. .他們再用數(shù)學(xué)技術(shù)他們再用數(shù)學(xué)技術(shù)( (優(yōu)選法優(yōu)選法) )重新校正減少了起伏重新校正減少了起伏, ,從而解決了這個(gè)大

8、問題從而解決了這個(gè)大問題. .這份這份報(bào)告提出的如下結(jié)論也頗有啟發(fā)性報(bào)告提出的如下結(jié)論也頗有啟發(fā)性:“:“在經(jīng)濟(jì)競爭在經(jīng)濟(jì)競爭中數(shù)學(xué)科學(xué)是必不可少的中數(shù)學(xué)科學(xué)是必不可少的. .數(shù)學(xué)科學(xué)是一種關(guān)鍵性數(shù)學(xué)科學(xué)是一種關(guān)鍵性的的, ,能夠?qū)嵭械募夹g(shù)能夠?qū)嵭械募夹g(shù).”.” 這個(gè)例子取自這個(gè)例子取自GlimmGlimm教授主持編撰的代表教授主持編撰的代表美國數(shù)學(xué)科學(xué)委員會(huì)給美國政府的公開報(bào)告美國數(shù)學(xué)科學(xué)委員會(huì)給美國政府的公開報(bào)告: :0.2 0.2 本課程的主要內(nèi)容本課程的主要內(nèi)容n初等方法建模初等方法建模n微分方程方法建模微分方程方法建模n層次分析方法建模層次分析方法建模n矩陣分析方法建模矩陣分析方法建

9、模n數(shù)學(xué)規(guī)劃方法建模數(shù)學(xué)規(guī)劃方法建模n依靠智力巧妙建模依靠智力巧妙建模n大學(xué)生數(shù)學(xué)建模競賽和大學(xué)生數(shù)學(xué)建模競賽和MatlabMatlab編程及應(yīng)用編程及應(yīng)用0.3 0.3 本課程的特點(diǎn)本課程的特點(diǎn)n以討論具體實(shí)際問題為主要線索以討論具體實(shí)際問題為主要線索. .n以講授數(shù)學(xué)建模的思路與方法為主要目的以講授數(shù)學(xué)建模的思路與方法為主要目的. .n強(qiáng)調(diào)啟發(fā)思路和分析、解決問題的技巧強(qiáng)調(diào)啟發(fā)思路和分析、解決問題的技巧. . n按求解所討論的具體數(shù)學(xué)模型的需要介紹按求解所討論的具體數(shù)學(xué)模型的需要介紹有關(guān)數(shù)學(xué)背景知識(shí)和基本方法有關(guān)數(shù)學(xué)背景知識(shí)和基本方法, ,即實(shí)際問題即實(shí)際問題需要什么介紹什么需要什么介紹什

10、么, ,不強(qiáng)求數(shù)學(xué)方面的系統(tǒng)不強(qiáng)求數(shù)學(xué)方面的系統(tǒng)性與完整性性與完整性. .第第1 1章章 初等模型初等模型 1.1 1.1 例子與定義例子與定義 1.2 1.2 其它初等模型其它初等模型1.1 1.1 例子與定義例子與定義例例1 1 航行問題航行問題: :已知已知: :沿長江在相距沿長江在相距750km750km的兩個(gè)碼頭的兩個(gè)碼頭A A與與B B之間之間, ,順順?biāo)叫袝r(shí)間是水航行時(shí)間是 30hr;30hr;逆水航行時(shí)間是逆水航行時(shí)間是50hr.50hr.試分別求出船和水的平均速度試分別求出船和水的平均速度. .AB解解: :令船和水的平均速度分別是令船和水的平均速度分別是x x和和y,y,

11、由題意得二由題意得二元方程組元方程組: :求解此方程組得求解此方程組得 x=20, y=5.x=20, y=5.答案答案: :船和水的平均速度分別是船和水的平均速度分別是20km/hr20km/hr和和5km/hr.5km/hr.5075030750yxyx必要的簡化與說明必要的簡化與說明 這里這里, ,只考慮平均速度是基本的簡化只考慮平均速度是基本的簡化, ,因因?yàn)榇退乃俣仁请S時(shí)間為船和水的速度是隨時(shí)間, ,地點(diǎn)而變化的地點(diǎn)而變化的. .嚴(yán)嚴(yán)格講格講, ,已知的順?biāo)阎捻標(biāo)? ,逆水航行時(shí)間是船在該河逆水航行時(shí)間是船在該河段上常年航行的平均時(shí)間段上常年航行的平均時(shí)間; ;而要求的船和水

12、而要求的船和水的平均速度也應(yīng)是該船和水在該河段上常年的平均速度也應(yīng)是該船和水在該河段上常年航行的平均速度航行的平均速度. . 若把實(shí)際問題看作原型的話若把實(shí)際問題看作原型的話, ,則數(shù)學(xué)模型是將原則數(shù)學(xué)模型是將原型經(jīng)過簡化提煉而構(gòu)成的替代物型經(jīng)過簡化提煉而構(gòu)成的替代物. .這里值得注意的這里值得注意的是是: :簡化是構(gòu)作數(shù)學(xué)模型的必要前提簡化是構(gòu)作數(shù)學(xué)模型的必要前提. . 解決本問題也需要速度等相關(guān)的物理概念解決本問題也需要速度等相關(guān)的物理概念. . 解決本問題的步驟解決本問題的步驟: :按照題意設(shè)定未知量并按照題意設(shè)定未知量并決定未知量滿足的數(shù)學(xué)公式?jīng)Q定未知量滿足的數(shù)學(xué)公式; ;求出這個(gè)方程

13、求出這個(gè)方程組的解組的解; ;并在討論解的存在性與唯一性之后并在討論解的存在性與唯一性之后確定該解就是原問題所需要的解確定該解就是原問題所需要的解. . 別忘了驗(yàn)證解的正確性別忘了驗(yàn)證解的正確性. .什么是數(shù)學(xué)模型什么是數(shù)學(xué)模型? ?n如果要下一個(gè)定義的話如果要下一個(gè)定義的話, ,可以說可以說: :數(shù)學(xué)模型數(shù)學(xué)模型是對是對一個(gè)實(shí)際問題一個(gè)實(shí)際問題, ,按照其內(nèi)在規(guī)律作出一些必要按照其內(nèi)在規(guī)律作出一些必要的假設(shè)的假設(shè)( (目的為了簡化和去掉不確定的因素使目的為了簡化和去掉不確定的因素使之能歸結(jié)為一個(gè)確定的數(shù)學(xué)問題之能歸結(jié)為一個(gè)確定的數(shù)學(xué)問題) )并應(yīng)用適當(dāng)并應(yīng)用適當(dāng)數(shù)學(xué)工具導(dǎo)出的一個(gè)數(shù)學(xué)結(jié)構(gòu)數(shù)學(xué)

14、工具導(dǎo)出的一個(gè)數(shù)學(xué)結(jié)構(gòu). .借助數(shù)學(xué)的分借助數(shù)學(xué)的分析與計(jì)算全面探討并求出所得數(shù)學(xué)模型的解析與計(jì)算全面探討并求出所得數(shù)學(xué)模型的解, ,再利用有關(guān)的背景知識(shí)可以成功地將所得數(shù)學(xué)再利用有關(guān)的背景知識(shí)可以成功地將所得數(shù)學(xué)解用來解釋和回答原先的實(shí)際問題解用來解釋和回答原先的實(shí)際問題. .這一整個(gè)這一整個(gè)過程稱為數(shù)學(xué)建模過程稱為數(shù)學(xué)建模. .可用下面的圖表直觀地表可用下面的圖表直觀地表示數(shù)學(xué)建模過程的各階段及其聯(lián)系示數(shù)學(xué)建模過程的各階段及其聯(lián)系. .實(shí)際問題實(shí)際問題抽象抽象, ,簡化簡化, ,假設(shè)假設(shè), ,確定變量與參數(shù)確定變量與參數(shù)建立數(shù)學(xué)模型并求解建立數(shù)學(xué)模型并求解, ,確定參數(shù)確定參數(shù)交付使用從而

15、產(chǎn)生經(jīng)濟(jì)交付使用從而產(chǎn)生經(jīng)濟(jì), ,社會(huì)效益社會(huì)效益用實(shí)際背景或數(shù)據(jù)等來檢驗(yàn)數(shù)學(xué)模型用實(shí)際背景或數(shù)據(jù)等來檢驗(yàn)數(shù)學(xué)模型若不符合實(shí)際若不符合實(shí)際若符合實(shí)際若符合實(shí)際例例2 2 氣象預(yù)報(bào)問題氣象預(yù)報(bào)問題氣象觀測與氣象觀測與氣象預(yù)報(bào)氣象預(yù)報(bào)偏微分方程組的初偏微分方程組的初值邊值混合問題值邊值混合問題求出數(shù)值解確定求出數(shù)值解確定有關(guān)參數(shù)有關(guān)參數(shù)作作24hr,48hr24hr,48hr和和72hr72hr預(yù)報(bào)預(yù)報(bào)簡化簡化, ,歸納歸納使用巨型使用巨型計(jì)算機(jī)計(jì)算機(jī)用數(shù)值結(jié)果用數(shù)值結(jié)果解釋氣象解釋氣象分析偏差及其分析偏差及其產(chǎn)生原因產(chǎn)生原因 作為天氣現(xiàn)象的數(shù)學(xué)模型在一百多年前就已經(jīng)作為天氣現(xiàn)象的數(shù)學(xué)模型在一百多

16、年前就已經(jīng)很成功地解決了很成功地解決了, ,它是一個(gè)特殊的二階非線性偏微分它是一個(gè)特殊的二階非線性偏微分方程組的初值方程組的初值, ,邊值混合問題邊值混合問題. .遺憾的是遺憾的是, ,這個(gè)偏微分這個(gè)偏微分方程組的混合問題很難求解方程組的混合問題很難求解, ,不要說不要說, ,精確解找不到精確解找不到, ,就是求很粗糙近似解的計(jì)算量也驚人地巨大就是求很粗糙近似解的計(jì)算量也驚人地巨大. .在現(xiàn)代在現(xiàn)代巨型電子計(jì)算機(jī)未出世以前巨型電子計(jì)算機(jī)未出世以前, ,即使通過求此混合問題即使通過求此混合問題很粗糙近似解來作短期天氣預(yù)報(bào)也是不現(xiàn)實(shí)的很粗糙近似解來作短期天氣預(yù)報(bào)也是不現(xiàn)實(shí)的, ,因?yàn)橐驗(yàn)榛粋€(gè)月甚

17、至更多時(shí)間也完成不了所需的計(jì)算化一個(gè)月甚至更多時(shí)間也完成不了所需的計(jì)算. .直到直到2020世紀(jì)世紀(jì)8080年代出現(xiàn)每秒可完成上億次運(yùn)算的巨型計(jì)算年代出現(xiàn)每秒可完成上億次運(yùn)算的巨型計(jì)算機(jī)以后機(jī)以后, , 數(shù)值天氣預(yù)報(bào)這個(gè)多年的夢想才得以實(shí)現(xiàn)數(shù)值天氣預(yù)報(bào)這個(gè)多年的夢想才得以實(shí)現(xiàn). .目前我國也研制成功每秒千億次運(yùn)算水平的巨型機(jī)目前我國也研制成功每秒千億次運(yùn)算水平的巨型機(jī), ,保證了中央氣象臺(tái)每天及時(shí)而準(zhǔn)確地發(fā)布各種天氣預(yù)保證了中央氣象臺(tái)每天及時(shí)而準(zhǔn)確地發(fā)布各種天氣預(yù)報(bào)報(bào), ,為國民生產(chǎn)及人民生活作出巨大貢獻(xiàn)為國民生產(chǎn)及人民生活作出巨大貢獻(xiàn). .實(shí)際問題與其數(shù)學(xué)模型之間的關(guān)系實(shí)際問題與其數(shù)學(xué)模型之

18、間的關(guān)系n大家知道大家知道原型原型與與模型模型之間的關(guān)系之間的關(guān)系. .若把實(shí)際問題看若把實(shí)際問題看作原型的話作原型的話, ,則數(shù)學(xué)模型是將原型經(jīng)過精致地簡化則數(shù)學(xué)模型是將原型經(jīng)過精致地簡化, ,提煉而構(gòu)成的替代物提煉而構(gòu)成的替代物. .n這里必須強(qiáng)調(diào)兩點(diǎn)這里必須強(qiáng)調(diào)兩點(diǎn): :第一第一, ,一般來說一般來說, ,原型是復(fù)雜和原型是復(fù)雜和困難的困難的, ,必須把它歸結(jié)為數(shù)學(xué)模型才能解決必須把它歸結(jié)為數(shù)學(xué)模型才能解決; ;第二第二, ,數(shù)學(xué)模型不是原型原封不動(dòng)的復(fù)制品數(shù)學(xué)模型不是原型原封不動(dòng)的復(fù)制品, ,它只是在突它只是在突出反映原型某些方面性質(zhì)的近似物出反映原型某些方面性質(zhì)的近似物. .這里難免

19、會(huì)存這里難免會(huì)存在數(shù)學(xué)模型與原型的差異甚至矛盾在數(shù)學(xué)模型與原型的差異甚至矛盾, ,沖突沖突. .但對我但對我們來講們來講, ,原型是根本的原型是根本的, ,當(dāng)二者出現(xiàn)無法解釋的矛當(dāng)二者出現(xiàn)無法解釋的矛盾時(shí)盾時(shí), ,必須修改相關(guān)的數(shù)學(xué)模型以適應(yīng)原型必須修改相關(guān)的數(shù)學(xué)模型以適應(yīng)原型. .例例3 3 安全過河問題安全過河問題問題問題: : 一位老師帶三名小學(xué)生一位老師帶三名小學(xué)生: :甲甲, ,乙和丙過河乙和丙過河. .假假設(shè)僅有一條小渡船設(shè)僅有一條小渡船, ,最多能容納二人最多能容納二人; ;并且只有老并且只有老師能劃船師能劃船. .此外此外, ,學(xué)生乙很頑皮學(xué)生乙很頑皮, ,無老師在場時(shí)他肯無老

20、師在場時(shí)他肯定要欺負(fù)甲和丙定要欺負(fù)甲和丙. . 老師應(yīng)如何安排過河方案使四老師應(yīng)如何安排過河方案使四人都到達(dá)彼岸并且不發(fā)生學(xué)生乙與學(xué)生甲人都到達(dá)彼岸并且不發(fā)生學(xué)生乙與學(xué)生甲, ,丙單獨(dú)丙單獨(dú)相處而發(fā)生打架傷人的事故相處而發(fā)生打架傷人的事故? ?甲甲乙乙丙丙師師 過河問題過河問題的解的解一種安全過河方案是一種安全過河方案是: : 師乙過去師乙過去, , 接著師回接著師回; ; 師甲去師甲去, , 接著師乙回接著師乙回; ; 師丙過去師丙過去, , 接著師回接著師回; ; 師乙過去師乙過去. . 師甲丙師甲丙乙乙?guī)熞冶麕熞冶准讕熞規(guī)熞壹妆妆麕熂滓冶麕熂滓冶麕熂滓冶麕熂滓冶?實(shí)際問題及其數(shù)學(xué)模型

21、不僅可以涉及實(shí)際問題及其數(shù)學(xué)模型不僅可以涉及數(shù)量關(guān)系數(shù)量關(guān)系, ,也可以涉及方案也可以涉及方案, ,規(guī)則規(guī)則, ,措施等措施等方面方面, ,過河問題就是一例過河問題就是一例. . n過河問題過河問題(1)(1)的答案唯一嗎的答案唯一嗎? ?n不允許重復(fù)時(shí)有幾個(gè)答案不允許重復(fù)時(shí)有幾個(gè)答案? ?n最少渡河次數(shù)是多少最少渡河次數(shù)是多少? ?n如果每人都能劃船結(jié)論又是如何如果每人都能劃船結(jié)論又是如何? ? 思考題思考題1-11-1例例4 4 安全過河問題安全過河問題問題問題：三個(gè)商人每人帶一隨從過河：三個(gè)商人每人帶一隨從過河. .假設(shè)僅有一條假設(shè)僅有一條小渡船小渡船, ,最多能容納二人最多能容納二人;

22、 ;并且因他們正處于偏并且因他們正處于偏僻地帶僻地帶, ,這幾個(gè)不安分的隨從在他們?nèi)藬?shù)超過商這幾個(gè)不安分的隨從在他們?nèi)藬?shù)超過商人人數(shù)時(shí)將圖謀不軌人人數(shù)時(shí)將圖謀不軌. .應(yīng)如何安排過河方案使六應(yīng)如何安排過河方案使六人到達(dá)彼岸之前都不發(fā)生隨從數(shù)超過商人數(shù)情人到達(dá)彼岸之前都不發(fā)生隨從數(shù)超過商人數(shù)情況而引發(fā)殺人越貨的事故況而引發(fā)殺人越貨的事故? ?從從1商商1從從2從從3商商2商商3 切莫以為數(shù)學(xué)建模問題都像例切莫以為數(shù)學(xué)建模問題都像例1,1,例例3 3那那么簡單么簡單. .不信的話不信的話, ,請你不要參看下面一張幻請你不要參看下面一張幻燈片燈片, ,試著對例試著對例4 4中的問題中的問題, ,給出

23、你的安全過給出你的安全過河方案河方案. .你能較快地寫出一個(gè)安全過河方案你能較快地寫出一個(gè)安全過河方案嗎嗎? ? 2 2從過去從過去 接著接著1 1從回來從回來; ; 2 2從過去從過去 接著接著1 1從回來從回來; ; 2 2商過去商過去 接著接著1 1商商1 1從回來從回來; ; 2 2商過去商過去 接著接著1 1從回來從回來; ; 2 2從過去從過去 接著接著1 1從回來從回來; ; 2 2從過去從過去. . 過河問題過河問題的解的解相關(guān)的數(shù)學(xué)表示與分析相關(guān)的數(shù)學(xué)表示與分析n河岸的人員狀態(tài)可用二維向量河岸的人員狀態(tài)可用二維向量(x,y)(x,y)表示表示, ,意指在意指在所考慮的時(shí)刻所考

24、慮的時(shí)刻, ,該岸有該岸有x x商人和商人和y y隨從隨從.x,y.x,y的取值范的取值范圍是圍是0,1,2,3.0,1,2,3.易見易見: :每岸共有每岸共有4 42 2=16=16種可能的人種可能的人員狀態(tài)員狀態(tài); ;兩岸人員狀態(tài)互相唯一決定兩岸人員狀態(tài)互相唯一決定, ,例如例如, ,若此岸若此岸狀態(tài)向量為狀態(tài)向量為(x,y),(x,y),則彼岸狀態(tài)向量則彼岸狀態(tài)向量為為(3-x,3-y).(3-x,3-y).n一岸的安全狀態(tài)向量一岸的安全狀態(tài)向量(x,y)(x,y)應(yīng)滿足條件應(yīng)滿足條件:x:x y y或或x=0.x=0.但當(dāng)此岸出現(xiàn)但當(dāng)此岸出現(xiàn) xy xy 時(shí)時(shí), ,彼岸狀態(tài)向量彼岸狀態(tài)

25、向量(x(x ,y,y )=(3-)=(3-x,3-y)x,3-y)將出現(xiàn)將出現(xiàn) x x yy xy 也認(rèn)為是不安全的狀態(tài)也認(rèn)為是不安全的狀態(tài). .n所以所以, ,每岸的每岸的1616種狀態(tài)中恰有種狀態(tài)中恰有1010種是安全的種是安全的, ,它它們組成的集合是們組成的集合是S=(x,y)|x=0S=(x,y)|x=0 x=3x=3x=y.x=y.n上述分析也適用于有上述分析也適用于有n n個(gè)商人及個(gè)商人及n n個(gè)隨從的情況個(gè)隨從的情況, ,其中其中,n,n為任意正整數(shù)為任意正整數(shù). .此時(shí)此時(shí), ,安全集為安全集為 S=(x,y)|x=0S=(x,y)|x=0 x=nx=nx=y.x=y.n在

26、直角坐標(biāo)系下安全集在直角坐標(biāo)系下安全集S S的點(diǎn)組成的點(diǎn)組成字形字形, ,詳見下圖詳見下圖. .xy(0,0)(3,3)(2,2)(1,1)(0,1)(0,2)(0,3)(3,0)(3,2)(3,1)此岸狀態(tài)圖此岸狀態(tài)圖圖圖 1-11-1解決安全過河問題解決安全過河問題(2)(2)的數(shù)學(xué)模型的數(shù)學(xué)模型 基于前面的分析建立解決基于前面的分析建立解決n n商商n n從安全過河問題的從安全過河問題的字形棋盤單人跳棋模型字形棋盤單人跳棋模型: :在此岸安全集在此岸安全集S S組成的組成的字形棋盤上字形棋盤上, ,經(jīng)奇數(shù)步經(jīng)奇數(shù)步從起點(diǎn)從起點(diǎn)(n,n)(n,n)跳到終點(diǎn)跳到終點(diǎn)(0,0)(0,0)為成功

27、為成功. .跳棋規(guī)則是跳棋規(guī)則是: :每步在水平或垂直方向跳每步在水平或垂直方向跳1 1或或2 2格格; ;或在或在4545 斜線方斜線方向跳向跳1 1格格. .奇數(shù)步向下向左跳奇數(shù)步向下向左跳; ;偶數(shù)步向上向右跳偶數(shù)步向上向右跳. .一個(gè)成功的跳棋過程將給出一個(gè)成功的跳棋過程將給出n n商商n n從安全過河問題的從安全過河問題的一個(gè)方案一個(gè)方案. .例如例如, ,圖圖1-11-1所示的成功跳棋過程正好對所示的成功跳棋過程正好對應(yīng)我們前面提出的那個(gè)安全過河方案應(yīng)我們前面提出的那個(gè)安全過河方案. .關(guān)于安全過河問題關(guān)于安全過河問題(2)(2)解的討論解的討論n一般來說一般來說, ,該問題只要有

28、一個(gè)解就有無窮多個(gè)解該問題只要有一個(gè)解就有無窮多個(gè)解. .因?yàn)橐驗(yàn)? :在這個(gè)解的第在這個(gè)解的第1 1步之前增加兩步步之前增加兩步:“1:“1隨從過隨從過去去, ,接著再回來接著再回來”, ,走完此兩步仍回到原狀態(tài)走完此兩步仍回到原狀態(tài). .顯然顯然, ,把這兩步作任意次循環(huán)把這兩步作任意次循環(huán), ,都將回到原狀態(tài)都將回到原狀態(tài). .所以所以, ,由由一個(gè)已知解可以構(gòu)造出無窮多個(gè)不同的解一個(gè)已知解可以構(gòu)造出無窮多個(gè)不同的解. .換句話換句話說說, ,此問題解的唯一性一般不成立此問題解的唯一性一般不成立. .n我們應(yīng)把兩個(gè)這樣的解看作同一類我們應(yīng)把兩個(gè)這樣的解看作同一類: :其中一個(gè)解除其中一個(gè)

29、解除多一個(gè)循環(huán)之外多一個(gè)循環(huán)之外, ,與另一個(gè)解完全相同與另一個(gè)解完全相同, ,這里這里, ,循環(huán)循環(huán)指的是偶數(shù)步來回過渡指的是偶數(shù)步來回過渡, ,并保持循環(huán)前和循環(huán)后兩并保持循環(huán)前和循環(huán)后兩岸狀態(tài)完全一樣岸狀態(tài)完全一樣. .今后今后, ,同一類的解中恒取那個(gè)同一類的解中恒取那個(gè)”不允許重復(fù)的解不允許重復(fù)的解”為代表為代表. .n注意注意: :即使不區(qū)別商人隨從間的置換即使不區(qū)別商人隨從間的置換, ,對于不允許對于不允許重復(fù)的解重復(fù)的解, ,解的唯一性一般地也是不成立的解的唯一性一般地也是不成立的. .例如例如, ,對于安全過河問題對于安全過河問題(2),(2),仔細(xì)觀察圖仔細(xì)觀察圖1-11-

30、1不難發(fā)現(xiàn)不難發(fā)現(xiàn): :從從(3,3)(3,3)出發(fā)出發(fā), ,經(jīng)經(jīng)“2 2從過去從過去, ,接著接著1 1從回來從回來”或或“1 1商商1 1從過去從過去, ,接著接著1 1商回來商回來”都達(dá)到同樣的狀都達(dá)到同樣的狀態(tài)態(tài):”1:”1從在彼岸從在彼岸, ,其余人員在此岸其余人員在此岸”. .因此因此, ,安全安全過河問題過河問題(2)(2)至少有兩個(gè)不允許重復(fù)的解至少有兩個(gè)不允許重復(fù)的解. .n每個(gè)不允許重復(fù)的解的渡河次數(shù)稱為最少渡河次每個(gè)不允許重復(fù)的解的渡河次數(shù)稱為最少渡河次數(shù)數(shù). .例如例如, ,對圖對圖1-11-1表示的那個(gè)不允許重復(fù)解最少表示的那個(gè)不允許重復(fù)解最少渡河次數(shù)是渡河次數(shù)是11

31、.11.你能證明你能證明:”:”對任何正整數(shù)對任何正整數(shù)n,nn,n商商n n從的安從的安全過河問題全過河問題, ,不允許重復(fù)的解一定是有限不允許重復(fù)的解一定是有限個(gè)個(gè)”嗎嗎? ?你能證明你能證明: :對對3 3商商3 3從安全過河問題從安全過河問題, ,不允許不允許重復(fù)的解個(gè)數(shù)是重復(fù)的解個(gè)數(shù)是4 4嗎嗎? ?思考題思考題1-21-2安全過河問題安全過河問題(2)(2)的各種推廣的各種推廣1. 1. 渡船容量不變渡船容量不變( (即至多容即至多容2 2人人),),僅商人僅商人, ,隨從隨從人數(shù)有所改變?nèi)藬?shù)有所改變思考題思考題1-31-3 對任意正整數(shù)對任意正整數(shù)n n 2,2,討論討論n n商

32、人和商人和n n隨從能否安全過隨從能否安全過河河, ,若能若能, ,并給出答案并給出答案. .思考題思考題1-41-4 對任意正整數(shù)對任意正整數(shù)n n 2,2,討論討論n+1n+1商人和商人和n n隨從能否安全隨從能否安全過河過河? ?若能并給出答案若能并給出答案. .2. 2. 渡船容量和商從人數(shù)都改變渡船容量和商從人數(shù)都改變思考題思考題1-51-5 假設(shè)渡船至多容假設(shè)渡船至多容3 3人人,5,5商人和商人和5 5隨從能否安全過河隨從能否安全過河? ?若能若能, ,請給出答案請給出答案. .并考慮怎樣作更一般性的推廣并考慮怎樣作更一般性的推廣? ? 思考題思考題1-61-6 假設(shè)渡船至多容假

33、設(shè)渡船至多容4 4人人, ,能否證明能否證明: :對任意正整數(shù)對任意正整數(shù)n,nn,n商人和商人和n n隨從都能安全過河隨從都能安全過河? ?給出你的答案的嚴(yán)格給出你的答案的嚴(yán)格證明證明. . 1.2 1.2 其它初等模型其它初等模型n小兔繁殖問題小兔繁殖問題n漢諾塔問題漢諾塔問題n圓內(nèi)接三角形計(jì)數(shù)問題圓內(nèi)接三角形計(jì)數(shù)問題n雙層玻璃窗保溫功效可行性分析雙層玻璃窗保溫功效可行性分析n代表席位公平分配問題代表席位公平分配問題n最優(yōu)價(jià)格制定問題最優(yōu)價(jià)格制定問題小兔繁殖問題小兔繁殖問題假設(shè)假設(shè): :一對剛出生的小兔一對剛出生的小兔( (一公一母一公一母) )被放到一被放到一個(gè)水草豐盛的孤島上個(gè)水草豐盛

34、的孤島上;2;2月齡及以上的每對月齡及以上的每對兔子每一個(gè)月恰好繁殖一對新兔兔子每一個(gè)月恰好繁殖一對新兔( (也是一也是一公一母公一母););在觀察期間沒有任何兔子死去在觀察期間沒有任何兔子死去. .問題問題: :試計(jì)算在觀察期間的第試計(jì)算在觀察期間的第n n個(gè)月島上兔子個(gè)月島上兔子總對數(shù)總對數(shù). .解解: :記第記第n n個(gè)月內(nèi)兔子總對數(shù)為個(gè)月內(nèi)兔子總對數(shù)為f fn n. .則顯然則顯然f f1 1=1;=1;因一月齡的兔不能繁殖因一月齡的兔不能繁殖, ,故故f f2 2=1.=1.當(dāng)當(dāng)n n 3 3時(shí)時(shí), ,為了計(jì)算第為了計(jì)算第n n月兔子對數(shù)月兔子對數(shù)f fn n, ,要把前一個(gè)月要把前

35、一個(gè)月的兔子對數(shù)的兔子對數(shù)f fn-1n-1加上新生兔子對數(shù)加上新生兔子對數(shù), ,而新生兔子而新生兔子對數(shù)正好等于對數(shù)正好等于f fn-2n-2( (因每對兔子一次生一對因每對兔子一次生一對).).這這就證明數(shù)列就證明數(shù)列ffn n 滿足初始條件滿足初始條件:f:f1 1=f=f2 2=1=1和遞推關(guān)和遞推關(guān)系系: : f fn n=f=fn-1n-1+f+fn-2n-2,n,n 3.3.不難依次求得數(shù)列不難依次求得數(shù)列ffn n 前若干項(xiàng)前若干項(xiàng)( (參看圖參看圖1-2)1-2)的值的值如上表所示如上表所示: :n n1 12 23 34 45 56 67 78 8f fn n1 11 12

36、 23 35 58 813132121123456考察期考察期間月數(shù)間月數(shù)圖圖 1-21-21月齡兔月齡兔2月齡兔月齡兔FibonacciFibonacci數(shù)列數(shù)列 數(shù)列數(shù)列ffn n 在理論和運(yùn)用方面都非常有用在理論和運(yùn)用方面都非常有用, ,被稱為被稱為FibonacciFibonacci數(shù)列數(shù)列. .可以方便地編程計(jì)可以方便地編程計(jì)算數(shù)列算數(shù)列ffn n,也可以證明它滿足下列封閉公也可以證明它滿足下列封閉公式式: : f fn n=(1/=(1/ 5)(u5)(un n-v-vn n),n=1,2,),n=1,2, (2.1) (2.1) 其中其中,u=(1+,u=(1+ 5)/2,v=(

37、1-5)/2,v=(1- 5)/2.5)/2.試用試用MatlabMatlab編程求編程求f fn n, ,其中其中n n為任意正整數(shù)為任意正整數(shù). .你能嚴(yán)格證明公式你能嚴(yán)格證明公式(2.1)(2.1)嗎嗎? ?思考題思考題 1-71-7漢諾塔問題漢諾塔問題: :一個(gè)著名數(shù)學(xué)游戲一個(gè)著名數(shù)學(xué)游戲游戲規(guī)則游戲規(guī)則: :今有安裝在一塊木板上的今有安裝在一塊木板上的3 3根柱子和若干根柱子和若干中心有孔的盤子中心有孔的盤子. .這些盤子的直徑兩兩不同這些盤子的直徑兩兩不同. .開始開始時(shí)時(shí), ,它們已按大小的次序套在第一根柱子上它們已按大小的次序套在第一根柱子上, ,使得使得每個(gè)盤子的下面沒有比它

38、小的盤子每個(gè)盤子的下面沒有比它小的盤子. .每一次把每一次把1 1個(gè)個(gè)盤子從一根柱子移動(dòng)到另一根柱子盤子從一根柱子移動(dòng)到另一根柱子, ,但是不允許但是不允許這個(gè)盤子放在任何比它小的盤子上面這個(gè)盤子放在任何比它小的盤子上面. .游戲的最游戲的最終目標(biāo)是把所有的盤子都放到第三根柱子上終目標(biāo)是把所有的盤子都放到第三根柱子上, ,并并保持按大小次序放置保持按大小次序放置, ,大盤子在下面大盤子在下面. .問題問題: :令令h hn n表示解表示解n n個(gè)盤子漢諾塔問題所需要的最少個(gè)盤子漢諾塔問題所需要的最少移動(dòng)次數(shù)移動(dòng)次數(shù). .試建立關(guān)于試建立關(guān)于h hn n的遞推關(guān)系并求出的遞推關(guān)系并求出h hn

39、n的封的封閉公式閉公式. .111222213333ABCD漢諾塔問題的解法漢諾塔問題的解法開始時(shí)開始時(shí)n n個(gè)盤子放在柱個(gè)盤子放在柱1.1.按照游戲規(guī)則我們可以用按照游戲規(guī)則我們可以用h hn-1n-1次移動(dòng)將上邊的次移動(dòng)將上邊的n-1n-1個(gè)盤子移到柱個(gè)盤子移到柱2.2.在這些在這些移動(dòng)中保留最大的盤子不動(dòng)移動(dòng)中保留最大的盤子不動(dòng), ,然后我們用一次移然后我們用一次移動(dòng)將最大盤子移動(dòng)到柱動(dòng)將最大盤子移動(dòng)到柱3.3.我們可以再使用我們可以再使用h hn-1n-1次次移動(dòng)將柱移動(dòng)將柱2 2上的上的n-1n-1個(gè)盤子移到柱個(gè)盤子移到柱3,3,把它們放到把它們放到最大的盤子上面最大的盤子上面( (

40、這個(gè)最大的盤子一直放在柱這個(gè)最大的盤子一直放在柱3 3的底部的底部).).容易看出容易看出, ,使用更少的次數(shù)是不可能達(dá)使用更少的次數(shù)是不可能達(dá)到目的的到目的的. .這就證明了這就證明了h hn n=2h=2hn-1n-1+1.+1.初始條件是初始條件是h h1 1=1,=1,因?yàn)橐勒找?guī)因?yàn)橐勒找?guī)則一個(gè)盤子可以經(jīng)則一個(gè)盤子可以經(jīng)1 1次移動(dòng)從柱次移動(dòng)從柱1 1移到柱移到柱3.3. h hn n=2h=2hn-1n-1+1+1 =2(2h =2(2hn-2n-2+1)+1+1)+1 =2 =22 2h hn-2n-2+2+1+2+1 =2 =22 2(2h(2hn-3n-3+1)+2+1+1)+

41、2+1 =2 =23 3h hn-3n-3+2+22 2+2+1+2+1 = = =2=2n-1n-1h h1 1+2+2n-2n-2+ + +2+1+2+1 =2 =2n-1n-1+2+2n-2 n-2 + + +2+1 +2+1 用了初始條件用了初始條件h h1 1=1=1 =2 =2n n-1-1 用了等比級(jí)數(shù)公式用了等比級(jí)數(shù)公式用迭代方法求解這個(gè)遞推關(guān)系用迭代方法求解這個(gè)遞推關(guān)系 在漢諾地方有一座塔在漢諾地方有一座塔, , 那里的僧侶們嚴(yán)格那里的僧侶們嚴(yán)格按照這個(gè)游戲規(guī)則從一個(gè)柱子到另一個(gè)柱子按照這個(gè)游戲規(guī)則從一個(gè)柱子到另一個(gè)柱子移動(dòng)移動(dòng)6464個(gè)金盤子個(gè)金盤子. . 他們一秒鐘移動(dòng)一

42、個(gè)盤子他們一秒鐘移動(dòng)一個(gè)盤子. . 據(jù)說當(dāng)他們結(jié)束游戲時(shí)世界就到了末日據(jù)說當(dāng)他們結(jié)束游戲時(shí)世界就到了末日. . 試問試問: : 這個(gè)世界在僧侶們開始移動(dòng)盤子多這個(gè)世界在僧侶們開始移動(dòng)盤子多久以后終結(jié)久以后終結(jié)? ? 答案答案: 2: 26464-1-1秒秒 50005000億年億年一個(gè)古老的傳說一個(gè)古老的傳說過圓周上等分點(diǎn)的三角形計(jì)數(shù)問題過圓周上等分點(diǎn)的三角形計(jì)數(shù)問題假設(shè)假設(shè)n(n( 2)2)為給定的正整數(shù)為給定的正整數(shù), ,并已知圓周并已知圓周上的上的n n個(gè)等分點(diǎn)個(gè)等分點(diǎn). .試計(jì)算以這些等分點(diǎn)試計(jì)算以這些等分點(diǎn)為頂點(diǎn)的一切可能的銳為頂點(diǎn)的一切可能的銳, ,直直, ,鈍角三角鈍角三角形個(gè)數(shù)

43、形個(gè)數(shù). . 下圖顯示下圖顯示n=8n=8的情形的情形. .12836547用循環(huán)數(shù)組用循環(huán)數(shù)組(i,j,k)(i,j,k)來刻畫所討論三角形的構(gòu)形來刻畫所討論三角形的構(gòu)形, ,其中其中i,j,ki,j,k分別表示該三角形按反時(shí)針方向相分別表示該三角形按反時(shí)針方向相鄰二點(diǎn)間所夾已知等分點(diǎn)的個(gè)數(shù)鄰二點(diǎn)間所夾已知等分點(diǎn)的個(gè)數(shù). .易見易見, ,經(jīng)旋轉(zhuǎn)經(jīng)旋轉(zhuǎn)后能重合的三角形構(gòu)形相等后能重合的三角形構(gòu)形相等; ;所討論三角形的所討論三角形的構(gòu)形滿足下列條件構(gòu)形滿足下列條件: : i,j,k i,j,k 0,i+j+k=n-3. (0,i+j+k=n-3. (* *) )例如例如, ,在上面例子中的銳角

44、三角形在上面例子中的銳角三角形472,472,直角三角形直角三角形156,156,鈍角三角形鈍角三角形238238可分別刻畫為可分別刻畫為 (2,2,1),(3,0,2)(2,2,1),(3,0,2)和和(0,4,1).(0,4,1).建立數(shù)學(xué)模型建立數(shù)學(xué)模型n構(gòu)形構(gòu)形(0,4,1)(0,4,1)與與(0,1,4)(0,1,4)視為不同視為不同, ,因?qū)?yīng)三角因?qū)?yīng)三角形形238238與與235235旋轉(zhuǎn)后不重合旋轉(zhuǎn)后不重合. .n設(shè)設(shè)ABCABC為有構(gòu)形為有構(gòu)形(i,j,k(i,j,k) )的三角形的三角形, ,顯然顯然, ,ABCABC為為直角直角三角形三角形 maxi,j,kmaxi,j

45、,k = =n/2-1;n/2-1;ABCABC為為銳角銳角三角形三角形 maxi,j,kmaxi,j,k n/2-1;n/2-1;ABCABC為為鈍角鈍角三角形三角形 maxi,j,kmaxi,j,k n/2-1.n/2-1.注注 記記n (i,j,k(i,j,k) )中的中的i,j,ki,j,k兩兩不同兩兩不同, ,則則(i,k,j(i,k,j) )視為與視為與 (i,j,k(i,j,k) )構(gòu)形不同的三角形構(gòu)形構(gòu)形不同的三角形構(gòu)形. .n 在具體計(jì)算直在具體計(jì)算直, ,鈍角三角形個(gè)數(shù)時(shí)鈍角三角形個(gè)數(shù)時(shí), ,只要確定一只要確定一切滿足條件切滿足條件( (* *) )的不同的不同( (非等邊非等邊) )三角形構(gòu)形三角形構(gòu)形(i,j,k)(i,j,k)的個(gè)數(shù)的個(gè)數(shù)a,a,再乘以再乘以n n即可即可. .計(jì)算銳角三角形計(jì)算銳角三角形個(gè)數(shù)時(shí)個(gè)數(shù)時(shí), ,還要計(jì)算等邊三角形還要計(jì)算等邊三角形(i=j=k)(i=j=k)構(gòu)形的個(gè)數(shù)構(gòu)形的個(gè)數(shù)b.b.則銳角三角形個(gè)數(shù)等于則銳角三角形個(gè)數(shù)等于 n(a+b/3).n(a+b/3).n=8n=8時(shí)共計(jì)有時(shí)共計(jì)有 銳角構(gòu)形一個(gè)銳角構(gòu)形一個(gè):(1,2,2);:(1,2,2); 直角構(gòu)形直角構(gòu)形3 3個(gè)個(gè):(1,1,3),(0,2,3)