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

1、管理运筹学课件05-运输模型5.1 运输问题及其数学模型运输问题及其数学模型5.2 表上作业法表上作业法5.3 运输模型的应用运输模型的应用第第5章章 运输模型运输模型5.1 运输问题及其数学模型运输问题及其数学模型问题的提出问题的提出 运输问题：产地、销地、产量、销量运输问题：产地、销地、产量、销量 例例1 有有A1，A2，A3三座铁矿，每天要把生产三座铁矿，每天要把生产的铁矿石运往的铁矿石运往B1，B2，B3，B4四个炼铁厂。各矿的四个炼铁厂。各矿的产量、各厂的销量以及各厂矿间的运价如下表所示。产量、各厂的销量以及各厂矿间的运价如下表所示。问应如何组织调运才能使运费最少？问应如何组织调运才

2、能使运费最少？5.1 运输问题及其数学模型运输问题及其数学模型B1 B2 B3 B4产量产量A1A2A36 3 2 57 5 8 43 2 9 7523销量销量2 3 1 4(百元百元/百吨百吨)xij Ai运给运给Bj的铁矿石数量（百吨）的铁矿石数量（百吨）z 总运费（百元）总运费（百元）5.1 运输问题及其数学模型运输问题及其数学模型B1B2B3B4产量产量A163255A275842A332973销量销量2314(百元百元/百吨百吨)x11x12x13x14x21x22x23x24x31x32x33x345.1 运输问题及其数学模型运输问题及其数学模型 数学模型为数学模型为:min z=

3、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 +x24 +x34=4 xij0 (i=1,2,3;j=1,2,3,4)s.t.5.1 运输问题及其数学模型运输问题及其数学模型表式表式模型模型 产销平衡产销平衡的运输问题的运输问题:aai i=bbj j 产大于销产大于销的运输问题的运输问题:aai i

4、bbj j 产小于销产小于销的运输问题的运输问题:aai ibbj jB1B2Bn 产量产量 A1c11 x11c12 x12c1n x1n a1A2c21 x21c22 x22c2n x2na2Amcm1 xm1 cm2 xm2 cmn xmnam销量销量b1b2bn aib bj5.1 运输问题及其数学模型运输问题及其数学模型xij 0 xij=ai i=1,2,，mj=1n xij=bj j=1,2,，ni=1ns.t.min z=i=1nj=1n cij xijLP式式 产销平衡产销平衡模型模型 LP式式 产大于销产大于销模型模型5.1 运输问题及其数学模型运输问题及其数学模型xij

5、0 xij ai i=1,2,，mj=1n xij =bj j=1,2,，ni=1ns.t.min z=i=1nj=1n cij xij5.1 运输问题及其数学模型运输问题及其数学模型xij 0 xij =ai i=1,2,，mj=1n xij bj j=1,2,，ni=1ns.t.min z=i=1nj=1n cij xijLP式式 产小于销产小于销模型模型5.1 运输问题及其数学模型运输问题及其数学模型 运输模型有两个特点：运输模型有两个特点：(1)它有它有mn个变量，个变量，m+n个约束方程个约束方程 (2)其系数阵具有特殊的结构其系数阵具有特殊的结构 m=3行行n=4行行A=1 1 1

6、 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5.2 表上作业法表上作业法 (1)确定初始方案确定初始方案；(2)进行最优性检验进行最优性检验；(3)调整、改进非最优方案调整、改进非最优方案。5.2 表上作业法表上作业法 5.2.1 初始方案的确定初始方案的确定 一一最小元素法最小元素法 所谓所谓最小元素最小元素，是指作业表中，是指作业表中最小运价最小运价cij。即先给最小运价那格安排。即先给最小运价那格安排运量，然后划去该运价所在行或列；直到求出初始方案为止。运量，然后划去该运价所在行或列；直到求出初始方案为止。1430022222B1B2B3B4产量

7、产量A163255A275842A332973销量销量2314 为了保证为了保证画圈数字为画圈数字为m+n-1个个，最小元素法有以下，最小元素法有以下三条原则三条原则:(1)在确定了某一基变量在确定了某一基变量 xlk及其数值并画圈以后，及其数值并画圈以后，若它所在的若它所在的Al行或行或Bk列中其余变量均应取列中其余变量均应取 0 值值,也也不能不能同时把同时把Al行和行和Bk列都划去列都划去，而只能划去其中之一。，而只能划去其中之一。(2)在确定为在确定为最小元素的最小元素的某一某一空格空格上，若该变量上，若该变量 xij=min ai,bj =0此时此时也不能保留该空格也不能保留该空格，

8、而必须把，而必须把 0 填上并画圈。填上并画圈。(3)最后一个空格必须画圈最后一个空格必须画圈，即便该格的，即便该格的xij=0也要也要填上填上0并画圈。并画圈。5.2 表上作业法表上作业法5.2 表上作业法表上作业法 (1)为了保证为了保证画圈个数为画圈个数为m+n-1个个，每画每画1 1个圈个圈,只许划去只许划去1 1行行/列，即，行列总数减少列，即，行列总数减少1 1；因为行列总数为因为行列总数为 m+n；(2)再如，当只剩下最后再如，当只剩下最后 行行/列时列时:当画了当画了m+n-2个个圈时，未划去的行列总数为圈时，未划去的行列总数为，即只剩下即只剩下1个空格，只能再画个空格，只能再

9、画1个圈，这样，个圈，这样，画圈个数画圈个数恰为恰为m+n-1。222不仅划去不仅划去1行行，同时也划，同时也划去了所有的列，去了所有的列，不可！不可！5.2 表上作业法表上作业法 “最小元素法最小元素法”和和“最大差额法最大差额法”所确定的所确定的满足以下条件：满足以下条件：(1)画圈数字的个数恰好等于线性无关的约束画圈数字的个数恰好等于线性无关的约束 个数，即个数，即m+n-1个个。(2)：满足所有约束条件。：满足所有约束条件。(3)表中不存在表中不存在“以画圈数字为顶点的闭回路以画圈数字为顶点的闭回路”。5.2 表上作业法表上作业法画圈数字为顶点的闭回路画圈数字为顶点的闭回路B1B2B3

10、B4产量产量A163255A275842A332973销量销量23141132215.2 表上作业法表上作业法二、最大差额法二、最大差额法 步骤步骤如下：如下：1对每行每列的运价对每行每列的运价cij分别计算分别计算两最小元素之差两最小元素之差(取正值取正值)，将，将“行差行差”记于表右侧，记于表右侧，“列差列差”记于表下端。记于表下端。2在所有行差、列差中选一在所有行差、列差中选一最大差额最大差额，若有几个同时最大，则可任选其中，若有几个同时最大，则可任选其中 之一。之一。3在最大差额所在行在最大差额所在行(列列)中选一中选一最小运价最小运价，若有几个同时最小，则可，若有几个同时最小，则可

11、任选其一。任选其一。4在所确定的最小运价格内，确定基变量数值并画圈，然后划去其所在行在所确定的最小运价格内，确定基变量数值并画圈，然后划去其所在行 或列，具体做法同最小元素法。或列，具体做法同最小元素法。5对剩余未划去的行列重复上述步骤，但当对剩余未划去的行列重复上述步骤，但当只剩下最后一行只剩下最后一行(列列)时，时，不再不再 计算行计算行(列列)差，而差，而直接按最小元素法直接按最小元素法分配运量并划去相应的行或列。分配运量并划去相应的行或列。5.2 表上作业法表上作业法B1B2B3B4产量产量A163255A275842A332973销量销量2314行行 差差列列差差1 11 11 13

12、 31 16 61 16314 42 21 11 121 12 21 15 55212 22 221 12 222 225.2 表上作业法表上作业法 5.2.2 最优性检验最优性检验 在初始方案表中在初始方案表中,可将基变量所在格的运价可将基变量所在格的运价cij分解为两部分分解为两部分 ui+=cij 其中其中ui代表产地代表产地Ai所在行的所在行的行位势量行位势量，代表销地代表销地Bj所在列所在列的的列位势量列位势量，cij为为画圈数字画圈数字所在格的所在格的运价运价。所有所有ui，vj的值确定以后，可以证明，的值确定以后，可以证明，ij可按下式计算：可按下式计算：ij=cij ui 基变

13、量对应的检验数显然全都为基变量对应的检验数显然全都为0，因此，只需计算非基，因此，只需计算非基变量的检验数。这种计算检验数的方法就是变量的检验数。这种计算检验数的方法就是。5.2 表上作业法表上作业法 B1 B2 B3 B4 产产量量 A1 6 3 2 5 5 A2 7 5 8 4 2 A3 3 2 9 7 3 销销量量 2 3 1 4 130222ui0-3-1-22171055.2 表上作业法表上作业法 二、闭回路法二、闭回路法 是指以一个非基变量的格子为始点和终点，而其是指以一个非基变量的格子为始点和终点，而其 余顶点均为画圈数字的一条封闭回路。余顶点均为画圈数字的一条封闭回路。符号符号

14、 +表示始点（非基变量），它及其闭表示始点（非基变量），它及其闭回路上标回路上标“+”号的顶点称为号的顶点称为偶点偶点，而标，而标“”号的顶点称为号的顶点称为奇点奇点。：的某一行进方向交错地标记奇偶符号。的某一行进方向交错地标记奇偶符号。则则 标标 号，号，（非基变量）必为（非基变量）必为偶点偶点，+=cij cij+-然后沿着闭回路然后沿着闭回路等于等于上上偶点偶点的的减去减去奇点奇点的的。即即5.2 表上作业法表上作业法B1B2B3B4产量产量A163255A275842A332973销量销量2314121222+-+补表补表 以以最大差额法最大差额法所确定所确定及其及其为例为例。=7-4

15、+5-3+2-3=5.2 表上作业法表上作业法 5.2.3 非优方案的调整非优方案的调整 在在进基变量的闭回路上的所有上的所有奇点中中,选择数值最小的那个作为离基变量选择数值最小的那个作为离基变量,并且取它的值作为并且取它的值作为调整量。B1 B2 B3 B4 产产量量 A1 6 3 2 5 5 A2 7 5 8 4 2 A3 3 2 9 7 3 销销量量 2 3 1 4 130222ui0-3-1-2 217105+-+5.2 表上作业法表上作业法 B1 B2 B3 B4 产产量量 A1 6 3 2 5 5 A2 7 5 8 4 2 A3 3 2 9 7 3 销销量量 2 3 1 4 130

16、22ui0-3-1-2217105+-+2调整之，调整之，2215.2 表上作业法表上作业法122122ui0-1-1243783为为最优方案最优方案，对所得新方案用对所得新方案用位势法位势法检验：检验：与与最大差额法最大差额法初始方案相同。初始方案相同。5.2 表上作业法表上作业法调整非优方案的一般步骤与规则调整非优方案的一般步骤与规则 1 1进基变量的确定进基变量的确定规则规则 按按 min ijij i5.3 运输模型的应用运输模型的应用 130 30 25352515 bj20 0MMM 45 0 52MM 35 0 5453M 30 0 535251 ai虚虚 销期销期j j 产期产期i i 545355555759cij=+c(j-i),ij+b(i-j),i jb=2 2