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

1、一、运输问题及其数学模型一、运输问题及其数学模型二、表上作业法求解运输问题二、表上作业法求解运输问题三、产销不平衡的运输问题及应用三、产销不平衡的运输问题及应用3问题的提出问题的提出 运输问题：产地、销地、产量、销量运输问题：产地、销地、产量、销量 例例1 有有A1，A2，A3三座铁矿，每天要把生产三座铁矿，每天要把生产的铁矿石运往的铁矿石运往B1，B2，B3，B4四个炼铁厂。各矿的四个炼铁厂。各矿的产量、各厂的销量以及各厂矿间的运价如下表所示。产量、各厂的销量以及各厂矿间的运价如下表所示。问应如何组织调运才能使运费最少？问应如何组织调运才能使运费最少？运输问题及其数学模型运输问题及其数学模型

2、4B1 B2 B3 B4产量产量A1A2A36 3 2 57 5 8 43 2 9 7523销量销量2 3 1 4(百元百元/百吨百吨)xij Ai运给运给Bj的铁矿石数量（百吨）的铁矿石数量（百吨）z 总运费（百元）总运费（百元）运输问题及其数学模型运输问题及其数学模型5B1B2B3B4产量产量A163255A275842A332973销量销量2314(百元百元/百吨百吨)x11x12x13x14x21x22x23x24x31x32x33x34运输问题及其数学模型运输问题及其数学模型6 数学模型为数学模型为:min z=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4

3、x24 +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 1 1 1 1 1 1 1 1

4、 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8表式表式模型模型 产销平衡产销平衡的运输问题的运输问题:aai i=bbj j 产大于销产大于销的运输问题的运输问题:aai ibbj j 产小于销产小于销的运输问题的运输问题:aai ibbj jB1B2Bn 产量产量 A1c11 x11c12 x12c1n x1n a1A2c21 x21c22 x22c2n x2na2Amcm1 xm1 cm2 xm2 cmn xmnam销量销量b1b2bn aib bj运输问题及其数学模型运输问题及其数学模型运输问题及其数学模型运输问题及其数学模型1 1、运输问题的网络图、线性规划模型及运输

5、表、运输问题的网络图、线性规划模型及运输表设有同一种货物从设有同一种货物从m m个供应地个供应地1 1，2 2，m m运往运往n n个需个需求地求地1 1，2 2，n n。第。第i i个供应地的供应量（个供应地的供应量（SupplySupply）为为 ，第，第j j个需求地的需求量（个需求地的需求量（DemandDemand）为为 。每单位货物从供应地。每单位货物从供应地i i运到需求地运到需求地j j的的运价为运价为 。求一个使总运费最小的运输方案。如果。求一个使总运费最小的运输方案。如果从任一供应地到任一需求地都有道路通行，这样的从任一供应地到任一需求地都有道路通行，这样的运输问题称为完全

6、的运输问题；如果总供应量等于运输问题称为完全的运输问题；如果总供应量等于总需求量，这样的运输问题称为供求平衡的运输问总需求量，这样的运输问题称为供求平衡的运输问题。我们先考虑完全的、供求平衡的运输问题。题。我们先考虑完全的、供求平衡的运输问题。)0(iiss)0(jjddijc运输问题及其数学模型运输问题及其数学模型1inj1m1sisndjd1dnc1jc111c1 icijcinc1mcmjcmncms 右图是运输问题的网络表示形式。运输问题及其数学模型运输问题及其数学模型运输问题也可以用线性规划表示。设 为从供应地i运往需求地j的运量，则总运费最小的线性规划问题如下式所示。ijxnjmi

7、xdxxxdxxxdxxxsxxxsxxxsxxxstxcxcxcxcxcxcxcxcxczijnmnnnnnmmnnnnnmnmnmmmmnnnn 1,1,0min2122221211211121222221111211221122222221211112121111运输问题及其数学模型运输问题及其数学模型运输问题线性规划变量个数为nm个，每个变量与运输网络的一条边对应，所有的变量都是非负的。约束个数为m+n个，全部为等式约束。前m个约束是供应地的供应量约束，后n个约束是需求地的需求量约束。运输问题约束的特点是约束左边所有的系数都是0或1，而且每一列中恰有两个系数是1，其他都是0。运输问题及

8、其数学模型运输问题及其数学模型在运输问题线性规划模型中，令),.,(212222111211mnmmnnxxxxxxxxxX ),.,(212222111211mnmmnncccccccccC 列列列列列行nnnnnm111111111111111111A=),(2121nmdddsssb 则运输问题的线性规划可以写成：运输问题及其数学模型运输问题及其数学模型完全的运输问题系数矩阵A中，列向量 中只有两个元素是1，其他元素都是0。第一个1位于矩阵的第i行，第二个1位于矩阵的第m+j行。这个列向量可以表示为两个单位向量之和，即ijpjmiijeejmip010000100110行第行第运输问题及

9、其数学模型运输问题及其数学模型 运输问题除了用网络表示及线性规划表示外，还可以用运输表表示，见右表。运输表是一个m行n列的表格，每一行对应于一个供应地，每一列对应于一个需求地。运输表共有mn个格子，每个格子对应于从一个供应地出发到一个需求地的运输路线。12n12 m1s2snd2d1dms11c12cnc121c22cnc21mc2mcmnc11x12xnx121x22xnx21mx2mxmnx运输问题及其数学模型运输问题及其数学模型 上页表中，每一格的左上角小方格内的数字表明从相应的供应地i到需求地j的运价 ，每一格右下角表明从相应的供应地i到需求地j的运量 。表右方表明各供应地的供应量 ，

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

11、一共有m+n-1条边。这m+n-1条边组成运输问题约束矩阵A中的m+n-1个列向量，这些列向量在A矩阵中的子矩阵是一个m+n行，m+n-1列的矩阵 列列行行1nmnm001111111111)1n,1()1,1()n,m()n,2()n,1(B=删除矩阵B的最后一行，得到 1n1m211n1m211111111B=可以看出，这是一个上三角矩阵，显然，秩Bm+n-1。由m+n-1=秩B秩A0。由于单纯形叠代在每一步都满足互补松弛条件，因此对于基变量xij0，相应的对偶约束条件ui+vj cij的松弛变量一定等于0，即 ui+vj=cij 由于基变量一共有m+n-1个，因此对偶问题一共有m+n-1

12、个等式约束，只要先确定一个对偶变量的值，就可以由m+n-1个等式约束确定其余m+n-1个对偶变量的值。不妨设vn=0，逐个递推求得ui和vj。求出ui、vj的值以后，就可以进一步计算各非基变量的检验数zij-cij=ui+vj-cij。3.解的改进（1）确定进基变量 由单纯形法原理可以知道，凡检验数zij-cij0的非基变量都可以进基。通常总是选取检验数中最小的对应变量进基。（2）确定离基变量 为保证改进后的解仍为基本可行解，需要保证所有变量的非负性。因此，改进的方法就是从检验数为负数的空格出发，作一条除该空格外其余顶点均为有数字格组成的闭合回路。在这条闭回路上，按对运量作最大可能的调整。表上

13、作业法求解运输问题表上作业法求解运输问题表上作业法求解运输问题表上作业法求解运输问题12341101191530151142131216945453118710501931414131213252515203184例 改进表中用最小元素法得到的初始基本可行解。由表可知，x34的检验数是-2，因此可以作为进基变量。选取变量x34作为进基变量，以其所在的空格为出发点作闭合回路。选取变量x34作为进基变量相应的闭合回路 表上作业法求解运输问题表上作业法求解运输问题12341101191530151521312169454531187105053114414131213252515203184将其改进

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

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

16、2，n+1），（m，n+1），这些运输路线上的运价全部等于0，即c1，n+1=c2，n+1=cm，n+1=0，这样就将供给大于需求的的问题转化为供求平衡的问题。在新的问题中，从供应地i到新设的需求地n+1的运量，实际上就是存储在供应地i没有运出的数量。新得到的供求平衡的运输问题的最优解，实际上就是各供应地存储多少、运出多少、运往何地，使总运价最低。niimiids11产销不平衡的运输问题及应用产销不平衡的运输问题及应用niimiids11例 设一个供求不平衡的运输问题如下左图。相应的供求平衡问题如图1，2。产销不平衡的运输问题及应用产销不平衡的运输问题及应用图1 供求不平衡的运输问题 图2 供

17、求不平衡的运输问题 由于需求地4是虚拟的，因此对应的运价设为0。供求平衡问题的运输表以及最优解如下：产销不平衡的运输问题及应用产销不平衡的运输问题及应用12341856015105271090251051010101010调整后的运输表及最优解及检验数表 342 已获得最优解。这个最优解的含义是：从供应地1到需求地2的运量为10，到需求地3的运量为5，供应量没有剩余；从供应地2到需求地1的运量为10，到需求地3的运量为5，供应量剩余10；最小运费为 min z=510+65+710+95=195.产销不平衡的运输问题及应用产销不平衡的运输问题及应用 2供给小于需求的情况，即 当市场的总需求量大

18、于总供给量时，可以仿照供给大于需求的情况处理。即增加一个假想的供应地，产量等于供应不足的部分，即 。由于假想的供应地并不存在，相应运价就等于0。niimiids11niimiisd1159运输模型的应用运输模型的应用短缺资源的分配问题短缺资源的分配问题自来水分配问题自来水分配问题 额额 外外 基基 本本60 50C60B50A供供水水量量引水引水 区区 管理费管理费水库水库(虚虚)甲甲 甲甲1甲甲2需需 求求 量量 乙乙 丙丙 丁丁 丁丁1丁丁2160140190160140190M130130200M220190230170150MM170150M自来水分配问题自来水分配问题的的运输模型的应

19、用运输模型的应用61210501030702030需求量需求量502030脱销脱销5002030C60301020B5050A供水量供水量丁丁2 2丁丁1 1丙丙乙乙甲甲2 2甲甲1 1分配量分配量水库水库区区的的运输模型的应用运输模型的应用62转运问题转运问题面粉转运问题面粉转运问题 设有设有A1、A2、A3三个面粉加工厂，每天分别将三个面粉加工厂，每天分别将 3、4、3吨面粉运往吨面粉运往B1、B2两个糕点厂，而两个糕点厂，而B1、B2每每 天分别需要天分别需要4、6吨面粉。在面粉厂与糕点厂之间有吨面粉。在面粉厂与糕点厂之间有T1、T2两个中继站。各地间每吨面粉的运价如下表所示。两个中继站

20、。各地间每吨面粉的运价如下表所示。应如何调运使总运费最低？应如何调运使总运费最低？运输模型的应用运输模型的应用63 9 9 2 3 6 4B1B2糕糕点点厂厂 2 5 2 6 7 3 5 2 3 2T1T2中中继继站站 6 813 711 4 3 5 2 3 2 3 2 4 2 2A1A2A3面面粉粉厂厂 B1 B2 T1 T2 A1 A2 A3 糕点厂糕点厂 中继站中继站 面面 粉粉 厂厂 终点终点 始点始点运输模型的应用运输模型的应用64 1 转运站转运站既是既是始点始点，又是，又是终点终点的运地。的运地。转化成为有转化成为有7 7个假想产地个假想产地Ai、7 7个假想销地个假想销地Bj的

21、的新问题新问题。2 虚设一个统一转运量虚设一个统一转运量t，应有，应有t max(ai，bj)ai+t，Ai 是是转运站转运站 ai，否则否则ai=假想产地假想产地Ai的产量的产量故可取作故可取作t=10=10本例本例 ai=bj运输模型的应用运输模型的应用65bj+t，Bj 是是转运站转运站 bj，否则否则bj=本例取作本例取作ai=ai+10bj=bj+10 3 虚设虚设 xii 也是运量，即假想各也是运量，即假想各转运站转运站可以自产自销，则其可以自产自销，则其 真实运量为真实运量为假想销地假想销地Bj 的销量的销量t -xii。不可能运输（即表中标不可能运输（即表中标“-”）之处：用大

22、）之处：用大 取代取代；xii 的的运价运价为为0；本例中即本例中即10-xii。4 新问题新问题的的运价运价：其余不变。其余不变。运输模型的应用运输模型的应用66 面粉转运问题的面粉转运问题的销销 量量B2B1T2T1A3A2A1产产量量 B2B1T2T1A3A2A1产地产地销地销地334461010101010101010109 3 4 9 2 6 27 3 3 5 6 2 5 3 4 11 2 3 2 7 13 2 5 2 4 8 6 3 2 3 2 M M M M MMM M M M 0 0 0 0 0 0 0 uivj3 13300 10 10 10 10 10 10 10 3 5

23、M-4 8 M+7 M 15 M+8 4M+10M+13 12 M-8 1 5 8 M-2 9 12 10 167 1 0 -5 5 M-4 -3 -6-1 -3 8 M+2 -1 6 10 +运输模型的应用运输模型的应用67 面粉转运问题的面粉转运问题的最优方案最优方案8016141010101010销销 量量100 9 83 5M M+14 8M M+4M M+4B2-4109 100 M M+32 4M M+5M M+56 11B1-5102M M-30 7 63 53 5M M+2T2-2105 426 70 2 55 83 6T1-313411 62 03 0 2 2M MA3014

24、7 313 84 5 22 20 4 4A20138 4 6 1M M-23 2 23 30 A10B2B1T2T1A3A2A1产产量量4523000 vj 销地销地 ui 产地产地36442614 10 10 10 10 10运输模型的应用运输模型的应用68 最优方案及最优路线最优方案及最优路线 最少总运费为最少总运费为 z*=33+24+31+42+24+24=44(元元)A1B1T1A2T2A3B23吨吨4吨吨3吨吨4吨吨6吨吨341244运输模型的应用运输模型的应用69生产调度问题生产调度问题拖拉机生产调度问题拖拉机生产调度问题 前进拖拉机厂与农机供销社签订了一项生产前进拖拉机厂与农机

25、供销社签订了一项生产100台某种台某种小型拖拉机的合同。按合同规定，该厂要在今后四个月的每小型拖拉机的合同。按合同规定，该厂要在今后四个月的每月内交付一定台数的拖拉机。为此，该厂生产计划科根据本月内交付一定台数的拖拉机。为此，该厂生产计划科根据本厂实际情况列出了一个生产调度表（见下表）。根据此表第厂实际情况列出了一个生产调度表（见下表）。根据此表第二栏（生产能力）的数据，该厂能够提前完成合同总台数，二栏（生产能力）的数据，该厂能够提前完成合同总台数，但生产出来的拖拉机若当月不交货，每台存储一个月，由于但生产出来的拖拉机若当月不交货，每台存储一个月，由于维修保养和积压资金等缘故，另需费用维修保养

26、和积压资金等缘故，另需费用100元。问该厂应如何元。问该厂应如何拟订最经济的生产进度？拟订最经济的生产进度？70130100合合 计计 5000 5200 5100 5300 30 35 45 20 15 25 35 25 单台成本单台成本（元）（元）生产能生产能力（台）力（台）合同规合同规定交付定交付台台 数数 月月 份份运输模型的应用运输模型的应用71 解解 设设 xij 为第为第 i 个月生产的、用于第个月生产的、用于第 j 个月交货的拖拉机台数个月交货的拖拉机台数(i，j=1，2，3，4)。若将各。若将各产期产期视为视为“产地产地”，各，各销期销期视为视为 “销地销地”，将，将xij视

27、为视为“运运量量”，就，就能构成一个运输模型。能构成一个运输模型。cij 表示第表示第i月生产的用于第月生产的用于第j月交货的每台拖拉机的实月交货的每台拖拉机的实际费用，它等于第际费用，它等于第 i 月的单台成本加上月的单台成本加上 j i 个月的贮存费用个月的贮存费用(j i).cij=ci+c(j-i)130100 15 25 35 25 销销 量量30354520 c11 c12 c13 c14 c21 c22 c23 c24 c31 c32 c33 c34 c41 c42 c43 c44 产产 量量 销期销期i i 产期产期j j运输模型的应用运输模型的应用72 130100 15 25 35 25 bj30354520 ai cij j i 51525352 50 -52 -51 -53MMMMMM5354cij=ci+c(j-i),j i运输模型的应用运输模型的应用73 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运输模型的应用运输模型的应用