运输规划问题研究及应用

运筹学课程设计运输规划问题研究及应用院（系）名称 信息工程学院 专 业 班 级 * 学 号 * 学 生 姓 名 * 指 导 教 师 * 2013 年 06 月 09 日课程设计任务书20122013 学年第二学期专业班级： 10 普本信息与计算科学 学号： * 姓名： * 课程设计名称： 运筹学 设计题目： 运输规划问题研究及应用 完成期限：自 2013 年 06 月 09 日至 2013 年 06 月 16 日共 7 天设计依据、要求及主要内容：一、设计目的 熟练掌握运输规划问题模型,并能理解运输规划的概念与理论,能够较熟练地应用lingo软件编写求解运输规划方程的程序和应用lingo软件进行案例求解. 二、设计内容 （1）认真挑选有代表性的运输规划案例 （2）运输规划在不同的环境情况下的模型建立 （3）建立的模型对不同的问题进行求解分析 （4）运输规划模型在实际生活中的扩展应用. 三、设计要求 1先用运输规划中的相应模型选定案例. 2然后使用所用的案例编写lingo程序求解. 计划答辩时间：2013 年 06 月 16 日工作任务与工作量要求： 查阅文献资料不少于 3 篇,课程设计报告 1 篇不少于 3000 字指导教师（签字）： 教研室主任（签字）： 批准日期： 2013 年 06 月 09 日课程设计说明书（论文） 第 I 页运输规划问题研究及应用摘 要运输问题是特殊的线性规划问题,在运筹学中占有重要地位,而费用最小化是经常遇到的一个问题.在社会的经济生产活动中,企业与客户都会想方设法合理调拨资源、降低费用,实现双方利益最大化,完成资源优化配置.本文以使费用成本最低为研究对象,列举多个实际问题建立基本运输模型,并针对不同的模型用 Lingo 算法解决运输模型中的问题. 关键词：运输规划,优化配置, Lingo 算法 课程设计说明书（论文） 第 II 页目 录1 研究背景 .12 运输规划模型的建立 .12.1 产销平衡问题的模型建立 .12.2 产销不平衡问题的模型建立 .22.21 产 大于销 的模型建立 .22.22 产大于销的模型建立 .22.3 运输问题的特点 .43 运输规划问题的实例分析 .53.1 运输问题 .53.2 采购问题 .84 运输规划问题的应用及前景 .11总 结 .12参考文献 .12课程设计说明书（论文） 第 1 页11 研究背景运输问题是社会经济生活和军事活动中经常出现的优化问题,是特殊的线性规划问题,它是早期的线性网络最优化的一个例子.运输问题不仅代表了物资合理调运、车辆合理调度等问题,有些其他类型的问题经过适当变换后也可以归结为运输问题,如最小费用流问题、最短路问题、指派问题可转化为运输问题或转运问题.运输问题在运筹学教学过程中占有重要地位,并且得到了众多学者的广泛关注,取得了许多重要的研究成果.但在我们的运筹学教材中仅仅介绍运输问题的基础理论知识,对于运输中的实际问题及计算机的应用都没有深入介绍.为此,我小组在介绍运输问题的基本理论和方法的基础上,列举实例运用传统的表上作业法和 LINGO 软件两种方法解决问题.2 运输规划模型的建立一般的运输问题就是要解决把某种产品从若干产（供应）地调运到若干销地,在每个产地的供应量与每个销地的需求量已知（供销近似相等）,并知道各地之间的运输单价的前提下,确定一个使得总的运输费用最小的方案.2.1 产销平衡问题的模型建立已知有 m 个场,其中 表示某物资的 m 个产地； 表12Am、 、 、 12Bn、 、 、示某物质的 n 个销地; 表示产地 的产量； 表示销地 的销量； 表示把物资从isijdiijc产地 Ai运往销地 的单位运价.iB设 为从产地 运往销地 的运输量,得到下列一般运输量问题的模型：ijxii11mn(1,2.),. ,.,0(,.;.)nijiijimijjijzcxaimstxbjni课程设计说明书（论文） 第 2 页2其中包含 个变量, 个约束条件,其系数矩阵是 行, 列的矩阵,即 的mnnmnijx系数向量 T(0,1,0)ijimjp 行 行 ， ，分量中除第 个和第 个元素为 1 外,其余都为 0.ij对于产销平衡的问题有 mi ,=1111a()()nnmnijijjjxxb所以模型中最多有 个独立的约束方程,即系数矩阵的秩不超过 .n 1mn2.2 产销不平衡问题的模型建立在实际生活中许多问题都是产销不平衡的问题,即可以产大于销,亦可以销大于产.因此产销不平衡问题可以转化为产销平衡问题来解决.2.21 产大于销的模型建立当产量大于销量时 mi1=a,njb则问题模型为 1inmnijizcx1(,2.),. 1,.,0(,.;.)nijimijjijxastbjnxim此时,要将多余的物资 mi 1=1anjb在生产地储存起来,假设一虚拟销售地的运费为 0,即设 表示产地 多生产的,1inxiA课程设计说明书（论文） 第 3 页3物资数量,运费为 ,其目标函数不变.于是问题的模型变为,10(,2.)inxim1,11m,1i 1=1, (,2.),.,. a0(,2.;,.)nijinijiniijjninjijzcxaxbst bx n即转化为产销平衡的为题了.2.22 产大于销的模型建立当产大于销时有 mi1=a,njb则问题模型为 1inmnijizcx1(,2.),. 1,.,0(,.;.)nijimijjijxastbjnxim此时,实际中即出现了供不应求的情况,可假设有一个虚拟的产地所缺的物资 mi11=a,njnb即设 表示产地 多生产的物资数量,运费为 ,其目标函数不变.1,mjxjB1,0(,2)mjxn于是问题的模型变为课程设计说明书（论文） 第 4 页411,m1, i1=1,min(1,2.),.,. a0(,2.;,.)nijinijimijjjnnjjjimzcxaxbnstxij 即转化为产销平衡的为题了.2.3 运输问题的特点运输问题具有的特点：（1）约束条件系数矩阵的元素等于 0 或 1；（2）约束条件系数矩阵的每一列有两个非零元素,这对应于每一个变量在前 m 个约束方程中出现一次,在后 n 个方程中也出现一次.对产销平衡运输问题,还有以下特点：（1）所有结构约束条件都是等式约束；（2）各产地产量之和等于各销地销量之和.3 运输规划问题的实例分析3.1 运输问题重庆有三家电子厂分别是新普,隆宇和恒华,生产的笔记本电脑将要运向北京,天津,广东,上海四个城市销售,其产量和销售量见下表：（单位：万台）表：1-1北京 天津 广东 上海 产量新普 6 2 6 7 30隆宇 4 9 5 3 25恒华 8 8 1 5 21销量 15 17 22 12 -问：哪种销售方案将会取得最少的运输费用,费用为多少？课程设计说明书（论文） 第 5 页5针对该运输问题,为了方便计算,可以设新普（A 1） ,隆宇（A 2）和恒华（A 3）分别销往北京（B 1）、天津（B 2）、广东（B 3）和上海（B 4）四个城市销售量为.建立以下模型：1234234123xxxx、 、 、 、 、 、 、 、 、 、 、表：1-2B1 B2 B3 B4 产量A1 6 2 6 7 30A2 4 9 5 3 25A3 8 8 1 5 21销量 15 17 22 12 -目标（The objective）最少费用： 3432312423 231 211411214 5x8xx5 9x766zMin ijjic约束条件：供应限制（The supply constrains） 指标约束（ The damand constrains）21xx53034321214312 12xx715x x34241432211LINGO模型：model:sets:origin/1.3/:a;sale/1.4/:b;routes(origin,sale):c,x;endsetsdata:a=30,25,21;课程设计说明书（论文） 第 6 页6b=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.0000Infeasibilities: 0.000000Total solver iterations: 6Variable Value Reduced CostX( 1, 1) 2.000000 0.000000X( 1, 2) 17.00000 0.000000X( 1, 3) 1.000000 0.000000X( 1, 4) 0.000000 2.000000X( 2, 1) 13.00000 0.000000X( 2, 2) 0.000000 9.000000X( 2, 3) 0