运筹运输问题习题

运输问题：

1、分别用西北角法、最低费用法和运费差额法，求下面运输问题(见表)的初始可行解，并计算其目标

函数。(可不写步骤)

2、以上题中最低费用法所得的解为初始基础可性解，用表上作业法（踏石法）求出最优解。（要求列

出每一步的运费矩阵和基础可行解矩阵）

第七章 运筹学 运输问题案例

第七章运输问题 一个农民承包了6块耕地共300亩，准备播种小麦、玉米、水果和蔬菜四种农产品， 问如何安排种植计划，可得到最大的总收益。 解： 这是一个产销平衡的运输问题。可以建立下列的运输模型： 代入产销平衡的运输模板可得如下结果： 得种植计划方案如下表：

# 某客车制造厂根据合同要求从当年开始起连续四年年末交付40辆规格型号相同的大型客车。该厂在这四年内生产大型客车的能力及每辆客车的成本情况如下表： 根据该厂的情况，若制造出来的客车产品当年未能交货，每辆车每积压一年的存储和维护费用为4万元。在签订合同时，该厂已储存了20辆客车，同时又要求四年期未完成合同后还需要储存25辆车备用。问该厂如何安排每年的客车生产量，使得在满足上述各项要求的情况下，总的生产费用加储存维护费用为最少 ^ 解：得运价表（产大于销的运输模型）如下： | 得生产安排的方案：

第一季度正常上班生产20台，加班27台，拿出正常生产18台和加班2台，加上年前储存的20台，满足本季度的40台； 第二季度正常生产38台，不安排加班。加上第一季度储存的2台，满足本季度的40台； 第三季度正常生产15台，不安排加班。加上第一季度储存的25台，满足本季度的40台； 第四季度正常生产42台。加班生产23台。拿出正常生产的17台的加班生产的23台满足本季度的40台。剩余25台以后务用。 如下表表示： 某企业生产有甲、乙、丙、丁四个分厂生产同一种产品，这四个分厂的产量分别为：200吨、300吨、400吨和100吨，这些产品供应给A、B、C、D、E、F六个地区，六个地区的需求量分别为：200吨、150吨、350吨、100吨、120吨、120吨。由于工艺、技术的差别，各分厂运往各销售地区的单位运价（万元/吨）、各厂单位产品成本（万元/吨）和各销地的销售价格（万元/吨）如下表： （万元/吨）

浅谈运筹学中的运输问题.doc11

浅谈运筹学中的运输问题 摘 要：运筹学自二战以来开始打来那个应用在除战争以外的许多领域，尤其在企业管理中表现的尤为突出。运筹学的思想贯穿了企业管理的始终，在企业战略管理、生产计划、市场营销、运输问题、库存管理、人事管理、财务会计等各个方面都具有重要的作用，对企业管理的发展产生重要影响。这里我们主要对运输问题几种方法做一个简单的介绍。 关键词：最下元素法；沃格尔法（V ogel ） 首先我们先来介绍运输问题的数学模型：设有m 个产地（记作A 1，A 2，A 3,…,Am ），生产某种物资，其产量分别为a 1,a 2，…，am ；有n 个销地（记作B 1，B 2，…，Bn ），其需要量分别为b 1,b 2，…，bn ；且产销平衡，即 。从第i 个产地到j 个销地的单位运价为cij ，在满足各地需要的前提下，求总运输费用最小的调运方案。 设xij (i =1,2,…，m ；j =1,2,…,n )为第i 个产地到第j 个销地的运量，则数学模型为： n j m i x n j b x m i a x ij j m i ij n j i ij ,,1;,,1, 0,,1,,11 1 ==≥====∑∑== ∑∑ ===n j ij ij m i x c z 1 1 min （！）最小元素法：最小元素法的思想是就近优先运送，即最小运价Cij 对应的变量xij 优先赋值 {} j i ij b a x ,min = 然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后一个初始基可行解。 下面举一个例子：求表3－7给出的运输问题的初始基本可行解。

解： 在x 12、x 22、x 33、x 34中任选一个变量作为基变量，例如选x 12 初始基本可行解可用下列矩阵表示 ??????????634610 表3－8中，标有符号 的变量恰好是3+4－1=6个且不包含闭回路， {} 323123141312,,,,,x x x x x x 是一组基变量，其余标有符号×的变量是非基变量， （2）运费差额法（V ogel ）:最小元素法只考虑了局部运输费用最小，对整个产销系统的总运输费用来说可能离最优值较远。有时为了节省某一处的运费，而在其它处可能运费很大。运费差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案， 20101258515 10??????=?C 2010125815510? ?????=?C 15 15 15 15 前一种按最小元素法求得，总运费是Z 1=10×8+5×2+15×1=105，后一种方案考虑到C 11与C 21之间的差额是8－2=6，如果不先调运x 21，到后来就有可能x 11≠0，这样会使总运费增加较大，从而先调运x 21，再是x 22，其次是x 12这时总运费Z 2=10×5+15×2+5×1=85

运筹学(胡运权版)第三章运输问题课后习题答案

P66： 8.某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂A 1， A 2，A 3的生产量、各销售点B 1，B 2，B 3，B 4的销售量（假定单位为t ）以及各工厂到销售点的单位运价（元/t ）示于下表中，问如何调运才能使总运费最小？ 表 解：一、该运输问题的数学模型为： 可以证明：约束矩阵的秩为r (A) = 6. 从而基变量的个数为 6. 34 33323124232221 3141 141312116115893102114124min x x x x x x x x x x x x x c z i j ij ij +++++++++++== ∑∑ ==??? ??????????==≥=++=++=++=++=+++=+++=+++4,3,2,1;3,2,1,0141214822 1016342414332313322212312111343332312423222114131211j i x x x x x x x x x x x x x x x x x x x x x x x x x ij 111213142122232431323334x x x x x x x x x x x x 712111111111111111111111111??? ? ? ? ? ? ? ? ? ???

二、给出运输问题的初始可行解（初始调运方案） 1. 最小元素法 思想：优先满足运价（或运距）最小的供销业务。

其余（非基）变量全等于零。此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6). 总运费为（目标函数值） ,1013=x ,821=x ,223=x ,1432=x ,834=x ,614=x ∑∑===314 1 i j ij ij x c Z

运筹学实验_动态规划

实验二用MATLAB解决动态规划问题 问题:有一部货车每天沿着公路给四个售货店卸下6箱货物,如果各零售店出售该货物所得利润如下表所示,试求在各零售店卸下几箱货物,能使获得总利润最 解: 1)将问题按售货店分为四个阶段 2)设s k表示为分配给第k个售货店到第n个工厂的货物数, x k设为决策变量,表示为分配给第k个售货店的货物数, 状态转移方程为s k＋1＝s k－x k。 P k(x k)表示为x k箱货物分到第k个售货店所得的盈利值。 f k(s k)表示为s k箱货物分配给第k个售货店到第n个售货店的最大盈利值。 3)递推关系式: f k(s k)＝max[ P k(x k)+ f k+1(s k－x k) ] k=4,3,2,1 边界条件:f5(s5)＝0 4)从最后一个阶段开始向前逆推计算。 第四阶段: 设将s4箱货物(s4＝0,1,2,3,4,5,6)全部分配给4售货店时,最大盈利值为: f4(s4)＝max[P4(x4)] 其中x4＝s4＝0,1,2,3,4,5,6 x4*表示使得f4(s4)为最大值时的最优决策。 第三阶段:

设将s3箱货物(s3＝0,1,2,3,4,5,6)分配给3售货店与4售货店时,对每一个s3值,都有一种最优分配方案,使得最大盈利值为:f3(s3)＝max[ P3(x3)+ f4(s3－x3) ] ,x3＝ 第二阶段: 设将s2箱货物(s2＝0,1,2,3,4,5,6)分配给2售货店、3售货店与4售货店时,则最大盈利值为:f2(s2)＝max[ P2(x2)+ f3(s2－x2) ] 第一阶段: 设将s2箱货物(s1＝0,1,2,3,4,5,6)分配给1售货店、2售货店、3售货店与4售货店时,则最大盈利值为:f1(s1)＝max[ P1(x1)+ f2(s1－x1) ] 按计算表格的顺序反推,可知最优分配方案有6个: 1） x1*＝1,x2*＝1,x3*=3,x4*=1。 2） x1*＝1,x2*＝2,x3*=2,x4*=1。 3） x1*＝1,x2*＝3,x3*=1,x4*=1。

第七章 运筹学 运输问题案例

第七章运输问题 7.1 一个农民承包了6块耕地共300亩，准备播种小麦、玉米、水果和蔬菜四种农产品， 问如何安排种植计划，可得到最大的总收益。 解： 这是一个产销平衡的运输问题。可以建立下列的运输模型： 代入产销平衡的运输模板可得如下结果： 得种植计划方案如下表： 7.2 某客车制造厂根据合同要求从当年开始起连续四年年末交付40辆规格型号相同的大型客车。该厂在这四年内生产大型客车的能力及每辆客车的成本情况如下表： 根据该厂的情况，若制造出来的客车产品当年未能交货，每辆车每积压一年的存储和维

护费用为4万元。在签订合同时，该厂已储存了20辆客车，同时又要求四年期未完成合同后还需要储存25辆车备用。问该厂如何安排每年的客车生产量，使得在满足上述各项要求的情况下，总的生产费用加储存维护费用为最少？ 解：得运价表（产大于销的运输模型）如下： 第一季度正常上班生产20台，加班27台，拿出正常生产18台和加班2台，加上年前储存的20台，满足本季度的40台； 第二季度正常生产38台，不安排加班。加上第一季度储存的2台，满足本季度的40台； 第三季度正常生产15台，不安排加班。加上第一季度储存的25台，满足本季度的40台； 第四季度正常生产42台。加班生产23台。拿出正常生产的17台的加班生产的23台满足本季度的40台。剩余25台以后务用。 7.3 某企业生产有甲、乙、丙、丁四个分厂生产同一种产品，这四个分厂的产量分别为：200吨、300吨、400吨和100吨，这些产品供应给A、B、C、D、E、F六个地区，六个地区的需求量分别为：200吨、150吨、350吨、100吨、120吨、120吨。由于工艺、技术的差别，各分厂运往各销售地区的单位运价（万元/吨）、各厂单位产品成本（万元/吨）和各销地的销售价格（万元/吨）如下表：

运筹学--第七章 动态规划

１８９ 习题七7.1计算如图所示的从A 到E 的最短路线及其长度（单位：km ）： （1） 用逆推解法；2用标号法。 7.2 用动态规划方法求解下列问题 （1） max z ＝x 12x 2 x 33 x 1＋x 2＋x 3 ≤6 x j ≥0 （j ＝1,2,3） （2）min z ＝ 3x 12＋4x 22 ＋x 32 x 1x 2 x 3 ≥ 9 x j ≥0 （j ＝1,2,3） 7.3 利用动态规划方法证明平均值不等式： n n n x x x n x x x 12121)()( ≥+++ 设x i ≥0，i ＝1，2，…，n 。 7.4 考虑一个有m 个产地和n 个销地的运输问题。设a i （i ＝1，2，…，m ）为产地i 可发运的物资数，b j （j ＝1，2，…，n ）为销地j 所需要的物资数。又从产地i 到销地j 发运x ij 单位物资所需的费用为h ij （x ij ），试将此问题建立动态规划的模型。 7.5 某公司在今后三年的每一年的开头将资金投入A 或B 项工程，年末的回收及其概率如下表所示。每年至多做一项投资，每次只能投入1000万元。求出三年后所拥有的期望金额达到最大的投资方案。 投 资 回 收 概 率 A 0 0.4 2000 0.6 B 1000 0.9 2000 0.1 7.6 某公司有三个工厂，它们都可以考虑改造扩建。每个工厂都有若干种方案可供选择，各种方案的投资及所能取得的收益如下表所示(单位：千万元)。现公司有资金5千万元，问应如何分配投资使公司的总收益最大?

7.7 某厂准备连续3个月生产A种产品，每月初开始生产。A的生产成本费用为x2，其中x是A产品当月的生产数量。仓库存货成本费是每月每单位为1元。估计3个月的需求量分别为d1＝100，d2＝110，d3＝120。现设开始时第一个月月初存货s0＝0，第三个月的月末存货s3＝0。试问：每月的生产数量应是多少才使总的生产和存货费用为最小。 7.8 设有一辆载重卡车，现有4种货物均可用此车运输。已知这4种货物的重量、容积及价值关系如下表所示。 货物代号重量（吨）容积（立方米）价值（千元） 1 2 2 3 2 3 2 4 3 4 2 5 4 5 3 6 若该卡车的最大载重为15吨，最大允许装载容积为10立方米，在许可的条件下，每车装载每一种货物的件数不限。问应如何搭配这四种货物，才能使每车装载货物的价值最大。 7.9 某警卫部门有12支巡逻队负责4个仓库的巡逻。按规定对每个仓库可分别派2－4支队伍巡逻。由于所派队伍数量上的差别，各仓库一年内预期发生事故的次数如下表所示。试应用动态规划的方法确定派往各仓库的巡逻队数，使预期事故的总次数为最少。 巡逻队数预期事故次数仓库 1 2 3 4 2 18 38 14 34 3 16 36 12 31 4 12 30 11 25 7.10 （生产计划问题）根据合同，某厂明年每个季度末应向销售公司提供产品，有关信息见下表。若产品过多，季末有积压，则一个季度每积压一吨产品需支付存贮费0.2万元。现需找出明年的最优生产方案，使该厂能在完成合同的情况下使全年的生产费用最低。 季度j生产能力a j（吨）生产成本d j（万元/吨）需求量b j（吨） 1 30 15.6 20 2 40 14.0 25 3 25 15.3 30 4 10 14.8 15 （1）请建立此问题的线性规划模型。（提示：设第j季度工厂生产产品x j吨，第j季度初存贮的产品为y j吨，显然y1＝0）（2）请建立此问题的动态规划模型。（均不用求解） １９０

运筹学课件第三章运输问题

第三章运输问题 一、学习目的与要求 1、掌握表上作业法及其在产销平衡运输问题求解中的应用 2、掌握产销不平衡运输问题求解方法 二、课时 6学时 第一节 运输问题及其数学模型 一、运输问题的数学模型 单一品种运输问题的典型情况：设某种物品有m 个产地A 1,A 2,…,A m ，各产地的产量分别是a 1,a 2,…,a m ；有N 个销地B 1,B 2,…,B n ，各销地地销量分别为b 1,b 2,…,b n 。假定从产地A i (i =1,2, …,m )向销地B j (j =1,2,…,n )运输单位物品的运价是c ij ，问怎样调运这些物品才能使总运费最小？ 表中x ij i j ij i j 如果运输问题的总产量等于其总销量，即有 ∑∑===n j j m i i b a 1 1 则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。 产销平衡运输问题的数学模型如下：

???? ? ????≥=====∑∑∑∑===+=0,...,2,1,...,2,1..min 1 111 1 ij m i j ij n j i ij m i n j ij ij x n j b x m i a x t s x c z 这就是运输问题的数学模型，它包含m ×n 个变量，(n 十m)个约束方程．其系数矩阵的结构比较松散，且特殊。 二、运输问题数学模型的特点 1、运输问题有有限最优解，即必有最优基本可行解 2、运输问题约束条件的系数矩阵A 的秩为(m+n-1) 该系数矩陈中对应于变量x ij 的系数向量p ij ，其分量中除第i 个和第m 十j 个为1以外，其余的都为零．即 A ij ＝(0…1…1…0)’=e i +e m+j 对产销平衡的运输问题具有以下特点： (1)约束条件系数矩阵的元素等于0或1 (2)约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前m 个约束方程中出现一次，在后n 个约束方程中也出现一次。 此外，对于产销平衡问题，还有以下特点 (3)所有结构约束条件都是等式约束 (4)各产地产量之和等于各销地销量之和

运筹学模型在运输问题中的应用

《数值分析》课程设计非线性方程求根公式的集成与菜单调用 院（系）名称信息工程学院 专业班级12普本信计 学号1201110054 学生姓名孟浩 指导教师孔繁民 2015年6月16日

课程设计任务书 2014—2015学年第二学期 专业班级：12 普本信计学号：1201110054 姓名：孟浩 课程设计名称：运筹学 设计题目：运筹学模型在运输问题中的应用 完成期限：自2015年 5 月24 日至2015 年05 月30 日共 1 周一、设计目的 运筹帷幄之中，决胜千里之外。运筹学是多种学科的综合性学科，是最早形成的一门软科学。他把科学的方法、技术和工具应用到包括一个系统管理在内的各种问题上，以便为那些掌握系统的人们提供最佳的解决问题的办法。他用科学的方法研究与某一系统的最优管理有关问题。因此运筹学是一门有重要应用价值的学科，特别在现代科学管理中是处处离不开运筹学。为了更好的理解运筹学，我们运用运筹学知识建立数学模型来解决运输问题中的应用的问题。 二、设计要求 1、运用LINGO等工具。 2、运筹学模型在运输问题中的应用。 3、按照格式要求写出3000字文档。 三、参考文献 [1]谢金星薛毅，优化建模与LINDO/LINGO软件[M]，北京：清华大学出版社. [2]吴祈宗，运筹学[M] ，北京：机械工业出版社. [3]朱德通，最优化模型与实验/应用数学系列丛书[M] ，上海：同济大学出版社 [4]谷歌地图 https://www.doczj.com/doc/0f17628812.html,/maps?q=%E4%BB%CB%AE+%BB%AF%B7%CA&ie=gbk. 工作任务与工作量要求：查阅文献资料不少于3篇，课程设计报告1篇不少于3000字 指导教师（签字）：教研室主任（签字）： 批准日期：年月日

运筹学在运输问题中的应用

运筹学在运输问题中的应用 关键字：运筹学运输 引言：运输是土木工程中经常遇到的问题，在工程造价中占较大的比例。如何使运输费用达到最小化，这就需要在施工前优化施工组织设计，将运筹学、网络技术等理论的设计方法应用到施工中，使得成本费用最经济。下面我们借鉴运筹学中的理论来解决运输问题。 一、运输路线最短问题。 根据运筹学中最短路径算法，寻找最短路线，就是从最后一段开始，用由后向前逐步递推的方法求卅各点到终点的最短路线，最终求得南起点到终点的最短路线。 某工程需要从点Sl运送500吨的建筑材料一个工地S1O。 首先．将图l的路线问题看成四个阶段的问题．南S1到S2，S3，S4为第一阶段；南S2，S3，S4到S5，S6，S7为第二阶段；南S5，S6，S7到S8。S9为第i阶段；南S8，S9到SIO为第四阶段。下面引进几个符号：

D(Sk,Sm)为Sk到Sm的距离，f(Sk)Sk到终点的最短距离。 (1)在第四阶段。 目前状态可以是S8或S9，可选择的下一状态是S1O，所以有 (2)在第i阶段。 目前状态可以是S5或S6或S7，可以选择的下一状态为S8或S9．所以有 (3)在第二阶段。 目前状态可以是S2或S3或S4，可以选择的下一状态为S5或S6或S7，所以有 (4)在第一阶段。 目前状态只有S1，可以选择的下一状态为S2或S3或S4．所以有 通过最短路径算法计算。可知从Sl(出发点)到S1O(终点)的最短运输路程为1080千米(权数路径距离)，所走的最优路线采用“顺序追踪法”来确定，最优运输路径：S1一S3一S6—S8—S10。 二、自卸车排队问题

在工程中经常遇到材料的运输和施工之间的关系，例如铺路的碎石、沥青的运输和路面的铺设之间的关系。如果运输工作进行得太快，而施工进程跟不上，就会有太多的原料来不及施工，导致运输设备和人员的闲置。相反，如果运输进度赶不上施工，就会出现施工设备和人员的闲置。 下面以高速公路高速公路沥青路面机械化施工系统为例子进行说明。高速公路沥青路面机械化施工系统，是指以沥青混合料拌和站、自卸汽车、沥青混凝土摊铺机、初压压路机、复压压路机、终压压路机等6种主体机械组成的沥青路面铺筑机群施工系统。沥青混凝土混合料作为纽带，将这6种机械共同联系在一起。准确、协调地工作，形成在“拌和一运料一摊铺一初压一复压一终压”过程中机械间的“相互影响、相互联系、相互制约”规律，即沥青路面施工系统机群工作规律。” 要研究沥青路面施工系统机群工作规律，首先应研究、分析机群施工系统的概率规律性及机械排队数量的目的，为研究拌和站、自卸汽车、摊铺机、初压压路机、复压压路机、终压压路机的运行工作情况作准备，为该系统资源优化配置(即机械的性能与数量优化组合)提供理论依据。其中重点是研究机械排队队长分布和机械排队数量。 1、系统流程分析 系统理想的工作情况是：当沥青混合料拌和站刚拌合好l车料时，就有l辆汽车到达拌和站处并装料；当摊铺机需要进料时，就有1辆汽车到达摊铺机处并立即卸料；沥青混凝土经摊铺机摊铺后，压路机立即分别予以压实。 拌和子系统是指由拌和站与运料汽车形成的系统。汽车总数是有限的。如只有M辆汽车，每辆汽车来到系统中接受服务后仍回到原来的总体，还会再来。由于拌和站的空间比较大，运输汽车是有限的，不会出现有运输车不能进入的情况，所以问题可以归结为单服务台等待制模型M/M/1/∞。这类问题的主要特征是系统空问是无限的，允许永远排队。 设：M为运料汽车总数量；L为平均队长；λn为拌和站处汽车平均到达率；μn为拌和站服务率，即单位时间内装车数量；W为平均逗留时间；Wq为平均等待时间。则系统状态流图见图1。