《運(yùn)籌學(xué)》- 運(yùn)輸問題課程設(shè)計(jì)報(bào)告.doc

工廠原料運(yùn)輸問題課程設(shè)計(jì)報(bào)告一、課程設(shè)計(jì)的目的運(yùn)籌與最優(yōu)化方法是信息與計(jì)算科學(xué)專業(yè)的一門重要的專業(yè)課程，是一門綜合應(yīng)用課程。主要內(nèi)容包括：線性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃、非線性規(guī)劃、庫存論、排隊(duì)論、博奕論、圖與網(wǎng)絡(luò)分析的基本概念、方法和模型等，以及有廣泛應(yīng)用前景的運(yùn)籌學(xué)問題的啟發(fā)式算法。運(yùn)籌學(xué)與最優(yōu)化方法中的運(yùn)輸問題是一種應(yīng)用廣泛的網(wǎng)絡(luò)最優(yōu)化模型，該模型的主要目的是為物資調(diào)運(yùn)，車輛調(diào)度選擇最經(jīng)濟(jì)的運(yùn)輸路線。運(yùn)籌學(xué)與最優(yōu)化方法運(yùn)輸問題課程設(shè)計(jì)的目的是為了適應(yīng)信息管理與信息系統(tǒng)培養(yǎng)目標(biāo)的要求，使我們學(xué)習(xí)掌握如何應(yīng)用運(yùn)籌學(xué)中的數(shù)量方法與模型來分析通過計(jì)算機(jī)來實(shí)現(xiàn)研究現(xiàn)代企業(yè)生產(chǎn)與技術(shù)管理以及經(jīng)營管理決策問題。課程設(shè)計(jì)使我們能成熟的理解和應(yīng)用運(yùn)籌學(xué)模型，使我們認(rèn)識(shí)運(yùn)籌學(xué)在生產(chǎn)與技術(shù)管理和經(jīng)營管理決策中的作用，領(lǐng)會(huì)其基本思想和分析與解決問題的思路。為我們以后畢業(yè)參加工作單位的策略策劃打下堅(jiān)實(shí)的基礎(chǔ)。二、課程設(shè)計(jì)地點(diǎn)：第三實(shí)驗(yàn)樓4樓，運(yùn)籌學(xué)實(shí)驗(yàn)室三、課程設(shè)計(jì)時(shí)間：第十八周，第十九周四、課程設(shè)計(jì)原理與過程（一）運(yùn)輸問題的內(nèi)容及其解決方法運(yùn)輸問題是一種應(yīng)用廣泛的網(wǎng)絡(luò)最優(yōu)化模型，該模型的主要目的是為物資調(diào)運(yùn)、車輛高度選擇最經(jīng)濟(jì)的運(yùn)輸路線。有些問題，如m臺(tái)機(jī)床加工零件問題、工廠合理布局問題，雖要求與提法不同，經(jīng)適當(dāng)變化也可以使用本模型求得最付佳方案。運(yùn)輸問題的一般提法：某種物資有m個(gè)產(chǎn)地Ai，產(chǎn)量是ai（i1，2,m），有m個(gè)銷售地Bi，銷量(需求量)是bj(j=1,2,m)。若從Ai運(yùn)到Bi單位運(yùn)價(jià)為dij(i=1,2,m;j=1,2,m),又假設(shè)產(chǎn)銷平衡，即 問如何安排運(yùn)輸可使總運(yùn)費(fèi)最??？ 若用xij(i=1,2,m;j=1,2,n)表示由Ai運(yùn)到Bj的運(yùn)輸量，則平衡運(yùn)輸問題可寫出以下線性規(guī)劃模型： 約束條件具體問題如下： 三個(gè)工廠B1，B2，B3，它們需要同一種原料，數(shù)量分別是72噸、102噸、41噸，另外有三座倉庫A1、A2、A3可以供應(yīng)上述原料56噸、82噸、77噸，由于工廠和倉庫位置不同，單位運(yùn)價(jià)不同，具體數(shù)據(jù)如表1。應(yīng)如何安排運(yùn)輸方案，才能使總運(yùn)費(fèi)最?。勘?B1B2B3產(chǎn)量A148856A216241682A38162477銷量7210241215解決方法用表上作業(yè)法，具體原理和方法如下：觀察運(yùn)輸問題的線性規(guī)劃模型可知：它有m*n具變量，(m+n)個(gè)約束方程，其系數(shù)矩陣為0-1矩陣，且有大量的零，通常稱為稀疏矩陣，形如：x11x12 x1nx21x22 x2n xm1xm2 xmn易知此矩陣的任何一個(gè)m+n階子方陣對(duì)應(yīng)的行列式等于零，所以系數(shù)矩陣的秩m+n-1，并可證明運(yùn)輸問題的約束方程組系數(shù)矩陣的秩為m+n-1.由此可知運(yùn)輸問題只有m+n-1個(gè)獨(dú)立的約束方程，即其基本可行解中基變量個(gè)數(shù)為m+n-1，其余均為非基變量。由于運(yùn)輸問題的以上特征，可用更簡便的方法進(jìn)行計(jì)算，即表上作業(yè)法。表上作業(yè)法原理同于單純形法，首先給出一個(gè)初始的調(diào)運(yùn)方案(實(shí)際上是初始基本可行解)，求出各非基變量的檢驗(yàn)數(shù)去判定當(dāng)前解是否為最優(yōu)解，若不是則進(jìn)行方案調(diào)整(即從一個(gè)基本可行解轉(zhuǎn)換成另一個(gè)基本可行解)，再判定是否為最優(yōu)解，重復(fù)以上步驟，直到獲得最優(yōu)解為止。這些步驟在表上進(jìn)行十分方便。操作過程在表上進(jìn)行，具體的表如下：表2B1B2B3產(chǎn)量A14 x118 x128 x1356A216 x2124 x2216 x2382A38 x3116 x3224 x3377銷量7210241215初始調(diào)運(yùn)方案如下表：表3B1B2B3產(chǎn)量A14 568 8 56A216 24 4116 4182A38 1616 6124 77銷量7210241215上表中“”表示非基變量。 最優(yōu)解的判定如下表B1B2B3產(chǎn)量uiA14 568 8 560A216 24 4116 418212A38 1616 6124 774銷量7210241215vj4124上表中帶圈的數(shù)字所表示的是非基變量。若令ij=dij-(ui+vj)(dij為非基變量所在的空格處的運(yùn)費(fèi))，稱ij為空格檢驗(yàn)數(shù)?？梢宰C明ij就是單純形法中的檢驗(yàn)數(shù)。所以用判定最優(yōu)解的原則也同于單純形法中的判定定理。當(dāng)ij0時(shí)，即可得到最優(yōu)解，若ij0，則返回上一級(jí)操作。直到得到最優(yōu)解。（二） 運(yùn)輸問題課程設(shè)計(jì)源程序代碼/ #include stdafx.h #include #include #include #include using namespace std; #define a(j) (* (C+(M-1)*N+j) / 銷量數(shù)組 #define b(i) (* (C+i*N+N-1) / 產(chǎn)量數(shù)組 #define c(i,j) (* (C+i*N+j) / 運(yùn)價(jià)數(shù)組 #define x(i,j) (* (X+i*(N-1)+j) / 運(yùn)量數(shù)組 const double BIG_NUM = 1.0E15; / 任意大數(shù) / ( = BIG_NUM : 運(yùn)量為 0 ) #define s(i,j) (*(S+i*(N-1)+j) / 檢驗(yàn)數(shù)數(shù)組Sij */ #define u(i) (*(U+i) / 位勢數(shù)組 Ui #define v(i) (*(V+i) / 位勢數(shù)組 Vi #define cpi(k) (CP+k)-i) / 閉回路點(diǎn) i 標(biāo) #define cpj(k) (CP+k)-j) / 閉回路點(diǎn) j 標(biāo) #define cpf(k) (CP+k)-f) / 閉回路點(diǎn) f 標(biāo) /* f = 0: j+; f = 1: i-; f = 2: j-; f = 3: i+; */ void TP(int M,int N,double *C,double *X); int main() int M, N, i, j; double* C; / 存儲(chǔ)運(yùn)價(jià), 產(chǎn)量及銷量 double* X; / 存儲(chǔ)運(yùn)量分配方案 double z; ifstream infile; char fn80; double sum; cout.setf(ios_base:left,ios_base:adjustfield); cout.setf(ios_base:fixed,ios_base:floatfield); cout.precision(3); coutfn; infile.open(fn); if (!infile) coutMN; M+; N+; X=new doublesizeof(double)*(M-1)*(N-1); C=new doublesizeof(double)*M*N; / 把運(yùn)價(jià), 供應(yīng)量和需求量的數(shù)據(jù)讀入到數(shù)組 c( i, j ) for(i=0;iM;+i) for(j=0;jz; c(i,j)=z; infile.close(); coutn= 數(shù)據(jù)文件 =n; for(i=0;iM;+i) for(j=0;jN;+j) coutsetw(10)c(i,j); coutendl; system(pause); TP(M,N,C,X); / 輸出產(chǎn)銷分配方案 coutn= 最優(yōu)解 =n; sum=0; for(i=0;iM-1;+i) for(j=0;j=BIG_NUM) coutsetw(10)*; else coutsetw(10)x(i,j); sum+=(x(i,j)*c(i,j); coutendl; /coutnntThe min Cost is: %-10.4fn, sum); coutnnt最高產(chǎn)量:setw(10)sumendl; /我們現(xiàn)在是在求max，max=-min free(X); free(C); system(pause); return 0; / 記錄閉回路點(diǎn)結(jié)構(gòu) struct PATH int i,j,f; ; void TP(int M,int N,double* C,double* X) double *U, *V, *S; int MN1,m,n; struct PATH* CP; int k,i,j,l,k1,l1,ip; double Cmin,sum; int I0,J0,Imin,Jmin; int fi,fj,fc,f; MN1=(M-1)+(N-1)-1; m=M-1; n=N-1; S=new doublesizeof(double)*(M-1)*(N-1); U=new doublesizeof(double)*M; V=new doublesizeof(double)*N; CP=new PATHsizeof(struct PATH)*(MN1+1); / 解初始化 Xij = BIG_NUM for(i=0;im;+i) for(j=0;jn;+j) x(i,j)=BIG_NUM; / 最小元素法求初始可行解 for ( k = 0; k MN1; +k ) Cmin = BIG_NUM; for ( i = 0; i m; +i ) fi = 0; for ( l = 0; l k; +l ) / 去除已經(jīng)用過的行 if ( i = cpi( l ) ) fi = 1; break; if ( fi = 1 ) continue; for ( j = 0; j n; +j ) fj = 0; for ( l = 0; l c( i, j ) ) Cmin = c( i, j ); I0 = i; J0 = j; / end for j / end for i / 得到了未劃去的最小運(yùn)價(jià)所在格的坐標(biāo)(I0,J0)和最小運(yùn)價(jià)Cmin if ( k 0 ) if(Cmin=BIG_NUM & cpi(k-1)=0) for(l1=0;l1m;l1+) if(x(l1,cpj(k-1)=BIG_NUM) x(l1,cpj(k-1)=0; else if(Cmin=BIG_NUM & cpi(k-1)!=0) for(l1=0;l1n;l1+) if(x(cpi(k-1),l1)=BIG_NUM) x(cpi(k-1),l1)=0; if ( b( I0 ) a( J0 ) ) cpi( k ) = I0; cpj( k ) = -1; x( I0, J0 ) = b( I0 ); a( J0 ) -= b( I0 ); b( I0 ) = 0; else cpi( k ) = -1; cpj( k ) = J0; x( I0, J0 ) = a( J0 ); b( I0 ) -= a( J0 ); a( J0 ) = 0; / end for k 用最小元素法求得了初使可行解 / 輸出初始可行解 cout n= 初始解 =n; sum = 0; for ( i = 0; i M - 1; i+ ) for ( j = 0; j = BIG_NUM ) cout setw( 10 ) *; else cout setw( 10 ) x( i, j ); sum += ( x( i, j ) * c( i, j ) ); cout endl; coutnnt初始產(chǎn)量:setw(10)sumendl;/我們現(xiàn)在是在求max，max=-min system( pause ); while ( true ) / 位勢置初值 Ui, Vi = BIG_NUM for ( i = 0; i m; i+ ) u( i ) = BIG_NUM; for ( j = 0; j n; j+ ) v( j ) = BIG_NUM; / 求位勢 l = 0; u( 0 ) = 0; for ( i = 0; i m; i+ ) for ( j = 0; j =BIG_NUM & v(j)=BIG_NUM & x(i,j)BIG_NUM) / 記錄未求過位勢的位置 cpi(l)=i; cpj(l)=j; l+; else if(x(i,j)BIG_NUM & u(i)BIG_NUM) v(j)=c(i,j)-u(i); else if(x(i,j)BIG_NUM & v(j)0) while (true) ip=0; for(k=0;k=BIG_NUM & v(j)=BIG_NUM & x(i,j)BIG_NUM) /記錄未求過位勢的位置 cpi(ip)=i; cpj(ip)=j; ip+; else if(x(i,j)BIG_NUM & u(i)BIG_NUM) v(j)=c(i,j)-u(i); else if(x(i,j)BIG_NUM & v(j)BIG_NUM) u(i)=c(i,j)-v(j); /end for k if ( ip = 0 ) break; l = ip; / end for while / 求檢驗(yàn)數(shù) for ( i = 0; i m; i+ ) for(j=0;j= BIG_NUM) s(i,j)=c(i,j)-u(i)-v(j); / 求最小檢驗(yàn)數(shù) Cmin = BIG_NUM; for(i=0;im;i+) for(j=0;js(i,j) Cmin=s(i,j); I0= i; J0=j; if ( Cmin = 0 ) return; / 已經(jīng)得到最優(yōu)解,返回主程序 / 此時(shí)找到了入基變量 X( I0, J0 ) / 求閉回路 for ( k = 0; k = 4