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

1工厂原料运输问题课程设计报告一、课程设计的目的《运筹与最优化方法》是信息与计算科学专业的一门重要的专业课程，是一门综合应用课程。主要内容包括：线性规划、整数规划、动态规划、非线性规划、库存论、排队论、博奕论、图与网络分析的基本概念、方法和模型等，以及有广泛应用前景的运筹学问题的启发式算法。《运筹学与最优化方法》中的运输问题是一种应用广泛的网络最优化模型，该模型的主要目的是为物资调运，车辆调度选择最经济的运输路线。《运筹学与最优化方法》运输问题课程设计的目的是为了适应信息管理与信息系统培养目标的要求，使我们学习掌握如何应用运筹学中的数量方法与模型来分析通过计算机来实现研究现代企业生产与技术管理以及经营管理决策问题。课程设计使我们能成熟的理解和应用运筹学模型，使我们认识运筹学在生产与技术管理和经营管理决策中的作用，领会其基本思想和分析与解决问题的思路。为我们以后毕业参加工作单位的策略策划打下坚实的基础。二、课程设计地点：第三实验楼4楼，运筹学实验室三、课程设计时间：第十八周，第十九周四、课程设计原理与过程（一）运输问题的内容及其解决方法运输问题是一种应用广泛的网络最优化模型，该模型的主要目的是为物资调运、车辆高度选择最经济的运输路线。有些问题，如m台机床加工零件问题、工厂合理布局问题，虽要求与提法不同，经适当变化也可以使用本模型求得最付佳方案。运输问题的一般提法：某种物资有m个产地Ai，产量是ai（i＝1，2,…,m），有m个销售地Bi，销量(需求量)是bj(j=1,2,…,m)。若从Ai运到Bi单位运价为dij(i=1,2,…,m;j=1,2,…,m),又假设产销平衡，即minjjiba11问如何安排运输可使总运费最小？若用xij(i=1,2,…,m;j=1,2,…,n)表示由Ai运到Bj的运输量，则平衡运输问题可写出以下线性规划模型：minjijijxdZ11min约束条件2),...,2,1;...,2,1(0)...,2,1()...,2,1(11njmixnjbxmiaxijmijijnjiij具体问题如下：三个工厂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111111111111111111行行nm易知此矩阵的任何一个m+n阶子方阵对应的行列式等于零，所以系数矩阵的秩≤m+n-1，并可证明运输问题的约束方程组系数矩阵的秩为m+n-1.由此可知运输问题只有m+n-1个独立的约束方程，即其基本可行解中基变量个数为m+n-1，其余均为非基变量。由于运输问题的以上特征，可用更简便的方法进行计算，即表上作业法。表上作业法原理同于单纯形法，首先给出一个初始的调运方案(实际上是初始基本可行解)，求出各非基变量的检验数去判定当前解是否为最优解，若不是则进行方案调整(即从一个基本可行解转换成另一个基本可行解)，再判定是否为最优解，重复以上步骤，直到获得最优解为止。这些步骤在表上进行十分方便。操作过程在表上进行，具体的表如下：表23B1B2B3产量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377销量7210241215初始调运方案如下表：表3B1B2B3产量A14568×8×56A216×2441164182A3816166124×77销量7210241215上表中“×”表示非基变量。最优解的判定如下表B1B2B3产量uiA14568○-48○4560A216○0244116418212A3816166124○16774销量7210241215vj4124上表中带圈的数字所表示的是非基变量。若令λij=dij-(ui+vj)(dij为非基变量所在的空格处的运费)，称λij为空格检验数。可以证明λij就是单纯形法中的检验数。所以用判定最优解的原则也同于单纯形法中的判定定理。当λij0时，即可得到最优解，若λij≯0，则返回上一级操作。直到得到最优解。（二）运输问题课程设计源程序代码//#includestdafx.h#includefstream#includeiomanip#includeiostream#includecmathusingnamespacestd;4#definea(j)(*(C+(M-1)*N+j))//销量数组#defineb(i)(*(C+i*N+N-1))//产量数组#definec(i,j)(*(C+i*N+j))//运价数组#definex(i,j)(*(X+i*(N-1)+j))//运量数组constdoubleBIG_NUM=1.0E15;//任意大数//(BIG_NUM:基本解,=BIG_NUM:运量为0)#defines(i,j)(*(S+i*(N-1)+j))//检验数数组Sij*/#defineu(i)(*(U+i))//位势数组Ui#definev(i)(*(V+i))//位势数组Vi#definecpi(k)((CP+k)-i)//闭回路点i标#definecpj(k)((CP+k)-j)//闭回路点j标#definecpf(k)((CP+k)-f)//闭回路点f标/*f=0:j++;f=1:i--;f=2:j--;f=3:i++;*/voidTP(intM,intN,double*C,double*X);intmain(){intM,N,i,j;double*C;//存储运价,产量及销量double*X;//存储运量分配方案doublez;ifstreaminfile;charfn[80];doublesum;cout.setf(ios_base::left,ios_base::adjustfield);cout.setf(ios_base::fixed,ios_base::floatfield);cout.precision(3);cout请输入数据文件名:;cinfn;infile.open(fn);if(!infile){5cout文件打开失败!\n;system(pause);exit(0);}infileMN;M++;N++;X=newdouble[sizeof(double)*(M-1)*(N-1)];C=newdouble[sizeof(double)*M*N];//把运价,供应量和需求量的数据读入到数组c(i,j)for(i=0;iM;++i)for(j=0;jN;++j){infilez;c(i,j)=z;}infile.close();cout\n=============数据文件================\n;for(i=0;iM;++i){for(j=0;jN;++j)coutsetw(10)c(i,j);coutendl;}system(pause);TP(M,N,C,X);//输出产销分配方案cout\n=============最优解===================\n;sum=0;for(i=0;iM-1;++i){for(j=0;jN-1;++j)if(x(i,j)=BIG_NUM)coutsetw(10)******;6else{coutsetw(10)x(i,j);sum+=(x(i,j)*c(i,j));}coutendl;}//cout\n\n\tTheminCostis:%-10.4f\n,sum);cout\n\n\t最高产量:setw(10)sumendl;//我们现在是在求max，max=-minfree(X);free(C);system(pause);return0;}//记录闭回路点结构structPATH{inti,j,f;};voidTP(intM,intN,double*C,double*X){double*U,*V,*S;intMN1,m,n;structPATH*CP;intk,i,j,l,k1,l1,ip;doubleCmin,sum;intI0,J0,Imin,Jmin;intfi,fj,fc,f;MN1=(M-1)+(N-1)-1;m=M-1;n=N-1;S=newdouble[sizeof(double)*(M-1)*(N-1)];U=newdouble[sizeof(double)*M];V=newdouble[sizeof(double)*N];CP=newPATH[sizeof(structPATH)*(MN1+1)];7//解初始化Xij=BIG_NUMfor(i=0;im;++i)for(j=0;jn;++j)x(i,j)=BIG_NUM;//最小元素法求初始可行解for(k=0;kMN1;++k){Cmin=BIG_NUM;for(i=0;im;++i){fi=0;for(l=0;lk;++l)//去除已经用过的行if(i==cpi(l)){fi=1;break;}if(fi==1)continue;for(j=0;jn;++j){fj=0;for(l=0;lk;++l)//去除已经用过的列if(j==cpj(l)){fj=1;break;}if(fj==1)continue;if(Cminc(i,j)){Cmin=c(i,j);I0=i;J0=j;}}//endforj}//endfori8//得到了未划去的最小运价所在格的坐标(I0,J0)和最小运价Cminif(k0)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;}elseif(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;}}//endfork用最小元素法求得了初使可行解//输出初始可行解cout\n=============初始解===================\n;sum=0;for(i=0;iM-1;i++){for(j=0;jN-1;j++)if(x(i,j)=BIG_NUM)coutsetw(10)******;else{coutsetw(10)x(i,j);sum+=(x(i,j)*c(i,j));9}coutendl;}cout\n\n\t初始产量:setw(10)sumendl;//我们现在是在求max，max=-minsystem(pause);while(true){//位势置初值Ui,Vi=BIG_NUMfor(i=0;im;i++)u(i)=BIG_NUM;for(j=0;jn;j++)v(j)=BIG_NUM;//求位势l=0;u(0)=