數(shù)學模型與計算機模擬

數(shù)學模型與計算機模擬

教學改革材料

數(shù)學模型與計算機模擬課程是以解決某個現(xiàn)實問題為目的，經(jīng)過分析、

簡化，將問題的內(nèi)在規(guī)律用數(shù)字、圖表，或者公式、符號表示出來，即經(jīng)

過抽象、歸納把事物的本質關系和本質結構用數(shù)學語言來描述，建立正確

的數(shù)學結構，并用科學的方法，通過編寫程序求解問題，得出供人們作分

析、預報、決策或者控制的定量結果。本課程的學習應注重學生的能力培

養(yǎng)。具體包括以下六個方面：

一、掌握與信息技術相關的自然科學和數(shù)學知識，并有創(chuàng)造性地將這

些知識應用于信息系統(tǒng)構建和應用的潛力；

二、為解決個人或組織機構所面臨的問題，能系統(tǒng)地分析、確定和闡

明用戶的需求；

三、能設計高效實用的信息技術解決方案；

四、能深刻理解成功的經(jīng)驗和標準，并能運用；

五、具有獨立思考和解決問題的能力；

六、具有團隊協(xié)作能力和論文寫作能力。

以上六個方面的要求與教育部高等學校計算機科學與技術教學指導委

員會制定的《高等學校計算機科學與技術發(fā)展戰(zhàn)略研究報告暨專業(yè)規(guī)范（試

行）》中計算機科學與技術專業(yè)（信息技術方向）人才培養(yǎng)要求和《信息工

程學院發(fā)展戰(zhàn)略綱要》中提出的堅持“知識、能力、素質協(xié)調(diào)發(fā)展，側重

于應用能力和自學能力的培養(yǎng)”的辦學方略相統(tǒng)一?；诖?，信息工程學

院對《數(shù)學模型與計算機模擬》課程的教學做了改革。

一、教學內(nèi)容上把傳統(tǒng)教學的“廣”，改為以運籌模型為主的“精二

經(jīng)過分析討論，將線性規(guī)劃模型、整數(shù)規(guī)劃模型、網(wǎng)絡模型、對策模型和

決策模型等運籌模型定為《數(shù)學模型與計算機模擬》課程的主要內(nèi)容，并

增加各模型的算法分析與編程實踐。

二、教學方式方法上由以往的講授為主，改為以學生為主的獨立思

考、分組討論，從探究實踐中歸納抽象理論的教學方法。在教學中教師選

定典型問題，引導學時討論，課后查閱相關資料。學生根據(jù)自己理解分析

問題，即分析問題的常量和變量的關系，把問題本身存在的邏輯關系找出

來，得出問題的數(shù)學結構，寫出數(shù)學模型，尋找適合的解法，并把算法的

每一步翻譯成高級語言（如C語言，VB等），根據(jù)解決問題的需要增加必

要的存儲變量實現(xiàn)算法，編寫完整程序求解問題。解決問題后再分析算法

的理論依據(jù)（正確性分析），并學習和借鑒已有經(jīng)驗。整個教學過程主要分

六步：一是提出問題；二是討論分析問題；三是建立數(shù)學模型；四是求解

模型；五是編寫程序驗證模型；六是歸納總結；（具體過程見模型解法）。

三、增加實驗實踐環(huán)節(jié)，提高應用能力。本課程開設實驗課，編寫了

實驗大綱和綜合實驗題目，并給出了參考程序。另外，每年組織學生參加

學院及全國大學生數(shù)學建模競賽，培養(yǎng)學生的協(xié)作能力和應用寫作能力。

四、本課程考核以建模和編寫程序、上機考試結合，注重能力考查。

附：部分教學講義和優(yōu)秀作業(yè)、論文、參考程序：

2

數(shù)學模型與計算機模擬

第2章線性規(guī)劃模型

1.問題的提出

某廠生產(chǎn)A,B兩種產(chǎn)品.生產(chǎn)A產(chǎn)品1kg,需用煤9t,電

力4000kwh,勞動量4人日;生產(chǎn)B產(chǎn)品1kg,需用煤5t,電力

5000kwh,勞動量10人日.現(xiàn)該廠有煤350t,電力20萬kwh,

勞動量300人日.生產(chǎn)A產(chǎn)品1kg可獲利潤1000元，生產(chǎn)B產(chǎn)

品1kg可獲利潤1500元，問應如何安排生產(chǎn)，才能使該廠獲

利最大？

2.問題的分析：

用xl表示A產(chǎn)品的數(shù)量，單位kg;

用x2表示B產(chǎn)品的數(shù)量，單位kg;

用w表示該廠的利潤；

本問題是:問xl,x2為何值時,W最大？

這就要建立W與xl,x2之間,xl與,x2之間的數(shù)量關系，這種數(shù)量關系就是

所謂的數(shù)學模型.

由于資源量的限制，所以xl,x2之間要滿足一定的數(shù)量關系，通常稱為約

束條件，所以這是一個約束條件下求最大值問題.

我們把滿足約束條件的xl,x2稱為可性解.記為(xl,x2)于是我們要在所有可

性解中，求出能使W最大的可行解，我們把這樣的可行解稱為最優(yōu)解.

所以如何建立模型，求出最優(yōu)解，是本問題的關鍵.

另外由于該廠所生產(chǎn)的產(chǎn)品，不見的都能賣出去，如果不能完全賣出去，就不

3

可能有從數(shù)學上推道出的利潤，為此我們假定該廠生產(chǎn)的產(chǎn)品都能賣出去,

這樣從數(shù)學上推道出的利潤就是該廠的實際利潤.

3.模型的建立

(1)利潤W與Xi,X2之間的數(shù)量關系

w=1OOOxj+1500—2

(2)X]與,X2之間的數(shù)量關系，即約束條件

9+5<350

4000修+5000220x104

<

4/+10A:2<300

,x2>0

在數(shù)學上把這個約束條件下求最大值問題.表述為：

maxw=1000/+1500x2

s.t.9%]+5JC2<350

4

<4000%+5000工2<20x10

4%]+10JC2<300

X],x2>0

并稱為線性規(guī)劃模型.

或者等價地化為：

4

minw=-1000x1-1500x2

s.t.9%]+5x2+匕=350(1)

4%[+5x2+x4=200(2)

2%]+5x2+x5=150(3)

4.模型的求解

⑴在目標函數(shù)中，看xi、X2前面的系數(shù)-1000、-1500那個小，因-1500

小，它對應的是X2,由X2做如下操作

(2)在約束條件各方程中分別用大于零的X2前面系數(shù)除右邊的常系數(shù)，即

(3)再看那個小，因30小它對應的是方程(3),由方程⑶做如下操作:

在方程⑶解出X2：2]

x9=30——x11——x

255

并代入目標函數(shù)和方程(1)、(2)中得

minw=-400xj+300JC5-45000

s.t.7%—/+%3=200(1)

2xy-x5+x4=50⑵

212

—%,+—JC5+A：2=30(3)

⑴在目標函數(shù)中，看xi、X5前面的系數(shù)-400、300那個小，因-400小,

它對應的是X],由xi做如下操作

5

(2)在約束條件各方程中分別用大于零的xi前面系數(shù)除右邊的常系數(shù)，即

^■二28.6,^-=25,—=75

720.4

(3)再看哪個小，因25小它對應的是方程(2),由方程(2)做如下操作:

在方程(2)解出x,

“11

X.=25——xA+—x

122

并代入目標函數(shù)和方程(1)、(3)中得

minw=-400x,+300x5-45000

s.t.7X1-x5+%3=200(1)

2xt-x5+x4=50(2)

21”

—+%2=30⑶

xl,x2,x3x4,x5>0

5.線性規(guī)劃模型的標準形式

具有如下形式的數(shù)學模型：

，N

minz=ZcJXJ+c0

<s.t.￡atjx=儲(z=1,2,…加)

j=i

Xj>0(j=l,2,…，N)

稱為標準形式的線性規(guī)劃模型,是指基變量的個數(shù)為m,且

國>0(i=1,2,---,m)

6.標準形式線性規(guī)劃模型的算法

6

⑴求k使Ck為與中最小的；

⑵求g使agk為bi/aik,aik>0中最小的；

⑶第g個方程兩邊除以agk；

(4)在第g個方程中求出Xk,代入到目標函數(shù)及第i個方程中去;(i=l,2,…

m,i!=g);

(5)讓Ck=O重復上述操作，直到4中沒有負數(shù)為止.

6.1求k使c[k]為題]中最小的

設置變量s,s=c[l];k=l.如果則讓s=c[j],k=j,否則s與k的數(shù)據(jù)

保持不變，分別讓j=2,…N做上述操作后，因為對于任意的j,min<=c[j],而

s=c[k],所以c[k]為c[j]中最小的.

s=c[l];

k=l;

for(j=2;j<=N;j++)

if(s<c[j])

{s=c[j];k=j;}

6.2求g使agk為bjaik,aik>0中最小的；

若alk<=0則讓i=l,如果以<=0,讓i=i+l,直至！Iai+(k>0為止,那么:aik<=0,

a2k<=0，,,,ai.lk<=O,.Mai+ik>0

a[m+l][N+l]a[iJ[N+l]=b[i](i=l,2,...m)

i=l；

while(a[i][k]<=l)

i=i+l;

7

s=a[i][N+l]/a[i][k|;

g=i；

for(j=i+l;j<=N;j++)

if(s<a皿N+l]/a皿k])

{if(s=a[j][N+l]/a[j][kJ);g=j;}

6.3第g個方程兩邊除以a[g][k]

讓s=a[g][k]

Y0門工-g

二％j一

<=&gj

a

s

bg

b=——

s=a[g][k];s

for(j=l;j<=N+l;j++)

a[g][j]=a[g][j]/s；

6.4第i個方程-第g個方程乘a[i][k]

s=aik

N

工。內(nèi)二嗎

j=l

N%<=a「saj

<Va.x=b」」?(j=l,2…N)

乙」8JJ;8n=><

j=lbj=hj-sbg

NN

EaijXj-sE%Xj=bj-sbg

j=lj=l

N

工包一saGXj=b「sbg

I>1

for(i=l;i<=m;i++)

8

{if(i!=g)

s=a[i][k];

for(j=l；j<=N+l;j++)

a[i]|j]=a[i][j]-a[g][j]*s;}

6.5在第g個方程中求出x[k],代入目標函數(shù)

NN

Z=ECjXj+Co-CjW/Xj-bg)

>1j=l

N

j=i

Cj=Cj—Ck%;Co=Co+Cjbg

s=c[k];

for(j=l;j<=N+l;j++)

c[jj=c[j]-c[k]*a[g][j];

6.6標準形式線性規(guī)劃模型算法C語言表述

while(e<=n)

{s=c[l];

k=l;

for(j=2;j<=N;j++)

if(s<c[jj){s=c[j];k=j;}/*(!)*/

9

i=l；

while(a[i][k]<=l)

i=i+l;s=a[i][N+l]/a[i][k];

g=i；

for(j=i+l;j<=N;j++)

if(s<a[j][N+l]/a[j][k])

{if(s=a[j][N+lJ/a[j][k]);g=j;}/*(2)*/

s=a[g][k];

for(j=l;j<=N+l;j++)

a[g][j]=a[g][j]/s;/*(3)*/

for(i=l;i<=m;i++)

{if(i!=g)s=a[i][k];

for(j=l;j<=N+l;j++)

a[i]Ljl=a[i]U]-4g][j]*s;}/*(4)*/

s=c[kj;

for(j=l;j<=N+l;j++)c[j]=c|j]-s*a[g][j];

c[O]=c[O]+s*a[g][N+l]

e=0;

for(j=l;j<=N;j++)

if(c[j]>0)

e=e+l;

10

參考程序：

#include<stdio.h>

#include<math.h>

#defineN5

#definem3

#definen2

staticfloatc[N+l]={0,-1000,-1500},aLm+l][N+2]={{0},{0,9,5,1,0,0,350},

{0,4,5,0,1,0,200},{0}2,5,0,0,1,150});

staticintt[m+l]={0,3,4,5};

main()

(

inti,j,g,k,e;

floats,x[N+l]={0};

e=0;

for(j=l;j<=N;j++)

if(c[j]>=0)

e=e+l;

while(e<=n)

{s=c[l];

k=l;

for(j=2;j<=N;j++)

if(s<c[jj){s=c[j];k=j;}/*⑴*/

ii

i=l；

while(a[i][k]<=l)

i=i+l;s=a[i][N+l]/a[i][k];

g=i；

for(j=i+l;j<=N;j++)

if(s<a[j][N+l]/a[j][k])

{if(s=a[j][N+lJ/a[j][k]);g=j;}/*(2)*/

s=a[g][k];

for(j=l;j<=N+l;j++)

a[g][j]=a[g][j]/s;/*(3)*/

for(i=l;i<=m;i++)

{if(i!=g)s=a[i][k];

for(j=l;j<=N+l;j++)

a[i]Ljl=a[i]U]-4g][j]*s;}/*(4)*/

s=c[kj;

for(j=l;j<=N+l;j++)c[j]=c|j]-s*a[g][j];

c[O]=c[O]+s*a[g][N+l]

e=0;

for(j=l;j<=N;j++)

if(c[j]>0)

e=e+l;

12

for(i=1;i<=m;i++)x[t[i]]=a[i][N+l];

for(j=l;j<=N;j++)printf("\nx[%dJ=%8.0f",j,x[j]);printf("\nmin=%8.0f",c[0J);

)

程序運行結果：

x[l]=0

x[2]=0

x[3]=350

x[4J=200

x[5]=150

min=55000

13

第三章超照規(guī)劃模型

一.提出問題：工廠選址

某企業(yè)欲建工廠，可選廠址有A1、A2、A3、A,四處，每個地址至多可建一

個工廠，在各地址建立工廠的生產(chǎn)能力、在各地址經(jīng)營工廠單位時間的固

定成本、產(chǎn)品運往各需求點的單位運費如下表:

單\?

生產(chǎn)能力固定成

B1B2B3B4

（件）本（元）

Al412411431

A221089532

A385116634

A412394435

量（件）2221

問應如何選擇廠址和安排運輸計劃，才能得到經(jīng)濟上花費最少的方案

二.分析問題

1.A]、A2、A3、A4各處都有可能建廠，用變量y[i]來表示是否建廠

在i地址建廠

y[i]=i=L2,3,4;

0在i地址不建廠

2.設從i地址運到j需求點的運輸量可設為為整數(shù)

3.運到各點的量應不小于需求（x[l][j]+x⑵U]+x[3][j]+x[4]|j]>=b[j]）；

4.各廠的生產(chǎn)總量不超過生產(chǎn)能力

（x[i][l]+x[i]⑵+x[i][3]+x[i][4]<=d[i]*y[i]i=l,2,3,4）；

5.運到各需求點的量如何計算bl[j]=x[l]|j]+x[2][j]+x[3][j]+x[4][j]

j=l,2,3,4;

14

6.各廠的生產(chǎn)總量al[i]=x[i][l]+x[i]⑵+x[i][3]+x[i][4];

7.目標函數(shù)：總費用2=建廠費用+運輸費用

8.運輸費用=單位運輸費用*運輸量(從i地址運到j需求點單位運輸費

用已知，從i地址運到j需求點的運輸量可設為x[i][j])

三.模型建立

根據(jù)分析建立整數(shù)規(guī)劃模型：

設，4建,(i=l,2,…,4),馬表示從，?點運到/點的貨物數(shù)量(i,j=l,2,…,4),

建立如下整數(shù)規(guī)劃模型：

’444

minz=

/=1/=1j=\

4

Z%44x(，=12…,4)

Vj=l

4

Z/2%(1=l,2,…,4)

/=1

Xg>0,yi=0或1

其中“表示從i點到/點的單位運費(i,)=1,2,…,4),

《為A,點處建廠經(jīng)營的單位固定成本(i=l,2,…,4),

勺表不需求點4處的需求量(j=l,2,…，4),

4表示4處的生產(chǎn)能力a=1,2,…,4)。

四.解題方法

根據(jù)題目可知x[i][j]>=0,x[i][j]<=y[i]*d[i],將所有可行方案一一列舉,

計算總費用，比較求得總費用最小的方案(枚舉或者叫窮舉)

注：最小費用唯一，方案可有多種。

15

五.設計算法求解

1.環(huán)嵌套，解決在i地址是否建廠，如for(y[i]=0;y[i]<=l;y[i]++)等,

i=l,2,3,4

2.循環(huán)嵌套，解決從i地址運到j需求點的貨物數(shù)量x[i][j],如

for(x[i][j]=0;x[i][j]<=d[i]*y[i];x[i][j]++)o

3.考察兩條件是否同時成立：

運到各需求點的貨物應不小于需求(blU]>=b[j]j=l,2,3,4)；

各廠的生產(chǎn)總量不超過生產(chǎn)能力(al[i]<=d[i]*y[i]i=l,2,3,4)；

4.計算：總費用2=建廠費用+運輸費用

建廠費用=2[1]*丫[1]+2[2]*丫[2]+2[引*y[3]+a[4]*y[4]

運輸費用=c[l][l]*x[l][l]+c[2][2]*x[2][2]+c[2][2]*x[2][2]+

c[2][2]*x[2][2]

5.比較總費用是否最小，并記錄最佳方案(可能有多種)：

min=le+4if(z<min){min=zv[i][j]=x[i][j];)

6、輸出最小費用和方案。

六.驗證結果(min=92在A1和A4處建廠，

v[l][l]=v[l][3]=2,v[4][2]=2,v[4][4]=L其他都為0)。

七.參考程序：

#defineSTEP1

#definem4

#definen4

staticfloatc[m][n]={4,12,4,11,2,10,8,9,8,5,11,6,12,3,9,4},

16

a[m]={31,32,34,35},b[n]={2,2,2,1},d[m]={4,5,6,4};

main()

{floaty[n],b1[n],a1[m],x[m][n],v[m][n],z=0,min=1e+4,t=0;

inti,j;

for(y[0]=0;y[0]<=l;y[0]++)

for(y[lj=0;y[l]<=1;y[l]++)

for(y[2]=0;y[2]<=l;y[2]++)

for(y[3]=0;y[3]<=l;y[3]++)

for(x[0][0]=0;x[0][0]<=b[0]*y[0];x[0][0]=x[0][0]+STEP)

for(x[0J[l]=0;x[0][1]<=b[1]*y[0];x[0][1]=x[0][l]+STEP)

for(x[0][2]=0;x[0][2]<=b[2]*y[0];x[0][2]=x[0][2]+STEP)

for(x[0][3]=0;x[0][3]<=b[3]*y[0];x[0][3]=x[0][3]+STEP)

for(x[l][0]=0;x[l][0]<=b[0]*y[l];x[l][0]=x[l][0]+STEP)

for(x[l][l]=0;x[l][l]<=b[l]*y[l];x[l][l]=x[l][l]+STEP)

for(x[l][2]=0;x[l][2]<=b[2]*y[l];x[l][2]=x[l][2]+STEP)

for(x[l][3]=0;x[l][3]<=b[3]*y[l];x[l][3]=x[l][3]+STEP)

for(x[2J[0J=0;x[2][0]<=b[0]*y[2];x[2][0]=x[2][0J+STEP)

for(x[2][l]=0;x[2][l]<=b[l]*y[2];x[2][l]=x[2][l]+STEP)

for(x⑵⑵=0;x⑵⑵<=b⑵*y[2];x⑵[2]=x⑵⑵+STEP)

for(x[2][3]=0;x[2][3]<=b[3]*y[2];x[2][3]=x[2][3]+STEP)

for(x[3][0]=0;x[3][0]<=b[0]*y[3];x[3][0]=x[3][0]+STEP)

for(X[3][l]=0;x[3][l]<=b[l]*y[3];x[3][l]=x[3][l]+STEP)

17

for(x[3][2]=0;x[3][2]<=b[2]*y[3];x[3][2]=x[3][2]+STEP)

for(x[3][3]=0;x[3][3]<=b[3]*y[3];x[3][3]=x[3][3]+STEP)

for(i=0;i<4;i++)

al[i]=O;

for(j=0;j<4;j++)

bl[j]=O;

for(i=0;i<4;i++)

for(j=0;j<4;j++)

{al[i]=al[i]+x[i]|j];

bl[j]=blU]+x[i][j]；)

for(i=0;i<4;i++)

if(al[i]<=d[i]*y[i])

t++；

for(j=0;j<4;j++)

if(bl[j]>=b[j])

t++；

if(t==8)

(

for(i=0;i<4;i++)

z=z+a[i]*y[i];

for(i=0;i<4;i++)

18

for(j=0;j<4;j++)

z=z+c[iJ[j]*x[i][j]；

if(z<=min)

{min=z;printf("min=%f\n",min);

for(i=0;i<4;i++)

for(j=0;j<4;j++)

printf("v[%dJ[%d]=%fm",i,j,v[iJ[j]=x[i]Lj])；}}

z=0;

t=0;

)

printf("min=%f\n",min);

for(i=0;i<4;i++)

for(j=0;j<4;j++)

printf("v[%d][%d]=%3f\n",i,j,v[i]|j]);

)

19

第五章最短路問題

上圖是十一個城市的交通示意圖(單位：千米)求解下列問題：

1、寫出求解從編號為1到編號為，?城市之間最短行駛距離的算法

(i=2,3,…,11)

2、求出從編號為1到編號為i城市之間的最短行駛距離(i=2,3,…,11)

3、編寫求編號為1的城市到其他城市之間的最短路算法程序

解：設置常量〃，〃表示城市的最大編號，即〃=11

設置二維數(shù)數(shù)組#。由w[n+l][n+l],具體數(shù)據(jù)如下

vu[l][2]=676w[U[3]=1813w⑵⑷=842

w[2][5]=511w[3][5]=695w[3][6]=811

w[4][7]=110卬⑷[8]=967w[5][9]=943

w[6][10]=1376w[7][8]=63948][9]=902

w[8][ll]=607w[9[10]=367w[9][ll]=672

其余數(shù)據(jù)均設置為0.

設置一維數(shù)數(shù)組加〃d[n+l],磯i]表示第一個城市到第i個城市的

最短行駛距離(i=2,3…J[l]<=0o

1、求從第一個城市到第i個城市的最短行駛距離的算法如下:

20

d[i]={磯刃+加i]H0}(z=2,3…,〃)

2、其求解過程如下：

d⑵=mm[d[j]+>V[J][Z]|VV[J][Z]H0}

d[2]=d[\]+w[l][2]

d[2]=676

2

刈3]=mm{d[j]+W[j][i^j][i]豐0}

43]=rf[l]+w[l][3]

磯3]=1813

d[4]=mjn{j[j]+w[j][/]|同加目W0}

d[4]=d[2]+w[2][4]

J[4]=1518

4

川5]=min[d[j]+w[j][i^w[j][i]^0}

d[2]+w[2][5]

d[5]=min<\=1187

J[3]+w[3][5]

d[6]=min{j[j]+w[j][z]|w[j][z]H0}

d[6]=d[3]+w[3][6]

d[6]=2624

譏7]=min{d[j]+w[j][/]|w[j][z]+0}

磯7]=磯4]+w[4][7]

叩]=1628

d[8]=mm{d[j]+w[j][i]\w[j][z]*0}

J[4]+w[4][8]

J[8]-min?\=2267

J[7]+w[7][8]

21

7

48]=min{d[j]+w[j][i^w[j][i]H0}

J[4]+w[4][8]

J[8]=min<>=2267

d[7]+卬[7][8]

8

d[9]=min{d[j]+vv[j][/]|vv[J][?]=0}

d[5]+w[5][9]

J[9]=min<\=2130

J[8]+w[8][9]

9

d[10]=min{j[j]+vu[j][/]|4j][/]Ho)

J[6]+wf6][10]

J[10]=min<\=2497

J[9]+w[9][10]

io

d[l1]=min{j[j]+w[j][z]|w[j][?-]H0}

J[8]+w[8][l1]

J[ll]=min<卜=2802

J[9]+49][11]

最考程序:

#include<stdio.h>

#definen11

voidmain()

(

longi,j,k,w[nJ[n+l]={0},d[n+l]={0},c[n+l],t；

w[l][2]=676;

w[lj[3]=1813;

w[2][4]=842;

w[2J[5]=511;

w[3][5]=695;

w[3][6]=811;

22

w[4][7J=110;

w[4][8]=967;

w[5][9]=943;

w[6J[10]=1376;

w[7][8]=639;

w[8][9]=902;

w[8][11]=607;

w[9J[10]=367;

w[9][11]=672;

for(i=l;i<n;i++)

(

for(j=i+l;j<=n;j++)

{if(w[i][j])dU]=d[i]+w[i]UJ；

for(k=j-l;k>l;k-)

if(w[k][j])

if(w[k][j]+d[k]<d[j])

dU]=w[k][j]+d[k];}}

for(j=l；j<=n;j++)printf("\nd[%ld]=%5d",j,d[j]);

for(j=2;j<=n;j++)

{t=l;c[t++]=j;i=j;

for(k=j-1;k>1;k—)

if(w[k][i])

23

if(w[k][i]==d[i]-d[k])

{c[t++]=k;i=k;}

printf("\nd[lj");

while((-t)!=O)

printf("->d[%d]",c[t]);

程序運行結果:

d[lj=0

d[2]=676

d[3]=1813

d[4J=1518

d[5J=1187

d[6J=2624

d[7J=1628

d[8]=2267

d[9J=2130

d[10]=2497

d[ll]=2802

d[lj->d[2]

d[lj->d[3]

24

d[l]->d[2J->d[4]

d[lj->d[2]->d[5]

d[l]->d[3]->d[6]

d[lJ->d[2J->d[4]->d[7]

d[1]->d[2]->d[4]->d[7]->d[8]

d[lJ->d[2J->d[5]->d[9]

d[1]->d[2]->d[5]->d[9]->d[10]

d[1]->d[2]->d[5]->d[9]->d[11]

25

數(shù)學建模獲獎論文

產(chǎn)品加工模型

摘要：社會經(jīng)濟生活中，我們常會遇到工廠在一段時期內(nèi)所生產(chǎn)的產(chǎn)品的

最大收益問題，如產(chǎn)品加工等，這時，我們不僅要考慮產(chǎn)品加工的當前經(jīng)

濟效益，還要考慮銷售及設備投入對整體經(jīng)濟效益的影響。本文涉及的問

題是在五件產(chǎn)品的加工工序一定的情況下，求出最優(yōu)的生產(chǎn)安排并考慮增

加設備的投入問題。我們也建立了一個對此問題最優(yōu)化的數(shù)學模型。

miny=min{"Ii=1,2,3…}

s.t.Fi=max{57Ij=1,2,3,4}

其中耳表示完成所有任務的第i種可行方案；

S」表示第/種設備完成所有任務的最短時間，即

58

m=ln=l

其中W表示第j種設備在加工第m種產(chǎn)品的第n工序時的等待時間；

Jmn

A表示第j種設備在加工第m種產(chǎn)品的第n工序的時間；

jnn

根據(jù)題目第（1）問已知條件可計算出四種設備完成任務的總時間依次為：

42、38、62、70；

生產(chǎn)五種產(chǎn)品所需的時間依次為:44、16、53、54、45。

于是可得設備的優(yōu)先生產(chǎn)順序為：設備4—＞設備3—＞設備1—＞設備2；

產(chǎn)品的優(yōu)先生產(chǎn)順序為：產(chǎn)品4—＞產(chǎn)品3—＞產(chǎn)品5—＞產(chǎn)品1—＞產(chǎn)品2o

再運用多設備加工多產(chǎn)品的啟發(fā)式方法和設備完成加工任務的最短路算

法，求出各設備的加工流程和所用時間（包括加工中的等待時間）如下：

26

設備4：完成

設備3：3—Jl—J4—J5—J2—A1，^5」T4—\68完成

設備1：2^^1-^3—^_?4—^5^~?3—^67完成

設備2：4^^5—完成

即完成所有加工任務的最短時間為70,同時保證了各產(chǎn)品的最短加工時間。

設備1：■設備2：設備3：設備4：■

備注：空白格表示產(chǎn)品在進入下一個工序時所等待的時間。

對問題(2)建議增加設備4,在保證各產(chǎn)品最短加工周期的前提下求

出了最小加工時間為62。方法同上。

設備3：^5—^2—^4-^62完成

設備4：(3)3」—(7)4—J(4)43T58完成

設備1：2—^(7)1—5—^~?4^^(6)3^^56完成

設備2：4—^(3)5—^1—^2—^(7)3^^?48完成

新增設備4：5-^->2—^(10)5—J(24)1—J5」^6O完成

數(shù)據(jù)如下表：

27

設備1：?設備2：設備3：?設備4：?設

備5：■

備注：空白格表示產(chǎn)品在進入下一個工序時所等待的時間。

關鍵詞：啟發(fā)式方法，最短路算法；

一.問題的提出

產(chǎn)品加工問題

某機械廠加工廠產(chǎn)品都是單件性的，其中有一車間共有4種不同設備,

現(xiàn)接受5件產(chǎn)品的加工任務，每件產(chǎn)品接受的程序在指定的設備上加工，

其工序與加工周期如下表：（S-設備號、T一周期）

工

12345678

序

產(chǎn)

品STSTSTSTSTSTSTST

138122432446

214452334

3334711522018

28

427364211141633

54102438441123641

要求：1、每件產(chǎn)品必須按規(guī)定的工序加工，不得顛倒。

2、每臺設備在同一時間只能擔任一項任務。（每件產(chǎn)品的每個工序

為一個任務）。

問題：1、求出生產(chǎn)安排，希望在盡可能短的時間里，完成所接受的全部任

務。

2、如果考慮增加設備一臺，你有什么建議。

二、對題中所給模型的分析

社會經(jīng)濟生活中，我們常會遇到工廠在一段時期內(nèi)所生產(chǎn)的產(chǎn)品的最

大收益問題，如產(chǎn)品加工等，這時、我們不僅要考慮產(chǎn)品加工的當前經(jīng)濟

效益，還要考慮銷售及設備投入對整體經(jīng)濟效益的影響。本文涉及的問題

是在五件產(chǎn)品的加工工序一定的情況下，求出最優(yōu)的生產(chǎn)安排并考慮增加

設備的投入問題。我們也建立了一個對此問題最優(yōu)化的數(shù)學模型。

miny=min{^\i=1,2,3…}

）s.t.E=max{SJj=1,2,3,4}

其中耳表示完成所有任務的第i種可行方案；

Sj表示第/種設備完成所有任務的最短時間，即

58

m=ln=l

其中W表示第j種設備在加工第m種產(chǎn)品的第n工序時的等待時間；

Jmn

A表示第j種設備在加工第m種產(chǎn)品的第n工序的時間；

jnn

根據(jù)題目第（1）問已知條件可計算出四種設備完成任務的總時間依次為：

29

42、38、62、70；

生產(chǎn)五種產(chǎn)品所需的時間依次為：44、16、53、54、45。

于是可得設備的優(yōu)先生產(chǎn)順序為：設備4——＞設備3——＞設備1——＞設

備2；

產(chǎn)品的優(yōu)先生產(chǎn)順序為：產(chǎn)品4——＞產(chǎn)品3——＞產(chǎn)品5——＞產(chǎn)品1——＞

產(chǎn)品2。

再運用多設備加工多產(chǎn)品的啟發(fā)式方法和設備完成加工任務的最短路算

法，求出各設備的加工流程和所用時間（包括加工中的等待時間）如下：

設備4：完成

設備3：3—J1—J4—J5—J2—J4—。68完成

設備1：^5—^67完成

設備2：4^^5—U]—完成

即完成所有加工任務的最短時間為70,同時保證了各產(chǎn)品的最短加工時間。

設備1：■設備2：設備3：■設備4：■

備注：空白格表示產(chǎn)品在進入下一個工序時所等待的時間。

30

對問題（2）建議增加設備4,在保證各產(chǎn)品最短加工周期的前提下求

出了最小加工時間為62。方法同上。

設備3：^~?5^_?4^~>62完成

設備4：(3)3—j(7)43T(4)4」^?58完成

設備1：2^^(7)1^^3—^-?(1)5^^4—^(6)3—^56完成

設備2：4-^(3)5—^1—^2-^(7)3^~?48完成

新增設備4：5—^?2—^(10)5^^(24)]—^5—i~?60完成

設備1：?設備2：設備3：■設備4：■新增

設備4：■

備注：空白格表示產(chǎn)品在進入下一個工序時所等待的時間。

三、對所建模型的驗證

根據(jù)所建模型

31

miny=min{^Ii=1,2,3---}

s￡E=max{5jlj=1,2,3,4}

其中耳表示I完成所有任務的第i種可行方案；

S」表示第/種設備完成所有任務的最短時間，即

58

s=yy⑸+Aj）

JJnnJmn

m=ln=l

其中W表示第j種設備在加工第m種產(chǎn)品的第n工序時的等待時間；

Jmn

A表示第j種設備在加工第m種產(chǎn)品的第n工序的時間；

jnn

進行驗證，得出在第（1）問題中的最短加工時間為70,并找出了具體

加工流程，求出了產(chǎn)品1到產(chǎn)品5的最短加工依次時間為69、29、67、68、

70,完成所有產(chǎn)品的最小總時間為303,對第（2）問題增加設備4之后的

最短加工時間為62,并找出了具體加工流程，求出了產(chǎn)品1到產(chǎn)品5的最

短加工依次時間為59、29、56、62、60,,完成所有產(chǎn)品的最小總時間為

266o

四、參考文獻

[1]塘煥文賀明縫數(shù)學模型引論。北京：科學普及出版社，1982

[2]姜啟源數(shù)學模型第三版北京：高等教育出版社，2003

[3]雷功炎數(shù)學模型講義北京：北京大學出版社，1999

32

預防與控制傳染病模型

摘要

為了定量地研究傳染病的傳播規(guī)律、有效地預測和控制傳染病的蔓延,

本文建立了一個能夠有效地預測以及能為預防和控制傳染病提供可靠、足

夠信息的數(shù)學模型：

=—&/(，)+〃)(，)+，(，)

at

x(q)=—

)(1)=)Q-o)

其中：

1、x(t):表示t時刻已發(fā)病病例的累計人數(shù)；

2、y(t)：表示t時刻與已發(fā)病病例直接接觸的現(xiàn)有人數(shù)；

3、p(t)：表示t時刻直接確定為發(fā)病病例與已發(fā)病但沒有被政府機關、

醫(yī)療機構發(fā)覺的發(fā)病人數(shù)之和；

4、q(t)：表示t時刻直接確定為疑似病例和與已發(fā)病病例直接接觸過

但還沒有被府機關、醫(yī)療機構發(fā)覺的發(fā)病人數(shù)之和；

5^%：表示在上,?。?=0,…，〃-1)這一時段內(nèi)發(fā)病病例的治愈率；

6、k表示在忙…1)這一時段疑似病例轉化為發(fā)病病例的

轉化率；

7、c”表示在上,(+/(i=0,…,〃-1)這一時段與發(fā)病病例接觸而轉化為疑

似病例的轉化率；

33

8、4：表示在t，7；+Ja=(),…，〃-1)這一時段，從疑似病例中被而成為健

康人的排除率。

9、T,表示在怔,?。?i=0,…，〃-1)這一時段的起始時刻或終止時刻。

并做了如下工作：

(1)對附件1所提供的一個早期的模型的合理性和實用性進行了評價。

(2)在此基礎上建立了優(yōu)于附件1中的模型；特別說明了要建立一個真

正能夠預測以及能為預防和控制提供可靠、足夠的信息模型的困難所在。

對于衛(wèi)生部門所采取的措施給出了評論：提前或延后5天采取嚴格的隔離

措施，對疫情傳播所造成的影響做出了估計。

(3)給當?shù)貓罂瘜懥艘黄ㄋ锥涛?，說明建立傳染病數(shù)學模型的重要

性。

34

一、問題的提出

SARS(SevereAcuteRespiratorySyndrome,嚴重急性呼吸道綜合癥，

俗稱：非典型肺炎)是21世紀第一個在世界范圍內(nèi)傳播的傳染病。SARS

的爆發(fā)和蔓延給我國的經(jīng)濟發(fā)展和人民生活帶來了很大影響，我們從中得

到了許多重要的經(jīng)驗和教訓，認識到定量地研究傳染病的傳播規(guī)律、為預

測和控制傳染病的蔓延創(chuàng)造條件的重要性。為此我們做了如下工作：

(1)對附件1所提供的一個早期的模型的合理性和實用性進行了評價。

(2)在此基礎上建立了優(yōu)于附件1中的模型；特別說明了要建立一個真

正能夠預測以及能為預防和控制提供可靠、足夠的信息模型的困難所在。

對于衛(wèi)生部門所采取的措施給出了評論：提前或延后5天采取嚴格的隔離

措施，對疫情傳播所造成的影響做出了估計。

(3)給當?shù)貓罂瘜懥艘黄ㄋ锥涛模f明建立傳染病數(shù)學模型的重要

性。

二、對附件1中一個早期模型的評價

為定量地研究傳染病SARS的傳播規(guī)律、為預測和控制傳染病的蔓延創(chuàng)

造條件，附件1提出了如下模型：

假定初始時刻的病例數(shù)為No,平均每病人每天可傳染《個人(〃一般為

小數(shù))，平均每個病人可以直接感染他人的時間為/天。則在￡天之內(nèi)，

病例數(shù)目的增長隨時間看(單位天)的關系是：

35

N(t)=No(1+X)1

(1)

不妨對關系式(1)在形式上做如下變換，若令：

(1+=e'

(2)

k=ex

(3)

則(1)式變?yōu)椋?/p>

N(t)=N。*

(4)

所以根據(jù)附件1的描述：“參數(shù)密口/具有比較明顯的實際意義。/可理

解為平均每個病人在被發(fā)現(xiàn)前后可以造成直接傳染的期限，在此期限后他

失去傳染作用，可能的原因是被嚴格隔離、病愈不再傳染或死去等等。從

原理上講，這個參數(shù)主要與醫(yī)療機構隔離病人的時機和隔離的嚴格程度有

關，只有醫(yī)療機構能有效縮短這個參數(shù)。但我們分析廣東、香港、北京現(xiàn)

有的數(shù)據(jù)后發(fā)現(xiàn)，不論對于疫情的爆發(fā)階段，還是疫情的控制階段，這個

參數(shù)都不能用得太小，否則無法描寫好各階段的數(shù)據(jù)?！备郊?的模型可

最確地表示為：

NNTi<t<Ti+l(z=O,---n-1)

(5)

其中N注［=NJ&(i=0,--??-1)

(6)

36

0<7；.+1-7：<L(z=0,-???-1)

(7)

或表示為:

g-0(8)

N(Tj=Ni

所以附件1表明，不同階段病例數(shù)是按照指數(shù)規(guī)律增長的，只不過是各

階段的增長率的大小不同而已。其文中的陳述：

“參數(shù)儂然代表某種社會環(huán)境下一個病人傳染他人的平均概率，與全

社會的警覺程度、政府和公眾采取的各種措施有關。在疾病初發(fā)期，社會

來不及防備，止匕時K值比較大。為了簡單起見，我們從開始至到高峰期間均

采用同樣的儂（從擬合這一階段的數(shù)據(jù)定出），即假定這階段社會的防范

程度都比較低，感染率比較高。到達高峰期后，我們在10天的范圍內(nèi)逐步

調(diào)整傕到比較小，然后保持不變，擬合其后在控制階段的全部數(shù)據(jù)，即認

為社會在經(jīng)過短期的劇烈調(diào)整之后，進入一個對疫情控制較好的常態(tài)。顯

然，如果疫情出現(xiàn)失控或反復的狀態(tài)，則罐需要做更多的調(diào)整?！笔怯幸?/p>

定的道理的，具有階段性的實用性。但附件一提供的模型過于簡單，為此

我們需要建立新的模型。

三、一個改進的模型

針對附件一提供的模型過于簡單，我們建立如下模型：

37

整=-aM)+，y(f)+p(f)

at

?=c/(f)—4y(f)+q(f)T.<t<TM(f=0,-/z-1)

at

x(rJ=x(T-。)

)(1)=Ml-。)

(9)

其中：

1、x(t)：表示t時刻已發(fā)病病例的累計人數(shù)；

2、y(t)：表示t時刻與已發(fā)病病例直接接觸的現(xiàn)有人數(shù)；

3、p(t)：表示t時刻直接確定為發(fā)病病例與已發(fā)病但還無被政府機關、

醫(yī)療機構發(fā)覺的發(fā)病人數(shù)之和；

4、q(t)：表示t時刻直接確定為疑似病例和與已發(fā)病病例直接接觸過

但還無被府機關、醫(yī)療機構發(fā)覺的發(fā)病人數(shù)之和；

5、年表示在匕,小)?=0,…〃-1)這一時段內(nèi)發(fā)病病例的治愈率；

6、“：表示在=…〃-1)這一時段疑似病例轉化為發(fā)病病例的

轉化率；

7、C,：表示在t，7；+J(i=0,…〃-1)這一時段與發(fā)病病例接觸而轉化為疑

似病例的轉化率；

8、4：表示在憶,心)《=0,…〃-1)這一時段，從疑似病例中被而成為健

康人的排除率。

9、Tj表示在忙,小)(i=0,…〃-1)這一時段的起始時刻或終止時刻。

四、對衛(wèi)生部門的建議

38