數(shù)學(xué)建模方法1/12/2023建立數(shù)學(xué)模型的方法層次分析法最小二乘法差分法定性理論法優(yōu)化法變分法回歸分析法機(jī)理分析法統(tǒng)計(jì)分析法聚類(lèi)分析法主成分分析法馬爾科夫預(yù)測(cè)法系統(tǒng)分析法模糊數(shù)學(xué)法灰色系統(tǒng)法1/12/2023優(yōu)化模型優(yōu)化模型概述優(yōu)化模型舉例最優(yōu)捕食策略運(yùn)輸問(wèn)題點(diǎn)菜問(wèn)題旅行商問(wèn)題1/12/2023優(yōu)化模型西北大學(xué)數(shù)學(xué)系1/12/2023優(yōu)化模型是中國(guó)大學(xué)生建模競(jìng)賽常見(jiàn)的類(lèi)型，占很大的比重。92年以來(lái)，優(yōu)化模型有：94年A題：“逢山開(kāi)路”設(shè)計(jì)最短路徑。95年A題：“一個(gè)飛行管理問(wèn)題”，線(xiàn)性規(guī)劃和非線(xiàn)性規(guī)劃模型。96年A題：“最優(yōu)捕魚(yú)策略”，以微分方程為基礎(chǔ)的優(yōu)化模型。西北大學(xué)數(shù)學(xué)系1/12/202396年B題：“洗衣節(jié)水問(wèn)題”，以用水量為目標(biāo)函數(shù)的優(yōu)化模型。97年A題：“零件的參數(shù)設(shè)計(jì)”，隨機(jī)優(yōu)化模型。97年B題：“截?cái)嗲懈睢?，?dòng)態(tài)優(yōu)化模型。98年A題：“投資的收益和風(fēng)險(xiǎn)”，雙目標(biāo)優(yōu)化模型。98年B題：“災(zāi)情巡視的最佳路線(xiàn)”，0-1線(xiàn)性規(guī)劃模型。西北大學(xué)數(shù)學(xué)系1/12/202399年A題：“自動(dòng)化車(chē)床管理”，雙參數(shù)規(guī)劃模型。99年B題：“鉆井布局”，非線(xiàn)性混合整數(shù)規(guī)劃模型。00年B題：“鋼管訂購(gòu)和運(yùn)輸”，二次規(guī)劃模型。01年B題：“公交車(chē)調(diào)度”，雙目標(biāo)規(guī)劃模型。02年A題：“車(chē)燈線(xiàn)光源的優(yōu)化設(shè)計(jì)”，規(guī)劃模型。西北大學(xué)數(shù)學(xué)系1/12/202303年B題：“露天礦生產(chǎn)的車(chē)輛安排”，非線(xiàn)性規(guī)劃模型。04年B題：“電力市場(chǎng)的輸電阻塞管理”，雙目標(biāo)線(xiàn)性規(guī)劃模型。05年B題：“DVD在現(xiàn)租賃”，0-1規(guī)劃模型。06年A題：“出版社的資源優(yōu)化配置”，線(xiàn)性規(guī)劃模型。西北大學(xué)數(shù)學(xué)系1/12/2023（一）優(yōu)化模型的數(shù)學(xué)描述下的最大值或最小值，其中設(shè)計(jì)變量（決策變量）目標(biāo)函數(shù)將一個(gè)優(yōu)化問(wèn)題用數(shù)學(xué)式子來(lái)描述，即求函數(shù)在約束條件和可行域西北大學(xué)數(shù)學(xué)系1/12/2023“受約束于”之意西北大學(xué)數(shù)學(xué)系1/12/2023（二）優(yōu)化模型的分類(lèi)1.根據(jù)是否存在約束條件有約束問(wèn)題和無(wú)約束問(wèn)題。2.根據(jù)設(shè)計(jì)變量的性質(zhì)靜態(tài)問(wèn)題和動(dòng)態(tài)問(wèn)題。3.根據(jù)目標(biāo)函數(shù)和約束條件表達(dá)式的性質(zhì)線(xiàn)性規(guī)劃，非線(xiàn)性規(guī)劃，二次規(guī)劃，多目標(biāo)規(guī)劃等。西北大學(xué)數(shù)學(xué)系1/12/2023（1）非線(xiàn)性規(guī)劃目標(biāo)函數(shù)和約束條件中，至少有一個(gè)非線(xiàn)性函數(shù)。西北大學(xué)數(shù)學(xué)系1/12/2023（2）線(xiàn)性規(guī)劃（LP）目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量的線(xiàn)性函數(shù)。西北大學(xué)數(shù)學(xué)系1/12/2023（3）二次規(guī)劃問(wèn)題目標(biāo)函數(shù)為二次函數(shù)，約束條件為線(xiàn)性約束西北大學(xué)數(shù)學(xué)系1/12/20235.根據(jù)變量具有確定值還是隨機(jī)值

確定規(guī)劃和隨機(jī)規(guī)劃。4.根據(jù)設(shè)計(jì)變量的允許值整數(shù)規(guī)劃（0-1規(guī)劃）和實(shí)數(shù)規(guī)劃。西北大學(xué)數(shù)學(xué)系1/12/2023（三）建立優(yōu)化模型的一般步驟1.確定設(shè)計(jì)變量和目標(biāo)變量；2.確定目標(biāo)函數(shù)的表達(dá)式；3.尋找約束條件。西北大學(xué)數(shù)學(xué)系1/12/2023最優(yōu)捕食策略運(yùn)輸問(wèn)題點(diǎn)菜問(wèn)題旅行商問(wèn)題（四）線(xiàn)性規(guī)劃模型舉例西北大學(xué)數(shù)學(xué)系1/12/2023實(shí)例1最優(yōu)捕食者策略

假設(shè)存在一種捕食者，穴居A處，在B和C處有兩個(gè)食物源X、Y。捕食者從巢穴A到區(qū)域B和C帶回一單位的食物所需的時(shí)間估計(jì)為2分鐘和3分鐘。捕食者在區(qū)域B平均花2分鐘捕獲一單位食物X，而在區(qū)域C只花1分鐘就捕獲一單位食物Y。一單位X所產(chǎn)生的熱量估計(jì)為25焦耳，一單位Y所產(chǎn)生的熱量估計(jì)為30焦耳。假設(shè)捕食者每天不可超過(guò)120分鐘用于從巢穴到食物區(qū)來(lái)回行走，同時(shí)每天不可能花80分鐘以上搜尋食物。估計(jì)捕食者每天能獲得的最大熱量值是多少？西北大學(xué)數(shù)學(xué)系1/12/2023一單位實(shí)物行走時(shí)間(分鐘)捕獲時(shí)間(分鐘)熱量(焦耳)X2225Y3130

假設(shè)捕食者每天能得到x單位的食物X和y單位的食物Y，則每天獲得的熱量值為西北大學(xué)數(shù)學(xué)系1/12/2023xyo2x+y=802x+3y=12060404080P(30,20)U=25x+30yU=25*30+30*20=1350焦耳圖解法西北大學(xué)數(shù)學(xué)系1/12/2023設(shè)有某物資從m個(gè)發(fā)點(diǎn)A1,A2,…,Am輸送到n個(gè)收點(diǎn)B1,B2,…,Bn，其中每個(gè)發(fā)點(diǎn)發(fā)出量分別為每個(gè)收點(diǎn)輸入量分別為，并且滿(mǎn)足從發(fā)點(diǎn)A到收點(diǎn)B的距離（或單位運(yùn)費(fèi)）是已知的，設(shè)為。一個(gè)調(diào)運(yùn)方案主要由一組從發(fā)點(diǎn)到收點(diǎn)的輸送量來(lái)描述。問(wèn)題：尋求一個(gè)調(diào)運(yùn)方案，使總運(yùn)輸費(fèi)用達(dá)到最小。實(shí)例2運(yùn)輸問(wèn)題西北大學(xué)數(shù)學(xué)系1/12/2023B1B2….BnA1A2Ama1a2am

b1b2….bn…..…..X11X12…..X1nX21X22….X2nXm1Xm2…..Xmn收點(diǎn)發(fā)點(diǎn)西北大學(xué)數(shù)學(xué)系1/12/2023總的費(fèi)用A1的總費(fèi)用A2的總費(fèi)用西北大學(xué)數(shù)學(xué)系1/12/2023s.t.數(shù)學(xué)模型求解：?jiǎn)渭冃畏椒?。西北大學(xué)數(shù)學(xué)系1/12/2023實(shí)例3點(diǎn)菜問(wèn)題

我們?cè)诓宛^中點(diǎn)菜，需要包含某些營(yíng)養(yǎng)成份，但同時(shí)又希望總價(jià)格最低。下表是這個(gè)餐館的部分菜單，請(qǐng)你提供合理的選菜方案。序號(hào)菜單價(jià)格(元)蛋白質(zhì)淀粉維生素礦物質(zhì)1菜肉蛋卷1810112炒豬肝21.501013色拉12.500104紅燒排骨2310005咖喱土豆10.501006清湯全雞321001西北大學(xué)數(shù)學(xué)系1/12/2023建模設(shè)xi

表示點(diǎn)序號(hào)為i的菜，則目標(biāo)函數(shù)：約束條件：西北大學(xué)數(shù)學(xué)系1/12/2023求解注：0-1規(guī)劃問(wèn)題至今尚無(wú)好的算法，目前使用的算法在很大程度上依賴(lài)于窮舉法。下面用Mathematica

軟件，求得結(jié)果：Inputc={18,21.5,12.5,23.10.5,32}A={{1,0,0,1,0,1},{0,1,0,0,1,0},{1,0,1,0,0,0},{1,1,0,0,0,1}}b={1,1,1,1}result=LinearProgramming{c,A,b}z=c.result西北大學(xué)數(shù)學(xué)系1/12/2023進(jìn)一步考慮如果至少點(diǎn)四個(gè)不同的菜，結(jié)果又如何？西北大學(xué)數(shù)學(xué)系1/12/2023利用mathematica

軟件，得這顯然不是我們想要的結(jié)果。Inputc={18,21.5,12.5,23.10.5,32}A={{1,0,0,1,0,1},{0,1,0,0,1,0},{1,0,1,0,0,0},{1,1,0,0,0,1},{1,1,1,1,1,1}}b={1,1,1,1,4}result=LinearProgramming{c,A,b}z=c.result49.5西北大學(xué)數(shù)學(xué)系1/12/2023點(diǎn)菜價(jià)格（元）點(diǎn)菜價(jià)格（元）1,2,3,6844,5,3,267.54,2,1,694.54,5,3,6784,5,1,2736,5,1,2824,5,1,683.56,5,3,1734,5,3,1646,5,3,276.51,2,3,562.5利用窮舉法，得西北大學(xué)數(shù)學(xué)系1/12/2023實(shí)例4旅行商問(wèn)題(Travelling

SalemanProblem）TSP某商人由一城市出發(fā)，擬去已確定的n個(gè)城市推銷(xiāo)產(chǎn)品，最后回到出發(fā)城市。設(shè)任意兩城市間的距離都是已知的，要求找出一條每個(gè)城市都只到一次的旅行線(xiàn)路，使其總旅程最短。1/12/2023建模TSP又稱(chēng)為貨郎擔(dān)問(wèn)題。給這些城市編號(hào)。出發(fā)城市為0，擬訪(fǎng)問(wèn)城市分別為1,2,…,n問(wèn)題就轉(zhuǎn)化為：其中為城市到的距離，最小。求一個(gè)的排序使得1/12/2023TSP的數(shù)學(xué)規(guī)劃形式：表示進(jìn)入且僅進(jìn)入城j一次;表示離開(kāi)且僅離開(kāi)城i一次;保證連通性。其中表示若該旅行商在訪(fǎng)問(wèn)城i后接著訪(fǎng)問(wèn)城j，則令，否則令（P）1/12/2023定理：0-1規(guī)劃問(wèn)題(P)即為旅行商問(wèn)題。證明：將n+1個(gè)城市看作頂點(diǎn)，可以作為一個(gè)完全圖（即任意兩點(diǎn)均有邊相連圖），{1,2,…,n}的每一排序?qū)?yīng)于圖中一個(gè)由0點(diǎn)出發(fā)經(jīng)每一頂點(diǎn)一次最后回到0點(diǎn)的圖。現(xiàn)在只需證明是(P)的可行解的充分必要條件對(duì)應(yīng)的邊組成完全圖中的一個(gè)圈。1/12/2023(P)的可行解必構(gòu)成完全圖中的若干回路（由約束條件中的前兩個(gè)得知）。假設(shè)不然，設(shè)城構(gòu)成不過(guò)0的回路由第三個(gè)條件得：上式兩邊相加得，矛盾?，F(xiàn)證明這些回路必經(jīng)過(guò)0，從而只能是唯一的回路，即完全圖中的一個(gè)圈（Hamilton圈）。1/12/2023反之，對(duì)每一由城0出發(fā)過(guò)每城一次回到城0的圈均可找到一組，使得條件3成立。事實(shí)上，可如下取之?，F(xiàn)令，若城i為第k個(gè)訪(fǎng)問(wèn)的城市，則令，于是，當(dāng)時(shí)，，從而成立，證畢。1/12/2023模型求解1窮舉法的不同排序有個(gè)，當(dāng)n稍大時(shí)，很難找出最佳答案。這是個(gè)NP-完全問(wèn)題。2近似算法貪婪算法西德曾對(duì)一個(gè)有318個(gè)點(diǎn)的問(wèn)題找到了最優(yōu)方案。3利用數(shù)學(xué)軟件1/12/2023

一個(gè)送報(bào)員從送報(bào)中心出發(fā)到五個(gè)小區(qū)送報(bào)，最后要回到送報(bào)中心。送報(bào)中心到各小區(qū)的距離及各小區(qū)間的距離均已知（見(jiàn)表1），問(wèn)送報(bào)員應(yīng)按怎樣的線(xiàn)路行駛較好？（距離單位為千米）送報(bào)線(xiàn)路安排1/12/2023表1送報(bào)中心及各小區(qū)間的距離01234500745861703109142430591035105014948991407561410970起終1/12/202301234500745861703109142430591035105014948991407561410970貪婪算法送報(bào)中心及五個(gè)小區(qū)分別用0，1，2，3，4，5來(lái)記。算法的中心思想：每次尋找最小距離。起終1/12/202301234500745861703109142430591035105014948991407561410970起終2131/12/202301234500745861703109142430591035105014948991407561410970起終021433051/12/20230214330501234500745861703109142430591035105014948991407561410970起終4571/12/20230214330501234500745861703109142430591035105014948991407561410970起終4571/12/20230214330501234500745861703109142430591035105014948991407561410970起終457991/12/202301234500745861703109142430591035105014948991407561410970起終0214530439795總距離：37千米。1/12/2023應(yīng)用例子某類(lèi)工件在加工時(shí)需在一些指定的位置上鉆孔。鉆頭從初始位置出發(fā)，到各處鉆孔，最后回到初始位置，以便繼續(xù)對(duì)下一工件加工。問(wèn)應(yīng)如何安排鉆孔的次序，使鉆頭在加工過(guò)程中移動(dòng)的總距離最小。1/12/2023報(bào)童的訣竅問(wèn)題：報(bào)童每天清晨從報(bào)社購(gòu)進(jìn)報(bào)紙零售，晚上將沒(méi)有賣(mài)掉的報(bào)紙退回。設(shè)報(bào)紙每份的購(gòu)進(jìn)價(jià)為b，零售價(jià)為a，退回價(jià)為c，假設(shè)a>b>c。即報(bào)童售出一份報(bào)紙賺a-b，退回一份賠b-c。報(bào)童每天購(gòu)進(jìn)報(bào)紙?zhí)?，賣(mài)不完會(huì)賠錢(qián)；購(gòu)進(jìn)太少，不夠賣(mài)會(huì)少掙錢(qián)。試為報(bào)童籌劃一下每天購(gòu)進(jìn)報(bào)紙的數(shù)量，以獲得最大收入。1/12/20231.確定設(shè)計(jì)變量和目標(biāo)變量2.確定目標(biāo)函數(shù)的表達(dá)式每天的總收入為目標(biāo)變量每天購(gòu)進(jìn)報(bào)紙的份數(shù)為設(shè)計(jì)變量3.尋找約束條件尋找設(shè)計(jì)變量與目標(biāo)變量之間的關(guān)系設(shè)計(jì)變量所受的限制問(wèn)題分析1/12/2023若每天購(gòu)進(jìn)0份，則收入為0。若每天購(gòu)進(jìn)1份，售出，則收入為a-b。退回，則收入為–(b-c)。若每天購(gòu)進(jìn)2份，售出1份，則收入為a-b–(b-c)

。退回，則收入為–2(b-c)。售出2份，則收入為2(a-b)

。收入還與每天的需求量有關(guān)，而需求量是隨機(jī)變量則收入也是隨機(jī)變量，通常用均值，即期望表示。1/12/2023數(shù)學(xué)期望離散型隨機(jī)變量X的概率分布為則隨機(jī)變量X的數(shù)學(xué)期望值為連續(xù)型隨機(jī)變量X的概率密度函數(shù)為則隨機(jī)變量X的數(shù)學(xué)期望值為期望值反映了隨機(jī)變量取值的“平均”意義！1/12/20231設(shè)每天購(gòu)進(jìn)n份，日平均收入為G(n)3每天需求量為r的概率f(r),r=0,1,2…2售出一份賺a-b；退回一份賠b-c模型假設(shè)與符號(hào)說(shuō)明1/12/2023求n使G(n)最大每天的收入函數(shù)記為U(n)，則收入函數(shù)的期望值為建模1/12/2023將r視為連續(xù)變量模型求解1/12/2023使報(bào)童日平均收入達(dá)到最大的購(gòu)進(jìn)量應(yīng)滿(mǎn)足上式。因?yàn)?/12/2023售完的概率因?yàn)楫?dāng)購(gòu)進(jìn)份報(bào)紙時(shí)，是需求量不超過(guò)的概率是需求量超過(guò)的概率售不完的概率上式意義為：購(gòu)進(jìn)的份數(shù)之比，恰好等于賣(mài)出一份賺的錢(qián)與退回一份賠的錢(qián)之比。應(yīng)該使賣(mài)不完與賣(mài)完的概率1/12/2023根據(jù)需求量的概率密度的圖形可以確定購(gòu)進(jìn)量在圖中用分別表示曲線(xiàn)下的兩塊面積，則Onr當(dāng)報(bào)童與報(bào)社簽訂的合同使報(bào)童每份賺錢(qián)與賠錢(qián)之比越大時(shí)，報(bào)童購(gòu)進(jìn)的份數(shù)就應(yīng)該越多。結(jié)論求解的幾何意義1/12/2023注意求解技巧：連續(xù)化建模方法：從特殊到到一般歸納抽象1998年B題災(zāi)情巡視路線(xiàn)單旅行商到多旅行商1999年B題鉆井布局網(wǎng)格的平行移動(dòng)到旋轉(zhuǎn)運(yùn)動(dòng)2000年B題鋼管的訂購(gòu)與運(yùn)輸線(xiàn)形到樹(shù)形2000年C題飛越北極球形到橢球形人口模型，戰(zhàn)爭(zhēng)模型隨機(jī)變量的目標(biāo)函數(shù)：期望值航空公司的超額訂票模型1/12/2023社會(huì)熱點(diǎn)問(wèn)題

1/12/2023經(jīng)濟(jì)發(fā)展問(wèn)題1/12/2023環(huán)保問(wèn)題1/12/2023新一輪全國(guó)性房?jī)r(jià)上漲已經(jīng)開(kāi)始，土地也隨之成了搶手貨。令地產(chǎn)商為難的是，拿不到地，很可能會(huì)被淘汰出局，但多拿了地，又意味著要承擔(dān)諸多風(fēng)險(xiǎn)。

房?jī)r(jià)問(wèn)題1/12/2023股票問(wèn)題依照機(jī)構(gòu)樂(lè)觀的分析，2007年股票市場(chǎng)整體機(jī)會(huì)大于風(fēng)險(xiǎn)，但股指整體在高位運(yùn)行，市場(chǎng)預(yù)期震蕩幅度加大。1/12/2023煤礦管理問(wèn)題1/12/2023高校本科評(píng)估就是一場(chǎng)鬧劇高校

高校本科評(píng)估問(wèn)題1/12/2023中國(guó)石油價(jià)格將走向何方?

石油價(jià)格問(wèn)題1/12/2023洞庭湖鼠患問(wèn)題20億田鼠洞庭“跑馬圈地”1/12/2023某服務(wù)部一周中的每天需要不同數(shù)目的雇員：周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人。現(xiàn)規(guī)定應(yīng)聘者需連續(xù)工作五天，試確定聘用方案，即周一到周日每天聘用多少人，使在滿(mǎn)足需要的條件下聘用總?cè)藬?shù)最少。課后作業(yè)1

服務(wù)員的聘用問(wèn)題1/12/2023優(yōu)化問(wèn)題決策變量：周一到周日每天聘請(qǐng)的人數(shù)，記為目標(biāo)函數(shù)：聘用總?cè)藬?shù)約束條件：每天需要的人數(shù)，由于每人連續(xù)工作5天，所以周一的雇員應(yīng)是周四到周一聘用的，按照需要至少有50人，于是1/12/2023優(yōu)化模型1/12/2023求解模型用LINDO求解美國(guó)芝加哥大學(xué)的linusSchrage教授于1980年前后開(kāi)發(fā)的一套專(zhuān)門(mén)用于求解優(yōu)化問(wèn)題的軟件包。包括4種主要產(chǎn)品：LINDO，LINGO，LINDOAPI，Wath’sBest!LINDO：linearInteractiveandDiscreteOptimizer.交互式的線(xiàn)性和離散優(yōu)化求解器LINDGO：linearInteractiveandGeneralOptimizer.交互式的線(xiàn)性和通用優(yōu)化求解器用以求解線(xiàn)性規(guī)劃（LP）和二次規(guī)劃（QP）問(wèn)題用以求解非線(xiàn)性規(guī)劃問(wèn)題1/12/2023用LINDO求解TITLE服務(wù)員聘用問(wèn)題的LINDO模型MINx1+x2+x3+x4+x5+x6+x7SUBJECTTOMON)x1++x4+x5+x6+x7>=50TUE)x1+x2++x5+x6+x7>=50WED)x1+x2+x3++x6+x7>=50THU)x1+x2+x3+x4++x7>=50FRI)x1+x2+x3+x4+x5>=80SAT)x2+x3+x4+x5+x6>=90SUN)x3+x4+x5+x6+x7>=90ENDGIN7GeneralInteger求解模型1/12/2023結(jié)果輸出主要結(jié)果OBJECTIVEFUNCTIONVALUE1)94.00000VARIABLEVALUE

x10.000000x24.000000x340.000000x42.000000x5