运输规划问题研究及应用

1、运筹学课程设计运输规划问题研究及应用院（系）名称 信息工程学院 专 业 班 级 * 学 号 * 学 生 姓 名 * 指 导 教 师 * 2013 年 06 月 09日课程设计任务书20122013学年第二学期专业班级： 10普本信息与计算科学 学号： * 姓名： * 课程设计名称： 运筹学 设计题目： 运输规划问题研究及应用 完成期限：自 2013 年 06月 09 日至2013年06 月16日共 7天设计依据、要求及主要内容： 一、设计目的 熟练掌握运输规划问题模型,并能理解运输规划的概念与理论,能够较熟练地应用lingo软件编写求解运输规划方程的程序和应用lingo软件进行案例求解. 二、

2、设计内容 （1）认真挑选有代表性的运输规划案例（2）运输规划在不同的环境情况下的模型建立（3）建立的模型对不同的问题进行求解分析（4）运输规划模型在实际生活中的扩展应用. 三、设计要求 1先用运输规划中的相应模型选定案例. 2然后使用所用的案例编写lingo程序求解. 计划答辩时间：2013年 06 月 16 日工作任务与工作量要求： 查阅文献资料不少于3篇,课程设计报告1篇不少于3000字指导教师（签字）： 教研室主任（签字）： 批准日期： 2013 年 06 月 09 日 课程设计说明书（论文） 第 II页运输规划问题研究及应用摘 要 运输问题是特殊的线性规划问题,在运筹学中占有重要地位,

3、而费用最小化是经常遇到的一个问题.在社会的经济生产活动中,企业与客户都会想方设法合理调拨资源、降低费用,实现双方利益最大化,完成资源优化配置.本文以使费用成本最低为研究对象,列举多个实际问题建立基本运输模型,并针对不同的模型用Lingo算法解决运输模型中的问题. 关键词：运输规划,优化配置, Lingo算法 目 录1 研究背景12 运输规划模型的建立12.1 产销平衡问题的模型建立12.2 产销不平衡问题的模型建立22.21 产大于销的模型建立22.22 产大于销的模型建立22.3 运输问题的特点43 运输规划问题的实例分析53.1 运输问题53.2 采购问题84 运输规划问题的应用及前景11

4、总 结12参考文献12 课程设计说明书（论文） 第 11 页1 研究背景运输问题是社会经济生活和军事活动中经常出现的优化问题,是特殊的线性规划问题,它是早期的线性网络最优化的一个例子.运输问题不仅代表了物资合理调运、车辆合理调度等问题,有些其他类型的问题经过适当变换后也可以归结为运输问题,如最小费用流问题、最短路问题、指派问题可转化为运输问题或转运问题.运输问题在运筹学教学过程中占有重要地位,并且得到了众多学者的广泛关注,取得了许多重要的研究成果.但在我们的运筹学教材中仅仅介绍运输问题的基础理论知识,对于运输中的实际问题及计算机的应用都没有深入介绍.为此,我小组在介绍运输问题的基本理论和方法的

5、基础上,列举实例运用传统的表上作业法和LINGO软件两种方法解决问题.2 运输规划模型的建立一般的运输问题就是要解决把某种产品从若干产（供应）地调运到若干销地,在每个产地的供应量与每个销地的需求量已知（供销近似相等）,并知道各地之间的运输单价的前提下,确定一个使得总的运输费用最小的方案.2.1 产销平衡问题的模型建立 已知有m个场,其中表示某物资的m个产地；表示某物质的n个销地;表示产地的产量；表示销地的销量；表示把物资从产地Ai运往销地的单位运价.设为从产地运往销地的运输量,得到下列一般运输量问题的模型：其中包含个变量,个约束条件,其系数矩阵是行,列的矩阵,即的系数向量分量中除第个和第个元素

6、为1外,其余都为0.对于产销平衡的问题有所以模型中最多有个独立的约束方程,即系数矩阵的秩不超过.2.2 产销不平衡问题的模型建立在实际生活中许多问题都是产销不平衡的问题,即可以产大于销,亦可以销大于产.因此产销不平衡问题可以转化为产销平衡问题来解决.2.21 产大于销的模型建立当产量大于销量时则问题模型为此时,要将多余的物资在生产地储存起来,假设一虚拟销售地的运费为0,即设表示产地多生产的物资数量,运费为,其目标函数不变.于是问题的模型变为即转化为产销平衡的为题了.2.22 产大于销的模型建立当产大于销时有则问题模型为此时,实际中即出现了供不应求的情况,可假设有一个虚拟的产地所缺的物资即设表示

7、产地多生产的物资数量,运费为,其目标函数不变.于是问题的模型变为即转化为产销平衡的为题了.2.3 运输问题的特点运输问题具有的特点：（1）约束条件系数矩阵的元素等于0或1；（2）约束条件系数矩阵的每一列有两个非零元素,这对应于每一个变量在前m个约束方程中出现一次,在后n个方程中也出现一次.对产销平衡运输问题,还有以下特点：（1）所有结构约束条件都是等式约束；（2）各产地产量之和等于各销地销量之和.3 运输规划问题的实例分析3.1 运输问题 重庆有三家电子厂分别是新普,隆宇和恒华,生产的笔记本电脑将要运向北京,天津,广东,上海四个城市销售,其产量和销售量见下表：（单位：万台）表：1-1北京天津广

8、东上海产量新普626730隆宇495325恒华881521销量15172212-问：哪种销售方案将会取得最少的运输费用,费用为多少？针对该运输问题,为了方便计算,可以设新普（A1）,隆宇（A2）和恒华（A3）分别销往北京（B1）、天津（B2）、广东（B3）和上海（B4）四个城市销售量为.建立以下模型：表：1-2B1B2B3B4产量A1626730A2495325A3881521销量15172212-目标（The objective）最少费用：约束条件：供应限制（The supply constrains） 指标约束（The damand constrains） LINGO模型：model:se

9、ts:origin/1.3/:a;sale/1.4/:b;routes(origin,sale):c,x;endsetsdata:a=30,25,21;b=15,17,22,12;c=6,2,6,7,4,9,5,3,8,8,1,5;enddataOBJmin=sum(routes:c*x);for(origin(i):SUPsum(sale(j):x(i,j)<=a(i);for(sale(j):DEMsum(origin(i):x(i,j)=b(j);endlingo结果： Global optimal solution found. Objective value: 161.0000

10、 Infeasibilities: 0.000000 Total solver iterations: 6 Variable Value Reduced Cost X( 1, 1) 2.000000 0.000000 X( 1, 2) 17.00000 0.000000 X( 1, 3) 1.000000 0.000000 X( 1, 4) 0.000000 2.000000 X( 2, 1) 13.00000 0.000000 X( 2, 2) 0.000000 9.000000 X( 2, 3) 0.000000 1.000000 X( 2, 4) 12.00000 0.000000 X(

11、 3, 1) 0.000000 7.000000 X( 3, 2) 0.000000 11.00000 X( 3, 3) 21.00000 0.000000 X( 3, 4) 0.000000 5.000000 Row Slack or Surplus Dual Price OBJ 161.0000 -1.000000 SUP( 1) 10.00000 0.000000 SUP( 2) 0.000000 2.000000 SUP( 3) 0.000000 5.000000 DEM( 1) 0.000000 -6.000000 DEM( 2) 0.000000 -2.000000 DEM( 3)

12、 0.000000 -6.000000 DEM( 4) 0.000000 -5.000000从计算结果可以得出,新普（A1）分别销往北京（B1）、天津（B2）、广东（B3）和上海（B4）四个城市销售量为分别为2万台,17万台,1万台,0万台,剩余10万台；隆宇（A2）分别销往北京（B1）、天津（B2）、广东（B3）和上海（B4）四个城市销售量为别为13万台,0万台,0万台,12万台,剩余0万台；恒华（A3）分别销往北京（B1）、天津（B2）、广东（B3）和上海（B4）四个城市销售量为分别为0万台,0万台,21万台,0万台,剩余0万台；总费用为161个单位.3.2 采购问题某公司去外地采购A、B

13、、C、D四种规格的商品,数量分别为：1500个,2000个,3000个,3500个现有甲、乙、丙三个城市的供应商可以供应这些商品,供应数量分别为2500个,2500个,5000个由于这三个供应商的商品质量、运价不同,使销售情况有差异,预计售出后的利润(元个)也不同,详见表3-5所示请帮助该公司制定一个预期盈利最大的采购方案表3-5预计销售利润表商品供应商 利润/(元/个)ABCD甲10567乙8276丙9348设表示第i(i=1,2,3)个城市供应第j(j=1,2,3,4)种规格的产品的数量.则建立模型如下：s.t. (i=1,2,3;j=1,2,3,4)用lingo编程求解如下：model:

14、sets:demand/1.4/:a;supply/1.3/:b;link(supply,demand):c,x;endsetsdata:a=1500 2000 3000 3500;b=2500 2500 5000;c=10 5 6 78 2 7 69 3 4 8;enddatamin=sum(link:c*x);for(supply(i):sum(demand(j):x(i,j)<=b(i);for(demand(j):sum(supply(i):x(i,j)=a(j);for(link:gin(x);end运行结果如下： Global optimal solution found.

15、Objective value: 53500.00 Extended solver steps: 0 Total solver iterations: 3 Variable Value Reduced Cost A( 1) 1500.000 0.000000 A( 2) 2000.000 0.000000 A( 3) 3000.000 0.000000 A( 4) 3500.000 0.000000 B( 1) 2500.000 0.000000 B( 2) 2500.000 0.000000 B( 3) 5000.000 0.000000 C( 1, 1) 10.00000 0.000000

16、 C( 1, 2) 5.000000 0.000000 C( 1, 3) 6.000000 0.000000 C( 1, 4) 7.000000 0.000000 C( 2, 1) 8.000000 0.000000 C( 2, 2) 2.000000 0.000000 C( 2, 3) 7.000000 0.000000 C( 2, 4) 6.000000 0.000000 C( 3, 1) 9.000000 0.000000 C( 3, 2) 3.000000 0.000000 C( 3, 3) 4.000000 0.000000 C( 3, 4) 8.000000 0.000000 X(

17、 1, 1) 0.000000 10.00000 X( 1, 2) 0.000000 5.000000 X( 1, 3) 0.000000 6.000000 X( 1, 4) 2500.000 7.000000 X( 2, 1) 1500.000 8.000000 X( 2, 2) 0.000000 2.000000 X( 2, 3) 0.000000 7.000000 X( 2, 4) 1000.000 6.000000 X( 3, 1) 0.000000 9.000000 X( 3, 2) 2000.000 3.000000 X( 3, 3) 3000.000 4.000000 X( 3,

18、 4) 0.000000 8.000000 Row Slack or Surplus Dual Price 1 53500.00 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000由以上结果不难看出分别从甲、乙、丙地采购A、B、C、D四种规格商品的数量,从甲城市购D商品2500个,从乙购A商品1500个,D商品1000个,从丙城市购B商品2000,C商品3000个可以使得预期最佳盈利最大为53500元.4 运输规划问题的应用及前景在社会、经济、军事等领域中,经常会遇到大宗物资的调运问题,如煤、钢铁、木材、粮食、军事装备等,在有若干生产地或存储地时,则需要根据已有的交通网制定调运方案,将这些物资运到消费或使用地,使总的运输费用最少或运输路