【正文】 學(xué)模型，二分用途是十分有用的，許多問(wèn)題可以用它來(lái)刻劃。 } flow += aug。 v v } } if(pre[t] = 0) { break。 v++) { if((c[u][v] 0) amp。 for(v = 0。 while(true) { memset(pre, 1, sizeof(pre))。long int c[128][128]。最小費(fèi)用流(或最小費(fèi)用最大流)問(wèn)題 ，可以交替使用求解最大流和最短路兩種方法，通過(guò)迭代得到解決。例如在交通運(yùn)輸問(wèn)題中，往往要求在完成運(yùn)輸任務(wù)的前提下，尋求一個(gè)使總運(yùn)輸費(fèi)用最省的運(yùn)輸方案，這就是最小費(fèi)用流問(wèn)題。 最大流理論是由福特和富爾克森于 1956 年創(chuàng)立的 ，他們指出最大流的流值等于最小割(截集)的容量這個(gè)重要的事實(shí)，并根據(jù)這一原理設(shè)計(jì)了用標(biāo)號(hào)法求最大流的方法，后來(lái)又有人加以改進(jìn)，使得求解最大流的方法更加豐富和完善 。1956年，. 福特和 . 富爾克森等人給出了解決這類(lèi)問(wèn)題的算法，從而建立了網(wǎng)絡(luò)流理論。 if length(index)=2 index=index(1)。 temp=tb(tmpb(1))。temp=1。index1=1。a(6,:)=zeros(1,6)。a(2,:)=[zeros(1,2),15,20,M,25]。求第一個(gè)城市到其它城市的最短路徑的Matlab程序如下：clear。/* 求1到N的最短路,dis[i] 表示第i個(gè)點(diǎn)到第一個(gè)點(diǎn)的最短路 By Ping*/還有其他算法：FloydWarshall算法 BellmanFord算法 Johnson算法實(shí)例：某公司在六個(gè)城市中有分公司，從到的直接航程票價(jià)記在下述矩陣的位置上。j=n。 tmin dis[j] ){ tmin = dis[j]。j=n。 for(int i=1。 Dijkstra 程序： void Dijkstra(){ for(int i=1。如果是更新它。 注意單獨(dú)一條邊的路徑也不一定是最佳路徑。全局最短路徑問(wèn)題求圖中所有的最短路徑。最短路問(wèn)題是網(wǎng)絡(luò)理論解決的典型問(wèn)題之一，可用來(lái)解決管路鋪設(shè)、線(xiàn)路安裝、廠區(qū)布局和設(shè)備更新等實(shí)際問(wèn)題。若，（這里表示集合中的元素個(gè)數(shù)），中無(wú)相鄰頂點(diǎn)對(duì)，中亦然，則稱(chēng)為二分圖(bipartite graph)；特別地，若，則，則稱(chēng)為完全二分圖，記成。這個(gè)圖稱(chēng)為的基礎(chǔ)圖。其中稱(chēng)為圖的頂點(diǎn)集或節(jié)點(diǎn)集， 中的每一個(gè)元素稱(chēng)為該圖的一個(gè)頂點(diǎn)或節(jié)點(diǎn)；稱(chēng)為圖的弧集（arc set），中的每一個(gè)元素(即中某兩個(gè)元素的有序?qū)?當(dāng)邊時(shí)，稱(chēng)為邊的端點(diǎn)，并稱(chēng)與相鄰（adjacent）；邊稱(chēng)為與頂點(diǎn)關(guān)聯(lián)（incident）。算法重要的算法 求有向圖的強(qiáng)連通分支 (Strongerst Connected Component)（1）Kosaraju算法（2）Gabow算法（3）Tarjan算法求最小生成樹(shù) (Minimal Spanning Trees)（1）Kruskal算法(2)Prim算法最小樹(shù)形圖（1）朱永津劉振宏算法最短路徑問(wèn)題（1）SSSP(Singlesource Shortest Paths)①Dijkstra算法②BellmanFord算法(SPFA算法)（2）APSP(Allpairs Shortest Paths)①FloydWarshall算法②Johnson算法網(wǎng)絡(luò)流問(wèn)題（1）最大網(wǎng)絡(luò)流①增廣路算法⒈FordFulkerson算法⒉EdmondsKarp算法⒊最短路徑增殖EK2（MPLA）⒋Dinic②預(yù)流推進(jìn)算法（2）最小費(fèi)用流圖匹配問(wèn)題（1）匈牙利算法（2）Hopcroft Karp算法（3）KuhnMunkres算法（4）Edmonds39。 在一般情況下，圖中的相對(duì)位置如何，點(diǎn)與點(diǎn)之間線(xiàn)的長(zhǎng)短曲直，對(duì)于反映研究對(duì)象之間的關(guān)系，顯的并不重要。此外還有萊姆基法、畢爾法、凱勒法等。通常通過(guò)解其庫(kù)恩—塔克條件（KT條件）,獲取一個(gè)KT條件的解稱(chēng)為KT對(duì)，其中與原問(wèn)題的變量對(duì)應(yīng)的部分稱(chēng)為KT點(diǎn)。目前比較成功又流行的方法是分枝定界法和割平面法，它們都是在上述框架下形成的。解整數(shù)規(guī)劃最典型的做法是逐步生成一個(gè)相關(guān)的問(wèn)題，稱(chēng)它是原問(wèn)題的衍生問(wèn)題。例如，背袋（或裝載）問(wèn)題、固定費(fèi)用問(wèn)題、和睦探險(xiǎn)隊(duì)問(wèn)題（組合學(xué)的對(duì)集問(wèn)題）、有效探險(xiǎn)隊(duì)問(wèn)題（組合學(xué)的覆蓋問(wèn)題）、旅行推銷(xiāo)員問(wèn)題, 車(chē)輛路徑問(wèn)題等。不同于線(xiàn)性規(guī)劃問(wèn)題，整數(shù)和01規(guī)劃問(wèn)題至今尚未找到一般的多項(xiàng)式解法。為了滿(mǎn)足整數(shù)的要求，初看起來(lái)似乎只要把已得的非整數(shù)解舍入化整就可以了。（2）整數(shù)規(guī)劃一類(lèi)要求問(wèn)題的解中的全部或一部分變量為整數(shù)的數(shù)學(xué)規(guī)劃。x2=0。3*x1+2*x2=18。實(shí)例生產(chǎn)計(jì)劃問(wèn)題問(wèn)題：某企業(yè)要在計(jì)劃期內(nèi)安排生產(chǎn)甲、乙兩種產(chǎn)品，這個(gè)企業(yè)現(xiàn)有的生產(chǎn)資料是：設(shè)備18臺(tái)時(shí)，原材料A ：4噸，原材料 B： 12噸；已知單位產(chǎn)品所需消耗生產(chǎn)資料及利潤(rùn)如下表。決策變量的一組值表示一種方案，同時(shí)決策變量一般是非負(fù)的。滿(mǎn)足線(xiàn)性約束條件的解叫做可行解，由所有可行解組成的集合叫做可行域。滿(mǎn)足這種要求的插值多項(xiàng)式就是埃爾米特插值多項(xiàng)式 三角函數(shù)插值當(dāng)被插函數(shù)是以2π為周期的函數(shù)時(shí)，通常用n階三角多項(xiàng)式作為插值函數(shù)，并通過(guò)高斯三角插值表出。差商可列表計(jì)算：xi yi 一階差商 二階差商 三階差商 四階差商 x0 f (x0)x1 f (x1) f [x0, x1]x2 f (x2) f [x1, x2] f [x0, x1, x2]x3 f (x3) f [x2, x3] f [x1, x2, x3] f [x0, x1, x2, x3]x4 f (x4) f [x3, x4] f [x2, x3, x4] f [x1, x2, x3, x4] f [x0,?, x4]由差商定義可知由差商定義可求得記 則 其中稱(chēng)為n次牛頓插值多項(xiàng)式，是截?cái)嗾`差。根據(jù)（4）式以外所有的節(jié)點(diǎn)都是的根，因此令 又由=1，得： 所以有 代入（5）得 拉格朗日插值多項(xiàng)式為： 牛頓插值：（拉格朗日插值的缺點(diǎn)）拉格朗日插值公式的形式雖然有一定的規(guī)律， 但是當(dāng)增加一個(gè)節(jié)點(diǎn)時(shí)，不僅要增加項(xiàng)數(shù)，而且以前各項(xiàng)也必須重新全部計(jì)算，不能利用已有的結(jié)果。當(dāng)估算點(diǎn)屬于包含x0，x1…xn的最小閉區(qū)間時(shí)，相應(yīng)的插值稱(chēng)為內(nèi)插，否則稱(chēng)為外插。插值是離散函數(shù)逼近的重要方法，利用它可通過(guò)函數(shù)在有限個(gè)點(diǎn)處的取值狀況，估算出函數(shù)在其他點(diǎn)處的近似值（與擬合的不同點(diǎn)在于擬合的函數(shù)不需通過(guò)每一個(gè)離散點(diǎn)）。這樣，確定最大似然估計(jì)量的問(wèn)題就歸結(jié)為微分學(xué)中的求最大值的問(wèn)題了。這種估計(jì)方法成為矩估計(jì)法。a1=Fit[data,{1,x,x^2,x^3},x]Show[ListPlot[data,FillingAxis],Plot[{a1},{x,0,60}]]結(jié)果：+ x2+ x3（2）參數(shù)估計(jì)（參考書(shū)：概率論與數(shù)理統(tǒng)計(jì)）參數(shù)估計(jì)為統(tǒng)計(jì)推斷的基本問(wèn)題，分為點(diǎn)估計(jì)和區(qū)間估計(jì)。 ，同時(shí)循環(huán)取樣次數(shù)一定，讓取樣結(jié)果隨時(shí)間變化，當(dāng)取樣次數(shù)為80000000時(shí)，可得6次的結(jié)果顯示： 應(yīng)用的范圍蒙特 if((x*x+y*y)=1) num++。 for(i=0。已知：K=，K，s=1，s1=，求Pi。只要能求出扇形面積S1在正方形面積S中占的比例K=S1/S就立即能得到S1，從而得到Pi的值。從歷年競(jìng)賽題來(lái)看，常用的方法：線(xiàn)性規(guī)劃 整數(shù)規(guī)劃 非線(xiàn)性規(guī)劃 動(dòng)態(tài)規(guī)劃 層次分析法圖論方法 擬合方法 插值方法 隨機(jī)方法 微分方程方法各種算法的詳解一、蒙特卡洛算法含義的理解　　以概率和統(tǒng)計(jì)理論方法為基礎(chǔ)的一種計(jì)算方法。開(kāi)放性還表現(xiàn)在對(duì)模型假設(shè)和對(duì)數(shù)據(jù)處理上。問(wèn)題的數(shù)據(jù)讀取需要計(jì)算機(jī)技術(shù)，如00A（大數(shù)據(jù)），01A（圖象數(shù)據(jù)，圖象處理的方法獲得），04A（數(shù)據(jù)庫(kù)數(shù)據(jù)，數(shù)據(jù)庫(kù)方法，統(tǒng)計(jì)軟件包）。 05B 04B電力市場(chǎng)的輸電阻塞管理 整數(shù)規(guī)劃、運(yùn)輸問(wèn)題 03B 單目標(biāo)決策 02B彩票問(wèn)題 01B 01A血管三維重建 模式識(shí)別、Fisher判別、人工神經(jīng)網(wǎng)絡(luò)DNA序列分類(lèi) 98B災(zāi)情巡視的最佳路線(xiàn) 動(dòng)態(tài)規(guī)劃、排隊(duì)論、圖論 非線(xiàn)性規(guī)劃、線(xiàn)性規(guī)劃 95A飛行管理問(wèn)題圖論、層次分析、整數(shù)規(guī)劃擬合、規(guī)劃 歷年全國(guó)數(shù)學(xué)建模試題及解法賽題 數(shù)值分析算法。 網(wǎng)格算法和窮舉法。 動(dòng)態(tài)規(guī)劃、回溯搜索、分治算法、分支定界等計(jì)算機(jī)算法。線(xiàn)性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等規(guī)劃類(lèi)問(wèn)題。From clown studio建模十大經(jīng)典算法 蒙特卡羅算法。比賽中通常會(huì)遇到大量的數(shù)據(jù)需要處理，而處理數(shù)據(jù)的關(guān)鍵就在于這些算法，通常使用Matlab作為工具。這類(lèi)算法可以分為很多種，包括最短路、網(wǎng)絡(luò)流、二分圖等算法，涉及到圖論的問(wèn)題可以用這些方法解決，需要認(rèn)真準(zhǔn)備。這些問(wèn)題是用來(lái)解決一些較困難的最優(yōu)化問(wèn)題的算法，對(duì)于有些問(wèn)題非常有幫助，但是算法的實(shí)現(xiàn)比較困難，需慎重使用。很多問(wèn)題都是實(shí)際來(lái)的，數(shù)據(jù)可以是連續(xù)的，而計(jì)算機(jī)只認(rèn)的是離散的數(shù)據(jù)，因此將其離散化后進(jìn)行差分代替微分、求和代替積分等思想是非常重要的。賽題中有一類(lèi)問(wèn)題與圖形有關(guān)，即使與圖形無(wú)關(guān)，論文中也應(yīng)該要不乏圖片的，這些圖形如何展示以及如何處理就是需要解決的問(wèn)題，通常使用Matlab進(jìn)行處理。 93A非線(xiàn)性交調(diào)的頻率設(shè)計(jì) 94B鎖具裝箱問(wèn)題圖論、組合數(shù)學(xué) 96B節(jié)水洗衣機(jī) 97A零件的參數(shù)設(shè)計(jì) 97B截?cái)嗲懈畹淖顑?yōu)排列 98A一類(lèi)投資組合問(wèn)題 多目標(biāo)優(yōu)化、非線(xiàn)性規(guī)劃 99A自動(dòng)化車(chē)床管理 00A 組合優(yōu)化、運(yùn)輸問(wèn)題 曲線(xiàn)擬合、曲面重建 02A車(chē)燈線(xiàn)光源的優(yōu)化 非線(xiàn)性規(guī)劃 微分方程、差分方程 統(tǒng)計(jì)分析、數(shù)據(jù)處理、優(yōu)化 05A長(zhǎng)江水質(zhì)的評(píng)價(jià)和預(yù)測(cè) 預(yù)測(cè)評(píng)價(jià)、數(shù)據(jù)處理 ：賽題的解決依賴(lài)計(jì)算機(jī)，題目的數(shù)據(jù)較多，手工計(jì)算不能完成，如03B，某些問(wèn)題需要使用計(jì)算機(jī)軟件，01A。解法的多樣性，一道賽題可用多種解法。 單位圓的1/4面積是一個(gè)扇形，它是邊長(zhǎng)為1單位正方形的一部分。P落在扇形內(nèi)的充要條件是 。 int i。/*RAND_MAX=32767，包含在中*/ y=rand()*。如果加入程序：srand(time(NULL))。實(shí)例：2010年蘇北賽B題 溫室中的綠色生態(tài)臭氧病蟲(chóng)害防治 中關(guān)于中華稻蝗密度與水稻減產(chǎn)率之間的關(guān)系可以通過(guò)數(shù)據(jù)擬合來(lái)觀察（簡(jiǎn)單舉例，沒(méi)有考慮全部數(shù)據(jù)）數(shù)據(jù)：密度（頭/m2）310203040減產(chǎn)率（%）程序（Mathematica）：data={{3,},{10,},{20,},{30,},{40,}}?；跇颖揪匾栏怕适諗坑谙鄳?yīng)的總體矩，樣本矩的連續(xù)函數(shù)依概率收斂于相應(yīng)的總體矩的連續(xù)函數(shù)，我們就用樣本矩作為相應(yīng)的總體矩的估計(jì)量，而以樣本矩的連續(xù)函數(shù)作為相應(yīng)的總體矩的連續(xù)函數(shù)的估計(jì)量。若則稱(chēng)為的最大似然估計(jì)值，稱(chēng)為的最大似然估計(jì)量。正態(tài)總體均值、方差的置信區(qū)間與單側(cè)置信限（置信水平為1）一個(gè)正態(tài)總體未知參數(shù)其他參數(shù)樞軸量的分布置信區(qū)間已知未知未知另外還包括兩個(gè)正態(tài)總體的情況，其他區(qū)間估計(jì)：（01）分布參數(shù)的區(qū)間估計(jì)（3）插值含義的理解在離散數(shù)據(jù)的基礎(chǔ)上補(bǔ)插連續(xù)函數(shù)，使得這條連續(xù)曲線(xiàn)通過(guò)全部給定的離散數(shù)據(jù)點(diǎn)。此處f（x）稱(chēng)為被插值函數(shù)，x0，x1，…xn稱(chēng)為插值結(jié)(節(jié))點(diǎn)，Φ(C0，C1，…Cn)稱(chēng)為插值函數(shù)類(lèi)，上面等式稱(chēng)為插值條件，Φ（C0，…Cn）中滿(mǎn)足上式的函數(shù)稱(chēng)為插值函數(shù)，R（x）＝ f（x）－P（x）稱(chēng)為插值余項(xiàng)。拉格朗日插值：設(shè)連續(xù)函數(shù)y = f（x）在[a, b]上對(duì)給定n + 1 個(gè)不同結(jié)點(diǎn)：分別取函數(shù)值其中 （1）試構(gòu)造一個(gè)次數(shù)不超過(guò) n的插值多項(xiàng)式 （2） 使之滿(mǎn)足條件 （3）構(gòu)造n次多項(xiàng)式 使 = （4） 由 (5)即 滿(mǎn)足插值條件，于是問(wèn)題歸結(jié)為具體求出基本插值多項(xiàng)式。一般稱(chēng)：為在處的n階差商。這類(lèi)插值稱(chēng)作切觸插值，或埃爾米特(Hermite)插值。在經(jīng)濟(jì)管理、交通運(yùn)輸、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟(jì)活動(dòng)中，提高經(jīng)濟(jì)效果是人們不可缺少的要求，而提高經(jīng)濟(jì)效果一般通過(guò)兩種途徑：一是技術(shù)方面的改進(jìn)，例如改善生產(chǎn)工藝，：在一定條件下，合理安排人力物力等資源，求線(xiàn)性目標(biāo)函數(shù)在線(xiàn)性約束條件下的最大值或最小值的問(wèn)題，統(tǒng)稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題。）所建立的數(shù)學(xué)模型具有以下特點(diǎn)：（1）、每個(gè)模型都有若干個(gè)決策變量（x1,x2,x3……，xn），其中n為決策