运筹学_第3章_运输问题习题

第三章运输问题

3.1农产品经销公司有三个棉花收购站，向三个纺织厂供应棉花。三个收购站A1、A2、A3的供应量分别为50kt、45kt和65kt，三个纺织厂B1、B2、B3的需求量分别为20kt、70kt和70kt。已知各收购站到各纺织厂的单位运价如表3—1所示（单位：千元/kt），问如何安排运输方案，使得经销公司的总运费最少？（只建模型，不求解）

设x ij表示从A i运往B j的棉花数量，则其运输量表如下表所示。

表3—2

min f= 4x11+8x12+5x13+6x21+3x22+6x23+2x31+5x32+7x33

x11+x12+x13 = 50

x21+x22+x23 = 45

x31+x32+x33 = 65

x11+x21+x31 = 20

x12+x22+x32 = 70

x13+x23+x33 = 70

x ij≥0，i=1，2，3；j=1，2，3

例3.2设有某物资从A1，A2，A3处运往B1，B2，B3，B4四个地方，各处供应量、需求量及单位运价见下表。问应如何安排运输方案，才能使总运费最少？

解：先用最小元素法求解。

用位势法对基可行解进行最优性检验。

位势方程组为

u1+v1=3 u1+v3=6 u1+v4=4

u2+v1=2

u3+v2=3

u3+v3=8

取u1=0，解上述方程组得

u1=0

u2=－1

u3=2

v1=3

v2=1

v3=6

v4=4

各非基变量的检验数为

σ12 =c12－（u1+v2）=7－（0+1）= 4>0

σ22 =c22－（u2+v2）=4－（－1+1）= 2>0

σ23 =c23－（u2+v3）=3－（－1+6）= －2<0

σ24 =c24－（u2+v4）=3－（－1+4）= 0

σ31 =c31－（u3+v1）=8－（2+3）= 3>0

σ34 =c34－（u3+v4）=9－（2+4）= 3>0

由于σ23 =－2<0，故表中基可行解不是最优解。

由于σ

该闭回路上，偶数顶点上的基变量最小值为5，以该调整量进行调整得到如表3—11的新的基可行解。

新基可行解的位势方程组为

u1+v1=3 u1+v4=4 u2+v1=2

u2+v3=3

u3+v2=3

u3+v3=8

取u1=0，解上述方程组得

u1=0 u2=－1 u3=4 v1=3 v2=－1 v3=4 v4=4

各非基变量的检验数为

σ12 =7－（0－1）= 8>0 σ13 =6－（0+4）= 2>0

σ22 =4－（－1－1）= 6>0 σ24 =3－（－1+4）= 0 σ31 =8－（4+3）= 1>0 σ34 =9－（4+4）= 1>0

由于所有非基变量的检验数均大等于零，故从表3—11中得到最优解为

x11=25，x14=25，x21=15，x23=5，x32=20，x33=10，其它x ij=0

最优目标值为

f*=3×25+4×25+2×15+3×5+3×20+8×10=360

此外，由于σ24 = 0，故此问题有另一最优基可行解。具体求法是在表3—11中，以x24为进基变量作闭回路，进行调整后得到。

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

第七章运输问题 一个农民承包了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

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

第七章运输问题 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吨。由于工艺、技术的差别，各分厂运往各销售地区的单位运价（万元/吨）、各厂单位产品成本（万元/吨）和各销地的销售价格（万元/吨）如下表：

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

第三章运输问题 一、学习目的与要求 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.wendangku.net/doc/b73924686.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。