《《运筹学》-运输问题课程设计报告.docx》由会员分享，可在线阅读，更多相关《《运筹学》-运输问题课程设计报告.docx（27页珍藏版）》请在三一文库上搜索。
1、运筹学 - 运输问题课程设计报告一、课程设计的目的运筹与最优化方法是信息与运算科学专业的一门重要的专业课程，是一门综合应用课程。要紧内容包括：线性规划、整数规划、动态规划、非线性规划、库存论、排队论、博奕论、图与网络分析的差不多概念、方法和模型等，以及有广泛应用前景的运筹学咨询题的启发式算法。运筹学与最优化方法中的运输咨询题是一种应用广泛的网络最优化模型，该模型的要紧目的是为物资调运，车辆调度选择最经济的运输路线。运筹学与最优化方法运输咨询题课程设计的目的是为了适应信息治理与信息系统培养目标的要求，使我们学习把握如何应用运筹学中的数量方法与模型来分析通过运算机来实现研究现代企业生产与技术治理以
2、及经营治理决策咨询题。课程设计使我们能成熟的明白得和应用运筹学模型，使我们认识运筹学在生产与技术治理和经营治理决策中的作用，领会其差不多思想和分析与解决咨询题的思路。为我们以后毕业参加工作单位的策略策划打下坚实的基础。三、课程设计时刻：第十八周，第十九周四、课程设计原理与过程（一）运输咨询题的内容及其解决方法运输咨询题是一种应用广泛的网络最优化模型，该模型的要紧目的是为物资调运、车辆高度选择最经济的运输路线。有些咨询题，如 m 台机床加工零件咨询题、工厂合理布局咨询题，虽要求与提法不同，经适当变化也能够使用本模型求得最付佳方案。运输咨询题的一样提法：某种物 有 m 个 地 Ai ， 量是 ai
3、（i 1，2,m），有 m 个 售地 Bi ， 量 (需求量 )是 bj(j=1,2, ,m)。若从 Ai 运到 Bi 位运价 dij(i=1,2, , m;j=1,2,m),又假 平 ，即mnaibji1j1咨 如何安排运 可使 运 最小？若用 xij(i=1,2, ,m;j=1,2, ,n)表示由 Ai 运到 Bj 的运 量， 平 运 咨 可写出以下 性 划模型：mnnmin Zdij xijxijai (ii 1j 11,2., m) 束条件j 1mxijbj ( j1,2.,n)i 1具xij体0咨(i询1题,2.如,下m;：j 1,2,.,n)三个工厂 B1，B2，B3，它 需要同一
4、种原料， 数量分不是 72 吨、 102 吨、 41 吨，另外有三座 A1 、A2、 A3 能 供 上述原料 56 吨、 82 吨、 77 吨，由于工厂和 位置不同， 位运价不同，具体数据如表1。 如何安排运 方案，才能使 运 最小？表 1BBB产量123A148856A216241682A81624773销量7210241215解决方法用表上作 法，具体原理和方法如下： 看运 咨 的 性 划模型可知： 它有 m*n 具 量，(m+n)个 束方程，其系数矩 0-1 矩 ，且有大量的零，通常称 稀疏矩 ，形如：111x11x12 x1nx21x22 x2n xm1xm2 xmn111行m1111
5、11111行n111易知此矩阵的任何一个m+n 阶子方阵对应的行列式等于零，因此系数矩阵的秩 m+n-1，并可证明运输咨询题的约束方程组系数矩阵的秩为m+n-1.由此可知运输咨询题只有m+n-1 个独立的约束方程，即其差不多可行解中基变量个数为m+n-1，其余均为非基变量。由于运输咨询题的以上特点，可用更简便的方法进行运算，即表上作业法。表上作业法原理同于单纯形法，第一给出一个初始的调运方案(实际上是初始差不多可行解 )，求出各非基变量的检验数去判定当前解是否为最优解，若不是则进行方案调整(即从一个差不多可行解转换成另一个差不多可行解 )，再判定是否为最优解，重复以上步骤，直到获得最优解为止。
6、这些步骤在表上进行十分方便。操作过程在表上进行，具体的表如下：表 2B1B2B3A1488x11x12xA2162416x21x22xA381624x31x32x销量7210241产量561382237733215初始调运方案如下表：表 3B1B2B3产量A14885656A2162416824141A381624771661销量7210241215上表中“”表示非基变量。最优解的判定如下表B1B2B3产量uiA148856056-44A2162416821241410A381624774166116销量7210241215vj4124上表中带圈的数字所表示的是非基变量。若令 ij=dij-(
7、ui+vj)(dij为非基变量所在的空格处的运费)，称 ij 为空格检验数。能够证明ij 确实是单纯形法中的检验数。因此用判定最优解的原则也同于单纯形法中的判定定理。当ij0 时，即可得到最优解，若 ij 0，则返回上一级操作。直到得到最优解。（二） 运输咨询题课程设计源程序代码/ #include stdafx.h#include#include#include#includeusing#define#definenamespacestd;a(j)(* (C+(M-1)*N+j)b(i)(* (C+i*N+N-1)/销量数组/产量数组#definec(i,j)(* (C+i*N+j)/运价数
8、组#definex(i,j)constdouble(* (X+i*(N-1)+j) BIG_NUM =1.0E15;/运量数组/ 任意大数/(= 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+;*/voidT
9、P(int M,int N,double *C,double *X);intmain()intM,N,i,j;double* C; / 储备运价 , 产量及销量 double* X; / 储备运量分配方案doublez;ifstreaminfile;charfn80;doublesum;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+;
10、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=BI
11、G_NUM)coutsetw(10)*;elsecoutsetw(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=-minfree(X);free(C);system(pause);return0;/ 记录闭回路点结构structPATHint i,j,f;voidTP(int M,int N,double* C,double* X)double *U, *V , *S;intMN1,m
12、,n;structPATH*CP;intk,i,j,l,k1,l1,ip;doubleCmin,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_NUMfor(i=0;im;+i)for(j=0;jn;+j)x(i
13、,j)=BIG_NUM;/ 最小元素法求初始可行解for(k=0;kMN1;+k)Cmin=BIG_NUM;for(i=0;im;+i)fifor=(0;l=0;lk;+l)/去除差不多用过的行if(i=cpi(l)fi=1;break;iffor( jfi = continue; = 0; j1) n; +j)fjfor=(0;l=0;lc(i,j)Cmin=c(i,j);I0=i;J0=j;/endforj/endfori/得到了未划去的最小运价所在格的坐标(I0,J0)和最小运价 Cminif(k0)if(Cmin=BIG_NUM&cpi(k-1)=0)for(l1=0;l1m;l1+)
14、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;elsecpi(k)=-1;cpj(k)=J0;x(I0,J0)=a(J0 );b(I0)-=a( J0 );a(J0)=0;/endfork用最小元素法求得了初使可行解/ 输出初始可行解co
15、utn=初始解=n;sum=0;for(i=0;iM-1;i+)for(j=0;j=BIG_NUM)coutsetw(10) *;elsecoutsetw(10)x(i,j);sum+=(x(i,j)*c(i,j);coutendl;coutnnt 初始产量 :setw(10)sumendl;/我们现在是在求 max，max=-minsystem(pause);while(true)/位势置初值Ui,Vi=BIG_NUMfor(i=0;im;i+)for(u(ji=)0;=jBIG_NUM;n;j+)v(j)=BIG_NUM;/ 求位势l=0;u(0)=0;for(i=0; i m; i+ )
16、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)
17、-u(i);else if(x(i,j)BIG_NUM &v(j)BIG_NUM)u(i)=c(i,j)-v(j);/endfor kif(ip=0 )break;l=ip;/endforwhile/ 求检验数for(i=0;im;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 return;=/0)差不多得到最优解,返回主程序/现在找到了入基变量X(I0,J0)/ 求闭回路for(k=0;k
18、=4)break;/幸免反向搜索if(k0)if(f=0&cpf(k-1)=2)continue;elseif(f=1&cpf(k-1)=3)continue;elseif(f=2&cpf(k-1)=0)continue;elseif(f=3&cpf(k-1)=1)continue;if(f=0)/沿j+方向搜索while(true)j+;if(j=n)fc=2;break;if(i=I0&j=J0)fc=1;break;if(s(i,j)=BIG_NUM)fc=3;break;else/ifend(forfj+=1)/沿i-方向搜索while(true)i-;if(i=BIG_NUM)fc=
19、3;break;/endfori-elseif(f=2)/沿j-方向搜索while(true)j-;if(j=BIG_NUM)fc=3;break;/endforj-elseif (f=3)/沿i+方向搜索while(true)i+;if(i=m)fc=2;break;if(i=I0&j=J0)fc=1;break;if(s(i,j)=BIG_NUM)fc=3;break;if/(endfcfor =i+1|fc=3)break;/endforwhileflag2if(fc=0)k-;/沿此方向搜索失败 ,退回到前一点elseif(fc=1)break;/搜索完成elseif(fc=3)/沿此
20、方向搜索成功 ,前进一点k+;cpi(k)=i;cpj(k)=j;cpf(k)=-1;/endwhile/ 去除闭回路中的非转折点l=0;while(lk-1)i=l+1;while(i ( l+ 1 )jk1=l=k+ 1; - (i-j);/如果某些点前进方向相同,则去除中间各点while(i=k)cpi(j)=cpi(i);cpj(j)=cpj(i);cpf(j)=cpf(i);i+;j+;l+=2;k=k1;elsel+;/endforwhilelk- 1/ 查找闭回路上差不多解的最小值Cmin=x(cpi(1),cpj(1);Imin=cpi(1);Jmin=cpj(1);for(
21、i=3;i x(cpi(i),cpj(i)Cmin=x(cpi(i),cpj(i);IminJmin=cpi(cpj(ii););/ 换入基变量x(I0,J0)=Cmin;for(i=1;i=k;i+=2)x(cpi(i),cpj(i)-=Cmin;couthaox(cpi(i),cpj(i);if(i+1)=k)x(cpi(i+1),cpj(i+1)+=Cmin;x(Imin,Jmin )= BIG_NUM;deleteCP;deleteV;deleteU;deleteS;（三）测试运行结果文本中输入如下并将其储存在D 盘下，文件名： yc.txt33488561624168281624777210241输出结果为：五、运行结果分析0560最优解矩阵为： x*09741最优值 Z*56 8 977250244116 72 8 5 16 4088六、课程设计总结通过对运筹学运输咨询题的课程设计对运筹学的书本知识得到了进一步的巩固，具体化确实是加深了我对运输咨询题深层明白得，使我们能成熟的明白得和应用运筹学模型，使我们认识运筹学在生产与技术治理和经营治理决策中的作用，领会其差不多思想和分析与解决咨询题的思路。为我们以后毕业参加工作单位的策略策划打下坚实的基础。还又我了解并发觉了专门多调试程序的方法，而且明白得了如何处理错误的方法。对 C