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

《《管理运筹学》课件05-运输模型.ppt》由会员分享，可在线阅读，更多相关《《管理运筹学》课件05-运输模型.ppt（45页珍藏版）》请在三一办公上搜索。

1、第5章 运输模型,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 总运费（百元

2、）,第5章 运输模型,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+x24+x34=4 xij0(i=1

3、,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个约束方程(2)其系数阵具有特殊的结构,m=3行,n=4行,A=,1 1 1

4、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+n-1个，最小元素法有以下三条原则:(1)在确定了某一基变量 xlk及其数值并画圈以后，若它所在的

5、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+n；,(2)再如，当只剩下最后1行/列时:,当画了m+n-2个圈时，未划去的行列总数为,2，,即只剩下1个空格，只能再画1个圈，这样，画圈个数

6、恰为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 表上作业法,二、最大差额法 步骤如下：1对每行每列的运价cij分别计算两最小元素之差(取正值)，将“行差”记于表右侧，“列差”记于表下端。2在所有行差、列差中选一最大

7、差额，若有几个同时最大，则可任选其中 之一。3在最大差额所在行(列)中选一最小运价，若有几个同时最小，则可 任选其一。,4在所确定的最小运价格内，确定基变量数值并画圈，然后划去其所在行 或列，具体做法同最小元素法。5对剩余未划去的行列重复上述步骤，但当只剩下最后一行(列)时，不再 计算行(列)差，而直接按最小元素法分配运量并划去相应的行或列。,第5章 运输模型,19,5.2 表上作业法,行 差,列差,1,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 最优性检验 一、位势

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

9、圈数字的一条封闭回路。,号的顶点称为偶点，而标“”号的顶点称为奇点。奇偶点的确定：,的某一行进方向交错地标记奇偶符号。则,然后沿着闭回路,检验数等于闭回路上偶点的运价总和减去奇点的运价总和。,即,第5章 运输模型,23,5.2 表上作业法,1,2,1,2,2,2,-,-,-,+,+,4,2,3,7,8,3,补表 以最大差额法所确定方案及其闭回路为例,x21的闭回路。,21=7-4+5-3+2-3,=4,第5章 运输模型,24,5.2 表上作业法,5.2.3 非优方案的调整 在进基变量的闭回路上的所有奇点中,选择数值最小的那个作为离基变量,并且取它的值作为调整量。,-,-,+,第5章 运输模型,

10、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章 运输模型,27,5.2 表上作业法,调整非优方案的一般步骤与规则 1进基变量的确定规则 按 min ijij 0=lk 确定xlk进基。若有多个lk同时最小，则选其中最小运价minclk 所对应的那个 xlk进基;又若有多个这样的clk同时最小，

11、则从中任选一个clk对应xlk的 进基。,进而画出进基变量xlk的闭回路及奇偶点。,2离基变量的确定规则 在进基变量xlk的闭回路上，按,确定xpq离基，同时也就确定xpq的值t为调整量。若有多个奇点 xpq 的值同时最小，则选其中最大运价 maxcpq 所对应的那个xpq离基；又若有多个这样的cpq同时最大，则从中任选一个cpq 对应的xpq离基。,第5章 运输模型,28,5.2 表上作业法,3非最优方案的调整规则,不在进基变量闭回路上的xij的值不变。,在进基变量的闭回路上：,第5章 运输模型,29,5.2 表上作业法,5.2.4 产销不平衡问题的解法,第5章 运输模型,30,5.2 表上

12、作业法,第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,160140190,160140190,M,0,130130200,M,220190230,0,170150M,M,170150M,0,自来水分配问题的规范表式运输模型,第5章 运输模型,33,5.3 运输模型的应用,第5章 运输模型,34,5.3 运输

13、模型的应用,5.3.2 转运问题 例5 面粉转运问题 设有A1、A2、A3三个面粉加工厂，每天分别将 3、4、3吨面粉运往B1、B2两个糕点厂，而B1、B2每 天分别需要4、6吨面粉。在面粉厂与糕点厂之间有T1、T2两个中继站。各地间每吨面粉的运价如下表所示。应如何调运使总运费最低？,第5章 运输模型,35,5.3 运输模型的应用,第5章 运输模型,36,5.3 运输模型的应用,1 转运站既是始点，又是终点的运地。转化成为有7个假想产地Ai、7个假想销地Bj的新问题。2 虚设一个统一转运量t，应有t max(ai，bj),假想产地Ai的产量,故可取作,t=10,=10,本例,ai=bj,第5章

14、 运输模型,37,5.3 运输模型的应用,本例取作,ai=ai+10bj=bj+10,3 虚设 xii 也是运量，即假想各转运站可以自产自销，则其 真实运量为,假想销地Bj 的销量,t-xii。,不可能运输（即表中标“-”）之处：用大 M 取代；xii 的运价为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章

15、运输模型,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章 运输模型,41,5.3 运输模型的应用,5.3.3 生产调度问题 例6 拖拉机生产调度问题 前进拖拉机厂与农机供销社签订了一项生产100台某种小型拖拉机的合同。按合同规定，该厂要在今后四个月的每月内交付一定台数的拖拉机。为此，该厂生产计划科根据本厂实际情况列出了一个生产调度表（见下表）。根据此表第二栏（生产能力）的数据，该厂能够提前完成合同总台数，但生产出来的拖拉机若当月

16、不交货，每台存储一个月，由于维修保养和积压资金等缘故，另需费用100元。问该厂应如何拟订最经济的生产进度？,第5章 运输模型,42,5.3 运输模型的应用,第5章 运输模型,43,5.3 运输模型的应用,解 设 xij 为第 i 个月生产的、用于第 j 个月交货的拖拉机台数(i，j=1，2，3，4)。若将各产期视为“产地”，各销期视为“销地”，将xij视为“运量”，就能构成一个运输模型。cij 表示第i月生产的用于第j月交货的每台拖拉机的实际费用，它等于第 i 月的单台成本加上 j i 个月的贮存费用(j i).cij=ci+c(j-i),第5章 运输模型,44,5.3 运输模型的应用,51,52,53,52,50-52-51-53,M,M,M,M,M,M,53,54,cij=ci+c(j-i),j i,第5章 运输模型,45,5.3 运输模型的应用,54,53,55,55,57,59,cij=,ci+c(j-i),ij,ci+b(i-j),i j,b=2,