《运筹学》- 运输问题课程设计报告.doc

工厂原料运输问题课程设计报告一、课程设计的目的运筹与最优化方法是信息与计算科学专业的一门重要的专业课程，是一门综合应用课程。主要内容包括：线性规划、整数规划、动态规划、非线性规划、库存论、排队论、博奕论、图与网络分析的基本概念、方法和模型等，以及有广泛应用前景的运筹学问题的启发式算法。运筹学与最优化方法中的运输问题是一种应用广泛的网络最优化模型，该模型的主要目的是为物资调运，车辆调度选择最经济的运输路线。运筹学与最优化方法运输问题课程设计的目的是为了适应信息管理与信息系统培养目标的要求，使我们学习掌握如何应用运筹学中的数量方法与模型来分析通过计算机来实现研究现代企业生产与技术管理以及经营管理决策问题。课程设计使我们能成熟的理解和应用运筹学模型，使我们认识运筹学在生产与技术管理和经营管理决策中的作用，领会其基本思想和分析与解决问题的思路。为我们以后毕业参加工作单位的策略策划打下坚实的基础。二、课程设计地点：第三实验楼4楼，运筹学实验室三、课程设计时间：第十八周，第十九周四、课程设计原理与过程（一）运输问题的内容及其解决方法运输问题是一种应用广泛的网络最优化模型，该模型的主要目的是为物资调运、车辆高度选择最经济的运输路线。有些问题，如m台机床加工零件问题、工厂合理布局问题，虽要求与提法不同，经适当变化也可以使用本模型求得最付佳方案。运输问题的一般提法：某种物资有m个产地Ai，产量是ai（i1，2,m），有m个销售地Bi，销量(需求量)是bj(j=1,2,m)。若从Ai运到Bi单位运价为dij(i=1,2,m;j=1,2,m),又假设产销平衡，即 问如何安排运输可使总运费最小？ 若用xij(i=1,2,m;j=1,2,n)表示由Ai运到Bj的运输量，则平衡运输问题可写出以下线性规划模型： 约束条件具体问题如下： 三个工厂B1，B2，B3，它们需要同一种原料，数量分别是72吨、102吨、41吨，另外有三座仓库A1、A2、A3可以供应上述原料56吨、82吨、77吨，由于工厂和仓库位置不同，单位运价不同，具体数据如表1。应如何安排运输方案，才能使总运费最小？表1B1B2B3产量A148856A216241682A38162477销量7210241215解决方法用表上作业法，具体原理和方法如下：观察运输问题的线性规划模型可知：它有m*n具变量，(m+n)个约束方程，其系数矩阵为0-1矩阵，且有大量的零，通常称为稀疏矩阵，形如：x11x12 x1nx21x22 x2n xm1xm2 xmn易知此矩阵的任何一个m+n阶子方阵对应的行列式等于零，所以系数矩阵的秩m+n-1，并可证明运输问题的约束方程组系数矩阵的秩为m+n-1.由此可知运输问题只有m+n-1个独立的约束方程，即其基本可行解中基变量个数为m+n-1，其余均为非基变量。由于运输问题的以上特征，可用更简便的方法进行计算，即表上作业法。表上作业法原理同于单纯形法，首先给出一个初始的调运方案(实际上是初始基本可行解)，求出各非基变量的检验数去判定当前解是否为最优解，若不是则进行方案调整(即从一个基本可行解转换成另一个基本可行解)，再判定是否为最优解，重复以上步骤，直到获得最优解为止。这些步骤在表上进行十分方便。操作过程在表上进行，具体的表如下：表2B1B2B3产量A14 x118 x128 x1356A216 x2124 x2216 x2382A38 x3116 x3224 x3377销量7210241215初始调运方案如下表：表3B1B2B3产量A14 568 8 56A216 24 4116 4182A38 1616 6124 77销量7210241215上表中“”表示非基变量。 最优解的判定如下表B1B2B3产量uiA14 568 8 560A216 24 4116 418212A38 1616 6124 774销量7210241215vj4124上表中带圈的数字所表示的是非基变量。若令ij=dij-(ui+vj)(dij为非基变量所在的空格处的运费)，称ij为空格检验数。可以证明ij就是单纯形法中的检验数。所以用判定最优解的原则也同于单纯形法中的判定定理。当ij0时，即可得到最优解，若ij0，则返回上一级操作。直到得到最优解。（二） 运输问题课程设计源程序代码/ #include stdafx.h #include #include #include #include using namespace std; #define a(j) (* (C+(M-1)*N+j) / 销量数组 #define b(i) (* (C+i*N+N-1) / 产量数组 #define c(i,j) (* (C+i*N+j) / 运价数组 #define x(i,j) (* (X+i*(N-1)+j) / 运量数组 const double BIG_NUM = 1.0E15; / 任意大数 / ( = BIG_NUM : 运量为 0 ) #define s(i,j) (*(S+i*(N-1)+j) / 检验数数组Sij */ #define u(i) (*(U+i) / 位势数组 Ui #define v(i) (*(V+i) / 位势数组 Vi #define cpi(k) (CP+k)-i) / 闭回路点 i 标 #define cpj(k) (CP+k)-j) / 闭回路点 j 标 #define cpf(k) (CP+k)-f) / 闭回路点 f 标 /* 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; / 存储运价, 产量及销量 double* X; / 存储运量分配方案 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; / 把运价, 供应量和需求量的数据读入到数组 c( i, j ) for(i=0;iM;+i) for(j=0;jz; c(i,j)=z; infile.close(); coutn= 数据文件 =n; for(i=0;iM;+i) for(j=0;jN;+j) coutsetw(10)c(i,j); coutendl; system(pause); TP(M,N,C,X); / 输出产销分配方案 coutn= 最优解 =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最高产量:setw(10)sumendl; /我们现在是在求max，max=-min free(X); free(C); system(pause); return 0; / 记录闭回路点结构 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 ) / 去除已经用过的行 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 / 得到了未划去的最小运价所在格的坐标(I0,J0)和最小运价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初始产量:setw(10)sumendl;/我们现在是在求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 / 求检验数 for ( i = 0; i m; i+ ) for(j=0;j= BIG_NUM) s(i,j)=c(i,j)-u(i)-v(j); / 求最小检验数 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; / 已经得到最优解,返回主程序 / 此时找到了入基变量 X( I0, J0 ) / 求闭回路 for ( k = 0; k = 4