數(shù)學(xué)模型與計(jì)算機(jī)模擬

教學(xué)改革材料

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

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

過(guò)抽象、歸納把事物的本質(zhì)關(guān)系和本質(zhì)結(jié)構(gòu)用數(shù)學(xué)語(yǔ)言來(lái)描述，建立正確

的數(shù)學(xué)結(jié)構(gòu)，并用科學(xué)的方法，通過(guò)編寫程序求解問(wèn)題，得出供人們作分

析、預(yù)報(bào)、決策或者控制的定量結(jié)果。本課程的學(xué)習(xí)應(yīng)注重學(xué)生的能力培

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

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

些知識(shí)應(yīng)用于信息系統(tǒng)構(gòu)建和應(yīng)用的潛力；

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

明用戶的需求；

三、能設(shè)計(jì)高效實(shí)用的信息技術(shù)解決方案；

四、能深刻理解成功的經(jīng)驗(yàn)和標(biāo)準(zhǔn)，并能運(yùn)用；

五、具有獨(dú)立思考和解決問(wèn)題的能力；

六、具有團(tuán)隊(duì)協(xié)作能力和論文寫作能力。

以上六個(gè)方面的要求與教育部高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委

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

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

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

于應(yīng)用能力和自學(xué)能力的培養(yǎng)”的辦學(xué)方略相統(tǒng)一。基于此，信息工程學(xué)

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

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

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

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

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

二、教學(xué)方式方法上由以往的講授為主，改為以學(xué)生為主的獨(dú)立思

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

定典型問(wèn)題，引導(dǎo)學(xué)時(shí)討論，課后查閱相關(guān)資料。學(xué)生根據(jù)自己理解分析

問(wèn)題，即分析問(wèn)題的常量和變量的關(guān)系，把問(wèn)題本身存在的邏輯關(guān)系找出

來(lái)，得出問(wèn)題的數(shù)學(xué)結(jié)構(gòu)，寫出數(shù)學(xué)模型，尋找適合的解法，并把算法的

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

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

的理論依據(jù)（正確性分析），并學(xué)習(xí)和借鑒已有經(jīng)驗(yàn)。整個(gè)教學(xué)過(guò)程主要分

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

模型；五是編寫程序驗(yàn)證模型；六是歸納總結(jié)；（具體過(guò)程見(jiàn)模型解法）。

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

實(shí)驗(yàn)大綱和綜合實(shí)驗(yàn)題目，并給出了參考程序。另外，每年組織學(xué)生參加

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

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

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

2

數(shù)學(xué)模型與計(jì)算機(jī)模擬

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

1.問(wèn)題的提出

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

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

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

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

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

利最大？

2.問(wèn)題的分析：

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

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

用w表示該廠的利潤(rùn)；

本問(wèn)題是:問(wèn)xl,x2為何值時(shí),W最大？

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

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

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

束條件，所以這是一個(gè)約束條件下求最大值問(wèn)題.

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

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

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

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

3

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

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

3.模型的建立

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

w=1OOOxj+1500—2

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

9+5<350

4000修+5000220x104

<

4/+10A:2<300

,x2>0

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

maxw=1000/+1500x2

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

4

<4000%+5000工2<20x10

4%]+10JC2<300

X],x2>0

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

或者等價(jià)地化為：

4

minw=-1000x1-1500x2

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

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

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

4.模型的求解

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

小，它對(duì)應(yīng)的是X2,由X2做如下操作

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

(3)再看那個(gè)小，因30小它對(duì)應(yīng)的是方程(3),由方程⑶做如下操作:

在方程⑶解出X2：2]

x9=30——x11——x

255

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

minw=-400xj+300JC5-45000

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

2xy-x5+x4=50⑵

212

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

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

它對(duì)應(yīng)的是X],由xi做如下操作

5

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

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

720.4

(3)再看哪個(gè)小，因25小它對(duì)應(yīng)的是方程(2),由方程(2)做如下操作:

在方程(2)解出x,

“11

X.=25——xA+—x

122

并代入目標(biāo)函數(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ī)劃模型的標(biāo)準(zhǔn)形式

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

，N

minz=ZcJXJ+c0

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

j=i

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

稱為標(biāo)準(zhǔn)形式的線性規(guī)劃模型,是指基變量的個(gè)數(shù)為m,且

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

6.標(biāo)準(zhǔn)形式線性規(guī)劃模型的算法

6

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

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

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

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

m,i!=g);

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

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

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

保持不變，分別讓j=2,…N做上述操作后，因?yàn)閷?duì)于任意的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個(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è)方程-第g個(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個(gè)方程中求出x[k],代入目標(biāo)函數(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標(biāo)準(zhǔn)形式線性規(guī)劃模型算法C語(yǔ)言表述

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);

)

程序運(yùn)行結(jié)果：

x[l]=0

x[2]=0

x[3]=350

x[4J=200

x[5]=150

min=55000

13

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

一.提出問(wèn)題：工廠選址

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

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

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

單\?

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

B1B2B3B4

（件）本（元）

Al412411431

A221089532

A385116634

A412394435

量（件）2221

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

二.分析問(wèn)題

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

在i地址建廠

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

0在i地址不建廠

2.設(shè)從i地址運(yùn)到j(luò)需求點(diǎn)的運(yùn)輸量可設(shè)為為整數(shù)

3.運(yùn)到各點(diǎn)的量應(yīng)不小于需求（x[l][j]+x⑵U]+x[3][j]+x[4]|j]>=b[j]）；

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

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

5.運(yùn)到各需求點(diǎn)的量如何計(jì)算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.目標(biāo)函數(shù)：總費(fèi)用2=建廠費(fèi)用+運(yùn)輸費(fèi)用

8.運(yùn)輸費(fèi)用=單位運(yùn)輸費(fèi)用*運(yùn)輸量(從i地址運(yùn)到j(luò)需求點(diǎn)單位運(yùn)輸費(fèi)

用已知，從i地址運(yùn)到j(luò)需求點(diǎn)的運(yùn)輸量可設(shè)為x[i][j])

三.模型建立

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

設(shè)，4建,(i=l,2,…,4),馬表示從，?點(diǎn)運(yùn)到/點(diǎn)的貨物數(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點(diǎn)到/點(diǎn)的單位運(yùn)費(fèi)(i,)=1,2,…,4),

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

勺表不需求點(diǎn)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],將所有可行方案一一列舉,

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

注：最小費(fèi)用唯一，方案可有多種。

15

五.設(shè)計(jì)算法求解

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

i=l,2,3,4

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

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

3.考察兩條件是否同時(shí)成立：

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

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

4.計(jì)算：總費(fèi)用2=建廠費(fèi)用+運(yùn)輸費(fèi)用

建廠費(fèi)用=2[1]*丫[1]+2[2]*丫[2]+2[引*y[3]+a[4]*y[4]

運(yùn)輸費(fèi)用=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.比較總費(fèi)用是否最小，并記錄最佳方案(可能有多種)：

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

6、輸出最小費(fèi)用和方案。

六.驗(yàn)證結(jié)果(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

第五章最短路問(wèn)題

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

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

(i=2,3,…,11)

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

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

解：設(shè)置常量〃，〃表示城市的最大編號(hào)，即〃=11

設(shè)置二維數(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ù)均設(shè)置為0.

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

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

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

20

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

2、其求解過(guò)程如下：

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]);

程序運(yùn)行結(jié)果:

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ù)學(xué)建模獲獎(jiǎng)?wù)撐?/p>

產(chǎn)品加工模型

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

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

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

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

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

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

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

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

S」表示第/種設(shè)備完成所有任務(wù)的最短時(shí)間，即

58

m=ln=l

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

Jmn

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

jnn

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

42、38、62、70；

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

于是可得設(shè)備的優(yōu)先生產(chǎn)順序?yàn)椋涸O(shè)備4—＞設(shè)備3—＞設(shè)備1—＞設(shè)備2；

產(chǎn)品的優(yōu)先生產(chǎn)順序?yàn)椋寒a(chǎn)品4—＞產(chǎn)品3—＞產(chǎn)品5—＞產(chǎn)品1—＞產(chǎn)品2o

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

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

26

設(shè)備4：完成

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

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

設(shè)備2：4^^5—完成

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

設(shè)備1：■設(shè)備2：設(shè)備3：設(shè)備4：■

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

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

出了最小加工時(shí)間為62。方法同上。

設(shè)備3：^5—^2—^4-^62完成

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

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

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

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

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

27

設(shè)備1：?設(shè)備2：設(shè)備3：?設(shè)備4：?設(shè)

備5：■

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

關(guān)鍵詞：?jiǎn)l(fā)式方法，最短路算法；

一.問(wèn)題的提出

產(chǎn)品加工問(wèn)題

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

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

其工序與加工周期如下表：（S-設(shè)備號(hào)、T一周期）

工

12345678

序

產(chǎn)

品STSTSTSTSTSTSTST

138122432446

214452334

3334711522018

28

427364211141633

54102438441123641

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

2、每臺(tái)設(shè)備在同一時(shí)間只能擔(dān)任一項(xiàng)任務(wù)。（每件產(chǎn)品的每個(gè)工序

為一個(gè)任務(wù)）。

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

務(wù)。

2、如果考慮增加設(shè)備一臺(tái)，你有什么建議。

二、對(duì)題中所給模型的分析

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

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

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

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

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

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

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

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

Sj表示第/種設(shè)備完成所有任務(wù)的最短時(shí)間，即

58

m=ln=l

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

Jmn

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

jnn

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

29

42、38、62、70；

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

于是可得設(shè)備的優(yōu)先生產(chǎn)順序?yàn)椋涸O(shè)備4——＞設(shè)備3——＞設(shè)備1——＞設(shè)

備2；

產(chǎn)品的優(yōu)先生產(chǎn)順序?yàn)椋寒a(chǎn)品4——＞產(chǎn)品3——＞產(chǎn)品5——＞產(chǎn)品1——＞

產(chǎn)品2。

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

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

設(shè)備4：完成

設(shè)備3：3—J1—J4—J5—J2—J4—。68完成

設(shè)備1：^5—^67完成

設(shè)備2：4^^5—U]—完成

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

設(shè)備1：■設(shè)備2：設(shè)備3：■設(shè)備4：■

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

30

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

出了最小加工時(shí)間為62。方法同上。

設(shè)備3：^~?5^_?4^~>62完成

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

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

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

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

設(shè)備1：?設(shè)備2：設(shè)備3：■設(shè)備4：■新增

設(shè)備4：■

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

三、對(duì)所建模型的驗(yàn)證

根據(jù)所建模型

31

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

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

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

S」表示第/種設(shè)備完成所有任務(wù)的最短時(shí)間，即

58

s=yy⑸+Aj）

JJnnJmn

m=ln=l

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

Jmn

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

jnn

進(jìn)行驗(yàn)證，得出在第（1）問(wèn)題中的最短加工時(shí)間為70,并找出了具體

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

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

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

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

266o

四、參考文獻(xiàn)

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

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

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

32

預(yù)防與控制傳染病模型

摘要

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

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

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

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

at

x(q)=—

)(1)=)Q-o)

其中：

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

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

3、p(t)：表示t時(shí)刻直接確定為發(fā)病病例與已發(fā)病但沒(méi)有被政府機(jī)關(guān)、

醫(yī)療機(jī)構(gòu)發(fā)覺(jué)的發(fā)病人數(shù)之和；

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

但還沒(méi)有被府機(jī)關(guān)、醫(yī)療機(jī)構(gòu)發(fā)覺(jué)的發(fā)病人數(shù)之和；

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

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

轉(zhuǎn)化率；

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

似病例的轉(zhuǎn)化率；

33

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

康人的排除率。

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

并做了如下工作：

(1)對(duì)附件1所提供的一個(gè)早期的模型的合理性和實(shí)用性進(jìn)行了評(píng)價(jià)。

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

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

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

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

(3)給當(dāng)?shù)貓?bào)刊寫了一篇通俗短文，說(shuō)明建立傳染病數(shù)學(xué)模型的重要

性。

34

一、問(wèn)題的提出

SARS(SevereAcuteRespiratorySyndrome,嚴(yán)重急性呼吸道綜合癥，

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

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

到了許多重要的經(jīng)驗(yàn)和教訓(xùn)，認(rèn)識(shí)到定量地研究傳染病的傳播規(guī)律、為預(yù)

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

(1)對(duì)附件1所提供的一個(gè)早期的模型的合理性和實(shí)用性進(jìn)行了評(píng)價(jià)。

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

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

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

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

(3)給當(dāng)?shù)貓?bào)刊寫了一篇通俗短文，說(shuō)明建立傳染病數(shù)學(xué)模型的重要

性。

二、對(duì)附件1中一個(gè)早期模型的評(píng)價(jià)

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

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

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

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

病例數(shù)目的增長(zhǎng)隨時(shí)間看(單位天)的關(guān)系是：

35

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

(1)

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

(1+=e'

(2)

k=ex

(3)

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

N(t)=N。*

(4)

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

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

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

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

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

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

參數(shù)都不能用得太小，否則無(wú)法描寫好各階段的數(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ī)律增長(zhǎng)的，只不過(guò)是各

階段的增長(zhǎng)率的大小不同而已。其文中的陳述：

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

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

來(lái)不及防備，止匕時(shí)K值比較大。為了簡(jiǎn)單起見(jiàn)，我們從開始至到高峰期間均

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

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

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

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

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

定的道理的，具有階段性的實(shí)用性。但附件一提供的模型過(guò)于簡(jiǎn)單，為此

我們需要建立新的模型。

三、一個(gè)改進(jìn)的模型

針對(duì)附件一提供的模型過(guò)于簡(jiǎn)單，我們建立如下模型：

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時(shí)刻已發(fā)病病例的累計(jì)人數(shù)；

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

3、p(t)：表示t時(shí)刻直接確定為發(fā)病病例與已發(fā)病但還無(wú)被政府機(jī)關(guān)、

醫(yī)療機(jī)構(gòu)發(fā)覺(jué)的發(fā)病人數(shù)之和；

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

但還無(wú)被府機(jī)關(guān)、醫(yī)療機(jī)構(gòu)發(fā)覺(jué)的發(fā)病人數(shù)之和；

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

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

轉(zhuǎn)化率；

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

似病例的轉(zhuǎn)化率；

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

康人的排除率。

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

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

38