管理运筹学--运输问题

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

1、管理运筹学,华国伟 Email:huaguowei 北京交通大学经管学院物流管理系,第三章 运输问题 Transportation Problem,本节内容提要,3.1 运输问题的数学模 3.2 表上作业法,3.1 运输问题的数学模型,A1,Ai,Am,产地,产量,销地,B1,Bj,Bn,销量,例：某运输问题的资料如下：,一、运输问题的数学模型,数学模型的一般形式 已知资料如下：,供需平衡,当产销平衡时，其模型如下：,Ai的产品全部供应出去,Bj的需求全部得到满足,产销平衡的运输问题必定存最优解.,当产大于销时，其模型是：,当产小于销时，其模型是：,m,n,平衡表、运价表和二为一：,约束条件或

2、解可用产销平衡表表示:,uivj无约束 （i=1,2, ,m;j=1,2, ,n),ui,vj,设ui,vj为对偶变量，对偶问题模型为,m个,n个,特征： 1、平衡运输问题必有可行解，也必有最优解； 2、运输问题的基本可行解中应包括 m+n1 个基变量。,.重复. ，直到找到最优解为止。,步骤：,.找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用西北角法、最小元素法；,.求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用位势法计算；,.改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；,二、表上作业法,确定m+n-1个基变量,空格,3.2

3、求解运输问题的算法:表上作业法,开 始,求各非基变 量的检验数,是否达到最优解,结束,确定换入变量 与换出变量,新的基可行解,求初始基可行解,N,Y,最小元素法， 伏格尔法,闭回路法， 位势法,闭回路调整法,例一、某运输资料如下表所示：,1、求初始方案：,3.2.1初始基可行解的确定西北角法,西北角发也就是从运价表的西北角位置开始,依次安排m个产地和n个销地之间的运输业务,从而得到一个初始调运方案的方法. 西北角法应遵循“优先安排运价表上编号最小的产地和销地之间(即运价表的西北角位置)的运输业务”的规则.,.西北角法(或左上角法): 此法是纯粹的人为的规定,没有理论依据和实际背景,但它易操作,

4、特别适合在计算机上编程计算,因而受欢迎.方法如下：,总的运费(33)(411)(29)(22)(310)(65)135元,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,.初始基可行解的确定-最小元素法： 基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。,总的运输费用（31）（64） （43）（12）（310）（35）86元,分别计算各行、各列次小、最小运价的差值,优先在最大差值处进行供需搭配. 差值=次小-最小,步骤：,10 计算未划去行、列的差额;,20 找出最大差额对应的最小元素cij进行供需分配;,30 在未被划去的行、

5、列重新计算差额.,(3)初始基可行解的确定 -最大差值法(伏格尔法) Vogel,6,行差值,0,1,1,6,3,3,6,3,5,1,2,6,3,以上方法得到的初始解为基可行解 每次行(需求)或列(供应)达到饱和 每次必划掉一行或一列 得到的元素个数必为m+n-1个 西北角法 最小元素法 最大差值法,练习,P97 3.1 3.2,ij0 （因为目标函数要求最小化） 表格中有调运量的地方为基变量,空格处为非基变 量.基变量的检验数ij0,非基变量的检验数 ij0. ij 0 表示运费增加.,2、最优解的判别（检验数的求法）：,非基变量增加一个单位目标值的变化,闭回路：从空格出发顺时针(或逆时针)

6、画水平(或垂直)直线,遇到填有运量的方格可转90,然后继续前进,直到到达出发的空格所形成的闭合回路.,调运方案的任意空格存在唯一闭回路.,差值法方案,一、最优调运方案的判定,最小元素法方案,+,-,+,-,x11为换入变量，x11：01，运费的变化为3-1+2-3=1。这个变化就是x11的检验数，故 11=1,3,1,3,6,3,1,2,4,3,1,3,6,3,1,2,-1,4,3,1,3,6,3,1,2,1,-1,4,3,1,3,6,3,1,2,1,-1,12,4,3,1,3,6,3,1,2,1,-1,12,10,4,检验数中有负数，说明原方案不是最优解。,检验数还存在负数, 原方案不是最优

7、方案.,用闭回路求解检验数时,需要给每一个空格找一条闭回路.当产销点较多时,该方法较麻烦.,ui,vj自由变量,（2） 位势法 标准型运输问题的对偶问题是：,检验数,对偶变量值等于原问题的检验数,松弛变量,基变量的检验数为零(基变量xij)，,得m+n-1个方程,含m+n个未知数, 令某个ui ( 或vj)=0,可解出m+n个ui 和vj;由此得非基变量的检验数.,1.由基变量的检验数为0, ij=cij-(ui+vj)=0, u1=0 (v1=0),得ui, vj 2. 利用ij=cij-(ui+vj),求非基变量的检验数 可令任意的行或列的位势为0 (任意值均可,为0出于计算简单考虑),位

8、势法,令v1=0, 由c21=1= u2 +v1，得 u2=1,0,1,1,2,0,1,1,2,8,-3,7,位势表,2,9,8,9,-3,-2,检验数,0,1,1,2,8,-3,7,检验数表,1,2,1,-1,10,12,24=-10，当前方案 不是最优方案。,1. 以最小负检验数为出发点寻找一条闭回路. 2. 确定调整量,调出格中最小的运量.,2.3 改进的方法闭回路调整法,从(p,q)空格开始画闭回路,其它转角点都是填有运量的方格,并从(p,q)空格开始给闭回路上的点按+1,-1,+1,-1编号，-1格的最小运量为调整量.,换出变量,运价,新的调运方案为：,或者直接算,7,1,3,4,9

9、,11,10,2,3,10,8,5,运输问题的求解表上作业法步骤小结,第一步:确定初始基可行解（可行调运方案） 方法：最小元素法与伏格尔法 第二步:判别当前可行方案是否最优 方法：闭回路法与位势法 第三步:对现有方案进行调整 方法：闭回路法,3.2.4 表上作业法计算中的问题,无穷多最优解 某非基变量(空格)的检验数为0. 退化 方案点数=产地数+销地数1; 同时去掉一行和一列时应添加0方案; 调整时出现两个或两个以上的最小值,新方案中也要添加0方案.,.无穷多最优解：产销平衡的运输问题必定存最优解.如果非基变量的ij0, 则该问题有无穷多最优解. 如上例: (1.1) 中的检验数是 0, 经

10、过调整, 可得到另一个最优解.,4、表上作业法计算中的问题,.退化: 表格中一般要有(m+n-1)个数字格.但有时, 在分配运量时则需要同时划去一行和一列, 这时需要补一个0, 以保证有(m+n-1)个数字格. 一般可在划去的行和列的任意空格处加一个 0 即可.,正常时一次只划掉同时划掉了一行和一列 此时同时划掉一行和一列, 不要补零,例1：,2 1 3 5 5 2 6 8 2 1 7 6,例2：,0,0,0,4 运输问题的扩展,本 节 重 点,供需不平衡的运输问题,转运问题,运输问题的分类,产销平衡问题：ai=bj 产销不平衡问题：,产大于销：ai bj,产小于销：ai bj,供需不平衡-虚

11、设产地、销地,产大于销时 增加一个虚拟的销售点,其销量为产销的差额,各产地到该销地的单位运价为0. 销大于产时 增加一个虚拟的产地,其产量为产销的差额,该产地到各销地的单位运价为0.,1. 产大于销 ：,模型：,运输表：,实际意义： 虚设一个销地,运价为零,2. 产小于销 ：,模型：,运输表：,实际意义： 虚设一 个 产地,运价为零,一、供需不平衡的运输问题,1、供不应求的运输问题,虚设一个供应地，其虚供应量为供不应求部分。,虚设一个供应地A3，其供应量=130-110=20,0 0 0,用最小元素法或差值法求初始方案。,例. 甲、乙、丙三个城市今年冬季分别需要煤炭320、250、350万吨,

12、 由A、B两处煤矿负责供应.已知煤炭年供应量为A400万吨,B450万吨.由各煤矿至各城市的单位运价(万元/万吨)如下.,由于需大于供,经研究决定,甲城市供应量可减少030万吨,乙城市需要量应全部满足,丙城市供应量不少于270万吨,试求将供应量分配完又使总运费最低的调运方案.,拆分需求刚需与弹性需求,甲：供应量可减少030万吨，乙城市全部满足，丙城市供应量不少于270万吨。,甲：供应量可减少030万吨，乙城市全部满足，丙城市供应量不少于270万吨。,15 21,22 16,M,M,M,0,0,最高需求产量,二、转运问题,出现下列问题： 产地与销地之间没有直达路线，货物由产地到销地必须通过中转站

13、转运； 某些产地可以输入货物，销地也可以输出货物， 产地与销地之间虽然有直达运输线，但直达运输的费用（距离）比经过某些中转站的还要高。,解法：,根据问题求出最大可能周转量Q；,3. 兼中转站的产地Ai=,4. 兼中转站的销地Bj=,列出各产地的输出量和各销地的输入量及各产销地之间的运价表, 用表上作业法求解.,输出：产地；中转站(纯/兼) 输入：销地；中转站(纯/兼),例 某货物, 其产地A1的产量为10单位,A2的产量为2单位, 销地A3、A4、A5的销量分别为3单位、1单位和8单位, 其中产地A2、销A4又可作为中转站. 同时, 货物可通过纯中转站A6进行运输. 各产地、销地及中转站之间的

14、单位物资运价如表所示, 试求一个使总运费最省的调运方案.,最大可能周转量 Q=a1+a2=10+2=12,A1 纯产地, 输出量10; A2产地兼中转站,输出量2+12=14,输入量12; A3 纯销地, 输入量3; A4销地兼中转站,输出量12,输入量1+12=13; A5纯销地,输入量8; A6纯中转站,输出量、输入量均为12. 根据以上情况列产销平衡表.,不参加实际调运,3.4 应用举例,搞清“产地、销地”、“运价”, “产量、需求”, 写出产销平衡表,运输问题的要素:,未知数如何设,虚设产地与销地; 拆分产地与销地,例 3. 某厂按合同规定须于每个季度末分别提供10,15,25,20台

15、同一规格的柴油机.已知该厂各季度的生产能力及生产每台柴油机的成本如下表.如果生产出来的柴油机当季不交货,每台积压一个季度需储存、维护费用0.15万元.要求在完成合同的情况下,做出该厂全年费用最小的决策.,搞清“产地、销地”、“运价”, “产量、需求”, 写出产销平衡表,未知数如何设,设xij为第i季度生产的用于第j季度交货的柴油机数.,合同要求：,产量约束：,第i季度生产的用于第j季度交货的柴油机的实际成本 cij=生产成本+储存维护费用,目标函数：,例: 某玩具公司分别生产三种新型的玩具, 每月可供应量分别为1000件, 2000件,2000件，他们分别被送到甲乙丙三个百货商店销售, 已知每月百货商店各类玩具预期销售量为1500件, 由于经营原因, 各百货商店销售不同玩具的盈利额不同, 又知丙百货商店要求至少供应C玩具1000件, 而拒绝进入A种玩具, 求满足上述条件下使总盈利额为最大的供销分配方案.,C先满足丙1000件,已知某运输问题的产销平衡表, 最优调运方案及单位运价表分别