运筹学-运输问题课件.ppt

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

1、第四节 运输问题,Transportation Model,一、运输问题及其数学模型二、表上作业法求解运输问题三、产销不平衡的运输问题及应用,3,问题的提出 运输问题：产地、销地、产量、销量 例1 有A1，A2，A3三座铁矿，每天要把生产的铁矿石运往B1，B2，B3，B4四个炼铁厂。各矿的产量、各厂的销量以及各厂矿间的运价如下表所示。问应如何组织调运才能使运费最少？,运输问题及其数学模型,4,(百元/百吨),xij Ai运给Bj的铁矿石数量（百吨）,z 总运费（百元）,运输问题及其数学模型,5,(百元/百吨),x11,x12,x13,x14,x21,x22,x23,x24,x31,x32,x3

2、3,x34,运输问题及其数学模型,6,数学模型为: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,2,3;j=1,2,3,4),s.t.,运输问题及其数学模型,7,运输模型的特点：(1)它有mn个变量，m+n个约束方程(2)其系数阵具有特殊的结构,m=3行,n=4行,A=,1

3、1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1,8,表式模型,产销平衡的运输问题:ai=bj 产大于销的运输问题:aibj 产小于销的运输问题:aibj,运输问题及其数学模型,运输问题及其数学模型,1、运输问题的网络图、线性规划模型及运输表,设有同一种货物从m个供应地1，2，m运往n个需求地1，2，n。第i个供应地的供应量（Supply）为，第j个需求地的需求量（Demand）为。每单位货物从供应地i运到需求地j的运价为。求一个使总运费最小的运输方案。如果从任一供应地到任一需求地都有道路通行，这样的运输问题称为完全的运输问题；如果总供应量等于总需求量

4、，这样的运输问题称为供求平衡的运输问题。我们先考虑完全的、供求平衡的运输问题。,运输问题及其数学模型,右图是运输问题的网络表示形式。,运输问题及其数学模型,运输问题也可以用线性规划表示。设 为从供应地i运往需求地j的运量，则总运费最小的线性规划问题如下式所示。,运输问题及其数学模型,运输问题线性规划变量个数为nm个，每个变量与运输网络的一条边对应，所有的变量都是非负的。约束个数为m+n个，全部为等式约束。前m个约束是供应地的供应量约束，后n个约束是需求地的需求量约束。运输问题约束的特点是约束左边所有的系数都是0或1，而且每一列中恰有两个系数是1，其他都是0。,运输问题及其数学模型,在运输问题线

5、性规划模型中，令,A=,则运输问题的线性规划可以写成：,运输问题及其数学模型,完全的运输问题系数矩阵A中，列向量 中只有两个元素是1，其他元素都是0。第一个1位于矩阵的第i行，第二个1位于矩阵的第m+j行。这个列向量可以表示为两个单位向量之和，即,运输问题及其数学模型,运输问题除了用网络表示及线性规划表示外，还可以用运输表表示，见右表。运输表是一个m行n列的表格，每一行对应于一个供应地，每一列对应于一个需求地。运输表共有mn个格子，每个格子对应于从一个供应地出发到一个需求地的运输路线。,运输问题及其数学模型,上页表中，每一格的左上角小方格内的数字表明从相应的供应地i到需求地j的运价，每一格右下

6、角表明从相应的供应地i到需求地j的运量。表右方表明各供应地的供应量，表下方表明各需求地的需求量。每一行运量之和表示从该供应地运往各需求地的运量之和，它应该等于该供应地的供应量；同样，每一列运量之和表示从各供应地运往该需求地的运量之和，它应该等于该需求地的需求量。,运输问题及其数学模型,运输问题约束矩阵的性质,A=,分别将A的前m行和后n行相加，得到两个相同的mn维向量，其中的元素都是1。即A矩阵的m+n个行向量是线性相关的，因此A矩阵的秩m+n。运输问题分别从供应地1、2、m到需求地n的m条边以及从供应地1分别到需求地1、2、n-1的n-1条边，一共有m+n-1条边。这m+n-1条边组成运输问

7、题约束矩阵A中的m+n-1个列向量，这些列向量在A矩阵中的子矩阵是一个m+n行，m+n-1列的矩阵,B=,删除矩阵B的最后一行，得到,B=,可以看出，这是一个上三角矩阵，显然，秩Bm+n-1。由m+n-1=秩B秩Am+n-1可以得到，运输问题约束矩阵A的秩为m+n-1。这是运输问题系数矩阵的一个重要性质，由此可知，运输问题的mn个变量中，基变量的个数是m+n-1，非基变量的个数是mn-(m+n-1)=(m-1)(m-1)。,运输问题及其数学模型,基在运输表中的表示,我们已经知道，运输表中的一行对应于一个供应地，一列对应于一个需求地，表中行列相交的一个格子表示从供应地节点到需求地节点的一条边。如

8、果运输网络图中有若干条边组成一个回路，在运输表中，这些边在运输表中相应的格子也构成一个回路。下面是运输问题的网络图中的回路的例子。,运输问题及其数学模型,运输表中的闭合回路,运输问题及其数学模型,运输表中的闭回路还可以出现更复杂的情况，如下表和下图所示。,从运输网络图中一个基应满足的条件，容易得出运输表中一个基必须满足的条件：1、一个基应占表中的m+n-1格；2、构成基的同行同列格子不能构成闭回路；一个基在表中所占的m+n-1个格子应包括表的每一行和每一列。运输问题可以用单纯形法求解，但由于其模型的特殊性，也可以用基于单纯形法思想的表上作业法求解。求解的速度要优于单纯形法。,运输问题及其数学模

9、型,1.确定初始基础可行解（1）最小元素法最小元素法的基本思想是就近供应，即从单位运价表中最小的运价处开始确定供销关系，依次类推，一直到给出全部方案为止。,表上作业法求解运输问题,例 给出运输表如右。最小运价为c33=7，供应地3的供应量为50，需求地3的需求量为31，安排运量x33=31。供应地3和需求地3的供应量和需求量分别变为19和0，同时划掉第三列运价，表示再次考虑最小运价时不再考虑第三列。,表上作业法求解运输问题,表上作业法求解运输问题,对于c32=8，供应地3的供应量为19，需求地2的需求量为20，安排x32=19，供应地3的供应量为0，需求地2的需求量为1。,表上作业法求解运输问

10、题,对于c24=9，安排x24=45，供应地2的供应量为0，需求地4的需求量为39。,表上作业法求解运输问题,对于c11=10，安排x11=15，供应地1的供应量为15，需求地1的需求量为0；,表上作业法求解运输问题,对于c12=11，安排x12=1，供应地1的供应量为14，需求地2的需求量为0；,表上作业法求解运输问题,对于c44=13，安排x44=25，供应地4的供应量为0，需求地4的需求量为14。,表上作业法求解运输问题,最后安排x14=14，所有供应地和需求地的供应量、需求量都等于0。,这样就得到一个运输问题的初始基础可行解。这个初始基础可行解的目标函数值为z=1015+111+151

11、4+945+819+731+1325=1470,（3）vogel法 虽然最小元素法所获得的初始基础可行解往往要优于西北角法所获得的初始解。但最小元素法选取最小运价，可能会局部地区运价较小，但却导致其他地区付出较高的运价作为代价，所以通常得到的不是最优解。Vogel法通过计算行和列的运价差值考虑了全局最优，所获得的结果在精度要求不高的情况下可以作为近似最优解。具体作法是：对每行每列的运价分别计算两最小元素之差（取正值），将“行差”记于表右侧，“列差”记于表下端。在所有行差、列差中选一最大差额，若有几个同时最大，则可任选其一。在最大差额所在行（列）中选一最小运价，若有几个同时最小，则可任选其一。在

12、前面所确定的最小运价格内，确定基变量数值，然后去掉其所在行或列，具体做法同最小元素法。其余未划去的行列重复上述步骤，但当只剩下最后一行（列）时，不再计算行（列）差，而直接按最小元素法分配运量，并去掉相应的行或列。,表上作业法求解运输问题,表上作业法求解运输问题,例 对上述例题用Vogel法求基本可行解。（1）计算每一行每一列两个最小运价的差值，第二行和第三列同时存在两个相同的最小差值3，选取其中最小运价8。对应的变量x32作为相应的基变量。,表上作业法求解运输问题,（2）根据供需值的最小值，确定x32=20，划掉第二列，重新计算相应运价的行差和列差。,表上作业法求解运输问题,（3）重复以上步骤

13、，直到得到基本可行解。,表上作业法求解运输问题,表上作业法求解运输问题,表上作业法求解运输问题,表上作业法求解运输问题,表上作业法求解运输问题,这个初始基础可行解的目标函数值为z=1015+91+1514+945+820+730+1325=1469这个解比用最小元素法求得的结果略小，但如果各个供需地之间运价差值较大，则结果的差异会更明显。由于Vogel法考虑到全局最优，在对精度要求不高的情况下，往往把Vogel得到的解作为近似最优解。,表上作业法求解运输问题,2.计算非基变量的检验数Zij-Cij（1）闭回路法运输问题中的闭回路是指运输问题的一个基本可行解中由一个空格（非基变量）和若干个有数字

14、格（基变量）的水平和垂直连线包围成的封闭回路。构建闭合回路的目的是要计算解中的各非基变量的检验数，方法是令某非基变量取值为1，通过变化原基变量的值找出一个新的可行解，将其同原来的基可行解目标函数的变化比较。,表上作业法求解运输问题,例 针对运输问题的一个基本可行解，求各非基变量检验数。令非基变量x13=1，则由x13找到唯一一个闭回回路。在闭合回路上分别对x13加1，对x12减1，对x22加1，对x23减1。得到新的可行解。见右表,表上作业法求解运输问题,非基变量x13所对应的闭合回路,表上作业法求解运输问题,对非基变量x13取值为1后，得到的新的可行解,注意到该解是可行解，但不是基本可行解。

15、由于除闭合回路外，其他各点的运量没有变化。因此新可行解与原来的解比较，运费变化为：9-11+12-16=-6，称之为检验数。即如果在该位置增加一个单位的运量，整体运费会减少6。因此原基本可行解不是最优解。,用同样的方法可以求得其他非基变量的检验数，并将以上检验数填入运输表，用“”表示。见表,表上作业法求解运输问题,非基变量检验数表,-6,-7,2,-1,-5,-10,-1,-3,-8,表上作业法求解运输问题,由于任意非基变量均可表示为基变量的唯一线性组合，因此通过任一空格可以找到，并且也只能找到唯一的闭合回路。由于运输问题的目标函数是极小化。所以当所有非基变量的检验数均大于等于0时，当前基本可

16、行解是最优解。,表上作业法求解运输问题,对用最小元素法得到的初始基础可行解，也可以用同样的方法求得各非基变量的检验数zij-cij，计算过程略，计算结果见下表,最小元素法所得到的初始基础可行解的检验数表,-1,9,7,12,-2,4,4,4,6,（2）对偶变量法设运输问题的原始问题为：,表上作业法求解运输问题,设与前m个约束对应的对偶变量为u1，u2，um，与后n个约束对应的对偶变量为v1，v2，vn。则对偶问题为：,表上作业法求解运输问题,以上对偶问题，可以简写成：,表上作业法求解运输问题,对偶问题中有m+n个变量，mn个约束。对于运输问题的一个基B，如果能够求出相应的对偶变量W=CBB-1

17、，就可以计算非基变量xij的检验数zij-cij：zij-cij=CBB-1pij-cij=W(ei+em+j)-cij=(ui+vj)-cij 对于一个确定的基，如果xij是基变量，则xij0。由于单纯形叠代在每一步都满足互补松弛条件，因此对于基变量xij0，相应的对偶约束条件ui+vj cij的松弛变量一定等于0，即 ui+vj=cij 由于基变量一共有m+n-1个，因此对偶问题一共有m+n-1个等式约束，只要先确定一个对偶变量的值，就可以由m+n-1个等式约束确定其余m+n-1个对偶变量的值。不妨设vn=0，逐个递推求得ui和vj。求出ui、vj的值以后，就可以进一步计算各非基变量的检验

18、数zij-cij=ui+vj-cij。,3.解的改进（1）确定进基变量由单纯形法原理可以知道，凡检验数zij-cij0的非基变量都可以进基。通常总是选取检验数中最小的对应变量进基。（2）确定离基变量为保证改进后的解仍为基本可行解，需要保证所有变量的非负性。因此，改进的方法就是从检验数为负数的空格出发，作一条除该空格外其余顶点均为有数字格组成的闭合回路。在这条闭回路上，按对运量作最大可能的调整。,表上作业法求解运输问题,表上作业法求解运输问题,例 改进表中用最小元素法得到的初始基本可行解。由表可知，x34的检验数是-2，因此可以作为进基变量。选取变量x34作为进基变量，以其所在的空格为出发点作闭

19、合回路。,选取变量x34作为进基变量相应的闭合回路,表上作业法求解运输问题,将其改进为新的基本可行解。则x34增加的同时，x14减少，x12增加，x32增加。为保证变量的非负性，能够减少的最大数量为14。此时，x14减少到0，是出基变量。得到新的基本可行解见下表,改进后的基本可行解,-1,2,10,5,7,4,4,2,2,表上作业法求解运输问题,上表给出的调运方案是否为最优呢？还需要对这个方案的空格处（非基变量）求出检验数。由于表中x13的检验数为-1，因此对上表进行改进。得到下表。计算表中的检验数。,最优基本可行解 由于检验数表2-38中的所有检验数大于等于0。因此上表是最优方案。,1,3,

20、10,5,6,3,3,2,2,最优解的目标函数值为z=1015+915+945+820+716+1014+1325=1427。需要指出的是，有时在闭合回路调整中，在需要减小运量的地方有两个以上相等的最小数，这样调整时原先空格处填上了这个最小数，而有两个以上最小数的地方成了空格。为了保证基变量的个数是m+n-1个，就要把最小数的空格之一变为空格，其余均补填0，补填0的格为有数字格，对应的变量是基变量。,表上作业法求解运输问题,1供给大于需求的情况，即 增加一个虚设的需求地n+1，它的需求量为。新增从各供应地到该需求地的运输路线（1，n+1），（2，n+1），（m，n+1），这些运输路线上的运价全

21、部等于0，即c1，n+1=c2，n+1=cm，n+1=0，这样就将供给大于需求的的问题转化为供求平衡的问题。在新的问题中，从供应地i到新设的需求地n+1的运量，实际上就是存储在供应地i没有运出的数量。新得到的供求平衡的运输问题的最优解，实际上就是各供应地存储多少、运出多少、运往何地，使总运价最低。,产销不平衡的运输问题及应用,例 设一个供求不平衡的运输问题如下左图。相应的供求平衡问题如图1，2。,产销不平衡的运输问题及应用,图1 供求不平衡的运输问题,图2 供求不平衡的运输问题,由于需求地4是虚拟的，因此对应的运价设为0。供求平衡问题的运输表以及最优解如下：,产销不平衡的运输问题及应用,调整后

22、的运输表及最优解及检验数表,3,4,2,已获得最优解。这个最优解的含义是：从供应地1到需求地2的运量为10，到需求地3的运量为5，供应量没有剩余；从供应地2到需求地1的运量为10，到需求地3的运量为5，供应量剩余10；最小运费为 min z=510+65+710+95=195.,产销不平衡的运输问题及应用,2供给小于需求的情况，即 当市场的总需求量大于总供给量时，可以仿照供给大于需求的情况处理。即增加一个假想的供应地，产量等于供应不足的部分，即。由于假想的供应地并不存在，相应运价就等于0。,59,运输模型的应用,短缺资源的分配问题自来水分配问题,160,110,6 0,210,160,额 外,

23、基 本,2 0,0,5 0,60,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,自来水分配问题的规范表式运输模型,运输模型的应用,61,运输模型的应用,62,转运问题面粉转运问题 设有A1、A2、A3三个面粉加工厂，每天分别将 3、4、3吨面粉运往B1、B2两个糕点厂，而B1、B2每 天分别需要4、6吨面粉。在面粉厂与糕点厂之间有T1、T2两个中继站。各地间每吨面粉的运价如下表所示。应如何调运使

24、总运费最低？,运输模型的应用,63,运输模型的应用,64,1 转运站既是始点，又是终点的运地。转化成为有7个假想产地Ai、7个假想销地Bj的新问题。2 虚设一个统一转运量t，应有t max(ai，bj),假想产地Ai的产量,故可取作,t=10,=10,本例,ai=bj,运输模型的应用,65,本例取作,ai=ai+10bj=bj+10,3 虚设 xii 也是运量，即假想各转运站可以自产自销，则其 真实运量为,假想销地Bj 的销量,t-xii。,不可能运输（即表中标“-”）之处：用大 M 取代；xii 的运价为0；,本例中即10-xii。,4 新问题的运价：,其余不变。,运输模型的应用,66,面粉

25、转运问题的初始方案,3,3,4,4,6,1,1,1,1,1,10,10,10,10,10,10,10,10,10,80,ui,vj,-,+,-,运输模型的应用,67,面粉转运问题的最优方案,运输模型的应用,68,最优方案及最优路线,最少总运费为 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,运输模型的应用,69,生产调度问题拖拉机生产调度问题 前进拖拉机厂与农机供销社签订了一项生产100台某种小型拖拉机的合同。按合同规定，该厂要在今后四个月的每月内交付一定台数的拖拉机。为此，该厂生产计划科根据本厂

26、实际情况列出了一个生产调度表（见下表）。根据此表第二栏（生产能力）的数据，该厂能够提前完成合同总台数，但生产出来的拖拉机若当月不交货，每台存储一个月，由于维修保养和积压资金等缘故，另需费用100元。问该厂应如何拟订最经济的生产进度？,70,运输模型的应用,71,解 设 xij 为第 i 个月生产的、用于第 j 个月交货的拖拉机台数(i，j=1，2，3，4)。若将各产期视为“产地”，各销期视为“销地”，将xij视为“运量”，就能构成一个运输模型。cij 表示第i月生产的用于第j月交货的每台拖拉机的实际费用，它等于第 i 月的单台成本加上 j i 个月的贮存费用(j i).cij=ci+c(j-i),运输模型的应用,72,51,52,53,52,50-52-51-53,M,M,M,M,M,M,53,54,cij=ci+c(j-i),j i,运输模型的应用,73,54,53,55,55,57,59,cij=,ci+c(j-i),ij,ci+b(i-j),i j,b=2,运输模型的应用,