數(shù)學(xué)建模十大經(jīng)典算法(__數(shù)學(xué)建模必備資料)

1、From clown studio建模十大經(jīng)典算法1、蒙特卡羅算法。該算法又稱隨機(jī)性模擬算法，足通過計(jì)算機(jī)仿真來解決問題的算法，同時(shí)通過模擬町以 來檢驗(yàn)自己模型的正確性。2、數(shù)據(jù)擬合、參數(shù)估計(jì)、插值等數(shù)據(jù)處理算法。比賽中通常會(huì)遇到人最的數(shù)據(jù)需要處理，而處理數(shù)據(jù)的關(guān)鍵就在于這些算法，通常使用Matlab作為工幾。3、線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等規(guī)劃類問題。建模競(jìng)賽人多數(shù)問題屬于最優(yōu)化問題，很多時(shí)候這些問題町以用數(shù)學(xué)規(guī)劃算法米描述， 通常使用Lindo、Lingo、MATLAB軟件實(shí)現(xiàn)。4、圖論算法。這類算法町以分為很多種，包括故短路、網(wǎng)絡(luò)流、二分圖等算法，涉及到圖論的問題町 以用這些

2、方法解決，需要認(rèn)真準(zhǔn)備。5、動(dòng)態(tài)規(guī)劃、回溯搜索、分治算法、分支定界等計(jì)算機(jī)算法。這些算法是算法設(shè)計(jì)中比較常用的方法，很多場(chǎng)合町以用到竟賽中。6、最優(yōu)化理論的三大非經(jīng)典算法：模擬退火法、神經(jīng)網(wǎng)絡(luò)、遺傳算法。這些問題是用來解決一些較困難的故優(yōu)化問題的算法，對(duì)于有些問題非常有幫助，但是 算敢的實(shí)現(xiàn)比較困難，需慎覓使用。7、網(wǎng)格算法和窮舉法。網(wǎng)格算法和窮舉法都是眾力搜索/優(yōu)點(diǎn)的算法，在很多竟賽題中仃應(yīng)用，當(dāng)重點(diǎn)討論模 型本身而輕視算法的時(shí)候，可以使用這種暴力方案，最好使用一些高級(jí)語言作為編程工貝。8、一些連續(xù)離散化方法。很多問題都是實(shí)際來的，數(shù)據(jù)町以是連續(xù)的，而計(jì)算機(jī)只認(rèn)的是離散的數(shù)據(jù)，因此將英 離散

3、化后進(jìn)行差分代替微分、求和代替積分等思想是非常乘要的。9、數(shù)值分析算法。如果在比賽中釆用高級(jí)語言進(jìn)行編程的話，那一些數(shù)值分析中常用的算法比如方程組求 解、矩陣運(yùn)算、函數(shù)枳分等算法就需要額外編寫庫歯數(shù)進(jìn)行調(diào)用。10、圖象處理算法。賽題中有一類問題與圖形有關(guān)，即使與圖形無關(guān)，論文中也應(yīng)該要不乏圖片的，這些圖形如何展示以及如何處理就是需要解決的問題，通常使用Matlab進(jìn)行處理。歷年全國(guó)數(shù)學(xué)建模試題及解法賽題解法93A非線性交調(diào)的頻率設(shè)計(jì)擬合、規(guī)劃93B足球隊(duì)排名圖論、層次分析、整數(shù)規(guī)劃94A逢山開路圖論、插值、動(dòng)態(tài)規(guī)劃94B鎖只裝箱問題圖論、組合數(shù)學(xué)95A飛行管理問題非線性規(guī)劃、線性規(guī)劃95B大車

4、與冶煉爐的作業(yè)調(diào)度動(dòng)態(tài)規(guī)劃、排隊(duì)論、圖論96A最優(yōu)捕魚策略微分方程、優(yōu)化96B節(jié)水洗衣機(jī)非線性規(guī)劃97A冬件的參數(shù)設(shè)計(jì)非線性規(guī)劃97B截?cái)嗲懈畹淖顑?yōu)排列隨機(jī)模擬、圖論98A類投資組合問題多目標(biāo)優(yōu)化、非線性規(guī)劃98B災(zāi)情巡視的最佳路線圖論、組合優(yōu)化99A自動(dòng)化乍床管理隨機(jī)優(yōu)化、計(jì)算機(jī)模擬99B鉆井布局0-1規(guī)劃、圖論00ADNA序列分類模式識(shí)別、Fishei-判別、人工神經(jīng)網(wǎng)絡(luò)00B鋼管訂購和運(yùn)輸組合優(yōu)化、運(yùn)輸問題01A血管三維巫建曲線擬合、曲面巫建01B公交乍調(diào)度問題多冃標(biāo)規(guī)劃02A車燈線光源的優(yōu)化非線性規(guī)劃02B彩栗問題單目標(biāo)決策03ASARS的傳播微分方程、差分方程03B露天礦生產(chǎn)的車輛安

5、排整數(shù)規(guī)劃、運(yùn)輸問題04A奧運(yùn)會(huì)臨時(shí)超市網(wǎng)點(diǎn)設(shè)計(jì)統(tǒng)計(jì)分析、數(shù)據(jù)處理、優(yōu)化04B電力市場(chǎng)的輸電阻塞管理數(shù)據(jù)擬合、優(yōu)化05A氏江水質(zhì)的評(píng)價(jià)和預(yù)測(cè)預(yù)測(cè)評(píng)價(jià)、數(shù)據(jù)處理05B DVD在線租賃隨機(jī)規(guī)劃、整數(shù)規(guī)劃06A出版資源配置06B艾滋病療法的評(píng)價(jià)及療效的預(yù)測(cè)07A中國(guó)人口增長(zhǎng)預(yù)測(cè)07B乘公交，看奧運(yùn)多目標(biāo)規(guī)劃 數(shù)據(jù)處理 圖論08A數(shù)碼相機(jī)定位08B高等教育學(xué)費(fèi)標(biāo)準(zhǔn)探討09A制動(dòng)器試驗(yàn)臺(tái)的控制方法分析09B眼科病床的合理安排動(dòng)態(tài)規(guī)劃10A10B賽題發(fā)展的特點(diǎn)：1對(duì)選F的計(jì)算機(jī)能力提出了更高的要求：賽題的解決依賴計(jì)算機(jī)，題目的數(shù)據(jù)較兔，于工 計(jì)算不能完成，如03B,某些問題需要使用計(jì)算機(jī)軟件，01A。問題

6、的數(shù)據(jù)讀取需要計(jì)算機(jī) 技術(shù)，如00A （大數(shù)據(jù)），01A （圖象數(shù)據(jù)，圖象處理的方法獲得），04A （數(shù)據(jù)庫數(shù)據(jù)，數(shù) 據(jù)庫方法，統(tǒng)計(jì)軟件包）。計(jì)算機(jī)模擬和以算法形式給出最終結(jié)果。2賽題的開放性增人解法的女樣性，一道賽題可用多種解法。開放性還衷現(xiàn)在對(duì)模型假設(shè)和 對(duì)數(shù)據(jù)處理上。3試題向大規(guī)模數(shù)據(jù)處理方向發(fā)展4求解算法和各類現(xiàn)代算法的融合從歷年競(jìng)賽題來看，常用的方法：線性規(guī)劃整數(shù)規(guī)劃非線性規(guī)劃動(dòng)態(tài)規(guī)劃層次分析法圖論方法擬合方法插值方法隨機(jī)方法微分方程方法各種算法的詳解一、蒙特卡洛算法1、含義的理解以概率和統(tǒng)計(jì)理論方法為基礎(chǔ)的一種計(jì)算方法。也稱統(tǒng)計(jì)模擬方法，是指使用隨機(jī)數(shù)（或更 常見的偽隨機(jī)數(shù)）來解決

7、很多計(jì)算問題的方法，它是將所求解的問題同一定的概率模型相 聯(lián)系，用計(jì)算機(jī)實(shí)現(xiàn)統(tǒng)計(jì)模擬或抽樣，以獲得問題的近似解。2、算法實(shí)例（有很多相似的例題，包括平行線等）在數(shù)值枳分法中，利用求單位圓的1/4的面積來求得P1/4從而得到Pl。單位圓的1/4面枳是 一個(gè)扇形，它是邊長(zhǎng)為1單位正方形的一部分。只要能求出扇形面積S1在正方形而積S中 占的比例K=S1/S就立即能得到S1,從而得到P1的值。怎樣求出扇形面積在正方形面積中 占的比例K呢？ 一個(gè)辦法是在正方形中隨機(jī)投入很多點(diǎn)，使所投的點(diǎn)落在正方形中每一個(gè) 位置的機(jī)會(huì)相等看其中有多少個(gè)點(diǎn)落在扇形內(nèi)。將落在扇形內(nèi)的點(diǎn)數(shù)m與所投點(diǎn)的總數(shù)n的比m/n作為k的近

8、似值。P落在扇形內(nèi)的充要條件足lC + y<l .求Pio已知：K= , K« , s=l, sl= sn4程序：(該算法口J以修改后用Mathematica計(jì)算或Matlab)/*利用蒙特卡洛算法近似求圓周率Pi*/*程序使用：VC4H5.0*/#indude<stdio.h>#indude<math.h>#include<stdlib.h>#define COUNT 800嚴(yán)循環(huán)取樣次數(shù)，每次取樣范圍依次變大*/void mainOdouble x,y;int num=0;int i;for(i=0 ;i VCOUNT i 卄)x=ran

9、dO*l 0/RAND_MAX;/*RAND_MAX=32767,包含在vstdio.h>中水/ y=randO*l 0/RAND_MAX;if(x*x+y*y)<=l)mmi-H-; /*統(tǒng)計(jì)落在四分之一圓之內(nèi)的點(diǎn)數(shù)*7printf(nPi 值等于：%firnum*4.0/COUNT);結(jié)果：測(cè)試6次的結(jié)果顯示：循壞取樣次數(shù)求得的P1值8003 085CC080003.110C00800003.1352008000003 13915080000003 141393From clown studio800000003 141321可以看出:隨看點(diǎn)數(shù)的增加，求得的Pl值漸漸接近真實(shí)值

10、。如果加入程序：si*and（time（NULL）,同時(shí)循環(huán)取樣次數(shù)一定，讓取樣結(jié)果隨時(shí)間變化，當(dāng) 取樣次數(shù)為80000000時(shí)，可得6次的結(jié)果顯示：3 1412903.141400 3 1412683.141484 3 141358 3 1414623、應(yīng)用的范國(guó)蒙特卡羅方法在金融工程學(xué)，宏觀經(jīng)濟(jì)學(xué)，計(jì)算物理學(xué)（如粒子輸運(yùn)計(jì)算、最子熱力學(xué)計(jì)算、空氣動(dòng)力學(xué)計(jì)算）等領(lǐng)域應(yīng)用廣泛。4、參考書籍1 蒙特卡羅方法及其在粒子輸運(yùn)問題中的應(yīng)用2蒙特卡羅方法引論二、數(shù)據(jù)擬合、參數(shù)估計(jì)、插值等數(shù)據(jù)處理算法（1）數(shù)據(jù)擬合在Nfathematica中，用Fit對(duì)數(shù)據(jù)進(jìn)行最小二乘擬合：Fit data,fims,v

11、ars在Matlab中，工具箱（toolboxes）中有曲線擬合工具（curve Fitting）* 實(shí)例：2010年蘇北賽B題 溫室中的綠色生態(tài)臭氧病蟲害防治中關(guān)于中華稻蝗密度與水稻減產(chǎn) 率之間的關(guān)系町以通過數(shù)據(jù)擬合來觀察（簡(jiǎn)單舉例，沒有考慮全部數(shù)據(jù)）數(shù)據(jù):密度（頭/m）310203040減產(chǎn)率（%）2.412. 916. 320. 126. 8程序(Mathematica )：data=(3,2.4,(10,12.9,(20,16.3),30,20.1,(40,26.8; al=Fitdata,1,x,x八2,x八3,xShowListPlotdata,Filling->Axis,P

12、lot al, x,0,60 結(jié)果：-3.68428+2.38529 x-0.0934637 x=+0.00132433 x3（2）參數(shù)估計(jì)（參考書：概率論與數(shù)理統(tǒng)計(jì)） 參數(shù)估計(jì)為統(tǒng)計(jì)推斷的基本問題，分為點(diǎn)估計(jì)和區(qū)間估計(jì)。點(diǎn)估計(jì)：矩估計(jì)法x連續(xù)型隨機(jī)變最，概率密度f（x；q,q,q）x為離散型隨機(jī)變量分布律px=x= p（%q,q,久）q，2，,q為待估參數(shù)，是來自x的樣本，假設(shè)總體x的前k階矩存在，為（X連續(xù)型）或” = E（X】）=工£p（x；q,，,久）（X離散型）1 =1,2,k （其中&是xuj能取 JCERy值的范國(guó)）。一般來說，它們是q,a,q的函數(shù)?；跇颖揪?/p>

13、a =依概率收斂1】臺(tái)于相應(yīng)的總體矩“（l=l,2,k）,樣本矩的連續(xù)函數(shù)依概率收斂于相應(yīng)的總體矩的連續(xù)函 數(shù)，我們就用樣本矩作為相應(yīng)的總體矩的估計(jì)量，而以樣本矩的連續(xù)函數(shù)作為相應(yīng)的總體矩 的連續(xù)函數(shù)的估計(jì)量。這種估計(jì)方法成為矩估計(jì)法。最大似然估計(jì)法X連續(xù)型隨機(jī)變量 似然函數(shù)L（9） = L（x1,x2,.,xn；） = nf（；）其中1=1 1=1是來自X的樣本XpX"九的聯(lián)合密度。x為離散型隨機(jī)變最似然函數(shù)1/0 = 1/齊,馮,£；0 =冇卩（;0,6®其中fjp區(qū)；。）是來自X的樣本務(wù)仝2，£的聯(lián)合分布律。 1=1若 L（0 = 1/逅，圣,，斗

14、；6 = 111宓1/齊心,0E則稱&.*,£）為8的最人似然估計(jì)值，稱/（XpX?,£）為0的最人似然估計(jì)量。這樣，確定最人似然估計(jì)最的問題就歸結(jié)為微分學(xué)中的求垠人值的問題了。估計(jì)量的評(píng)選標(biāo)準(zhǔn)為：（丄）無偏性（2）有效性（3）相合性區(qū)間估計(jì)：對(duì)于一個(gè)未知最，人們?cè)跍y(cè)最或計(jì)算時(shí)，常不以得到近似值為滿足，還需要估計(jì)誤差，即要 求知道近似值的精確程度（亦即所求真值所在的范I韋I）。這樣的范I韋I常以區(qū)間的形式給出， 同時(shí)還給出此區(qū)間包含參數(shù)真值的對(duì)信度，這種形式的估計(jì)稱為區(qū)間估計(jì)，這樣的區(qū)間即所 謂冒信區(qū)間。正態(tài)總體均值、方差的置信區(qū)間與單側(cè)置信限（置信水平為1-

15、71;）一個(gè)正態(tài)總體未知參數(shù)英他參數(shù)樞軸量的分布置信區(qū)間b2己知z = £dn（oj） cr! yjn（唇 Z“）A未知1 =t(n-l)S/Vn-s(X 土za/2 (n 一 1)CT未知(n-l)S2(n-l)S2zt2(Ta(T另外還包括兩個(gè)正態(tài)總體的情況，其他區(qū)間估計(jì)：(0-1)分布參數(shù)的區(qū)間估計(jì)(3) 插值1、含義的理解在離散數(shù)據(jù)的基礎(chǔ)匕補(bǔ)插連續(xù)曲數(shù)，使得這條連續(xù)曲線通過全部給定的離散數(shù)據(jù)點(diǎn)。插值是 離散函數(shù)逼近的巫要方法，利用它叮通過函數(shù)在有限個(gè)點(diǎn)處的取值狀況，估算出函數(shù)在其他 點(diǎn)處的近似值(與擬合的不同點(diǎn)在于擬合的函數(shù)不需通過每一個(gè)離散點(diǎn))。插值問題的提法是：假定區(qū)間a

16、, b上的實(shí)值函數(shù)f (x)在該區(qū)間上n+1個(gè)互不相 同點(diǎn)x0, xl . xn處的值是fx0,f (xn),要求估算f (x)在a, b中某點(diǎn)的值。 其做法是：在事先選定的一個(gè)由簡(jiǎn)單函數(shù)構(gòu)成的有n+1個(gè)參數(shù)CO, Cl, .Cn的函 數(shù)類(CO, Cl, .Cn)中求出滿足條件 P (xi) =f (xi) (1 = 0, 1. . n)的函數(shù) P(x), 并以P0作為f0的估值。此處f (x)稱為被插值旳數(shù)，x0, xl, .xn稱為插值結(jié)(節(jié)) 點(diǎn)，(CO, Cl, .Cn)稱為插值函數(shù)類，上面等式稱為插值條件，(CO, . Cn)中 滿足上式的函數(shù)稱為插值函數(shù)，R (x) = f (x

17、) -P (x)稱為插值余項(xiàng)。當(dāng)估算點(diǎn) 屬于包含x0, xl. xn的最小閉區(qū)間時(shí)，相應(yīng)的插值稱為內(nèi)插，否則稱為外插。2、基本類型多項(xiàng)式插值在般插值問題中，若選取為n次多項(xiàng)式類，由插值條件可以唯一確定一個(gè)n次插 值多項(xiàng)式滿足上述條件。拉恪朗口插值和牛頓插值都屈于多項(xiàng)式插值。拉格朗日插值：設(shè)連續(xù)函數(shù)y = f (x)在a,b上對(duì)給定n+1個(gè)不同結(jié)點(diǎn)：,檢分別取函數(shù)值,%,其中 乂=片(兀)i = 0,1 v n(1)試構(gòu)造一個(gè)次數(shù)不超過n的插值多項(xiàng)式匕(x) = % + aX+gx2 + + ©疋(2)使之滿足條件匕(兀)i = 0,1,-2-,n(3)構(gòu)造n次多項(xiàng)式l'x)

18、k = 0,lv n 使(4)由 只（兀）=Z yA） =y： i = o, i ,2,n k=i即pn（x）滿足插值條件，于是問題歸結(jié)為具體求出基本插值實(shí)項(xiàng)式h（x）。根拯（4）式h（x）以外所有的節(jié)點(diǎn)都是lk（x）的根，因此令h (x) = 2(x- Xq)(x-齊)(x- Vi)(x-觀乜)(x xj= 2fJ(x-xJ) j=0 存k又由lk(x)=l,得:（兀一毛）（怎氏）-忑1）（彖兀也）（ xj所以旳(X)= (Xf( -況)(忑-xi) - Vi)( - +1) ( - )代入（5）得拉格朗日插值多項(xiàng)式為:W = S1k(x)yk=Sk=0k=OYk牛頓描值：（拉格朗日插值的峽

19、點(diǎn)）拉格朗口插值公式的形式雖然冇一定的規(guī)律，但是肖增加 一個(gè)節(jié)點(diǎn)時(shí)，不僅要增加項(xiàng)數(shù)，而且以前各項(xiàng)也必須覓新全部計(jì)算，不能利用己有的 結(jié)果。為克服這一缺點(diǎn)，我們?nèi)∮昧硪环N形式一一牛頓插值公式。牛頓插值公式中用到了差商。一般稱：差商町列表計(jì)算：XIyi一階差商二階差商三階差商xOf(xO)X1f(xl)f xO, xlxZf (xZ)f xl, xZf xO, xl, x2x3f(x3)f x2, x3f xl, x2» x3f xO, xl, x2, x3為f（x）在Xg,Xp,處的n階差商。四階差商x4 f (x4) f x3, x4 f x2, x3, x4 f xlt x2t x

20、3, x4 f xOm> x4由差商定義可知E(x)= f(Xo)+坷(X-Xjj)+ f%,兀，叩(X-Xjj)(X-齊)由差商定義町求得f(X)= f (Xq) +(X- Xq) fXo，xJ+(X-Xq)(X-齊)口毛,齊,卷+ +(x_x；j)(x_ 齊)(x_ 心i)fXo，»i，兀+ (X-Xo)(X-Xi).(X-) 口耳忌，齊,，兀J記Nn(x) = f (*)+ (x- Xq) fXQ,齊+ (x- Xq)(X-舌)f%“+ -+(x-x0)(x-).(x-_1)fx0,x1,.,x11%( x> g oX)(X 1 X) K x)fl %jX ,沖則

21、(x) = Nn(x) + Rh(x)其中Nn(x)稱為n次牛頓插值多項(xiàng)式，RJx)是截?cái)嗾`差。最終我們町以證明Nn(X)滿足插值條件Nn() = §(兀)i = 0,1,2,.,n因此有叫(£)=(X牛頓插值公式的優(yōu)點(diǎn)是：當(dāng)增加一個(gè)節(jié)點(diǎn)時(shí)，只要再增加一項(xiàng)就行了，即有遞推式當(dāng)然，與拉格朗口插值相比它還有節(jié)省運(yùn)算次數(shù)的優(yōu)點(diǎn)(尤其是節(jié)省乘法運(yùn)算次數(shù))。 分段插值與樣條插值為了避免高次插值町能出現(xiàn)的大幅度波動(dòng)現(xiàn)象，在實(shí)際應(yīng)用中通常采用分段低次插值 來提離近似程度埃爾米特插值許多實(shí)際插值問題中，為使插值兩數(shù)能更好地和原來的兩數(shù)更合，不但要求二者在節(jié) 點(diǎn)上函數(shù)值相等，而且還要求柑切，

22、對(duì)應(yīng)的導(dǎo)數(shù)值也相等，其至要求高階導(dǎo)數(shù)也相等。 這類插值稱作切觸插值，或埃爾米特(Hermite)插值。滿足這種要求的插值多項(xiàng)式就是 埃爾米特插值多項(xiàng)式三角函數(shù)插值當(dāng)被插曲數(shù)是以2兀為周期的函數(shù)時(shí)，通常用n階三角多項(xiàng)式作為插值函數(shù)，并通過 高斯三角插值表出。三、線性規(guī)劃、整數(shù)規(guī)劃.多元規(guī)劃、二次規(guī)劃(1) 線性規(guī)劃1、含義的理解線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支，它是輔 助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法研究線性約束條件下線性目標(biāo)函數(shù)的極值問題的數(shù)學(xué) 理論和方法，英文縮寫LP。它是運(yùn)籌學(xué)的一個(gè)重要分支。在經(jīng)濟(jì)管理、交通運(yùn)輸、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟(jì)活動(dòng)中，提高經(jīng)濟(jì)效果

23、是人們不可缺少的要求, 而提高經(jīng)濟(jì)效果一般通過兩種途徑：一是技術(shù)方面的改進(jìn)，例如改善生產(chǎn)工藝，使用新設(shè) $和新型原材料二是生產(chǎn)組織與計(jì)劃的改進(jìn)，即介理安排人力物力資源線性規(guī)劃所研究的 是：在一定條件F，合理安排人力物力等資源，使經(jīng)濟(jì)效果達(dá)到最好一般地，求線性目標(biāo) 函數(shù)在線性約束條件下的最大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題。滿足線性約束條 件的解叫做可行解，由所有可行解組成的集合叫做可行域。決策變童、約束條件、目標(biāo)函 數(shù)是線性規(guī)劃的三要素。2、線性規(guī)劃問題的數(shù)學(xué)模型的-般形式和模型建立（1）列出約束條件及目標(biāo)函數(shù)（2）畫出約束條件所表示的可行域（3）在可行域內(nèi)求目 標(biāo)函數(shù)的最優(yōu)解及最優(yōu)值（實(shí)

24、際問題中建立數(shù)學(xué)模型一般有以下三個(gè)步驟：根據(jù)影響所要達(dá) 到目的的因素找到?jīng)Q策變最：2由決策變量和所在達(dá)到目的之間的函數(shù)關(guān)系確定目標(biāo)函數(shù)； 3由決策變量所受的限制條件確定決策變量所要滿足的約束條件。） 所建立的數(shù)學(xué)模型具有以下特點(diǎn)：（1）、每個(gè)模型都有若干個(gè)決策變量（xl,x2,x3，xn）,其中n為決策變量個(gè)數(shù)。決策變 量的一組值表示一種方案，同時(shí)決策變量一般是非負(fù)的。（2）、目標(biāo)函數(shù)是決策變屋的線性函數(shù)，根據(jù)具體問題可以是最人化（max）或最小化（min）, 二者統(tǒng)稱為最優(yōu)化（opt）。（3）、約束條件也是決策變量的線性函數(shù)。當(dāng)我們得到的數(shù)學(xué)模型的目標(biāo)函數(shù)為線性函數(shù), 約束條件為線性等式或不

25、等式時(shí)稱此數(shù)學(xué)模型為線性規(guī)劃模型。3、實(shí)例生產(chǎn)計(jì)劃問題問題：某企業(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)如卜表。問 應(yīng)如何確定生產(chǎn)計(jì)劃使企業(yè)獲利最多？品資源'、甲乙資源量設(shè)備/臺(tái)時(shí)318原料A/噸104原料B/噸012單位嵐利/萬元55設(shè)xl為甲產(chǎn)品分配的設(shè)備臺(tái)數(shù)，為乙產(chǎn)品分配的臺(tái)數(shù)。則 條件限制為：3*xl+2*x2<18 l*xl+0*x2<4 0*xl+2*x2<12 xl>0, x2>0 求 max z=3*xl+5*x2用lingo編

26、程，程序如卜：max=3*xl+5*x2;3*xl+2*x2<=l &xlv=4,x2<=6,xl>=0,x2>=0,結(jié)果為：Global optimal solution foundObjective value:36. 00000Total solver iterations:1VariableValue2.0000006.000000Reduced Cost0.000000D.000000XIX2RowSlack.or SurplusDual Price136.000001.000000o0.0000001.0000D03o0000000.0000D040

27、.0000003.0000005o0000000.00000066.0000000.0000D0即在xl=2» 乂2=6時(shí)企業(yè)獲利最多，為36萬元。4、線性規(guī)劃的應(yīng)用在企業(yè)的各項(xiàng)管理活動(dòng)中，例如計(jì)劃、生產(chǎn)、運(yùn)輸、技術(shù)等問題,線性規(guī)劃是指從各種限制條 件的組合中，選擇出放為介理的計(jì)算方法,建立線性規(guī)劃模型從而求得最佳結(jié)果廣泛應(yīng)用于 軍爭(zhēng)作戰(zhàn)、經(jīng)濟(jì)分析、經(jīng)營(yíng)管理和工程技術(shù)等方面。為合理地利用有限的人力、物力、財(cái)力 等資源作出的最優(yōu)決策，提供科學(xué)的依據(jù)。（2）整數(shù)規(guī)劃一類要求問題的解中的全部或一部分變最為整數(shù)的數(shù)學(xué)規(guī)劃。從約束條件的構(gòu)成又町細(xì)分為 線性，二次和非線性的整數(shù)規(guī)劃。在線性規(guī)劃問

28、題中，有些域優(yōu)解町能是分?jǐn)?shù)或小數(shù),但對(duì)于某些具體問題，常要求某些變量的解必須足整數(shù)。例如，當(dāng)變量代表的是機(jī)器的臺(tái) 數(shù)，工作的人數(shù)或裝貨的車數(shù)等。為了滿足整數(shù)的要求，初看起來似乎只要把已得的非整 數(shù)解舍入化整就町以了。實(shí)際上化整后的數(shù)不見得是可行解和最優(yōu)解，所以應(yīng)該有特殊的 方法來求解整數(shù)規(guī)劃。在整數(shù)規(guī)劃中，如果所仃變量都限制為整數(shù)，則稱為純整數(shù)規(guī)劃； 如果僅一部分變量限制為盛數(shù)，則稱為混介整數(shù)規(guī)劃。整數(shù)規(guī)劃的一種特殊情形是01規(guī)劃, 它的變數(shù)僅限于0或1。不同于線性規(guī)劃問題，整數(shù)和01規(guī)劃問題至今尚未找到一般的多 項(xiàng)式解法。組合鍛優(yōu)化通常都可表述為整數(shù)規(guī)劃問題。兩者都是在有限個(gè)町供選擇的方案中

29、，尋找滿 足一定約束的最好方案。有許多典型的問題反映整數(shù)規(guī)劃的廣泛巧景。例如，背袋（或裝載） 問題、固定費(fèi)用問題、和睦探險(xiǎn)隊(duì)問題（組合學(xué)的對(duì)集問題）、有效探險(xiǎn)隊(duì)問題（組合學(xué)的 覆孟問題）、旅行推銷員問題，車輛路徑問題等。因此整數(shù)規(guī)劃的應(yīng)用范圉也是極其廣泛的。 它不僅在工業(yè)和工程設(shè)計(jì)和科學(xué)研究方面有許多應(yīng)用，而且在計(jì)算機(jī)設(shè)計(jì)、系統(tǒng)可靠性、編 碼和經(jīng)濟(jì)分析等方面也有新的應(yīng)用。整數(shù)規(guī)劃是從1958年由RE戈莫里提出割平面法之后形成獨(dú)立分支的。解整數(shù)規(guī)劃最典 型的做法是逐步生成一個(gè)相關(guān)的問題，稱它是原問題的衍生問題。對(duì)每個(gè)衍生問題又伴隨 一個(gè)比它更易于求解的松弛問題（衍生問題稱為松弛問題的源問題）。通

30、過松地問題的解來 確定它的源問題的歸宿，即源問題應(yīng)被舍棄，還是再生成一個(gè)或多個(gè)它本身的衍生問題來 替代它。隨即再選擇一個(gè)尚未被舍棄的或替代的原問題的衍生問題，車復(fù)以上步驟直至不 再剩令未解決的衍生問題為止。目前比較成功又流行的方法是分枝定界法和割平面法，它 們都是在上述框架下形成的。0-1規(guī)劃在整數(shù)規(guī)劃中占有更要地位，一方面因?yàn)樵S多實(shí)際問題，例如指派問題、選地問題、 送貨問題都町歸結(jié)為此類規(guī)劃，另一方面任何右界變最的整數(shù)規(guī)劃都與0規(guī)劃等價(jià)，用 0-1規(guī)劃方法還町以把多種非線性規(guī)劃問題表示成整數(shù)規(guī)劃問題，所以不少人致力丁這個(gè) 方向的研究。求解01規(guī)劃的常用方法是分枝定界法，對(duì)齊種特殊問題還冇一些

31、特殊方法， 例如求解指派問題用匈牙利方法就比較方便。（4）二次規(guī)劃二次規(guī)劃是非線形規(guī)劃中一類特殊的數(shù)學(xué)規(guī)劃問題，它的解是町以通過求解得到的。通常通 過解英庫恩一塔克條件（KT條件），獲取一個(gè)KT條件的解稱為KT對(duì)，英中與原問題的變 最對(duì)應(yīng)的部分稱為KT點(diǎn)。二次觀劃分為凸二次規(guī)劃與非凸二次規(guī)劃，前者的KT點(diǎn)便是其全局極小值點(diǎn)，而后者的 KT點(diǎn)町能連局部極小值點(diǎn)都不是。若它的目標(biāo)函數(shù)是二次函數(shù)，則約束條件是線性的。由 于求解二次規(guī)劃的方法很多，所以較為復(fù)雜：英較簡(jiǎn)便易行的足沃爾夫法，它是依據(jù)庫恩 塔克條件，在線性規(guī)劃單純形法的基礎(chǔ)卜.加以修正而成的。此外還有萊姆基法、畢爾法、 凱勒法等。From

32、clown studioFrom clown studioU!圖論: （參考資料：建模教程（圖與網(wǎng)絡(luò)）From clown studio（1）含義的理解圖論是專門研究圖的理論的一門數(shù)學(xué)分支，屬于離散數(shù)學(xué)范躊，與運(yùn)籌學(xué)有交叉。圖論中常用點(diǎn)和點(diǎn)之間的線所構(gòu)成的圖，反映實(shí)際生產(chǎn)和生活中的某些特定對(duì)象之間的特定 關(guān)系。一般來說，通常用點(diǎn)表示研究對(duì)象、用點(diǎn)與點(diǎn)之間的線表示研究對(duì)彖之間的特定關(guān)系。在一般情況卜，圖中的相對(duì)位置如何，點(diǎn)與點(diǎn)之間線的長(zhǎng)短曲直，對(duì)于反映研究對(duì)象之 間的關(guān)系，顯的并不重要。因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上是不同的。（2）歷史（包括應(yīng)用范闈）它有200多年歷史，大體可劃分為三

33、個(gè)階段：第一階段是從十八世紀(jì)中葉到十九世紀(jì)中葉，處于萌芽階段，多數(shù)問題閑游戲而產(chǎn)生，故有 代表性的工作是所謂的Euler七橋問題，即一筆畫問題。第二階段是從十九世紀(jì)中葉到二十世紀(jì)中葉，這時(shí)，圖論問題大最出現(xiàn)，如Hamilton問題, 地圖染色的四色問題以及可平面性問題等，這時(shí)，也出現(xiàn)用圖解決實(shí)際問題，如Cayley把 樹應(yīng)用于化學(xué)領(lǐng)域，Kirchhoff用樹去研究電網(wǎng)絡(luò)等.第三階段是二十世紀(jì)中葉以后，由生產(chǎn)管理、軍班、交通、運(yùn)輸、計(jì)算機(jī)網(wǎng)絡(luò)等方面提出實(shí) 際問題，以及人型計(jì)算機(jī)使人規(guī)模問題的求解成為可能，特別是以Ford和Fulkerson建立 的網(wǎng)絡(luò)流理論，與線性規(guī)劃、動(dòng)態(tài)規(guī)劃等優(yōu)化理論和方法

34、柑互滲透，促進(jìn)了圖論対實(shí)際問題 的應(yīng)用。算法重要的算法1、求有向圖的強(qiáng)連通分支(Strongerst Connected Component)(1) Kos ar a j u 算法(2) Gabow 算法(3) Tarjan 算法2、求最小生成樹(Minimal Spanning Trees)(1) Kruskal 算法(2) Prim 算法3、最小樹形圖(1)朱水津劉振宏算法4、最短路徑問題(1) SSSP (Single-source Shortest Paths)©Dijkstra 算法BelIman-Ford 算法(SPFA 算法)(2) APSP(All-pairs Sho

35、rtest Paths) Floyd-Warshall 算法 Johnson算法5、網(wǎng)絡(luò)流問題(1) 最人網(wǎng)絡(luò)流 增廣路算法1 .Ford-Fulkerson 篦法2. Edmonds-Karp 算法3加短路徑增殖EK-2 (MPLA)4.Dinic 預(yù)流推進(jìn)算法(2) 最小費(fèi)用流6、圖匹配問題(1) 匈牙利算法(2) Hopcroft Karp 算法(3) KuhnMunkres 算法(4) Edmonds' blossom_contraction 算法(有關(guān)資料網(wǎng)址：http: www. nocow. cn/index, php/%E5%9B%BE%E8%AE%BA)(1)基本概念

36、無向圖一個(gè)無向圖(undirected graph) G是由一個(gè)非空有限集合V(G)和V(G)中某些元素的 無序?qū)螮(G)構(gòu)成的二元組，記為G=(V(G),E(G)。其中V(G) = %“,稱 為圖G的頂點(diǎn)集(vertex set )或節(jié)點(diǎn)集(node set ) , V(G)中的每一個(gè)元素 出(i = 12,口)稱為該圖的個(gè)頂點(diǎn)(vertex)或廿點(diǎn)(node )； E(G) = 勺冷,稱 為圖G的邊集(edge set), E(G)中的每一個(gè)元素q (即V(G)中某兩個(gè)元素乂,耳的無序From clown studio對(duì))記為豈= (V"Vj)或ek =vy =Vj2 (k

37、= 12,m),被稱為該圖的一條從v】到Vj的 邊(edge)。當(dāng)邊時(shí)，稱V,V)為邊耳的端點(diǎn)，并稱V：與V相鄰(adjacent)：邊乞稱為與頂點(diǎn)V,Vj關(guān)聯(lián)(incident )o如果某兩條邊至少有一個(gè)公共端點(diǎn)，則稱這兩條邊在圖G中 相鄰。邊上賦權(quán)的無向圖稱為賦權(quán)無向圖或無向網(wǎng)絡(luò)(undirected network)。我們對(duì)圖和網(wǎng)絡(luò)不 作嚴(yán)格區(qū)分，因?yàn)槿魏螆D總是可以賦權(quán)的有向圖一個(gè)有向圖(directed graph或digraph) G是由一個(gè)非空有限集合V和V中某些元素的有序 對(duì)集合A構(gòu)成的二元組，記為G=(V,丹。其中V = %,%,*稱為圖G的頂點(diǎn)集或節(jié)點(diǎn)集， V中的每一個(gè)元素v

38、】(i =稱為該圖的一個(gè)頂點(diǎn)或節(jié)點(diǎn)；A=a1,a2,- -,am稱為圖G的弧集(arc set), A中的每一個(gè)元素兀(即V中某兩個(gè)元素vx,Vj的有序?qū)?記為孔=(VpVj)或孔=vy (k = 12,n)，被稱為該圖的一條從y到v的弧(arc)a肖弧ak = 時(shí)，稱V為疋的尾(tail),耳為a的頭(head),并稱弧a*為V】的出弧(outgoing arc), 為V)的入弧 (incoming arc)。對(duì)應(yīng)于每個(gè)有向圖D,可以在相同頂點(diǎn)集上作一個(gè)圖G,使得對(duì)于D的每條弧，G有一條 有相同端點(diǎn)的邊與之相對(duì)應(yīng)。這個(gè)圖稱為D的基礎(chǔ)圖。反之，給定任意圖G,對(duì)于它的每 個(gè)邊，給其端點(diǎn)指定一個(gè)順

39、序，從而確定一條弧，由此得到一個(gè)有向圖，這樣的有向圖稱 為G的一個(gè)定向圖。完全圖、二分圖每一對(duì)不同的頂點(diǎn)都有一條邊相連的簡(jiǎn)單圖稱為完全圖(complete graph)o n個(gè)頂點(diǎn)的完全圖 記為Kn。若V (G)=XUY, XnY=<D, |X|Y|hO (這里| X |表示集合X中的元素個(gè)數(shù))，X中無相鄰頂點(diǎn)對(duì),Y中亦然,則稱G為二分圖(bipartitegraph)；特別地,若VxwXNywY,則取wE(G),則稱G為完全二分圖，記成片鞏曲。最短路、網(wǎng)絡(luò)流、二分圖1、最短路問題(SPPshortest patli problem)最短路徑問題足圖論中十分幣.要的最優(yōu)化問題之一，它作為

40、一個(gè)經(jīng)常被用到的基本工只，町 以解決生產(chǎn)實(shí)際中的許多問題，比如城市中的管道鋪設(shè)，線路安排，工廠布局，設(shè)備更新等等。也可以用于解決其它的最優(yōu)化問題。若網(wǎng)絡(luò)中的每條邊都有一個(gè)數(shù)值（長(zhǎng)度、成本、時(shí)間等），則找出兩節(jié)點(diǎn)（通常是源節(jié)點(diǎn) 和阱節(jié)點(diǎn)）之間總權(quán)和最小的路徑就是最短路問題。最短路問題是網(wǎng)絡(luò)理論解決的典 型問題之一，可用來解決管路鋪設(shè)、線路安裝、廠區(qū)布局和設(shè)備更新等實(shí)際問題。最 短路問題，我們通常歸屬為三類單源瑕短路徑問題包扌舌起點(diǎn)的最短路徑問題，確定終點(diǎn)的最短路徑問題（與確定起點(diǎn)的問題相反，該問 題是已知終結(jié)結(jié)點(diǎn)，求授短路徑的問題。在無向圖中該問題與確定起點(diǎn)的問題完全相 同，在有向圖中該問題等同

41、于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。）確定起點(diǎn)終點(diǎn)的最短路徑問題即己知起點(diǎn)和終點(diǎn)，求兩點(diǎn)之間的最短路徑。全局最短路徑問題求圖中所有的最短路徑。算法只要采用Floyed-Warshall算法（這是北洛伊德利用動(dòng)態(tài) 規(guī)劃（dynamic programming）的原理設(shè)計(jì)的一個(gè)高效算法）。Floyed-Warshall算法用來找出每對(duì)點(diǎn)之間的繪短距離。它需要用鄰接矩陣來儲(chǔ)存邊，這個(gè) 算法通過考世最佳子路徑來得到瑕佳路徑。注意單獨(dú)一條邊的路徑也不一定是最佳路徑。從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，或者無窮大，如果兩點(diǎn)之間沒有 邊相連。對(duì)于每一對(duì)頂點(diǎn)u和v,看看是否存在一個(gè)頂點(diǎn)w使得

42、從u到w再到v比己知的路徑 更短。如果是更新它。不可思議的是，只要按排適半，就能得到結(jié)果。最短路算法：Dijkstra 算法Dijksti'a 復(fù)雜度是 o（nt）,如果用 binary heap 優(yōu)化可以達(dá)到 o（E+N）iogN），用 fibonacci heap可以優(yōu)化到o（NiogN+E）其基本思想是釆用貪心法，對(duì)于每個(gè)節(jié)點(diǎn)vi,維護(hù)估計(jì)敲短路長(zhǎng)度敲人值，每次取出一個(gè) 使得該估計(jì)值最小的t,并采用與t相連的邊對(duì)英余點(diǎn)的估計(jì)值進(jìn)行更新，更新后不再考慮 to在此過程中，估計(jì)值單調(diào)遞減，所以町以得到確切的最短路。Dijkstra 程序：:void DijkstraO ；for(int

43、 i=l;i<=n;i+)；disi = mapl i;II:int k;:for(int i=l;i<n;i+)int tmin = maxint;:for(int j=l:j<=n;j+):if( !usedj && tmin > disj )；tmin 二 dis j;:k = j;: ；usedk = 1;:for(int j=l;j<=n;j+) if ( disk + mapk j < disj):disj = disk + mapk j:I printfdis n);:II:/*求1到N的最短路,disij表示第i個(gè)點(diǎn)到第一個(gè)點(diǎn)

44、的最短路By Ping*/II«»OB«還有其他算法：FloydWarshal 1 算法Be liman "Ford 算法Johnson 算法實(shí)例：某公司在六個(gè)城市q,c2，-,c6中有分公司，從c,到勺的直接航程票價(jià)記在下述矩陣的(i,j)位宣上。(s表示無直接航路)，請(qǐng)幫助該公司設(shè)計(jì)一張城市q到其它城市間的票價(jià)最便宜的路線圖。050co4025105001520CO25CO1501020CO4020100102525CO20100551025CO25550用矩陣玄如“(n為頂點(diǎn)個(gè)數(shù))存放備邊權(quán)的鄰接矩陣，行向最pb、index、index.d分別用來

45、存放P標(biāo)號(hào)信息、標(biāo)號(hào)頂點(diǎn)順序.標(biāo)號(hào)頂點(diǎn)索引、最短通路的值。其中分最pb(i) = ?為第訂貞點(diǎn)己標(biāo)號(hào)當(dāng)?shù)谟嗧擖c(diǎn)未標(biāo)號(hào)iiidex2(i)存放始點(diǎn)到第i點(diǎn)蟻短通路中第i頂點(diǎn)前一頂點(diǎn)的序號(hào);d(i)存放由始點(diǎn)到第i點(diǎn)最短通路的值。求第一個(gè)城市到其它城市的蟻短路徑的Matlab程序如K：clear;clc;M=10000;a(l, :) = 0,50,M, 40,25,10;a (2,:) = zeros(1<2)r15r20rMr25;a(3r:) = zeros(lz 3)r10f20rM;a(4,:) = zeros(lz 4)F10r25;a(5r:) = zeros (1,5),55

46、;a(6r:)=zeros (1,6);a=a+a1;pb(1:length(a)=0;pb(1)=1;indexl=l;index2=ones(lrlength(a); d(1:length(a)=M;d(1)=0;temp=l;while sum(pb)<iength (a)tb=find(pb=0);d (tb)=min (d (tb)# d(temp)+a(temp,tb);tmpb=find(d(tb)=min(d(tb);temp=tb(tmpb(1);pb (temp)=1;indexl=indexlf temp;index=indexl (find(d (indexl)=

47、d (temp)-a(temp,indexl); if length (index)>=2index=index(1);endindexZ (temp)=index;endd, indexlrindex?運(yùn)行結(jié)果為：d =03545352510indexl =1 6543index?=1 65611即:d （最短通路的值）03545352510indexl （標(biāo)號(hào)頂點(diǎn)順序）16543index?（標(biāo)號(hào)頂點(diǎn)索引）1656112、網(wǎng)絡(luò)流（1）含義的理解網(wǎng)絡(luò)流（network flows）是圖論中的一種理論與方法，研究網(wǎng)絡(luò)上的一類址優(yōu)化問題。（2）歷史及應(yīng)用1955年，T. E.哈里斯在研究鐵

48、路最大通量時(shí)首先提出在一個(gè)給定的網(wǎng)絡(luò)上尋求兩點(diǎn)間最 人運(yùn)輸量的問題。1956年，L. R.福特和D.R.常爾克森等人給出了解決這類問題的算法， 從而建立了網(wǎng)絡(luò)流理論。所謂網(wǎng)絡(luò)或容屋網(wǎng)絡(luò)指的是一個(gè)連通的賦權(quán)有向圖D= （V、E、C）, 其中V是該圖的頂點(diǎn)集，E是有向邊（即?。┘珻是弧上的容量。此外頂點(diǎn)集中包括一個(gè)起 點(diǎn)和一個(gè)終點(diǎn)。網(wǎng)絡(luò)上的流就是由起點(diǎn)流向終點(diǎn)的可行流，這是定義在網(wǎng)絡(luò)上的非負(fù)函數(shù), 它一方而受到容量的限制，另一方而除去起點(diǎn)和終點(diǎn)以外，在所有中途點(diǎn)要求保持流入量和 流出量是平衡的。最人流理論是由福特和富爾克森于1956年創(chuàng)立的，他們指出最人流的流值等于繪小割（截 集）的容屋這個(gè)重要

49、的事實(shí)，并根據(jù)這-原理設(shè)計(jì)了用標(biāo)號(hào)法求最人流的方法，后來又宿人 加以改進(jìn)，使得求解最人流的方法更加豐富和完善。最人流問題的研究密切了圖論和運(yùn)籌 學(xué)，特別是與線性規(guī)劃的聯(lián)系，開辟了圖論應(yīng)用的新途徑。最人流問題僅注意網(wǎng)絡(luò)流的流通能力，沒有考慮流通的費(fèi)用。實(shí)際上費(fèi)用內(nèi)素是很重要的。 例如在交通運(yùn)輸問題中，往往要求在完成運(yùn)輸任務(wù)的前提F，尋求一個(gè)使總運(yùn)輸費(fèi)用般省的 運(yùn)輸方案，這就是最小費(fèi)用流問題。如果只考慮單位貨物的運(yùn)輸費(fèi)用，那么這個(gè)問題就變成 最短路問題。由此町見，最短路問題是最小費(fèi)用流問題的基礎(chǔ)?，F(xiàn)已有一系列求最短路的成 功方法。最小費(fèi)用流（或繪小費(fèi)用最人流）問題，町以交替使用求解最人流和址短路兩

50、種方 法，通過迭代得到解決。目前網(wǎng)絡(luò)流的理論和應(yīng)用在不斷發(fā)展，出現(xiàn)了具有熠益的流、多終端流、毛商品流以及網(wǎng)絡(luò) 流的分解與合成等新課題。網(wǎng)絡(luò)流的應(yīng)用已遍及通訊、運(yùn)輸、電力、工程規(guī)劃、任務(wù)分派、 設(shè)備更新以及計(jì)算機(jī)輔助設(shè)計(jì)等眾多領(lǐng)域。（3）算法的實(shí)現(xiàn)Edmonds _Karp 算法建立在Ford-Fulkerson方法上的增廣路算法，與一般的Ford-Fulkerson算法不 同的是，它用廣度搜索實(shí)現(xiàn)對(duì)增廣路的尋找.以下為代碼：int n;long int c128 128:long maxflow int s, int tint p, q, queue ., u, v, pre 128;long

51、 int flow, aug;flow = 0;while truememset pre, 1, sizeof pre 丨；for(queue p = q = _ = s; p <= q; p+u = queue p ;for(v = 0; (v < n) && (pre t) < 0; v+) if (c u v > 0) && (prev < 0)pre v一 = u; queue +q= v;if pre t >= ： breakif (pre t < 0)breakaug = OxTfff;v = u , u=p

52、re ufor u = pre v 二 t ; v if c u v < aug aug = c u_ V-;for u = pre v 二 t ; vcuv -= aug; c v u += aug;flow += aug;return flow:3、二分圖(1) 含義的理解二分圖又稱作二部圖，是圖論中的一種特殊模型。設(shè)G=(V,E)是一個(gè)無向圖，如果頂點(diǎn)V 可分割為兩個(gè)互不相交的子集(A,B),并且圖中的每條邊(I, j)所關(guān)聯(lián)的兩個(gè)頂點(diǎn)1和j分 別屬于這兩個(gè)不同的頂點(diǎn)集(iinAjinB),則稱圖G為一個(gè)二分圖。2、相關(guān)應(yīng)用作為種數(shù)學(xué)模型，二分用途是十分有用的，許多問題可以用它來刻

53、劃。例如“資源匹配”、 “工作安排”、“人員擇偶”等等。而這就需要考慮匹配問題。匹配：給定一個(gè)二分圖G,在G的一個(gè)子圖M中，M的邊集中的任意兩條邊都不依 附于同一個(gè)頂點(diǎn)，則稱M是一個(gè)匹配。而二分圖最人匹配可以用最人流或者匈牙利算法。最大流在網(wǎng)絡(luò)流中有介紹。匈牙利算法為：(資料：百度百科)匈牙利算法是由匈牙利數(shù)學(xué)家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理（此定理使用于組合問題中。二部圖G中的兩部分頂點(diǎn)組成的集介分別為X, Y, Z,=X1, X2, X3.X4,Xm , Y=yl,y2, y3, y4 yn,G 中有一組無公共點(diǎn)的邊，一端恰好為組成X的點(diǎn)的充分必要條

54、件足：X中的任意k個(gè)點(diǎn)至少與Y中的k個(gè)點(diǎn)相鄰.（l<k<m）中充分性證明的思想，它是部圖匹配最常見的算法，該算法的核心就是尋找增 廣路徑，它是一種用増廣路徑求二分圖最大匹配的算法。算法的思路：不停的找增廣軌，并增加匹配的個(gè)數(shù)，增廣軌顧名思義是指一條町以使匹配數(shù)變多的路 徑，在匹配問題中,增廣軌的表現(xiàn)形式是一條”交錯(cuò)軌，也就是說這條由圖的邊組成的路 徑，它的第一條邊是冃前還沒有參與匹配的，第二條邊參與了匹配,第三條邊沒有最后 一條邊沒有參與匹配，并且始點(diǎn)和終點(diǎn)還沒有被選擇過這樣交錯(cuò)進(jìn)行，顯然他有奇數(shù) 條邊那么對(duì)于這樣一條路徑，我們可以將第一條邊改為己匹配，第二條邊改為未匹配 以此類推也就是將所冇的邊進(jìn)行反色"，容易發(fā)現(xiàn)這樣修改以后，匹配仍然是介法的, 但是匹配數(shù)增加了一對(duì)另外，單獨(dú)的一條連接兩個(gè)未匹配點(diǎn)的邊顯然也是交錯(cuò)軌可 以證明，當(dāng)不能再找到增廣軌時(shí),就得到了一個(gè)最人匹配這也就是匈牙