《管理运筹学》课件05-运输模型

1、,第5章 运输模型,Transportation Model,TM,第5章 运输模型,2,5.1 运输问题及其数学模型 5.2 表上作业法 5.3 运输模型的应用,第5章 运输模型,第5章 运输模型,3,5.1 运输问题及其数学模型,问题的提出 运输问题：产地、销地、产量、销量 例1 有A1，A2，A3三座铁矿，每天要把生产 的铁矿石运往B1，B2，B3，B4四个炼铁厂。各矿的 产量、各厂的销量以及各厂矿间的运价如下表所示。 问应如何组织调运才能使运费最少？,第5章 运输模型,4,5.1 运输问题及其数学模型,(百元/百吨 ),xij Ai运给Bj的铁矿石数量（百吨）,z 总运费（百元）,第5

2、章 运输模型,5,5.1 运输问题及其数学模型,(百元/百吨 ),x11,x12,x13,x14,x21,x22,x23,x24,x31,x32,x33,x34,第5章 运输模型,6,5.1 运输问题及其数学模型,数学模型为: min z = 6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24 +3x31+2x32+9x33+7x34 x11+x12+x13+x14 = 5 x21+x22+x23+x24 = 2 x31+x32+x33+x34 = 3 x11 +x21 +x31 = 2 x12 +x22 +x32 = 3 x13 +x23 +x33 = 1 x14

3、 +x24 +x34 = 4 xij0 ( i =1, 2, 3; j =1, 2, 3, 4 ),s.t.,第5章 运输模型,7,5.1 运输问题及其数学模型,表式模型,产销平衡的运输问题: ai=bj 产大于销的运输问题: aibj 产小于销的运输问题: aibj,第5章 运输模型,8,5.1 运输问题及其数学模型,LP式 产销平衡模型,第5章 运输模型,9,LP式 产大于销模型,5.1 运输问题及其数学模型,第5章 运输模型,10,5.1 运输问题及其数学模型,LP式 产小于销模型,第5章 运输模型,11,5.1 运输问题及其数学模型,运输模型有两个特点： (1) 它有mn个变量，m+n

4、个约束方程 (2) 其系数阵具有特殊的结构,m=3行,n=4行,A =,1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1,第5章 运输模型,12,5.2 表上作业法,基本步骤 (1) 确定初始方案； (2) 进行最优性检验； (3) 调整、改进非最优方案。,第5章 运输模型,13,5.2 表上作业法,5.2.1 初始方案的确定 一、最小元素法 所谓最小元素，是指作业表中最小运价cij。即先给最小运价那格安排 运量，然后划去该运价所在行或列；直到求出初始方案为止。,1,4,3,0,0,2,2,2,2,2,第5章 运输模型,14,为了保证画圈数字为m+

5、n-1个，最小元素法有以下 三条原则: (1) 在确定了某一基变量 xlk及其数值并画圈以后， 若它所在的Al行或Bk列中其余变量均应取 0 值, 也不能 同时把Al行和Bk列都划去，而只能划去其中之一。 (2) 在确定为最小元素的某一空格上，若该变量 xij = min ai, bj = 0 此时也不能保留该空格，而必须把 0 填上并画圈。 (3) 最后一个空格必须画圈，即便该格的xij= 0也要 填上0并画圈。,5.2 表上作业法,第5章 运输模型,15,5.2 表上作业法,(1) 为了保证画圈个数为m +n-1个，每画1个圈, 只许划去1行/列，即，行列总数减少1； 因为行列总数为,m+

6、n；,(2) 再如，当只剩下最后1行/列时:,当画了m+n -2个圈时，未划去的行列总数为,2，,即只剩下1个空格，只能再画1个圈，这样，画圈个数 恰为m +n -1。,不仅划去1行，同时也划去了所有的列，不可！,第5章 运输模型,16,5.2 表上作业法,“最小元素法”和“最大差额法”所确定的 初始方案满足以下条件： (1) 画圈数字的个数恰好等于线性无关的约束 个数，即m+n-1个 。 (2) 可行：满足所有约束条件。 (3) 表中不存在“以画圈数字为顶点的闭回路”。,第5章 运输模型,17,5.2 表上作业法,画圈数字为顶点的闭回路,1,1,3,2,2,1,第5章 运输模型,18,5.2

7、 表上作业法,二、最大差额法 步骤如下： 1对每行每列的运价cij分别计算两最小元素之差(取正值) ，将 “行差” 记于表右侧， “列差” 记于表下端。 2在所有行差、列差中选一最大差额，若有几个同时最大，则可任选其中 之一。 3在最大差额所在行(列) 中选一最小运价，若有几个同时最小，则可 任选其一。,4在所确定的最小运价格内，确定基变量数值并画圈，然后划去其所在行 或列，具体做法同最小元素法。 5对剩余未划去的行列重复上述步骤，但当只剩下最后一行(列) 时，不再 计算行(列)差，而直接按最小元素法分配运量并划去相应的行或列。,第5章 运输模型,19,5.2 表上作业法,行 差,列 差,1,

8、1,1,3,1,6,1,6,3,1,4,2,1,1,2,1,2,1,5,5,2,1,2,2,2,1,2,2,2,2,第5章 运输模型,20,5.2 表上作业法,5.2.2 最优性检验 一、位势法 在初始方案表中, 可将基变量所在格的运价cij分解为两部分 ui + vj = cij 其中ui代表产地Ai所在行的行位势量，vj代表销地Bj所在列 的列位势量，cij为画圈数字所在格的运价。 所有ui，vj的值确定以后，可以证明，ij可按下式计算： ij = cij ui vj 基变量对应的检验数显然全都为0，因此，只需计算非基 变量的检验数。这种计算检验数的方法就是位势法。,第5章 运输模型,21

9、,5.2 表上作业法,ui,vj,0,6,2,5,-3,5,-1,-2,2,1,7,10,5,第5章 运输模型,22,5.2 表上作业法,二、闭回路法 闭回路是指以一个非基变量的格子为始点和终点，而其 余顶点均为画圈数字的一条封闭回路。,号的顶点称为偶点，而标 “”号的顶点称为奇点。 奇偶点的确定：,的某一行进方向交错地标记奇偶符号。 则,然后沿着闭回路,检验数等于闭回路上偶点的运价总和减去奇点的运价总和。,即,第5章 运输模型,23,5.2 表上作业法,1,2,1,2,2,2,-,-,-,+,+,4,2,3,7,8,3,补表 以最大差额法所确定方案及其闭回路为例,x21的闭回路。,21 =

10、7 -4 +5 -3 +2 -3,= 4,第5章 运输模型,24,5.2 表上作业法,5.2.3 非优方案的调整 在进基变量的闭回路上的所有奇点中, 选择数值最小的那个作为离基变量, 并且取它的值作为调整量。,-,-,+,第5章 运输模型,25,5.2 表上作业法,1,3,0,2,2,ui,vj,0,6,2,5,-3,5,-1,-2,2,1,7,10,5,-,-,+,2,调整之，,t=2,2,2,1,第5章 运输模型,26,5.2 表上作业法,1,2,2,0,4,2,5,-1,3,-1,2,4,3,7,8,3,为最优方案，,对所得新方案用位势法检验：,与最大差额法初始方案相同。,第5章 运输模

11、型,27,5.2 表上作业法,调整非优方案的一般步骤与规则 1进基变量的确定规则 按 min ijij 0 = lk 确定xlk进基。 若有多个lk同时最小，则选其中最小运价minclk 所对应的那个 xlk进基; 又若有多个这样的clk同时最小， 则从中任选一个clk对应xlk的 进基。,进而画出进基变量xlk的闭回路及奇偶点。,2离基变量的确定规则 在进基变量xlk的闭回路上，按,确定xpq离基，同时也就确定xpq的值t为调整量。 若有多个奇点 xpq 的值同时最小，则选其中最大运价 maxcpq 所对 应的那个xpq离基；又若有多个这样的cpq同时最大，则从中任选一个cpq 对应的xpq

12、离基。,第5章 运输模型,28,5.2 表上作业法,3非最优方案的调整规则,不在进基变量闭回路上的xij的值不变。,在进基变量的闭回路上：,第5章 运输模型,29,5.2 表上作业法,5.2.4 产销不平衡问题的解法,第5章 运输模型,30,5.2 表上作业法,第5章 运输模型,31,5.3 运输模型的应用,5.3.1 短缺资源的分配问题 例4 自来水分配问题,160,110,6 0,210,160,额 外,基 本,2 0,0,5 0,第5章 运输模型,32,5.3 运输模型的应用,D (虚),50,210,甲,甲1,甲2,需 求 量,30,20,乙,70,丙,30,丁,丁1,丁2,10,50

13、,160 140 190,160 140 190,M,0,130 130 200,M,220 190 230,0,170 150 M,M,170 150 M,0,自来水分配问题的规范表式运输模型,第5章 运输模型,33,5.3 运输模型的应用,第5章 运输模型,34,5.3 运输模型的应用,5.3.2 转运问题 例5 面粉转运问题 设有A1、A2、A3三个面粉加工厂，每天分别将 3、4、3吨面粉运往B1、B2两个糕点厂，而B1、B2每 天分别需要4、6吨面粉。在面粉厂与糕点厂之间有T1、 T2两个中继站。各地间每吨面粉的运价如下表所示。 应如何调运使总运费最低？,第5章 运输模型,35,5.3

14、 运输模型的应用,第5章 运输模型,36,5.3 运输模型的应用,1 转运站既是始点，又是终点的运地。 转化成为有7个假想产地Ai 、7个假想销地Bj的新问题。 2 虚设一个统一转运量t，应有 t max ( ai ， bj),假想产地Ai的产量,故可取作,t = 10,= 10,本例, ai = bj,第5章 运输模型,37,5.3 运输模型的应用,本例取作,ai = ai + 10 bj = bj+ 10,3 虚设 xii 也是运量，即假想各转运站可以自产自销，则其 真实运量为,假想销地Bj 的销量,t - xii 。,不可能运输（即表中标“-” ）之处：用大 M 取代； xii 的运价为

15、0；,本例中即10 - xii 。,4 新问题的运价：,其余不变。,第5章 运输模型,38,5.3 运输模型的应用,面粉转运问题的初始方案,3,3,4,4,6,1,1,1,1,1,10,10,10,10,10,10,10,10,10,80,ui,vj,-,+,-,第5章 运输模型,39,5.3 运输模型的应用,面粉转运问题的最优方案,第5章 运输模型,40,5.3 运输模型的应用,最优方案及最优路线,最少总运费为 z* = 33 +24 +31 +42 +24 +24 = 44(元),A1,B1,T1,A2,T2,A3,B2,3吨 4吨 3吨,4吨 6吨,3,4,1,2,4,4,第5章 运输模

16、型,41,5.3 运输模型的应用,5.3.3 生产调度问题 例6 拖拉机生产调度问题 前进拖拉机厂与农机供销社签订了一项生产100台某种 小型拖拉机的合同。按合同规定，该厂要在今后四个月的每 月内交付一定台数的拖拉机。为此，该厂生产计划科根据本 厂实际情况列出了一个生产调度表（见下表）。根据此表第 二栏（生产能力）的数据，该厂能够提前完成合同总台数， 但生产出来的拖拉机若当月不交货，每台存储一个月，由于 维修保养和积压资金等缘故，另需费用100元。问该厂应如何 拟订最经济的生产进度？,第5章 运输模型,42,5.3 运输模型的应用,第5章 运输模型,43,5.3 运输模型的应用,解 设 xij 为第 i 个月生产的、用于第 j 个月交货的拖拉机台数(i，j =1，2， 3，4 ) 。若将各产期视为“产地”，各销期视为 “销地”，将xij视为“运量”，就 能构成一个运输模型。cij 表示第i月生产的用于第j月交货的每台拖拉机的