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

1、1 / 15工厂原料运输问题课程设计报告一、课程设计的目的运筹与最优化方法 是信息与计算科学专业的一门重要的专业课程， 是一 门综合应用课程。 主要内容包括： 线性规划、整数规划、动态规划、非线性规划、 库存论、排队论、博奕论、图与网络分析的基本概念、方法和模型等，以及有广 泛应用前景的运筹学问题的启发式算法。运筹学与最优化方法中的运输问题是一种应用广泛的网络最优化模型， 该模型的主要目的是为物资调运，车辆调度选择最经济的运输路线。运筹学与最优化方法 运输问题课程设计的目的是为了适应信息管理与信 息系统培养目标的要求， 使我们学习掌握如何应用运筹学中的数量方法与模型来 分析通过计算机来实现研究

2、现代企业生产与技术管理以及经营管理决策问题。 课 程设计使我们能成熟的理解和应用运筹学模型， 使我们认识运筹学在生产与技术 管理和经营管理决策中的作用， 领会其基本思想和分析与解决问题的思路。 为我 们以后毕业参加工作单位的策略策划打下坚实的基础。二、课程设计地点：第三实验楼4楼， 运筹学实验室三、课程设计时间：第十八周，第十九周四、课程设计原理与过程(一)运输问题的内容及其解决方法 运输问题是一种应用广泛的网络最优化模型，该模型的主要目的是为物资 调运、车辆高度选择最经济的运输路线。有些问题，如m台机床加工零件问题、工厂合理布局问题， 虽要求与提法不同， 经适当变化也可以使用本模型求得最付

3、佳方案。运输问题的一般提法：某种物资有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),又假设产销平衡,即mnaibji 1 j 1问如何安排运输可使总运费最小？若用xij(i=1,2,m;j=1,2,n)表示由A运到B的运输量，则平衡运输 问题可写出以下线性规划模型：mnmin Zdijxiji1j1约束条件n2 / 15Xjja (i 1,2., m)j imXijbj(j 1,2.,n)i 1xij0(i1,2.,m; j 1,2,.,n)具体问题如下：三个工厂B1

4、,B,它们需要同一种原料，数量分别是72吨、102吨、41吨，另外有三座仓库A、A、A可以供应上述原料56吨、82吨、77吨，由于 工厂和仓库位置不同，单位运价不同，具体数据如表1。应如何安排运输方案，才能使总运费最小？表1BRB3产量A48856A16241682A8162477销量7210241215解决方法用表上作业法，具体原理和方法如下：观察运输问题的线性规划模型可知：它有m*n具变量，（m+n）个约束方程,其系数矩阵为0-1矩阵，且有大量的零，通常称为稀疏矩阵，形如:X11X12X1nX21X22X2nXmXm2Xmn1 11m行1 111 11111111n行111易知此矩阵的任何

5、一个m+n阶子方阵对应的行列式等于零，所以系数矩阵的 秩wm+n-1，并可证明运输问题的约束方程组系数矩阵的秩为m+n-1.由此可知运输问题只有m+n-1个独立的约束方程，即其基本可行解中基变量 个数为m+n-1，其余均为非基变量。由于运输问题的以上特征，可用更简便的方法进行计算，即表上作业法。表上作业法原理同于单纯形法，首先给出一个初始的调运方案（实际上是初 始基本可行解），求出各非基变量的检验数去判定当前解是否为最优解，若不是 则进行方案调整（即从一个基本可行解转换成另一个基本可行解），再判定是否为 最优解，重复以上步骤，直到获得最优解为止。这些步骤在表上进行十分方便。 操作过程在表上进行

6、，具体的表如下：表23 / 15B1B2B3产量A14X118X128X1356A216X2124X2216X2382A38X3116X3224X3377销量7210241215初始调运方案如下表:表3B1B2B3产量A14568x8x56A216x2441164182A3816166124x77销量7210241215上表中“x”表示非基变量最优解的判定如下表B1B2B3产量UiA14568CD8560A216244116418212A3816166124774销量7210241215vj4124上表中带圈的数字所表示的是非基变量。若令入j=dj-（ui+vj（dj为非基变量所在的空格处的运

7、费），称入j为空格检验数。可以证明入j就是单纯形法中的检验数。所以用判定最优解的原则也同于 单纯形法中的判定定理。当入j0时，即可得到最优解，若入j0,则返回上级操作。直到得到最优解。（二） 运输问题课程设计源程序代码/ #include stdafx.h#include#include#include#includeusing namespace std;4 / 15#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*(

8、N-1)+j)/运量数组constdoubleBIG_NUM =1.0E15;/任意大数/ (=JBIG_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(int M,int N,doub

9、le *C,double *X);int main()int M, N, i,double* C; /double* X; / doublez;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;j;存储运价,产量及销量存储运量分配方案5 / 15M+;N+;X=new

10、 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_

11、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，free(X);free(C);system(pause);return 0;/记录闭回路点结构max=-min6 / 15struct PATHint 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