迷宮求解數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)及通訊設(shè)備分配問(wèn)題-數(shù)學(xué)規(guī)劃課程設(shè)計(jì)_第1頁(yè)
迷宮求解數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)及通訊設(shè)備分配問(wèn)題-數(shù)學(xué)規(guī)劃課程設(shè)計(jì)_第2頁(yè)
迷宮求解數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)及通訊設(shè)備分配問(wèn)題-數(shù)學(xué)規(guī)劃課程設(shè)計(jì)_第3頁(yè)
迷宮求解數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)及通訊設(shè)備分配問(wèn)題-數(shù)學(xué)規(guī)劃課程設(shè)計(jì)_第4頁(yè)
迷宮求解數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)及通訊設(shè)備分配問(wèn)題-數(shù)學(xué)規(guī)劃課程設(shè)計(jì)_第5頁(yè)
已閱讀5頁(yè),還剩30頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)題目:迷宮求解班級(jí):學(xué)號(hào):作者姓名:指導(dǎo)教師:目錄1.需求分析…………….…….…..……12.概要設(shè)計(jì)…………….….……..……12.1.?dāng)?shù)據(jù)結(jié)構(gòu)………….……..……12.1.1.邏輯結(jié)構(gòu)…………..………..…..…….12.1.1.存儲(chǔ)結(jié)構(gòu)…………………..…….…22.2.基本操作…………..…...…….…32.2.1.迷宮中棧的基本操作………….…….32.2.2.迷宮的抽象數(shù)據(jù)類(lèi)型…………..………32.2.3.本程序包含三個(gè)模塊……….….….43.詳細(xì)設(shè)計(jì)……………..……….……54.調(diào)試與分析………..……….………95.用戶手冊(cè)……………96.測(cè)試結(jié)果…………….107.附錄………………….128.參考文獻(xiàn)…………….129、心得體會(huì)……………1210、小組成員工作分配………………..13PAGE -PAGE33-共9頁(yè)第1頁(yè)需求分析以二維數(shù)組maze[n+2][m+2]表示迷宮,其中:maze[0][j]和maze[n+1][j](0<=j<=m+1)及maze[i][0]和maze[i][m+1](0<=i<=j+1)為添加的一圈障礙。數(shù)組中以元素值為0的表示通路,1表示障礙,限定迷宮的大小,m,n<=0。迷宮的入口位置和出口位置可由用戶自行設(shè)定。如設(shè)定的迷宮處在通路,則值輸出迷宮中的通路,即0,現(xiàn)實(shí)的0連起來(lái)就是一個(gè)迷宮通路路徑;如設(shè)定的迷宮中不出在通路,則輸出“該迷宮找不到通路!”;測(cè)試樣例:輸入迷宮的長(zhǎng)寬為5和6,輸入迷宮為:100111001111100011010111110000當(dāng)入口位置為(1,2),出口位置為(5,6)時(shí),則輸出數(shù)據(jù)為:#########0##0##00##0##0000#########程序執(zhí)行的命令為:輸入迷宮的尺寸;2、創(chuàng)建迷宮;3、輸入迷宮的的出入口位置;4、求解迷宮;輸出迷宮的解。概要設(shè)計(jì)2.1.數(shù)據(jù)結(jié)構(gòu)2.1.1、邏輯結(jié)構(gòu)1)棧的定義:限定僅在表尾進(jìn)行插入或刪除操作的線性表;2)操作特性:后進(jìn)先出;3)ADT定義:ADTStack{數(shù)據(jù)對(duì)象:D={ai|ai∈CharSet,i=1,2,…,n,n>=0}數(shù)據(jù)關(guān)系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}基本操作:InitStack(&S)操作結(jié)果:構(gòu)造一個(gè)空棧S。DestroyStack(&S)初始條件:棧S已存在。操作結(jié)果:銷(xiāo)毀棧S。ClearStack(&S)初始條件:棧S已存在。操作結(jié)果:將S清為空棧。StackLength(&S)初始條件:棧S已存在。操作結(jié)果:返回棧S的長(zhǎng)度。StackEmpty(&S)初始條件:棧S已存在。操作結(jié)果:若S為空棧,則返回TRUE,否則返回FALSE。GetTop(S,&e)初始條件:棧S已存在。操作結(jié)果:若棧S不空,則以e返回棧頂元素。Push(&S,e)初始條件:棧S已存在。操作結(jié)果:在棧S的棧頂插入新的棧頂元素e。Pop(&S,&e)初始條件:棧S已存在。操作結(jié)果:刪除S的棧頂元素,并以e返回其值。StackTraverse(S,visit())初始條件:棧S已存在。操作結(jié)果:從棧底到棧頂依次對(duì)S中的每個(gè)元素調(diào)用函數(shù)visit()。}ADTStack2.1.2、存儲(chǔ)結(jié)構(gòu)1)順序存儲(chǔ)結(jié)構(gòu):順序棧:是利用一塊地址連續(xù)的存儲(chǔ)單元來(lái)存放棧中的元素,同時(shí)要利用一個(gè)指針top來(lái)指示棧頂元素的位置。注:在本迷宮求解程序設(shè)計(jì)中用到的就是棧的順序存儲(chǔ)結(jié)構(gòu)。//棧的順序存儲(chǔ)表示#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)綏#烘湕J侵覆捎面準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的棧。鏈棧是一種特殊的單鏈表,即限定僅在表頭進(jìn)行插入和刪除操作的單鏈表,因此鏈棧的結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)點(diǎn)結(jié)構(gòu)相同。2.2、基本操作2.2.1、迷宮中棧的基本操作:基本操作:InitStack(&S)操作結(jié)果:構(gòu)造一個(gè)空棧S。StackEmpty(&S)初始條件:棧S已存在。操作結(jié)果:若S為空棧,則返回TRUE,否則返回FALSE。GetTop(S,&e)初始條件:棧S已存在。操作結(jié)果:若棧S不空,則以e返回棧頂元素。Push(&S,e)初始條件:棧S已存在。操作結(jié)果:在棧S的棧頂插入新的棧頂元素e。Pop(&S,&e)初始條件:棧S已存在。操作結(jié)果:刪除S的棧頂元素,并以e返回其值。2.2.2、迷宮的抽象數(shù)據(jù)類(lèi)型ADTMazeType{數(shù)據(jù)對(duì)象:D={ai,j|ai,j∈{‘’,‘#’、‘@’、‘*’},0<=i<=n+1,0<=j<=m+1,m,n<=20} 數(shù)據(jù)關(guān)系:R={ROW,LINE}ROW={<ai-1,j,ai,j>|ai-1,j,ai,j∈D,i=1,…,m+1,j=0,…,n+1}LINE={<ai-1,j,ai,j>|ai-1,j,ai,j∈D,i=1,…,m+1,j=0,…,n+1} 基本操作:StatusPass(MazeType&maze,PosTypecurpos) 初始條件:maze存在迷宮,curpos保存了當(dāng)前位置的坐標(biāo) 操作結(jié)果:如果可通,返回真,否則為假voidFootPrint(MazeType&maze,PosTypecurpos) 初始條件:maze存在迷宮,curpos保存了當(dāng)前位置的坐標(biāo) 操作結(jié)果:將當(dāng)前坐標(biāo)curpos處的maze[][]值記為足跡PosTypeNextPos(PosTypeCurPos,intdi) 初始條件:各參數(shù)值已經(jīng)定義操作結(jié)果:求得以當(dāng)前位置為棧頂?shù)南乱粋€(gè)方向的元素的坐標(biāo)StatusMazePath(SqStack&S,PosTypestart,PosTypeend) 初始條件:maze存在迷宮地圖操作結(jié)果:為建立的迷宮找到一條路徑}ADTmaze;2.2.3、本程序包含三個(gè)模塊1)主函數(shù)模塊:intmain(){初始化迷宮;求解迷宮;輸出迷宮的解;return0;}2)棧實(shí)現(xiàn)模塊—實(shí)現(xiàn)棧的抽象殊絕類(lèi)型3)迷宮實(shí)現(xiàn)模塊—實(shí)現(xiàn)迷宮的抽象數(shù)據(jù)類(lèi)型各模塊的調(diào)用關(guān)系如下:主函數(shù)模塊——>迷宮模塊——>棧模塊4)求解迷宮中一條通路的偽碼算法:設(shè)定當(dāng)前位置的初值為入口位置;do{ 若當(dāng)前位置可通, 則{將當(dāng)前位置插入棧頂;//納入路徑 若該位置是出口位置,則結(jié)束;//求得路徑存放在棧中 否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置;}否則{若棧不空且棧位置尚有其他方向未被探索,則設(shè)定新的當(dāng)前位置為沿順時(shí)針?lè)较蛐D(zhuǎn)找到的棧頂位置的下一相鄰塊;若棧不空但棧頂位置的四周均不可通,則{刪去棧頂位置;//后退一步,從路徑中刪去該通道塊;若棧不空,則重新測(cè)試新的棧頂位置;直到找到一個(gè)可通的相鄰塊或出棧至???;}}}while(棧不空);{??照f(shuō)明沒(méi)有路徑存在}詳細(xì)設(shè)計(jì)坐標(biāo)位置類(lèi)型typedefstruct{ introw; intline;}PosType;迷宮類(lèi)型StatusPass(PosTypeCurPos)//判定當(dāng)前位置是否可以通過(guò),即是未曾走到過(guò)的通道塊voidFootPrint(PosTypeCurPos)//給當(dāng)前可通過(guò)的位置標(biāo)記PosTypeNextPos(PosTypeCurPos,intdi)//探尋下一個(gè)位置,并標(biāo)記方向StatusMazePath(SqStack&S,PosTypestart,PosTypeend)//求解迷宮maze中,從入口start到出口end的一條路徑,//如存在,返回OK,否則返回ERROR棧類(lèi)型typedefstruct{ intord;//通道塊在路徑上的“序號(hào)” intdi;//通道塊在迷宮中的“坐標(biāo)位置” PosTypeseat;//從此通道塊走向下一通道塊的“方向”}SElemType;//棧的元素類(lèi)型typedefstruct{ SElemType*base;//在構(gòu)造棧之前和銷(xiāo)毀之后,base的值為NULL SElemType*top;//棧頂指針 intstacksize;//當(dāng)前已分配的存儲(chǔ)空間,以元素為單位}SqStack;//棧定義棧的基本操作如下:voidInitStack(SqStack&S)//初始化棧,設(shè)棧S為空棧(S.top=NULL)voidPush(SqStack&S,SElemTypee)//若分配空間成功,則在S的棧頂插入新的棧頂元素e//否則增加棧棧的存儲(chǔ)空間,再插入新的元素intGetTop(SqStack&S,SElemTypee)//若棧S不空,則以e帶回棧頂元素并返回TRUE,否則返回FALSEintPop(SqStack&S,SElemType&e)//若棧不空,則刪除S的棧頂元素并以e帶回其值,且返回TRUE//否則返回FALSEintStackEmpty(SqStackS)//若S為空棧(S.top==NULL),則返回TRUE;否則返回FALSE具體部分操作的算法如下:voidInitStack(SqStack&S){//初始化棧S為空棧(S.top=NULL) S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE;}//InitstackvoidPush(SqStack&S,SElemTypee){//若分配空間成功,則在S的棧頂插入新的棧頂元素e//否則增加棧棧的存儲(chǔ)空間,再插入新的元素 if(S.top-S.base>=S.stacksize) { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e;}//Push求解迷宮的偽碼算法:StatusMazePath(SqStack&S,PosTypestart,PosTypeend){//若迷宮maze中存在從入口start到出口end的通道,則//一條存放在棧中(從棧底到棧頂為從入口到出口的路徑),并返//回OK,否則返回ERROR PosTypecurpos; intcurstep; SElemTypee; InitStack(S); curpos=start;//設(shè)定“當(dāng)前位置”為“初始位置” curstep=1;//探索第一步 do{ if(Pass(curpos)) {//當(dāng)前位置可以通過(guò),即是未曾走到過(guò)的的通道塊//留下足跡 FootPrint(curpos); e.di=1; e.ord=curstep; e.seat=curpos; Push(S,e);//加入路徑 if(curpos.row==end.row&&curpos.line==end.line)returnOK;//到達(dá)出口位置 curpos=NextPos(curpos,1); curstep++;//探索下一步 } else//當(dāng)前位置不能通過(guò) { if(!StackEmpty(S)) { Pop(S,e); while(e.di==4&&!StackEmpty(S)) { FootPrint(e.seat); Pop(S,e);curstep--; } if(e.di<4) { e.di++; Push(S,e); curpos=NextPos(e.seat,e.di); }//if }//if } }while(!StackEmpty(S)); returnERROR;}//MazePath主函數(shù)和其它函數(shù)的偽碼算法voidprintpath(SqStackS,intn,intm){//打印路徑 printf("\n\n通路路徑為:\n"); //PosTypestart,end;SElemType*p=S.base;//定義一個(gè)指針p指向棧中的元素,設(shè)//定初值為p=S.base while(p!=S.top) { maze[p->seat.row][p->seat.line]=2; p++;//將有效路徑的通道塊全部標(biāo)記為2或其他不為1或0的//值 } inti,flag=0;//打印出路徑,周?chē)谩?”圍成一圈作圍墻 for(i=0;i<m+2;i++)printf("%c",'#');printf("\n"); for(i=1;i<n+1;i++) { printf("%c",'#'); for(intj=1;j<m+1;j++) { if(maze[i][j]==2)printf("%c",'0'); elseprintf(""); } printf("%c",'#'); printf("\n"); } for(i=0;i<m+2;i++)printf("%c",'#');printf("\n\n");}//printpathintmain(){//主函數(shù) SqStackS; intr,l; while(true) { printf("創(chuàng)建一個(gè)迷宮,請(qǐng)輸入迷宮長(zhǎng)和寬(不得大于20):\n"); scanf("%d%d",&r,&l);if(r<1||r>20||l<1||l>20){printf("輸入錯(cuò)誤!");} inti; printf("按行輸入%d*%d數(shù)據(jù)(0代表可通,1代表不可通):\n",r,l); for(i=0;i<l+2;i++)maze[0][i]=1; for(i=1;i<r+1;i++) { maze[i][0]=1; for(intj=1;j<l+1;j++) scanf("%d",&maze[i][j]); maze[i][l+1]=1; } for(i=0;i<l+2;i++)maze[r+1][i]=1; PosTypestart,end; printf("輸入入口行坐標(biāo)和列坐標(biāo):");scanf("%d",&start.row);scanf("%d",&start.line); printf("輸入出口行坐標(biāo)和列坐標(biāo):");scanf("%d",&end.row);scanf("%d",&end.line); if(MazePath(S,start,end)) printpath(S,r,l); elseprintf("該迷宮找不到通路!\n\n"); } return0;}//main調(diào)試分析1、在本次的程序設(shè)計(jì)中,最核心的算法就是MazePath()函數(shù),其他的算法并沒(méi)有出現(xiàn)什么問(wèn)題。不過(guò)在最后輸出的時(shí)候本來(lái)想輸出路徑的先后順序,即maze[1][2]>maze[2][2]>maze[3][2]>maze[3][3]>maze[4][3]>maze[5][3]>maze[5][4]>maze[5][5]>maze[5][6],但是最后發(fā)現(xiàn)這樣只有在入口在左上角,出口在右下角時(shí),才可以正確輸出。但是入口和出口是隨機(jī)的,若是入口在右下角,出口在左上角,則也同樣輸出maze[1][2]>maze[2][2]>maze[3][2]>maze[3][3]>maze[4][3]>maze[5][3]>maze[5][4]>maze[5][5]>maze[5][6],雖然這兩個(gè)路徑是一樣的,但是有先后順序,故最后沒(méi)有輸出這種形式,將這段代碼注釋了(源程序中有注釋的代碼);2、本來(lái)是想設(shè)計(jì)成既可以手動(dòng)輸入迷宮又可以自動(dòng)生成迷宮,但是感覺(jué)沒(méi)有太大的用處,所以最后省略了,只保留了手動(dòng)輸入。3、在整個(gè)編寫(xiě)的過(guò)程中,出現(xiàn)過(guò)很多錯(cuò)誤,包括一些標(biāo)點(diǎn)符號(hào)的小錯(cuò)誤,但是借助DEBUG調(diào)試器和數(shù)據(jù)觀察窗口,很快找出來(lái)問(wèn)題的所在。用戶手冊(cè)本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng),執(zhí)行文件為:迷宮求解.exe.進(jìn)入演示程序后,即顯示文本方式的用戶界面:根據(jù)提示輸入迷宮大小及迷宮后,輸入迷宮的行和列,回車(chē)后即可得到所輸入迷宮的解或者是顯示“該迷宮找不到通路!”字樣。測(cè)試結(jié)果輸入長(zhǎng)寬為5,6,入口為(1,2),出口為(5,6)的迷宮100111001111100011010111110000求解結(jié)果:輸入長(zhǎng)寬為4,5,入口為(1,1),出口為(4,5)的迷宮01011001101011110000輸出結(jié)果為:輸入長(zhǎng)寬為4,5,入口為(1,1),出口為(4,5)的迷宮110111010101100011010111110000輸出結(jié)果為:附錄源程序文件名清單:主函數(shù).cpp迷宮的實(shí)現(xiàn).h棧的實(shí)現(xiàn).h參考文獻(xiàn)1、嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)[M].北京:清華大學(xué)出版社,2012.2、嚴(yán)蔚敏,吳偉民,米寧.數(shù)據(jù)結(jié)構(gòu)題集(C語(yǔ)言版)[M].北京:清華大學(xué)出版社,2012.3、蘇仕華,魏韋巍,王敬生,劉燕君.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)[M].北京:機(jī)械工業(yè)出版社,2010.心得體會(huì)做了這次程序設(shè)計(jì),我們發(fā)現(xiàn)利用數(shù)據(jù)結(jié)構(gòu)進(jìn)行程序設(shè)計(jì)并不像想像中的那么高深,像我們現(xiàn)在所做的,只是一些最基本的程序。經(jīng)過(guò)一個(gè)學(xué)期的學(xué)習(xí),對(duì)數(shù)據(jù)結(jié)構(gòu)有了一個(gè)初步的認(rèn)識(shí),但沒(méi)有進(jìn)行實(shí)際應(yīng)用。這次程序設(shè)計(jì),就相當(dāng)于對(duì)一個(gè)學(xué)期的所學(xué)做一個(gè)總結(jié),再進(jìn)行一次綜合運(yùn)用,更是學(xué)到了很多新的東西,無(wú)意中也提升了自己的程序設(shè)計(jì)水平;在程序設(shè)計(jì)過(guò)程中碰到了很多問(wèn)題,通過(guò)上網(wǎng)查資料等各種手段,我們的解決實(shí)際問(wèn)題的能力也得到了提高。這次的程序設(shè)計(jì),讓我們對(duì)程序設(shè)計(jì)有了一個(gè)更全面的認(rèn)識(shí),如果我們以后能在編程領(lǐng)域深入發(fā)展,這一次也算是我們邁出的重要一步吧。小組成員工作分配程序、文檔的編寫(xiě);程序校對(duì)及查找資料;文檔的勘誤及字體的調(diào)整。數(shù)學(xué)規(guī)劃課程設(shè)計(jì)

題目通訊設(shè)備分配問(wèn)題姓名班級(jí)學(xué)號(hào)1. 課程設(shè)計(jì)評(píng)價(jià)參考標(biāo)準(zhǔn)及得分序號(hào)指標(biāo)分值得分1所選題目應(yīng)用價(jià)值與難度202綜合應(yīng)用數(shù)學(xué)專(zhuān)業(yè)知識(shí)解決實(shí)際問(wèn)題的能力303與學(xué)分相適應(yīng)的工作量和難度,有一定的創(chuàng)新304圖標(biāo)美觀,參考文獻(xiàn),格式合適等20論文成績(jī)指導(dǎo)教師簽名通訊設(shè)備分配問(wèn)題摘要:數(shù)學(xué)規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要組成部分,它是近幾十年里發(fā)展起來(lái)的一門(mén)新興科學(xué)。隨著電子計(jì)算機(jī)的普及與發(fā)展,它在自然科學(xué),社會(huì)科學(xué),工程技術(shù)和現(xiàn)代管理中得到了廣泛的應(yīng)用,日益受到人們的重視。而作為數(shù)學(xué)規(guī)劃中的一個(gè)重要分支的動(dòng)態(tài)規(guī)劃,是一種解決復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的方法,是目前解決多階段決策過(guò)程問(wèn)題的基本理論之一。由于動(dòng)態(tài)規(guī)劃不是一種特定的算法,因而它不像線性規(guī)劃那樣有自己標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和統(tǒng)一的求解方法,而必須對(duì)具體問(wèn)題進(jìn)行具體的分析處理。因此其更具有實(shí)用價(jià)值,解決了我們現(xiàn)實(shí)生活中許多實(shí)際問(wèn)題。實(shí)踐證明,動(dòng)態(tài)規(guī)劃在工程技術(shù),經(jīng)濟(jì)管理,工業(yè)生產(chǎn),軍事以及現(xiàn)代控制工程等領(lǐng)域都有廣泛的應(yīng)用,并獲得顯著效果。在本文中,我們主要介紹的運(yùn)用動(dòng)態(tài)規(guī)劃的思想,利用計(jì)算機(jī)軟件Excel,解決資源分配問(wèn)題,就是一個(gè)現(xiàn)實(shí)生活中動(dòng)態(tài)規(guī)劃的運(yùn)用實(shí)例,同時(shí),又充分利用計(jì)算機(jī)技術(shù),使計(jì)算更為便捷有效,從而更方便的解決了實(shí)際問(wèn)題。關(guān)鍵詞:數(shù)學(xué)規(guī)劃;動(dòng)態(tài)規(guī)劃;多階段決策過(guò)程問(wèn)題;計(jì)算機(jī)軟件Excel;資源分配問(wèn)題一.引言正所謂資源分配,即是將數(shù)量一定的或若干種,諸如:材料,設(shè)備,人力,資金,時(shí)間等資源,合理地分給若干個(gè)使用者,而是目標(biāo)函數(shù)最大。在此處,由于分配的資源過(guò)多,且目標(biāo)函數(shù)是非線性函數(shù),可將其看成一個(gè)多階段決策問(wèn)題,利用動(dòng)態(tài)規(guī)劃的方法求解。在動(dòng)態(tài)規(guī)劃方法求解時(shí),通常以把資源分配給一個(gè)或幾個(gè)使用者的過(guò)程作為一個(gè)階段,把規(guī)劃問(wèn)題中的變量取為決策變量,將累計(jì)的量或遞推過(guò)程變化的量選為狀態(tài)變量。二.問(wèn)題闡述某郵局有4套通訊設(shè)備準(zhǔn)備分給甲乙丙三個(gè)地區(qū),事先調(diào)查了各地原有生產(chǎn)活動(dòng)情況,在此基礎(chǔ)上對(duì)各種分配方案的經(jīng)濟(jì)效益進(jìn)行了估計(jì),得下表1(附錄)的數(shù)據(jù),例如:甲區(qū)原有生產(chǎn)活動(dòng)的收益為38萬(wàn)元,當(dāng)新增加一套通訊設(shè)備時(shí)總收益為41萬(wàn)元,其他類(lèi)推。試求4套設(shè)備的分配方案,使3地區(qū)總利益最大。三.模型的建立和求解3.1模型的建立首先我們對(duì)設(shè)備的分配規(guī)定一個(gè)順序,即先考慮分配給甲區(qū),其次乙區(qū),最后丙區(qū),但分配時(shí)必須保證郵電局德宗受益最大。將問(wèn)題按分配過(guò)程分為3個(gè)階段,根據(jù)動(dòng)態(tài)規(guī)劃逆序算法,可設(shè):階段數(shù)t=1,2,3(即甲,乙,丙3個(gè)地區(qū)的編號(hào)分別為1,2,3);狀態(tài)變量dk:表示分配給第k個(gè)地區(qū)至第3地區(qū)的設(shè)備套數(shù)(即第k階段初尚未分配的設(shè)備套數(shù));決策變量Xk:表示分配給第k個(gè)地區(qū)的設(shè)備套數(shù);狀態(tài)轉(zhuǎn)移方程:dk+1=dk-Xk;Rt(Xk):表示Xk臺(tái)設(shè)備分配到第k個(gè)地區(qū)所得的收益值,它由表1查得;Ft(dk):表示將dk臺(tái)設(shè)備分配到第k個(gè)地區(qū)至第3地區(qū)所得的最大收益值,因而可得出遞推方程:Ft(dk)=max[Rt(Xk)+Ft+1(dk-Xk)](k=1,2,3;t=1,2,3;Xk=0,1,2,3,4)F4(d4)=03.2模型的求解運(yùn)用動(dòng)態(tài)規(guī)劃的思想,利用窮舉的方法以及計(jì)算機(jī)軟件Excel,進(jìn)行模型求解。根據(jù)問(wèn)題分析中的相關(guān)公式,此處,為方便,令Jt(dk,Xk)=Rt(Xk)+Ft+1(dk-Xk)。求解步驟:(1)根據(jù)表1數(shù)據(jù),將Rt(Xk)輸入A4:F7來(lái)構(gòu)建電子表格,如圖1(附錄中)所示。例如:將R2(2)=50輸入到單元格D6中;(2)在B11:F11中的各單元各內(nèi)輸入0,因?yàn)閷?duì)所有的dk都有F4(dk)=0;在第18~20行,設(shè)置計(jì)算指令求出Jt(dk,Xk),此處使用Excel中的HLOOKUP命令來(lái)查找Rt(Xk)(在第5行至第7行)和Ft+1(dk-Xk)(在第11行至第14行)的值。例如,要計(jì)算J3(3,1),需要將下列公式輸入單元格I18中:=HLOOKUP(I$17,$B$4:$F$7,$A18+1)+HLOOKUP(I$16-I$17,$B$10:$F$14,$A18+1)。(其中,該公式前半部分HLOOKUP(I$17,$B$4:$F$7,$A18+1)表示在B4

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論