运筹学与运输问题

《运筹学与运输问题》由会员分享，可在线阅读，更多相关《运筹学与运输问题（37页珍藏版）》请在金锄头文库上搜索。

1、运输规划 ( Transportation Problem )1.运输规划问题的数学模型2.表上作业法3.运输问题的应用 本章主要内容：本章主要内容：1.运输规划问题的数学模型例3.1 某公司从两个产地A1、A2将物品运往三个销地B1, B2, B3，各产地的产量、各销地的销量和各产地运往各销地每件 物品的运费如下表所示，问：应如何调运可使总运输费用最 小？B1B2B3产量 A1646200 A2655300 销量150150200解：产销平衡问题：总产量 = 总销量500设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输 量表：B1B2B3产量 A1x11x12x13200 A2x2

2、1x22x23300 销量150150200Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200x21 + x22+ x23 = 300x11 + x21 = 150x12 + x22 = 150x13 + x23 = 200xij 0 ( i = 1、2；j = 1、2、3） 运输问题的一般形式：产销平衡A1、 A2、 Am 表示某物资的m个产地； B1、B2、Bn 表示某物质的n个销地；ai 表示产地Ai的产量； bj 表示销地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价。设 xij

3、为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：变化：1）有时目标函数求最大。如求利润最大或营业额最大等；2）当某些运输线路上的能力有限制时，在模型中直接加入 约束条件（等式或不等式约束)；3）产销不平衡时，可加入假想的产地（销大于产时）或销 地（产大于销时）。 定理: 设有m个产地n个销地且产销平衡的 运输问题，则基变量数为m+n-1。2.表上作业法表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。步骤描述方法第一步求初始基行可行解（初始调运方案）西北角法、 最小元素法、 元素差额法第二步求检验 数并判断是否得到最优解当非基变 量的检验 数ij全都非负时 得到最优解，

4、若 存在检验 数ij 0，说明还没有达到最优， 转第三步。闭回路法、 位势法 运价矩阵法第三步调整运量，即换基，选一个变量出基，对 原运量进行调整得到新的基可行解，转入 第二步闭回路调整 法例3.2 某运输资料如下表所示：单位 销地运价 产地产量3113107 19284 741059 销量3656问：应如何调运可使总运输费用最小？解：第1步 求初始方案，见下表所示。最小元素法基本思想是就近供应，即从运价最小的地方开始供应（调运 ），然后次小，直到最后供完为止。B1B2B3B4产量A17A2 4A39销量3656311310192741058341633总的运输费(31)+(64) +(43)

5、 +(12)+(310)+(35)=86元第第2 2步步 最优解的判别（检验数的求法）最优解的判别（检验数的求法）求出一组基可行解后，判断是否为最优解，仍然是用检 验数来判断，记xij的检验数为ij由第一章知，求最小值的运 输问题的最优判别准则是：所有非基变量的检验数都大于等于，则运输方案 最优求检验数的方法有三种：闭回路法位势法（）运价矩阵法运价矩阵法当存在非基变量的检验数kl 0 且kl =minij时， 令Xkl 进基。从表中知可选x24进基。第3步 确定换入基的变量第4步 确定换出基的变量以进基变量xik为起点的闭回路中，所有偶顶点中的最小 运量作为调整量，对应的基变量为出基变量。闭回

6、路的概念为一个闭回路 ，集合中的变量称为回路的顶点，相邻两个变 量的连线为闭回路的边。如下表例下表中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35, x31共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。 B1B2B3B4B5 A1X11X12 A2X23X25 A3X31X35 A4X42X43一条回路中的顶点数一定是偶数，回路遇到顶点必须转90 度与另一顶点连接，上表中的变量x 32及x33不是闭回路的顶点 ，只是连线的交点。 闭回路B1B2B3A1X11X12 A2A3X32X33 A4X41X43例如变量组 不能构成一条闭回路， 但A中

7、包含有闭回路 变量组 变量数是奇数，显然不是 闭回路，也不含有闭回路； B1B2B3B4UiA1A2A3Vj3113 31010192 27410105 58 84 4363 31 13 3( () )( () )( () )( () )调整步骤为：在进基变量的闭回路中所有奇顶点对应的变量加上 调整量，所有偶顶点对应的变量减去调整量，其余变量不变 ，得到一组新的基可行解。1 12 25 5过x24的闭回路为：x24，x14,x13,x23因为所有非基变量的检验数均非负，故当前调运方案即 为最优方案，如表此时最小总运费：Z =(13)(46)(35)(210)(18)(35)85元表上作业法的计

8、算步骤：分析实际问题列出产销平 衡表及单位运价表确定初始调运方案（最小 元素法或Vogel法）求检验数（位势法）所有检验数0找出绝对值最大的负检验数，用闭合 回路调整，得到新的调运方案得到最优方案， 算出总运价表上作业法计算中的问题：表上作业法计算中的问题：（1）若运输问题的某一基可行解有多个非基变量的检验数为 负，在继续迭代时，取它们中任一变量为换入变量均可使目标 函数值得到改善，但通常取ij0中最小者对应的变量为换入变 量。（2）无穷多最优解产销平衡的运输问题必定存最优解。如果非基变量的ij0，则该问题有无穷多最优解。 退化解： 表格中一般要有(m+n-1)个数字格。但有时在分配运量 时则

9、需要同时划去一行和一列，这时需要补一个0，以保证有 (m+n-1)个数字格作为基变量。一般可在划去的行和列的任意 空格处加一个0即可。 利用进基变量的闭回路对解进行调整时，所有偶顶点 中的最小运量（超过2个最小值）作为调整量，选择任意一 个最小运量对应的基变量作为出基变量，并打上“”以示作为 非基变量，另一个变量仍为基变量且它的值为0。3.运输问题的应用 求极大值问题求极大值问题目标函数求利润最大或营业额最大等问题。目标函数求利润最大或营业额最大等问题。求解方法：将极大化问题转化为极小化问题。设极大化问题的运价表为C ，用一 个较大的数M（Mmaxcij）去减每一个cij得到矩阵C，其中C=（

10、M cij）0,将C作为极小化问题的运价表，用表上用业法求出最优解。例3.3 下列矩阵C是Ai（I=1，2，3）到Bj的吨公里利润,运输 部门如何安排运输方案使总利润最大.销地 产地B1B2B3产量A12 25 58 89 9A29 910107 71010 A36 65 54 41212 销量8 814149 9销地 产地B1B2B3产量A12 25 58 89 9A29 910107 71010 A36 65 54 41212 销量8 814149 9得到新的最小化运输问题，用表上作业法求解即可。 产销不平衡的运输问题产销不平衡的运输问题当总产量与总销量不相等时,称为不平衡运输问题.这类

11、运输问题在实际中常常碰到,它的求解方法是将不平衡问题化 为平衡问题再按平衡问题求解。当产大于销时，即：数学模型为：由于总产量大于总销量，必有部分产地的产量不能全部运送 完，必须就地库存，即每个产地设一个仓库，假设该仓库为 一个虚拟销地Bn+1， bn+1作为一个虚设销地Bn+1的销量(即库 存量)。各产地Ai到Bn+1的运价为零，即Ci,n+1=0,（i=1， m）。则平衡问题的数学模型为：具体求解时,只在 运价表右端增加 一列Bn+1，运价 为0,销量为bn+1 即可 当销大于产时，即：数学模型为：由于总销量大于总产 量,故一定有些需求地 不完全满足,这时虚设一个产地Am+1，运价 为0，产

12、量为：销大于产化为平衡问题的数学模型为 ：具体计算时，在运价表的下方增加一行Am+1，运价为0。产量 为am+1即可。 例3.4 求下列表中极小化运输问题的最优解。 B1B2B3B4ai A1592360 A2-47840 A3364230 A448101150bj20603545180 160因为有：所以是一个产大于销的运输问题。表中A2不可达B1，用一个 很大的正数M表示运价C21。虚设一个销量为b5=180-160=20 ，Ci5=0，i=1,2,3,4，表的右边增添一列 ，得到新的运价表。B1B2B3B4B5ai A15923060 A2M478040 A33642030 A44810

13、11050 bj2060354520180下表为计算结果。可看出：产地A4还有20个单位没有运出。B1B2B3B4B5Ai A1352560 A24040 A3102030 A420102050 Bj20603545201803. 生产与储存问题例3.5 某厂按合同规定须于当年每个季度末分别提供10、15、25 、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每 台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每 台每积压一个季度需储存、维护等费用0.15万元。试求在完成合 同的情况下，使该厂全年生产总费用为最小的决策方案。季度生产能力/台单位成本/万 元 2510.8 3511

14、.1 3011 1011.3解： 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那 么应满足： 交货： x11 = 10 x12 + x22= 15x13 + x23 + x33= 25x14 + x24 + x34 + x44 = 20生产：x11 + x12 + x13 + x14 25x22 + x23 + x24 35x33 + x34 30x44 10把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；设cij是第i季度 生产的第j季度交货的每台柴油机的实际成本，应该等于该季度单 位成本加上储存、维护等费用

15、。可构造下列产销平衡问题：j i产量10.810.9511.111.2525 M11.1011.2511.4035 MM11.0011.1530 MMM11.3010 销量10152520 100 70 由于产大于销，加上一个虚拟的销地D，化为平衡问题， 即可应用表上作业法求解。该问题的数学模型：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 j iD产量10.810.9511.111.25025 M11.1011.2511.40035 MM11.0011.15030 MMM11.30010 销量1015252030 100 100j iD产量1015025 053035 25530 1010 销量1015252030100 100最优生产决策如下表，最小费用z773万元。4.转运问题 例3.6 某公司有A1、 A2、 A3三个分厂生产某种物资，分别供应B1 、 B2、 B3、 B4四个地区的销售公司销售。假设质量相同，有关 数据如下表：试求总费用为最少的调运方案。 假设：1.每个分厂的物资不一定直接发运到销地，可以从其中几个产 地集中一起运；2.运往各销地的物资可以先运给其中几