目錄

一、最大流有關(guān)的概念

例1

1、容量網(wǎng)絡(luò)的定義

2、符號設(shè)置

3、建立模型

3.1 每條邊的容量限制

3.2 平衡條件

3.3 網(wǎng)絡(luò)的總流量

4、網(wǎng)絡(luò)最大流數(shù)學(xué)模型

5、計(jì)算

二、最小費(fèi)用流

例2

【符號說明】

?【建立模型】

（1）各條邊的流量限制

（2）網(wǎng)絡(luò)總流量

（3）網(wǎng)絡(luò)總費(fèi)用

（4）中間點(diǎn)的流量平衡

【數(shù)學(xué)模型】

【模型求解】

?三、最大匹配問題

例3

?【問題假設(shè)】

【問題分析】

【符號設(shè)置】

?【數(shù)學(xué)模型】

【模型求解】

一、最大流有關(guān)的概念

最大流是應(yīng)用廣泛的一類問題，例如交通運(yùn)輸網(wǎng)絡(luò)中的人流、車流、物流；供水網(wǎng)絡(luò)中的水流、金融系統(tǒng)中的資金流；通訊系統(tǒng)中的信息流。上世紀(jì)50年代Ford，F(xiàn)ulkerson建立的《網(wǎng)絡(luò)流理論》是網(wǎng)絡(luò)應(yīng)用的基礎(chǔ)。

例1

如圖1所示網(wǎng)絡(luò)為輸油管道網(wǎng)絡(luò)，vs為起點(diǎn)，vt為終點(diǎn)，v1,v2,v3,v4為中轉(zhuǎn)站，邊上的數(shù)字表示該管道的最大輸油能力（t/h）。問如何安排各管道的輸油量，才能使得從vs到vt的輸油量最大。

1、容量網(wǎng)絡(luò)的定義

?設(shè)有連通圖G=(V,E)，G的每一條邊(vi,vj)上有非負(fù)數(shù)cij稱為容量，僅有一個入次為0的點(diǎn)vs稱為發(fā)點(diǎn)（源），一個出次為0的點(diǎn)vt稱為收點(diǎn)（匯），其余點(diǎn)位中間點(diǎn)，這樣的網(wǎng)絡(luò)G稱為容量網(wǎng)絡(luò)，記為G=(V,E,C)。如圖1所示。

2、符號設(shè)置

• Cij ?邊(i,j)的容量限制；
• fij ?邊(i,j)的實(shí)際流量；（稱f={fij}為網(wǎng)絡(luò)的一個流。）
• W ?網(wǎng)絡(luò)的總流量；

3、建立模型

3.1 每條邊的容量限制

3.2 平衡條件

對中間點(diǎn)u，流入=流出，即

3.3 網(wǎng)絡(luò)的總流量

稱發(fā)點(diǎn)流量之和或匯點(diǎn)流量之和為網(wǎng)絡(luò)總流量（忽略損失）。

4、網(wǎng)絡(luò)最大流數(shù)學(xué)模型

5、計(jì)算

?編寫例1的Lingo計(jì)算程序，將計(jì)算結(jié)果填入表1，將數(shù)據(jù)反映如圖1，得到圖2.

sets:
dian/vs v1 v2 v3 v4 vt/:;
bian(dian,dian)/vs,v1 vs,v3 vs,v4 v1,v2 v1,v3 v2,v3 v2,vt v3,vt v3,v4 v4,v3 v4,vt/:c,f;
endsets
data:
c=4 3 4 2 1 2 4 2 3 2 3;
enddata
max=w;
w=@sum(bian(i,j)|j#eq#6:f(i,j));
@for(bian(i,j):f(i,j)<c(i,j));
@for(dian(k)|k#ne#1#and#k#ne#6:@sum(bian(i,k):f(i,k))=@sum(bian(k,j):f(k,j)));

表1 流量分布（不唯一）

?如圖2所示，稱形如(vs,v4),(v4,vt),(v4,v3),(v1,v2),(v1,v3)為飽和邊;其余的邊都是非飽和邊。

要增大網(wǎng)絡(luò)的流量，必須對飽和邊擴(kuò)容??！

二、最小費(fèi)用流

設(shè)G=(V,E,C)為流量網(wǎng)絡(luò)，邊(i,j)除了容量限制cij外，還有因?yàn)榱髁慷a(chǎn)生的單位費(fèi)用dij(dij>0)，記為G=(V,E,C,d)。這時如果不管流量大小，而只把網(wǎng)絡(luò)流產(chǎn)生的費(fèi)用當(dāng)產(chǎn)目標(biāo)，最優(yōu)解必定是0，即各條邊的實(shí)際流量為0時費(fèi)用最小。研究方法必須改變?yōu)楸３至髁恳欢ǖ那闆r下，使得流量產(chǎn)生的總費(fèi)用最小。當(dāng)網(wǎng)絡(luò)流量保持最大而流量費(fèi)用最小的網(wǎng)絡(luò)流稱為最小費(fèi)用最大流。

例2

如圖3所示網(wǎng)絡(luò)G=(V,E,c,d)，每條邊有兩個數(shù)字，第一個是容量限制，第二個是流量產(chǎn)生的單位費(fèi)用。求該網(wǎng)絡(luò)的最小費(fèi)用最大流（最大流例1求得為7）。

【符號說明】

• G=(V,E,c,d] 如圖3所示網(wǎng)絡(luò)圖；
• Cij ?邊(i,j)的管道容量限制；
• Dij ?邊(i,j)的單位費(fèi)用；
• Xij ?邊(i,j)的實(shí)際流量；
• W ? 網(wǎng)絡(luò)G的總流量。

?【建立模型】

（1）各條邊的流量限制

（2）網(wǎng)絡(luò)總流量

（3）網(wǎng)絡(luò)總費(fèi)用

（4）中間點(diǎn)的流量平衡

【數(shù)學(xué)模型】

【模型求解】

編寫lingo求解程序，計(jì)算得個各條邊的實(shí)際流量見表2和總費(fèi)用為50.（總流量為7時）

sets:
dian/vs v1 v2 v3 v4 vt/:;
bian(dian,dian)/vs,v1 vs,v3 vs,v4 v1,v2 v1,v3 v2,v3 v2,vt v3,vt v3,v4 v4,v3 v4,vt/:c,x,d;
endsets
data:
c=4 3 4 2 1 2 4 2 3 2 3;
d=3 3 2 4 2 1 3 3 3 2 4;
enddata
min=@sum(bian:d*x);
w=@sum(bian(i,j)|j#eq#6:x(i,j));
@for(bian(i,j):x(i,j)<c(i,j));
@for(dian(k)|k#ne#1#and#k#ne#6:@sum(bian(i,k):x(i,k))=@sum(bian(k,j):x(k,j)));
w=7;

?表2 最小費(fèi)用的流量分布

?三、最大匹配問題

問題來源：

? 有n個人，m件工作，每個人的工作能力不同，各能勝任某幾項(xiàng)工作。假設(shè)每個只做一件工作；一件工作只需一個人做，怎樣分配才能使得盡量多的工人有工作。

?轉(zhuǎn)化為匹配問題：

• ? x1,x2,…,xn表示工人；
• y1,y2,…,ym表示工作,
• X表示{x1,x2,…,xn}, Y表示{y1,y2,…,ym}。

?這樣就產(chǎn)生一個二部圖G=(X,Y,E),其中E中的邊(xi,yj)就表示xi勝任工作yj。如圖4所示

?匹配定義：

二部圖G=(X,Y,E)，M是E的子集，M中任意兩條邊都沒有公共端點(diǎn)，則稱M是G的一個匹配（對集）。使得|M|達(dá)到最大的匹配稱為最大匹配。

例3

設(shè)有5位待業(yè)者，5項(xiàng)工作，他們各自能勝任的工作情況如圖5所示，設(shè)計(jì)一個就業(yè)方案，使盡量多人能就業(yè)。

?【問題假設(shè)】

一人最多一工作，一工作最多一人。

【問題分析】

?注意到，對xi來說，出次可能不唯一，但最多有一條邊可能實(shí)現(xiàn)；對yj來說，入次可能不唯一，但也最多一條邊實(shí)現(xiàn)。根據(jù)流量平衡，在xi前置vs作為發(fā)點(diǎn)；在yj后置vt作為匯點(diǎn)，將圖5改造為流量網(wǎng)絡(luò)，見圖六。

?如圖6所示流量網(wǎng)絡(luò)圖G=(V,E,C),其中每條邊的容量都為1.

【符號設(shè)置】

• G=(V,E,C)流量網(wǎng)絡(luò)圖，如圖6；
• vs 發(fā)點(diǎn)；
• vt 匯點(diǎn)；
• x1,…,x5,y1,…,y5，網(wǎng)絡(luò)中間點(diǎn)；
• Cij ?邊(i,j)的容量限制，且cij=1,(i,j)∈E；
• xij 邊(i,j)的實(shí)際流量，且只取0-1；

?【數(shù)學(xué)模型】

【模型求解】

? ?編寫Lingo程序，計(jì)算得到最大匹配為4，具體安排反映在圖6上，見圖7.

sets:
dian/vs x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 vt/:;
bian(dian,dian)/vs,x1 vs,x2 vs,x3 vs,x4 vs,x5 
x1,y1 x1,y2 x1,y3 x2,y1 x2,y4 x3,y4 x3,y5 x4,y5
x5,y4 x5,y5 y1,vt y2,vt y3,vt y4,vt y5,vt/:x,c;
endsets
data:
c=1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1;
enddata
n=@size(dian);
max=@sum(bian(i,j)|i#eq#1:x(i,j));
@for(bian:@bin(x));
@for(bian:x<c);
@for(dian(k)|k#ne#1#and#k#ne#n:@sum(bian(i,k):x(i,k))=@sum(bian(k,j):x(k,j))); 

文章來源地址http://www.zghlxwxcb.cn/news/detail-754075.html

到了這里，關(guān)于數(shù)學(xué)建?！畲罅鲉栴}（配合例子說明）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！